隐马尔可夫模型&＃xff08;HMM&＃xff09;

• 隐马尔可夫模型&＃xff08;HMM&＃xff09;
  • 1. 隐马尔可夫模型基本概念
    • 1.1 定义
    • 1.2 观测序列生成过程
    • 1.3 3个基本问题
  • 2. 概率计算方法
    • 2.1 直接计算法
    • 2.2 前向算法
    • 2.3 后向算法
  • 3. 学习算法
    • 3.1 监督学习方法
    • 3.2 非监督学习方法 EM算法 Baum-Welch算法
  • 4. 预测算法
    • 4.1 近似算法
    • 4.2 维特比算法

1. 隐马尔可夫模型基本概念

1.1 定义

• 隐马尔可夫模型&＃xff0c;又叫做HMM&＃xff0c;是关于时序的概率模型&＃xff0c;描述一个由隐藏的马尔科夫链随机生成不可观测的状态随机序列,再由各个状态生成一个可观测的观测随机序列的过程。
• 状态序列&＃xff08;state sequence&＃xff09;: 由隐藏的马尔可夫链生成的状态的序列&＃xff1b;
• 观测序列&＃xff08;observation sequence&＃xff09;: 每个状态生成一个观测&＃xff0c;由此产生一个观测序列&＃xff1b;
• 序列的每一个位置可以看做一个时刻&＃xff1b;
• 隐马尔可夫模型属于生成模型。在语音识别、自然语言处理等领域应用广泛

三元组来表示一个隐马尔可夫模型

• π 初始状态概率向量。 表示第1个时刻处于各个状态的概率
• A 状态转移概率矩阵。 Aij 表示由状态i转移到状态j的概率
• B 观测概率矩阵。 每一行对应一个状态&＃xff0c;每一列对应一个观测&＃xff0c;表示在该状态下&＃xff0c;出现某个观测的概率

两个基本假设&＃xff1a;

• 齐次马尔可夫性假设。隐藏的马尔可夫链在任意时刻t的状态&＃xff0c;只依赖于他前一个时刻的状态。与其他的状态和观测无关
• 观测独立性假设。任意时刻的观测只依赖于该时刻的状态。与其他的观测和状态无关

应用&＃xff1a;标注。
标注问题是给定观测序列预测其对应的标记序列。这是标记序列对应着状态序列。可以假设标注问题的数据是由隐马尔可夫模型生成的。

再多的公式也不如一个例子&＃xff1a;
掷骰子&＃xff0c;非常经典的问题&＃xff0c;三种骰子&＃xff0c;给出一个观测到的结果序列&＃xff0c;那么对应的骰子序列&＃xff0c;就是对应的隐藏状态序列。

1.2 观测序列生成过程

• 按照初始状态概率分布 π 产生初始时刻 t&＃61;1 的状态
• 按照观测概率矩阵&＃xff0c;产生在此状态下的观测
• 按照状态转移概率矩阵&＃xff0c;得到下一个时刻 t&＃61;2 的状态
• 依次直到t&＃61;T为止&＃xff0c;就产生了一个长度为T的观测序列和状态序列

1.3 3个基本问题

1. 概率计算。给定模型
   &＃xff0c;以及观测序列 O &＃xff0c;求该观测序列出现的概率
2. 学习问题。已知观测序列 O &＃xff0c;求模型参数A, B, π&＃xff0c;使得该模型下该观测序列出现的概率最大&＃xff0c;即用极大似然估计的方法估计参数
3. 预测问题。给定模型和观测序列&＃xff0c;求对应的最有可能的状态序列。即最大化条件概率P(I|O)

2. 概率计算方法

给出模型 &＃43; 观测序列。求该观测序列出现的概率

2.1 直接计算法

把所有可能出现该观测序列的状态序列&＃xff0c;全部枚举出来。然后计算每一个状态序列&＃43;观测序列对应的概率。取其中最大的一个作为该观测序列的概率。
当马尔可夫链比较长的时候&＃xff0c;枚举的情况太多&＃xff0c;导致此方法理论可行&＃xff0c;实际往往不行。

2.2 前向算法

先说一个简单的问题&＃xff0c;假如你知道了隐藏的状态序列&＃xff0c;让你求当前观测的序列概率。

那么概率的计算无非就是各个概率的相乘&＃xff1a;&＃xff08;包括状态到状态的转移概率&＃xff0c;以及状态到观测的概率&＃xff09;

现在问题升级&＃xff1a;不知道隐藏状态序列&＃xff0c;如何求出观测序列概率&＃xff1f;

解法也很简单&＃xff1a;对于t&＃61;1时刻&＃xff0c;依次假设当前处于某一个状态&＃xff0c;然后计算该状态下得到观测O(1)的概率。那么把所有的状态计算出来的概率**求和**&＃xff0c;就得到了t&＃61;1时刻&＃xff0c;出现该观测的概率&＃xff08;也就是我们要求的结果&＃xff09;。
然后开始递推&＃xff0c;假设已经求出来t&＃61;T-1时刻&＃xff0c;每一个状态对应的概率。那么对于t&＃61;T时刻&＃xff0c;我们依旧遍历当前处于的状态&＃xff0c;然后依据t&＃61;T-1的各状态概率计算结果&＃xff0c;来得到t&＃61;T时刻&＃xff0c;处于各个状态并得到T时刻观测的概率。遍历各个状态的概率&＃xff0c;**求和**就得到了T时刻观测的概率&＃xff0c;这个概率就是出现整个观测序列的概率&＃xff0c;也就是我们要求的最终结果.
这就是前向算法&＃xff08;forward algorithm&＃xff09;。

比如下面这个例子&＃xff1a;我们模型参数&＃xff08;骰子及各个概率&＃xff09;&＃xff0c;要求出出现观测1&＃xff0c;6&＃xff0c;3的概率是多少&＃xff1f;

首先&＃xff0c;如果我们只掷一次骰子&＃xff1a;

观测结果为1。产生这个结果的总概率可以按照如下来计算&＃xff0c;总概率为0.18:

P1表示第一次掷&＃xff0c;对应的每一行&＃xff0c;一次表示当前投掷的时候&＃xff0c;分别使用的是D6 D4 D8骰子。

情况拓展&＃xff0c;投掷两次骰子&＃xff1a;

看到结果为1&＃xff0c;6.产生这个结果的总概率为0.05&＃xff1a;

我们拿P2列&＃xff0c;D6行来解释下&＃xff1a;它表示第二次投掷用的是D6骰子&＃xff0c;那么第一次用哪个那&＃xff1f;都有可能&＃xff01;所以第二次观测到6的总概率&＃xff0c;就是&＃xff08;第一次用D6并投出了1的概率 &＃43; 第一次用D4并投出了1 &＃43; 第一次用D8并投出了1&＃xff09; * 第二次用了D6 * D6投出了6.
也就是说&＃xff0c;第二个状态是D6&＃xff0c;那么他可能是怎么来的那&＃xff1f;它是由第一个状态转化来的&＃xff0c;而且每一种第一个状态都可能以不同的概率转换成第二个状态。&＃xff08;这里我们为了简单&＃xff0c;认为都是1/3&＃xff09;
然后依次遍历第二个状态所有的状态&＃xff0c;求出概率后&＃xff0c;把概率加起来就是我们t&＃61;2时刻的观测出现的概率了。

继续拓展&＃xff0c;投三次&＃xff1a;

看到结果为1&＃xff0c;6&＃xff0c;3&＃xff0c;总概率为0.03&＃xff1a;

这样一步一步的计算&＃xff0c;无论马尔可夫链有多长&＃xff0c;总能算完。相比直接穷举这样复杂度会低很多。减少计算量的关键在于每一次计算都直接引用前一个计算的结果&＃xff0c;避免了重复计算。局部计算前向概率&＃xff0c;然后利用路径结构将前向概率递推到全局。

2.3 后向算法

与前向计算相对应的是后向计算。从后向前推&＃xff0c;大体的思想也是利用之前计算的结果来计算当前时刻的概率。

3. 学习算法

学习算法。主要是给出观测概率&＃xff0c;让我们估计模型参数。也就是学习这个模型是什么。是最常见的情况。

3.1 监督学习方法

如果给出了多个观测序列和对应的状态序列&＃xff0c;那么就属于监督学习。
所谓的监督学习就是用频率来估计概率。属于极大似然估计
比如&＃xff1a;统计每个状态序列t&＃61;1时刻的状态&＃xff0c;那么状态的频率我们就认为是状态的初始概率π

3.2 非监督学习方法 EM算法 Baum-Welch算法

非监督学习利用的是EM算法来进行参数估计

只有观测序列&＃xff0c;没有状态序列&＃xff0c;目标是求出对应的隐马尔可夫模型参数。那么隐马尔可夫模型实际上是一个含有隐变量的概率模型&＃xff1a;

• 第一步&＃xff1a;定义完全数据的对数似然函数。

定义完全数据为&＃xff1a;
完全数据的对数似然函数是

• 第二步&＃xff1a;EM算法的E步&＃xff1a;

利用当前模型参数的估计值&＃xff0c;得到完全数据的对数似然函数的期望&＃xff1a;

其中&＃xff0c;是当前模型参数的估计值。是要极大化的模型参数。

• 第三步&＃xff1a;EM算法的M步&＃xff1a;

将上面公式拆解成三部分&＃xff0c;分别只包含π, A, B然后分别极大化每一部分。利用了概率和为1这个约束条件&＃xff0c;再加上拉格朗日乘子法得到最终结果。

4. 预测算法

已知模型参数和观测序列&＃xff0c;目标&＃xff1a;求出最可能的状态序列

4.1 近似算法

思想非常简单&＃xff1a;在每个时刻t选择在该时刻最优可能出现的状态&＃xff0c;从而得到一个状态序列&＃xff0c;作为最终的预测结果。

4.2 维特比算法

维特比算法是用动态规划解决隐马尔可夫预测问题。求概率最大路径&＃xff0c;这时一条路径对应着一个状态序列。
最优路径特性&＃xff1a;从路径中间截开&＃xff0c;那么前面一段和后面一段都是最优的。
跟前向算法求观测概率一样&＃xff0c;我们还是递推的来求&＃xff0c;但是这次只关注如何选择状态可以得到一个最大概率&＃xff0c;而不是概率的和。最大的那个概率对应的状态&＃xff0c;就是我们预测的状态。
继续拿投骰子说事&＃xff1a;
首先&＃xff0c;如果我们只投一次骰子&＃xff1a;

观测结果为1&＃xff0c;对应最大概率的骰子序列就是D4&＃xff0c;因为D4产生1的概率是1/4&＃xff0c;大于1/6和1/8.

继续&＃xff0c;投两次骰子&＃xff1a;

观测结果为1&＃xff0c;6. 这时我们需要计算三个值&＃xff0c;分别是第二个骰子是D4&＃xff0c;D6&＃xff0c;D8的最大概率。

以第二个骰子是D6为例。第一个可选的状态为D4&＃xff0c;D6&＃xff0c;D8&＃xff0c;分别计算出概率为&＃xff1a;

最终&＃xff0c;P2(D6)选上面三个中概率最大的一个。

依次计算出P2(D4)和P2(D8)&＃xff0c;然后从这些里面取最大概率值&＃xff0c;作为第二轮的预测状态。

这里跟前向传播比较相似&＃xff0c;只不过每次都只取最大值。同样是利用了之前的计算结果&＃xff0c;所以减小了计算量。

欢迎关注公众号&＃xff1a;机器学习荐货情报局
一起进步&＃xff0c;一起学习&＃xff0c;一起充电~
欢迎投稿&＃xff0c;讨论&＃xff0c;拍砖