隐马尔可夫模型(Hidden Markov Model)

Hits: 216

我们先从马尔科夫模型说起。

Markov Model

马尔科夫模型(The Markov chain, sometimes called the observed Markov model)本质上是一个加权的有限状态机(weighted finite automaton),它描述了不同状态之间的转换关系以及转换概率(这里的权重就是状态转移概率)。示意图如下:
imgur
一个严格定义的马尔科夫模型由以下几个部分组成:

$$
\begin{align*}
& Q = q_1,q_2,...,q_N \\
& A = a_{01},a_{02},...,a_{nn} \\
& q_0, q_F
\end{align*}
$$

其中,

  • \(Q\)是大小为\(N\)的状态集合;
  • \(A\)是状态转移矩阵(transition probability matrix),矩阵内的元素\(a_{ij}\)表示的是从状态\(i\)转移到状态\(j\)的概率,他们之间满足:对于任意\(i\)都有\(\sum_{j=1}^{n}a_{ij} = 1\),也就是所有从状态\(i\)出去的概率之和为1;
  • \(q_0\)和\(q_F\)分别表示初始状态和结束状态;

我们常说的Markov Model其实是一阶马尔科夫模型(first-order Markov Model),它有个最基本的假设:当前状态出现的概率,只取决于上一个状态(In a first-order Markov chain, the probability of a particular state depends only on the previous state),数学表达式如下:

$$
P(q_i|q_1,q_2,...,q_{i-1}) = P(q_i | q_{i-1})
$$

马尔科夫模型有什么用呢?

我们知道两个状态之间的转移概率是很容易计算出来的,但是一连串的状态出现的概率却没那么容易计算。于是,我们可以先通过计算两两状态之间的转移概率构造出一个马尔科夫链,然后再通过马尔科夫链去计算一连串状态出现的概率(A Markov chain is useful when we need to compute a probability for a sequence of events that we can observe in the world.)这句话的重点是如何计算一连串状态出现的概率。

Hidden Markov Model

马尔科夫模型主要用于计算observed event之间的转换概率,然而现实场景中有些事件是不能直接观测到的,比如part-of-speech tagging(POS tagging)任务:给定一句话(sentence或者a sequence of words),然后预测这句话中每个单词的词性(part-of-speech)。在这个任务中,a sequence of words是可以被直接观测到的,但是每个word的词性(part-of-speech)却是隐藏的;Hidden Markov Model就是用来联系观测事件(observed event)和隐藏事件(hidden event)的模型。Hidden Markov models (HMMs) are a way of relating a sequence of observations to a sequence of hidden classes or hidden states that explain the observations。
那隐马尔可夫模型具体是怎么联系观测事件和隐藏事件的呢?其实也很简单:在马尔科夫模型的基础上增加了一个新的状态输出:从一个隐藏状态到观察状态的输出。直观上来讲,马尔科夫模型只有下图上面蓝色一排的状态转换,但是隐马尔科夫模型则多了下面一排红色的输出状态。
Imgur
那么怎么理解隐藏状态到观察状态的输出概率呢?我们先举个例子,

假设你是一个气象学家,你现在要研究2001年某个地区某几天的气候状况,我们假设天气要么热(H)要么冷(C)。但是那几天该地区的气象资料全部丢失了,你无法直接得到数据。幸运的是,有一个叫Jason的小朋友每天都写日记,并且把自己吃冰激凌的数量都记录了下来。我们知道每天吃冰激凌的数量跟当天的温度是有关系的,自然是天气越热吃的冰激凌就越多。于是,你的任务就变成是通过观察Jason每天吃冰激凌的数量来预测当天的气候状况

上面描述的任务转化为隐马尔可夫模型的术语就是:

Given a sequence of observations O, each observation an integer corresponding to the number of ice creams eaten on a given day, figure out the correct ‘hidden’ sequence Q of weather states (H or C) which caused Jason to eat the ice cream.

Imgur
如上图所示:隐藏状态到观察状态的输出概率指的就是概率矩阵B,我们称之为似然概率(observation likelihoods)或者emission probabilities。我们以B1为例,它表达的意思是:在当天气候是H的情况下,Jason吃掉1/2/3根冰激凌的概率分别是多少。

下面我们给出隐马尔科夫模型的正式定义:

$$
\begin{align*}
& Q = q_1,q_2,...,q_N \\
& A = a_{01},a_{02},...,a_{nn} \\
& O = o_{1},o_{2},...o_{T} \\
& B = b_i(o_t) \\
& q_0, q_F
\end{align*}
$$

其中,

  • \(Q\)是大小为\(N\)的状态集合;
  • \(A\)是状态转移矩阵(transition probability matrix),矩阵内的元素\(a_{ij}\)表示的是从状态\(i\)转移到状态\(j\)的概率,他们之间满足:对于任意\(i\)都有\(\sum_{j=1}^{n}a_{ij} = 1\),也就是所有从状态\(i\)出去的概率之和为1;
  • \(O\)表示的是观测序列;
  • \(B\)是observation likelihoods或者emission probabilities,它表示的是在给定状态\(i\)的情况下生成观测对象\(o_i\)的概率;
  • \(q_0\)和\(q_F\)分别表示初始状态和结束状态;

理解了隐马尔科夫模型之后,我们再来看看它的三个基本问题:

  • 问题一(Likelihood)
    给定一个隐马尔科夫模型HMM: \( \lambda = (A,B)\)和观测序列\(O\),求解似然概率:\(P(O|\lambda)\)。这个直观的算法是穷举所有情况,复杂度是\(O(N^{T})\),\(N\)是隐藏状态的数量,\(T\)是观测序列的个数;这种蛮力算法复杂度太高,取而代之的是一种动态规划的方法:The Forward Algorithm,它能把复杂度降低到\(O(N^{2}T)\)。

  • 问题二(Decoding)
    给定一个隐马尔科夫模型HMM: \( \lambda = (A,B)\)和观测序列\(O\),找出最佳的隐藏状态序列\(Q\)。这个问题就是我们上面介绍的根据Jason吃冰激凌的数量来预测气候的抽象。求解的方法是:The Viterbi Algorithm,同样是一种动态规划算法。

  • 问题三(Learning)
    给定一个观察序列\(O\)和所有可能状态的集合,学习HMM的参数:\(A\)和\(B\)。求解的方法是一种特殊的EM(Expectation-Maximization)算法:The Forward-Backward Algorithm。

由于篇幅有限,以上三个问题的求解算法请参考:Charpter 9: Hidden Markov Models


发表评论

电子邮件地址不会被公开。 必填项已用*标注