What is max-sum / max-product variant of loopy BP computing?

Question

In (Nowazin and Lampert, Structured Learning and Prediction in Computer Vision, p. 29.), they say that in the max-sum variant of loopy belief propagation, the "variable max-beliefs are no longer interpretable as marginals but instead $\mu_i(y_i)$ describes the maximum negative energy achievable when fixing the variable $Y_i = y_i$."

I understand that to mean that if we set $Y_i = y_i$, the maximum negative energy that the MRF can achieve across all variable assignments to other nodes (with $Y_i = y_i$ being fixed) is $\mu_i(y_i)$. Is that correct?

In the next paragraph, they say: to recover a joint minimum energy labeling, we select for each variable $Y_i$ the state $y_i \in \mathcal{Y}_i$ with the maximum max-belief,

$y_i^* = \text{argmax}_{y_i \in \mathcal{Y}_i} \mu_i(y_i) \text{ } \forall i \in V$.

How is this a joint minimum energy labelling? I don't see how this chooses the $y_i$ such that their pair-wise interaction terms are considered. It looks like it considers each on its own, selecting the $y_i$ such that the selection of the other variables could result in a maximum given that selection of $y_i$, but then it goes on to select the other $y$ locally as well, without consideration of this $y_i$.

Is this "joint minimum energy labelling" not a global minimum energy labelling? If not what is meant by "joint"?

Answer 1

You are correct about the max-marginal $\mu_i(y_i)$ being the maximum achievable neg-energy with $y_i$ fixed.

Indeed, you can obtain the labelling $\mathbf{y}$ that minimizes the energy globally (jointly) by maximizing individual max-marginals iff those max-marginals are unambiguous (i.e. all maximums are unique) [Koller and Friedman, 2009; Proposition 13.3]. Pairwise factors are already accounted during the computation of max-marginals (so, estimation of max-marginals is not a simple problem itself, see below).

However, there may be problems in practice. First, sometimes you need to work with distributions/energies where max-marginals can be ambiguous by design (say, in case of deterministic relations). In this case the problem is called decoding max-marginals, and is quite difficult. Second, unless you work with tree-structured graphs (or low-treewidth ones), you can estimate max-marginals only approximately. Thus, the assignment obtained by local maximization is only approximately optimal anyway. See [Koller and Friedman, 2009; sections 13.2.2 and 13.3.3] for more details.