概率图模型使用图的方式表示概率分布。为了在图中添加各种概率，首先总结一下随机变量分布的一些规则：

6.概率图模型 - 图1%3D%5Cint%20p(x1%2Cx_2)dx_2%5C%5C%0A%26Product%5C%20Rule%3Ap(x_1%2Cx_2)%3Dp(x_1%7Cx_2)p(x_2)%5C%5C%0A%26Chain%5C%20Rule%3Ap(x_1%2Cx_2%2C%5Ccdots%2Cx_p)%3D%5Cprod%5Climits%7Bi%3D1%7D%5Epp(xi%7Cx%7Bi%2B1%2Cx%7Bi%2B2%7D%20%5Ccdots%7Dx_p)%5C%5C%0A%26Bayesian%5C%20Rule%3Ap(x_1%7Cx_2)%3D%5Cfrac%7Bp(x_2%7Cx_1)p(x_1)%7D%7Bp(x_2)%7D%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0A%26Sum%5C%20Rule%3Ap%28x_1%29%3D%5Cint%20p%28x_1%2Cx_2%29dx_2%5C%5C%0A%26Product%5C%20Rule%3Ap%28x_1%2Cx_2%29%3Dp%28x_1%7Cx_2%29p%28x_2%29%5C%5C%0A%26Chain%5C%20Rule%3Ap%28x_1%2Cx_2%2C%5Ccdots%2Cx_p%29%3D%5Cprod%5Climits%7Bi%3D1%7D%5Epp%28xi%7Cx%7Bi%2B1%2Cx_%7Bi%2B2%7D%20%5Ccdots%7Dx_p%29%5C%5C%0A%26Bayesian%5C%20Rule%3Ap%28x_1%7Cx_2%29%3D%5Cfrac%7Bp%28x_2%7Cx_1%29p%28x_1%29%7D%7Bp%28x_2%29%7D%0A%5Cend%7Balign%7D%0A#crop=0&crop=0&crop=1&crop=1&id=P5bPS&originHeight=203&originWidth=500&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

可以看到，在链式法则中，如果数据维度特别高，那么的采样和计算非常困难，我们需要在一定程度上作出简化，在朴素贝叶斯中，作出了条件独立性假设。在 Markov 假设中，给定数据的维度是以时间顺序出现的，给定当前时间的维度，那么下一个维度与之前的维度独立。在 HMM 中，采用了齐次 Markov 假设。在 Markov 假设之上，更一般的，加入条件独立性假设，对维度划分集合 6.概率图模型 - 图2，使得 6.概率图模型 - 图3。

概率图模型采用图的特点表示上述的条件独立性假设，节点表示随机变量，边表示条件概率。概率图模型可以分为三大理论部分：

  1. 表示：
    1. 有向图（离散）：贝叶斯网络
    2. 高斯图（连续）：高斯贝叶斯和高斯马尔可夫网路
    3. 无向图（离散）：马尔可夫网络
  2. 推断
    1. 精确推断
    2. 近似推断
      1. 确定性近似（如变分推断）
      2. 随机近似（如 MCMC）
  3. 学习
    1. 参数学习
      1. 完备数据
      2. 隐变量：E-M 算法
    2. 结构学习

有向图-贝叶斯网络

已知联合分布中，各个随机变量之间的依赖关系，那么可以通过拓扑排序（根据依赖关系）可以获得一个有向图。而如果已知一个图，也可以直接得到联合概率分布的因子分解：

6.概率图模型 - 图4%3D%5Cprod%5Climits%7Bi%3D1%7D%5Epp(x_i%7Cx%7Bparent(i)%7D)%0A#card=math&code=p%28x1%2Cx_2%2C%5Ccdots%2Cx_p%29%3D%5Cprod%5Climits%7Bi%3D1%7D%5Epp%28xi%7Cx%7Bparent%28i%29%7D%29%0A#crop=0&crop=0&crop=1&crop=1&id=EJ5ne&originHeight=63&originWidth=332&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

那么实际的图中条件独立性是如何体现的呢？在局部任何三个节点，可以有三种结构：


6.概率图模型 - 图5%3Dp(A)p(B%7CA)p(C%7CB)%3Dp(A)p(B%7CA)p(C%7CB%2CA)%5C%5C%0A%5CLongrightarrow%20p(C%7CB)%3Dp(C%7CB%2CA)%5C%5C%0A%5CLeftrightarrow%20p(C%7CB)p(A%7CB)%3Dp(C%7CA%2CB)p(A%7CB)%3Dp(C%2CA%7CB)%5C%5C%0A%5CLongrightarrow%20C%5Cperp%20A%7CB%0A#card=math&code=p%28A%2CB%2CC%29%3Dp%28A%29p%28B%7CA%29p%28C%7CB%29%3Dp%28A%29p%28B%7CA%29p%28C%7CB%2CA%29%5C%5C%0A%5CLongrightarrow%20p%28C%7CB%29%3Dp%28C%7CB%2CA%29%5C%5C%0A%5CLeftrightarrow%20p%28C%7CB%29p%28A%7CB%29%3Dp%28C%7CA%2CB%29p%28A%7CB%29%3Dp%28C%2CA%7CB%29%5C%5C%0A%5CLongrightarrow%20C%5Cperp%20A%7CB%0A#crop=0&crop=0&crop=1&crop=1&id=J8Evj&originHeight=116&originWidth=900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
image.png


6.概率图模型 - 图7%3Dp(A%7CB)p(B)p(C%7CB)%3Dp(B)p(A%7CB)p(C%7CA%2CB)%5C%5C%0A%5CLongrightarrow%20p(C%7CB)%3Dp(C%7CB%2CA)%5C%5C%0A%5CLeftrightarrow%20p(C%7CB)p(A%7CB)%3Dp(C%7CA%2CB)p(A%7CB)%3Dp(C%2CA%7CB)%5C%5C%0A%5CLongrightarrow%20C%5Cperp%20A%7CB%0A#card=math&code=p%28A%2CB%2CC%29%3Dp%28A%7CB%29p%28B%29p%28C%7CB%29%3Dp%28B%29p%28A%7CB%29p%28C%7CA%2CB%29%5C%5C%0A%5CLongrightarrow%20p%28C%7CB%29%3Dp%28C%7CB%2CA%29%5C%5C%0A%5CLeftrightarrow%20p%28C%7CB%29p%28A%7CB%29%3Dp%28C%7CA%2CB%29p%28A%7CB%29%3Dp%28C%2CA%7CB%29%5C%5C%0A%5CLongrightarrow%20C%5Cperp%20A%7CB%0A#crop=0&crop=0&crop=1&crop=1&id=PvsJj&originHeight=116&originWidth=900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
image.png


6.概率图模型 - 图9%3Dp(A)p(C)p(B%7CC%2CA)%3Dp(A)p(C%7CA)p(B%7CC%2CA)%5C%5C%0A%5CLongrightarrow%20p(C)%3Dp(C%7CA)%5C%5C%0A%5CLeftrightarrow%20C%5Cperp%20A%5C%5C%0A#card=math&code=p%28A%2CB%2CC%29%3Dp%28A%29p%28C%29p%28B%7CC%2CA%29%3Dp%28A%29p%28C%7CA%29p%28B%7CC%2CA%29%5C%5C%0A%5CLongrightarrow%20p%28C%29%3Dp%28C%7CA%29%5C%5C%0A%5CLeftrightarrow%20C%5Cperp%20A%5C%5C%0A#crop=0&crop=0&crop=1&crop=1&id=Nafbp&originHeight=105&originWidth=900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
image.png

对这种结构，6.概率图模型 - 图11 不与 6.概率图模型 - 图12 条件独立。

从整体的图来看，可以引入 D 划分的概念。对于类似上面图 1和图 2的关系，引入集合A，B，那么满足 6.概率图模型 - 图13 的 6.概率图模型 - 图14 集合中的点与 6.概率图模型 - 图15 中的点的关系都满足图 1，2，满足图3 关系的点都不在 6.概率图模型 - 图16 中。D 划分应用在贝叶斯定理中：

6.概率图模型 - 图17%3D%5Cfrac%7Bp(x)%7D%7B%5Cint%20p(x)dx%7Bi%7D%7D%3D%5Cfrac%7B%5Cprod%5Climits%7Bj%3D1%7D%5Epp(xj%7Cx%7Bparents(j)%7D)%7D%7B%5Cint%5Cprod%5Climits%7Bj%3D1%7D%5Epp(x_j%7Cx%7Bparents(j)%7D)dxi%7D%0A#card=math&code=p%28x_i%7Cx%7B-i%7D%29%3D%5Cfrac%7Bp%28x%29%7D%7B%5Cint%20p%28x%29dx%7Bi%7D%7D%3D%5Cfrac%7B%5Cprod%5Climits%7Bj%3D1%7D%5Epp%28xj%7Cx%7Bparents%28j%29%7D%29%7D%7B%5Cint%5Cprod%5Climits%7Bj%3D1%7D%5Epp%28x_j%7Cx%7Bparents%28j%29%7D%29dx_i%7D%0A#crop=0&crop=0&crop=1&crop=1&id=QfF4x&originHeight=122&originWidth=449&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

可以发现，上下部分可以分为两部分，一部分是和 6.概率图模型 - 图18 相关的，另一部分是和 6.概率图模型 - 图19 无关的，而这个无关的部分可以相互约掉。于是计算只涉及和 6.概率图模型 - 图20 相关的部分。

与 6.概率图模型 - 图21 相关的部分可以写成：

6.概率图模型 - 图22%7D)p(x%7Bchild(i)%7D%7Cx_i)%0A#card=math&code=p%28x_i%7Cx%7Bparents%28i%29%7D%29p%28x_%7Bchild%28i%29%7D%7Cx_i%29%0A#crop=0&crop=0&crop=1&crop=1&id=jU9gH&originHeight=29&originWidth=248&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这些相关的部分又叫做 Markov 毯。

实际应用的模型中，对这些条件独立性作出了假设，从单一到混合，从有限到无限（时间，空间）可以分为：

  1. 朴素贝叶斯，单一的条件独立性假设 6.概率图模型 - 图23%3D%5Cprod%5Climits%7Bi%3D1%7D%5Epp(x_i%7Cy)#card=math&code=p%28x%7Cy%29%3D%5Cprod%5Climits%7Bi%3D1%7D%5Epp%28x_i%7Cy%29#crop=0&crop=0&crop=1&crop=1&id=d7To1&originHeight=63&originWidth=176&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，在 D 划分后，所有条件依赖的集合就是单个元素。
  2. 高斯混合模型：混合的条件独立。引入多类别的隐变量 6.概率图模型 - 图24， 6.概率图模型 - 图25%3D%5Cmathcal%7BN%7D(%5Cmu%2C%5CSigma)#card=math&code=p%28x%7Cz%29%3D%5Cmathcal%7BN%7D%28%5Cmu%2C%5CSigma%29#crop=0&crop=0&crop=1&crop=1&id=aT1Dw&originHeight=27&originWidth=157&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，条件依赖集合为多个元素。
  3. 与时间相关的条件依赖
    1. Markov 链
    2. 高斯过程（无限维高斯分布）
  4. 连续：高斯贝叶斯网络
  5. 组合上面的分类
    • GMM 与时序结合：动态模型
      • HMM（离散）
      • 线性动态系统 LDS（Kalman 滤波）
      • 粒子滤波（非高斯，非线性）

无向图-马尔可夫网络（马尔可夫随机场）

无向图没有了类似有向图的局部不同结构，在马尔可夫网络中，也存在 D 划分的概念。直接将条件独立的集合 6.概率图模型 - 图26 划分为三个集合。这个也叫全局 Markov。对局部的节点，6.概率图模型 - 图27)%7CNeighbour(x)#card=math&code=x%5Cperp%20%28X-Neighbour%28%5Cmathcal%7Bx%7D%29%29%7CNeighbour%28x%29#crop=0&crop=0&crop=1&crop=1&id=Uf81R&originHeight=26&originWidth=358&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。这也叫局部 Markov。对于成对的节点：6.概率图模型 - 图28，其中 6.概率图模型 - 图29 不能相邻。这也叫成对 Markov。事实上上面三个点局部全局成对是相互等价的。

有了这个条件独立性的划分，还需要因子分解来实际计算。引入团的概念：

团，最大团：图中节点的集合，集合中的节点之间相互都是连接的叫做团，如果不能再添加节点，那么叫最大团。

利用这个定义进行的 6.概率图模型 - 图30 所有维度的联合概率分布的因子分解为，假设有 6.概率图模型 - 图31 个团，6.概率图模型 - 图32 就是对所有可能取值求和：

6.概率图模型 - 图33%3D%5Cfrac%7B1%7D%7BZ%7D%5Cprod%5Climits%7Bi%3D1%7D%5E%7BK%7D%5Cphi(x%7Bci%7D)%5C%5C%0AZ%3D%5Csum%5Climits%7Bx%5Cin%5Cmathcal%7BX%7D%7D%5Cprod%5Climits%7Bi%3D1%7D%5E%7BK%7D%5Cphi(x%7Bci%7D)%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7Dp%28x%29%3D%5Cfrac%7B1%7D%7BZ%7D%5Cprod%5Climits%7Bi%3D1%7D%5E%7BK%7D%5Cphi%28x%7Bci%7D%29%5C%5C%0AZ%3D%5Csum%5Climits%7Bx%5Cin%5Cmathcal%7BX%7D%7D%5Cprod%5Climits%7Bi%3D1%7D%5E%7BK%7D%5Cphi%28x%7Bci%7D%29%0A%5Cend%7Balign%7D%0A#crop=0&crop=0&crop=1&crop=1&id=Ykgee&originHeight=134&originWidth=184&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

其中 6.概率图模型 - 图34#card=math&code=%5Cphi%28x_%7Bci%7D%29#crop=0&crop=0&crop=1&crop=1&id=i6UAl&originHeight=26&originWidth=54&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 叫做势函数，它必须是一个正值，可以记为：

6.概率图模型 - 图35%3D%5Cexp(-E(x%7Bci%7D))%0A#card=math&code=%5Cphi%28x%7Bci%7D%29%3D%5Cexp%28-E%28x_%7Bci%7D%29%29%0A#crop=0&crop=0&crop=1&crop=1&id=kQShA&originHeight=26&originWidth=205&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这个分布叫做 Gibbs 分布（玻尔兹曼分布）。于是也可以记为：6.概率图模型 - 图36%3D%5Cfrac%7B1%7D%7BZ%7D%5Cexp(-%5Csum%5Climits%7Bi%3D1%7D%5EKE(x%7Bci%7D))#card=math&code=p%28x%29%3D%5Cfrac%7B1%7D%7BZ%7D%5Cexp%28-%5Csum%5Climits%7Bi%3D1%7D%5EKE%28x%7Bci%7D%29%29#crop=0&crop=0&crop=1&crop=1&id=sxi0q&originHeight=66&originWidth=250&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。这个分解和条件独立性等价（Hammesley-Clifford 定理），这个分布的形式也和指数族分布形式上相同，于是满足最大熵原理。

两种图的转换-道德图

我们常常想将有向图转为无向图，从而应用更一般的表达式。

  1. 链式：
    直接去掉箭头，6.概率图模型 - 图37%3Dp(a)p(b%7Ca)p(c%7Cb)%3D%5Cphi(a%2Cb)%5Cphi(b%2Cc)#card=math&code=p%28a%2Cb%2Cc%29%3Dp%28a%29p%28b%7Ca%29p%28c%7Cb%29%3D%5Cphi%28a%2Cb%29%5Cphi%28b%2Cc%29#crop=0&crop=0&crop=1&crop=1&id=yAccy&originHeight=26&originWidth=387&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)：

image.png

  1. V 形：
    由于 6.概率图模型 - 图39%3Dp(b)p(a%7Cb)p(c%7Cb)%3D%5Cphi(a%2Cb)%5Cphi(b%2Cc)#card=math&code=p%28a%2Cb%2Cc%29%3Dp%28b%29p%28a%7Cb%29p%28c%7Cb%29%3D%5Cphi%28a%2Cb%29%5Cphi%28b%2Cc%29#crop=0&crop=0&crop=1&crop=1&id=mYVRV&originHeight=26&originWidth=384&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，直接去掉箭头：

image.png

  1. 倒 V 形：
    由于 6.概率图模型 - 图41%3Dp(a)p(c)p(b%7Ca%2Cc)%3D%5Cphi(a%2Cb%2Cc)#card=math&code=p%28a%2Cb%2Cc%29%3Dp%28a%29p%28c%29p%28b%7Ca%2Cc%29%3D%5Cphi%28a%2Cb%2Cc%29#crop=0&crop=0&crop=1&crop=1&id=ILtBW&originHeight=26&originWidth=352&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，于是在 6.概率图模型 - 图42 之间添加线：

image.png
观察着三种情况可以概括为：

  1. 将每个节点的父节点两两相连
  2. 将有向边替换为无向边

更精细的分解-因子图

对于一个有向图，可以通过引入环的方式，可以将其转换为无向图（Tree-like graph），这个图就叫做道德图。但是我们上面的 BP 算法只对无环图有效，通过因子图可以变为无环图。

考虑一个无向图：
image.png
可以将其转为：
image.png
其中 6.概率图模型 - 图46#card=math&code=f%3Df%28a%2Cb%2Cc%29#crop=0&crop=0&crop=1&crop=1&id=r9IbA&originHeight=26&originWidth=115&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。因子图不是唯一的，这是由于因式分解本身就对应一个特殊的因子图，将因式分解：6.概率图模型 - 图47%3D%5Cprod%5Climits%7Bs%7Df_s(x_s)#card=math&code=p%28x%29%3D%5Cprod%5Climits%7Bs%7Df_s%28x_s%29#crop=0&crop=0&crop=1&crop=1&id=KpovY&originHeight=50&originWidth=154&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 可以进一步分解得到因子图。

推断

推断的主要目的是求各种概率分布，包括边缘概率，条件概率，以及使用 MAP 来求得参数。通常推断可以分为：

  1. 精确推断
    1. Variable Elimination(VE)
    2. Belief Propagation(BP, Sum-Product Algo)，从 VE 发展而来
    3. Junction Tree，上面两种在树结构上应用，Junction Tree 在图结构上应用
  2. 近似推断
    1. Loop Belief Propagation（针对有环图）
    2. Mente Carlo Interference：例如 Importance Sampling，MCMC
    3. Variational Inference

推断-变量消除（VE）

变量消除的方法是在求解概率分布的时候，将相关的条件概率先行求和或积分，从而一步步地消除变量，例如在马尔可夫链中：
image.png
6.概率图模型 - 图49%3D%5Csum%5Climits%7Ba%2Cb%2Cc%7Dp(a%2Cb%2Cc%2Cd)%3D%5Csum%5Climits_cp(d%7Cc)%5Csum%5Climits_bp(c%7Cb)%5Csum%5Climits_ap(b%7Ca)p(a)%0A#card=math&code=p%28d%29%3D%5Csum%5Climits%7Ba%2Cb%2Cc%7Dp%28a%2Cb%2Cc%2Cd%29%3D%5Csum%5Climits_cp%28d%7Cc%29%5Csum%5Climits_bp%28c%7Cb%29%5Csum%5Climits_ap%28b%7Ca%29p%28a%29%0A#crop=0&crop=0&crop=1&crop=1&id=o6qIM&originHeight=53&originWidth=525&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

变量消除的缺点很明显：

  1. 计算步骤无法存储
  2. 消除的最优次序是一个 NP-hard 问题

推断-信念传播（BP）

为了克服 VE 的第一个缺陷-计算步骤无法存储。我们进一步地对上面的马尔可夫链进行观察：
image.png
要求 6.概率图模型 - 图51#card=math&code=p%28e%29#crop=0&crop=0&crop=1&crop=1&id=cy3Wd&originHeight=26&originWidth=37&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，当然使用 VE，从 6.概率图模型 - 图52 一直消除到 6.概率图模型 - 图53，记 6.概率图模型 - 图54p(b%7Ca)%3Dm%7Ba%5Cto%20b(b)%7D#card=math&code=%5Csum%5Climits_ap%28a%29p%28b%7Ca%29%3Dm%7Ba%5Cto%20b%28b%29%7D#crop=0&crop=0&crop=1&crop=1&id=zJAPD&originHeight=50&originWidth=219&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，表示这是消除 6.概率图模型 - 图55 后的关于 6.概率图模型 - 图56 的概率，类似地，记 6.概率图模型 - 图57m%7Ba%5Cto%20b%7D(b)%3Dm%7Bb%5Cto%20c%7D(c)#card=math&code=%5Csum%5Climitsbp%28c%7Cb%29m%7Ba%5Cto%20b%7D%28b%29%3Dm%7Bb%5Cto%20c%7D%28c%29#crop=0&crop=0&crop=1&crop=1&id=E8wu2&originHeight=50&originWidth=260&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。于是 6.概率图模型 - 图58%3D%5Csum%5Climits_dp(e%7Cd)m%7Bb%5Cto%20c%7D(c)#card=math&code=p%28e%29%3D%5Csum%5Climitsdp%28e%7Cd%29m%7Bb%5Cto%20c%7D%28c%29#crop=0&crop=0&crop=1&crop=1&id=tO6p2&originHeight=50&originWidth=226&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。进一步观察，对 6.概率图模型 - 图59#card=math&code=p%28c%29#crop=0&crop=0&crop=1&crop=1&id=Fwqoh&originHeight=26&originWidth=37&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)：

6.概率图模型 - 图60%3D%5B%5Csum%5Climits_bp(c%7Cb)%5Csum%5Climits_ap(b%7Ca)p(a)%5D%5Ccdot%5B%5Csum%5Climits_dp(d%7Cc)%5Csum%5Climits_ep(e)p(e%7Cd)%5D%0A#card=math&code=p%28c%29%3D%5B%5Csum%5Climits_bp%28c%7Cb%29%5Csum%5Climits_ap%28b%7Ca%29p%28a%29%5D%5Ccdot%5B%5Csum%5Climits_dp%28d%7Cc%29%5Csum%5Climits_ep%28e%29p%28e%7Cd%29%5D%0A#crop=0&crop=0&crop=1&crop=1&id=GYnSf&originHeight=50&originWidth=528&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

我们发现了和上面计算 6.概率图模型 - 图61#card=math&code=p%28e%29#crop=0&crop=0&crop=1&crop=1&id=HiMFb&originHeight=26&originWidth=37&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 类似的结构，这个式子可以分成两个部分，一部分是从 6.概率图模型 - 图62 传播过来的概率，第二部分是从 6.概率图模型 - 图63 传播过来的概率。

一般地，对于图（只对树形状的图）：
image.png
这四个团（对于无向图是团，对于有向图就是概率为除了根的节点为1），有四个节点，三个边：

6.概率图模型 - 图65%3D%5Cfrac%7B1%7D%7BZ%7D%5Cphia(a)%5Cphi_b(b)%5Cphi_c(c)%5Cphi_d(d)%5Ccdot%5Cphi%7Bab%7D(a%2Cb)%5Cphi%7Bbc%7D(c%2Cb)%5Cphi%7Bbd%7D(d%2Cb)%0A#card=math&code=p%28a%2Cb%2Cc%2Cd%29%3D%5Cfrac%7B1%7D%7BZ%7D%5Cphia%28a%29%5Cphi_b%28b%29%5Cphi_c%28c%29%5Cphi_d%28d%29%5Ccdot%5Cphi%7Bab%7D%28a%2Cb%29%5Cphi%7Bbc%7D%28c%2Cb%29%5Cphi%7Bbd%7D%28d%2Cb%29%0A#crop=0&crop=0&crop=1&crop=1&id=Aggy6&originHeight=47&originWidth=572&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

套用上面关于有向图的观察，如果求解边缘概率 6.概率图模型 - 图66#card=math&code=p%28a%29#crop=0&crop=0&crop=1&crop=1&id=Ln9eX&originHeight=26&originWidth=39&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，定义 6.概率图模型 - 图67%3D%5Csum%5Climitsc%5Cphi_c(c)%5Cphi%7Bbc%7D(bc)#card=math&code=m%7Bc%5Cto%20b%7D%28b%29%3D%5Csum%5Climits_c%5Cphi_c%28c%29%5Cphi%7Bbc%7D%28bc%29#crop=0&crop=0&crop=1&crop=1&id=SIzlH&originHeight=50&originWidth=243&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，6.概率图模型 - 图68%3D%5Csum%5Climitsd%5Cphi_d(d)%5Cphi%7Bbd%7D(bd)#card=math&code=m%7Bd%5Cto%20b%7D%28b%29%3D%5Csum%5Climits_d%5Cphi_d%28d%29%5Cphi%7Bbd%7D%28bd%29#crop=0&crop=0&crop=1&crop=1&id=NtTUq&originHeight=50&originWidth=251&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，6.概率图模型 - 图69%3D%5Csum%5Climitsb%5Cphi%7Bba%7D(ba)%5Cphib(b)m%7Bc%5Cto%20b%7D(b)%7Bd%5Cto%20b%7Dm(b)#card=math&code=m%7Bb%5Cto%20a%7D%28a%29%3D%5Csum%5Climitsb%5Cphi%7Bba%7D%28ba%29%5Cphib%28b%29m%7Bc%5Cto%20b%7D%28b%29_%7Bd%5Cto%20b%7Dm%28b%29#crop=0&crop=0&crop=1&crop=1&id=T8rgY&originHeight=50&originWidth=397&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，这样概率就一步步地传播到了 6.概率图模型 - 图70：

6.概率图模型 - 图71%3D%5Cphia(a)m%7Bb%5Cto%20a%7D(a)%0A#card=math&code=p%28a%29%3D%5Cphia%28a%29m%7Bb%5Cto%20a%7D%28a%29%0A#crop=0&crop=0&crop=1&crop=1&id=mrqsi&originHeight=26&originWidth=193&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

写成一般的形式，对于相邻节点 6.概率图模型 - 图72：

6.概率图模型 - 图73%3D%5Csum%5Climitsj%5Cphi_j(j)%5Cphi%7Bij%7D(ij)%5Cprod%5Climits%7Bk%5Cin%20Neighbour(j)-i%7Dm%7Bk%5Cto%20j%7D(j)%0A#card=math&code=m%7Bj%5Cto%20i%7D%28i%29%3D%5Csum%5Climits_j%5Cphi_j%28j%29%5Cphi%7Bij%7D%28ij%29%5Cprod%5Climits%7Bk%5Cin%20Neighbour%28j%29-i%7Dm%7Bk%5Cto%20j%7D%28j%29%0A#crop=0&crop=0&crop=1&crop=1&id=ljRRw&originHeight=54&originWidth=437&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这个表达式，就可以保存计算过程了，只要对每条边的传播分别计算，对于一个无向树形图可以递归并行实现：

  1. 任取一个节点 6.概率图模型 - 图74 作为根节点
  2. 对这个根节点的邻居中的每一个节点，收集信息（计算入信息）
  3. 对根节点的邻居，分发信息（计算出信息）

推断-Max-Product 算法

在推断任务中，MAP 也是常常需要的，MAP 的目的是寻找最佳参数：

6.概率图模型 - 图75%3D%5Cmathop%7Bargmax%7D%7Ba%2Cb%2Cc%2Cd%7Dp(a%2Cb%2Cc%2Cd%7CE)%0A#card=math&code=%28%5Chat%7Ba%7D%2C%5Chat%7Bb%7D%2C%5Chat%7Bc%7D%2C%5Chat%7Bd%7D%29%3D%5Cmathop%7Bargmax%7D%7Ba%2Cb%2Cc%2Cd%7Dp%28a%2Cb%2Cc%2Cd%7CE%29%0A#crop=0&crop=0&crop=1&crop=1&id=JLTM2&originHeight=48&originWidth=311&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

类似 BP，我们采用信息传递的方式来求得最优参数，不同的是，我们在所有信息传递中，传递的是最大化参数的概率，而不是将所有可能求和：

6.概率图模型 - 图76-i%7Dm%7Bk%5Cto%20j%7D%0A#card=math&code=m%7Bj%5Cto%20i%7D%3D%5Cmax%5Climits%7Bj%7D%5Cphi_j%5Cphi%7Bij%7D%5Cprod%5Climits%7Bk%5Cin%20Neighbour%28j%29-i%7Dm%7Bk%5Cto%20j%7D%0A#crop=0&crop=0&crop=1&crop=1&id=DHfCv&originHeight=54&originWidth=340&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

于是对于上面的图：

6.概率图模型 - 图77%3D%5Cmaxa%5Cphi_a%5Cphi%7Bab%7Dm%7Bc%5Cto%20b%7Dm%7Bd%5Cto%20b%7D%0A#card=math&code=%5Cmaxa%20p%28a%2Cb%2Cc%2Cd%29%3D%5Cmax_a%5Cphi_a%5Cphi%7Bab%7Dm%7Bc%5Cto%20b%7Dm%7Bd%5Cto%20b%7D%0A#crop=0&crop=0&crop=1&crop=1&id=HtUWc&originHeight=36&originWidth=356&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这个算法是 Sum-Product 算法的改进，也是在 HMM 中应用给的 Viterbi 算法的推广。