中国的博客,走近我们的产品、技术和文化
Google 中国的博客,走近我们的产品、技术和文化
数学之美 系列十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)
2006年11月28日
Google 研究员 吴军
自从有了搜索引擎,就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的,用句俗话说,闪光的不一定是金子。
搜索引擎的作弊,虽然方法很多,目的只有一个,就是采用不正当手
段提高自己网页的排名。早期最常见的作弊方法是重复关键词
。比如一个卖数码相机的网站,重复地罗列各种数码相机的品牌,如尼康
、佳能和柯达等等。为了不让读者看到众多讨厌的关键词
,聪明一点的作弊者常用很小的字体和与背景相同的颜色来掩盖这些
关键词。其实,这种做法很容易被搜索引擎发现并纠正。
在有了网页排名
(page rank)以后,作弊者发现一个网页被引用的连接越多,排名就可能越靠前
,于是就有了专门卖链接和买链接的生意。比如,有人自己创建成百
上千个网站,这些网站上没有实质的内容,只有到他们的客户网站的
连接。这种做法比重复关键词要高明得多,但是还是不太难被发现
。因为那些所谓帮别人提高排名的网站,为了维持生意需要大量地卖链
接,所以很容易露马脚。(这就如同造假钞票,当某一种假钞票的流通量相当大以后,就容易找到根源了。)再以后,又有了形形色色的作弊方式
,我们就不在这里一一赘述了。
几年前,我加入Google做的第一件事就是消除网络作弊
。在Google最早发现搜索引擎作弊的是Matt Cutts,他在我加入Google前几个月开始研究这个问题
,后来,辛格,马丁和我先后加入进来。我们经过几个月的努力
,清除了一半的作弊者。(当然,以后抓作弊的效率就不会有这么高了。
)其中一部分网站从此"痛改前非",但是还是有很多网站换一种作弊方法
继续作弊,因此,抓作弊成了一种长期的猫捉老鼠的游戏
。虽然至今还没有一个一劳永逸地解决作弊问题的方法,但是
,Google基本做到了对于任何已知的作弊方法
,在一定时间内发现并清除它,从而总是将作弊的网站的数量控制在一
个很小的比例范围。
抓作弊的方法很像信号处理中的去噪音的办法。学过信息论和有信号
处理经验的读者可能知道这么一个事实,我们如果在发动机很吵的汽
车里用手机打电话,对方可能听不清;但是如果我们知道了汽车发动
机的频率,我们可以加上一个和发动机噪音相反的信号
,很容易地消除发动机的噪音,这样,收话人可以完全听不到汽车的噪音
。事实上,现在一些高端的手机已经有了这种检测和消除噪音的功能
。消除噪音的流程可以概括如下:
在图中,原始的信号混入了噪音,在数学上相当于两个信号做卷积
。噪音消除的过程是一个解卷积的过程。这在信号处理中并不是什么
难题。因为第一,汽车发动机的频率是固定的,第二
,这个频率的噪音重复出现,只要采集几秒钟的信号进行处理就能做
到。从广义上讲,只要噪音不是完全随机的、并且前后有相关性
,就可以检测到并且消除。(事实上,完全随机不相关的高斯白噪音
是很难消除的。)
搜索引擎的作弊者所作的事,就如同在手机信号中加入了噪音
,使得搜索结果的排名完全乱了。但是,这种人为加入的噪音并不难
消除,因为作弊者的方法不可能是随机的(否则就无法提高排名了)
。而且,作弊者也不可能是一天换一种方法,即作弊方法是时间相关
的。因此,搞搜索引擎排名算法的人,可以在搜集一段时间的作弊信
息后,将作弊者抓出来,还原原有的排名。当然这个过程需要时间
,就如同采集汽车发动机噪音需要时间一样,在这段时间内
,作弊者可能会尝到些甜头。因此,有些人看到自己的网站经过所谓
的优化(其实是作弊),排名在短期内靠前了,以为这种所谓的优
化是有效的。但是,不久就会发现排名掉下去了很多。这倒不是搜索引擎
以前宽容,现在严厉了,而是说明抓作弊需要一定的时间
,以前只是还没有检测到这些作弊的网站而已。
还要强调一点
,Google抓作弊和恢复网站原有排名的过程完全是自动的(并没有个人的好恶)
,就如同手机消除噪音是自动的一样。一个网站要想长期排名靠前
,就需要把内容做好,同时要和那些作弊网站划清界限。
Google(谷歌)全球编程挑战赛中国获奖选手(花絮)
2006年11月20日
发表者:吴丹丹,Google 黑板报小组
2006 年 Google(谷歌)全球编程挑战赛刚刚落下帷幕,来自中国的选手王颖夺得本次比赛的第二名,另有 6 名选手进入前 50 名,本次比赛共有 13 名中国选手成功入围前 100 名,据了解,此次中国进入决赛的选手人数仅次于俄罗斯。这里与大家分享一些比赛的小花絮。
“我是中国人!”
“我是中国人!我希望能与中国同胞分享我的喜悦!” 这是来自中国的王颖在获得 2006 Google(谷歌)编程大赛亚军后写给 Google(谷歌)的第一句话。他的自豪溢于言表,这位身高近 1.9 米的年仅 22 岁的小伙子毕业于中山大学,目前正在美国斯坦福大学攻读数学博士学位。
这位说自己不是天才,只在初中跳过一次级的王颖在接受访问时谦虚地说他能获得第二名要归功于好运和不错的临场发挥,但了解了他的经历之后发现他的获奖并不是简单的幸运和临场发挥。王颖可以说是世界顶级编程大赛的常客,多次入围全球著名编程赛事 ACM,Topcoder,微软创新杯等比赛的决赛。在今年的决赛中,王颖凭借自己扎实的数学功底及严谨的逻辑思维,成功地完成了难度值最大的题,并且在最后的 PK 环节胜出。
获得第二名之后,王颖说自己一直就有冠军梦,虽然这次离冠军还有一步之遥,他说他已经很满足了,对自己的冠军梦不会有遗憾了。
“中国造” 的编程神童
除了王颖获奖,来自广东中山的高三学生余江伟也很突出。作为今年决赛中唯一的一名中学生选手,年纪最小的余江伟显得格外的引人注目,在强手林立的决赛中,余江伟最终获得了全球第 96 名的好成绩。
余江伟从小就对编程有浓厚的兴趣,并在这方面展示出了非凡的才能。还在小学就读四年级期间,余江伟就夺得了全国国际象棋冠军,出色的逻辑思维和能力使他在计算机编程方面很早就显示了非凡的才能,在参加 Google(谷歌)的编程大赛之前,他在 7 月份的全国信息学奥林匹克大赛中获得了一等奖。他是无意中在网上获知 Google(谷歌)编程大赛的相关信息,报着试试看的心态报名参加了比赛。在随后的预赛中,余江伟经过三轮‘厮杀’,成功地以预赛第 22名的成绩入围决赛。
在本次比赛中晋级全球百强的 13 名中国选手中,有 11 人来自于高校。4 名来自清华大学的学生全部进入了前 50强,有一位来自复旦大学的学生获得了第十五名的成绩,是仅次于王颖的第二好成绩。
数学之美 系列十六 (下)- 不要把所有的鸡蛋放在一个篮子里 最大熵模型
2006年11月16日
发表者:Google 研究员,吴军
我们
上次谈到
用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答,就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式,现在只需要确定指数函数的参数就可以了,这个过程称为模型的训练。
最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂,大致可以概括为以下几个步骤:
1. 假定第零次迭代的初始模型为等概率的均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则,将它们便大。
3. 重复步骤 2 直到收敛。
GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是,这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨(Csiszar)解释清楚的,因此,人们在谈到这个算法时,总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长,需要迭代很多次才能收敛,而且不太稳定,即使在 64 位计算机上都会出现溢出。因此,在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。
八十年代,很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进,提出了改进迭代算法 IIS(improved iterative scaling)。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此,在当时也只有 IBM 有条件是用最大熵模型。
由于最大熵模型在数学上十分完美,对科学家们有很大的诱惑力,因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似,最大熵模型就变得不完美了,结果可想而知,比打补丁的凑合的方法也好不了多少。于是,不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的,是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似,而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题,比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性(名词、动词和形容词等)、句子成分(主谓宾)通过最大熵模型结合起来,做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统,至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中,又看到了用最大熵模型解决复杂的文字信息处理的希望。
但是,最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天,我对我的导师说,我发现一种数学变换,可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时,他没有找出我的推导中的任何破绽,接着他又回去想了两天,然后告诉我我的算法是对的。从此,我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后,为了训练一个包含上下文信息,主题信息和语法信息的文法模型(language model),我并行使用了 20 台当时最快的 SUN 工作站,仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂,到今天为止,世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读
我的论文
。
最大熵模型,可以说是集简与繁于一体,形式简单,实现复杂。值得一提的是,在Google的很多产品中,比如机器翻译,都直接或间接地用到了最大熵模型。
讲到这里,读者也许会问,当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗?他们在九十年代初贾里尼克离开 IBM 后,也退出了学术界,而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大,但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道,决定股票涨落的因素可能有几十甚至上百种,而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮垂兄弟等科学家在那里,用于最大熵模型和其他一些先进的数学工具对股票预测,获得了巨大的成功。从该基金 1988 年创立至今,它的净回报率高达平均每年 34%。也就是说,如果 1988 年你在该基金投入一块钱,今天你能得到 200 块钱。这个业绩,远远超过股神巴菲特的旗舰公司伯克夏哈撒韦(Berkshire Hathaway)。同期,伯克夏哈撒韦的总回报是 16 倍。
值得一提的是,信息处理的很多数学手段,包括隐含马尔可夫模型、子波变换、贝叶斯网络等等,在华尔街多有直接的应用。由此可见,数学模型的作用。
標籤
编程之夏,UR
创新
创意改善社会 公益温暖中国
促进智能能源利用
大学
谷歌翻译,即时相机翻译,Instant Camera Translation
谷歌十周年系列
谷歌艺术与文化
观妙中国,Shadow Art,智玩皮影
广告
广告安全
互联网,Internet
科技
女性开发者
社会
视频广告
数据中心
数字营销
搜索
网站管理员
文化研究所
艺术计划
音乐搜索
愚人节
增强型广告系列
智能隐形眼镜项目
中小企业
adexchange
Admob
admob sdk
Ads
Adsense
AdWords
android
android m
Android应用开发中国大学生挑战赛
App Inventor
Calendar
cardboard
CES
Chrome
Chrome Web Store
Chrome,Chrome实验
Chrome实验
CI
Code Jam
corporate
Creative
Cross-device
Cultural Institute
culture
Data Center
DevArt
Developer
display
diversity
Doodle
DoubleClick
G+
G2G,Culture
GA&C
gaming
Global Impact Awards
Gmail
Gogle科学挑战赛
Good to Know
Google Ads
Google AdWords
Google Analytics
Google Art Project
Google Arts & Culture
Google Code-in竞赛
Google Demo Day Asia
Google Docs
Google Doodle
Google Drive
Google Drive 云端硬盘
Google Fiber
Google Font
Google for Startups
Google Green
Google I/O
Google Image Search
Google Keep
Google partners
Google Play
Google Science Fair
Google Search
Google Top Contributor Summit
Google Translate
Google Trend
Google Trends
Google Zeitgeist 2012
Google安全系统
Google博士生奖研金
Google翻译
Google奖学金
Google杰出贡献者峰会
Google科学挑战赛
Google网站管理员
Google网站管理员,Webmaster
Google文化研究所
Google在线营销挑战赛
Google中国教育高峰会
IME 输入法
Innovation
Made with Code
maps
mobile ads
mobile ads sdk
Modoo
moonshot
native ads
Nexus
programmatic buying
Project X
Pwn20wn及Pwnium3 黑客大赛
Remarketing. Ads
Search
Security
smb
Solve for X
Street view
student
UR
VR
Web Platform Docs
web security
Webmaster
year in search 2014
YouTube
zeitgeist
博客归档
2024
12月
11月
10月
8月
7月
6月
5月
4月
3月
2月
1月
2023
12月
11月
10月
9月
5月
4月
3月
2月
2022
11月
10月
5月
4月
2月
1月
2021
10月
9月
5月
4月
3月
2月
2020
12月
5月
4月
3月
2019
10月
8月
7月
6月
5月
4月
3月
2018
12月
10月
9月
8月
7月
6月
5月
3月
2月
1月
2017
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2016
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2013
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2012
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2011
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2010
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2009
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2008
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2007
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2006
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
Feed