隐马尔科夫模型(HMM)

隐形马尔可夫模型，英文是 Hidden Markov Models，所以以下就简称 HMM。
既是马尔可夫模型，就一定存在马尔可夫链，该马尔可夫链服从马尔可夫性质：即无记忆性。也就是说，这一时刻的状态，受且只受前一时刻的影响，而不受更往前时刻的状态的影响。
其实隐马尔科夫模型就是一个三元的元组，隐含状态转移概率矩阵 A，观测状态转移概率矩阵 B，初始状态概率矩阵π。
这里说说大概怎么用这个模型。
假设我有几个句子：

要买\o 一个\o 70平\m 房子\o 价格\o 6000元\j 每平\o
想\o 买个\o 大小\o 80\m 房子\o 价格\o 5000元\j 每平\o
一个\o 100平\m 房子\o 每平\o 9000\j
有没有\o 60平\m 房子\o 两个人\o 住\o 够\o
大小\o 100平\m 房子\o 价格\o 80万\j

那么这些句子连在一起我们就可以看做是一个链，在这个链中，每个词就是一个可观测序列，每个词对应的标签就是它的隐藏状态。例如：要买\o，那么要买就是可观测的，\o就是它的隐藏状态。
对于这个链的三个状态分别如下：

• 初始状态 π：表示隐含状态在初始时刻t=1的[概率]矩阵，(例如t=1时，P(S1)=p1、P(S2)=P2、P(S3)=p3，则初始状态概率矩阵 π=[ p1 p2 p3 ]。
  那么该链隐藏状态的初始概率为，
  \o： 22/30
  \m： 5/30
  \j： 4/30
  分别就是每个隐状态出现的次数和所有隐状态次数作比较。

• 隐含状态转移概率矩阵 A：描述了HMM模型中各个状态之间的转移概率。其中Aij = P( Sj | Si ),1≤i,j≤N.表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。
  p(sj|si) = #(si,sj)/(si)

sj/si	\o	\m	\j
\o	13/22	5/22	4/22
\m	1	0	0
\j	1	0	0

这个矩阵就是指每个隐藏状态和它前一刻的状态的转移概率。

• 观测状态转移概率矩阵 B(混淆矩阵)：令N代表隐含状态数目，M代表可观测状态数目，则：Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N.表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率。
  p(oi|sj) = #(oi,sj)/#(sj)

sj/oi	要买	一个	70平	房子	价格	每平	6000元	想	买个	大小	80	5000元	100平	9000	有没有	60平	两个人	住	够	80万
\o	1/22	2/22	0	5/22	3/22	3/22	0	1/22	1/22	2/22	0	0	0	0	1/22	0	1/22	1/22	1/22	0
\m	0	0	1/5	0	0	0	0	0	0	0	1/5	0	2/5	0	0	1/5	0	0	0	0
\j	0	0	0	0	0	0	1/3	0	0	0	0	1/3	0	1/3	0	0	0	0	0	0

---

一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系。

---

一般HMM模型对应着三个问题，我们来看看百度怎么说的这三个问题：

• 评估问题：
  给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样有效计算某一观测序列的概率，进而可对该HMM做出相关评估。例如，已有一些模型参数各异的HMM，给定观测序列O=O1O2O3…Ot，我们想知道哪个HMM模型最可能生成该观测序列。通常我们利用forward算法或者Backward算法分别计算每个HMM产生给定观测序列O的概率，然后从中选出最优的HMM模型。
  对于上面咱们自己建的那个模型，这个问题就是给定一句话，并给出这句话中每个词对应的标签，根据模型，计算每个标签的概率。

• 解码问题：
  给定观测序列 O=O1O2O3…Ot 和模型参数λ=(A,B,π)，怎样寻找某种意义上最优的隐状态序列。在这类问题中，我们感兴趣的是马尔科夫模型中隐含状态，这些状态不能直接观测但却更具有价值，通常利用Viterbi算法来寻找。
  对于上面已经建好的模型，给定三个词，那么，根据模型，计算产生这三个词分别对应了什么标签。

• 学习问题：
  即HMM的模型参数λ=(A,B,π)未知，如何调整这些参数以使观测序列O=O1O2O3…Ot的概率尽可能的大。通常使用Baum-Welch算法以及Reversed Viterbi算法解决。
  假设我只有一句话和这句话有哪些标签，那么我们如何建立一个模型，使我们知道的句子的概率尽可能的大。

---

这里大概讲两种算法：

向前算法

假设我拿上面的一句话来做向前算法：
一个\o 100平\m 房子\o 每平\o 9000\j

• 那么在t=1时刻，该时刻标签为\o，如果该时刻的词是一个，那么概率就是
  P(一个,\o)=P(\o的初始概率) x P(一个 | \o)=22/30 x 2/22
• 在t=2时刻该词为100平，那么\m概率
  P(t=1 一个,t=2 100平,t=2 \m) = [P(t=1 一个,t=1 \o) x P(t=2 \m | t=1 \o) +P(t=1 一个,t=1 \m) x P(t=2 \m | t=1 \m) + P(t=1 一个,t=1 \j) x P(t=2 \m | t=1 \j)] x P(t=2 100平 | t=2 \m)
• 在t=3时刻该词为房子，那么\o的概率
  P(t=1 一个,t=2 100平,t=3 房子,t=3 \o)
  ...这里就不推了，太多了，不过计算方式如上。

维特比求解

也是我们假设我们有一句话：
一个 100平 房子 每平 9000
在这里我们只知道这个序列的可观测状态，想要获得每一个词的隐含状态。那么，

• t=1时刻
  P(\o)=P(一个|\o) x P(\o|初始概率)=2/22 x 22/30
  P(\m)=P(一个|\m) x P(\m|初始概率)=0 x 5/30
  P(\j)=P(一个|\j) x P(\j|初始概率)=0 x 4/30
  那么一个这个词最有可能的便签就是\o
• t=2时刻
  P(t=1 \o,t=2 \o) = P(t=1 \o) x P(\o -> \o) x P(100平|\o)=(2/22 x 22/30) x 13/22 x 0
  P(t=1 \o,t=2 \m) = P(t=1 \o) x P(\o -> \m) x P(100平|\m)
  P(t=1 \o,t=2 \j) ...
  P(t=1 \m,t=2 \o) ...
  P(t=1 \m,t=2 \m) ...
  P(t=1 \m,t=2 \j) ...
  P(t=1 \j,t=2 \o) ...
  P(t=1 \j,t=2 \m) ...
  P(t=1 \j,t=2 \j) ...
• t=3时刻计算方式如上，他们的状态都只和上一时刻t-1有关。

最后我们可以获得每一时刻最大概率的隐藏状态就是每一时刻观测状态对应的隐藏状态。
这个算法大概就是通过已知的可以观察到的序列，和一些已知的状态转换之间的概率情况，通过综合状态之间的转移概率和前一个状态的情况计算出概率最大的状态转换路径，从而推断出隐含状态的序列的情况。