论文部分内容阅读
摘要
隐马尔可夫模型（Hidden Markov Model，HMM）作为一种统计分析模型，创立于20世纪70年代。80年代得到了传播和发展，成为信号处理的一个重要方向，现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域。
本文先是简要介绍了HMM的由来和概念，之后重点介绍了3个隐马尔科夫模型的核心问题。
关键词：HMM，三个核心问题
HMM的由来
1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出马尔可夫模型。马尔可夫在分析俄国文学家普希金的名著《叶夫盖尼•奥涅金》的文字的过程中，提出了后来被称为马尔可夫框架的思想。而Baum及其同事则提出了隐马尔可夫模型，这一思想后来在语音识别领域得到了异常成功的应用。同时，隐马尔可夫模型在“统计语言学习”以及“序列符号识别”（比如DNA序列）等領域也得到了应用。人们还把隐马尔可夫模型扩展到二维领域，用于光学字符识别。而其中的解码算法则是由Viterbi和他的同事们发展起来的。
马尔可夫性和马尔可夫链
1. 马尔可夫性
如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性，或称此过程为马尔可夫过程。马尔可夫性可用如下式子形象地表示：
X(t+1)=f(X(t))
2. 马尔可夫链
时间和状态都离散的马尔可夫过程称为马尔可夫链。
记作{Xn=X(n), n=0,1,2,…}
这是在时间集T1={0,1,2,…}上对离散状态的过程相继观察的结果。
链的状态空间记作I={a1, a2,...}, ai ∈R.
条件概率Pij(m, m+n)=P{ Xm+n = aj | Xm = aj }为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率。
3. 转移概率矩阵
如下图所示，这是一个转移概率矩阵的例子。
由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有
当 与m无关时，称马尔可夫链为齐次马尔可夫链，通常说的马尔可夫链都是指齐次马尔可夫链。
对实例的描述：
设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下：
—根据初始概率分布，随机选择N个缸中的一个开始实验；
—根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中；
—根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。
最后得到一个描述球的颜色的序列O1, O2,…,称为观察值序列O。
在上述实验中，有几个要点需要注意：
不能被直接观察缸间的转移；
从缸中所选取的球的颜色和缸并不是一一对应的；
每次选取哪个缸由一组转移概率决定。
2. HMM概念
HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来。
观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系。
HMM是一个双重随机过程，两个组成部分：
—马尔可夫链：描述状态的转移，用转移概率描述。
—一般随机过程：描述状态与观察序列间的关系，用观察值概率描述。
3. HMM组成
通过上述例子可以看出，一个HMM由如下几个部分组成：
(1) 模型中状态的数目N(上例中缸的数目)；
(2) 从每个状态可能输出的不同符号的数目M(上例中球的不同颜色的数目)；
(3) 状态转移概率矩阵A={aij}(aij为实验员从一个缸(状态si)转向另一个缸(sj)取球的概率)；
(4) 从状态sj观察到符号vk的概率分布矩阵B={bj(k)}(bj(k)为实验员从第j个缸中取出第k种颜色的球的概率)；
(5) 初始状态概率分布π={πi}。
4. HMM的基本要素
用模型五元组 ＝( N, M,π,A,B）用来描述HMM，或简写为 =(π,A,B)。
具体说明见下表所示：
定义了这些符号和术语之后，使得我们可以关注下列3个隐马尔可夫模型的核心问题：
(1) 估值问题：假设我们有一个HMM，其转移概率aij和bij均已知。计算这个模型产生某一个特定观测序列VT的概率。
(2) 解码问题：假设我们已经有了一个HMM和它所产生的一个观测序列，决定最有可能产生这个可见观测序列的隐状态序列 。
(3) 学习问题：假设我们只知道一个HMM的大致的结构（比如隐状态数量和可见状态数量），但aij和bjk军位置。如何从一组可见符号的训练序列中，决定这些参数。
HMM的3个基本问题
针对以上三个问题，人们提出了相应的算法。
评估问题：向前向后算法。
解码问题：Viterbi算法。
学习问题：Baum-Welch算法。
1. Viterbi算法
维特比算法用来求解第二个问题。对“最优状态序列”的理解为：在给定模型μ和观察序列O的条件下，使条件概率P(Q|O, μ)最大的状态序列，即
采用动态规划算法。复杂度O(K2L)。K和L分别为状态个数和序列长度。
2. 前向—后向算法
用来解决第一种问题。实际上我们可以采用前向算法和后向算法相结合的方法来计算观察序列的概率。
前向算法：动态规划，复杂度同Viterbi。
HMM的应用
应用于语音识别，机器视觉（人脸检测，机器人足球），图像处理（图像去噪，图像识别），生物医学分析（DNA/蛋白质序列分析）等各个领域。
注：文章内所有公式及图表请用PDF形式查看。
隐马尔可夫模型（Hidden Markov Model，HMM）作为一种统计分析模型，创立于20世纪70年代。80年代得到了传播和发展，成为信号处理的一个重要方向，现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域。
本文先是简要介绍了HMM的由来和概念，之后重点介绍了3个隐马尔科夫模型的核心问题。
关键词：HMM，三个核心问题
HMM的由来
1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出马尔可夫模型。马尔可夫在分析俄国文学家普希金的名著《叶夫盖尼•奥涅金》的文字的过程中，提出了后来被称为马尔可夫框架的思想。而Baum及其同事则提出了隐马尔可夫模型，这一思想后来在语音识别领域得到了异常成功的应用。同时，隐马尔可夫模型在“统计语言学习”以及“序列符号识别”（比如DNA序列）等領域也得到了应用。人们还把隐马尔可夫模型扩展到二维领域，用于光学字符识别。而其中的解码算法则是由Viterbi和他的同事们发展起来的。
马尔可夫性和马尔可夫链
1. 马尔可夫性
如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性，或称此过程为马尔可夫过程。马尔可夫性可用如下式子形象地表示：
X(t+1)=f(X(t))
2. 马尔可夫链
时间和状态都离散的马尔可夫过程称为马尔可夫链。
记作{Xn=X(n), n=0,1,2,…}
这是在时间集T1={0,1,2,…}上对离散状态的过程相继观察的结果。
链的状态空间记作I={a1, a2,...}, ai ∈R.
条件概率Pij(m, m+n)=P{ Xm+n = aj | Xm = aj }为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率。
3. 转移概率矩阵
如下图所示，这是一个转移概率矩阵的例子。
由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有
当 与m无关时，称马尔可夫链为齐次马尔可夫链，通常说的马尔可夫链都是指齐次马尔可夫链。
对实例的描述：
设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下：
—根据初始概率分布，随机选择N个缸中的一个开始实验；
—根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中；
—根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。
最后得到一个描述球的颜色的序列O1, O2,…,称为观察值序列O。
在上述实验中，有几个要点需要注意：
不能被直接观察缸间的转移；
从缸中所选取的球的颜色和缸并不是一一对应的；
每次选取哪个缸由一组转移概率决定。
2. HMM概念
HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来。
观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系。
HMM是一个双重随机过程，两个组成部分：
—马尔可夫链：描述状态的转移，用转移概率描述。
—一般随机过程：描述状态与观察序列间的关系，用观察值概率描述。
3. HMM组成
通过上述例子可以看出，一个HMM由如下几个部分组成：
(1) 模型中状态的数目N(上例中缸的数目)；
(2) 从每个状态可能输出的不同符号的数目M(上例中球的不同颜色的数目)；
(3) 状态转移概率矩阵A={aij}(aij为实验员从一个缸(状态si)转向另一个缸(sj)取球的概率)；
(4) 从状态sj观察到符号vk的概率分布矩阵B={bj(k)}(bj(k)为实验员从第j个缸中取出第k种颜色的球的概率)；
(5) 初始状态概率分布π={πi}。
4. HMM的基本要素
用模型五元组 ＝( N, M,π,A,B）用来描述HMM，或简写为 =(π,A,B)。
具体说明见下表所示：
定义了这些符号和术语之后，使得我们可以关注下列3个隐马尔可夫模型的核心问题：
(1) 估值问题：假设我们有一个HMM，其转移概率aij和bij均已知。计算这个模型产生某一个特定观测序列VT的概率。
(2) 解码问题：假设我们已经有了一个HMM和它所产生的一个观测序列，决定最有可能产生这个可见观测序列的隐状态序列 。
(3) 学习问题：假设我们只知道一个HMM的大致的结构（比如隐状态数量和可见状态数量），但aij和bjk军位置。如何从一组可见符号的训练序列中，决定这些参数。
HMM的3个基本问题
针对以上三个问题，人们提出了相应的算法。
评估问题：向前向后算法。
解码问题：Viterbi算法。
学习问题：Baum-Welch算法。
1. Viterbi算法
维特比算法用来求解第二个问题。对“最优状态序列”的理解为：在给定模型μ和观察序列O的条件下，使条件概率P(Q|O, μ)最大的状态序列，即
采用动态规划算法。复杂度O(K2L)。K和L分别为状态个数和序列长度。
2. 前向—后向算法
用来解决第一种问题。实际上我们可以采用前向算法和后向算法相结合的方法来计算观察序列的概率。
前向算法：动态规划，复杂度同Viterbi。
HMM的应用
应用于语音识别，机器视觉（人脸检测，机器人足球），图像处理（图像去噪，图像识别），生物医学分析（DNA/蛋白质序列分析）等各个领域。
注：文章内所有公式及图表请用PDF形式查看。