机器学习&数据挖掘笔记_PGM练习四：图模型的精确推理

前言：

　　这次实验完成的是图模型的精确推理。exact inference分为2种，求边缘概率和求MAP，分别对应sum-product和max-sum算法。这次实验涉及到的知识点很多，不仅需要熟悉图模型的representation，而且还需明白图模型的inference理论，大家可参考coursera课程：Probabilistic Graphical Models 的课件和视频。多花点功夫去理解每行代码，无形之中会收获不少。新年第一篇博客，继续加油！

算法流程：

　　Sum-product求条件概率过程为(inference I)：

　　(a): 输入factor list F、观察到的变量E

　　(b): 由F中的factor得到graph所对应的skeleton C.

　　(c): 依次进行变量消除，首先在图C中采用min-neighbors方法找到需要消除的变量。然后进行消除(其实就是factor的求和积分)，消除过程中会用掉一些factor，同时也会生成一个新的factor(注意对新的factor补全各节点之间的边)。每消除一个变量就会得到一个clique，同时更新该clique与前面已得clique之间的edge情况。步骤c一直进行直到所有的变量都被消除掉。结束后得到一棵clique tree.

　　(d): 由于上面的tree中有冗余的clique(即某个clique可能是其相邻clique的子集)。这时需将这2个clique合并，该过程也称为树的剪枝：首先去点冗余的clique节点，然后将其sepset节点与该冗余节点其它所有邻节点都连接上边。

　　(e): 前面步骤得到的是clique tree skeleton，还需要对每个clique算出其factor表格，由于clique中对应的子factor信息已掌握，所以直接factor相乘即可(注意观察变量E).该步骤完成后就真正得到了一棵clique tree了。

　　(f): 接着对上面的clique tree进行message passing. 首先选出一个message通道，即找到那些clique i，和其连接的cliques中，只剩下一个clique j没有与之传递消息了，那么(I-->j即为通道)。不过这还是得按照某种节点顺序进行。

　　(g): 计算clique i发射到clique j的message,采用的方法是求和积分掉非公共元素。

　　(h): 当clique tree中所有的message都传递完成后，clique tree就变成calibrate了，而calibrate具有很多良好的性质，首先可以获得calibrate时每个clique的belief.

　　(i): 如果要求某个变量的边缘概率，则找到包含该变量的一个clique(随便哪个都行)，在该clique上，对其belief求和积分掉其它所有变量，然后归一化即可。

　　Max-sum求概率最大时的assignment过程为(inference II)：

　　(a)~(e): 和sum-product过程一样。

　　(f): 将factorlist中的val都取log值。因为需要将max-product转换成对应的max-sum问题。

　　(g): 和sum-product一样，对clique tree进行message passing. 首先选出一个message通道(I→j).

　　(h): 计算(I→j)之间的message. 采用的方法是max掉非公共元素。

　　(i): 当clique tree中所有的message都传递完成后，clique tree就变成calibrate了，采用factorsum计算每个clique的belief.

　　(j): 如果要求某个变量的max-marginal，则找到包含该变量的一个clique(随便哪个都行)，在该clique上，max掉其belief 上其它所有变量，此时不需要归一化。

　　(k): 通过步骤j，可以得到每个变量的max-marginal factor，找到需要assigment中元素对应的factor，取出其val中最大概率值对应的var，组合在一起为最终的结果。

　　Belief propagation流程如下：

　　matlab知识：

　　C = unique(A):

　　如果A是向量，则C表示去掉了A中重复的元素(只保留1个)。

　　C = union(A,B):

　　如果A和B是向量，则C为A和B的并集，且去掉了重复的元素(只保留1个)。

　　在matlab中，true只表示数字1,其它非1的数都不能表示，而false只表示0.所以其它整数既等于false也不等于true.

　　实验code中一些函数简单说明：

　　P = ComputeInitialPotentials(C):

　　练习1所需完成的内容。该函数的作用是计算clique tree P的初始势能。其中C是P的骨架部分(骨架的意思是有clique节点，但是没有clique对应的factor，而这个函数的主要功能就是给每个clique都弄一个factor表)，C结构体包括节点nodes(每个node都是一个clique)，边之间的关系edges, 以及factor集合factorList. 返回的P结构包含2部分，clique tree节点之间边的edges, 以及clique集合cliqueList, 该集合的每个clique形式和factor是一样的，其计算方法是：计算factorList中属于同一个clique的factor的乘积，并将新factor中的assignment按照var按升序一一整理。

　　[i, j] = GetNextCliques(P, messages):

　　练习2所需完成的内容。该函数返回一个矩阵的下标索引i和j，意思是选择从clique i到clique j的消息用于下一次传递。选择这个消息的依据是：与clique i连接的所有cliques中，只剩下一个clique j没有与之传递消息了，则(I,j)就是下一次所需传递的。

　　P = CliqueTreeCalibrate(P, isMax):

　　实验3和实验6的内容。其中P是clique tree，isMax如果为1，则置信传播时采用max-sum,,否则采用sum-product. 该函数的作用是对tree进行calibrate.

　　[newF C E] = EliminateVar(F, C, E, Z):

　　F为factorList, C为clique tree的骨架，E为factorList中factor edge的连接关系。该函数作用是对F进行变量消除，消除的变量为Z。newF为变量消除后得到的factorList. 返回的C中多了一个edge项和factorInds项，该edge表示两个clique之间的连接情况，而factorInds表示产生新的factor后还剩多少个factor(这个参数只在本函数内部使用，用来计算edge矩阵的，对外没作用)。大概的实现思想为：将含有需消除变量的factor相乘得到一个新的factor，并对这个factor进行Z边缘化(积分掉Z)后得到更新的factor。最新的factor和剩余暂时没有进行变量消除的factor放在一起，构成newF.

　　C = PruneTree(C):

　　C依旧为clique tree skeleton. 该函数是对C进行剪枝，依次扫描C的node i，如果某个node是它邻居node k的子集，则将i与k之间的边去掉，且将k与i的其它所有邻居node相连接。该处理的目的是为了维持RIP特性，获得更紧凑的clique tree.

　　F = ObserveEvidence(F, E):

　　F为一个factor的容器。E为一个2列的矩阵，每1行代表1对观察值，其中第1个元素为变量名称v，第2个元素为该变量对应的值，假设为x。作用是在F的每个factor中，只保留变量v等于x时对应assignment的值，而变量v等于其它值的assignment值都清0。但不改变每个factor表格的大小，只是有很多0值的行而已。

　　P = CreateCliqueTree(F, Evidence):

　　F为factorList，P为clique tree, Evidence为观察到的变量。该函数是用F来构造P。其大概过程为：用F构造骨架C，对C使用EliminateVar()进行变量消除，得到冗余的clique tree，接着调用pruneTree()对clique tree剪枝，去掉冗余的cliuqe。最用调用ObserveEvidence()进行factor reduce, 同时函数ComputeInitialPotentials()获得clique对应的table.

　　B = FactorMarginalization(A, V):

　　A，B为factor，V为变量的集合。该函数的作用是在factor A上求和积分掉V中的元素，得到新的factor B. B的尺寸当然变小了。

　　M = ComputeExactMarginalsBP(F, E, isMax):

　　实验4和实验7的内容。F为factorList，E为Evidence. 先调用CreateCliqueTree()创建clique tree, 然后调用CliqueTreeCalibrate()对树进行校正。当isMax为0时，调用FactorMarginalization()计算边缘概率，否则用FactorMaxMarginalization()来计算。

　　B = FactorMaxMarginalization(A, V)：

　　实验5的内容。边缘化factor表，不过这时不是对V变量求和，而是求其中的最大值。和

函数FactorMarginalization()基本一样，需将sum改成max. 同时需要考虑当factor中val值为负数的情况，如果所有这些值都为负数，则max后应该也为负数，而我们初始化时一开始B.val为0,要小心（加一个if语句判断即可）。

　　A = MaxDecoding( M ):

　　实验8的内容。找到M中每个元素的val向量值最大的那个所对应的var，并将该var赋给对应的A. 这就是max-decoding过程。

　　相关的理论知识点：

　　主要参考Daphne Koller的PGM教材和courera教程，还有网友的PGM笔记。

　　factor的其它名字：affinity(密切关系), compatibility(兼容性),soft constraints. factor与联合概率没有直接关系，还需考虑其它的factor.

　　一个图G是一个分布P的I-map是指图G所诱导出的独立性断言是P独立性断言的子集。

　　如果图G是分布P的I-map,则分布P可以按照图G来分解。反之，如果分布P能够按照图G来分解，则图G是分布P的I-map(以上在BNs网络内成立).

　　BN中complete graph是指不能再往图中多加边了，否则会构成环。因为complete graph中没有任何独立性断言，所以所有的complete graph是任意分布P的I-map.

　　BN的skeleton: 是一个无向图，包含BN的所有顶点，把每条有向边都对应一条无向边。

　　I-equivalent: 如果2个图具有相同的独立性断言，则这两个图是I-equivalent. 其一个充分条件为：如果两个图含有相同的 skeleton 且对应的 v-structure（common effect）也相同，则他们是 I-equivalent 的。

　　如果 v-structure 中没有两个 prior 之间的边，我们就称这个 v-structure 时 immorality，否则这条边称为 covering edge. 两个图是I-equivalent关于v-structure的条件更松一点，只需要其中 immoral 部分的v-structure即可. 另一种表述：如果两个图是 I-equivalent，当且仅当存在一个 graph 序列，每两个相邻的graph仅仅是将 covering edge 转向.

　　positive distribution: P为正分布是指：只要事件A不为空，则P(A)>0. 正分布具有intersection特性(独立性中的交叉律)。

　　minimal I-map:给定一个独立性断言集合，图  是 minimal I-map 当且仅当G是该独立性断言集合的I-map，且G中去掉任意一条边都会导致其不是I-map. minimal I-map比较容易获得, 且不唯一。不同的节点构造顺序可造出不同的minimal I-map。由此可知，单单由P的I-map不足以保证该graph提取出P中所有的独立性结构。

　　perfect I-map: 图G的独立性断言和分布P的独立性断言相等，也叫P-map. perfect I-map比较难获得。虽然P-map可以完全capture分布P的结构，但并不是所有的分布P都有其对应的P-map，比如具有与四边形MRF相同独立性的P，或者具有与XOR网络独立性相同的P都是没有对应P-map的。

　　对正概率情形，GRF、global Markovian、local Markovian 和 pairwise Markovian 是等价的.

　　BN的参数是CPDs，而MRF的参数是factors. MRF中的联合概率是由所有的factor决定的。

　　clique：就是最大完全子图。一个图中可能会有多个最大完全子图，它们彼此之间的顶点个数有可能不相等(因为最大完全子图表示不能再往里面加入节点了)。而这些clique中节点个数最多的那个叫做largest clique.

　　Clique potential:如果将MRF分解成的最大完全子图(MRF中的完全子图是指子图中任意2个节点之间都有连线，注意与BN中完全子图的概念区分开，BN完全子图是指不能往子图中加任何边，否则会构成环)，则每个完全子图构成的factor都叫做clique potential.

　　Pairwise Markov Network: 网络中所有的factor只有2个变量。带有n个节点的fully connected pairwise markov network，如果每个节点的取值有d个，则该图中共有O(n*n*d*d)个参数(先用组合的方法求出edge的个数，然后每个edge都有d*d个参数)。而如果要描述图中所有的分布，则需要更多参数(O(n^d))，因此pairwise markov network并不能描述所有的分布。

　　GRF(Gibbs random fields):比pairwise markov network更广，因为它的每个factor可有多于2个的变量，且每个factor中所有的变量之间都有连线。

　　CRF和GRF的不同处在于划分函数，在GRF中，划分函数的值是一样的，在CRF中，划分函数值和输入的X有关，不同的X对应的值不同。logistic regression是一个简单的CRF，只需在CRF中将factor定义成指数形式。

　　分布P能够按照图H分解是指，存在一个factor集合，且由该集合中所有factor的乘积归一化后得到的概率和P相等。由这些factor集获得的图为H，H也叫是induced graph. 但是我们不能反过来从图H中来得到这些factor集，因为这样会得到多个答案。

　　如果P能够按照H分解，则H中的separation对应于P中的条件独立。对正分布P而言，如果H是P的一个I-map，则P能够按照H来分解。

　　graph越sparse，则参数越少，含有的独立性信息越多。

　　Reduced Markov Network: 去点一些节点以及与这些节点相连的边后得到的网络。

　　在MRF中，如果图H是分布P(positive)的I-map，则P是Gibbs分布，且P能按照H进行分解。

　　Soundness: 可靠性，由语法蕴含推导出语义蕴含。用来证明一个东西是错的。

　　Completeness，完备性，由语义蕴含推导出语法蕴含。用来证明一个东西是对的。

　　Markov blanket：一个节点的Markov blanket指的是该节点的父节点，孩子节点以及孩子节点的另外父节点。

　　I(H):MRF中的全局独立性，没有active trial.

　　Il(H):MRF中local独立性，给定Markov blanket.

　　Ip(H):MRF中的pairwise独立性, 非相邻，给定其它节点。

　　其中Il(H)蕴含了Ip(H), 而I(H)蕴含了Ip(H).

　　对正分布的P而言，上面3种独立性是等价的。

　　当P是正分布时，可以从P获得唯一的minimal I-map H. 当P为非正分布时，构造出来的H不能保证是I-map.因为此时的Il(H)和Ip(H)都不能蕴含I(L).

　　MRF的参数表达有3种形式：a product over potentials on cliques; a product of factors; a product of feature weight. 其表达形式依次更细致。应用场合不同，weight模型主要用于求解参数，factor模型主要用于推理。

　　贝叶斯网络在观察到一条边后是Gibbs分布。

　　Moral Graph:一贝叶斯网络G中Moral Graph是个无向图，记为M(G), 它是将v结构的2个父节点之间加入一条边，且将所有的有向边变成无向边。M(G)是G的minniial  I-map.

　　moral:一个贝叶斯网络是moral的，当且仅当其所有的v结构中两个父节点之间都有连线。如果一个图G是moral的，则M(G)是图G的一个perfect map.这样的图G如果转换成markov network的话是不会丢失独立性信息的。遗憾的是，实际情况中，属于moral的图很少。moral graph可以用来证明d-seperation的合理性。

　　如果贝叶斯网络G是MRF H的minimal I-map, 则G是moral graph(和书中说的没有immoralities是一个意思)。

　　chordal：图中所有的loop边长不大于3。将BN转换成MRF的过程叫做triangularization.

　　Chordal graph:在MRF中，没有边长超过3的环。也就是所有环的长度都是3.

　　BNs和MNs之间的相互转换会导致一些独立性的丢失。比如说从BN转到MN时，v-structure的独立性会消失。

　　Log-linear model: 在该模型中，P可以由指数表示。指数型一般为多个系数与特征的乘积，因此是线性的(取对数后也是线性的，因此叫log-linear模型)，每个特征都有scope，不同特征可以共用一个scope.

　　很容易知道，每一个factor table都可以转换成log-linear model，只需将特征取为合适的指示函数，且前面的系数和factor table中的值成log关系即可。

　　如果一个距离函数满足自反性和对称性，则称为semi metric，如果还满足三角不等式性质，则称为metric. Metric MRF中的特征为，相连接的2个节点（每个节点都在同一个向量空间内取值）具有相似的值，所以它的特征是一个距离函数。越相似，距离越小，则得到的概率越大。一般的距离函数可以取两者的绝对值(或者限制绝对值)。在segmentation领域，Metric MRF利用的特征为：相邻的超像素趋向于相同的类别。在denoising领域其使用的特征为：相邻像素趋向相同的像素值。

　　Ising model和Matric MRF一样，也是一个feature-based model。Ising model来自统计物理，是一个pairwise Markov network. 其特征取两个相邻节点的乘积(在磁场中，判断两个方向是否一致)。并且其指数项还有一个温度系数T，用来控制惩罚的强度。

　　Tabular CPD的局限性是表格大小随着变量个数呈指数增长。为了减少参数，CPD形式一般采用函数的形式来表示。这样的模型主要有deterministic CPD, tree-structured CPD, logistic CPD&generalizations, nosiy and/or, linear gaussians&generalizations.

　　Tree-structured CPD能够减小参数时因为在tree中隐含了很多独立性的信息，比如说给定一个节点，则目标的条件概率与该节点的兄弟节点所在树分支无关(即独立)，因此对应的tabular CPD中就可以减少很多项。tree-structured CPD一般与context-specific 独立性有关。

　　Multiplexer CPD: 有一个开关，不同开关值对应不同的结构，因而有不同的独立性信息。这和电路中的多路选择器是一样的。

　　noisy on/and/max等都类似，即多个父节点之间取on/and/max等关系。这种表示方法当然可以减小参数个数。

　　sigmoid和linear gaussian是输出连续概率值的模型。

　　interface variable:指那些在t时刻能够直接影响自己在t+1时刻的变量。

　　Inter-time-slice edge:不同时刻间变量之间的边。

　　Intra-time-slice edge:同一时刻里变量之间的边。

　　Dynamic bayesian network(DBN):是一个时序模型，对应一个初始分布和2-TBN过程。它有2个假设：markov 假设和时序不变性假设。2-TBN对应的是条件概率(注意不是联合概率)，且该条件概率是按照图的结构来分解的。

　　Ground network: unrolled network.展开的网络。

　　Linear dynamical system(LCS):也叫kalman filter，它是一个DBN，且满足所有的变量都是连续的，变量之间的独立性满足linear gaussian.

　　常见例子中，时序模型中的template variables/attribute(一类变量)可以是time, person, pixel, student, course等。

　　markov假设是个很强的假设，一般不会成立，为了使其更好的近似成立，可以加入当前时刻的一些其它信息。另外semi-markov也能够更好的近似。

　　在plate model中，每一个box(方框)都叫做plate. plate里面的node都是需要index的。plate可以嵌套，可以重叠。

　　在模型的表述中，要考虑template-based vs specific; directed vs undirected; generative vs discriminative. 或者它们的混合。在模型的结构上，需要考虑causal vs non-causal.

　　Generative model适用于数据缺失或标签比较难获得的领域，且它能够产生数据。discriminative model适用于标签多或者高维变量的领域，它不需要拟合联合分布。

　　在MN中，factor的个数一般等于变量的个数，而在MRF中factor的个数一般大于变量的个数。

　　计算P(X=x)或者验证P(X=x)>0都是NP-hard的，不过这是在worst case情况下，在general case情况下还是可以计算的。

　　图模型中一般有两种类型的inference。第一种是求解部分联合概率(包括边缘概率)或者条件概率，一般采用的方法是sum-product。其中sum对应将无关变量求和消  掉的过程(variable elimination)，product对应多个factor的乘积。如果是在求条件概率时，则这些factor应该为reduced factor;另外还可以采用belief propagation或者变分法. 第二种推理过程为MAP(最大后验)，即求给定evidence时，其它变量(除去evidence后的所有变量)出现的最大概率对应的组合(此时求得不是最大概率，而是变量的configuration)。因此MAP得到的结果可能不唯一。求解该推理可以采用max-product，其中的max是根据定义求概率最大时的变量组合，prodcut依旧是factor(reduced factor)的乘积，这个过程也会可以采用variable elimination. 类似的，还可以用max-product belief propagation,或者integer programming, 或者combinatorial search.如果是一些特殊的网络则可用graph-cut. 注意这里的MAP不等于Max over marginals(对应每个变量单独取最大值的组合)。

　　变量消除法在BN和MRF中都可以使用。

　　变量消除算法的复杂度和2个因素成线性关系：一个是关于model本身的factor个数和变量个数;另一个是中间产生的factor表格的大小(最大那个table的行数，这个行数与表格的scope成指数关系，所以是影响算法复杂度的关键)。由变量消除复杂度分析可知，不同的变量消除顺序的计算复杂度是不同的。

　　moralization: 将BN转换成MN时的过程，将有向边变成无向，还需要在对应的v-struction中加入边，这个过程也叫做moralization.

　　在对应的graph上进行变量消除时，可能会加入fill edge，因为得到的新factor可能变量之间没有边，此时需要手动加入边，这条边就叫做fill edge.

　　Induced graph: 是一个无向图，由变量消除得到的。induced graph与factors以及变量消除的顺序有关，不同的变量消除顺序可能引入不同的fill edge.

　　变量消除过程中产生的每一个factor都是induced graph里的一个clique.反过来也成立。

　　induced width: 指的是largest clique中节点个数减1.

　　minimal induced width:所有变量消除顺序中得到的induced width.

　　变量消除过程可以看做是对无向图的变形过程。

　　在图H中找到一个变量消除顺序使得induced width长度小于K是一个NP难问题。所以一般采用启发式搜索，启发式的cost function可以为：min-neighbors;min-weight;min-fill;weighted min-fill.其中min-fill最常用。

　　Cluster graph: 是一个无向图，图中每一个节点(该节点也叫cluster)都是整个scope的一个子集，cluster graph具有family-preversing特性，即每个factor的scope都是cluster中某个节点的子集。两个cluster之间的边为两节点scope交集的子集。

　　Cluster tree: 变量消除的过程就会得到一个cluster graph. 其实，更准确的说，这个消除过程得到的是一棵树，因为消除过程是有方向的，最后箭头指向的终止节点为我们需要计算的值，这个节点也称为root(注意和数据结构中的root稍微不同，这里箭头指向root，而数据结构中是由root指向其它节点)，从其它节点流向root的过程也叫做up-stream. 这棵树叫做cluster tree，是有方向的。

　　Running intersection property(RIP): 只要cluster tree T中某一个变量同时属于2个节点，则该变量存在于这两个节点连接的path上每(且是唯一的一条path，否则这个变量会构成环来传播)一个节点里。此时称该cluster tree具有RIP特性。

　　Clique tree: 如果cluster tree满足RIP特性，则该cluster tree也叫做clique tree，原先节点cluster也叫做clique. Clique tree和cluster tree的不同之处在于，edge上的变量不再是相邻cluster scope交集的子集，而只能是交集。另一种等价表示是对任意一个变量x，由clusters和sepsets构成的path能够构成一棵树(既不能断开，也不能有环).可以用变量消除得到clique tree，也可反过来用clique tree进行变量消除。

　　belief：clique tree中当前clique的势与其所有邻节点传过来的message乘积之和。

　　calibrated: 当两个相邻的clique对自己的belief消除非公共变量后得到的message相等时，则称它们是calibrated.

　　Calibrated clique tree: 满足clique tree中所有相邻的clique都是calibrated的。

　　Calibrated belief：满足calibrated公式时的那个值。

　　如果BP算法过程收敛(收敛意味着当前时刻发射的message和下一时刻发射的message相等)，则可以推断出cluster tree是calibrated的。

　　除了可以用VE(表示变量消除)进行inference外，还可以用message passing.

　　在cluster graph中，BP(belief propagation)算法可能不收敛，且计算结果是近似的，通过它计算出的边缘概率也叫pseudo-marginals.虽然这样，不过在实际应用中还是很有用的。但在clique tree上进行BP得到的边缘概率是正确的。

　　Bethe cluster graph:由factor构成cluster，且每个变量也单独构成cluster，这个single cluster与前面的cluster节点元素有交集时需要添加一条边。bethe cluster graph同时需要满足RIP性质。

　　Sepset belief：指2个cluster之间edge上两个方向发射出来的message的乘积。

　　reparameterization: 因为每两个cluster之间的message在cluster belief和sepset belief中都出现了一遍，所以如果将所有cluster belief的乘积当做分子，所有sepset belief之间的乘积当做分母，则两者之间的比值等于各个cluster初始势能的乘积(unnormalization),这个性质叫做reparameterization. 这意味着进行message passing过程时没有信息丢失。

　　在clique tree中由RIP特性可以推断出clique tree是correctness的(指的是VE过程和message passing过程得到的结果一致)。

　　在clique tree上进行message passing时，如果message传递的顺序是正确的(必须从叶子节点开始传递)，则仅仅需要传递2(k-1)次message, k为tree中的edge数。

　　Answer question：计算后验概率，给定evidence Z情况下计算后验值X的概率(这也叫做incremental inference).分为2种情况，一种是X和Z在同一个cluster中，此时直接reduced cluster即可。另一种情况是X和Z在不同的cluster中，则需要重新用message passing来计算与Z相关的那些cluster.

　　Cluster tree满足RIP特性，当且仅当某边两侧单独出现的变量在这条边变量下相互独立。也就是说cluster tree中蕴含了条件独立性。

　　通过VE可以得到correct clique tree.

　　BP算法的收敛性具有局部性，且不能保证收敛，即使收敛也不能保证结果正确。因此通常会采用一些小技巧，比如说选合适的VE顺序，采用异步message passing方式，采用TRP(Tree reparameterization)或RBP(Residual belief propagation)方式传递,或者用damping技术。

　　一般可将max-product问题取对数后变成max-sum问题，当然也可以加入负号后变成energy minimization问题。

　　在max-sum中引入2个新的操作，factor sum和factor maximization.很容易从字面意思理解其操作。这2个操作分布对应message passing过程中的belief计算和message计算。

　　使用max-sum算法对chain进行变量消除时，最后得到的结果称为max-marginal. 在clique tree中，每个clique的belief和max-marginal是一样的。

　　Max-sum中clique tree的calibration特性是：2个belief中对应变量的max结果一样。

　　和sum-product类似，如果clique i收到了除clique j以外的其它相邻clique节点的message，则从I passing到j的message不会再变化了。由此可知，来自叶节点的message将不再变化。在max-sum中采用单一的up-down message传播时最终也会收敛(calibration)。

　　即使MAP assignment答案不唯一，也可以从calibration clique tree中decoding出一个MAP assignment来。

　　有些MAP问题不可解，有些可解。如果对应的树的width越小，则该问题越可能有解。

　　一些match问题可以转换成MAP问题，而某些MAP问题可以转换为graph cut.

　　Cardinality Factors,Sparse Pattern Factors,Convexity Factors常用于一些MAP问题的求解。

　　参考资料：

       Daphne Koller，Probabilistic Graphical Models Principles and Techniques书籍第3、4、5、6、9、10、13章

       coursera课程：Probabilistic Graphical Models 

       网友demonstrate 的 blog：PGM 读书笔记节选（一）到（十）

作者：tornadomeet
出处：http://www.cnblogs.com/tornadomeet 欢迎转载或分享，但请务必声明文章出处。
新浪微博：tornadomeet,欢迎交流！