I desperately need your help. I have to understand the sequential tree-reweighted message passing algorithm proposed by Kolmogorov [1] for energy minimization. I tried to understand it, but I have no real "Aha moment", so I hope that someone of you, has already understood it and could explain the algorithm to me step by step.
Here is what I understood so far:
If we have a undirected graph where each node can be assigned a label $l_1 \in \{0,1\}$ and only two clique potential functions are considered, then the algorithm first does a LP relaxation. I.e. instead of assigning each node a label $l_1 \in \{0,1\}$, it now assigns them a label from $l_1 \in [0,1]$. Initially, the assignment of labels to nodes is random, e.g. $n_1 = \begin{pmatrix}0.3\\0.2\end{pmatrix}$
As I understand it, the next step then is to divide the given graph into acyclic subgraphs (trees). Now, on each tree Belief Propagation is applied, which gives a vector of belief values for each label, e.g. $\begin{pmatrix}0.8\\0.3\end{pmatrix}$. So in this case label 0 is more likely than label 1.
Since one node can be part of many trees, it can have several vectors assigned to it, thus, all values of the different vectors are averaged for one node. Finally, each node has only one vector from which the final label can be derived as explained above.
I don't really understand the reparametrization step that is mentioned in the cited work of Kolmogorov. It would also be nice, if you could tell me, how BP updates the messages, since Kolmogorov does not mention it in his work. How is the BP update related to the energy function?
I would appreciate any kind of help! Thanks.
[1] Kolmogorov, Vladimir. "Convergent tree-reweighted message passing for energy minimization." IEEE transactions on pattern analysis and machine intelligence 28.10 (2006): 1568-1583.
