Kuang Algorithm Engineer&Data Mining Engineer

数据科学算法基础——马尔可夫链

2018-03-22
Kuang

数据科学算法基础之马尔可夫链

0 链式规则

设E,F和C都是事件,有:

1 Markov 性质和Markov 过程

若$X(t)$ 满足马尔可夫性质则:

  • 若一个随机过程满足马尔可夫性,即其条件概率至于当前状态有关,而与它的过去或未来状态都是独立、不相关的,则该过程称为马尔可夫过程

  • 马尔可夫过程$X_0,X_1,\cdots$ 满足

2 马尔可夫链

时齐的马尔可夫链

如果一个马尔可夫链$X_t$ 满足$P(X_{s+t}=j\vert X_s=i)$与$s$无关,则称该马尔可夫链为时齐的。

##### 转移矩阵

时刻t的转移矩阵$P^{(t+1)}$满足

状态分布

设$\pi^{(t)}$ 为马尔可夫链在时刻t的状态分布,那么$\pi_x^{(t)} = P[X_t = x]$ 。对于一个确定的马尔可夫来说,$\pi^{(t)}$是一个N维的向量,向量的每一个维度都为非负,且有$\sum_x\pi_x^{(t)} = 1$ 。因此,若$\pi^{(t+1)}=\pi^{(t)}P^{(t+1)}$. 根据全概率公式有

这里的意思是说,t+1时刻的状态分布,等于t时刻的状态分布乘上转移矩阵。

平稳分布

平稳分布指的是对于一个确定的马尔可夫链,其状态转移矩阵为P,平稳分布$\pi$满足$\pi P=\pi$.

  • 对于一些马尔可夫链来说,无论其起始状态的分布是如何,在其进行一定次数的转以后,该马尔可夫链的分布接近于平稳分布。
可约的马尔可夫链

若马尔可夫链中任意状态x都能通过转移到达另一状态y,则称该马尔可夫链不可约,换句话说,若马尔可夫链不可约,则其状态转移图为强连通分量。

##### 马尔可夫链的周期性

若马尔可夫链中至少存在一个状态经过一个固定的时间段后连续返回,即$d_x = gcd{n\vert (P^n)_{x,x}>0}$ ,$d_x$不等于1,则称该马尔可夫链具有周期性。

马尔可夫链的收敛性

设$X_0,X_1,…$为一个不可约的反周期性的马尔可夫链,转移矩阵为P,则任意初始分布$\pi^{(0)}$ ,存在一个唯一的平稳分布$\pi$使得$\pi P=\pi$,并且$lim_{t\rightarrow\infty}\pi^{(0)}P^t=\pi$ 。

3 Google Page Rank

任务定义

给定n个网页链接,根据重要性给这些链接排序.

算法简介

矩阵$A = \begin{bmatrix} a_{11} & \cdots& a_{1n} &\cdots& a_{1M}\ \cdots&&&&\cdots \ a_{m1}&\cdots&a_{mn}&\cdots&a_{mM} \ \cdots &&&&\cdots \ a_{M1}&\cdots&a_{Mn}&\cdots&a_{MM}\end{bmatrix}$

为网页之间的链接数目,$a_{mn}$表示第m个网页指向第n个网页的链接数除以第m个网页上的链接总数。该矩阵每一行的和为1,是一个马尔可夫状态转移矩阵。

假设初始的状态下

$B_0 = (\frac{1}{N},\frac{1}{N},\cdots,\frac{1}{N})$

通过多次运算最终$B_i$会收敛。得到的$B_i$就是各个网页的重要性。

由于网页之间的链接数量相比于互联网的规模非常稀疏,因此计算网页的网页排名也需要对零概率或者小概率事件进行平滑处理。例如将矩阵A变成B=0.85A+0.15。这样得到的B仍然是马尔科夫状态转移矩阵,且没有非零项。


Comments