1701003444
X的奇幻之旅：在现实生活中发现数学思维之美 [:1701001378]
1701003445
X的奇幻之旅：在现实生活中发现数学思维之美 第24章 线性代数与强大的谷歌搜索引擎
1701003446
1701003447
在谷歌搜索引擎问世之前，网络搜索是一件很让人崩溃的事情。那时的搜索引擎常常给出一些不相关的搜索结果。而你想找的网站不是排在网站列表的第50页，就是显示根本找不到。
1701003448
1701003449
由于有了“链接分析”的算法，上述问题如今已被解决。“链接分析”算法的原理听起来像是一条似是而非的禅理：网络搜索应该反馈最佳网页。那么，什么样的网页是最佳网页呢？最佳网页是那些链接着其他最佳网页的网页。
1701003450
1701003451
这听起来有点儿循环论证的意味。事实上，这就是一个循环论证，而且这个理念的深刻之处就在于它的循环论证性。“链接分析”征服了这个循环论证，把劣势变成了优势，最终，一种柔术般的网络搜索方法横空出世了。
1701003452
1701003453
这种算法的数学基础是线性代数。线性代数是处理向量和矩阵的一种数学工具，当你想从大量数据中发现规律，或者进行含有数百万个变量的超大型计算的时候，你就需要用到线性代数。线性代数除了可以帮谷歌公司设计出“网页排序号”的搜索算法，还可用于人脸识别技术、分析高等法院的判决规律、赢得网飞（Netflix）公司的百万美元大奖等。
1701003454
1701003455
为了解释线性代数的工作原理，我们以谷歌的网页链接搜索技术为实例进行说明。当然，现实中这个技术是非常复杂的，但此处我们只看一个极度简化的模型。假设有一个迷你网络，这个网络只含有3个页面X、Y和Z，这3个页面的链接方式如下图所示。
1701003456
1701003457
1701003458
1701003459
1701003460
上图中的箭头含义如下：页面X含有页面Y的链接，但是页面Y却不含有页面X的链接。页面Y含有页面Z的链接。页面X和Z互相链接。
1701003461
1701003462
下面，我们考虑这样一个问题：在这个迷你网络中，哪个网页最重要，哪个网页最不重要？你可能会说，信息不足回答不了这个问题，因为我们完全不知道这3个网页的内容。抱歉，你的这种说法已经过时了。事实证明，通过研究网页的内容来研究网络搜索是行不通的，这种方法现在基本被淘汰了。计算机不大善于评判一个网页的内容，而我们也不可能人为地去做这件事情，毕竟每天都有成千上万的新网络页面产生。
1701003463
1701003464
谷歌的创始人拉里·佩奇和谢尔盖·布林当时还是研究生院的两个学生，他们发明了一种新的网络搜索算法：让网页自己给自己投票，不是举手投票，而是用实际行动（链接）投票。在上面的例子中，页面X和页面Y都链向页面Z，页面Z是这个迷你网络中唯一有两个外链接指向它的页面。所以，页面Z是这个迷你网络中最“流行”的网页。“流行度”是有信息含量的。但是，如果一个可疑网页链向另一个网页，那么另一个网页也应该被扣分，就像一个不可靠的人推荐的人不值得别人信任一样。“流行度”本身不说明问题，只有被好的网页“推荐”（好的网页里含有你的链接），才能获得加分。
1701003465
1701003466
于是，我们又回到了那句禅语：最佳网页是那些链接其他最佳网页的网页。但是，一开始，谁来决定哪些网页是最佳网页呢？
1701003467
1701003468
我们让网络自己来决定，具体方式如下：
1701003469
1701003470
谷歌的搜索算法给每个网页打一个分数，这个分数叫作“网页排序号”，是一个介于0和1之间的数字。“网页排序号”考虑一个假想的上网者，他会在这个网页上花掉的时间占总上网时间的多大比例？通过回答这个问题，我们可以度量一个网页相对于其他网页的重要程度。这个假想的上网者是这样上网的：如果一个网页上有另外几个网站的链接，他就会从这些链接中随机选择一个点击，点击每个链接的概率相等。在这个假设条件下，一个网页的访问量越大（我们假想的上网者的访问量，不是实际互联网用户的访问量），这个网站就越重要。
1701003471
1701003472
因为“网页排序号”的定义是（假想上网者）访问这个网站的时间占总上网时间的比例，所以网络上所有网页的“网页排序号”的总和必然为1。根据守恒定律，我们还可以把“网页排序号”想象成一股水流，这股水流在网页间流动，从体验不佳的网页不断地向体验良好的网页汇聚。谷歌的算法考察的就是，从长期来看，这股水流如何分配到网络中的各个网页中。
1701003473
1701003474
为了算出水流的分配，我们需要一个巧妙的迭代算法。首先，我们对每个网页的“网页排序号”进行一个粗略的估计，用这个猜测值作为迭代的初始值。然后，我们考虑水流如何不断地分流到新的网页中，规则是：如果一个网页上有另外几个网站的链接，假设上网者就从这些链接中随机选择一个点击，点击每个链接的概率相等。这个过程不断地进行下去，直到水停止流动，每个网页的访问量稳定下来。
1701003475
1701003476
一开始，谷歌的算法比较宽泛：每个网页的初始值都一样。比如，我们的迷你网络共有3个网页，那么每个网页的“网页排序号”的初始值都是1/3。
1701003477
1701003478
1701003479
1701003480
1701003481
然后，我们开始进行迭代计算，以便更好地估计出每个网页在网络中的重要程度。在每一轮迭代计算中，每个网页把上一轮终止时的水量（网页排序号）平均分流到它链接的各个网页中。在我们的模型里面，第一轮结束时，X的网页排序号仍然是1/3，因为只有网页Z向网页X输水，网页X从网页Z处获得了1/3的水量。网页Y的水量则下降为1/6，因为Y只获得了X一半的水量。X的另一半水量（1/6）流向了Z，同时Z还从Y处获得了1/3的水量，所以Z获得的总水量是1/2。第一轮结束时，网页X、Y和Z的水量如下图所示。
1701003482
1701003483
1701003484
1701003485
1701003486
第一轮结束，第二轮开始，水量分流的规则和上一轮一样。如果我们用（x，y，z）来表示网页X、Y、Z当前的网页排序号，那么分流的情况可以用如下的方程式来描述：
1701003487
1701003488
1701003489
1701003490
1701003491
x‘、y‘、z‘分别表示x、y、z更新后的值。这种迭代算法可以用Excel办公软件完成（对于我们的迷你网络，其实手算就可以了）。
1701003492
1701003493
经过10轮迭代计算，我们会发现页面X、Y、Z的网页排序号的值趋于稳定，再继续进行迭代计算的话，每轮数值的改变很小。10轮迭代计算之后，X获得40.6%的水量，Y获得19.8%的水量，Z获得39.6%的水量。这3个数字分别趋近于40%、20%、40%。我们可以猜测，这些数值已经向均衡状态收敛，而均衡状态的值正是40%、20%、40%。