轻舟过
谷歌如何从网络的大海里捞到针
>>
完整版
谷歌如何从网络的大海里捞到针David Austin
关键词： 谷歌，搜索，随机矩阵，特征值
想象一个含有250亿份文件，却没有集中管理机构和馆员的图书馆，而且任何人都可以在任何时间添加新的文件而不需要通知其他人。一方面你可以确定，这庞大的文件堆中有一份文件含有对你至关重要的信息，而另一方面，你又像我们中的大多数人那样没有耐心，想要在几秒钟之内就找到这条信息。你有什么办法呢？摆在你面前的这个难题看起来似乎无法解决。而这个文件堆跟万维网（World Wide Web）其实相差无几，后者就是一个超大的、高度混乱的以各种形式存放的文件堆。当然，从万维网中找信息我们有办法解决，因为我们对搜索引擎非常熟悉（或许你就是通过搜索找到这篇文章的）。本文将介绍谷歌的网页排序算法（PageRank Algorithm），以及它如何从250亿份网页中捞到与你的搜索条件匹配的结果。它的匹配效果如此之好，以至于“谷歌”（google）今天已经成为一个被广泛使用的动词了。包括谷歌在内，多数搜索引擎都是不断地运行计算机程序群，来检索网络上的网页、搜索每份文件中的词语并且将相关信息以高效的形式进行存储。每当用户检索一个短语，例如“搜索引擎”，搜索引擎就将找出所有含有被检索短语的网页。（或许，类似“搜索”与“引擎”之间的距离这样的额外信息都被会考虑在内。）但问题是，谷歌现在需要检索250亿个页面，而这些页面上大约95%的文本仅由大约一万个单词组成。也就是说，对于大多数搜索而言，将会有超级多的网页含有搜索短语中的单词。我们所需要的其实是这样一种办法，它能够将这些符合搜索条件的网页按照重要程度进行排序，这样才能够将最重要的页面排在最上面。确定网页重要性的一个方法是使用人为排序。例如，你或许见过这样一些网页，他们包含了大量的链接，后者连接到某个特定兴趣领域的其他资源。假定维护这个网页的人是可靠的，那么他推荐的网页在很大程度上就可能有用。当然，这种做法也有其局限性，比如这个列表可能很快就过期了，也可能维护这个列表的人会无意或因某种未知的偏见而遗漏掉一些重要的网页。谷歌的网页排序算法则不借助人为的内容评估来确定网页的重要性。事实上，谷歌发现，它的服务的价值很大程度上是它能够提供给用户无偏见的搜索结果。谷歌声称，“我们软件的核心就是网页排序（PageRank）。” 正如我们将要看到的，技巧就是让网页自身按照重要性进行排序。如何辨别谁重要如果你曾建立过一个网页，你应该会列入一些你感兴趣的链接，它们很容易使你点击到其它含有重要、可靠信息的网页。这样就相当于你肯定了你所链接页面的重要性。谷歌的网页排序算法每月在所有网页中进行一次受欢迎程度的评估，以确定哪些网页最重要。网页排序算法的提出者，谢尔盖?布林(Sergey Brin)和拉里?佩奇(Lawrence Page)的基本想法是：一个网页的重要性是由链接到它的其他网页的数量及其重要性来决定。我们对任意一个网页[tex]P[/tex]，以[tex]I(P)[/tex]来表述其重要性，并称之为网页的网页排序。在很多网站，你可以找到一个近似的网页排序值。（例如，美国数学会的首页目前的网页排序值为8，最高分是10。你可以试试找到一个网页排序值为10的网页吗？）这个网页排序值仅是一个近似值，因为谷歌拒绝提供真实的网页排序值，以阻止那些试图干扰排序的行为。网页排序是这样确定的。假定网页[tex]P_j[/tex]有[tex]l_j[/tex]个链接。如果这些链接中的一个链接到网页[tex]P_i[/tex]，那么网页[tex]P_j[/tex]将会将其重要性的[tex]1/l_j[/tex]赋给[tex]P_i[/tex]。网页[tex]P_i[/tex]的重要性就是所有指向这个网页的其他网页所贡献的重要性的加和。换言之，如果我们记链接到网页[tex]P_i[/tex]的网页集合为[tex]B_i[/tex]，那么[tex]I(P_i)=\displaystyle \sum_{P_j \in B_i} \dfrac{I(P_j)}{l_j}.[/tex]这或许让你想起“先有鸡还是先有蛋”的问题：为了确定一个网页的重要性，我们首先得知道所有指向它的其他网页的重要性。然而，我们可将这个问题改写为一个更数学化的问题。首先建立一个矩阵，称为超链矩阵（hyperlink matrix），[tex]\mathrm H=[H_{ij}][/tex]，其中第[tex]i[/tex]行第[tex]j[/tex]列的元素为[tex]H_{ij}=\begin{cases} \dfrac{1}{l_j}~& \mathrm{如果} P_j \in B_i \\ 0 & \mathrm{上述条件不成立}. \end{cases}[/tex]注意到[tex]\mathrm H[/tex]有一些特殊的性质。首先，它所有的元都是非负的。其次，除非对应这一列的网页没有任何链接，它的每一列的和为1。所有元均非负且列和为1的矩阵称为随机矩阵，随机矩阵将在下述内容中起到重要作用。我们还需要定义向量[tex]I=[I(P_i)][/tex]，它的元素为所有网页的网页排序——重要性的排序值。前面定义的网页排序可以表述为[tex]I = \mathrm HI.[/tex]换言之，向量[tex]I[/tex]是矩阵[tex]\mathrm H[/tex]对应特征值1的特征向量。我们也称之为矩阵[tex]\mathrm H[/tex]的平稳向量（stationary vector）。让我们来看一个例子。下图所示为一个网页集合（8个），箭头表示链接。其相应的矩阵为这说明网页8的受欢迎程度最高。下图是阴影化的图，其中网页排序值越高的网页阴影越浅。计算平稳向量[tex]I[/tex]
有很多方法可以找到一个方阵的特征向量。然而，我们面对的是一个特殊的挑战，因为矩阵[tex]\mathrm H[/tex]是一个这样的方阵，它的每一列都对应谷歌检索到的一个网页。也就是说，[tex]\mathrm H[/tex]大约有n=250亿行和列。不过其中大多数的元都是0；事实上，研究表明每个网页平均约有10个链接，换言之，平均而言，每一列中除了10个元外全是0。我们将选择被称为幂法（power method）的方法来找到矩阵[tex]\mathrm H[/tex]的平稳向量[tex]I[/tex]。幂法如何实现呢？首先选择[tex]I[/tex]的备选向量[tex]I^0[/tex]，进而按下式产生向量序列[tex]I^k[/tex][tex]I^{k+1} = \mathrm HI^k,~~~k=0,1,2,...[/tex]这个方法是建立在如下的一般原理上：一般原理：序列[tex]I^k[/tex]将收敛到平稳向量[tex]I[/tex]。我们首先用个例子验证上面的结论。
- 序列[tex]I^k[/tex]总是收敛吗？（即运算多次后，[tex]I^k[/tex]和[tex]I^{k+1}[/tex]几乎是一样的）
- 收敛后的平稳向量是否和初始向量[tex]I^0[/tex]的选取没有关系？
- 重要性排序值是否包含了我们想要的信息？
对目前的方法而言，上述三个的答案都是否定的！下面，我们将看看如何改进我们的方法，使得改进后的算法满足上述三个要求。先看个非常简单的例子。考虑如下包含两个网页的小网络，其中一个链接到另一个：下例展示了算法的运行过程：
- Michael Berry, Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval. Second Edition, SIAM, Philadelphia. 2005.
- Sergey Brin, Lawrence Page, The antaomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 33: 107-17, 1998. Also available online at http://infolab.stanford.edu/pub/papers/google.pdf
- Kurt Bryan, Tanya Leise, The $25,000,000,000 eigenvector. The linear algebra behind Google. SIAM Review, 48 (3), 569-81. 2006. Also avaiable at http://www.rose-hulman.edu/~bryan/google.html
- Google Corporate Information: Technology.
- Taher Haveliwala, Sepandar Kamvar, The second eigenvalue of the Google matrix.
- Amy Langville, Carl Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.This is an informative, accessible book, written in an engaging style. Besides providing the relevant mathematical background and details of PageRank and its implementation (as well as Kleinberg's HITS algorithm), this book contains many interesting "Asides" that give trivia illuminating the context of search engine design.
原文链接: http://www.ams.org/samplings/feature-column/fcarc-pagerank 作 者: David Austin，Grand Valley State University 翻 译: 沈栋，中科院数学与系统科学研究院博士，北京化工大学副教授 校 对: 汤涛，香港浸会大学数学讲座教授
轻舟过
谷歌如何从网络的大海里捞到针
>>
完整版
谷歌如何从网络的大海里捞到针David Austin
关键词： 谷歌，搜索，随机矩阵，特征值
想象一个含有250亿份文件，却没有集中管理机构和馆员的图书馆，而且任何人都可以在任何时间添加新的文件而不需要通知其他人。一方面你可以确定，这庞大的文件堆中有一份文件含有对你至关重要的信息，而另一方面，你又像我们中的大多数人那样没有耐心，想要在几秒钟之内就找到这条信息。你有什么办法呢？摆在你面前的这个难题看起来似乎无法解决。而这个文件堆跟万维网（World Wide Web）其实相差无几，后者就是一个超大的、高度混乱的以各种形式存放的文件堆。当然，从万维网中找信息我们有办法解决，因为我们对搜索引擎非常熟悉（或许你就是通过搜索找到这篇文章的）。本文将介绍谷歌的网页排序算法（PageRank Algorithm），以及它如何从250亿份网页中捞到与你的搜索条件匹配的结果。它的匹配效果如此之好，以至于“谷歌”（google）今天已经成为一个被广泛使用的动词了。包括谷歌在内，多数搜索引擎都是不断地运行计算机程序群，来检索网络上的网页、搜索每份文件中的词语并且将相关信息以高效的形式进行存储。每当用户检索一个短语，例如“搜索引擎”，搜索引擎就将找出所有含有被检索短语的网页。（或许，类似“搜索”与“引擎”之间的距离这样的额外信息都被会考虑在内。）但问题是，谷歌现在需要检索250亿个页面，而这些页面上大约95%的文本仅由大约一万个单词组成。也就是说，对于大多数搜索而言，将会有超级多的网页含有搜索短语中的单词。我们所需要的其实是这样一种办法，它能够将这些符合搜索条件的网页按照重要程度进行排序，这样才能够将最重要的页面排在最上面。确定网页重要性的一个方法是使用人为排序。例如，你或许见过这样一些网页，他们包含了大量的链接，后者连接到某个特定兴趣领域的其他资源。假定维护这个网页的人是可靠的，那么他推荐的网页在很大程度上就可能有用。当然，这种做法也有其局限性，比如这个列表可能很快就过期了，也可能维护这个列表的人会无意或因某种未知的偏见而遗漏掉一些重要的网页。谷歌的网页排序算法则不借助人为的内容评估来确定网页的重要性。事实上，谷歌发现，它的服务的价值很大程度上是它能够提供给用户无偏见的搜索结果。谷歌声称，“我们软件的核心就是网页排序（PageRank）。” 正如我们将要看到的，技巧就是让网页自身按照重要性进行排序。如何辨别谁重要如果你曾建立过一个网页，你应该会列入一些你感兴趣的链接，它们很容易使你点击到其它含有重要、可靠信息的网页。这样就相当于你肯定了你所链接页面的重要性。谷歌的网页排序算法每月在所有网页中进行一次受欢迎程度的评估，以确定哪些网页最重要。网页排序算法的提出者，谢尔盖•布林(Sergey Brin)和拉里•佩奇(Lawrence Page)的基本想法是：一个网页的重要性是由链接到它的其他网页的数量及其重要性来决定。我们对任意一个网页P，以I(P)来表述其重要性，并称之为网页的网页排序。在很多网站，你可以找到一个近似的网页排序值。（例如，美国数学会的首页目前的网页排序值为8，最高分是10。你可以试试找到一个网页排序值为10的网页吗？）这个网页排序值仅是一个近似值，因为谷歌拒绝提供真实的网页排序值，以阻止那些试图干扰排序的行为。网页排序是这样确定的。假定网页Pj有lj个链接。如果这些链接中的一个链接到网页Pi，那么网页Pj将会将其重要性的1/lj赋给Pi。网页Pi的重要性就是所有指向这个网页的其他网页所贡献的重要性的加和。换言之，如果我们记链接到网页Pi的网页集合为Bi，那么I(Pi)=∑Pj∈BiI(Pj)lj.这或许让你想起“先有鸡还是先有蛋”的问题：为了确定一个网页的重要性，我们首先得知道所有指向它的其他网页的重要性。然而，我们可将这个问题改写为一个更数学化的问题。首先建立一个矩阵，称为超链矩阵（hyperlink matrix），H=[Hij]，其中第i行第j列的元素为Hij=⎧⎩⎨1lj 0如果Pj∈Bi上述条件不成立.注意到H有一些特殊的性质。首先，它所有的元都是非负的。其次，除非对应这一列的网页没有任何链接，它的每一列的和为1。所有元均非负且列和为1的矩阵称为随机矩阵，随机矩阵将在下述内容中起到重要作用。我们还需要定义向量I=[I(Pi)]，它的元素为所有网页的网页排序——重要性的排序值。前面定义的网页排序可以表述为I=HI.换言之，向量I是矩阵H对应特征值1的特征向量。我们也称之为矩阵H的平稳向量（stationary vector）。让我们来看一个例子。下图所示为一个网页集合（8个），箭头表示链接。其相应的矩阵为这说明网页8的受欢迎程度最高。下图是阴影化的图，其中网页排序值越高的网页阴影越浅。计算平稳向量
I有很多方法可以找到一个方阵的特征向量。然而，我们面对的是一个特殊的挑战，因为矩阵H是一个这样的方阵，它的每一列都对应谷歌检索到的一个网页。也就是说，H大约有n=250亿行和列。不过其中大多数的元都是0；事实上，研究表明每个网页平均约有10个链接，换言之，平均而言，每一列中除了10个元外全是0。我们将选择被称为幂法（power method）的方法来找到矩阵H的平稳向量I。幂法如何实现呢？首先选择I的备选向量I0，进而按下式产生向量序列IkIk+1=HIk, k=0,1,2,...这个方法是建立在如下的一般原理上：一般原理：序列Ik将收敛到平稳向量I。我们首先用个例子验证上面的结论。
- 序列
Ik总是收敛吗？（即运算多次后，Ik和Ik+1几乎是一样的）- 收敛后的平稳向量是否和初始向量
I0的选取没有关系？- 重要性排序值是否包含了我们想要的信息？
对目前的方法而言，上述三个的答案都是否定的！下面，我们将看看如何改进我们的方法，使得改进后的算法满足上述三个要求。先看个非常简单的例子。考虑如下包含两个网页的小网络，其中一个链接到另一个：下例展示了算法的运行过程：
- Michael Berry, Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval. Second Edition, SIAM, Philadelphia. 2005.
- Sergey Brin, Lawrence Page, The antaomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 33: 107-17, 1998. Also available online at http://infolab.stanford.edu/pub/papers/google.pdf
- Kurt Bryan, Tanya Leise, The $25,000,000,000 eigenvector. The linear algebra behind Google. SIAM Review, 48 (3), 569-81. 2006. Also avaiable at http://www.rose-hulman.edu/~bryan/google.html
- Google Corporate Information: Technology.
- Taher Haveliwala, Sepandar Kamvar, The second eigenvalue of the Google matrix.
- Amy Langville, Carl Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.This is an informative, accessible book, written in an engaging style. Besides providing the relevant mathematical background and details of PageRank and its implementation (as well as Kleinberg's HITS algorithm), this book contains many interesting "Asides" that give trivia illuminating the context of search engine design.
原文链接: http://www.ams.org/samplings/feature-column/fcarc-pagerank 作 者: David Austin，Grand Valley State University 翻 译: 沈栋，中科院数学与系统科学研究院博士，北京化工大学副教授 校 对: 汤涛，香港浸会大学数学讲座教授
轻舟过
判定被7整除的简易方法
>>
完整版
转自：Matrix67的博客
判断一个数的整除性对于某些除数来说是一件非常容易的事，比如2、3、4、5、6、8、9、10、11、12、15……
但是对于7来说一直是一个难题，而判定是否被7整除在数字运算中又比较常用。我刚看到一种判定能否被7整除的方法，在这里写一下。
比如，我们要看86415能否被7整除。首先我们把它从个位开始往左边走两个数字一组划分开来，这样，86415就划分成8 64 15；然后，从左开始“一加一减找余数”：
6 6
8 64 15
1
看上面，6+8正好被7整除，64-1被7整除，15+6被7整除。
然后把找到的余数从右往左读出来，616，现在，如果616能被7整除，那么86415就能被7整除。
如果你还看不出616能被7整除的话，可以继续这样做下去：
1
6 16
2
现在很明显了吧，21能被7整除。因此，86415就能被7整除。
下面我再举一个例子：6913580247。
1 5 2
69 13 58 02 47
6 2
22561
5 2
2 25 61
4
245能被7整除，因此6913580247能被7整除。
更加奇妙的是，这个方法对于判定被11整除、被13整除同样有效。
至于为什么，我没仔细研究，估计和那个有关。看到7、11、13这三个数，你难道还想不起那个吗？
最后补充：比较流行的割位法对于三位数、四位数比较简便；但位数一多，显然这种方法比较简便。6913580247我们用这种方法只做了两次，用割位法要做9次！
做人要厚道，转帖请注明出处。
轻舟过