M.J. Wainwright, T.S. Jaakkola, A.S.Willsky

the basic idea is to use a convex combination of tree-structured distributions to derive upper bound on the cost of a MAP configuration.

翻译：论文的基本思想是使用树形结构分布的凸组合来获取MAP问题的上界

本文的着眼点在于如何找到一个比较紧的上界，为此提出了两种算法：

1）第一种方法根据上界的凸性以及拉格朗日对偶的相关理论。首先把在有环图上的MAP问题转化为在marginal polytope上的linear program(LP)问题，然后考虑最优化上界问题的拉格朗日对偶。事实上，这个对偶问题其实也是一个linear program(LP)问题，并且有一个很自然的解释，它可以看做是精确MAP问题的LP问题的松弛！松弛是这样得到的：把有环图的marginal polytope松弛为outer bound上的一个较简单的结构。the outer bound is an exact characterization of the marginal polytope of any tree-structured distribution, for which reason we refer to this approach as a tree-based LP relaxation.

2）第二种方法包含一类信息传播方法，目标是找到一系列共享最优值的树形结构分布。

本篇论文建立起如下两者之间的联系：

1）整数规划问题的LP松弛

2）使用max-product算法中消息传播的动态规划方法

section 2: graph theory, graphical models, marginal polytopes, formulation of MAP estimation problem

marginal polytope ===== locally consistent polytope

$(1)MARG(G) := \{\mu \in R^d | \mu_{s;j} = E_p[\delta_j(x_s)], \mu_{st;jk} = E_p[\delta_j(x_s)\delta_k(x_t)]\}$

$(2)\sum_{j \in X_s}\mu_{s;j} = 1, \forall s \in V$

$(3)\sum_{(j,k) \in X_s*X_t}\mu_{st;jk} = 1, \forall (s,t) \in E$

$(4)\sum_{k \in X_t}\mu_{st;jk} = \mu_{s;j}, \forall (s,t) \in E, j \in X_s $

满足公式(2),(3),(4)的称为$LOCAL(G)$

MAP问题的定义：

A.

$\arg\max_\theta P(\theta | D) =  \arg\max_\theta P(\theta,D)/P(D) = \arg\max_\theta P(\theta)P(D|\theta)/P(D) = \arg\max_\theta P(\theta)P(D|\theta)$

在频率学派中，$\theta$被视为未知的常量，极大似然估计用于求出这个常量

在贝叶斯估计中，$\theta$被视为变量，其中$P(\theta)$是先验概率，$P(\theta|D)$是后验概率

B.

MAP问题等价于找到$x_{MAP} \in X^n $使得下式最大化：

$<\theta,\phi(x)> := \sum_{s \in V}\theta_s(x_s) + \sum_{(s,t) \in E}\theta_{st}(x_s,x_t)$

尽管$\theta$在这里是一个已知的常数，但为了分析方便，论文中把它看做是一个变量，并且定义了如下的函数：

$\psi_{\infty}(\theta) = \max_{x \in X^n}<\theta,\phi(x)>$

section 3:

section 4:

section 5:

section 6:

section 7: