前言

马尔可夫链（Markov Chain）可以说是机器学习和人工智能的基石，在强化学习、自然语言处理、金融领域、天气预测、语音识别方面都有着极其广泛的应用

The future is independent of the past given the present
未来独立于过去，只基于当下。

这句人生哲理的话也代表了马尔科夫链的思想：过去所有的信息都已经被保存到了现在的状态，基于现在就可以预测未来。

虽然这么说可能有些极端，但是却可以大大简化模型的复杂度，因此马尔可夫链在很多时间序列模型中得到广泛的应用，比如循环神经网络 RNN，隐式马尔可夫模型 HMM 等，当然 MCMC 也需要它。

随机过程

马尔可夫链是随机过程这门课程中的一部分，先来简单了解一下。

简单来说，随机过程就是使用统计模型一些事物的过程进行预测和处理，比如股价预测通过今天股票的涨跌，却预测明天后天股票的涨跌；天气预报通过今天是否下雨，预测明天后天是否下雨。这些过程都是可以通过数学公式进行量化计算的。通过下雨、股票涨跌的概率，用公式就可以推导出来 N 天后的状况。

俄国数学家 Andrey Andreyevich Markov 研究并提出一个用数学方法就能解释自然变化的一般规律模型，被命名为马尔科夫链（Markov Chain）。马尔科夫链为状态空间中经过从一个状态到另一个状态的转换的随机过程，该过程要求具备“无记忆性”，即下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

数学定义

假设我们的序列状态是 $...X_{t−2}, X_{t−1}, X_t, X_{t+1}...$，那么在 $X_{t+1}$ 时刻的状态的条件概率仅依赖于前一刻的状态 $X_t$，即：

$$ P(X_{t+1} \mid \ldots X_{t−2}, X_{t−1}, X_t) = P(X_{t+1} \mid X_t) $$

既然某一时刻状态转移的概率只依赖于它的前一个状态，那么我们只要能求出系统中任意两个状态之间的转换概率，这个马尔科夫链的模型就定了。

转移概率矩阵

通过马尔科夫链的模型转换，我们可以将事件的状态转换成概率矩阵（又称状态分布矩阵），如下例：

上图中有 $A$ 和 $B$ 两个状态，$A$ 到 $A$ 的概率是 $0.3$，$A$ 到 $B$ 的概率是 $0.7$；$B$ 到 $B$ 的概率是 $0.1$，$B$ 到 $A$ 的概率是 $0.9$。

  • 初始状态在 $A$，如果我们求 2 次运动后状态还在 $A$ 的概率是多少？非常简单：
    $P = A \rightarrow A \rightarrow A + A \rightarrow B \rightarrow A = 0.3 \times 0.3 + 0.7 \times 0.9 = 0.72$
  • 如果求 2 次运动后的状态概率分别是多少？初始状态和终止状态未知时怎么办呢？这时就要引入转移概率矩阵，可以非常直观的描述所有的概率。
$$\begin{aligned} P &= \begin{bmatrix} & A & B \\ A & 0.3 & 0.7 \\ B & 0.9 & 0.1 \end{bmatrix}, \\ & \text{两次运动后:} \\ P &= \begin{bmatrix} & A & B \\ A & 0.3 & 0.7 \\ B & 0.9 & 0.1 \end{bmatrix} \begin{bmatrix} & A & B \\ A & 0.3 & 0.7 \\ B & 0.9 & 0.1 \end{bmatrix} \\ &= \begin{bmatrix} & A & B \\ A & 0.72 & 0.28 \\ B & 0.36 & 0.64 \end{bmatrix} \end{aligned}$$

有了状态矩阵，我们可以轻松得出以下结论：

  • 初始状态 $A$，$2$ 次运动后状态为 $A$ 的概率是 $0.72$；
  • 初始状态 $A$，$2$ 次运动后状态为 $B$ 的概率是 $0.28$；
  • 初始状态 $B$，$2$ 次运动后状态为 $A$ 的概率是 $0.36$；
  • 初始状态 $B$，$2$ 次运动后状态为 $B$ 的概率是 $0.64$；

状态转移矩阵的稳定性

状态转移矩阵有一个非常重要的特性，经过一定有限次数序列的转换，最终一定可以得到一个稳定的概率分布，且与初始状态概率分布无关。例如：

假设我们当前股市的概率分布为：$[0.3，0.4, 0.3]$，即 $30\%$ 概率的牛市，$40\%$ 概率的熊盘与 $30\%$ 的横盘。然后这个状态作为序列概率分布的初始状态 $t_0$，将其带入这个状态转移矩阵计算 $t_1, t_2, t_3, \dots$ 的状态。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import numpy as np

matrix = np.matrix([[0.9, 0.075, 0.025],
                    [0.15, 0.8, 0.05],
                    [0.25, 0.25, 0.5]], dtype=float)
vector1 = np.matrix([[0.3, 0.4, 0.3]], dtype=float)

for i in range(100):
    vector1 = vector1 * matrix
    print('Current round: {}'.format(i+1))
    print(vector1)

部分输出结果如下：

1
2
3
4
5
6
7
8

Current round: 1
[[ 0.405   0.4175  0.1775]]
...
Current round: 60
[[ 0.625   0.3125  0.0625]]
...
Current round: 100
[[ 0.625   0.3125  0.0625]]

可以发现，从第 60 轮开始，我们的状态概率分布就不变了，一直保持 $[0.625, 0.3125, 0.0625]$，即 $62.5\%$ 的牛市，$31.25\%$ 的熊市与 $6.25\%$ 的横盘。

非马尔科夫链过程的例子

只有满足马尔科夫链的特性，才属于马尔科夫链过程。例如对于不放回的袋中取球问题：

显然当前取球的概率，不仅和最后一次取的球的颜色有关，也和之前每一次取球的颜色有关，所以这个过程不是一个马尔科夫链过程。

如果是放回的袋中取球问题，这就建立了一个马尔科夫随机过程。

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

盒子摸球实验

假定我们有三个完全相同的盒子 $box$，每个 $box$ 中装有一些球，分布如下：

  1. $box_1: 3\ \text{black},\ 8\ \text{white}$
  2. $box_2: 6\ \text{black},\ 4\ \text{white}$
  3. $box_3: 4\ \text{black},\ 6\ \text{white}$

实验过程如下：

  1. 随机取一个 $box_i$
  2. 从取出的 $box_i$ 中拿出一个球
  3. 记录球的颜色并放回（古典概型）

可以看出，每次过程中只有取出的球的颜色是可以观察的，但是取出的 $box$ 的编号是无法被观察的。

所以整个盒子摸球实验中关系如下：

这幅图能够很好的说明隐马尔科夫模型当中的两个核心关键词：一个关键词是隐，指的就是状态序列，也就是盒子序列，它是我们无法观测得知的，是隐含的；另一个关键词是马尔科夫，指的是整个隐含状态序列，隐含状态之间的转换是一个马尔科夫过程，隐含状态之间是有特定的转换概率的。

参考