［坡仔跟你一起阅读好书·第九十九期］《X的奇幻之旅》Part 5 数据——第二十四章 线性代数与强大的谷歌搜索引擎
世界级数学家、《纽约时报》专栏作者史蒂夫·斯托加茨，引领我们踏上一段领略最伟大的数学思想的赏心悦目之旅。沿途中你会看到数学如何与文学、哲学、法律、医学、艺术、商业彼此交融，甚至流行文化也能以我们意想不到的方式和数学共舞。
辛普森到底有没有谋杀他的前妻?多长时间、以何种方式翻转你的床垫才会让它的磨损率最小?谷歌搜索引擎是如何找到你想要的网页的?在步入婚姻殿堂之前，你应该和多少位异性约会?不管你相不相信，数学在回答这些问题以及更多其他问题时，都扮演着至关重要的角色。
数学是宇宙万物存在的基础，当然也包括人类，但是我们中却很少有人能很好地掌握这门通用语言，体验它的智慧、美丽和乐趣。这本启迪智慧而又妙趣横生的书旨在对专业、枯燥的数学语言进行翻译，帮助广大对数学感到恐惧、陌生或是不理解的读者，重新认识和欣赏数学之美。
在这段从企鹅吃鱼到无穷大的数学之旅中，每一章都是一道美丽的“风景”:斑马身上的黑白条纹中的正弦波;美国《独立宣言)中欧几里得几何定理的身影;流星雨划过夜空时留下的美丽抛物线;罗密欧和朱丽叶爱情悲剧背后的微积分方程式;拆穿小布什减税计划谎言的长尾分布......
虽然真正喜欢数学、了解数学的人为数不多，但每个人都离不开数学，相信读完这本书后，不少人会从此爱上数学，成为“数学发烧友”。
［美］史蒂夫·斯托加茨◎著
［中］鲁冬旭◎译
第二十四章 线性代数与强大的谷歌搜索引擎
在谷歌搜索引擎问世之前，网络搜索是一件很让人崩溃的事情。那时的搜索引擎常常给出一些不相关的搜索结果。而你想找的网站不是排在网站列表的第50页，就是显示根本找不到。
由于有了“链接分析”的算法，上述问题如今已被解决。“链接分析”算法的原理听起来像是一条似是而非的禅理:网络搜索应该反馈最佳网页。那么，什么样的网页是最佳网页呢?最佳网页是那些链接着其他最佳网页的网页。
这听起来有点儿循环论证的意味。事实上，这就是一个循环论证，而且这个理念的深刻之处就在于它的循环论证性。“链接分析”征服了这个循环论证，把劣势变成了优势，最终，一种柔术般的网络搜索方法横空出世了。
这种算法的数学基础是线性代数。线性代数是处理向量和矩阵的一种数学工具，当你想从大量数据中发现规律，或者进行含有数百万个变量的超大型计算的时候，你就需要用到线性代数。线性代数除了可以帮谷歌公司设计出“网页排序号”的搜索算法，还可用于人脸识别技术、分析高等法院的判决规律、赢得网飞(Netflix)公司的百万美元大奖等。
为了解释线性代数的工作原理，我们以谷歌的网页链接搜索技术为实例进行说明。当然，现实中这个技术是非常复杂的，但此处我们只看一个极度简化的模型。假设有一个迷你网络，这个网络只含有3个页面X、Y和Z，这3个页面的链接方式如下图所示。
上图中的箭头含义如下:页面X含有页面Y的链接，但是页面Y却不含有页面X的链接。页面Y含有页面Z的链接。页面X和Z互相链接。
下面，我们考虑这样一个问题:在这个迷你网络中，哪个网页最重要，哪个网页最不重要?你可能会说，信息不足回答不了这个问题，因为我们完全不知道这3个网页的内容。抱歉，你的这种说法已经过时了。事实证明，通过研究网页的内容来研究网络搜索是行不通的，这种方法现在基本被淘汰了。计算机不大善于评判一个网页的内容，而我们也不可能人为地去做这件事情，毕竟每天都有成千上万的新网络页面产生。
谷歌的创始人拉里·佩奇和谢尔盖·布林当时还是研究生院的两个学生，他们发明了一种新的网络搜索算法:让网页自己给自己投票，不是举手投票，而是用实际行动(链接)投票。在上面的例子中，页面X和页面Y都链向页面Z，页面Z是这个迷你网络中唯一有两个外链接指向它的页面。所以，页面Z是这个迷你网络中最“流行”的网页。“流行度”是有信息含量的。但是，如果一个可疑网页链向另一个网页，那么另一个网页也应该被扣分，就像一个不可靠的人推荐的人不值得别人信任一样。“流行度”本身不说明问题，只有被好的网页“推荐”(好的网页里含有你的链接)，才能获得加分。
于是，我们又回到了那句禅语:最佳网页是那些链接其他最佳网页的网页。但是，一开始，谁来决定哪些网页是最佳网页呢?
我们让网络自己来决定，具体方式如下:
谷歌的搜索算法给每个网页打一个分数，这个分数叫作“网页排序号”是一个介于0和1之间的数字。“网页排序号”考虑一个假想的上网者，他会在这个网页上花掉的时间占总上网时间的多大比例?通过回答这个问题，我们可以度量一个网页相对于其他网页的重要程度。这个假想的上网者是这样上网的:如果一个网页上有另外几个网站的链接，他就会从这些链接中随机选择一个点击，点击每个链接的概率相等。在这个假设条件下，一个网页的访问量越大(我们假想的上网者的访问量，不是实际互联网用户的访问量)，这个网站就越重要。
因为“网页排序号”的定义是(假想上网者)访问这个网站的时间占总上网时间的比例，所以网络上所有网页的“网页排序号”的总和必然为1。根据守恒定律，我们还可以把“网页排序号”想象成一股水流，这股水流在网页间流动，从体验不佳的网页不断地向体验良好的网页汇聚。谷歌的算法考察的就是，从长期来看，这股水流如何分配到网络中的各个网页中。
为了算出水流的分配，我们需要一个巧妙的迭代算法。首先，我们对每个网页的“网页排序号”进行一个粗略的估计，用这个猜测值作为迭代的初始值。然后，我们考虑水流如何不断地分流到新的网页中，规则是:如果一个网页上有另外几个网站的链接，假设上网者就从这些链接中随机选择一个点击，点击每个链接的概率相等。这个过程不断地进行下去，直到水停止流动，每个网页的访问量稳定下来。
一开始，谷歌的算法比较宽泛:每个网页的初始值都一样。比如，我们的迷你网络共有3个网页，那么每个网页的“网页排序号”的初始值都是1/3。
然后，我们开始进行迭代计算，以便更好地估计出每个网页在网络中的重要程度。在每一轮迭代计算中，每个网页把上一轮终止时的水量(网页排序号)平均分流到它链接的各个网页中。在我们的模型里面，第一轮结束时，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的水量如下图所示。
第一轮结束，第二轮开始，水量分流的规则和上一轮一样。如果我们用(x,y,z)来表示网页X、Y、Z当前的网页排序号，那么分流的情况可以用如下的方程式来描述:
x'、y'、z'分别表示x、y、z更新后的值。这种迭代算法可以用Excel办公软件完成(对于我们的迷你网络，其实手算就可以了)。
经过10轮迭代计算，我们会发现页面X、Y、Z的网页排序号的值趋于稳定，再继续进行迭代计算的话，每轮数值的改变很小。10轮迭代计算之后，X获得40.6%的水量，Y获得19.8%的水量，Z获得39.6%的水量。这3个数字分别趋近于40%、20%、40%。我们可以猜测，这些数值已经向均衡状态收敛，而均衡状态的值正是40%、20%、40%。
谷歌也是利用这样的算法，把均衡状态下的极限值记为每个网页的网页排序号。
这个算法的结论是，在这个迷你网络中，虽然有两个外链接指连向网页Z，但是网页X和网页Z其实一样重要。这个结果并不奇怪，因为Z用全部流量支持X，而 X却只用一半流量回报Z，把另一半给了Y。这也解释了为什么网页Y的最终得分是 X和Z的 1/2。
神奇的是，这个最终得分可以直接算出，而不需要经过这个复杂的迭代计算过程。想一想，均衡的定义是什么?如果系统不再发生变化，那就说明系统已经达到了稳定的“均衡状态”，所以均衡状态的定义就是x'=x，y'=y，z'=z。把这3个方程式代入上面的方程组，我们就得到:
很容易解出x=2y=z。最后，别忘了x、y、z这3个数字之和为1。所以，最后的答案是x=2/5，y=1/5，z=2/5。这个得数和我们迭代计算的结果是完全一致的。
这道题已经解决了，接下来我们应该研究一下这道题和线性代数到底有什么关系。不管是表示均衡状态的方程组，还是上面表示x、y、z更新变化的方程组都是典型的线性方程式。这种方程式之所以叫作线性方程式，是因为它们和直线有关。在这些方程式里，所有变量都是一次方的形式，与中学代数课上的直线方程式(一次方程式)y=mx+b的形式完全一样。
与非线性方程式相比(比如含有x的平方、yz、sinx等项的方程)，线性方程式是比较容易求解的。但是如果线性方程组有很多个未知数，问题就变得比较复杂，互联网的情况正是如此。线性代数的核心目标之一，就是不断发明更快、更有效率的算法，去求解巨大的线性方程组。线性方程组解法、算法上的细微提高，就会给我们的日常生活带来极大的便利:航班排期会更合理，图像压缩技术会更有效率，网络搜索会更快速准确。
线性代数在现实世界中最大的胜利，可能要算网络搜索问题的解决了。“什么样的网页是最佳网页呢?最佳网页是那些链接着其他最佳网页的网页”，这句话用数学语言来表述，就是网页排序号的线性方程组。
谷歌使用的线性方程组和我们上面求解的方程组并无本质区别，只不过我们的方程组只有3个未知数，而谷歌要解决的方程组却有数十亿个未知数。当然，对谷歌来说，解出这数十亿个未知数，意味着会有数十亿美元的利润入账。