Google 的秘密- PageRank 彻底解说

作者:佚名       来源于:中国营销策划网

准备:数学用语(主要概率过程)的解说

推移概率行列和概率过程上的马尔可夫过程存在很深的关系。本章先离开与 PageRank 本身的说明,预先说明几个呈现在概率过程上的数学用语。因为会设计相当难的部分,如果不能够理解也可以跳过这里。(也可能是我的说明方法不好) 同时,请注意这里几乎没有证明就直接使用了。详细的解说请阅读教科书。

从有向图表S的状态 i 出发,将有限时间之后再次回复到状态 i 的概率作为 1 时,也就是说,当沿着(有向)图表的方向前进能够回到原来位置的路径存在的时候,i 就被成为「回归」。不能回归的状态被称为「非回归」。从状态 i 出发,当通过有限次数的推移达到状态 j 的概率非负的时候,我们就说「从状态 i 到达状态 j 是可能的」。当反方向也可能到达的时候,我们称「i 和 j 互相可能到达」。从状态 i 不能到达其他任何状态的时候,称 i 为「吸收状态」。

从邻接行列 A 所决定的图表(graph)的任意顶点出发,指向其他任意的顶点图表的路径能够像箭头那样到达时被称为「强联结」( 也被称为「分解不能」)。强联结,等价于从任意状态到任意状态可以互相到达。邻接行列 A 的成分中有很多 0 时,强联结性就会有问题。注意,如果全部成分都为 aij ≠0 的话,则都属于强联结。因为,对应的 马尔可夫链的样本路径表示 S 的任意两点间以正的概率来往通行。

我们可以把全体状态以等价类(或者回归类)来划分。在这里,回归类是指链接所围成的范围。属于一个等价类的状态可以互相到达。从一个类出发以正的概率进入到其他的类的可能性也是存在的。可是很明显,在这种情况下不可能回复到原来的类。不然的话,这两个类就归于等价类了。下图表示了,当 T 作为非回归性的等价类、R 作为回归性等价类时,虽然存在 马尔可夫链 既不来自回归类,也不来自非回归类的情况,但如果一旦来自前两者的话,就不再会回到非回归类中了。

重归?非重归的图
回归、非回归示意图(修改了小谷(1997)的图11.1)

这个等价关系中只有一个回归类的时候,那个 马尔可夫链就被称为「最简」。换句话说,全部的状态之间互相可以到达时就被称为最简。最简时都是强联结。

互相完全没有关联的邻接行列(或推移概率行列),乘以恰当的置换行列(掉换行和列)以后得到

P = | P1 0 |
    | 0 P2 |

这样的关系。这表示回归类 P1 和 P2 间完全不存在直接的链接关系。

回归类、非回归类掺杂在一起的邻接行列(或推移概率行列),乘以恰当的置换行列后得到,

P = | P1 0 | 
    | Q P2 |

这样的关系(Q≠0)。此时,P1是非回归类,P2是回归类。

推移概率行列有时也被称作马尔可夫行列。称马尔可夫过程的试验行列的观测结果为马尔可夫链(Markov chain)。 当经过相当的时间后马尔可夫链会趋向某种平衡状态。对任意的状态 i, 如果 j 是非回归状态,则 Pij(n)→0。相反,当 i 为非回归、j 为回归时,停留在状态 i 上着的概率是0。如果 i,j 属于同样的非周期性回归类的话,Pij(n)→Pj≥0。

定理:若 P 是有限马尔可夫行列的话,P 的特性值 1 的重复度等于 P 决定的回归类的数目。(证明太长,省略)。

跟随着推移概率行列的有向图表的最大强联结成分(与之对应的状态的集合)被称为Ergodic部分(历遍部分),此外的强联结成分被称为消散部分。因为无论从怎样的初期状态概率 x(0)开始,经过时间 n 后 x(n) = P(n)x(0),所以属于消散部分的状态概率几乎接近于0。关于EllGoth部分,连同与各联结成分对应状态的类、像独立的最简的马尔可夫链一样行动,其中,各类中的状态概率(即从过去开始的平均值)的值和初期状态概率无关,换言之,是近似于与对应 P 的最简成分的固有矢量成比例的东西。在类之间概率的分配依存于初期状态的概率。

离散时间型马尔可夫链的不变分布是属于极限分布,从那个分布开始已经不是在分布意义上的随时间的变化了。状态的概率分布在时间变化时也不会变化时被称为

|<< << < 1 2 3 4 5 6 7 8 9 10 > >> >>|


 7/12   首页 上一页 5 6 7 8 9 10 下一页 尾页

上一篇登录搜索引擎的准备工作

下一篇搜索引擎垃圾

 【相关文章




版权声明:文章观点仅代表作者观点,作为参考,不代表本站观点。部分文章来源于网络,如果网站中图片和文字侵犯了您的版权,请联系我们及时删除处理!转载本站内容,请注明转载网址、作者和出处,避免无谓的侵权纠纷。