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

Both sides previous revision Previous revision | |||

cs-677sp2010:clique-trees [2014/12/11 23:35] ryancha |
cs-677sp2010:clique-trees [2014/12/11 23:36] (current) ryancha |
||
---|---|---|---|

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}} $ |