侧边栏壁纸
    • 累计撰写 207 篇文章
    • 累计收到 466 条评论
    马尔科夫链讲解(Markov)
    2021-03-18 / 0 评论 / 66 阅读 / 1 点赞

    马尔科夫链讲解(Markov)

    刘航宇
    2021-03-18 / 0 评论 / 66 阅读 / 正在检测是否收录...

    说到马尔可夫链,在机器学习界真是无人不知,无人不晓。谷歌用于确定搜索结果顺序的算法,称为PageRank,就是一种马尔可夫链。在卷积网络出现之前,HMM马尔可夫模型也是语音处理的常用方法。到底什么才是马尔可夫链,之前看了几个介绍特别生动,这里总结一下:

    马尔可夫链
    马尔科夫链是指数学中具有马尔科夫性质的离散事件随机过程。在其每一步中,系统根据概率分布可以从一个状态变到另一个状态,也可以保持当前状态。状态的改变叫做转移,与不同的状态改变相关的概率叫做转移概率。

    下图中有两种状态:A和B。如果我们在A,接下来可以过渡到B或留在A。如果我们在B,可以过渡到A或者留在B。在这张图中,从任意状态到任意状态的转移概率是0.5。
    默认图片
    真正的建模工作者不会总是就画一张马尔科夫链图。 相反,他们会使用“转移矩阵”来计算转移概率。状态空间中的每个状态都会出现在表格中的一列或者一行中。矩阵中的每个单元格都告诉你从行状态转换到列状态的概率。因此,在矩阵中,单元格做的工作和图中的箭头所示是一样。在状态转移矩阵中,行和列都是可能的所有状态,对应位置就是已知行状态,转移到列状态的概率。
    默认图片
    如果状态空间添加了一个状态,我们将添加一行和一列,向每个现有的列和行添加一个单元格。 这意味着当我们向马尔可夫链添加状态时,单元格的数量会呈二次方增长。因此,转换矩阵就起到了很大的作用(除非你想把法尔科夫链图画的跟丛林一样)。

    状态转移矩阵
    从上面可以看出,整个马尔可夫链中的核心就是状态转移矩阵。以股市模型为例,假设初始状态为,然后算之后的状态。

    
    def markov():
        init_array = np.array([0.1, 0.2, 0.7])
        transfer_matrix = np.array([[0.9, 0.075, 0.025],
                                   [0.15, 0.8, 0.05],
                                   [0.25, 0.25, 0.5]])
        restmp = init_array
        for i in range(25):
            res = np.dot(restmp, transfer_matrix)
            print i, "\t", res
            restmp = res
    
    markov()
    输出结果:
    
    0   [ 0.295   0.3425  0.3625]
    1   [ 0.4075   0.38675  0.20575]
    2   [ 0.4762  0.3914  0.1324]
    3   [ 0.52039   0.381935  0.097675]
    4   [ 0.55006   0.368996  0.080944]
    5   [ 0.5706394  0.3566873  0.0726733]
    6   [ 0.58524688  0.34631612  0.068437  ]
    7   [ 0.59577886  0.33805566  0.06616548]
    8   [ 0.60345069  0.33166931  0.06487999]
    9   [ 0.60907602  0.32681425  0.06410973]
    10  [ 0.61321799  0.32315953  0.06362248]
    11  [ 0.61627574  0.3204246   0.06329967]
    12  [ 0.61853677  0.31838527  0.06307796]
    13  [ 0.62021037  0.31686797  0.06292166]
    14  [ 0.62144995  0.31574057  0.06280949]
    15  [ 0.62236841  0.31490357  0.06272802]
    16  [ 0.62304911  0.31428249  0.0626684 ]
    17  [ 0.62355367  0.31382178  0.06262455]
    18  [ 0.62392771  0.31348008  0.06259221]
    19  [ 0.624205   0.3132267  0.0625683]
    20  [ 0.62441058  0.31303881  0.06255061]
    21  [ 0.624563    0.31289949  0.06253751]
    22  [ 0.624676   0.3127962  0.0625278]
    23  [ 0.62475978  0.31271961  0.06252061]
    24  [ 0.6248219   0.31266282  0.06251528]

    从第18次开始,状态就开始收敛至。
    如果我们换一个初始状态,比如,继续运行上面的代码,只是将init_array变一下,最后结果为:

    
    0   [ 0.35  0.38  0.27]
    1   [ 0.4395   0.39775  0.16275]
    2   [ 0.4959   0.39185  0.11225]
    3   [ 0.53315   0.378735  0.088115]
    4   [ 0.558674  0.365003  0.076323]
    5   [ 0.5766378  0.3529837  0.0703785]
    6   [ 0.5895162   0.34322942  0.06725438]
    7   [ 0.59886259  0.33561085  0.06552657]
    8   [ 0.6056996   0.32978501  0.06451539]
    9   [ 0.61072624  0.32538433  0.06388944]
    10  [ 0.61443362  0.32208429  0.06348209]
    11  [ 0.61717343  0.31962047  0.0632061 ]
    12  [ 0.61920068  0.31778591  0.06301341]
    13  [ 0.62070185  0.31642213  0.06287602]
    14  [ 0.62181399  0.31540935  0.06277666]
    15  [ 0.62263816  0.31465769  0.06270415]
    16  [ 0.62324903  0.31410005  0.06265091]
    17  [ 0.62370187  0.31368645  0.06261168]
    18  [ 0.62403757  0.31337972  0.06258271]
    19  [ 0.62428645  0.31315227  0.06256128]
    20  [ 0.62447096  0.31298362  0.06254542]
    21  [ 0.62460776  0.31285857  0.06253366]
    22  [ 0.62470919  0.31276586  0.06252495]
    23  [ 0.62478439  0.31269711  0.0625185 ]
    24  [ 0.62484014  0.31264614  0.06251372]

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

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

    可能的状态数是有限的。
    状态间的转移概率需要固定不变。
    从任意状态能够转变到任意状态。
    不能是简单的循环,例如全是从x到y再从y到x。
    由前面的例子我们不难看出,当与的n次幂相乘以后,发现得到的向量都会收敛到一个稳定值,而且此稳定值与初始向量 无关!那么所有的转移矩阵都有这种现象嘛?或者说满足什么样的条件的转移矩阵会有这种现象?

    细致平衡条件(Detailed Balance Condition):给定一个马尔科夫链,分布 和概率转移矩阵,如果下面等式成立:
    默认图片
    则此马尔科夫链具有一个平稳分布(Stationary Distribution)。

    1

    打赏

    海报

    正在生成.....
    数字图像处理绪论、基础、图像增强简答
    « 上一篇 2021-03-19
    T分布及T分布表
    下一篇 » 2021-03-17

    评论 (0)

    取消