Markov&HMM

Markov

马尔可夫模型（Markov Model）和回归、分类那些处理相互独立的样本数据的模型不同，它用于处理时间序列数据，即样本之间有时间序列关系的数据。Markov 最核心的思想是："当前状态只与上一时刻状态有关，而与之前其它任何时刻的状态都无关"。我个人觉得这是 Markov 最大的问题，至于为什么，放在文章后面。下面先举个例子具体讲解一下 Markov 模型

现在有这么一个人，每天有三种状态：吃、睡、玩。这就是传说中的状态分布

现在你想知道他第 n 天是什么状态，是在吃，还是在玩，还是在睡？这些状态发生的概率分别都是多少？

先做个假设，假设他每天状态的转移都是有固定概率的。比如说，今天玩了，明天吃的概率是 0.6、明天睡的概率是 0.3、明天继续玩的概率是 0.1，那我们就能构建下面这个矩阵

这个矩阵就是状态转移概率矩阵 $P$，并且它是保持不变的，也就是说第一天的状态转移概率矩阵和第二天以及之后每天的状态转移概率矩阵都是一样的

有了这个矩阵，再加上如果已知第一天的状态分布（向量），就可以算出任意一天的状态的概率分布（向量）了

举个很简单例子，假设这个人 10 月 1 号在吃、玩、睡的概率分别是 $S_1=(0.6, 0.2, 0.2)$，那么

10 月 2 号的状态分布向量 $S_2=S_1 * P = (0.22, 0.4, 0.38)$

10 月 3 号的状态分布向量 $S_3=S_2 * P=(0.236,0.496,0.268)$（看见没，跟 $S_1$ 无关，只跟 $S_2$ 有关）

10 月 4 号的状态分布向量 $S_4=S_3 * P$（看见没，只跟 $S_3$ 有关）

10 月 n 号的状态分布向量 $S_n=S_{n-1}*P$（看见没，只跟它前面的一个状态 $S_{n-1}$ 有关）

朴素的 Markov 内容就这么多。最后做个总结，其实如果你要算第 n 个时刻的状态 $S_n$，只需要计算 $S_1*P^n$ 即可

关于我一开始提到的 Markov 的问题，不知道你看到有没有体会到，我觉得它最大的问题就是太不关注以前的数据了。举个很简单的例子，假设现在你从商场买完东西回到了家，我们就研究这段路径

假设我们将这段路径平均分为 5 个时刻（图中蓝点）。我们可以思考一下这个人的决策过程，她肯定应该是从商场一出来就想直接回家，心里已经有了一个长期的规划。如果是 Markov 来做预测，会怎么想呢？Markov 模型会认为这是一个短期的决策，它认为这个人只是在绿点开始才突然想回家的，前面你怎么想，Markov 并不知道，也并不管，因为在它看来，最重要的就是前一时刻的状态

我个人无论如何都觉得 Markov 用来处理时间序列数据的时候会有很大的问题。这也是我当时写论文的时候发现的，本来论文准备主用 Markov 的，后来改成一个能预测长期趋势的模型 + Markov 修正这样的策略。有兴趣的可以去看下我这篇论文

HMM（隐马尔可夫模型）

所谓隐，就是看不见的意思。借用一句话："当看到方便面中的油包变成固体的时候，宅男知道，冬天来了"。这里的季节 (冬天) 就是隐藏起来的变量，宅男 (观察者) 不出门，所以看不到天气，他只能看到方便面调料 (可观测结果)。HMM 除了要求隐状态本身之间有固定的转移概率之外，还要求观测序列和隐状态序列之间也有固定的概率关系

设 $Q$ 是所有可能的 (隐) 状态的集合，$V$ 是所有可能的观测集合：

$$ Q=\{q_1, q_2, ..., q_N\}, V=\{v_1,v_2,...,v_M\} $$

其中，$N$ 是可能的状态数，$M$ 是可能的观测数。

$I$ 是长度为 $T$ 的状态序列，$O$ 是对应的观测序列：

$$ I=(i_1, i_2, ..., i_T), O=(o_1, o_2, ..., o_T) $$

$A$ 是 (隐) 状态转移概率矩阵：

$$ A=[a_{ij}]_{N\times N} $$

其中，

$$ a_{ij}=P(i_{t+1}=q_j\mid i_t=q_i),\ \ \ \ i,j=1, 2, ..., N $$

表示在时刻 $t$ 处于状态 $q_i$ 条件下，在时刻 $t+1$ 转移到状态 $q_j$ 的概率。例如现在是冬天，下一时刻转换到春、秋、夏的概率

$B$ 是观测矩阵：

$$ B=[b_j(k)]_{N\times M} $$

其中，

$$ b_j(k)=P(o_t=v_k\mid i_t=q_j),\ \ \ \ k=1,2,...,M;\ \ j=1,2,...,N $$

表示在时刻 $t$ 处于状态 $q_j$ 的条件下生成观测 $v_k$ 的概率。例如宅男看到油包变成固体时，认为现在是冬天的概率

$\pi$ 是初始状态概率向量：

$$ \pi =(\pi_i) $$

其中，

$$ \pi_i = P(i_1=q_i),\ \ \ \ i=1,2,...,N $$

表示时刻 $t=1$ 处于状态 $q_i$ 的概率。例如最开始是春、夏、秋、冬四个季节的概率

隐马尔可夫模型由初始状态概率向量 $\pi$、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。$\pi$ 和 $A$ 决定状态序列，$B$ 决定观测序列。因此隐马尔可夫模型 $\lambda$ 可以用三元符号表示，即

$$ \lambda=(A,B, \pi) $$

$A,B,\pi$ 称为隐马尔可夫模型的三要素

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

从定义可知，隐马尔可夫模型作了两个基本的假设：

• 齐次马尔可夫性假设。即假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻 $t$ 无关：

$$ P(i_t\mid i_{t-1},o_{t-1},...,i_1,o_1)={P(i_t\mid i_{t-1})},\ \ \ \ t=1,2,...,T $$

• 观测独立性假设。即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其它观测及状态无关：

$$ P(o_t\mid i_T,o_T,i_{T-1},o_{T-1},...,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},...,i_1,o_1)=P(o_t\mid i_t) $$

隐马尔可夫模型可以用于标注，这时状态对应着标记。标注问题是给定观测的序列预测其对应的标记序列。可以嘉定标注问题的数据是由隐马尔可夫模型生成的。这样我们可以利用隐马尔可夫模型的学习与预测算法进行标注

下面看一个隐马尔可夫模型的例子

假设有 4 个盒子，每个盒子里都装有红、白两种颜色的球，盒子里的红、白球数由下表给出

按照下面的方法，产生一个球的颜色的观测序列：

• 开始，从 4 个盒子里以等概率随机选取 1 个盒子，从这个盒子里随机抽出 1 个球，记录其颜色后，放回
• 然后，从当前盒子随机转移到下一个盒子，规则是：如果当前盒子是盒子 1，那么下一盒子一定是盒子 2；如果当前是 2 或 3，那么分别以概率 0.4 和 0.6 转移到左边和右边的盒子；如果当前盒子是 4，那么各以 0.5 的概率停留在盒子 4 或转移到盒子 3
• 确定转移的盒子后，再从这个盒子里随机抽出 1 个球，记录其颜色，放回
• 如此下去，重复进行 5 次，得到一个球的颜色的观测序列

$$ O=(\mbox {红},\mbox {红}, 白，白，红) $$

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

在这个例子中有两个随机序列，一个是盒子的序列（状态序列），一个是球的颜色的序列（观测序列）。前者是隐藏的，只有后者是可观测的。这是一个隐马尔可夫模型的例子。根据所给条件，可以明确状态集合、观测集合、序列长度以及模型的三要素

盒子对应状态，而这个状态的集合是：

$$ Q=\{盒子 1, 盒子 2, 盒子 3, 盒子 4\},\ \ \ \ N=4 $$

球的颜色对应观测。而这个观测的集合是：

$$ V=\{红，白 \},\ \ \ \ M=2 $$

状态序列和观测序列长度 $T=5$

初始概率分布为

$$ \pi = (0.25, 0.25, 0.25, 0.25)^T $$

状态转移概率分布为

$$ A = \begin{bmatrix} {0}&{1}&{0}&{0}\\ {0.4}&{0}&{0.6}&{0}\\ {0}&{0.4}&{0}&{0.6}\\ {0}&{0}&{0.5}&{0.5}\\ \end{bmatrix} $$

观测概率分布为

$$ B = \begin{bmatrix} {0.5}&{0.5}\\ {0.3}&{0.7}\\ {0.6}&{0.4}\\ {0.8}&{0.8}\\ \end{bmatrix} $$

观测序列的生成

根据隐马尔可夫模型的定义，可以将一个长度为 $T$ 的观测序列 $O={o_1,o_2,...,o_T}$ 的生成过程描述如下：

输入：隐马尔可夫模型 $\lambda=(A,B,\pi)$，观测序列长度 $T$

输出：观测序列 $O=(o_1,o_2,...,o_T)$

1. 按照初始状态分布 $\pi$ 产生状态 $i_1$
2. 令 $t=1$
3. 按照状态 $i_1$ 的观测概率分布 $b_{i_t}(k)$ 生成 $o_t$
4. 按照状态 $i_t$ 的状态转移概率分布 $\{a_{i_ti_{t+1}}\}$ 产生状态 $i_{t+1},i_{t+1}=1,2,...,N$
5. 令 $t=t+1$；如果 $t<T$，转步骤 3；否侧，终止

隐马尔可夫模型的 3 个基本问题（重点）

隐马尔可夫模型有 3 个基本问题：

1. 概率计算问题。给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,...,o_T)$，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P (O\mid \lambda)$
2. 学习问题。已知观测序列 $O=(o_1,o_2,...,o_T)$，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在该模型下观测序列概率 $P (O\mid \lambda)$ 最大。即用最大似然估计的方法估计参数
3. 预测问题，也称为解码（decoding）问题。已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,...,o_T)$，求给定观测序列条件 $P (I\mid O)$ 最大的状态序列 $I=(i_1,i_2,...,i_T)$。即给定观测序列，求最有可能对应的状态序列

HMM 的概率计算法

下面主要介绍计算观测序列概率 $P (O\mid \lambda)$ 的前向（forward）与后向（backward）算法。先介绍概念上可行但计算上不可行的直接计算法

1. 直接计算法

给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,...,o_T)$，计算观测序列 $O$ 出现的概率 $P (O\mid \lambda)$。最直接的方法是按概率公式直接计算。通过列举所有可能的长度为 $T$ 的状态序列 $I=(i_1,i_2,...,i_T)$，求各个状态序列 $I$ 与观测序列 $O=(o_1,o_2,...,o_T)$ 的联合概率 $P (O,I\mid \lambda)$，然后对所有可能的状态序列求和，得到 $P (O\mid \lambda)$

状态序列 $I=(i_1,i_2,...,i_T)$ 的概率是

$$ P(I\mid \lambda) = \pi_{i_1}a_{i_1i_2}a_{i_2i_3}···a_{i_{T-1}i_T} $$

对固定的状态序列 $I=(i_1,i_2,...,i_T)$，观测序列 $O=(o_1,o_2,...,o_T)$ 的概率是

$$ P(O\mid I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)···b_{i_t}(o_T) $$

然后，对所有可能的状态序列 $I$ 求和，得到观测序列 $O$ 的概率 $P (O\mid \lambda)$，即

$$ \begin{align*} P(O\mid \lambda)&=\sum_I P(O\mid I,\lambda)P(I\mid \lambda)\\ &=\sum_{i_1,i_2,..,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)···a_{i_{T-1}i_T}b_{i_T}(o_T) \end{align*} $$

但是上面这个公式的计算量很大，时间复杂度是 $O (TN^T)$ 阶的，这种算法不可行

下面介绍计算观测序列概率 $P (O\mid \lambda)$ 的有效算法：前向 - 后向算法（forward-backward algorithm）

2. 前向算法

首先定义前向概率。给定隐马尔可夫模型 $\lambda$，定义到时刻 $t$ 部分观测序列为 $o_1,o_2,...,o_t$ 且状态为 $q_i$ 的概率为前向概率，记作

$$ \alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i\mid \lambda) $$

可以递推地求得前向概率 $\alpha_t (i)$ 及观测序列概率 $P (O\mid \lambda)$

输入：隐马尔可夫模型 $\lambda$，观测序列 $O$

输出：观测序列概率 $P (O\mid \lambda)$

（1）初值

$$ \alpha_1(i)=\pi_ib_i(o_1),\ \ \ \ i=1,2,...,N $$

（2）递推，对 $t=1,2,...,T-1$

$$ \alpha_{t+1}(i)=\bigg [\sum_{j=1}^N \alpha_t(j)a_{ji}\bigg ]b_i(o_{t+1}),\ \ \ \ i=1,2,...,N $$

（3）终止

$$ P(O\mid \lambda)=\sum_{i=1}^N \alpha_T(i) $$

前向算法，步骤（1）初始化前向概率，是初始时刻的状态 $i_1=q_i$ 和观测 $o_1$ 的联合概率。步骤（2）是前向概率的递推公式，计算到时刻 $t+1$ 部分观测序列为 $o_1,o_2,...,o_t,o_{t+1}$ 且在时刻 $t+1$ 处于状态 $q_i$ 的前向概率，如下图所示

在步骤（2）公式的方括弧里，既然 $\alpha_t (j)$ 是到时刻 $t$ 观测到 $o_1,o_2,...,o_t$ 并在时刻 $t$ 处于状态 $q_j$ 的前向概率，那么乘积 $\alpha_t (j) a_{ji}$ 就是到时刻 $t$ 观测到 $o_1,o_2,...,o_t$ 并在时刻 $t$ 处于状态 $q_j$ 而在时刻 $t+1$ 到达状态 $q_i$ 的联合概率。对这个乘积在时刻 $t$ 的所有可能的 $N$ 个状态 $q_j$ 求和，其结果就是到时刻 $t$ 观测为 $o_1,o_2,...,o_t$ 并在时刻 $t+1$ 处于状态 $q_i$ 的联合概率。方括弧里的值与观测概率 $b_i (o_{t+1})$ 的乘积恰好是到时刻 $t+1$ 观测到 $o_1,o_2,...,o_t,o_{t+1}$ 并在时刻 $t+1$ 处于状态 $q_i$ 的前向概率 $\alpha_{t+1}(i)$。步骤（3）给出 $P (O\mid \lambda)$ 的计算公式。因为

$$ \alpha_T(i)=P(o_1,o_2,...,o_T,i_T=q_i\mid \lambda) $$

所以

$$ P(O\mid \lambda)=\sum_{i=1}^N\alpha_T(i) $$

举个例子，考虑盒子和球的模型 $\lambda=(A,B,\pi)$，状态集合 $Q=\{1,2,3\}$，观测集合 $V=\{红，白 \}$

$$ A = \begin{bmatrix} {0.5}&{0.2}&{0.3}\\ {0.3}&{0.5}&{0.2}\\ {0.2}&{0.3}&{0.5}\\ \end{bmatrix},\ \ \ \ B= \begin{bmatrix} {0.5}&{0.5}\\ {0.4}&{0.6}\\ {0.7}&{0.3} \end{bmatrix},\ \ \ \ \pi= \begin{bmatrix} {0.2}\\ {0.4}\\ {0.4} \end{bmatrix} $$

设 $T=3,O=(红，白，红)$，试用前向算法计算 $P (O\mid \lambda)$

解：按照前向算法

（1）计算初值

$$ \alpha_1(1)=\pi_1 b_1(o_1)=0.10\\ \alpha_1(2)=\pi_2 b_2(o_1)=0.16\\ \alpha_1(3)=\pi_3b_3(o_1)=0.28 $$

（2）递推计算

$$ \begin{align*} &\alpha_2(1)=\bigg [\sum_{i=1}^3\alpha_1(i)a_{i1}\bigg ]b_1(o_2)=0.154\times 0.5=0.077\\ &\alpha_2(2)=\bigg [\sum_{i=1}^3\alpha_1(i)a_{i2}\bigg ]b_2(o_2)=0.184\times 0.6=0.1104\\ &\alpha_2(3)=\bigg [\sum_{i=1}^3\alpha_1(i)a_{i3}\bigg ]b_3(o_2)=0.202\times 0.3=0.0606\\ &\alpha_3(1)=\bigg [\sum_{i=2}^3\alpha_1(i)a_{i3}\bigg ]b_1(o_3)=0.04187\\ &\alpha_3(2)=\bigg [\sum_{i=2}^3\alpha_1(i)a_{i3}\bigg ]b_2(o_3)=0.03551\\ &\alpha_3(3)=\bigg [\sum_{i=2}^3\alpha_1(i)a_{i3}\bigg ]b_3(o_3)=0.05284\\ \end{align*} $$

（3）终止

$$ P(O\mid \lambda)=\sum_{i=1}^3\alpha_3(i)=0.13022 $$

3. 后向算法

给定隐马尔可夫模型 $\lambda$，定义时刻 $t$ 状态为 $q_i$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的概率为后向概率，记作

$$ \beta_t(i)=P(o_{t+1},o_{t+2},...,o_T\mid i_t=q_i,\lambda) $$

可以用递推的方法求得后向概率 $\beta_t (i)$ 即观测序列概率 $P (O\mid \lambda)$

输入：隐马尔可夫模型 $\lambda$，观测序列 $O$

输出：观测序列概率 $P (O\mid \lambda)$

（1）

$$ \beta_t(i)=1, \ \ i=1,2,...,N $$

（2）对 $t=T-1,T-2,...,1$

$$ \beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ i=1,2,...,N $$

（3）

$$ P(O\mid \lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i) $$

步骤（1）初始化后向概率，对最终时刻的所有状态 $q_i$ 规定 $\beta_t (i)=1$。步骤（2）是后向概率的递推公式。如下图所示

为了计算在时刻 $t$ 状态为 $q_i$ 条件下时刻 $t+1$ 之后的观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的后向概率 $\beta_t (i)$，只需要考虑在时刻 $t+1$ 所有可能的 $N$ 个状态 $q_j$ 的转移概率（即 $a_{ij}$ 项），以及在此状态下的观测 $o_{t+1}$ 的观测概率（即 $b_j (o_{t+1})$ 项），然后考虑状态 $q_j$ 之后的观测序列的后向概率（即 $\beta_{t+1}(j)$ 项）。步骤（3）求 $P (O\mid \lambda)$ 得思路与步骤（2）一致，只是初始概率 $\pi_i$ 代替转移概率

利用前向概率和后向概率的定义可以将观测序列概率 $P (O\mid \lambda)$ 统一写成

$$ P(O\mid \lambda)=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ t = 1,2,...,T-1 $$