5分钟理解NPL算法 之 马尔可夫链 Markov Chain

马尔可夫链（Markov Chain）

马尔可夫链是一种简单的推理模型。用于描述受当前事件影响下的下一事件发生概率。在预测学科中广泛应用。例如股票预测、文字推理、路线推荐等。

他的核心思路是：假设事件顺序为: $X_1,X_2,X_3,.....$
那么马尔可夫链认为，$X_2的值只与X_1的值有关，同样，X_3的值也只与X_2的值有关$

举个栗子

假设你正在策划旅游路线，当然是希望旅游地点之间是相近的且有序的，所以你的第一站目的地会理所应当的会直接影响第二站的选择。以北京和深圳为例：

以矩阵方式描述就显得更直观些：
$$下一站概率=P=\left[\begin{array}{ccc}& 北京& 深圳\\ 北京& 0.2& 0.3\\ 深圳& 0.7& 0.5\end{array}\right]$$
如上所示，如果你现在身在北京，下一站为深圳的概率是0.3，继续停留在北京的概率是0.2，
如果当前身在深圳，下一站去北京的概率是0.7，继续停留在深圳的概率是0.5

那如果我想知道，已经在两地辗转移动两次后的下一站概率怎么办呢？
只需要将前后的关系矩阵相乘：

$$移动2次后的下一站概率=P=\left[\begin{array}{ccc}& 北京& 深圳\\ 北京& 0.2& 0.3\\ 深圳& 0.7& 0.5\end{array}\right]\left[\begin{array}{ccc}& 北京& 深圳\\ 北京& 0.2& 0.3\\ 深圳& 0.7& 0.5\end{array}\right]$$

$$=\left[\begin{array}{ccc}& 北京& 深圳\\ 北京& 0.2\ast 0.2+0.3\ast 0.7& 0.2\ast 0.3+0.3\ast 0.5\\ 深圳& 0.7\ast 0.2+0.5\ast 0.7& 0.7\ast 0.3+0.5\ast 0.5\end{array}\right]$$
$$=\left[\begin{array}{ccc}& 北京& 深圳\\ 北京& 0.25& 0.21\\ 深圳& 0.49& 0.46\end{array}\right]$$
结论：在两地移动2次后，如果当前在北京，继续留在北京的概率是0.25，去深圳的概率是0.21.
如果当前在深圳，继续留在深圳的概率是0.46，去北京的概率是0.49

结论

由此可以推断马尔可夫链的三个主要特征是：

1. 状态空间：选择范围是有限集
2. 无记忆性：预测仅与上一状态相关联
3. 转移矩阵：通过矩阵相乘可计算出概率