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

图片名称

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

Markov Chain

介绍

这里写图片描述

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

稳定态

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

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

这里写图片描述

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

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

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

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

Gibbs Sampling

介绍

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

Gibbs Sampling的解决办法是:设置外循环$t$,遍历采样点数;设置内循环$k$,遍历特征数,对于每一个特征值$z_k^t$,根据分布$z_k^t \sim P(z_k = z_k^t | z_1 =z_1^t, z_2 =z_2^t,…)$采样$z_k^t$。最后,根据${z^1,z^2,z^3,…}$得到$P(z) (z = {z_1,…,z_N})$的分布。

这里写图片描述

Gibbs Sampling与Markov

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

下面,分两个步骤证明:

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

Gibbs Sampling中条件概率没有0值确保了Gibbs Sampling存在单一且稳定的状态分布。
这里写图片描述

根据概率公式,可推导Gibbs Sampling单一且稳定的状态分布就是$P(z)$。
这里写图片描述

Page Rank

介绍

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

示例如下:
这里写图片描述

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

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

稳定性

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

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

原来的式子是:

$$r = Mr$$

考虑稳定性后的式子是:

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

示例如下:

这里写图片描述

稀疏计算

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

因此,改进计算如下:

$$\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}$$