概率图模型

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

Sum Rule:p(x1)=p(x1,x2)dx2Product Rule:p(x1,x2)=p(x1x2)p(x2)Chain Rule:p(x1,x2,,xp)=i=1pp(xixi+1,xi+2xp)Bayesian Rule:p(x1x2)=p(x2x1)p(x1)p(x2)\begin{split} &Sum\ Rule:p(x_1)=\int p(x_1,x_2)dx_2\\ &Product\ Rule:p(x_1,x_2)=p(x_1|x_2)p(x_2)\\ &Chain\ Rule:p(x_1,x_2,\cdots,x_p)=\prod\limits_{i=1}^pp(x_i|x_{i+1,x_{i+2} \cdots}x_p)\\ &Bayesian\ Rule:p(x_1|x_2)=\frac{p(x_2|x_1)p(x_1)}{p(x_2)} \end{split}

可以看到,在链式法则中,如果数据维度特别高,那么的采样和计算非常困难,我们需要在一定程度上作出简化,在朴素贝叶斯中,作出了条件独立性假设。在 Markov 假设中,给定数据的维度是以时间顺序出现的,给定当前时间的维度,那么下一个维度与之前的维度独立。在 HMM 中,采用了齐次 Markov 假设。在 Markov 假设之上,更一般的,加入条件独立性假设,对维度划分集合 A,B,CA,B,C,使得 XAXBXCX_A\perp X_B|X_C

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

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

有向图-贝叶斯网络

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

p(x1,x2,,xp)=i=1pp(xixparent(i))p(x_1,x_2,\cdots,x_p)=\prod\limits_{i=1}^pp(x_i|x_{parent(i)})

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

  1. p(A,B,C)=p(A)p(BA)p(CB)=p(A)p(BA)p(CB,A)p(CB)=p(CB,A)p(CB)p(AB)=p(CA,B)p(AB)=p(C,AB)CABp(A,B,C)=p(A)p(B|A)p(C|B)=p(A)p(B|A)p(C|B,A)\\ \Longrightarrow p(C|B)=p(C|B,A)\\ \Leftrightarrow p(C|B)p(A|B)=p(C|A,B)p(A|B)=p(C,A|B)\\ \Longrightarrow C\perp A|B

  2. p(A,B,C)=p(AB)p(B)p(CB)=p(B)p(AB)p(CA,B)p(CB)=p(CB,A)p(CB)p(AB)=p(CA,B)p(AB)=p(C,AB)CABp(A,B,C)=p(A|B)p(B)p(C|B)=p(B)p(A|B)p(C|A,B)\\ \Longrightarrow p(C|B)=p(C|B,A)\\ \Leftrightarrow p(C|B)p(A|B)=p(C|A,B)p(A|B)=p(C,A|B)\\ \Longrightarrow C\perp A|B

  3. p(A,B,C)=p(A)p(C)p(BC,A)=p(A)p(CA)p(BC,A)p(C)=p(CA)CAp(A,B,C)=p(A)p(C)p(B|C,A)=p(A)p(C|A)p(B|C,A)\\ \Longrightarrow p(C)=p(C|A)\\ \Leftrightarrow C\perp A\\

    对这种结构,A,CA,C 不与 BB 条件独立。

从整体的图来看,可以引入 D 划分的概念。对于类似上面图 1和图 2的关系,引入集合A,B,那么满足 ABCA\perp B|CCC 集合中的点与 A,BA,B 中的点的关系都满足图 1,2,满足图3 关系的点都不在 CC 中。D 划分应用在贝叶斯定理中:

p(xixi)=p(x)p(x)dxi=j=1pp(xjxparents(j))j=1pp(xjxparents(j))dxip(x_i|x_{-i})=\frac{p(x)}{\int p(x)dx_{i}}=\frac{\prod\limits_{j=1}^pp(x_j|x_{parents(j)})}{\int\prod\limits_{j=1}^pp(x_j|x_{parents(j)})dx_i}

可以发现,上下部分可以分为两部分,一部分是和 xix_i 相关的,另一部分是和 xix_i 无关的,而这个无关的部分可以相互约掉。于是计算只涉及和 xix_i 相关的部分。

xix_i 相关的部分可以写成:

p(xixparents(i))p(xchild(i)xi)p(x_i|x_{parents(i)})p(x_{child(i)}|x_i)

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

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

  1. 朴素贝叶斯,单一的条件独立性假设 p(xy)=i=1pp(xiy)p(x|y)=\prod\limits_{i=1}^pp(x_i|y),在 D 划分后,所有条件依赖的集合就是单个元素。
  2. 高斯混合模型:混合的条件独立。引入多类别的隐变量 z1,z2,,zkz_1, z_2,\cdots,z_kp(xz)=N(μ,Σ)p(x|z)=\mathcal{N}(\mu,\Sigma),条件依赖集合为多个元素。
  3. 与时间相关的条件依赖
    1. Markov 链
    2. 高斯过程(无限维高斯分布)
  4. 连续:高斯贝叶斯网络
  5. 组合上面的分类
    • GMM 与时序结合:动态模型
      • HMM(离散)
      • 线性动态系统 LDS(Kalman 滤波)
      • 粒子滤波(非高斯,非线性)

无向图-马尔可夫网络(马尔可夫随机场)

无向图没有了类似有向图的局部不同结构,在马尔可夫网络中,也存在 D 划分的概念。直接将条件独立的集合 xAxBxCx_A\perp x_B|x_C 划分为三个集合。这个也叫全局 Markov。对局部的节点,x(XNeighbour(x))Neighbour(x)x\perp (X-Neighbour(\mathcal{x}))|Neighbour(x)。这也叫局部 Markov。对于成对的节点:xixjxijx_i\perp x_j|x_{-i-j},其中 i,ji,j 不能相邻。这也叫成对 Markov。事实上上面三个点局部全局成对是相互等价的。

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

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

利用这个定义进行的 xx 所有维度的联合概率分布的因子分解为,假设有 KK 个团,ZZ 就是对所有可能取值求和:

p(x)=1Zi=1Kϕ(xci)Z=xXi=1Kϕ(xci)\begin{split}p(x)=\frac{1}{Z}\prod\limits_{i=1}^{K}\phi(x_{ci})\\ Z=\sum\limits_{x\in\mathcal{X}}\prod\limits_{i=1}^{K}\phi(x_{ci}) \end{split}

其中 ϕ(xci)\phi(x_{ci}) 叫做势函数,它必须是一个正值,可以记为:

ϕ(xci)=exp(E(xci))\phi(x_{ci})=\exp(-E(x_{ci}))

这个分布叫做 Gibbs 分布(玻尔兹曼分布)。于是也可以记为:p(x)=1Zexp(i=1KE(xci))p(x)=\frac{1}{Z}\exp(-\sum\limits_{i=1}^KE(x_{ci}))。这个分解和条件独立性等价(Hammesley-Clifford 定理),这个分布的形式也和指数族分布形式上相同,于是满足最大熵原理。

两种图的转换-道德图

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

  1. 链式:

    直接去掉箭头,p(a,b,c)=p(a)p(ba)p(cb)=ϕ(a,b)ϕ(b,c)p(a,b,c)=p(a)p(b|a)p(c|b)=\phi(a,b)\phi(b,c)

  2. V 形:

    由于 p(a,b,c)=p(b)p(ab)p(cb)=ϕ(a,b)ϕ(b,c)p(a,b,c)=p(b)p(a|b)p(c|b)=\phi(a,b)\phi(b,c),直接去掉箭头:

  3. 倒 V 形:

    由于 p(a,b,c)=p(a)p(c)p(ba,c)=ϕ(a,b,c)p(a,b,c)=p(a)p(c)p(b|a,c)=\phi(a,b,c),于是在 a,ca,c 之间添加线:

    观察着三种情况可以概括为:

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

更精细的分解-因子图

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

考虑一个无向图:

可以将其转为:

其中 f=f(a,b,c)f=f(a,b,c)。因子图不是唯一的,这是由于因式分解本身就对应一个特殊的因子图,将因式分解:p(x)=sfs(xs)p(x)=\prod\limits_{s}f_s(x_s) 可以进一步分解得到因子图。

推断

推断的主要目的是求各种概率分布,包括边缘概率,条件概率,以及使用 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)

变量消除的方法是在求解概率分布的时候,将相关的条件概率先行求和或积分,从而一步步地消除变量,例如在马尔可夫链中:

p(d)=a,b,cp(a,b,c,d)=cp(dc)bp(cb)ap(ba)p(a)p(d)=\sum\limits_{a,b,c}p(a,b,c,d)=\sum\limits_cp(d|c)\sum\limits_bp(c|b)\sum\limits_ap(b|a)p(a)

变量消除的缺点很明显:

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

推断-信念传播(BP)

为了克服 VE 的第一个缺陷-计算步骤无法存储。我们进一步地对上面的马尔可夫链进行观察:

要求 p(e)p(e),当然使用 VE,从 aa 一直消除到 dd,记 ap(a)p(ba)=mab(b)\sum\limits_ap(a)p(b|a)=m_{a\to b(b)},表示这是消除 aa 后的关于 bb 的概率,类似地,记 bp(cb)mab(b)=mbc(c)\sum\limits_bp(c|b)m_{a\to b}(b)=m_{b\to c}(c)。于是 p(e)=dp(ed)mbc(c)p(e)=\sum\limits_dp(e|d)m_{b\to c}(c)。进一步观察,对 p(c)p(c)

p(c)=[bp(cb)ap(ba)p(a)][dp(dc)ep(e)p(ed)]p(c)=[\sum\limits_bp(c|b)\sum\limits_ap(b|a)p(a)]\cdot[\sum\limits_dp(d|c)\sum\limits_ep(e)p(e|d)]

我们发现了和上面计算 p(e)p(e) 类似的结构,这个式子可以分成两个部分,一部分是从 aa 传播过来的概率,第二部分是从  e e 传播过来的概率。

一般地,对于图(只对树形状的图):

这四个团(对于无向图是团,对于有向图就是概率为除了根的节点为1),有四个节点,三个边:

p(a,b,c,d)=1Zϕa(a)ϕb(b)ϕc(c)ϕd(d)ϕab(a,b)ϕbc(c,b)ϕbd(d,b)p(a,b,c,d)=\frac{1}{Z}\phi_a(a)\phi_b(b)\phi_c(c)\phi_d(d)\cdot\phi_{ab}(a,b)\phi_{bc}(c,b)\phi_{bd}(d,b)

套用上面关于有向图的观察,如果求解边缘概率 p(a)p(a),定义 mcb(b)=cϕc(c)ϕbc(bc)m_{c\to b}(b)=\sum\limits_c\phi_c(c)\phi_{bc}(bc)mdb(b)=dϕd(d)ϕbd(bd)m_{d\to b}(b)=\sum\limits_d\phi_d(d)\phi_{bd}(bd)mba(a)=bϕba(ba)ϕb(b)mcb(b)dbm(b)m_{b\to a}(a)=\sum\limits_b\phi_{ba}(ba)\phi_b(b)m_{c\to b}(b)_{d\to b}m(b),这样概率就一步步地传播到了 aa

p(a)=ϕa(a)mba(a)p(a)=\phi_a(a)m_{b\to a}(a)

写成一般的形式,对于相邻节点 i,ji,j

mji(i)=jϕj(j)ϕij(ij)kNeighbour(j)imkj(j)m_{j\to i}(i)=\sum\limits_j\phi_j(j)\phi_{ij}(ij)\prod\limits_{k\in Neighbour(j)-i}m_{k\to j}(j)

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

  1. 任取一个节点 aa 作为根节点
  2. 对这个根节点的邻居中的每一个节点,收集信息(计算入信息)
  3. 对根节点的邻居,分发信息(计算出信息)

推断-Max-Product 算法

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

(a^,b^,c^,d^)=argmaxa,b,c,dp(a,b,c,dE)(\hat{a},\hat{b},\hat{c},\hat{d})=\mathop{argmax}_{a,b,c,d}p(a,b,c,d|E)

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

mji=maxjϕjϕijkNeighbour(j)imkjm_{j\to i}=\max\limits_{j}\phi_j\phi_{ij}\prod\limits_{k\in Neighbour(j)-i}m_{k\to j}

于是对于上面的图:

maxap(a,b,c,d)=maxaϕaϕabmcbmdb\max_a p(a,b,c,d)=\max_a\phi_a\phi_{ab}m_{c\to b}m_{d\to b}

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