概率无向图模型(probabilistic undirected graphical model),又称为马尔可夫随机场(Markov random field),是一个可以由无向图表示的联合概率分布。
图Graph包含顶点node、边edge,无向图指的是边没有方向的图。
概率图模型指的是,图中的边表示随机变量之间的概率依赖关系。
无向图表示的随机变量之间存在 成对马尔科夫性、局部马尔科夫性、全局马尔科夫性 。
分别对应随机变量
。其他所有结点为
, 对应随机变量组为
。
成对马尔可夫性指:
是无向图中任意一个结点,
是与
有连接的所有结点,
是
和
以外的其他所有结点。
局部马尔可夫性指:
在
时,上式等价于
是图中被结点集合
分开的任意结点集合
全局马尔可夫性指:
上述成对的、局部的、全局的马尔可夫性定义是等价的
团与最大团 的定义:
任何两个结点均有连接的结点子集称为团,若
是无向图的一个团,且不能再加进任何一个结点使其成为一个更大的团,则称
为最大团(maximal clique)
例如,上图中2个结点组成的团有5个
,有2个最大团
。
而
不是一个团,因为
和
没有边连接。
将概率无向图模型的联合概率分布表示为其 最大团 上的随机变量的函数的乘积形式的操作,称为 概率无向图模型的因子分解(factorization) 。
给定概率无向图模型,
是图
上的最大团,
表示
对应的随机变量。那么,概率无向图模型的联合概率分布
可写作所有最大团
上的函数
的乘积形式:
`$
\color{red}P(Y) = \frac{1}{Z} \prod\limits_C \Psi_C(Y_C),\quad 其中Z=\sum\limits_Y \prod\limits_C \Psi_C(Y_C)是规范化因子
$`
函数
称为势函数(potential function),通常定义为指数函数
条件随机场:
设
与
是随机变量,
是在给定
的条件下
的条件概率分布。若随机变量
构成一个无向图的马尔科夫随机场,即:
`$
\color{red}P(Yv|X,Y\omega, \omega \neq v) = P(Yv|X,Y\omega,\omega \sim v)
$`
左边表示,条件里是多个
, 且
;右边是多个
, 且
都与
相连。则称条件概率分布
为条件随机场。
线性链条件随机场:
`$
\color{red}P(Yi|X,Y_1,...,Y{i-1},Y{i+1},...,Y_n) = P(Y_i|X,Y{i-1},Y_{i+1})\
i=1,2,...,n(在i=1,n时只考虑单边)
$`
则称条件概率分布
为线性链条件随机场。在标注问题中,
表示输入观测序列,
表示对应的输出标记序列或状态序列。
根据上面,可以给出线性链条件随机场
的因子分解式,各因子是定义在相邻两个结点(最大团)上的势函数。在随机变量
取值为
的条件下,随机变量
取值为
的条件概率具有如下形式:
`$
\begin{aligned}
\color{red}P(y|x) &\color{red}= \frac{1}{Z(x)} \exp \Bigg( \sum\limits{i,k} \lambda_k t_k (y{i-1},yi,x,i) + \sum\limits{i,l} \mu_ls_l(y_i,x,i)\Bigg)\
其中,Z(x) &= \sum\limitsy \exp \Bigg( \sum\limits{i,k} \lambdak t_k (y{i-1},yi,x,i) + \sum\limits{i,l} \mu_ls_l(y_i,x,i)\Bigg)
\end{aligned}
$`
式中,
是特征函数,
是对应权值。
是规范化因子。
是边上的特征函数,称为转移特征,依赖于当前和前一个位置
是结点特征函数,称为状态特征,依赖于当前位置
都依赖于位置,是局部特征函数。函数取值 1 或者 0
特征函数,
对应权值 确定
设有一标注问题:输入观测序列
,输出标记序列
,
取值于
.
假设特征
和对应权值
如下:
`$
\begin{aligned}
t1&=t_1(y{i-1}=1,y_i=2,x,i), i=2,3 , \lambda_1=1, 特征函数取值为1 (其余条件取0)\
t_2 &= t_2(y_1=1,y_2=1,x,2), \quad\quad \lambda_2=0.6\
t_3 &= t_3(y_2=2,y_3=1,x,3) ,\quad\quad \lambda_3=1\
t_4 &= t_4(y_1=2,y_2=1,x,2) ,\quad\quad \lambda_4=1\
t_5 &= t_5(y_2=2,y_3=2,x,3) ,\quad\quad \lambda_5=0.2\
s_1 &= s_1(y_1=1,x,1), \quad\quad\quad\quad\quad \mu_1=1\
s_2 &= s_2(y_i=2,x,i), i=1,2 \quad\quad \mu_2=0.5\
s_3 &= s_3(y_i=1,x,i), i=2,3 \quad\quad \mu_3=0.8\
s_4 &= s_4(y_3=2,x,3), \quad\quad\quad\quad\quad \mu_4=0.5
\end{aligned}
$`
对给定的观测序列
,求标记序列为
的非规范化条件概率(未除以规范化因子的条件概率)。
解:
由线性链条件随机场模型有:
`$
\begin{aligned}
P(y|x) &\propto \exp \Bigg( \sum\limits{i,k} \lambda_k t_k (y{i-1},yi,x,i) + \sum\limits{i,l} \mu_ls_l(y_i,x,i)\Bigg)\
&= \exp \Bigg\sum\limits{k=1}^5 \lambda_k \sum\limits{i=2}^3tk (y{i-1},yi,x,i) + \sum\limits{k=1}^4 \muk \sum\limits{i=1}^3 s_k(y_i,x,i) \Bigg\
&= \exp (1+0.2+1+0.5+0.5) = \exp (3.2)
\end{aligned}
$`
个转移特征和
个状态特征,
,记特征函数:
`$ fk(y{i-1},y_i,x,i)=\left{
\begin{aligned}
tk(y{i-1},y_i,x,i), \quad\quad\quad\quad k=1,2,...,K_1 \
s_l(y_i,x,i), \quad k=K_1+l; l=1,2,...,K_2
\end{aligned}
\right.
$`
求和,记作:
`$
fk(y,x) = \sum\limits{i=1}^n fk(y{i-1},y_i,x,i),k=1,2,...,K
$`
表示特征
的权值,即
`$ \omega_k=\left{
\begin{aligned}
\lambda_k, \quad\quad\quad\quad\quad\quad k=1,2,...,K_1 \
\mu_l, \quad k=K_1+l; l=1,2,...,K_2
\end{aligned}
\right.
$`
`$P(y|x) = \frac{1}{Z(x)} \exp \sum\limits_{k=1}^K \omega_kf_k(y,x)\
Z(x) = \sum\limitsy \exp \sum\limits{k=1}^K \omega_kf_k(y,x)$`
表示权值向量,
表示全局特征向量,即
,对比2.2节的表达式,可见该式少了对位置
求和
的方阵(m为状态的个数,行为
位置的状态,列为
位置的状态,值为
, 用矩阵
来表示所有的情况)
是规范化因子,是
个矩阵乘积的
位置的元素,是路径
所有可能的状态组合的非规范化概率之和。
假设有如下线性链条件随机场,观测序列
, 状态序列
, 标记
, 假设
,各个位置的随机矩阵
是
求状态序列
以
为起点,
为终点所有路径的非规范化概率及规范化因子。
解:
所有可能的路径有 8 条:
各路径的非规范化概率是:
`$a{01}b{11}c{11},\quad a{01}b{11}c{12},\quad a{01}b{12}c{21},\quad a{01}b{12}c{22}\
a{02}b{21}c{11},\quad a{02}b{21}c{12},\quad a{02}b{22}c{21},\quad a{02}b{22}c{22}$`
规范化因子
`$Z\omega(x) = [M_1(x)M_2(x) M_3(x)M{4}(x)]_{1,1}\
a{01}b{11}c{11}+ a{01}b{11}c{12}+ a{01}b{12}c{21}+a{01}b{12}c{22}+\
a{02}b{21}c{11}+ a{02}b{21}c{12}+ a{02}b{22}c{21}+a{02}b{22}c{22}$`
矩阵其他3个位置为 0 。可见规范化因子恰好等于所有路径的非规范化概率之和。
,输入序列
,输出序列
以及相应数学期望
类似HMM,引进前向-后向向量进行计算。
对每个位置
,定义前向向量
:
`$\alpha_0(y|x)=\left{
\begin{aligned}
1, \quad y=start\
0, \quad\quad\quad 否则
\end{aligned}
\right.
$`
递归公式:
又可以表示为:
表示在位置
的标记是
并且从 1 到
的前部分标记序列的非规范化概率,
可取的值有
个,所以
是
维列向量,
表示转置。
同样,对每个位置
,定义后向向量
:
`$\beta{n+1}(y{n+1}|x)=\left{
\begin{aligned}
1, \quad y_{n+1}=stop\
0, \quad\quad\quad\quad 否则
\end{aligned}
\right.
$`
又可以表示为:
表示在位置
的标记是
并且从
到
的后部分标记序列的非规范化概率。
根据前后向向量的定义,可知:
`$
P(Y_i = y_i|x) = \frac{\alpha_i^T(y_i|x) \beta_i(y_i|x)}{Z(x)}\
P(Y{i-1}=y{i-1},Yi = y_i|x) = \frac{\alpha{i-1}^T(y{i-1}|x)M_i(y{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\
其中,Z(x) = \alpha_n^T(x)\mathbf{1} = \mathbf{1}\beta_1(x),\mathbf{1}是元素均为1的m维列向量。
$`
关于条件分布
的数学期望
`$\begin{aligned}
E{P(Y|X)}f_k &= \sum{y}P(y|x)f_k(y,x)\
&= \sum{y}P(y|x)\sum{i=1}^{n+1} fk(y{i-1},y_i,x,i)\
&= \sum{i=1}^{n+1}\sum{y{i-1}y_i}f_k(y{i-1},yi,x,i)P(Y{i-1}=y_{i-1},Y_i=y_i|x)\
&= \sum{i=1}^{n+1}\sum{y{i-1}y_i}f_k(y{i-1},yi,x,i)\frac{\alpha{i-1}^T(y{i-1}|x)M_i(y{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\
\end{aligned}$`
其中,
,
的经验分布为
,特征函数
关于联合分布
的数学期望:
`$\begin{aligned}
E{P(X,Y)}f_k &= \sum{x,y}P(x,y)f_k(y,x)\
&= \sumx\tilde P(x) \sum{y}P(y|x)\sum{i=1}^{n+1} f_k(y{i-1},y_i,x,i)\
&= \sumx\tilde P(x)\sum{i=1}^{n+1}\sum{y{i-1}yi}f_k(y{i-1},yi,x,i)\frac{\alpha{i-1}^T(y{i-1}|x)M_i(y{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}
\end{aligned}$`
其中,
,
通过一次前向扫描计算
,一次后向扫描计算
,可以计算所有的概率、特征的期望
学习方法包括极大似然估计和正则化的极大似然估计。
具体的优化实现算法有改进的迭代尺度法IIS、梯度下降法、拟牛顿法。
看不懂(跳过)
给定条件随机场
和观测序列
,求条件概率最大的状态序列
。与 HMM 类似,使用维特比算法。
由式
可得:
`$
\begin{aligned}
y^* &= \argmaxy P\omega(y|x)\
&= \argmaxy \frac{\exp (\omega \cdot F(y,x))}{Z\omega(x)}\
&= \argmax_y \exp(\omega \cdot F(y,x))\
&= \argmax_y (\omega \cdot F(y,x))
\end{aligned}
$`
其中:
`$
\begin{aligned}
\omega &= (\omega_1,\omega_2,...,\omega_K)^T\
F(y,x) &= (f_1(y,x),f_2(y,x),...,f_K(y,x))^T\
fk(y,x) &= \sum\limits{i=1}^nfk(y{i-1},y_i,x,i),\quad k=1,2,...,K
\end{aligned}
$`
最优路径问题:
其中,
是局部特征向量
维特比算法:
的非规范化概率:
的各个状态
的非规范化概率的最大值,同时记录最大路径
时终止,求得非规范化概率最大值
,最优路径终点
设有一标注问题:输入观测序列
,输出标记序列
,
取值于
.
假设特征
和对应权值
如下:
`$
\begin{aligned}
t1&=t_1(y{i-1}=1,y_i=2,x,i), i=2,3 , \lambda_1=1, 特征函数取值为1 (其余条件取0)\
t_2 &= t_2(y_1=1,y_2=1,x,2), \quad\quad \lambda_2=0.6\
t_3 &= t_3(y_2=2,y_3=1,x,3) ,\quad\quad \lambda_3=1\
t_4 &= t_4(y_1=2,y_2=1,x,2) ,\quad\quad \lambda_4=1\
t_5 &= t_5(y_2=2,y_3=2,x,3) ,\quad\quad \lambda_5=0.2\
s_1 &= s_1(y_1=1,x,1), \quad\quad\quad\quad\quad \mu_1=1\
s_2 &= s_2(y_i=2,x,i), i=1,2 \quad\quad \mu_2=0.5\
s_3 &= s_3(y_i=1,x,i), i=2,3 \quad\quad \mu_3=0.8\
s_4 &= s_4(y_3=2,x,3), \quad\quad\quad\quad\quad \mu_4=0.5
\end{aligned}
$`
求给定的观测序列
对应的最优标记序列
。
解:
`$\delta_1(j) = \omega \cdot F_1(y_0 = start, y_1 = j, x), \quad j=1,2 \quad \quad \quad \quad \quad \quad \quad \quad \
i=1, \quad \delta_1(1) = \mu_1s_1=1,\quad \delta_1(2) = \mu_2s_2 = 0.5 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $`
`$
\begin{aligned}
i=2\quad \delta_2(l) &=\max\limits_j {\delta_1(j) + \omega \cdot F_2(j,l,x)}\
\delta_2(1) &= \max{1+\lambda_2t_2 + \mu_3s_3,\quad 0.5+\lambda_4t_4 + \mu_3s_3} = \max{2.4,2.3} = 2.4\
&\quad\Psi_2(1) = 1\
\delta_2(2) &= \max{1+\lambda_1t_1 + \mu_2s_2,\quad 0.5+ \mu_2s_2} = \max{2.5,1} = 2.5\
&\quad\Psi_2(2) = 1\
i=3 \quad \delta_3(l) &=\max\limits_j {\delta_2(j) + \omega \cdot F_3(j,l,x)}\
\delta_3(1) &= \max{2.4+ \mu_3s_3,\quad 2.5+\lambda_3t_3 + \mu_3s_3} = \max{3.2,4.3} = 4.3\
&\quad\Psi_3(1) = 2\
\delta_3(2) &= \max{2.4+\lambda_1t_1 + \mu_4s_4,\quad 2.5+\lambda_5t_5 + \mu_4s_4} = \max{3.9,3.2} = 3.9\
&\quad\Psi_3(2) = 1\
\end{aligned}
$`
`$
\max\limits_y(\omega \cdot F(y,x)) = \max \delta_3(l) = \delta_3(1) = 4.3\
y_3^* = \argmax\limits_l \delta_3(l) = 1$`
`$y_2^ = \Psi_3(y_3^) = \Psi_3(1) = 2\
y_1^ = \Psi_2(y_2^) = \Psi_2(2) = 1
$`
所以最优状态序列为
# -*- coding:utf-8 -*-
# Python 3.7
# @Time: 2020/2/6 20:42
# @Author: Michael Ming
# @Website: https://michael.blog.csdn.net/
# @File: ConditionalRandomField_viterbi.py
import numpy as np
def viterbi(s, t):
time = len(s)
y_state = [0, 1] # 表示状态 1,2
m = len(y_state) # 状态数量
y_star = np.zeros((time), dtype=np.int32) # 最优路径
delta = np.zeros((time, m)) # 最大概率矩阵(可以DP状态压缩)
psi = np.zeros((time, m), dtype=np.int32) # 记录最优路径
# 初始化delta
delta[0][0] = s[0][0]
delta[0][1] = s[0][1]
# 递推
for i in range(1, time):
for j in range(m):
temp = [delta[i - 1][k] + s[i][j] + t[i][k][j] for k in range(m)]
# i表示时间,从k状态转移到j状态
psi[i][j] = np.argmax(temp) # 返回最大值的下标
delta[i][j] = temp[psi[i][j]] # 最大的概率填入
# 终止
y_star[time - 1] = np.argmax(delta[time - 1])
# 返回
for i in range(time - 2, -1, -1):
y_star[i] = psi[i + 1][y_star[i + 1]]
return y_star, delta, psi
def crf_viterbi():
# 状态特征
s = np.array([[1, 0.5],
[0.8, 0.5],
[0.8, 0.5]])
# 转移特征
t = np.array([[[0, 0],
[0, 0]], # 辅助,使得后面序号方便
[[0.6, 1],
[1, 0]],
[[0, 1],
[1, 0.2]]])
y_star, delta, psi = viterbi(s, t)
print("最优路径:", y_star + 1) # +1表示所有的都+1,序号从1开始
print("概率矩阵:\n", delta)
psi[1:] += 1 # 序号从1开始,第0行没用
print("Psi路径:\n", psi)
if __name__ == '__main__':
crf_viterbi()
运行结果,与上面一致。
最优路径: [1. 2. 1.]
概率矩阵:
[[1. 0.5]
[2.4 2.5]
[4.3 3.9]]
Psi路径:
[[0 0]
[1 1]
[2 1]]
Process finished with exit code 0