Archive for 2012年六月

SEO装逼指南

当你说我是SEO时,高手肯定说现在我在做的是SEM。

当你说我是SEM时,高手肯定在说我现在在做MKT。

你怒了:为什么你总走在我前面?

高手看着你无辜的眼神:因为你比我先说!

你说我做热词排名,高手说我在做长尾建设。

你说我在群发长尾链接,高手说我在做站内优化。

你在说我在做站内优化,高手说我在做整站架构。

你说我在做整站架构,高手说我在做数据分析。

你说我在做数据分析,高手说我在做流程分析。

你说我也来做流程分析了,高手说我已经在做行为分析了。

你说我在做行为分析了,高手说我在努力提高转化率。

你说我们转化率正在提高,高手说我们的口碑营销已经出效果了。

你怒了:你是不是SEO了啊? readmore

猎狗兔子

一条猎狗将兔子赶出了窝,一直追赶他,追了很久仍没有捉到。

牧羊看到此种情景,讥笑猎狗说"你们两个之间小的反而跑得快得多。"

猎狗回答说:"你不知道我们两个的跑是完全不同的!我仅仅为了一顿饭而跑,他却是

为了性命而跑呀!"

...........................目标.... ............................

 

这话被猎人听到了,猎人想:猎狗说的对啊,那我要想得到更多的猎物,得想个好法子.

于是,猎人又买来几条猎狗,凡是能够在打猎中捉到兔子的,就可以得到几根骨头,捉不到

的就没有饭吃.这一招果然有用,猎狗们纷纷去努力追兔子,因为谁都不愿意看着别人有

骨头吃,自已没的吃.就这样过了一段时间,问题又出现了.大兔子非常难捉到,小兔子好

捉.但捉到大兔子得到的奖赏和捉到小兔子得到的骨头差不多,猎狗们善于观察,发现了

这个窍门,专门去捉小兔子.慢慢的,大家都发现了这个窍门.猎人对猎狗说:最近你们捉

的兔子越来越小了,为什么?猎狗们说:反正没有什么大的区别,为什么费那么大的劲去捉

那些大的呢?

................................动力.........................

 

猎人经过思考后,决定不将分得骨头的数量与是否捉到兔子挂钩,而是采用每过一段时

间,就统计一次猎狗捉到兔子的总重量.按照重量来评价猎狗,决定一段时间内的待遇.

于是猎狗们捉到兔子的数量和重量都增加了.猎人很开心.

但是过了一段时间,猎人发现,猎狗们捉兔子的数量又少了,而且越有经验的猎狗,捉兔子

的数量下降的就越利害.于是猎人又去问猎狗.

猎狗说"我们把最好的时间都奉献给了您,主人,但是我们随着时间的推移会老,当我们捉

不到兔子的时候,您还会给我们骨头吃吗?"

............................长期的骨头........................

 

猎人做了论功行赏的决定.分析与汇总了所有猎狗捉到兔子的数量与重量,规定如果捉到

的兔子超过了一定的数量后,即使捉不到兔子,每顿饭也可以得到一定数量的骨头. 猎狗

们都很高兴,大家都努力去达到猎人规定的数量.一段时间过后,终于有一些猎狗达到了

猎人规定的数量.这时,其中有一只猎狗说:我们这么努力,只得到几根骨头,而我们捉的

猎物远远超过了这几根骨头.我们为什么不能给自己捉兔子呢?"于是,有些猎狗离开了猎

人,自己捉兔子去了.

.............................骨头与肉兼而有之...........

 

猎人意识到猎狗正在流失,并且那些流失的猎狗像野狗一般和自己的猎狗抢兔子。

情况变得越来越糟,猎人不得已引诱了一条野狗,问他到底野狗比猎狗强在那里。

野狗说:“猎狗吃的是骨头,吐出来的是肉啊!”,接着又道:“也不是所有的野狗都

顿顿有肉吃,大部分最后骨头都没的舔!不然也不至于被你诱惑。” 于是猎人进行了

改革,使得每条猎狗除基本骨头外,可获得其所猎兔肉总量的n,而且随着服务时间加

长,贡献变大,该比例还可递增,并有权分享猎人总兔肉的m。就这样,猎狗们与猎人

一起努力,将野狗们逼得叫苦连天,纷纷强烈要求重归猎狗队伍。

 

 

故事还在继续................

 

--------------------只有永远的利益,没有永远的朋友--------------

 

日子一天一天地过去,冬天到了,兔子越来越少,猎人们的收成也一天不如一天。而那

些服务时间长的老猎狗们老得不能捉到兔子,但仍然在无忧无虑地享受着那些他们自以

为是应得的大份食物。终于有一天猎人再也不能忍受,把他们扫地出门,因为猎人更需

要身强力壮的猎狗。。。。。

 

--------------------- Birth of MicroBone Co. --------------

 

被扫地出门的老猎狗们得了一笔不菲的赔偿金,于是他们成立了MicroBone公司。他们

采用连锁加盟的方式招募野狗,向野狗们传授猎兔的技巧,他们从猎得的兔子中抽取一

部分作为管理费。当赔偿金几乎全部用于广告后,他们终于有了足够多的野狗加盟。公

司开始赢利。一年后,他们收购了猎人的家当...

 

------Development of MicroBone Co. -----------------------

 

MicroBone公司许诺给加盟的野狗能得到公司n的股份。这实在是太有诱惑力了。这些

自认为是怀才不遇的野狗们都以为找到了知音:终于做公司的主人了,不用再忍受猎人

们呼来唤去的不快,不用再为捉到足够多的兔子而累死累活,也不用眼巴巴地乞求猎人

多给两跟骨头而扮得楚楚可怜。这一切对这些野狗来说,这比多吃两根骨头更加受用。

于是野狗们拖家带口地加入了MicroBone,一些在猎人门下的年轻猎口也开始蠢蠢欲

动,甚至很多自以为聪明实际愚蠢的猎人也想加入。好多同类型的公司象雨后春笋般地

成立了,BoneEase, Bone.com, ChinaBone....一时间,森林里热闹起来。

 

总结。

以人为本,合理分配,善于激励、利益共享才能使员工稳定工作,企业稳定发展,作为人力资源管理者要不断、及时的了解员工的需求,针对员工的需求不断调整管理的思路,并制定相关的制度才能让员工发挥更大的潜能

为什么不参加企业的“拓展训练”

保险很像传销,所以我怕保险
大跃进似的口号高呼,无感
争先恐后的举手发言,无感
深情剖白的分享表态,无感

而拓展也是一样
每一个活动都是总结,每一次体验都有预设,每一种感受都被设计,
以相似的形式,装载相近的内容,得出相同的结论,
军事化训练,统一思想,宣传,煽情,然后抱头痛哭。。。。

当一群或成熟、或木然、或嚣张、或淡定的千姿百态之人,在拓展结束时,表情以感激涕零
当训练师以一副上帝的样子,注视着来自祖国各地的每一群高官子弟、平头百姓、菜鸟新丁,宣示神的旨意
我有一种被玩弄于鼓掌的可笑

大茶壶、背摔、抱团……知道后面还是静态运动之后,更是无比失望

就好比说团队和个人的矛盾吧,在拓展培训的时候,教官就是要我们知道,团队合作的重要性等等,但是游戏归游戏,道理虽然大家都懂,但是基本不可能移植到工作中,一旦与金钱挂钩的东西,在当今这个世界永远是个人利益高于一切!

在不到生死存亡的边缘,人们基本是不懂得团结的,别告诉我抗日时期,全国人民是如何团结的,那也要结合当时的大背景来说吧!

让我感觉最搞笑的是那个所谓的毕业墙:要大家在不借助任何外力的情况下一起爬上4米高的墙上去,那么究竟怎么爬呢,那就是搭人墙了,几个人在底下当墩子,先让一个人爬上去,然后在让上面那个人在上面拉从下面送上去的人!虽然,这个项目是通过了,但是这个要移植到工作中,基本上是不可能的。

没有人愿意当他人的垫脚石,我们来试想一下:

第一个被推上去的我们把他当做领导:如果这个人上去以后专搞破坏,那么这个项目就不要想完成了。在工作中,如果那个曾经把你当做垫脚石的人当上领导后,却不在管你的死活,你还会像游戏训练中那么无怨无悔吗?!

还记得两年多以前入职军训的时候培训部的老师领着我们做游戏,每个环节都有预谋,每个环节都被设计,我们分组竞争,选出自己的Leader,让他肩负责任,游戏难度不断加大,每个组的Leader都会被惩罚,有脑子的人都知道这是时间问题,最后培训师放起煽情的音乐,朗诵他准备好的稿子,大家都哭了,培训师嘴角露出一丝不易察觉的自豪。两年以后,这场洗脑有什么效果呢?该辞职的照样辞职,连培训师都跳槽了,能提升企业团队的凝聚力么?

当大家都在写拓展的时候我没有写,因为我突然发现,我居然也开始反思,我开始从活动中寻找结论,我开始投入其中发现自己的弱点
传销的理念就是准军事化的管理,对人性的掌控、统一思想,高度集中,相信组织
当我们相信集体主义、有成功欲求、又怀疑自己的时候,传销即可存在了,也是所有组织存在的可能
也许有了真正的产品,传销也就合法了
以上内容全部整理自互联网,不代表本人观点,不要喷我,希望能帮助需要帮助的人。


				

搜索引擎中的粒度问题@baidu-tech

一.前言

传统的搜索引擎的定义,是指一种对于指定的查询(Query),能够返回与之相关的文档集合(Documents)的系统。而百度将这个定义更加丰富化,即搜索引擎能够帮助人们更方便的找到所求。这里的“所求”,比“文档”更加宽泛和丰富,比如一个关于天气的查询,直接返回一个天气预报的窗口,而非一篇关于天气的文档;再如一个关于小游戏的查询,直接返回这个小游戏的Flash页面而非简单的介绍性的文字。

百度对Query深刻的理解,源于自然语言处理技术在其中发挥的巨大作用。对搜索引擎而言,文本切分是最基础也是最重要的自然语言问题之一。今天,我们就来谈谈文本切分粒度与搜索引擎的关系。

本文后续章节组织如下:第二节介绍什么是文本的粒度,第三节讲述搜索引擎的基本原理与文本切分粒度的关系,第四节深入探讨粒度的属性与检索相关性计算,第五节小结。

 

二.文本粒度

什么是文本的粒度?我们用什么来衡量文本粒度?在回答这些问题前,让我们先看看以下几组词汇:

缠绵、崎岖、葡萄、乒乓

绿茶、篮球、红色、鼠标垫、起重机

打球、跳绳、炒菜、登山

笔记本电脑、高清机顶盒、IP电视

但是、然后、如果、非常

步步惊心、家的n次方、一个人的精彩

百度在线网络技术(北京)有限公司、清华大学

张学友、赵传、工藤新一、里奥内尔·安德雷斯·梅西

……

这几组词汇中,哪些的粒度大,哪些的粒度小?

不管在传统的语言学领域,还是在自然语言处理领域,都没有对粒度下一个清晰准确的定义。但是就搜索引擎而言,我们不妨这样定义:粒度是衡量文本所含信息量的大小。文本含信息量多,粒度就大,反之就小。有了这个原则,我们就很容易判断文本粒度大小了。像“缠绵”,“崎岖”,“葡萄”这些词,虽然有两个字组成,但是仅表达一个意思,这些词的粒度是小的。而“篮球”,“鼠标垫”等词,是由简单词合成的,虽然也只有一个意思,但还可以拆分,如“篮”和“球”,“鼠标”和“垫”。这类词,粒度稍微大一些。而“笔记本电脑”,“高清机顶盒”这样的词,粒度就更大了。

专名是一类比较特殊的词,尽管所含字数很多,但其实只表达一个意思,如“步步惊心”,“家的n次方”这样的电影、电视剧的名称,粒度是很小的。机构名、人名等属于有内部结构的专名,比电影名的粒度稍大一些。

显然易见,我们在讨论文本粒度时,理想的方式是从语义角度出发,合理的分析和判断。然而以上我们仅对粒度做了定性的分析,为粒度找一个合适的度量单位和计算方法,是百度人一直追求的目标。

三.搜索引擎的基本原理与词汇切分关系

3.1 搜索引擎的基本原理

文本检索系统,是搜索引擎最简单的实现方式。通过返回包含关键字的页面,来满足用户的检索需求。形式化的表达就是给定一系列关键字集合K,要求返回所有包含关键字的文档D,对D中的任意一个文档d,包含K中的任意一个关键字k。

一般我们采用倒排索引的方式来实现这个系统。所谓倒排索引,就是对关键字建立索引,记录包含这个关键字的文档集合D。对于请求的关键字集合,找出所有关键字对应的索引,并对索引求交,最后返回同时存在于所有索引中的文档。

在百度,我们不仅允许用户输入关键字,也可以输入任何长度在一定范围内的文本。此时我们需要对文本做一定处理,切分成一系列关键字,从而能够从倒排索引中找出对应的文档。

那么为什么要对输入文本做切分,如果不切分会有什么问题?

我们可以想象一下,如果不对输入文本做切分,直接用输入文本去做匹配,会怎么样?首先,得到的结果会非常少,因为直接用全部文本匹配,就失去了灵活性,对结果限制的非常死,必须完全匹配才能满足要求;其次,系统性能会非常差,因为需要对所有长度的文本都建立索引,这是指数级的,在实际系统中根本不可能实现。再考虑一下另一个极端?我们对输入文本做单字切分,结果又是怎样?我们会得到大量无关的页面,不仅浪费系统性能,对相关性计算也造成了巨大的压力。

所以,我们需要对文本做一个合适的切分。

3.2 用户满意度与粒度关系

无论是建立倒排索引、还是处理输入文本,我们都需要对文本做切分,切出合适的关键字出来。为了能够使用户对查询结果满意,搜索引擎需要什么样的粒度?让我们先看一下下面几个例子:

1. Q:“北京地图” P1:“北京市地图” P2:“北京城市地图”

2. Q:“闹太套是神马意思”, P:”A:神呐,我骑不了这烈马。B:闹太套!”

3. Q:“兽兽门” P:“兽兽艳照门”

4. Q1:“工业园” Q2:“园区” P:“工业园区”

5. Q:“ip电视” P1:“ip电视的历史” P2:“电视销售…您的IP是xxx”

注:Q表示query,P表示页面中包含Q的内容

Case1,要求query能找到P1和P2这样的结果,就必须对P1和P2都切出“北京”这个词来。Case2,必须把”神马”切为一个词,否则会召回P这样不相关的结果。Case3,不能把Q中的“兽兽门“切为一个词,而需要切除“兽兽”,否则就召不回”兽兽艳照门”这个结果。Case4中,对“工业园区”这样的页面,必须同时切出“工业园”和“园区”这两个重叠的词汇,才能保证Q1和Q2都能召回。Case5与Case2类似,如果把ip和电视分开切分,将召回P2这样不相关的结果。

以上几个case,基本上概括了搜索引擎对切分粒度的要求,我们可以从两方面来描述:1)影响召回 2)影响相关性

以上从用户满意度的角度,讨论了搜索引擎与粒度的关系,当然,这是最基本的要求,在第四节我们还会对文本的粒度问题做更深入的分析。

3.3 搜索系统性能与粒度的关系

显而易见,粒度越小,召回就越多,建立倒排索引时,索引的长度就越长;粒度的层次越多,索引的数量就越多。一个多,一个长,就对搜索系统的性能构成了极大的考验。

一般而言,大型搜索引擎的索引都采用分布式系统。不同文本的索引,被某种hash算法“分配”到了某台机器。理论上讲,索引的数量的增长,只会造成所需机器的增长,而对整体系统性能的消耗影响比较小。所以一般搜索引擎会从性价比的角度来考虑索引数量与机器数量的折衷,也就是召回与硬件投入的折衷。粒度分析对于折衷的性价比也有一定的贡献,在粒度层次里,当粒度逐渐变小的过程中,我们并不一定对所有小粒度词都建索引,而是选择“更有可能召回相关结果”的小粒度词。词汇的什么性质决定了“更有可能召回相关结果”?我们同样会在第四节讨论。

四.深入分析粒度的性质

在第三节中我们反复提到:一般情况下,粒度越大,相关性越好,召回越差;粒度越小,相关性越差,召回越好。在搜索引擎中,如果做到折衷呢?基本的原则是,在系统性能可接受的前提下,尽量多召回有效结果,计算相关性时,将最相关的排在前面。

我们如何做到将合理减小粒度,增加有效召回,又如何做到将最好的排在最前呢?这里涉及到两个问题:紧密度与重要性。

既然粒度是衡量文本所含信息量的大小,那么紧密度就是描述文本所含信息紧密程度的量。再说的通俗一些,紧密度就是信息被人们表达和接受的稳定程度。稳定有两种解释,第一,稳定是相对于临时而言的。一般来说,如果信息是因为某些因素临时组合在一起,那就是不稳定的,即不紧密。比如许多动宾结构的短语(“过马路”,“踢足球”),定中结构的短语(“红苹果”,“豪华轿车”)。第二,稳定是相对于顺序不固定而言的。如果同样一个信息,内部的子信息顺序可以互换,那么这个词汇就不稳定,即不紧密。比如一些大粒度的词汇“鼠标护腕垫”、“护腕鼠标垫”。

由此可见,我们根据词汇的紧密程度,可以将结果中表述与查询表述的一致程度联系起来,作为计算相关性的一个因素。同样,我们也可以将紧密度作为减小粒度的依据之一,词汇越不紧密,我们就有理由将其拆分为更小的粒度。

短语的重要性,其实是短语子成分的重要性,有很多定义。其中一种被普遍接受的定义为其占短语完整含义的比例。一般情况下,偏正结构短语中,“正”的部分比较重要,比如“绿茶”中的“茶”,但也有例外,如“珊瑚虫”中的“珊瑚”。而主谓、动宾短语一般来说,都比较重要,如“打球”,“你说”。所以,短语的子成分重要性,不能仅靠语法来识别,而应综合各种因素来确定。

假设有了词汇的子成分重要性,那么就可以帮助判断将词汇粒度变小后的语义损失风险程度(注意,这里使用了“语义损失”,而不是“转义”,想一想为什么)。这也就回答了第四节末尾的问题:语义损失越小,越有可能召回相关结果。

五.结束语

本文介绍了搜索引擎中的粒度问题,重点讨论了搜索引擎与短语切分粒度的关系,并进一步探讨了短语的两个重要性质——紧密度和重要性。通过本文,读者应该能够大致明白搜索引擎中关于粒度的种种。当然,本文只是对搜索引擎的粒度问题开了一个头,怎么合理的处理好粒度、在不同场合使用何种粒度,都是需要我们继续深入研究的。

浅谈网页搜索排序中的投票模型-百度搜索研发部

前些天读了一本《选举的困境》,其中有一章,从美国的选举制度说起,介绍美国选举制度的不足,然后针对其不足,提出种种改善,然而每种改善都有其各自的问题,其中的变化很有趣。

先说美国选举制度,美国的总统选举是一种“赢者通吃”的方式,每个州根据其人口多少,有几十或几百的“州票”,州里的人对总统候选人进行选举,在某个州获得票最多的那个候选人,获得这个州所有的“州票”,然后统计所有候选人的“州票”多少,获得最多“州票”的候选人获胜。

这样制度的问题是显然的,比如如果只有两个州,A州5个人,而B州4个人,州票也分别是5和4,如果某候选人X在A州以3:2获胜,另一个候选人Y在B州以4:0获胜,这样显然候选人Y在全国范围内获得了6张票,而候选人X只有在A州的3张票,但是由于“赢者通吃”,X获得了A周的全部5张“州票”,Y只获得了B周的4张“州票”,在全国只有1/3民众支持的X居然获得了选举的胜利。

这样的情况在2000年美国总统选举中就出现过,小布什的州票领先于戈尔,然而在全国民众中统计支持戈尔的人数却是大于小布什的,当然戈尔输给小布什还有另一个原因,这里按下不表。

 

如果放在算法领域,可以看出这里的问题在于,为了统计结果R(最适合的总统人选),找到了一个特征A(每个民众的投票),而决定结果R的,却不是特征A,而是由特征A推导出来的特征B(州票),在特征A向特征B的推导过程中,信息丢失了(每个洲的支持百分比不一样)。

“赢者通吃”这种制度的具体历史原因先不说,有兴趣的朋友可以去看原著。解决这种问题的最直接方案就是从“赢者通吃”变成直选,也就是一人一票,直接统计票数,然而这样也会遇到一系列问题。

在谈那一系列问题之前,先把要解决的问题抽象一下:

有n个候选人,每个选民对这n个候选人投票,最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人。

方案1:一票制,每人一票,选出自己最喜欢的候选人,对结果进行统计,得票最多的那个人当选。

这样做的问题是会导致作者定义的一种“鹬蚌困局”,举例说,如果有ABC三个候选人,其中BC政见比较类似,支持B的人也比较支持C,反之亦然,在全民中,喜欢BC的人占多数,A的政见和BC相反,支持A的人在全民中占少数。这样导致的后果就是,BC获得的票会比较分散,而A获得的票比较集中从而获得胜利,如果BC中有1人不参加选举,票就会集中到B或者C一个人的手中,从而使多数选民的支持者当选。前面按下不表的戈尔失败的另一个原因,就是有人认为有跟戈尔政见类似的耐德的参与,他分散了部分戈尔的选票。

可以对此问题有所改善的方案叫做“二选制”。

方案2:二选制,每人一票,如果无人获得大于50%的支持,则将得票最高的两个候选人拿出来,再进行一轮选举,得票多的人获胜。

法国总统选举就是这样的二选制,但是这样的方法只能改善“鹬蚌困局”,而不能彻底解决,2002年的法国总统大选就出现了类似的情况,当时支持左派政见的民众较多,然而在二选制下,最终的前两名却是一个右派和一个极右派。出现这种情况的原因是当年有16个总统候选人,且多数是持左派政见者,这样就导致左派的票极端分散。

方案3:n选制,每人一票,如果无人获得大于50%的支持,则去掉支持最少的候选人,再进行一轮投票,若依旧无人获得大于50%的支持,再去掉得票最少的候选人,直到有人大于50%支持为止。

2001年奥委会决定北京为2008年奥运会主办城市的时候,就是用的这样的制度,在第一轮投票里大阪被淘汰,北京在第二轮就获得了半数以上的支持,从而当选。

n选制的问题在于不实用,如果是奥委会这种只有几百个人投票的情况还可以使用,如果类似前面法国总统选举,有16个候选人,举国上下最多可能进行15次投票,成本太高。

方案4:即刻复选制,每个民众对候选人进行排序,如果某个候选人获得了50%以上的首选,则直接获得胜利,否则淘汰票数最低的候选人,并且把票数最低候选人的得票中的第二候选人拿出来,分给对应的候选人,如果有人获得50%以上,则当选,否则再淘汰一位最低的,并且把他票分给里面排序最高的且未被淘汰的候选人,如此往复。

爱尔兰总统选举和伦敦市长选举采用的是类似的方案,此方案也有问题,试想如此场景:选民共10人,中间派候选人是3人的首选,左派和右派的候选人分别是4人的首选,当然左派选民最讨厌右派候选人,而右派选民也最讨厌左派候选人,而左派右派的民众对中间派候选人倒是都可以接受,不管是即可复选制还是n选制,中间派候选人都会在第一轮被淘汰。而中间派候选人则是全体民众都可以接受的人,也最能调和各派之间矛盾,最和谐。

这个方案的本质问题是,虽然每个选民可以对候选人排序,但是在第一轮的时候却只考虑了第一选,没有考虑选民的二、三选。

方案5:上行复选制,跟方案4类似,只不过第一轮淘汰的不是支持最少,而是反对最多的候选人(获得最多末选票的候选人)

再看上面提到的情况,中间派候选人由于不是任何人的末选,所以第一轮淘汰的是左派或者右派,再第二轮选举中,中间派的候选人就可以获胜了。

方案5也有方案5的问题,考虑这样一种情况,只有两个候选人AB参选,选民9人,其中6人喜欢A而讨厌B,3人喜欢B而讨厌A,无论按照之前的哪种方式,都会是A获胜。但是现在又多了两个候选人C和D,喜欢B的3人中,都是把A列在最后一个候选的,而喜欢A的6人的末选,却是BCD各2票,这样,在第一轮选举中,A就由于获得了最多的末选票被淘汰了,而通过精心的构造例子,完全可以使B最终当选。仅仅由于CD参选或者不参选,A和B之间的胜负关系就发生了大逆转。

实际使用此方案的例子不多,只有在公元前507年的雅典有类似的方案,不是让民众投支持票,而是投反对票,把反对最多的人投出局。

方案6:多赛制,民众对候选人排序,然后候选人之间两两pk,统计每一张选票上看候选人A在候选人B前面还是B在A前面,如此找到获胜场次最多的候选人来赢得选举。

这样的问题是可能导致循环胜负,如ABC三个候选人,有3个民众,投票分别是ABC,BCA,CAB,可以看出AB之间A获胜两次,A>B;BC之间B获胜两次,B>C,AC之间C获胜两次,C>A,这样就构成了一个A>B>C的循环。这个是不是有点像足球联赛的记分制啊,如果积分相同,足球比赛中可以再看净胜球、进球、胜负关系等,但是作者并没有在这个方面进行展开,而是介绍了另一种方式:博达制。

方案7:博达制,民众对候选人排序,假如有n个候选人,第一位的候选人得n分,第二位得n-1分,以此类推,然后统计每个候选人的总分,获得最多分的获胜。

有人对博达制的批评是:可能有选民会利用这种方式进行作弊(投“策略票”),最支持B的候选人本来心目中的排序是B>A>C,但是由于相对A,他们还是更喜欢B,因此,为了把B拉上来,就得把A拉下去,他们的投票就变成了B>C>A。博达对此批评的回应是:我的制度只适用于诚实的投票者。

而这本书的作者却认为博达制的“策略票”问题没那么严重,如果无法准确预测民意和精确控制策略票的投法,有可能因为用力过猛,不但把A拉下来了,反而让C获得的支持票增加,这样就使得最支持B的那些人的“策略票”反而使得他们最讨厌的C当选了,当年在IMDB上就发生过类似一幕:

电影《蝙蝠侠6》上映后,蝙蝠侠的粉丝们觉得这部片太酷了,于是就想把蝙蝠侠6投成IMDB第一位,于是他们疯狂的给蝙蝠侠6打高分,而同时,也纷纷的给当时的IMDB第一《教父》投低分,导致的结果就是用力过猛,教父变成了第三名,原来的第二肖申克的救赎(TSR)变成了第二(原来的第二是排在教父后面,新的第二是排在蝙蝠侠6后面),而后来,随着疯狂粉丝的热情消退,理性的意见占据了上风,蝙蝠侠6的得分逐渐下降,跌到了第10。而教父还是在肖申克的救赎后面,很久没有回去了。

博达制是否有其他问题呢?

以上只是对这本书第14章的一个笔记,也仅仅针对“多候选人单职位”问题进行了讨论,书的后面还会对“多候选人多职位”的情况继续探讨,也就是根据每个人对候选人的排序,来决定最终的候选人排序。

回到搜索引擎领域来,如上策略的变迁会给我们一些启示,先看看之前抽象出来的问题:

有n个候选人,每个选民对这n个候选人投票,最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人。

这很像搜索引擎在解决的问题:

系统里有n个网页,有m个特征(页面质量、页面内容丰富度、页面超链、文本相关性等)对n个网页有不同的打分,如何根据这些特征的“投票”,选出最适合放在第一位的网页呢?

从选举的例子中,我们可以得到的几个启示:

1. 设计算法时,要避免出现“赢者通吃”带来的信息丢失问题。

2. 不要因为某几个特征特别好,就把某个网页排到最前,或者因为某几个特征特别差,就把某个网页抛弃。

3. 最合适放在首位的网页不一定是在每个特征上都最好,而应该是能够兼顾所有特征,综合表现最好的那个。

4. 搜索引擎使用者对搜索结果的点击行为,可以看成是对搜索结果进行的“投票”,这样的“投票”信息的使用方式,也要注意考虑是否会带来选举过程中出现的种种不合理。

以上提到的种种选举方案,仅仅是对“多候选人单职位的”的情况进行讨论,而搜索引擎面对的问题,则更类似于“多候选人排序”的情况,也即:

系统里有n个网页,有m个特征(页面质量、页面内容丰富度、页面超链、文本相关性等)对n个网页有不同的打分,如何根据这些特征的“投票”,决定n个网页的顺序?

而这个“多候选人排序”问题,是有一个“不可能的民主”的理论的,该理论的大意是,“合理”的民主应该满足3个条件:

1. 如果选民都认为A比B好,那么最终结果应该也是A比B好

2. 没有“独裁者”,也即,不存在这样一个人,无论别人怎么排序,最终结果的排序都和这个人的排序一致

3. 无关因素独立性,也即,在第一次投票完成后,A排在B前面,现在进行第二次投票,如果所有人都没有改变自己投票中A和B的相对顺序,那最终结果应该也是A在B前面

而通过数学的证明,可以得出结论:如果某种选举方式满足条件1和3,则必然不满足2,也即必然存在“独裁者”,这个问题的证明,可以参考这篇博客:http://roba.rushcj.com/?p=509

根据“不可能的民主”理论,和搜索引擎结合起来看,似乎搜索引擎很难给出一个合理的网页排序,但是搜索引擎和投票又似乎有所不同,有两个角度可以破解

1. 认为条件3过于强,需要弱化。

2. 也许在网页排序问题上,真的存在这样一个“独裁特征”,这个“独裁特征”从目前看来,最适合的应该就是“用户满意度”了,按照用户的满意程度来排序网页,就是最合理的网页排序。如何衡量“用户满意度”呢?这就是我们一直在努力的。

by liangaili(baidu-tech)