从马尔科夫链到吉布斯采样与PageRank

马尔科夫链表示state的链式关系,下一个state只跟上一个state有关。 吉布斯采样通过采样条件概率分布得到的样本点,近似估计概率分布P(z)P(z)。PageRank通过节点间的连接,估计节点的重要程度rr。吉布斯采样中,state代表不同的样本点,state的分布就是P(z)P(z)。PageRank中,state代表不同节点的分数,state的分布就是要求的rr。不论吉布斯采样还是PageRank,state的分布本质上都是马尔科夫链,而最后都希望state的分布是独一并且稳定的。

Markov Chain

介绍

上图表示了一个典型的马尔科夫链,每个城市A、B、C代表不同的state。该图描述了不同state间的转移变化关系。并且下一个时间的state只和上一个时间的state有关。

稳定态

想象上述的马尔科夫链,state不停的变化,我们可以求出不同state的概率,也就是state的概率分布。

最简单的办法是列出不同state的概率公式,然后解线性方程组求解,如下:

可是,单一稳定的state不一定存在,例如下面两种情况:

  • Spider trap,a⇔ba \Leftrightarrow b,相当于状态被困在某区域(多个状态)。
  • Dead End,a⇒ba \Rightarrow b,相当于状态被困在单个状态中。

那么,什么情况下才有单一稳定的state的存在呢?

单一稳定的state分布的存在的充分条件是:对于任意两个states1,s2s_1,s_2,它们之间的状态转移概率不为0。也就是p(s1|s2)>0p(s_1|s_2)>0。也就是说,state间(包含自身)都有连接,这样的话便存在单一稳定的state分布。

Gibbs Sampling

介绍

Gibbs Sampling遇到的问题是:在已知P(zi|z1,...,zi−1,zi+1,...zN)P(z_i|z_1,...,z_{i-1},z_{i+1},...z_{N})分布的情况下,求变量P(z)(z=z1,...,zN)P(z) (z = {z_1,...,z_N})的分布。

Gibbs Sampling的解决办法是:设置外循环tt,遍历采样点数;设置内循环kk,遍历特征数,对于每一个特征值ztkz_k^t,根据分布ztk∼P(zk=ztk|z1=zt1,z2=zt2,...)z_k^t \sim P(z_k = z_k^t | z_1 =z_1^t, z_2 =z_2^t,...)采样ztkz_k^t。最后,根据z1,z2,z3,...{z^1,z^2,z^3,...}得到P(z)(z=z1,...,zN)P(z) (z = {z_1,...,z_N})的分布。

Gibbs Sampling与Markov

吉布斯采样的数据z1,z2,z3,...{z^1,z^2,z^3,...}相当于马尔科夫链中不同的state(因为ztz^t只和zt−1z^{t-1}有关)。如果马尔科夫链存在单一且稳定的状态分布,那么就可以通过采样求出P(z)(z=z1,...,zN)P(z) (z = {z_1,...,z_N})。

下面,分两个步骤证明:

  1. Gibbs Sampling存在单一且稳定的状态分布。
  2. Gibbs Sampling单一且稳定的状态分布就是P(z)P(z)。

Gibbs Sampling中条件概率没有0值确保了Gibbs Sampling存在单一且稳定的状态分布。

根据概率公式,可推导Gibbs Sampling单一且稳定的状态分布就是P(z)P(z)。

Page Rank

介绍

Page Rank的哲学是:一个点的重要性跟这个点的in-link有关,不同的in-link权重不一样,score越大的节点对应的in-link也就越重要。 令节点的score向量为rr,节点的邻接矩阵为MM。那么,rr和MM的关系可写作:

r=Mr

r = Mr

示例如下:

这个例子中,可以把矩阵MM和向量rr相乘当做MM的列以向量rr为权重进行线性组合,矩阵MM同一列的不同行代表该节点向其他节点的分发连接。这样理解起来就比较清晰了。

rr的求解可以使用特征值-特征向量分解,最大特征值对应的特征向量即是rr。

稳定性

rr的值在满足特定情况下才是单一且稳定的。

实际计算Page Rank中,需要增加一个条件:每个节点都有1N\frac{1}{N}的概率变换到任何其他节点状态。

原来的式子是:

r=Mr

r = Mr

考虑稳定性后的式子是:

Ar=βM+(1−β)1N11T=Ar

\begin{split} A &= \beta M + (1-\beta) \frac{1}{N} \mathbf{1} \mathbf{1}^T \\ r &= Ar \end{split}

示例如下:

稀疏计算

在上面的计算公式中,矩阵AA是稠密的,空间复杂度是O(N2)O(N^2),占得空间很大。

因此,改进计算如下:

Arr=βM+(1−β)1N11T=Ar=βMr+1−βN

\begin{split} A &= \beta M + (1-\beta) \frac{1}{N} \mathbf{1} \mathbf{1}^T \\ r &= Ar \\ r &= \beta M r + \frac{1-\beta}{N} \end{split}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

【深度学习自动上色,数月工作几秒完成】开源神经网络图片上色技术解析

【新智元导读】本文是作者对Reddit社区用户Amir Avni深度学习上色机器人的实现,看完本文后,你也能打造媲美大师级着色效果的自动上色神经网络应用。此外,...

65470
来自专栏数据科学与人工智能

【算法】LDA算法及应用

Latent Dirichlet Allocation是Blei等人于2003年提出的基于概率模型的主题模型算法,LDA是一种非监督机器学习技术,可以用来识别大...

16000
来自专栏ATYUN订阅号

使用Keras创建一个卷积神经网络模型,可对手写数字进行识别

在过去的几年里,图像识别研究已经达到了惊人的精确度。不可否认的是,深度学习在这个领域击败了传统的计算机视觉技术。 将神经网络应用于MNIST的数据集以识别手写的...

30630
来自专栏人工智能LeadAI

卷积神经网络实现多个数字识别

数据集:MNIST 框架:Keras 显卡:NVIDIA GEFORCE 750M 参考:Keras中文文档(http://keras-cn.readthedo...

17520
来自专栏ATYUN订阅号

深度学习中的动手实践:在CIFAR-10上进行图像分类

你想开始进行深度学习吗? 这有一篇关于Keras的深度学习的文章(地址见下方链接),对图像分类的神经网络做了一个总体概述。然而,它缺少一个关键的因素——实际的动...

35860
来自专栏瓜大三哥

视频压缩编码技术(H.264) 之前世今生

众所周知,一幅图像由许多个所谓像素的点组成,如下图中的“O”表示一个像素,大量的统计表明,同一幅图像中像素之间具有较强的相关性,两个像素之间的距离越短,则其相关...

13710
来自专栏文智的专栏

【 文智背后的奥秘 】系列篇 :文本聚类系统

通过文本聚类的自动化流程,文本聚类用户可以挖掘出数据中的热门话题或热门事件,从而为用户对数据的分析提供重要的基础。本文下面先对文本聚类的主要算法作介绍,然后再具...

3.3K00
来自专栏null的专栏

论文阅读——Wide & Deep Learning

这篇文章是阅读《Wide & Deep Learning for Recommender Systems》后的总结,该文章中提出结合Wide模型和Deep模型...

80350
来自专栏ATYUN订阅号

使用Keras的Python深度学习模型的学习率方案

训练神经网络或大型深度学习模型是一项很难的优化任务。传统的训练神经网络的算法称为随机梯度下降。你可以通过在训练中改变学习率来提高性能和提高训练速度。 在这篇文章...

80950
来自专栏AI研习社

深度学习中 GPU 和显存分析

深度学习最吃机器,耗资源,在本文,我将来科普一下在深度学习中: 何为 “资源” 不同操作都耗费什么资源 如何充分的利用有限的资源 如何合理选择显卡 并纠正几个误...

1.9K100

扫码关注云+社区

领取腾讯云代金券