Google 的秘密- PageRank 彻底解说

散部分的状态概率几乎接近于0。关于EllGoth部分，连同与各联结成分对应状态的类、像独立的最简的马尔可夫链一样行动，其中，各类中的状态概率(即从过去开始的平均值)的值和初期状态概率无关，换言之，是近似于与对应 P 的最简成分的固有矢量成比例的东西。在类之间概率的分配依存于初期状态的概率。

离散时间型马尔可夫链的不变分布是属于极限分布，从那个分布开始已经不是在分布意义上的随时间的变化了。状态的概率分布在时间变化时也不会变化时被称为固定分布。PageRank 用马尔可夫过程来说就是，PageRank就是以一定时间内用户随机地沿着(网页)链接前进时对各个页面访问的固定分布。
假想模型和现实世界的不同

那么，让我们将概率过程(即图表原理)的考虑方法和实际的网页链接构造合起来看一看。

对于刚才举例的假想网页群来说，只要相互顺着链接前进则在彼此页面间必定有相互链接的关系。即，有向图表是强联结的行列既是回归又是最简。像上面举的很多的概率过程的教科书一样，许多证明都是把回归和最简作为前提来证明的，如果是最简的话，各种各样的性质就变得容易说了。

但是现实的网页并不是强联结。也就是说邻接行列不是最简的。具体来说，顺着链接前进的话，有时会走到完全没有向外链接的网页。通常这样的情况，只有利用 web 浏览器的「返回」功能了。如果人们只是浏览而已的话，一切就到此结束了，然而 PageRank 的计算却不能到此结束。因为PageRank 一旦被引入以后是不能返回的。Pagerank 称这种页面为为「dangling page」。同样道理，只有向外的链接而没有反向链接的页面也是存在的。但 Pagerank 并不考虑这样的页面,因为没有流入的 PageRank 而只流出的 PageRank，从对称性来考虑的话必定是很奇怪的。

同时，有时候也有链接只在一个集合内部旋转而不向外界链接的现象。这是非周期性的回归类多重存在时可能出现的问题。(请读者考虑一下陷入上图中一个 R 中而不能移动到别的 R 和 T 的情况)。 Pagerank 称之为「rank sink」。在现实中的页面，无论怎样顺着链接前进，仅仅顺着链接是绝对不能进入的页面群总归存在，也就是说，这些页面群是从互相没有关联的多数的同值类(回归类)形成的。

总之，由现实的 Web 页组成的推移概率行列大部分都不是最简的。当不是最简时，最大特性值(即1)是重复的，并且不能避免优固有矢量多数存在的问题。换句话说，PageRank 并不是从一个意义上来决定的。

在此，Pagerank 为了解决这样的问题，考虑了一种「用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面里」,这样的浏览模型。再者，将「时常」固定为 15％ 来计算。用户在 85％ 的情况下沿着链接前进,但在 15％ 的情况下会突然跳跃到无关的页面中去。(注:Pagerank 的原始手法是各自87％(＝1/1.15 )和13％(＝0.15/1.15)。)

将此用算式来表示的话得到以下公式。

M'= c*M +(1-c)*[1/N]

其中，[1/N]是所有要素为 1/N 的 N次正方行列，c =0.85(=1-0.15)。M'当然也同样是推移概率行列了。也就是说，根据 Pagerank 的变形，原先求行列 M 的特性值问题变成了求行列 M'的优固有矢量特性值问题。M 是固定无记忆信息源(i.i.d.)时，M'被称为「混合信息源」，这也就是固定但非ellGoth信息源的典型例子。

如果从数学角度看，「把非最简的推移行列最简化」操作的另外一种说法就是「把不是强联结的图表变成强联结」的变换操作。所谓对全部的要素都考虑0.15的迁移概率，就是意味着将原本非最简的推移概率行列转换为最简并回归的（当然非负的情况也存在）推移概率行列。针对原本的推移概率行列，进行这样的变换操作的话，就能从一个意义上定义 PageRank、也就是说能保证最大特性值的重复度为1。如果考虑了这样的变换操作的话，因为推移概率行列的回归类的数目变成 1 的同时也最简化，根据前面的定理，优固有矢量(即 PageRank)就被从一个意义上定义了。
数值计算上的问题点(其1)

在此，只要大概明白 PageRank 的概念就可以了，不需要很深的陷入数值计算上的技术的问题中(其实，笔者自己即使有自信也说不清楚)。但是，因为特性值分析和联立一次方程式分析一样，是利用在各种的统计分析中重要的数值计算手法的一中，所以这里我们简单的触及一些分析方法。

主记忆领域的问题是在数值计算上的问题之一。

假设 N 是 104 的 order。通常，数值计算程序内部行列和矢量是用双精度记录的，N 次正方行列 A 的记忆领域为 sizeof(double)* N * N =8 *104 * 104＝800MB。 800MB 的主记忆领域不是那种经常会拥有的东西, 虽然这么说也非那种不可能的数字。但是，N 如果变成 105 或106 的话，各自就变成80GB,8TB。这样的话不用说内存就连硬盘也已经很困难了。 Google 从处理着10亿以上的页面(2001年时)以来，就知道这种规矩的做法已经完全不适用了。

不过，A 只是稀疏(sparse)行列。因为即使有一部分的页面拼命地进行链接，但是向整个Web展开链接的页面是没有的，即使有也是极为稀少的。平均一下，每一张页面有10-20个左右的链接(根据 IBM Almaden 研究所'Graph structure in the web' 的统计，平均在16.1个左右)。因此，我们可以采用恰当的压缩方法来压缩 A 。 N 即使是 106 时，如果平均链接数是10，最终的记忆领域只要 80MB，从规模上来说可以收纳到合理的数字里。

稀疏行列的容纳方式当今已经被充分地研究(有限要素法的解法等)，在恰当的数值计算的专业书中就可以学到。虽然这么说，因为相当地难解还是需要很复杂的手法。但想指出的是如果可以很好的解决的话，并列化的高速计算(也许)就变得可能了。因为比起怎样排列并容纳非零要素来说，计算性能和并列性能对其的影响会更大。
数值计算上的问题点(其2)

另一个是收敛问题。

固定方程式

xi＝ΣAijxi

是 N 元的联立一次方程式，一般地不能得到分析解，所以只能解其数值。刚才举的例子中为了求特性值和固有矢量，使用了 Octave 的 eig()函数, 不过，这个在问题小的时候不能适用。说起来，并不需要计算全部的特性值/固有矢量。

求最大特性值和属于它的固有矢量(优固有矢量)的数值计算手法中，一般使用「幂乘法」(也叫反复法)。这是指，取适当初期矢量 x0 ，当 x(n+1) = A y(n) (其中 y(n) = x(n) / c(n) )中的 n →∞ 时，x 向拥有最大特性值的固有矢量收敛的同时 c 向此最大特性值收敛的利用线形代数性质的计算方法(证明请参照线形代数的教科书)。幂乘法(反复法)的特长与逐次反复计算的近似法比，能够改善解矢量的问题。它的优点是，因为只要反复对行列和矢量进行适当次数的乘法运算，所以只要通过程序就能够简单地解决，并且还可以进行由于受到内存和硬盘的限制通过直接法不能解决的大规模分析。这是许多的实用算法的出发点。

在这里，请注意从线形代数的简单定理(Peron-Frobenius定理)得到推移概率行列的绝对价值的最大特性值是1。如果采用了这个，就会使得反复法的 PageRank 的计算变得更容易。即，因为最大特性值是既知的，比起求满足 Ax=x 的矢量 x来说 ，变成更加简单的问题了。这虽然是很细小的地方但是很重要。首先，可以去掉比较花费成本的除法计算 (y(n)=x(n)/c(n))不用完成。如果是反复法的话，不能得到很高的精确度，并且如果搞错了加速方法的话，计算出的不是是最大特性值而是第二大特性值和属于它的固有矢量(虽然这种情况很少，但是说不定就是从根本上错误的值)。但如果知道了最大特性值，就可以进行核对了。在 Pagerank 的第一篇论文中他们似乎没有注意到这个事情,但在 Haveliwala 的第二论文中增加了关于此的修正。

反复的次数取决于想要求的精度。也就是说，想要求的精度越高，反复的次数就越多。可是，幂乘法(反复法)的误差的收敛比与系数行列的谱段特性(特性值的绝对值分布)有很强的依存关系。具体地说，绝对值最大的特性值用λ1表示，第二位用 λ2 表示，优越率(收敛率 probability of dominance)为 d =λ1/λ2 话，可以知道d离1越近收敛就变得越慢。在 N 很大的情况时d当然离1很近。这是因为，绝对值最大的特性值是1，而其他所有的 N-1 个特性值的绝对值都比1小。但是，N-1个特性值之间非常的拥挤，所以λ1和λ2 之间几乎没有差别。因此一般来说，收敛会变慢。

所谓收敛变慢，严密地说，就是无论经过多少时间也完成不了的计算。对此，为了使收敛加快的适当的加速方法也是存在的，应用这些方法时，需要对数值计算技术有十二分的理解，因此如果不是数值计算的专家就很难引入。
5. Namazu 上的实际安装实验

为了使更简单地推测上文描述的问题，PageRank 并不是非世界所有的web页面而不能使用的考虑方法，即使是个人的利用方法也能实现。为了实现「Personalized PageRank」，针对在各种 UNIX 和 Windows 上运作的中小规模网站适用的全文检索系统 Namazu 进行了实际安装实验。(关于Namazu可参考 日语全文检索引擎软件列表。)

由于实验能简单地控制内存的使用量，并将最大特性值用1来考虑，所以将 Have liwala(1999)的想法做为基本的考虑方法。但是对 dangling pages 的处理有少许不同。固有矢量的计算内核使用了数值计算脚本 GNU Octave。所以基本的代码编写自己只用了一天就解决了。另外，从用 mknmz 编写的索引不能直接计算 PageRank，而要事前准备表示邻接关系的索引(邻接列表)。这个也有可能被编入检索者(Indexer)的主要部分。

以下表示了实际计算时间(单位：秒)。运行机器的配置为 PentiumII 400MHz x 2,内存512MB，Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp)，Octave-2.0.16(一般状态分发物)。收敛精度(剩余差矢量的L1规范)取了到1.0e-10,也许有些过分精确了。

文书数N     mknmz时间    准备时间   PageRank计算时间
============================================================
128          58