打字猴:1.701003444e+09
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%。
[ 上一页 ]  [ :1.701003444e+09 ]  [ 下一页 ]