##### Differences

This shows you the differences between two versions of the page.

 cs-677sp2010:clique-trees [2014/12/11 16:35]ryancha cs-677sp2010:clique-trees [2014/12/11 16:36] (current)ryancha Both sides previous revision Previous revision 2014/12/11 16:36 ryancha 2014/12/11 16:35 ryancha 2014/12/11 16:34 ryancha 2014/12/11 16:33 ryancha 2014/12/11 16:32 ryancha 2014/12/11 16:22 ryancha 2014/12/11 16:21 ryancha 2014/12/09 09:51 ryancha created 2014/12/11 16:36 ryancha 2014/12/11 16:35 ryancha 2014/12/11 16:34 ryancha 2014/12/11 16:33 ryancha 2014/12/11 16:32 ryancha 2014/12/11 16:22 ryancha 2014/12/11 16:21 ryancha 2014/12/09 09:51 ryancha created Line 60: Line 60: Fig.5 Message passing Fig.5 Message passing - In Fig.5, for example, the clique $C_2(G,​I,​D)$ ​ generates a factor ( message ) by multiplying the message$\delta_{1 \overrightarrow ​2}(D)$ ​  from $C_1$  with its initial potential $\pi^0_2(G,​I,​D)$ ​ and then summing out the variable D. The resulting factor ( message ) which has a scope G, I, is then sent to clique $C_3(G,​S,​I)$ . + In Fig.5, for example, the clique $C_2(G,​I,​D)$ ​ generates a factor ( message ) by multiplying the message$\delta_{1 \rightarrow ​2}(D)$ ​  from $C_1$  with its initial potential $\pi^0_2(G,​I,​D)$ ​ and then summing out the variable D. The resulting factor ( message ) which has a scope G, I, is then sent to clique $C_3(G,​S,​I)$ . We say that a clique is ''​ready''​ when it has received all of its incoming messages. Thus, in this example, we could see that $C_4$ is ''​ready''​ at the very start of the algorithm, and the computation associated with it can be performed at any point in the execution. We say that a clique is ''​ready''​ when it has received all of its incoming messages. Thus, in this example, we could see that $C_4$ is ''​ready''​ at the very start of the algorithm, and the computation associated with it can be performed at any point in the execution. Line 79: Line 79: ===Calibrated Clique Tree=== ===Calibrated Clique Tree=== - * Define a term, belief ​ $\beta_i(C_i)=\pi^0_i \prod_{k \in Nb_i} \delta_{k \overrightarrow ​i}$ + * Define a term, belief ​ $\beta_i(C_i)=\pi^0_i \prod_{k \in Nb_i} \delta_{k \rightarrow ​i}$ * Two adjacent cliques $C_i$  and $C_j$  are said to be ''​calibrated''​ if $\sum_{C_i - S_{i,j}} \beta_i(C_i) = \sum_{C_j - S_{i,j}} \beta_j(C_j)$ ​ * Two adjacent cliques $C_i$  and $C_j$  are said to be ''​calibrated''​ if $\sum_{C_i - S_{i,j}} \beta_i(C_i) = \sum_{C_j - S_{i,j}} \beta_j(C_j)$ ​ * A clique tree is ''​calibrated''​ if all pairs of adjacent cliques are ''​calibrated''​. * A clique tree is ''​calibrated''​ if all pairs of adjacent cliques are ''​calibrated''​. Line 90: Line 90: An alternative approach to computing the message is to multiply in all of the messages and then divide the resulting factor by returning message. ​ An alternative approach to computing the message is to multiply in all of the messages and then divide the resulting factor by returning message. ​ - $\delta_{i \overrightarrow ​j} = \dfrac{\sum_{C_i - S_{i,j}} \beta_i(C_i)}{ \delta_{j \overrightarrow ​i}}$ + $\delta_{i \rightarrow ​j} = \dfrac{\sum_{C_i - S_{i,j}} \beta_i(C_i)}{ \delta_{j \rightarrow ​i}}$