概率图模型.pptx

概率图-背景

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

概率图模型 - 图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)

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

概率图-总览

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

概率图表示-有向图(贝叶斯网络)

条件独立性

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

概率图模型 - 图5%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)

那么实际的图中条件独立性是如何体现的呢？在局部任何三个节点，可以有三种结构：
1.head to tail
image.png
2.tail to tail
image.png
3.Head to head
image.png
对这种结构，概率图模型 - 图9 不与 概率图模型 - 图10 条件独立。

D划分

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

概率图模型 - 图15%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)

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

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

概率图模型 - 图20%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)

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

例子-具体模型

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

  1. 朴素贝叶斯，单一的条件独立性假设 概率图模型 - 图21%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)，在 D 划分后，所有条件依赖的集合就是单个元素。
  2. 高斯混合模型：混合的条件独立。引入多类别的隐变量 概率图模型 - 图22， 概率图模型 - 图23%3D%5Cmathcal%7BN%7D(%5Cmu%2C%5CSigma)#card=math&code=p%28x%7Cz%29%3D%5Cmathcal%7BN%7D%28%5Cmu%2C%5CSigma%29)，条件依赖集合为多个元素。
  3. 与时间相关的条件依赖
    1. Markov 链
    2. 高斯过程（无限维高斯分布）
  4. 连续：高斯贝叶斯网络
  5. 组合上面的分类
    • GMM 与时序结合：动态模型
      • HMM（离散）
      • 线性动态系统 LDS（Kalman 滤波）
      • 粒子滤波（非高斯，非线性）

        概率图表示-无向图(马尔可夫网络/马尔可夫随机场）

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

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

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

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

概率图模型 - 图31%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)

其中 概率图模型 - 图32#card=math&code=%5Cphi%28x_%7Bci%7D%29) 叫做势函数，它必须是一个正值，可以记为：

概率图模型 - 图33%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)

这个分布叫做 Gibbs 分布（玻尔兹曼分布）。于是也可以记为：概率图模型 - 图34%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)。这个分解和条件独立性等价（Hammesley-Clifford 定理），这个分布的形式也和指数族分布形式上相同，于是满足最大熵原理。