简介

「马尔可夫模型」是指基于马尔可夫性质的模型，其假设一个给定过程的未来状态仅取决于当前状态。根据系统状态是否完全可被观测以及系统是自动的还是受控的，可以将常见的马尔可夫模型分成四种：马尔可夫链、隐马尔可夫模型（HMM）、马尔可夫决策过程（MDP）和部分可观测马尔可夫决策过程（POMDP）。另外还有马尔可夫随机场（MRF）和马尔可夫链蒙特卡洛（MCMC）这两个模型也常常被用于近似和预测。

分类	系统状态完全可被观测	系统状态不是完全可被观测
系统是自动的	马尔可夫链	隐马尔可夫模型
系统是受控的	马尔可夫决策过程	部分可观测马尔可夫决策过程

最简单的马尔可夫模型是马尔可夫链。它用一个随时间变化的随机变量来模拟系统的状态。在这种情况下，马尔可夫性质表明，这个变量的分布只取决于之前状态的分布。

当马尔可夫链的状态只能部分观察到，这就是隐马尔可夫模型。隐马尔可夫模型常用的用途是语音识别，它是大多数现代自动语音识别系统的基础。

马尔可夫决策过程也是马尔可夫链，但其状态转换取决于当前状态和应用于系统的动作向量。通常，使用马尔可夫决策过程来计算行动策略，该行为策略将最大限度地提高与预期奖励相关的某种效用。它与强化学习密切相关，可以用价值迭代法和相关方法解决。

部分可观测马尔可夫决策过程是一个系统的状态只被部分观察到的马尔可夫决策过程，其中系统的状态只被部分观察到。部分可观测马尔可夫决策过程可以用于控制简单代理或机器人。

马尔可夫模型还包括马尔可夫随机场（MRF）和马尔可夫链蒙特卡洛（MCMC）。这两个模型也常常被用于近似和预测 Tolerant Markov model (TMM)、层级马尔科夫模型（Hierarchical Markov models）、层级隐马尔可夫模型(hierarchicalhiddenMarkov model)。

马尔可夫链

马尔可夫链，又称离散时间马尔可夫链，因俄国数学家安德烈·马尔可夫得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

马尔可夫链是一个随机系统，它必须满足两个条件：

系统任意时刻可以用有限个可能状态之一来描述
系统无后效性，即某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响

数学表达

状态向量

X^{(n)}=(x_1^{(n)},x_2^{(n)},…,x_k^{(n)})

概率向量的每个元素都是概率，并且元素之和为1。
系统的可能状态数有k个。
向量中各个元素分别表示表示第n次观测时第i个状态的概率。
$X^{(0)}$ 被称为初始状态。

概率转移矩阵

P=\begin{pmatrix} p_{11}&p_{12}&…&p_{1k}\\ p_{21}&p_{22}&…&p_{2k}\\ .&.&&.\\ .&.&&.\\ .&.&&.\\ p_{k1}&p_{k2}&…&p_{kk}\\ \end{pmatrix} \tag{1}

$p_{ij}(i,j=1,2,…,k)$ 表示这次观测前状态为i,现在观测是状态为j的概率
P矩阵元素非负
每一行的元素之和都为1

根据无后效性，可以得到：

X^{(n+1)}=X^{(n)}P

从而： $X^{(n+1)}=X^{(0)}P^n$

由于某一时刻状态转移的情况只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，这个马尔科夫链的模型就确定了。

举例

有一个大的汽车租赁公司，有三家门店，你租的时候可以选择任何一个门店，还的时候也可以选择任何一家门店，从不同门店借出和归还的概率如下：

	1	2	3
借出
1	0.5	0.2	0.3
2	0.3	0.1	0.6
3	0.3	0.6	0.1

可以写出转移矩阵为：

\begin{pmatrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.1 & 0.6 \\ 0.3 & 0.6 & 0.1 \end{pmatrix} \tag{2}

如果在已知一辆车位于2号门店，三次借还以后，这辆车最可能在哪个门店呢？基于转移矩阵我们可以求解如下：

设置初始状态向量为： $X^{(0)}=(0,1,0)$

可以快速求出：

X^{(1)}=X^{(0)}P=(0.3,0.1,0.6)\\ X^{(2)}=X^{(1)}P=(0.36,0.43,0.21)\\ X^{(3)}=X^{(2)}P=(0.372,0.241,0.387)\\

故三次借还后这辆车最可能在三号门店。

如果进行n次借还车之后，且n趋向于无穷大时，此时结果是否能够收敛。代码验证如下：

import numpy as np




def markov():
    init_array = np.array([0, 1, 0])
    transfer_matrix = np.array([[0.5, 0.2, 0.3],
                                [0.3, 0.1, 0.6],
                                [0.3, 0.6, 0.1]])
    rtmp = init_array
    for i in range(15):
        res = np.dot(rtmp, transfer_matrix)
        print(i+1, "\t", res)
        rtmp = res



markov()

输出结果如下：

1 	 [0.3 0.1 0.6]
2 	 [0.36 0.43 0.21]
3 	 [0.372 0.241 0.387]
4 	 [0.3744 0.3307 0.2949]
5 	 [0.37488 0.28489 0.34023]
6 	 [0.374976 0.307603 0.317421]
7 	 [0.3749952 0.2962081 0.3287967]
8 	 [0.37499904 0.30189787 0.32310309]
9 	 [0.37499981 0.29905145 0.32594874]
10 	 [0.37499996 0.30047435 0.32452569]
11 	 [0.37499999 0.29976284 0.32523717]
12 	 [0.375      0.30011858 0.32488142]
13 	 [0.375      0.29994071 0.32505929]
14 	 [0.375      0.30002965 0.32497035]
15 	 [0.375      0.29998518 0.32501482]

可以发现，当n -> 无穷大时，状态向量趋近于：

X^{(n)}=(0.375, 0.3, 0.325)

如果转移矩阵经过n次幂后，此时转移矩阵是否能够收敛。代码验证如下：

import numpy as np




def matrixPower():
    transfer_matrix = np.array([[0.5, 0.2, 0.3],
                                [0.3, 0.1, 0.6],
                                [0.3, 0.6, 0.1]])
    rtmp = transfer_matrix
    for i in range(15):
        res = np.dot(rtmp, transfer_matrix)
        print(i+1, "\t", res)
        rtmp = res



matrixPower()

输出结果如下：

1 	 [[0.4  0.3  0.3 ]
 [0.36 0.43 0.21]
 [0.36 0.18 0.46]]
2 	 [[0.38  0.29  0.33 ]
 [0.372 0.241 0.387]
 [0.372 0.366 0.262]]
3 	 [[0.376  0.303  0.321 ]
 [0.3744 0.3307 0.2949]
 [0.3744 0.2682 0.3574]]
4 	 [[0.3752  0.2981  0.3267 ]
 [0.37488 0.28489 0.34023]
 [0.37488 0.31614 0.30898]]
5 	 [[0.37504  0.30087  0.32409 ]
 [0.374976 0.307603 0.317421]
 [0.374976 0.291978 0.333046]]
6 	 [[0.375008  0.299549  0.325443 ]
 [0.3749952 0.2962081 0.3287967]
 [0.3749952 0.3040206 0.3209842]]
7 	 [[0.3750016  0.3002223  0.3247761 ]
 [0.37499904 0.30189787 0.32310309]
 [0.37499904 0.29799162 0.32700934]]
8 	 [[0.37500032 0.29988821 0.32511147]
 [0.37499981 0.29905145 0.32594874]
 [0.37499981 0.30100457 0.32399562]]
9 	 [[0.37500006 0.30005577 0.32494417]
 [0.37499996 0.30047435 0.32452569]
 [0.37499996 0.29949779 0.32550225]]
10 	 [[0.37500001 0.29997209 0.3250279 ]
 [0.37499999 0.29976284 0.32523717]
 [0.37499999 0.30025112 0.32474889]]
11 	 [[0.375      0.30001395 0.32498605]
 [0.375      0.30011858 0.32488142]
 [0.375      0.29987444 0.32512556]]
12 	 [[0.375      0.29999302 0.32500698]
 [0.375      0.29994071 0.32505929]
 [0.375      0.30006278 0.32493722]]
13 	 [[0.375      0.30000349 0.32499651]
 [0.375      0.30002965 0.32497035]
 [0.375      0.29996861 0.32503139]]
14 	 [[0.375      0.29999826 0.32500174]
 [0.375      0.29998518 0.32501482]
 [0.375      0.30001569 0.32498431]]
15 	 [[0.375      0.30000087 0.32499913]
 [0.375      0.30000741 0.32499259]
 [0.375      0.29999215 0.32500785]]

同样发现转移矩阵趋向于：

\begin{pmatrix} 0.375 & 0.3 & 0.325 \\ 0.375 & 0.3 & 0.325 \\ 0.375 & 0.3 & 0.325 \end{pmatrix} \tag{3}

结论

马尔科夫链要能收敛，需要满足以下必要条件：

可能的状态数有限。
状态间的转移概率固定不变。
能从任意状态转变到任意状态。
不能是简单的循环，例如从x到y再从y到x。

转移矩阵要满足细致平衡条件，给定一个马尔可夫链，分布π和概率转移矩阵P，如果下面等式成立:

π_{i}P_{ij}=π_{j}P_{ji}

则此马尔可夫链具有一个平稳分布。

隐马尔可夫模型（HMM）

隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如语言识别，自然语言处理，模式识别。

什么样的问题需要HMM模型

使用HMM模型时我们的问题一般有这两个特征：

１）我们的问题是基于序列的，比如时间序列，或者状态序列。

２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：

我现在在打字写博客，我在键盘上敲出来的一系列字符就是观测序列，而我实际想写的一段话就是隐藏序列，输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话，并把最可能的词语放在最前面让我选择，这就可以看做一个HMM模型了。
再举一个，我在和你说话，我发出的一串连续的声音就是观测序列，而我实际要表达的一段话就是状态序列，你大脑的任务，就是从这一串连续的声音中判断出我最可能要表达的话的内容。

HMM模型的定义

对于HMM模型，首先我们假设Q是所有可能的隐藏状态的集合，V是所有可能的观测状态的集合，即：

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

其中，N是可能的隐藏状态数，M是所有的可能的观察状态数。

对于一个长度为 T 的序列， I 对应的状态序列, O 是对应的观察序列，即：

I=\{i_1,i_2,…,i_T\},O=\{o_1,o_2,…,o_T\} \\ i_t\in Q, o_t\in V

HMM模型两个很重要的假设如下：

齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态。当然这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者是前三个。但是这样假设的好处就是模型简单，便于求解。如果在时刻 t 的隐藏状态是 $i_t=q_i$ ，在时刻 t+1 的隐藏状态是 $i_{t+1}=q_j$ ，则从时刻 t 到时刻 t+1 的HMM状态转移概率 $a_{ij}$ 可以表示为：

a_{ij}=P(i_{t+1}=q_j|i_t=q_i)

这样 $a_{ij}$ 可以组成马尔科夫链的状态转移矩阵A:

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

观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。如果在时刻 t 的隐藏状态是 $i_t=q_j$ ，而对应的观察状态为 $o_t=v_k$ ，则该时刻观察状态 $v_k$ 在隐藏状态 $q_j$ 下生成的概率 $b_j(k)$ 满足：

b_j(k)=P(o_t=v_k|i_t=q_j)

基于 $b_j(k)$ 可以组成观测状态生成的概率矩阵B:

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

除此之外，我们需要一组在时刻 t=1 的隐藏状态概率分布 $\Pi$ ：

\Pi=[\pi(i)]_{N}\\ \pi(i)=P(i_1=q_i)

一个HMM模型，可以由隐藏状态初始概率分布 $\Pi$ ，状态转移概率矩阵 A 和观测状态概率矩阵 B 决定。 $\Pi$ , A 决定状态序列， B 决定观测序列。因此，HMM模型可以由一个三元组 λ 表示如下： $λ=(A,B,\Pi)$

马尔可夫决策过程（MDP）

强化学习任务通常使用马尔可夫决策过程（Markov Decision Process，简称MDP）来描述，具体而言：机器处在一个环境中，每个状态为机器对当前环境的感知；机器只能通过动作来影响环境，当机器执行一个动作后，会使得环境按某种概率转移到另一个状态；同时，环境会根据潜在的奖赏函数反馈给机器一个奖赏。综合而言，强化学习主要包含四个要素：状态、动作、转移概率以及奖赏函数。

根据上图，agent（智能体）在进行某个任务时，首先与environment进行交互，产生新的状态state，同时环境给出奖励reward，如此循环下去，agent和environment不断交互产生更多新的数据。强化学习算法就是通过一系列动作策略与环境交互，产生新的数据，再利用新的数据去修改自身的动作策略，经过数次迭代后，agent就会学习到完成任务所需要的动作策略。

# 强化学习 — 马尔可夫决策过程（MDP）