马尔科夫链(Markov Chain)
说到马尔可夫链,在机器学习界真是无人不知,无人不晓。谷歌用于确定搜索结果顺序的算法,称为PageRank,就是一种马尔可夫链。在卷积网络出现之前,HMM马尔可夫模型也是语音处理的常用方法。到底什么才是马尔可夫链,之前看了几个介绍特别生动,这里总结一下:
马尔科夫链是指数学中具有马尔科夫性质的离散事件随机过程。在其每一步中,系统根据概率分布可以从一个状态变到另一个状态,也可以保持当前状态。状态的改变叫做转移,与不同的状态改变相关的概率叫做转移概率。
下图中有两种状态:A和B。如果我们在A,接下来可以过渡到B或留在A。如果我们在B,可以过渡到A或者留在B。在这张图中,从任意状态到任意状态的转移概率是0.5。
真正的建模工作者不会总是就画一张马尔科夫链图。 相反,他们会使用“转移矩阵”来计算转移概率。状态空间中的每个状态都会出现在表格中的一列或者一行中。矩阵中的每个单元格都告诉你从行状态转换到列状态的概率。因此,在矩阵中,单元格做的工作和图中的箭头所示是一样。在状态转移矩阵中,行和列都是可能的所有状态,对应位置就是已知行状态,转移到列状态的概率。
如果状态空间添加了一个状态,我们将添加一行和一列,向每个现有的列和行添加一个单元格。 这意味着当我们向马尔可夫链添加状态时,单元格的数量会呈二次方增长。因此,转换矩阵就起到了很大的作用(除非你想把法尔科夫链图画的跟丛林一样)。
从上面可以看出,整个马尔可夫链中的核心就是状态转移矩阵。以股市模型为例,假设初始状态为,然后算之后的状态。
输出结果:
从第18次开始,状态就开始收敛至。 如果我们换一个初始状态,比如,继续运行上面的代码,只是将init_array变一下,最后结果为:
到第18次的时候,又收敛到了!这个转移矩阵就厉害了。不管我们的初始状态是什么样子的,只要状态转移矩阵不发生变化,当时,最终状态始终会收敛到一个固定值。
首先,马尔科夫链要能收敛,需要满足以下条件:
由前面的例子我们不难看出,当与的n次幂相乘以后,发现得到的向量都会收敛到一个稳定值,而且此稳定值与初始向量 无关!那么所有的转移矩阵都有这种现象嘛?或者说满足什么样的条件的转移矩阵会有这种现象?
细致平衡条件(Detailed Balance Condition):给定一个马尔科夫链,分布 和概率转移矩阵,如果下面等式成立:
