从马尔科夫链到吉布斯采样与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 条评论
登录 后参与评论

相关文章

来自专栏新智元

【信息图】神经网络动物园前序:Cell与层之间如何连接

【新智元导读】 此前介绍的神经网络动物园让大家大饱眼福,看到了各种各样的神经网络模型。今天带来更为基础的介绍:组成神经网络模型的基本单元和层是怎么样的?通过信...

3096
来自专栏贾志刚-OpenCV学堂

OpenCV 基于Inception模型图像分类

要介绍Inception网络结构首先应该介绍一下NIN(Network in Network)网络模型,2014年新加坡国立大学发表了一篇关于计算机视觉图像分类...

894
来自专栏机器学习算法全栈工程师

随机采样方法——蒙特卡罗方法

地址:http://www.cnblogs.com/pinard/p/6625739.html

643
来自专栏新智元

TensorFlow 自动句子语义编码,谷歌开源机器学习模型 Skip-Thoughts

【新智元导读】谷歌今天开源一个句子编码器模型 Skip-Thoughts,在 TensorFlow 上实现,学习将输入的句子编码成固定维度的向量表示,可以用于语...

3083
来自专栏AI研习社

利用 SKLearn 重建线性模型

线性模型通常是训练模型的一个比较好的起点。 但是由于许多数据集的自变量和因变量之间并不是线性关系,所以经常需要创建多项式模型,导致这些模型很容易过拟合。 正则化...

903
来自专栏人工智能头条

人脸识别技术大总结1——Face Detection &Alignment

1345
来自专栏贾志刚-OpenCV学堂

LDA(Linear Discriminant Analysis)算法介绍

一:LDA概述。 线性判别分析(LDA)是一种用来实现两个或者多个对象特征分类方法,在数据统计、模式识别、机器学习领域均有应用。LDA跟PCA非常相似、唯一不同...

2536
来自专栏AILearning

【Scikit-Learn 中文文档】概率校准 - 监督学习 - 用户指南 | ApacheCN

1.16. 概率校准 执行分类时, 您经常希望不仅可以预测类标签, 还要获得相应标签的概率. 这个概率给你一些预测的信心. 一些模型可以给你贫乏的概率估计,...

2627
来自专栏AI研习社

使用 Scikit-learn 理解随机森林

在我以前的一篇文章(https://blog.datadive.net/interpreting-random-forests/)中,我讨论了随机森林如何变成一...

912
来自专栏AlgorithmDog的专栏

Metropolis-Hastings 和 Gibbs sampling

在科学研究中,如何生成服从某个概率分布的样本是一个重要的问题。 如果样本维度很低,只有一两维,我们可以用反切法、拒绝采样和重要性采样等方法。 但是对...

2059

扫描关注云+社区