当前位置:首页 » SEO技术 » 正文

深度解读页面查找排序中的投票baidu算法

作者:盖 继东 时间:2015-04-22 标签:
文章摘要: 前些天读了一本《推举的窘境》,其间有一章,从美国的推举准则说起,介绍美国推举准则的缺乏,然后对于其缺乏,提出各种改进,可是每种改进都有其各自的疑问,其间的改动很风趣。 先说美国推举准则,美国的总统推举是一种“赢者通吃”的办法,每个州依据其人员多少,有几十或几百的“州票”,州里的人对总统提名人进行推举,…

前些天读了一本《推举的窘境》,其间有一章,从美国的推举准则说起,介绍美国推举准则的缺乏,然后对于其缺乏,提出各种改进,可是每种改进都有其各自的疑问,其间的改动很风趣。

先说美国推举准则,美国的总统推举是一种“赢者通吃”的办法,每个州依据其人员多少,有几十或几百的“州票”,州里的人对总统提名人进行推举,在某个州取得票最多的那个提名人,取得这个州一切的“州票”,然后计算一切提名人的“州票”多少,取得最多“州票”的提名人取胜。

这样准则的疑问是明显的,比方假如只要两个州,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前面,如今进行第2次投票,假如一切人都没有改动自个投票中A和B的相对次序,那终究成果应当也是A在B前面

而经过数学的证实,能够得出结论:假如某种推举办法满足条件1和3,则必定不满足2,也即必定存在“独裁者”,这个疑问的证实,能够参阅这篇博客:http://roba.rushcj.com/?p=509

依据“不或许的民主”理论,和查找引擎结合起来看,好像查找引擎很难给出一个合理的页面排序,可是查找引擎和投票又好像有所纷歧样,有两个视点能够破解

1. 以为条件3过于强,需求弱化。

2. 或许在页面排序疑问上,真的存在这样一个“独裁特征”,这个“独裁特征”从当前看来,最适合的应当即是“用户满足度”了,依照用户的满足程度来排序页面,即是最合理的页面排序。如何衡量“用户满足度”呢?这即是咱们一直在尽力的。

更多
没有评论
发表评论

你需要先 登录 才能回复


网站地图