从马尔科夫链到吉布斯采样与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
  • 介绍
  • 稳定态
• Gibbs Sampling
  • 介绍
  • Gibbs Sampling与Markov
• Page Rank
  • 介绍
  • 稳定性
  • 稀疏计算

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}