【ML算法】马尔科夫链_马尔可夫链公式

文档介绍：https://download.csdn.net/download/liudongdong19/10420151

一、马尔可夫链

1、马尔可夫链

设XtXt表示随机变量XX在离散时间tt时刻的取值。若该变量随时间变化的转移概率仅仅依赖于它的当前取值，即

 

P(Xt+1=sj∣X0=s0,X1=s1,⋯,Xt=si)=P(Xt+1=sj∣Xt=si)P(Xt+1=sj∣X0=s0,X1=s1,⋯,Xt=si)=P(Xt+1=sj∣Xt=si)

 

也就是说状态转移的概率只依赖于前一个状态。称这个变量为马尔可夫变量，其中，s0,s1,⋯,si,sj∈Ωs0,s1,⋯,si,sj∈Ω为随机变量XX可能的状态。这个性质称为马尔可夫性质，具有马尔可夫性质的随机过程称为马尔可夫过程。

马尔可夫链指的是在一段时间内随机变量XX的取值序列(X0,X1,⋯,Xm)(X0,X1,⋯,Xm)，它们满足如上的马尔可夫性质。

2、转移概率

马尔可夫链是通过对应的转移概率定义的，转移概率指的是随机变量从一个时刻到下一个时刻，从状态sisi转移到另一个状态sjsj的概率，即：

 

P(i→j):=Pi,j=P(Xt+1=sj∣Xt=si)P(i→j):=Pi,j=P(Xt+1=sj∣Xt=si)

 

记π(t)kπk(t)表示随机变量XX在时刻tt的取值为sksk的概率，则随机变量XX在时刻t+1t+1的取值为sisi的概率为：

 

π(t+1)i=P(Xt+1=si)=∑kP(Xt+1=si∣Xt=sk)⋅P(Xt=sk)=∑kPk,i⋅π(t)kπi(t+1)=P(Xt+1=si)=∑kP(Xt+1=si∣Xt=sk)⋅P(Xt=sk)=∑kPk,i⋅πk(t)

 

假设状态的数目为nn，则有：

 

(π(t+1)1,⋯,π(t+1)n)=(π(t)1,⋯,π(t)n)⎡⎣⎢⎢⎢⎢⎢P1,1P2,1⋮Pn,1P1,2P2,2⋮Pn,2⋯⋯⋯P1,nP2,n⋮Pn,n⎤⎦⎥⎥⎥⎥⎥(π1(t+1),⋯,πn(t+1))=(π1(t),⋯,πn(t))[P1,1P1,2⋯P1,nP2,1P2,2⋯P2,n⋮⋮⋮Pn,1Pn,2⋯Pn,n]

 

3、马尔可夫链的平稳分布

对于马尔可夫链，需要注意以下的两点：

• 1、周期性：即经过有限次的状态转移，又回到了自身；
• 2、不可约：即两个状态之间相互转移；

如果一个马尔可夫过程既没有周期性，又不可约，则称为各态遍历的。

对于一个各态遍历的马尔可夫过程，无论初始值π(0)π(0)取何值，随着转移次数的增多，随机变量的取值分布最终都会收敛到唯一的平稳分布π∗π∗，即：

 

limt→∞π(0)Pt=π∗limt→∞π(0)Pt=π∗

 

且这个平稳分布π∗π∗满足：

 

π∗P=π∗π∗P=π∗

 

其中，P=(pi,j)n×nP=(pi,j)n×n为转移概率矩阵。

二、马尔可夫链蒙特卡罗方法

1、基本思想

对于一个给定的概率分布P(X)P(X)，若是要得到其样本，通过上述的马尔可夫链的概念，我们可以构造一个转移矩阵为PP的马尔可夫链，使得该马尔可夫链的平稳分布为P(X)P(X)，这样，无论其初始状态为何值，假设记为x0x0，那么随着马尔科夫过程的转移，得到了一系列的状态值，如：x0,x1,x2,⋯,xn,xn+1,⋯,x0,x1,x2,⋯,xn,xn+1,⋯,，如果这个马尔可夫过程在第nn步时已经收敛，那么分布P(X)P(X)的样本即为xn,xn+1,⋯xn,xn+1,⋯。

2、细致平稳条件

对于一个各态遍历的马尔可夫过程，若其转移矩阵为PP，分布为π(x)π(x)，若满足：

 

π(i)Pi,j=π(j)Pj,iπ(i)Pi,j=π(j)Pj,i

 

则π(x)π(x)是马尔可夫链的平稳分布，上式称为细致平稳条件。

3、Metropolis采样算法

Metropolis采样算法是最基本的基于MCMC的采样算法。

3.1、Metropolis采样算法的基本原理

假设需要从目标概率密度函数p(θ)p(θ)中进行采样，同时，θθ满足−∞<θ<∞−∞<θ<∞。Metropolis采样算法根据马尔可夫链去生成一个序列：

 

θ(1)→θ(2)→⋯θ(t)→θ(1)→θ(2)→⋯θ(t)→

 

其中，θ(t)θ(t)表示的是马尔可夫链在第tt代时的状态。

在Metropolis采样算法的过程中，首先初始化状态值θ(1)θ(1)，然后利用一个已知的分布q(θ∣θ(t−1))q(θ∣θ(t−1))生成一个新的候选状态θ(∗)θ(∗)，随后根据一定的概率选择接受这个新值，或者拒绝这个新值，在Metropolis采样算法中，概率为：

 

α=min(1,p(θ(∗))p(θ(t−1)))α=min(1,p(θ(∗))p(θ(t−1)))

 

这样的过程一直持续到采样过程的收敛，当收敛以后，样本θ(t)θ(t)即为目标分布p(θ)p(θ)中的样本。

3.2、Metropolis采样算法的流程

基于以上的分析，可以总结出如下的Metropolis采样算法的流程：

• 初始化时间t=1t=1
• 设置uu的值，并初始化初始状态θ(t)=uθ(t)=u
• 重复一下的过程： 
  • 令t=t+1t=t+1
  • 从已知分布q(θ∣θ(t−1))q(θ∣θ(t−1))中生成一个候选状态θ(∗)θ(∗)
  • 计算接受的概率：α=min(1,p(θ(∗))p(θ(t−1)))α=min(1,p(θ(∗))p(θ(t−1)))
  • 从均匀分布Uniform(0,1)Uniform(0,1)生成一个随机值aa
  • 如果a⩽αa⩽α，接受新生成的值：θ(t)=θ(∗)θ(t)=θ(∗)；否则：θ(t)=θ(t−1)θ(t)=θ(t−1)
• 直到t=Tt=T

3.3、Metropolis算法的解释

要证明Metropolis采样算法的正确性，最重要的是要证明构造的马尔可夫过程满足如上的细致平稳条件，即：

 

π(i)Pi,j=π(j)Pj,iπ(i)Pi,j=π(j)Pj,i

 

对于上面所述的过程，分布为p(θ)p(θ)，从状态ii转移到状态jj的转移概率为：

 

Pi,j=αi,j⋅Qi,jPi,j=αi,j⋅Qi,j

 

其中，Qi,jQi,j为上述已知的分布。

对于选择该已知的分布，在Metropolis采样算法中，要求该已知的分布必须是对称的，即Qi,j=Qj,iQi,j=Qj,i，即 

q(θ=θ(t)∣θ(t−1))=q(θ=θ(t−1)∣θ(t))q(θ=θ(t)∣θ(t−1))=q(θ=θ(t−1)∣θ(t))

常用的符合对称的分布主要有：正态分布，柯西分布以及均匀分布等。

 

接下来，需要证明在Metropolis采样算法中构造的马尔可夫链满足细致平稳条件。

 

p(θ(i))Pi,j=p(θ(i))⋅αi,j⋅Qi,j=p(θ(i))⋅min{1,p(θ(j))p(θ(i))}⋅Qi,j=min{p(θ(i))Qi,j,p(θ(j))Qi,j}=p(θ(j))⋅min{p(θ(i))p(θ(j)),1}⋅Qj,i=p(θ(j))⋅αj,i⋅Qj,i=p(θ(j))Pj,ip(θ(i))Pi,j=p(θ(i))⋅αi,j⋅Qi,j=p(θ(i))⋅min{1,p(θ(j))p(θ(i))}⋅Qi,j=min{p(θ(i))Qi,j,p(θ(j))Qi,j}=p(θ(j))⋅min{p(θ(i))p(θ(j)),1}⋅Qj,i=p(θ(j))⋅αj,i⋅Qj,i=p(θ(j))Pj,i

 

因此，通过以上的方法构造出来的马尔可夫链是满足细致平稳条件的。

3.4、实验

假设需要从柯西分布中采样数据，我们利用Metropolis采样算法来生成样本，其中，柯西分布的概率密度函数为：

 

f(θ)=1π(1+θ2)f(θ)=1π(1+θ2)

 

那么，根据上述的Metropolis采样算法的流程，接受概率αα的值为：

 

α=min⎛⎝1,1+[θ(t)]21+[θ(∗)]2⎞⎠α=min(1,1+[θ(t)]21+[θ(∗)]2)

 

代码如下：

'''
Date:20160629
@author: zhaozhiyong
'''
import random
from scipy.stats import norm
import matplotlib.pyplot as plt
 
def cauchy(theta):
    y = 1.0 / (1.0 + theta ** 2)
    return y
 
T = 5000
sigma = 1
thetamin = -30
thetamax = 30
theta = [0.0] * (T+1)
theta[0] = random.uniform(thetamin, thetamax)
 
t = 0
while t < T:
    t = t + 1
    theta_star = norm.rvs(loc=theta[t - 1], scale=sigma, size=1, random_state=None)
    #print theta_star
    alpha = min(1, (cauchy(theta_star[0]) / cauchy(theta[t - 1])))
 
    u = random.uniform(0, 1)
    if u <= alpha:
        theta[t] = theta_star[0]
    else:
        theta[t] = theta[t - 1]
 
ax1 = plt.subplot(211)
ax2 = plt.subplot(212) 
plt.sca(ax1)
plt.ylim(thetamin, thetamax)
plt.plot(range(T+1), theta, 'g-')
plt.sca(ax2)
num_bins = 50
plt.hist(theta, num_bins, normed=1, facecolor='red', alpha=0.5)
plt.show()

•  

实验的结果：

 

隐马尔可夫模型 Hidden Markov Models

参考资料：https://wenku.baidu.com/view/54836f106c175f0e7cd13715.html?sxts=1541074228954

隐马尔可夫模型（Hidden Markov Models, HMM）描述由一个隐藏的马尔可夫链随机生成的不可观测的状态序列，再由各个状态生成一个观测而产生观测随机序列的过程，属于生成模型。HMM(隐马尔可夫模型)是结构最简单的动态贝叶斯网，是一种著名的有向(无环)图模型，主要用于时序数据建模（语音识别、自然语言处理等）。

隐马尔科夫模型可以被看成状态空间模型[顺序数据：状态空间模型]的一个具体实例,其中潜在变量是离散的。如果我们考察模型的一个单一的时间切片,那么我们看到它对应于一个混合概率分布,对应的分量密度为 p(x | z) 。于是,它也可以表述为混合概率模型的一个推广,其中每个观测的混合系数不是独立地选择的,而是依赖于对于前一次观测的分量（隐含状态）的选择。

在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。[马尔科夫模型]而在隐马尔可夫模型中,状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布，因此输出符号的序列能够透露出状态序列的一些信息。其难点是从可观察的参数中确定该过程的隐含参数，然后利用这些参数来作进一步的分析。

HMM的概率图表示

与马尔科夫相比，隐马尔科夫模型则是双重随机过程，不仅状态转移之间是个随机事件，状态和输出之间也是一个随机过程，如下图所示：

 

该图分为上下两行，上面那行就是一个马尔科夫转移过程，下面这一行则是输出，即我们可以观察到的值，现在，我们将上面那行的马尔科夫转移过程中的状态称为隐藏状态，下面的观察到的值称为观察状态，观察状态的集合表示为 O={X1,X2,X3,…XN}。 Note: 每个状态z_i都是一个向量分布，即在N个状态集合 {k1,k2,k3,...k_K}上的概率分布。

 

[顺序数据：状态空间模型 ]

 

 

HMM输出独立性假设

 

齐次马尔科夫性：

即只考虑一阶马尔科夫模型。其实还有一个同质性质，即状态转移矩阵在所有时间步是一样的。[马尔科夫模型]

观测独立性假设：

 

相应的，隐马尔科夫也比马尔科夫多了一个假设，即输出仅与当前状态有关，可以用如下公式表示：

P(O1,O2,…,Ot|S1,S2,…,St)=P(O1|S1)*P(O2|S2)*...*P(Ot|St)

其中，O1,O2,…,Ot为从时刻1到时刻t的观测状态序列，S1,S2,…,St则为隐藏状态序列。

 

HMM的形式定义

HMM三要素

隐马尔可夫模型是由初始状态项链π、状态转移概率矩阵A和观测概率矩阵φ（观测变量的条件概率，亦称发射概率）决定。π和A决定状态序列，φ决定观测序列。因此A、B和φ就是隐马尔可夫模型的三要素，而θ = {π, A, φ} 表示控制隐马尔可夫模型参数的集合。

状态转移概率矩阵A与初始状态概率向量π确定了隐藏的马尔科夫链，生成不可观测的状态序列；观测概率矩阵φ确定了如何从状态生成观测，与状态序列综合确定了如何产生概率序列。

说白了，hmm就是考虑了观测概率，同时也考虑了状态之间的关系（即状态转移概率），相当于混合概率模型中考虑了混合系数间的关联。

Note: 由于潜在变量是 K 维二值变量,因此条件概率分布对应于数字组成的表格,记作 A ,它的元素被称为转移概率( transition probabilities)。元素为 A jk ≡  p(z nk = 1 | z n−1,j = 1) 。由于它们是概率值,因此满足 0 ≤ A jk ≤ 1 且 ∑k A jk = 1 ,从而矩阵 A 有 K(K − 1) 个独立的参数。

潜在变量的条件概率

 

同质的( homogeneous )模型所有控制潜在变量的条件概率分布都共享相同的参数 A ,类似地所有发射概率分布都共享相同的参数 φ (推广到更一般的情形很容易)。即zn-1到zn 和 zn到zn+1的状态转移矩阵是相同的！在状态转移矩阵及发射矩阵中的每一个概率都是时间无关的——也就是说，当系统演化时这些矩阵并不随时间改变。实际上，这是马尔科夫模型关于真实世界最不现实的一个假设。

但是注意,对于一个独立同分布的数据集,一个混合模型对应于参数 A jk 对于所有的 j 值都相同的情况,从而条件概率分布 p(z n | z n−1 ) 与 z n−1 无关。

初始潜在结点 z 1 很特别,因为它没有父结点,因此它的边缘概率分布 p(z 1 ) 由一个概率向量 π 表示,元素为 π k ≡ p(z 1k = 1) ,即

其中 ∑k π k = 1 。

隐马尔科夫模型的晶格图

潜在变量之间转移的表示方法,被称为晶格图( lattice diagram )或者格子图( trellis diagram )。

观测变量的条件概率分布：发射概率( emission probabilities )

发射概率的特定选择：事实上,模型对于一大类发射概率的选择都是可以计算的,包括离散表格、高斯以及混合高斯。也可以利用判别式模型例如神经网络。这些可以用来直接对发射概率密度 p(x | z) 建模,也可以用来给出 p(z | x) 的一个表达式,这个表达式可以使用贝叶斯定理转化为所需的发射概率密度 p(x | z) ( Bishop et al.,2004 )。

观测变量和潜在变量上的联合概率分布

其中 X = {x 1 , . . . , x N }, Z = {z 1 , . . . , z N } 和 θ = {π, A, φ} 表示控制模型参数的集合。

完全和状态空间模型的联合分布一样。

生成式的观点考虑隐马尔科夫模型

首先我们选择初始的潜在变量 z 1 ,概率由参数 π k 控制,然后采样对应的观测 x 1 。现在我们使用已经初始化的 z 1 的值,根据转移概率 p(z 2 | z 1 ) 来选择变量 z 2 的状态。从而我们以概率 A jk 选择 z 2 的状态 k ,其中 k = 1, . . . , K 。一旦我们知道了 z 2 ,我们就可以对 x 2 采样,从而也可以对下一个潜在变量 z 3 采样,以此类推。

这是有向图模型的祖先采样的一个例子。

某小皮

 

隐马尔科夫模型的示例

示例1（盒子和球模型）

 如上图所示，有4个盒子，每个盒子里都装有红白两种颜色的球，每个盒子中球的个数见上图。然后，按照下面的规则抽5次球：

                   第一次：从4个盒子里等概论随机选取1个盒子，然后从这个盒子里随机抽出1个球，记录其颜色后放回；

                   剩下4次：若上一次是从盒子1中抽球，那这次一定是盒子2；若上一次是盒子2或3，那这次则分别以0.4和0.6的概率选择左边或右边的盒子；若上一次是盒子4，那这次各以0.5的概率选择是停留在盒子4还是转移到盒子3。确定转译的盒子后，再从这个盒子里随机抽出一个球，记录其颜色后放回。

         就这样，得到一个球的颜色序列：  {红，红，白，白，红}

         在这个过程中，观察者只能观测到球颜色的序列，观测不到球是从哪个盒子取出的，即：观测不到盒子的序列。

         1，在这个例子中有两个随机序列：

                   盒子的序列（之后称之为：状态序列）

                   球颜色的观测序列（之后称之为：观测序列）

         2，状态序列的每个状态值仅取决于前面有限个状态（见上面的“抽5次球的规则描述”），这种状态序列就是马尔可夫链。

         3，状态序列是隐藏的，观测序列是可观测的。

         于是乎，像这种由一个隐藏的马尔可夫链随机生成的不可观测的状态序列，再由各个状态生成一个观测而产生观测随机序列的过程，就是隐马尔可夫模型。

         由题目知：

         1，盒子对应的状态，即状态集合是： Q= {盒子1，盒子2，盒子3，盒子4}   状态集合表述的是“所有可能的状态的集合”；  状态序列表述的是“实际操作中产生的状态序列”

         2，状态序列因无法观测，所以不可知，但在定义中我们还是给出其表示方法，即：   I= (i1, i2, ..., iT)

         3，球颜色对应的观测，即观测集合是：V= {红，白}

                            观测集合表述的是“所有可能的观测的集合”；观测序列表述的是“实际操作中产生的观测序列”

         4，观测序列是：  O= {红，红，白，白，红}

                   在定义中，观测序列中的各个元素用oT表示，即：O = {o1, o2, ..., oT}

         5，状态序列和观测序列的长度T=5，这个长度的产生是因为一共进行了5次抽样，然后第一次抽样我们称之为时刻1，第二次称之为时刻2，以此类推。

         6，初始概率分布为：π = (0.25,0.25, 0.25, 0.25)

                   在定义中，初始概率分布中的各个元素用πi表示，即：π=(πi)，其中π=P(i1 = qi), i = 1, 2, ..., N，表示时刻t=1处于状态qi的概率。

         7，状态转移概率分布的矩阵为：

                  

                   PS：A = [aij]N*N，其中aij= P(it+1 = qj | it = qi), i = 1, 2,..., N; j = 1, 2, ..., N，表示在时刻t处于状态qi条件下，时刻t+1转译到状态qj的概率。如：a12(第一行第二列) = 1，表示：时刻t选择的盒子1(q1)时，时刻t+1选择盒子2(q2)的概率是1。

         8，观测概率分布矩阵为：

                  

                   PS：B = [bj(k)]N*N，其中，bj(k)= P(ot+1 = vk | it = qj), k = 1, 2,..., M; j = 1, 2, ..., N，表示在时刻t处于状态qj的条件下生成观测vk的概率。如B2(1) = 0.5，表示：时刻t处于状态盒子2(q2)时选择红球(v1)的的概率是0.3。

示例2

回顾一下马尔科夫过程[马尔科夫模型]天气那个例子，一个隐士也许不能够直接获取到天气的观察情况，但是他有一些水藻。民间传说告诉我们水藻的状态与天气状态有一定的概率关系——天气和水藻的状态是紧密相关的。在这个例子中我们有两组状态，观察的状态（水藻的状态）和隐藏的状态（天气的状态）。我们希望为隐士设计一种算法，在不能够直接观察天气的情况下，通过水藻和马尔科夫假设来预测天气。
例子中，需要着重指出的是，隐藏状态的数目与观察状态的数目可以是不同的。一个包含三个状态的天气系统（晴天、多云、雨天）中，可以观察到4个等级的海藻湿润情况（干、稍干、潮湿、湿润）。在这种情况下，观察到的状态序列与隐藏过程有一定的概率关系。我们使用隐马尔科夫模型对这样的过程建模，这个模型包含了一个底层隐藏的随时间改变的马尔科夫过程，以及一个与隐藏状态某种程度相关的可观察到的状态集合。
下图显示的是天气例子中的隐藏状态和观察状态。

 

假设隐藏状态（实际的天气）由一个简单的一阶马尔科夫过程描述，那么它们之间都相互连接。
　　
　　隐藏状态和观察状态之间的连接表示：在给定的马尔科夫过程中，一个特定的隐藏状态生成特定的观察状态的概率。这很清晰的表示了‘进入’一个观察状态的所有概率之和为1，在上面这个例子中就是Pr(Obs|Sun)，Pr(Obs|Cloud) 及 Pr(Obs|Rain)之和。
Note:这里是把obs作为参数来用，就是说Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Sun) = 1;
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Cloud) = 1;
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Rain) = 1;
　　除了定义了马尔科夫过程的概率关系，我们还有另一个矩阵，定义为混淆矩阵（confusion matrix），它包含了给定一个隐藏状态后得到的观察状态的概率。对于天气例子，混淆矩阵是：
　　
注意矩阵的每一行之和是1。

皮皮blog

 

 

 

隐马尔科夫模型的变体和拓展

通过对转移矩阵 A 的形式进行限制的方式进 行 限 制 ( Rabiner, 1989 )

从 左到右 HMM ( left-to-right HMM )

将 A 中 k < j 的元素 A jk 设置为零。语音识别或在线字符识别都使用了这种从左到右的结构。

图 13.9: 三状态隐马尔科夫模型的状态转移图的例子。注意,一旦离开了某个状态,就无法再次回到这个状态。

通 常 对 于 这 种 模 型, 初 始 状 态 概 率 p(z 1 ) 被 修 改, 使得 p(z 11 ) = 1 且 p(z 1j ) = 0, j ̸ = 1 ,换句话说,每个序列被限制为从状态 j = 1 开始。转移矩阵可以进一步被限制,来确保状态的下标不会发生过大的变化,即如果 k > j + ∆ ,那么 A jk = 0 。

隐马尔科夫模型的一个强大的性质是它对于时间轴上局部的变形(压缩和拉伸)具有某种程
度的不变性。但是注意,如果数字“2”用相反的顺序书写,即从右下角开始,结束于左上角,那么即使笔迹的坐标与训练集里的一个例子完全相同,在这个模型下的观测的概率会非常小。

判别式方法

如果目标是序列分类,那么在确定隐马尔科夫模型的参数时,使用判别式方法而不是最大似然方法会产生很多好处。假设我们有一个训练集,由 R 个观测序列 X r 组成,其中 r = 1, . . . , R ,每个序列根据它的类别 m 进行标记,其中 m = 1, . . . , M 。对于每个类别,我们有一个独立的隐马尔可夫模型,它的参数为 θ m ,我们将确定参数值的问题看成标准的分类问题,其中我们想最优化交叉熵。这种方法需要每个训练序列在每个模型下进行计算。

隐马尔科夫模型加上判别式的训练方法在语音识别中广泛应用( Kapadia, 1998 )。

对状态持续时间建模

隐马尔科夫模型的一个很大的缺点是,模型对于时间分布的表示方法不好（系统保持在一个给定的状态下）。

从一个给定的隐马尔科夫模型中采样到一个序列,这个序列在状态 k 恰好花费了 T 个步骤,然后转移到了一个不同的状态,因此它是 T 的一个指数衰减的函数。对于许多应用,这对于状态持续时间（太长？）来说是一个相当不现实的模型。

解决:直接对状态持续时间建模,其中对角系数 A kk 全部被设置为零,每个状态 k 显式地与可能的持续时间的概率分布 p(T | k) 相关联。从生成式的观点来看,当系统进入状态 k 时,表示系统保持在状态 k 的时间数 T 会从 p(T | k) 中抽取。

自回归隐马尔科夫模型( autoregressive hidden Markov model )

( Ephraim et al., 1989 )

标准 HMM 的另一个局限性是它在描述观测变量的长距离相关性(被许多时间步骤分开的变量的相关性)时,效果很差。长距离的效果原则上可以通过在图模型中添加额外链接的方式被包含到模型中。

输入输出隐马尔科夫模型( input-output hidden Markov model )

( Bengio and Frasconi, 1995 )

有一个观测变量的序列 u 1 , . . . , u N ,以及输出变量的序列 x 1 , . . . , x N ,观测变量的值要么影响潜在变量的分布,要么影响输出变量的分布,或者对两者都产生影响。这将 HMM 的框架推广到了顺序数据的有监督学习领域。

 

因子隐马尔可夫模型( factorial hidden Markov model )

( Ghahramani and Jordan, 1997 )

研究因子 HMM 的动机：在一个给定的时刻,为了表示例如10比特的信息,标准的 HMM 需要 K = 2 10 = 1024 个潜在状态,而因子 HMM 可以使用10个二值潜在链。然而,因子 HMM 的主要缺点是训练时的额外的复杂度。因子 HMM 的 M 步骤很容易。然而, x 变量的观测引入了潜在链之间的依赖关系,从而给 E 步骤带来了困难。

等价的标准 HMM的改进

由一个单独的潜在变量链,每个潜在变量有 K M 个潜在状态。然后我们可以在 E 步骤中运行标准的前向后向递归方法。计算复杂度为 O(N K 2M ) ,它与潜在链的数量 M 是指数的关系,因此除了对于很小的 M 值以外均无法计算。

一个解决方法是使用采样方法。作为另一个优雅的确定性的解决方法, Ghahramani and Jordan ( 1997 )研究了使用变分推断方法来得到近似推断的一个可以计算的算法。

[PRML]

 

某小皮

<br>

 

隐马尔科夫过程的应用

HMM一开始是在信息论中应用的，后来才被应用到自然语言处理还有其他图像识别等各个方面。HMM 广泛用于语音识别( Jelinek, 1997; Rabiner and Juang, 1993 )、自然语言建模( Manning and Schütze,1999 )、在线手写识别( Nag et al., 1986 )以及生物序列(例如蛋白质和 DNA )的分析( Kroghet al., 1994; Durbin et al., 1998; Baldi and Brunak, 2001 )。还有汉语分词、词性标注等。

下面举两个例子说明他的应用，一个是输入法的整句解码，一个是语音识别。有图为证：

 

 

输入法把拼音看做是观察状态，需要得到的汉字为隐藏状态，这样，输入法的整句解码就变成了维特比解码，其转移概率即是二元语言模型，其输出概率即是多音字对应不同拼音的概率。

将上图中的拼音换成语音，就成了语音识别问题，转移概率仍然是二元语言模型，其输出概率则是语音模型，即语音和汉字的对应模型。

隐马尔可夫模型的其它应用

语音识别、中文断词/分词或光学字符识别

机器翻译

生物信息学 和 基因组学

基因组序列中蛋白质编码区域的预测

对于相互关联的DNA或蛋白质族的建模

从基本结构中预测第二结构元素

通信中的译码过程

隐马可夫模型在语音处理上的应用

因为马可夫模型有下列特色：

时间点的隐藏条件和时间点的隐藏条件有关。因为人类语音拥有前后的关联，可以从语义与发音两点来看：

单字的发音拥有前后关联：例如"They are"常常发音成"They're"，或是"Did you"会因为"you"的发音受"did"的影响，常常发音成"did ju"，而且语音辨识中用句子的发音来进行分析，因此需要考虑到每个音节的前后关系，才能够有较高的准确率。

句子中的单字有前后关系：从英文文法来看，主词后面常常接助动词或是动词，动词后面接的会是受词或介系词。而或是从单一单字的使用方法来看，对应的动词会有固定使用的介系词或对应名词。因此分析语音讯息时需要为了提升每个单字的准确率，也需要分析前后的单字。

马可夫模型将输入讯息视为一单位一单位，接着进行分析，与人类语音模型的特性相似。语音系统辨识的单位为一个单位时间内的声音。利用梅尔倒频谱等语音处理方法，转换成一个发音单位，为离散型的资讯。而马可夫模型使用的隐藏条件也是一个个被封包的，因此使用马可夫模型来处理声音讯号比较合适。

1.如果概率最大的路径p(或者说最短路径)经过某个点，比如途中的X22，那么这条路径上的起始点S到X22的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到X22的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。

2.从S到E的路径必定经过第i个时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中一条，这样，在任意时刻，只要考虑非常有限的最短路即可。

3. 结合以上两点，假定当我们从状态i进入状态i+1时，从S到状态i上各个节的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到第i+1状态的某个节点Xi+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这个节点到Xi+1，j的距离即可。 [1] 

Viterbi算法：

package com.hankcs.algorithm;
 
/**
 * 维特比算法
 * @author hankcs
 */
public class Viterbi
{
    /**
     * 求解HMM模型
     * @param obs 观测序列
     * @param states 隐状态
     * @param start_p 初始概率（隐状态）
     * @param trans_p 转移概率（隐状态）
     * @param emit_p 发射概率 （隐状态表现为显状态的概率）
     * @return 最可能的序列
     */
    public static int[] compute(int[] obs, int[] states, double[] start_p, double[][] trans_p, double[][] emit_p)
    {
        double[][] V = new double[obs.length][states.length];
        int[][] path = new int[states.length][obs.length];
 
        for (int y : states)
        {
            V[0][y] = start_p[y] * emit_p[y][obs[0]];
            path[y][0] = y;
        }
 
        for (int t = 1; t < obs.length; ++t)
        {
            int[][] newpath = new int[states.length][obs.length];
 
            for (int y : states)
            {
                double prob = -1;
                int state;
                for (int y0 : states)
                {
                    double nprob = V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]];
                    if (nprob > prob)
                    {
                        prob = nprob;
                        state = y0;
                        // 记录最大概率
                        V[t][y] = prob;
                        // 记录路径
                        System.arraycopy(path[state], 0, newpath[y], 0, t);
                        newpath[y][t] = y;
                    }
                }
            }
 
            path = newpath;
        }
 
        double prob = -1;
        int state = 0;
        for (int y : states)
        {
            if (V[obs.length - 1][y] > prob)
            {
                prob = V[obs.length - 1][y];
                state = y;
            }
        }
 
        return path[state];
    }
}

package com.hankcs.algorithm;
 
import static com.hankcs.algorithm.WeatherExample.Weather.*;
import static com.hankcs.algorithm.WeatherExample.Activity.*;
 
public class WeatherExample
{
    enum Weather
    {
        Rainy,
        Sunny,
    }
    enum Activity
    {
        walk,
        shop,
        clean,
    }
    static int[] states = new int[]{Rainy.ordinal(), Sunny.ordinal()};
    static int[] observations = new int[]{walk.ordinal(), shop.ordinal(), clean.ordinal()};
    static double[] start_probability = new double[]{0.6, 0.4};
    static double[][] transititon_probability = new double[][]{
            {0.7, 0.3},
            {0.4, 0.6},
    };
    static double[][] emission_probability = new double[][]{
            {0.1, 0.4, 0.5},
            {0.6, 0.3, 0.1},
    };
 
    public static void main(String[] args)
    {
        int[] result = Viterbi.compute(observations, states, start_probability, transititon_probability, emission_probability);
        for (int r : result)
        {
            System.out.print(Weather.values()[r] + " ");
        }
        System.out.println();
    }
}

 转于：https://github.com/hankcs/Viterbi

转载学习于：https://blog.csdn.net/pipisorry/article/details/50722178