What is max-sum / max-product variant of loopy BP computing? 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"?
 A: 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.
