用户名:  密码:   
网站首页即时通讯活动公告最新消息科技前沿学人动向两岸三地人在海外历届活动关于我们联系我们申请加入
栏目导航 — 美国华裔教授专家网两岸三地百家论坛
关键字  范围   
 
学好线性代数,走遍世界都称霸
学好线性代数,走遍世界都称霸
作者:Cloud | 11/1/2018 8:32:48 AM | 浏览:261 | 评论:0

学好线性代数,走遍世界都称霸

如鱼得水

当人们在使用搜索引擎时,总会对搜索结果排名靠前的网页更信任。

在大多数人的直觉里,最重要的、可信度高的网页应该排在前面。可是,怎样判断一个网页的重要性?一个很自然的想法是:一个网页获得链接越多,可信度就越高,那么它的排名就越高。

这个看似简单的想法,正是谷歌PageRank网页排名算法的核心思想。

学好线性代数,走遍世界都称霸

图 | Pixabay

1

光看网页链接数,靠谱吗?

不过,算法实际上要复杂的多。比如,你想呀,把每个网页获得的链接从多到少排名一下可以吗?好像也不行,光是想想庞大的网络水军就知道,这样排名的注水量一定能淹了龙王庙。这很容易作弊不说,也不能反映不同网页内容和领域的差异。

假如,你是学校的招生老师,看推荐信,是看谁的信多谁厉害吗?当然不是,还要看写信的人是谁。同样的道理,我们应该看一下链过去的网页到底有多厉害。如果一个网页被很多其他网页所链接,由于有的网页重要,而有的网页很水,我们当然要对来自不同网页的链接区别对待。因而,在判断一个网页的重要性时对那些重要网页的链接应该给予大的权重,而权重又取决于它们的重要程度——被链接的次数……

这样,问题就来了。和单向的推荐信不同,所有的网页都是连在一起的,你链我、我链她、她链他,他链我,构成了一个死循环。而你评估必须要有一个起点,但是,用任何网页作为起点都不公平,怎么办?

PageRank的解决办法是:先同时把所有网站作为起点,也就是先假定所有的网页一样重要、排名相同。然后,进行迭代

2

看线代怎么解决算法难题

同时起点又该怎么做?这时候,就是线性代数非出场不可的时候了。

1996年,谷歌的创始人拉里·佩奇(Larry Page)和谢尔盖·布林(Sergey Brin)在斯坦福大学开发出PageRank。“Page”一语双关,既有网页的意思,也是佩奇的名字。当时,佩奇和布林把整个互联网当做一个整体来看待,他们认为“整个互联网就像一张大的图,每个网站就像一个节点,而每个网页的链接就像一个弧”[1]。于是,佩奇就想用一个图或者线性代数的矩阵来描述互联网。而布林把无从下手的网页相连问题变成了一个二维矩阵相乘的问题,并通过迭代,算出了网页排名。

学好线性代数,走遍世界都称霸

图1 | 四个网页之间的链接情况

【前方高能,可以不爱线代,但请不要伤害!】

布林先假定所有网页的排名是一样的:一共n个网页的话,那每个网页的最初排名都是1/n。假设一共4个网页(见图1),那每个网页的初始排名都是1/4,当我们用一个向量r来保存所有网页的排名时,r的初始值就如下所示:

学好线性代数,走遍世界都称霸

r的初始值,即所有网页的初始网页排名

然后,我们把一个网页的链接情况看作是一个向量,那么,根据图1,网页A的链接情况

学好线性代数,走遍世界都称霸

以此类推

学好线性代数,走遍世界都称霸

学好线性代数,走遍世界都称霸

这样,我们就能把所有网页之间的链接情况用一个矩阵L表示:

学好线性代数,走遍世界都称霸

列:指向外部的链接数,行:指向自己的链接数,例如,第一列表示从A指出的链接数,第一行表示箭头指向A的链接数。

我们已经知道,一个网页的重要程度,要看它被多少网页所链接;同时,对于不同的链接网页,根据它们的网页排名,我们给予不同的权重所以,网页A的排名应该等于所有指向网页A的其他网页的权重之和。而我们现在既知道所有网页的链接数——矩阵L,也知道所有网页的排名——向量r,那么,就可以算出一个网页的排名,比如网页A的排名:

学好线性代数,走遍世界都称霸

j表示第几个网页

接着,就开始迭代。当所有网页的最初排名都一样的时候,我们可以算出每个网页的第一次迭代排名。网页A、B、C、D的第一次迭代排名计算如下:

学好线性代数,走遍世界都称霸

网页BCD的第一次迭代排名依次为0.2083、 0.2083、 0.4583。

有了第一次迭代排名,我们又能算出第二次迭代排名……最终,排名r会收敛,不再变化。一般只要10次左右的迭代基本上就收敛了。而且,这种算法不需要任何人工干预。如下图,经过多次迭代,红框内的数值,就是这四个网页的最终排名:D排最前面,中间是B和C,排在最后的是A。

学好线性代数,走遍世界都称霸

图 | coursera.org- Imperial College London, Mathematics for Machine Learning:Linear Algebra

3

算出来的网页排名是真实的吗?

迭代计算的结果会收敛到网页排名的真实值吗?打比方的话,网页之间的链接关系,有点类似动物之间的食物链关系。而网页排名结果通过多次迭代、最终收敛,就有些类似于常见的兔子数量问题,在一个自然的生态环境里,不管兔子最开始的数量是多少,最终它们的数量都会达到一个稳定的值。关于网页排名计算的迭代收敛,佩奇和布林从理论上证明了不论初始值如何选取,这种算法都能保证网页排名的估计值能收敛到排名的真实值[1]。

学好线性代数,走遍世界都称霸

随着迭代次数的增加,与上一次迭代结果的总差异在变小

简言之,网页排名的的计算主要是矩阵相乘。但是,在实际运用中,这些运算其实非常复杂。另外,实际的网页数量多得惊人,巨大的矩阵相乘需要的计算量也就无法估计,而这也难不过科技大牛们,佩奇和布林又利用稀疏矩阵计算的技巧解决了庞大计算量这一问题。但是现在,对一个网页重要性的衡量是全方位的,除了要看PageRank,还要看别的数据,比如网页的内容权威性……

谷歌PageRank网页排名算法,让谷歌搜索引擎从同时代的搜索引擎中脱颖而出,也让两位创始人成为了亿万富翁。

现在,妈妈再也不用担心我不知道线性代数能干啥使了……

学好线性代数,走遍世界都称霸

 

参考文献:

[1].吴军. 数学之美[M]. 人民邮电出版社, 2012.

[2].https://www.coursera.org/lecture/linear-algebra-machine-learning/introduction-to-pagerank-hExUC

[3].Page L, Brin S, Motwani R, et al. The PageRank citation ranking:Bringing order to the web[R]. Stanford InfoLab, 1999.

[4].Brin S, Page L. The anatomy of a large-scale hypertextual web search engine[J]. Computer networks and ISDN systems, 1998, 30(1-7):107-117.

[5].https://en.wikipedia.org/wiki/PageRank

相关栏目:『百家论坛
德國弗賴堡大學研究发现:經常泡澡有助於降低抑鬱 2018-11-15 [15]
探索过敏:生命早期接触无害微生物对免疫系统的平衡至关重要 2018-11-14 [26]
Regression Analysis for Brand Assessment in Marketing Research 2018-11-14 [36]
音乐欣赏:永恒的珍藏 - 纪念柴可夫斯基逝世125周年 2018-11-06 [166]
中国资本市场重大改革:将设立科创板并试点注册制! 2018-11-06 [151]
中国依赖美国的根本不是经济 2018-11-01 [343]
希凡终归去 红楼梦未完 2018-10-31 [167]
“优秀基因”就能造就“聪明孩子”? 2018-10-30 [221]
深圳没有名牌大学和国家级研究机构,为何高科技企业蓬勃发展全国领先 2018-10-29 [163]
观摩教学示范课,教师最应该听什么? 2018-10-24 [162]
相关栏目更多文章
最新图文:
:MIT校长Rafael Reif:麻省理工学院必须与世界上最有才华的人一起行动 :全新化合物抗癌:STING激动剂联合PD-1抗体的临床试验 :京都大学医学部附属医院实施世界上首例iPS细胞治疗帕金森病手术 :探索过敏:生命早期接触无害微生物对免疫系统的平衡至关重要 :中国物理学会核物理分会集体抗议核物理被外行一夜“取消” 美寶:美國人婚姻中三件事:結婚、離婚、分財產 Alan J Pan:Regression Analysis for Brand Assessment in Marketing Research :美國華裔教授專家網盛情邀请您参加我们的2018歲末团聚晚餐(12/9)
更多最新图文
更多《即时通讯》>>
 
打印本文章
 
您的名字:
电子邮件:
留言内容:
注意: 留言内容不要超过4000字,否则会被截断。
未 审 核:  是
  
关于我们联系我们申请加入后台管理设为主页加入收藏
美国华裔教授专家网版权所有,谢绝拷贝。如欲选登或发表,请与美国华裔教授专家网联系。
Copyright © 2018 ScholarsUpdate.com. All Rights Reserved.