马尔可夫链

前言

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

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

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

一句话描述：状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备**“无记忆”的性质：下一状态的概率分布只能由当前状态决定**，在时间序列中它前面的事件均与之无关。

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

1. 随机过程是啥玩意儿

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

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

讲马尔可夫链不得不提到随机过程，因为它是随机过程课本中的，啊啊。

顾名思义，它其实就是个过程，比如今天下雨，那么明天下不下雨呢？后天下不下雨呢？从今天下雨到明天不下雨再到后天下雨，这就是个过程。那么怎么预测N天后到底下不下雨呢？这其实是可以利用公式进行计算的，随机过程就是这样一个工具，把整个过程进行量化处理，用公式就可以推导出来N天后的天气状况，下雨的概率是多少，不下雨的概率是多少。说白了，随机过程就是一些统计模型，利用这些统计模型可以对自然界的一些事物进行预测和处理，比如天气预报，比如股票，比如市场分析，比如人工智能。它的应用还真是多了去了。

话说回来，还真是佩服能构造出这些统计模型的大牛，简直脑洞大开啊。

2. 马尔可夫链（Markov Chain）又是什么鬼

好了，终于可以来看看马尔可夫链（Markov Chain）到底是什么了。

它是随机过程中的一种过程，到底是哪一种过程呢？好像一两句话也说不清楚，还是先看个例子吧。

先说说我们村智商为0的王二狗，人傻不拉几的，见人就傻笑，每天中午12点的标配，仨状态：吃，玩，睡。这就是传说中的状态分布。

你想知道他n天后中午12点的状态么？是在吃，还是在玩，还是在睡？这些状态发生的概率分别都是多少？（知道你不想，就假装想知道吧~~学习真的好累~~）

先看个假设，他每个状态的转移都是有概率的，比如今天玩，明天睡的概率是几，今天玩，明天也玩的概率是几几，看图更清楚一点。

这个矩阵就是转移概率矩阵P，并且它是保持不变的，就是说第一天到第二天的转移概率矩阵跟第二天到第三天的转移概率矩阵是一样的。（这个叫时齐，不细说了，有兴趣的同学自行百度）。

有了这个矩阵，再加上已知的第一天的状态分布，就可以计算出第N天的状态分布了。

S1 是4月1号中午12点的的状态分布矩阵 [0.6, 0.2, 0.2]，里面的数字分别代表吃的概率，玩的概率，睡的概率。

那么

4月2号的状态分布矩阵 S2 = S1 * P (俩矩阵相乘)。

4月3号的状态分布矩阵 S3 = S2 * P (看见没，跟S1无关，只跟S2有关)。

4月4号的状态分布矩阵 S4 = S3 * P (看见没，跟S1，S2无关，只跟S3有关)。

…

4月n号的状态分布矩阵 Sn = Sn-1 * P (看见没，只跟它前面一个状态Sn-1有关)。

总结：马尔可夫链就是这样一个任性的过程，它将来的状态分布只取决于现在，跟过去无关！

就把下面这幅图想象成是一个马尔可夫链吧。实际上就是一个随机变量随时间按照Markov性进行变化的过程。

作者：Suprit

链接：https://zhuanlan.zhihu.com/p/448575579

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

马尔科夫链

简介

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

马尔科夫链认为过去所有的信息都被保存在了现在的状态下了 。比如这样一串数列 1 - 2 - 3 - 4 - 5 - 6，在马尔科夫链看来，6 的状态只与 5 有关，与前面的其它过程无关。

数学定义

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

P(Xt+1∣…Xt−2,Xt−1,Xt)=P(Xt+1∣Xt) P\left(X_{t+1} \mid \ldots X_{t-2}, X_{t-1}, X_{t}\right)=P\left(X_{t+1} \mid X_{t}\right)\

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

转移概率矩阵

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

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

初始状态在 A，如果我们求 2 次运动后状态还在 A 的概率是多少？非常简单：
P=A→A→A+A→B→A=0.3∗0.3+0.7∗0.9=0.72 P = A→A→A + A→B→A = 0.3 * 0.3 + 0.7 * 0.9 = 0.72\
如果求 2 次运动后的状态概率分别是多少？初始状态和终止状态未知时怎么办呢？这是就要引入转移概率矩阵 ，可以非常直观的描述所有的概率。

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

- 初始状态 A，2 次运动后状态为 A 的概率是 0.72；
- 初始状态 A，2 次运动后状态为 B 的概率是 0.28；
- 初始状态 B，2 次运动后状态为 A 的概率是 0.36；
- 初始状态 B，2 次运动后状态为 B 的概率是 0.64；
有了概率矩阵，即便求运动 n 次后的各种概率，也能非常方便求出。

来看一个多个状态更复杂的情况：

状态转移矩阵的稳定性

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

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

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('Courrent round: {}'.format(i+1))
    print(vector1)

输出结果：

Current round: 1
[[ 0.405   0.4175  0.1775]]
Current round: 2
[[ 0.4715   0.40875  0.11975]]
Current round: 3
[[ 0.5156  0.3923  0.0921]]
Current round: 4
[[ 0.54591   0.375535  0.078555]]
。。。。。。
Current round: 58
[[ 0.62499999  0.31250001  0.0625    ]]
Current round: 59
[[ 0.62499999  0.3125      0.0625    ]]
Current round: 60
[[ 0.625   0.3125  0.0625]]
。。。。。。
Current round: 99
[[ 0.625   0.3125  0.0625]]
Current round: 100
[[ 0.625   0.3125  0.0625]]