【机器学习】马尔可夫链 ▏小白都能看懂的马尔可夫链详解

共 2214字,需浏览 5分钟

 ·

2023-03-11 06:51



1.什么是马尔可夫链



在机器学习算法中,马尔可夫链(Markov chain)是个很重要的概念。马尔可夫链(Markov chain),又称离散时间马尔可夫链(discrete-time Markov chain),因俄国数学家安德烈·马尔可夫(俄语:Андрей Андреевич Марков)得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。


在马尔可夫链的每一步,系统根据概率分布,可以从一个状态变到另一个状态,也可以保持当前状态。状态的改变叫做转移,与不同的状态改变相关的概率叫做转移概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点,每一步可以移动到任何一个相邻的点,在这里移动到每一个点的概率都是相同的(无论之前漫步路径是如何的)。



2.一个经典的马尔科夫链实例



用一句话来概括马尔科夫链的话,那就是某一时刻状态转移的概率只依赖于它的前一个状态。


举个简单的例子,假如每天的天气是一个状态的话,那个今天是不是晴天只依赖于昨天的天气,而和前天的天气没有任何关系。


这么说可能有些不严谨,但是这样做可以大大简化模型的复杂度,因此马尔科夫链在很多时间序列模型中得到广泛的应用,比如循环神经网络RNN,隐式马尔科夫模型HMM等。


假设状态序列为

由马尔科夫链定义可知,

时刻Xt+1 的状态只与Xt 有关,用数学公式来描述就是:


既然某一时刻状态转移的概率只依赖前一个状态,那么只要求出系统中任意两个状态之间的转移概率,这个马尔科夫链的模型就定了。看一个具体的例子。


这个马尔科夫链是表示股市模型的,共有三种状态:牛市(Bull market), 熊市(Bear market)和横盘(Stagnant market)。


每一个状态都以一定的概率转化到下一个状态。比如,牛市以0.025的概率转化到横盘的状态。这个状态概率转化图可以以矩阵的形式表示。如果我们定义矩阵阵P某一位置P(i, j)的值为P(j|i),即从状态i变为状态j的概率。另外定义牛市、熊市、横盘的状态分别为0、1、2,这样我们得到了马尔科夫链模型的状态转移矩阵为:



当这个状态转移矩阵P确定以后,整个股市模型就已经确定!



3.状态转移矩阵



从上面的例子不难看出来,整个马尔可夫链模型的核心是状态转移矩阵P。那这个矩阵P有一些什么有意思的地方呢?接下来再看一下。


以股市模型为例,假设初始状态为t0=[0.1,0.2,0.7] ,然后算之后的状态。

最终输出结果为

从第18次开始,状态就开始收敛至[0.624,0.312,0.0625] 。最终数字上略有不同,只是计算机浮点数运算造成的罢了。


如果我们换一个初始状态t0 ,比如[0.2,0.3.0.5] 继续运行上面的代码,只是将init_array变一下,最后结果为:

到第18次的时候,

又收敛到了[0.624,0.312,0.0625] 


这个转移矩阵就厉害了。不管我们的初始状态是什么样子的,只要状态转移矩阵不发生变化,当n→∞ 时,最终状态始终会收敛到一个固定值。


在矩阵分析,自动控制原理等过程中,经常会提到矩阵的幂次方的性质。我们也看看这个状态转移矩阵P的幂次方有什么有意思的地方?直接上代码。

代码运行结果为


从第20次开始,结果开始收敛,并且每一行都为[0.625,0.312,0.0625] 。



4.马尔可夫链细致平稳条件



首先,马尔科夫链要能收敛,需要满足以下条件:


1.可能的状态数是有限的。

2.状态间的转移概率需要固定不变。

3.从任意状态能够转变到任意状态。

4.不能是简单的循环,例如全是从x到y再从y到x。


以上是马尔可夫链收敛的必要条件。


假设有一个概率的单纯形向量

有一个概率转移矩阵P PP,例如我们前面的例子:

其中,v0 每个元素的取值范围为[0,1],并且所有元素的和为1。而P 的每一行也是个概率单纯形向量。


由前面的例子我们不难看出,当v0 与P 的n次幂相乘以后,发现得到的向量都会收敛到一个稳定值,而且此稳定值与初始向量v0 无关!


那么所有的转移矩阵P 都有这种现象嘛?或者说满足什么样的条件的转移矩阵P会有这种现象?


细致平衡条件(Detailed Balance Condition):给定一个马尔科夫链,分布π和概率转移矩阵P,如果下面等式成立:

则此马尔科夫链具有一个平稳分布(Stationary Distribution)。

证明过程比较简单:

上式取j→∞ ,就可以得到矩阵表达式:



5.马尔可夫链收敛性质



如果一个非周期的马尔可夫链收敛,有状态转移矩阵P,并且任何两个状态都是连通的,那么

π是方程πP=π 的唯一非负解,其中:



  END  


文章来源:CSDN博主「bitcarmanlee」

原文链接:https://blog.csdn.net/bitcarmanlee/java/article/details/82819860

往期精彩回顾





浏览 77
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报