这部分讨论 MAP 估计。从某个角度上来说，我们可以将这个问题转换成为前面讨论过的：

这样一来我们只需要将原先的 sum-product 换成 max-sum 即可。话虽这么说，我们还是看看 Koller 同学给大家准备了些什么东西。

首先是一些复杂性方面的结论，如给定一个 BN 和常数 ，问是否存在 。这个 decision 问题（BN-MAP-DP）是 NP-hard 的，这导致 marginal 版本也是 NP-hard 的，事实上 marginal 版本在某种意义上更难一些，即是 -complete（这个大概的意思可以从这个 wiki page 上推测出来），更直接的证据是，即便是对 polytree，对应的 decision problem 仍然是 NP-hard 的。

为了更好地说明一些算法，我们可以先为一些这类问题里面的对应概念起个名字，比如 margin 可以对应于 max-margin：对应于给定部分变量后最大的概率（可以对一般的函数类似的定义）。利用 max-margin，我们也可以为 MAP 导出 variable elimination 算法（每次乘几个 factor，然后对某个变量取 max），这个流程和求 margin 的 VE 是完全一样的，影响该算法效率的也是对应 clique tree 的 width。MAP 里面需要的很多时候并不是“最大后验概率的数值”本身，而是随机变量的值，这个过程一般称为 decoding，如信息论/编码理论里面比较强调的解码就可以看成 MAP 的一种特例。decoding 一般有一个回溯的过程，也就是获得了最大值之后一个变量一个变量带回求得所有的赋值的过程。

对于 marginal MAP 我们往往需要先做求和获得 margin，然后在 margin 上重复以上过程。但事实上即便是形如 HMM 但是将生成观测部分的依赖关系反过来获得的 polytree 也会有 exponential time 求解 marginal MAP 问题的时间开销。

除了 belief propagation 可以沿用以外，belief update 的参数化也可以用在这里。为此我们首先引入 max-calibrated 概念，即两个 cluster graph 中 node 的 max-margin 在 sep set 部分的 max-margin 是 agree 的。事实上我们也只需要对原来的算法稍加修改（将 换掉，原先 sum 变成 max 即可），同时令人吃惊的是此时的 belief update 仍然能保证这个 parameterization 和原分布的 factor 乘积一致。这个地方我们知道其实是 tree 上做 dynamic programming 的一个例子，那么它也满足所谓的全局最优导致的局部最优，即 MAP 的解也能最大化每个 max-belief。

类似 BP 在有环的 cluster graph 上的应用，这里我们也可以将这类算法应用到该情况下的 MAP，这时收敛的解称为 pseudo-max-marginals。一般来说，尽管获得的解并非全局最优，但可以是 strong local maxima，因此仍然有较高概率（仍然是比较合理的解）。类似 Bethe energy approximation，这个算法也可以看成是某个自由能最大化对应 stationary point 求解 fixed point equation 的过程。

另一个有意思的视角是将 MAP 转换成为整数线性优化问题（integer linear programming），这个可以简单的将目标后验取 log，变成几个 factor 对数之和，那么为每个 factor 对应的表构造一个取值乘以 log 概率的和就能得到最原始的线性规划目标函数了，只是我们还需要 local 的赋值与其他的要 compatible，这就是约束，或者我们直接用无约束的形式也可以。这个 ILP 仍然是难的，常见的 relaxation 是将取值这个 函数变成 取值的，这就得到了 linear programming。往往在这种松弛下，我们需要额外的信息帮助我们剔出掉一些不合理的解。一种是在 energy 中的熵上乘以温度，当温度足够低的时候的解是我们需要的（可以理解成为一种 regularizer？）这个解释如果从 log 域转换回来，对应的是将 max-product 当做 sum-product 在温度足够低时的极限。

一种神奇情况下的解（精确解！），是对 pairwise Markov network 且变量取 0-1 值的情况，这时的 MAP 还能转换成为 graph cut从而可以被诸如 min-cut 算法获得精确解。这种情况可以用所谓的 submodular energy function 来定义，如果 ，这时每条边的 loss 其实是 log-linear model 的系数（诡异，后面看文献吧）。非 binary 的情况一般就变成难的问题了，常用的技术是 alpha-expansion 和 alpha-beta-swap。这块 mm 应该最熟悉了！

最后一系列解决方案是暴力的搜索，说是暴力其实也有一定的技巧比如 branch and bound、beam search 等等。下面是需要察看的文献：

• correspondence/data association：find a matching via graph cut or max flow，3D cell reconstruction，NIPS 2006
• mesh registration，NIPS 2004
• associative potentials，graph cut，CVPR 2003
• dual decomposition for MAP，好像这方面的资料挺多的，比如这篇 standord 的，MIT 的，Columbia 的和 CMU 的。这部分似乎书上没 cover？

——————
For Sarah conceived, and bore Abraham a son in his old age, at the set time of which God had spoken to him.