概率图

概率图构建了这样一幅图,用观测结点来表示观测到的数据,用隐含结点表示潜在的知识,用边来描述知识与数据的相互关系,最后基于这样的关系图获得一个概率分布,非常优雅的解决了问题.
概率图的结点分为隐藏结点和观测结点,边分为有向边和无向边,其中有向边表示单向的依赖关系,无向边表示相互依赖关系.概率图模型分为贝叶斯网络和马尔可夫网络,马尔可夫网络可以表示成一个无向图的网络结构,而贝叶斯网络则是一个有向图的网络结构。

马尔可夫网络的联合概率分布

在马尔可夫网络中,联合概率分布的定义:

$P(x)=\frac{1}{Z}\prod_{Q∈C}\phi_Q(x_Q)$

其中C为图中最大团构成的集合,$Z=\sum_x\prod_{Q∈C}(x_Q)$为归一化因子,用来保证P(x)是被正确定义的概率
$\phi_Q$是团Q对应的势函数.势函数是非负的,并且应该在概率较大的变量上取得较大的指,例如指数函数

$\phi_Q(x_Q=e^{-H_Q(x_Q)}$

其中$H_Q(x_Q)=\sum_{u,v∈Q,u≠v}α_{u,v}x_ux_v+\sum_{v∈Q}β_vx_v$
对于图中所有节点$x={x_1,x_2,…,x_n}$所构成的一个子集,如果在这个子集中,任意两点之间都存在边相连,则这个子集中的所有结点构成了一个团.如果在这个子集中加入任意其他结点,就不能构成一个团,则称为这样的子集构成了一个最大团.

概率图表示

解释朴素贝叶斯模型的原理,并给出概率图模型表示

朴素贝叶斯模型通过预测指定样本属于特定类别的概率P(y_i|x)来预测该样本的所属类别,即

$y=max_{y_i}P(y_i|x)$

其中P(y_i|x)可以写成

$P(y_i|x)=\frac{P(x|y_i)P(y_i)}{P(x)}$

其中$x=(x_1,x_2,…,x_n)$为样本对应的特征向量,P(x)为样本的先验概率。对于特定的样本x和任意类别$y_i$,P(x)的取值均相同,并不影响P(y_i|x)取值的相对大小,因此在计算中可以被忽略.假设特征$x_1,x_2,…x_n$相互独立,可得到

其中$P(x_1|y),P(x_2|y)…,P(x_n|y_i)以及P(y_i)$可以通过训练样本统计得到.

解释最大熵模型的原理,并给出概率图模型的表示

假设离散随机变量x的分布P(x),则关于分布P的熵定义为:

$H(P)=\sum_xP(x)logP(x)$

条件熵的定义:

$H(Y|X)=\sum_xP(x)\sum_yP(y|x)logP(y|x)=\sum_{x,y}P(x,y)log(P(y|x))$

其中P(x)为样本在训练数据集上的经验分布,这是一种频率统计

最大熵模型就是要学习到合适的分布P(y|x),使得条件熵的取值最大。
显然在我们对训练数据集一无所知的情况下，最大熵模型认为P(y|x)是符合均匀分布.
那么当我们有了训练数据集之后呢？我们希望从中找到一些规律,从而消除一些不确定性,这时要用到一个 特征函数f(x,y).这些特征函数f描述了输入x和输出y之间的一个规律,例如当x=y时.f(x,y)等于一个较大的正数.为了使学习到的模型P(y|x)能够正确的捕捉训练数据集中的这一规律,我们加入一个约束,使得特征函数f(x,y)关于经验分布$\hat{P}(x,y)$的期望值与关于模型P(y|x)和经验分布$\hat{P}(x)$的期望值相等,即

$E_{\hat{P}}(f)=E_P(f)$

其中$E_{\hat{P}}(f)=\sum_{x,y}\hat{P}(x,y)f(x,y)$
$E_{P}(f)=\sum_{x,y}\hat{P}(x)P(y|x)f(x,y)$
其中$\hat{P}(x,y)和\hat{P}(x)$都是经验分布,都是通过统计获得的.
最大熵模型的学习等价于约束最优化问题:
给定训练数据集$T=\{(x_1,y_1),(x_2,y_2),..,(x_N,y_N)\}$,以及M个特征函数$\{f_i(x,y),i=1,2,…,M\}$

$max_PH(P)=-\sum_{x,y}\hat{P}(x)P(y|x)logP(y|x)$ $s.t. E_{\hat{P}}(f_i)=E_P(f_i) \ \ \ \ i=1,2,3,....,M$

求解之后可以得到最大熵模型的表达形式为

$P_w(y|x)=\frac{1}{Z}exp(\sum_{i=1}^Mw_if_i(x,y))$

最终,最大熵模型归结为学习最佳参数w,使得$P_w(y|x)$最大化

马尔可夫模型

介绍隐马尔可夫模型前,先简单了解马尔可夫过程,马尔可夫过程是满足无后效性的随机过程.$P(x_n|x_1,x_2,…,x_{n-1})=P(x_n|x_{n-1})$,即称为马尔可夫过程.

若时间和状态的取值都是离散的马尔可夫过程也成为马尔可夫链

隐马尔可夫模型是对含有未知参数(隐状态)的马尔可夫链进行建模的生成模型.
在隐马尔科夫模型中,隐状态$x_i$对于观测者而言是不可见的,观测者能够观测到的只有每个隐状态$x_i$对应的输出$y_i$,而观测状态$y_i$的概率分布仅仅取决于对应的隐状态$x_i$.

隐马尔可夫模型的参数包括:隐状态的转移概率,隐状态到观测状态的输出概率,隐状态x的取值空间,观测状态y的取值空间以及初始状态概率分布.

隐马尔可夫模型包括概率计算问题、预测问题、学习问题三个基本问题

概率计算问题:已知模型的所有参数,计算观测序列Y出现的概率,可使用前向和后向算法求解
预测问题:已知模型所有参数,和观测序列Y,计算最可能的隐状态序列X,可使用经典的动态规划算法——维特比算法来求解最可能的状态序列
学习问题:已知观测序列Y,求解使得该观测学列概率最大的模型参数,包括隐状态序列,隐状态转移概率以及从隐状态到观测状态的输出概率.可使用Baum-Welch算法进行参数学习(本质是EM,无监督学习).

概率计算算法

常用的计算观测序列O概率$P(O|\lambda)$的方法是前向算法与后向算法.其中$\lambda$是模型的参数$(A,B,\pi)$，A是状态转移概率,B是输出概率,$\pi$是初始状态概率

先介绍一种理论上可以但计算上不可行的直接计算法

直接计算法
设隐状态序列$I=(i_1,i_2,..,i_T)$的概率为 $P(I|\lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}..a_{i_{T-1}i_T}$ 这就是简单的根据初始状态概率选择$i_1$,然后根据状态转移矩阵求得隐状态序列I的联合概率.
对固定状态序列I=$(i_1,i_2,…,i_T)$,观测序列$O=(o_1,o_2,…,o_T)$的概率是$P(O|I,\lambda)$ $P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)$ 在已知I=$(i_1,i_2,…,i_T)$的条件下,观测序列为$o_1,o_2,….o_T$的概率
综上有: $P(O,I|\lambda)=P(O|I,\lambda)P(I|\lambda)$ 我们的目标概率为 $P(O|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)$ 利用该公式的计算量很大,是$O(TN^T)$
所以我们要采用讨巧的方法
前向算法
定义前向概率: 给定隐马尔科夫模型$\lambda$,定义到时刻t部分观测序列为$o_1,o_2,…,o_t$且隐状态为$q_i$的概率为前向概率,记作
$α_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)$
可以递推地求得前向概率α_t(i)及观测序列概率$P(O|\lambda)$
前向算法：
输入:参数$\lambda$,观测序列O
输出：观测序列O出现的概率
(1)初值：$α_1(i)=P(o_1,q_i)=P(q_i|\lambda)P(o_1|q_i)=\pi_ib_i(o_1) i=1,2,…,N$
(2)递推:对t=1,2,…,T-1,
$α_{t+1}(i)=[\sum_{j=1}^Nα_t(j)a_{ji}]b_i(o_{t+1})$
先要求前t个时刻序列为$o_1,o_2,…,o_t$且下一时刻隐状态为q_i的概率.
(3)终止
$P(O|\lambda)=\sum_{i=1}^Nα_T(i)$
后向算法
定义后向概率: 给定马尔可夫模型$\lambda$,定义在时刻t状态为$q_t$的条件下,从t+1到T的部分观测序列为$o_{t+1},o_{t+2},…,o_{T}$的概率为后向概率,记作
$β_t(i)=P(o_{t+1},o+{t+2},...o_T|i_t=q_i,\lambda)$
这种形式有点像前行概率的互补型
后向算法:
输入：参数$\lambda$,观测序列O
输出：观测序列O出现的概率
(1)初值$β_T(i)=1$
(2)对t=T-1,T-2,…,1
$β_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})β_{t+1}(j) \ \ \ \ i=1,2,...,N$
t+1时刻的后向概率需要乘以t时刻的转移概率,才能得到$o_{t+1},..o_{T}$和$i_t$的联合概率条件是$i_{t-1}$,然后用输出概率得到含有$o_t$输出的概率,最后求和.
(3) 终止：
$P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)β_1(i)$

预测算法

预测算法也有两种可以的方法:分别是近似算法和维特比算法

近似算法
算法:
输入:参数$\lambda$,观测序列
输出:最有可能的隐状态序列
主要公式：
$\gamma_t(i)=\frac{α_t(i)β_t(i)}{P(O|\lambda)}=\frac{α_t(i)β_t(i)}{\sum_{j=1}^Nα_t(j)β_t(j)}$
这里分子得到的是$P(o_1,o_2,…,o_T,q_i|\lambda)$,分母则是P(O|\lambda),前面说过α和β有点像互补
维特比算法
这是一种 动态规划 ,求概率最大路径(最优路径).这时一条路径对应着状态序列.
导入两个变量,定义在时刻t状态为i的所有单个路径$i_1,i_2,…,i_t$中概率最大值为
$\delta_t(i)=max_{i_1,i_2,…,i_{t-1}}P(i_t=i,i_{t-1},…,i_1,o_t,…,o_1|\lambda), i=1,2,..,N$
由定义可得变量$\delta$的递推公式:
$\delta_{t+1}(i)=max_{i_1,i_2,...,i_{t}}P(i_{t+1}=i,i_{t},...,i_1,o_{t+1},...,o_1|\lambda)$ $\delta_{t+1}(i)=max_{1≤j≤N}[\delta_t(j)a_{ji}]b_i(o_{t+1}) \ \ \ \ i=1,2,...,N; t=1,2,...,T-1$
定义在时刻t状态为i的所有单个路径$(i_1,i_2,…,i_{t-1,i})$中概率最大的路径的第t-1个结点为.
$\psi_t(i)=argmax_{1≤j≤N}[\delta_{t-1}(j)a_{ji}] \ \ \ \ i=1,2,..,N$
算法:
维特比算法
输入:模型$\lambda=(A,B,\pi)$和观测$O=(o_1,o_2,..,o_T)$;
输出:最优路径$I^ =(i_1^ ,i_2^ ,…,i_T^ )$.
(1)初值:
$\delta_1(i)=\pi_ib_i(o_1), i=1,2,…,N$
$\psi_1(i)=0, i=1,2,…,N$
(2)递推:对t=2,3,…,T
$\delta_t(i)=max_{1≤j≤N}[\delta_{t-1}(j)a_{ji}]b_i(o_t)$ $\psi_t(i)=argmax_{1≤j≤N}[\delta_{t-1}(j)a_{ji}]$
(3)最终:
$P^* =max_{1≤i≤N}\delta_T(i)$
$$i_T^* =argmax_{1≤i≤N}[\delta_T(i)]

学习算法

也有两种算法,一种适用于监督学习,一种适用于非监督学习

监督学习
(1)转移概率$a_{ij}$的估计
设样本中时刻t处于状态i时刻t+1转移到状态j的频数为$A_{ij}$,那么状态转移概率$a_{ij}$估计是 $\hat{a}_{ij}=\frac{A_{ij}}{\sum_{j=1}^NA_{ij}}$ (2)输出概率$b_j(k)$的估计
同样也是用频数方式统计
(3)初始状态概率$\pi_i$的估计一样是用频率
Baum-Welch算法(非监督算法,EM算法的特例)
(a) $γ_t(i)=P(i_t=q_i|O,\lambda)$为前向后向概率计算 $γ_t(i)=\frac{α_t(i)β_t(i)}{P(O|\lambda)}=\frac{α_t(i)β_t(i)}{\sum_{j=1}^Nα_t(j)β_t(j)}$ (b)$\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)$在给定模型$\lambda$和观测O,在时刻t处于状态$q_i$且在时间t+1处于状态$q_j$的概率 $\xi_t(i,j)=\frac{α_t(i)a_{ij}b_j(o_{t+1})β_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^Nα_t(i)a_{ij}b_j(o_{t+1})β_{t+1}(j)}$

Baum-Welch算法
输入:观测数据$O=(o_1,o_2,…,o_T)$
输出:隐马尔科夫模型参数$\lambda$
(1)初值:
对n=0;选取$a_{ij}^(0),b_j(k)^{(0)},\pi_i^{(0)}$,得到模型$\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})$
(2)递推：
对n=1,2,…,

$a_{ij}^{(n+1)}=\frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1}γ_t(i)}$ $b_j(k)^{(n+1)}=\frac{\sum_{t=1,o_t=v_k}γ_t(j)}{\sum_{t=1}^Tγ_t(j)}$ $\pi_i^{(n+1)}=γ_1(i)$

右端各值按观测$O=(o_1,o_2,…,o_T)$和模型$\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})$计算,式中$γ_t(i)$,$\xi_t(i,j)$由式(a)和(b)给出
(3)终止,得到模型参数$\lambda^{(n+1)}=(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})$