Skip to content

概率图模型

概率模型

概率模型：将学习任务归结于计算变量的概率分布

  • Y: 所关心的变量
  • O: 可观测变量集合
  • R: 其他变量集合

生成式模型：考虑联合分布 \(P(Y,R,O)\) 判别式模型：考虑条件分布 \(P(Y,R|O)\)

给定一组观测变量值，推断就是要由 \(P(Y,R,O)\) 或 \(P(Y,R|O)\) 得到条件概率分布 \(P(Y|O)\)

  • 概率图模型(probabilistic graphical model) 是一类用图来表达变量相关关系的概率模型.它以图为表示工具，最常见的是用一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系，即"变量关系图"

根据边的性质不间，概率图模型可大致分为两类:

  • 使用有向无环图表示变量间的依赖关系，称为有向图模型或贝叶斯网 (Bayesian network);
  • 使用无向图表示变量间的相关关系，称为无向图模型或马尔可夫网 (Markov network)

隐马尔可夫模型

  • 结构最简单的动态贝叶斯网，为有向图模型

两类变量：

  • 状态变量：表示第i时刻系统状态，假定状态变量是隐藏的、不可被观测的，因此状态变量亦称隐变量。状态空间 \(Y=\{s_1, s_2, ..., s_N\}\)

  • 观测变量：第i时刻的观测值，可以是离散型也可以是连续型。观测空间 \(X=\{o_1, ..., o_M\}\)

  • 马尔科夫链：系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态.基于这种依赖关系，所有变量的联合概率分布为

\[ P(x_1,y_1\dots,x_n,y_n) = P(y_1)P(x_1|y_1)\Pi_{i=2}^n P(y_i|y_{i-1})P(x_i|y_i) \]

除了结构信息，欲确定一个隐马尔可夫模型还需以下三组参数：

  1. 状态转移概率：模型在各个状态间转换的概率，通常记为矩阵 \(A=[a_{ij}]_{N\times N}\)，其中

    \[ a_{ij}=P(y_{t+1} = s_j| y_t=s_i) \]

  2. 输出观测概率：模型根据当前状态获得各个观测值的概率，通常记为矩阵 \(B=[b_{ij}]_{N\times M}\)，其中

    \[ b_{ij} = P(x_t=o_j|y_t=s_i), 1\leq i \leq N, 1\leq j \leq M \]

    表示在任意时刻t，若状态为 \(s_i\). 则观测值 \(o_j\) 被获取的概率.

  3. 初始状态概率：模型在初始时刻各状态出现的概率，通常记为 \(\pi = (\pi_1,..., \pi_N)\)，其中

    \[ \pi_i=P(y_1=s_i), 1\leq i \leq N \]

表示模型的初始状态为 \(s_i\) 的概率

通过指定状态空间 \(\mathcal{Y}\)，观测空间 \(\mathcal{X}\) 和上述三组参数\(\lambda = [A, B, \pi]\)，就能确定一个马尔科夫模型， 它按如下过程产生观测序列 \(\{x_1,\dots, x_n\}\)：

  1. 设置 \(t=1\)，并根据初始状态概率 \(\pi\) 选择初始状态 \(y_1\)
  2. 根据状态 \(y_t\) 和输出现测概率 B 选择观测变量取值 \(x_t\)
  3. 根据状态 \(y_t\) 和状态转移矩阵 A 转移模型状态，即确定 y_{t+1}
  4. 若 \(t<n\) 设置 \(t= t + 1\)，并转到第 (2) 步，否则停止.

马尔可夫随机场

马尔可夫随机场(Markov Random Field ，简称 MRF)是典型的马尔可夫网，是一种无向图模型

  • 图中每个结点表示一个或一组变量， 结点之间的边表示两个变量之间的依赖关系.
  • 马尔可夫随机场有一组势函数(potential functions) ，亦称"因子" (factor) ，这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。
  • 势函数 \(\psi_Q(x_Q)\) 的作用是刻画变量集z_Q中变量之间的相关关系，为非负函数且在所偏好的变量取值上有较大函数值。
  • 团（clique）：图中节点的子集，其中任意两节点间都有边连接。不能被其他团所包含的团叫极大团

  • 为便于计算，我们在每个极大团上定义势函数，进而计算联合概率：

    \[ P(x)=\frac{1}{Z}\Pi_{Q\in C*}\psi_Q(x_Q) \]

    \(Z=\Sigma_x \Pi_{Q\in C*}\psi_Q(x_Q)\) 为规范化因子，C*为极大团的集合

  • 分离集：若从结点集A中的结点到 B 中的结点都必须经过结点集C中的结点，则称结点集A和B被结点集C分离，C称分离集

  • 全局马尔可夫性：给定两个变量子集的分离集，则这两个变量子集条件独立

其推论：

  • 局部马尔科夫性：给定某变量的邻接变量，则该变量条件独立于其他变量
  • 成对马尔科夫性：给定所有其他变量，两个非邻接变量条件独立

条件随机场

条件随机场(Conditional Random Field ，简称 CRF)：判别式的无向图模型。前面的隐马尔科夫模型和马尔科夫随机场都是生成式模型

条件随机场试图对多个变量在给定观测值后的条件概率进行建模

学习与推断

变量消去

  • 精确确推断的实质是一类动态规划算法，它利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量
  • 变量消去法是最直观的精确推断算法，也是构建其他精确推断算法的基础

信念传播

  • 信念传播(Belief Propagation)算法将变量消去法中的求和操作看作一个消息传递过程，较好地解决了求解多个边际分布时的重复计算问题
  • 在信念传播算法中，一个结点仅在接收到来自其他所有结点的消息后才能向另一个结点发送消息，且结点的边际分布正比于它所接收的消息的乘积
  • 若图结构中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而能计算所有变量上的边际分布：
    • 指定一个根结点，从所有叶结点开始向根结点传递消息，直到根结点收到所有邻接结点的消息
    • 从根结点开始向叶结点传递消息，直到所有叶结点均收到消息

近似推断

  • 精确推断方法通常需要很大的计算开销，因此在现实应用中近似推断方法更为常用.
  • 近似推断方法大致可分为两大类:
    1. 第一类是采样(sampling) ，通过使用随机化方法完成近似;
    2. 第二类是使用确定性近似完成近似推断，典型代表为变分推断

MCMC采样

  • MCMC 方法先设法构造一条马尔可夫链，使其收敛至平稳分布恰为待估计参数的后验分布，然后通过这条马尔可夫链来产生符合后验分布的样本，并基于这些样本来进行估计。
  • 这里马尔可夫链转移概率的构造至关重要，不同的构造方法将产生不同的 MCMC 算法.

变分推断（variational inference）

变分推断通过使用己知简单分布来逼近需推断的复杂分布，并通过限制近 似分布的类型，从而得到某种局部最优、但具有确定解的近似后验分布.

话题模型

话题模型(topic model) 是一族生成式有向图模型，主要用于处理离散型的数据(如文本集合)，在信息检索、自然语言处理等领域有广泛应用

  • 词：待处理数据的基本离散单元
  • 文档：待处理的数据对象，它由一组词组成，这些词在文档中是不计顺序的
  • 话题：表示一个概念，具体表示为一系列相关的词，以及它们在该概念下出现的概率
  • 数据对象只要能用词袋描述，就可使用话题模型“话题”表示一个概念，具体表示为一系列相关的词，以及它们在该概念下出现的概率。

Comments