概率图模型

概率图模型是用图结构来表达随机变量依赖关系的概率模型,用结点表示一个或一组随机变量,用边来表示随机变量之间的概率依赖关系。

信封问题

桌上有两个信封,其中一个信封装有一个红球(价值 $100$ 美元)和一个黑球,另外一个信封装有两个黑球。


-w300

你随机选了一个信封并从中随机取出一个球,发现是黑球。
这时你被告知可以有一次换信封重新取球的机会,你会选择换还是不换?

随机变量:
$E={1,0}, B={红,黑}$,
$P(E=1)=P(E=0)=1/2$
$P(B=红|E=1)=1/2, P(B=红|E=0)=0$

实际上我们在考察 $P(E=1|B=黑) \ge 1/2$

$$ P(E=1|B=黑) = \frac {P(B=黑|E=1)P(E=1)} {P(B=黑|E=1)P(E=1)P(B=黑|E=0)P(E=0)} = \frac 1 3 $$

所以我们选择

有向图模型

有向图模型又称贝叶斯网络,以有向边表示变量间的因果关系。

贝叶斯网络


-w555

联合概率分布分解形式


-w555

草坪问题


-w555
  • 同时观测到下雨、给草坪浇水、草坪湿的概率有多大?
    $$ P(G=1,S=1,R=1) = P(G=1|S=1,R=1)P(S=1|R=1)P(R=1) = 0.99 \times 0.01 \times 0.2 = 0.00198 $$
  • 当已知不下雨时,观测到草坪湿的概率有多大?
    $$ P(G=1|R=0) = \frac {P(G=1,R=0)} {P(R=0)} = \frac {\sum_{S \in {0,1}} P(G=1,S,R=0)} {P(R=0)} = \frac {0.288+0} {0.8} = 0.36 $$
  • 当已知草坪湿了后,推测下雨的概率有多大?
    $$ P(R=1|G=1) = \frac {P(G=1,R=1)} {P(G=1)} = \frac {\sum_{S \in {0,1}} P(G=1,S,R=1)} {\sum_{S,R \in {0,1}}P(G=1,S,R)} = \frac {0.00198+0.1584} {0.00198+0.288+0.1584+0} \approx 0.3577 $$
  • 当已知草坪湿了后,推测给草坪浇过水的概率有多大?
    $$ P(S=1|G=1) = \frac {P(G=1,S=1)} {P(G=1)} = \frac {\sum_{R \in {0,1}} P(G=1,S=1,R)} {\sum_{S,R \in {0,1}}P(G=1,S,R)} = \frac {0.00198+0.288} {0.00198+0.288+0.1584+0} \approx 0.6467$$

条件独立性


-w555
-w555
-w555

无向图模型

无向图模型又称马尔科夫随机场,以无向边表示变量间的简单相关。

马尔科夫随机场


-w555

上图的极大团为 ${x_1,x_2}{x_1,x_3}{x_2,x_4}{x_3,x_5}{x_2,x_5,x_6}$

联合概率分布分解形式


-w555

最简单的马尔科夫随机场


-w555

条件独立性


-w555
-w555

学习与推断


-w555
-w555
-w555

精确推断

精确推断经过变换来计算 $P(x_E)$ 或 $P(x_Q|x_E)$ 的精确值。

变量消除

算法动机:利用图模型的紧凑概率分布形式来削减计算量。


-w555

变量消除的顺序为 $x_1$, $x_2$,$x_4$,$x_3$:

$$ \begin{align}
P(x_5) & = \sum_{x_4}\sum_{x_3}\sum_{x_2}\sum_{x_1} P(x_1)P(x_2|x_1)P(x_3|x_2)P(x_4|x_3)P(x_5|x_3) \nonumber \\
& = \sum_{x_4}\sum_{x_3}\sum_{x_2}P(x_3|x_2)P(x_4|x_3)P(x_5|x_3) \sum_{x_1} P(x_1)P(x_2|x_1) \nonumber \\
& = \sum_{x_4}\sum_{x_3}\sum_{x_2}P(x_3|x_2)P(x_4|x_3)P(x_5|x_3) m_{12}(x_2) \nonumber \\
& = \sum_{x_4}\sum_{x_3}P(x_4|x_3)P(x_5|x_3) \sum_{x_2}P(x_3|x_2)m_{12}(x_2) \nonumber \\
& = \sum_{x_4}\sum_{x_3}P(x_4|x_3)P(x_5|x_3) m_{23}(x_3) \nonumber \\
& = \sum_{x_3}P(x_5|x_3) m_{23}(x_3)\sum_{x_4}P(x_4|x_3) \nonumber \\
& = \sum_{x_3}P(x_5|x_3) m_{23}(x_3) m_{43}(x_3) \nonumber \\
& = m_{35}(x_5) \nonumber
\end{align}$$


-w555

信念传播

算法动机:将变量消除过程中产生的中间结果视为可复用的消息,避免重复计算。


-w555
  • $m_{12}(x_2)$ 是 $x_1$ 向 $x_2$ 传递的一个消息
  • $m_{12}(x_2)$ 对 $x_1$ 进行了求和操作,是关于 $x_2$ 的函数
  • $m_{12}(x_2)$ 仅与图的拓扑结构有关,与证据变量的选取无关(可复用)

-w555

近似推断

精确推断的计算复杂度随着极大团规模的增长呈指数级增长,适用范围有限。
近似推断采用的是采样的方法,在较低的时间复杂度下获得原问题的近似解,适用范围更广,可操作性更强。

基于采样的近似推断

问题:估计条件概率 $P(x_Q|x_E)$ :

$$P(x_Q=c_Q|x_E) = \int 1_{(x_Q=c_Q)} P(x_Q|x_E)dx_Q$$

  1. 根据 $P(x_Q|x_E)$ 抽取一组样本 $x^{(1)},…,x^{(m)}$
  2. 计算 $1_{(x_Q=c_Q)}$ 在这组样本上的均值来近似 $P(x_Q=c_Q|x_E)$
    $$ P(x_Q=c_Q|x_E) \approx \frac 1 m \sum_{i=1}^m 1_{(x^{(i)}=c_Q)}$$

前向采样

前向采样是依照贝叶斯网络的(条件)概率直接采样。

问题:通过采样来确定 $P(B=1|E=0,J=1)$


-w555

对于第一次采样,采样 $r\sim U(0,1)$;若 $r\lt 0.001$,则 $B=1$,否则 $B=0$。


-w272

前向采样存在很多问题:

  1. 对于小概率事件采样困难,可能经历漫长的采样过程也无法获得足够多满足条件的样本
  2. 仅适用于贝叶斯网络,不适用于马尔科夫随机场

吉布斯采样

吉布斯采样直接依照条件概率 $P(x_Q|x_E)$ 进行采样


-w555
-w555
-w555

总结

  • 吉布斯采样解决了小概率时间采样难的问题
  • 同时适用于贝叶斯网络和马尔科夫随机场
  • 简单易推导,时间和空间开销合理

隐马尔科夫模型

模型介绍

隐马尔科夫模型($Hidden\;Markov\;Model,HMM$)是关于时序的概率模型,是最简单的动态贝叶斯网络。


-w555

其中,第三行的假设叫做齐次马尔可夫性假设,第四行的假设叫做观测独立性假设,显然,

$$ P(x_1,y_1,\dots, x_n, y_n) = P(y_1)P(x_1|y_1) \prod_{t=2}^n P(y_t|y_t-1)P(x_t|y_t) $$

隐马尔科夫模型由 $A$,$B$,$\pi$ 唯一决定, $A$,$B$,$\pi$ 是隐马尔科夫模型的三要素

  • 状态转移矩阵 $A = [a_{ij}]_{N\times N}$,其中
    $$ a_{ij} = P(y_{t+1}=s_j|y_t=s_i)\; 1\le i, j\le N $$
    表示在时刻 $t$ 处于状态 $s_i$ 的条件下下一时刻转移到状态 $s_j$ 的概率。

  • 观测概率矩阵 $B = [b_{ij}]_{N\times M}$,其中
    $$ b_{ij} = P(x_t=o_j|y_t=s_i)\; 1\le i\le N, 1\le j \le M$$
    表示在时刻 $t$ 处于状态 $s_i$ 的条件下观测到 $o_j$ 的概率。

  • 初始状态概率向量 $\pi=(\pi_1, \pi_2,\dots, \pi_N)$,其中
    $$\pi = P(y_1 = s_i)\; 1\le i\le N $$
    表示系统在初始状态状态为 $s_i$ 的概率。

生成过程


-w555

生成过程示例


-w300

再回到最开始的信封问题,我们规定:

  • 等概率随机选择一个信封并从中随机抽取一个球,记录其颜色后放回
  • 再次选择一个信封,如果上一次选的是第一个信封,则本次默认选择第二个信封;否则等概率随机选择
  • 确定信封后,再从这个信封里随机抽出一个球,记录其颜色后放回
  • 如下下去重复进行五次,得到一个球的颜色观测序列
    $$ {红,黑,黑,黑,红} $$

于是可以得到:


-w555

三个基本问题

  1. 概率计算问题:给定模型 $\lambda = (A,B,\pi)$ 和观测序列 $x={x_1,\dots,x_n}$,计算在模型 $\lambda$ 下观测序列 $x$ 出现的概率 $P(x|\lambda)$,即评估模型与观测序列之间的匹配程度,典型方法有前向后向算法。
  2. 预测问题:给定模型 $\lambda = (A,B,\pi)$ 和观测序列 $x={x_1,\dots,x_n}$,求使得条件概率 $P(y|x,\lambda)$ 最大的状态序列 $y={y_1,\dots,y_n}$,即根据观测序列推断出的隐藏的状态模型(词项标注、语音识别),典型方法有维特比算法。
  3. 学习问题:给定观测序列 $x={x_1,\dots,x_n}$,学习模型$\lambda = (A,B,\pi)$ 参数使得该序列出现的概率 $P(x|\lambda)$ 最大,即使训练模型能够更好地描述观测数据,典型方法有 $EM$。

概率计算问题

定模型 $\lambda = (A,B,\pi)$ 和观测序列 $x={x_1,\dots,x_n}$,计算在模型 $\lambda$ 下观测序列 $x$ 出现的概率 $P(x|\lambda)$,即评估模型与观测序列之间的匹配程度。

  • 直接计算法
  • 前向后向算法

直接计算法

  • 列举所有可能的长度为 $n$ 的状态序列 $y={y_1,\dots,y_n}$
    $$ Pr(y|\lambda) = \pi_{y1}a_{y_1y_2}a_{y_2y_3}\dots a_{y_n-1y_n} $$
  • 求各状态序列 $y$ 与观测序列 $x$ 的联合概率 $P(x,y|\lambda)$
    $$Pr(x|y,\lambda) = b_{y_1}(x_1)b_{y_2}(x_2)\dots b_{y_n}(x_n) \\ Pr(x,y|\lambda) = Pr(x|y,\lambda)Pr(y|\lambda) = \pi_{y_1}b_{y_1}(x_1)a_{y_1y_2} b_{y_2}(x_2)\dots a_{y_{n-1}y_n}b_{y_n}(x_n)$$
  • 对所有可能的状态序列 $y$ 求和,得到 $P(x|\lambda)$
    $$Pr(x|\lambda) = \sum_yPr(x,y|\lambda) = \sum_{y_1,y_2,\dots,y_n}\pi_{y_1}b_{y_1}(x_1)a_{y_1y_2} b_{y_2}(x_2)\dots a_{y_{n-1}y_n}b_{y_n}(x_n) $$

显然,该方法的计算复杂度为 $O(nN^n)$,并不适用于大规模的数据。

前向后向算法

前向算法

前向概率:给定隐马尔科夫模型 $\lambda = (A,B,\pi)$,记到时刻 $t$ 部分观测序列为 $x_1,x_2\dots x_t$ 且状态为 $s_i$ 的概率为前向概率,记作
$$\alpha_t(i) = Pr(x_1,x_2\dots x_t,y_t=s_i|\lambda) $$

前向概率递推公式



其中,$b_i(x_{t+1})$ 表示的是在状态为 $y_{t+1}=s_i$ 观测值为 $x_{t+1}$ 的观测概率,例如假设 $x_{t+1} = o_j$,则有 $b_i(x_{t+1}) = b_i(o_j) = b_{ij}$



显然前向算法的时间复杂度为 $O(nN^2)$

算法实例


后向算法

后向概率:给定隐马尔科夫模型 $\lambda = (A,B,\pi)$,记在时刻 $t$ 状态为 $s_i$ 的条件下,从时刻 $t+1$ 到 $n$ 的部分观测序列为 $x_{t+1},x_{t+2}\dots x_n$ 的概率为后向概率,记作
$$\beta_t(i) = Pr(x_{t+1},x_{t+2}\dots x_n | y_t=s_i,\lambda) $$

后向概率递推公式




显然后向算法的时间复杂度也为 $O(nN^2)$

前向后向算法

利用前向概率和后向概率的递推公式,可以将观测序列统一写成


-w444

$$Pr(x|\lambda) =\sum_{i=1}^N \alpha_t(i)\beta_t(i)\quad t=1,2,\dots n $$

进一步展开:


-w444

$$Pr(x|\lambda) =\sum_{i=1}^N\sum_{j=1}^N \alpha_t(i) a_{ij}b_j(x_{t+1})\beta_{t+1}(i)\quad t=1,2,\dots n-1 $$

相关概率和期望

  • 给定隐马尔科夫模型 $\lambda = (A,B,\pi)$ 和观测序列 $x$,在时刻 $t$ 处于状态 $s_i$ 的概率
    $$ \gamma_t(i) = Pr(y_t=s_i|x,\lambda) = \frac {Pr(y_t=s_i,x|\lambda)} {Pr(x|\lambda)} = \frac {\alpha_t(i)\beta_t(i)} {\sum_{j=1}^N \alpha_t(j)\beta_t(j)} $$
  • 给定隐马尔科夫模型 $\lambda = (A,B,\pi)$ 和观测序列 $x$,在时刻 $t$ 处于状态 $s_i$ 并且在时刻 $t+1$ 处于状态 $s_j$ 的概率
    $$\xi_t(i,j) = Pr(y_t=s_i, y_{t+1}=s_j|x,\lambda) = \frac {Pr(y_t=s_i, y_{t+1}=s_j, x|\lambda)} {Pr(x|\lambda)} = \frac {\alpha_t(i) a_{ij}b_j(x_{t+1})\beta_{t+1}(i)} {\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i) a_{ij}b_j(x_{t+1})\beta_{t+1}(i)}$$
  • 将 $\gamma_t(i)$ 和 $\xi_t(i,j)$ 相加,我们可以得到一些有用的期望
    • 在观测 $x$ 下状态 $s_i$ 出现的期望值为为 $ \sum_{t=1}^n \gamma_t(i)$
    • 在观测 $x$ 下由状态 $s_i$ 转移的期望值为 $ \sum_{t=1}^{n-1} \gamma_t(i)$
    • 在观测 $x$ 下由状态 $s_i$ 转移到状态状态 $s_j$ 期望值为 $ \sum_{t=1}^{n-1} \xi_t(i,j)$

预测问题

给定模型 $\lambda = (A,B,\pi)$ 和观测序列 $x={x_1,\dots,x_n}$,求使得条件概率 $P(y|x,\lambda)$ 最大的状态序列 $y={y_1,\dots,y_n}$,即根据观测序列推断出隐藏的模型状态。

  • 近似算法
  • 维特比算法

近似算法

在每个时刻 $t$ 选择在该时间最有可能出现的状态 $y_t^*$,得到一个状态序列 $y^*={y_1^*,y_2^*,\dots,y_n^*}$,将它作为预测结果

$$ y_t^* = \arg\max_{1\le i\le N} Pr(y_t=s_i|x,\lambda) = \arg\max_{1\le i\le N}\gamma_t(i) = \arg\max_{1\le i\le N} \frac {\alpha_t(i)\beta_t(i)} {\sum_{j=1}^N \alpha_t(j)\beta_t(j)}\quad t=1,2,\dots, n$$

近似算法的优点是计算简单,缺点是不能保证预测的状态序列整体是合法的,即可能会出现 $a_{ij}=0$ 的情况,尽管如此,近似算法仍然是有用的。

维特比算法

维特比算法实际上是利用动态规划来解隐马尔科夫模型的预测问题,根据动态规划的原理,如果最优路径在时刻 $t$ 通过节点 $i_t^*$,那么这一路径从节点 $i_t^*$ 到终点 $i_T^*$ 的部分路径,对于从 $i_t^*$ 到 $i_T^*$ 的所有可能路径来说,必然是最优的。
为了实现维特比算法,我们引入两个变量:

  • 维特比向量:在时刻 $t$,隐马尔科夫模型沿着一条路径到达状态 $s_i$,并输出观测序列 $x_1,x_2,\dots,_t$ 的最大概率
    $$ \begin{align} \delta_t(i) &= \max_{y_1,y_2,\dots,y_{n-1}}Pr(y_t=s_i, y_{t-1},\dots , y_1,x_t,x_{t-1},\dots,x_1|\lambda) \nonumber \\&=\max_{1\le j \le N} \delta_{t-1}(j)a_{ji}b_i(x_t)\quad t=2,3,\dots, n \nonumber \end{align} $$
    其中,$\delta_1(i) = \pi_1b_i(x_1) $
  • 路径变量:记录该路径上状态 $s_i$ 的前一个状态,即概率最大路径上的前一个节点
    $$ \phi_t(i) = \arg\max_{1\le j \le N} \delta_{t-1}(j)a_{ji}b_i(x_t)\quad t=2,3,\dots,n $$

算法过程



显然维特比算法的计算复杂度为 $O(nN^2)$

算法实例


学习问题

给定观测序列 $x={x_1,\dots,x_n}$,学习模型$\lambda = (A,B,\pi)$ 参数使得该序列出现的概率 $P(x|\lambda)$ 最大,即使训练模型能够更好地描述观测数据。

  • 监督学习方法
  • 非监督学习方法($Baum-Welch$算法)

监督学习方法


-w555

非监督学习方法


-w555

条件随机场

条件随机场($Conditional\;Random\;Field,CRF$)是给定随机变量 $x$ 的条件下,随机变量 $y$ 的马尔科夫随机场。

  • $G(V,E)$ 是 $y$ 中的随机变量构成的无向图,途中每个变量在给定 $x$ 的条件下都满足马尔可夫性
    $$ P(y_v|x ,y_{V \backslash {v}})=P(y_v|x,y_{MB(v)}) $$
    • $y_v$ 是图 $G$ 中任意一个随机变量
    • $y_{V \backslash {v}}$ 是图 $G$ 中除了 $y_v$ 外其他随机变量
    • $y_{MB(v)}$ 是 $y_v$ 在图 $G$ 中的马尔科夫毯

线性链条件随机场


-w555
-w555

词性标注

隐马尔科夫模型:


-w555

线性链条件随机场


-w555

三个基本问题


-w555

参考文献:
[1] 王泉,《统计机器学习》,中国科学院大学2017年秋季研究生课程