淺談網(wǎng)頁搜索排序中的投票模型
來源:SEO優(yōu)化 2012-05-30
前些天讀了一本《選舉的困境》,其中有一章,從美國的選舉制度說起,介紹美國選舉制度的不足,然后針對(duì)其不足,提出種種改善,然而每種改善都有其各自的問題,其中的變化很有趣。
先說美國選舉制度,美國的總統(tǒng)選舉是一種“贏者通吃”的方式,每個(gè)州根據(jù)其人口多少,有幾十或幾百的“州票”,州里的人對(duì)總統(tǒng)候選人進(jìn)行選舉,在某個(gè)州獲得票最多的那個(gè)候選人,獲得這個(gè)州所有的“州票”,然后統(tǒng)計(jì)所有候選人的“州票”多少,獲得最多“州票”的候選人獲勝。
這樣制度的問題是顯然的,比如如果只有兩個(gè)州,A州5個(gè)人,而B州4個(gè)人,州票也分別是5和4,如果某候選人X在A州以3:2獲勝,另一個(gè)候選人Y在B州以4:0獲勝,這樣顯然候選人Y在全國范圍內(nèi)獲得了6張票,而候選人X只有在A州的3張票,但是由于“贏者通吃”,X獲得了A周的全部5張“州票”,Y只獲得了B周的4張“州票”,在全國只有1/3民眾支持的X居然獲得了選舉的勝利。
這樣的情況在2000年美國總統(tǒng)選舉中就出現(xiàn)過,小布什的州票領(lǐng)先于戈?duì)?然而在全國民眾中統(tǒng)計(jì)支持戈?duì)柕娜藬?shù)卻是大于小布什的,當(dāng)然戈?duì)栞斀o小布什還有另一個(gè)原因,這里按下不表。
如果放在算法領(lǐng)域,可以看出這里的問題在于,為了統(tǒng)計(jì)結(jié)果R(最適合的總統(tǒng)人選),找到了一個(gè)特征A(每個(gè)民眾的投票),而決定結(jié)果R的,卻不是特征A,而是由特征A推導(dǎo)出來的特征B(州票),在特征A向特征B的推導(dǎo)過程中,信息丟失了(每個(gè)洲的支持百分比不一樣)。
“贏者通吃”這種制度的具體歷史原因先不說,有興趣的朋友可以去看原著。解決這種問題的最直接方案就是從“贏者通吃”變成直選,也就是一人一票,直接統(tǒng)計(jì)票數(shù),然而這樣也會(huì)遇到一系列問題。
在談那一系列問題之前,先把要解決的問題抽象一下:
有n個(gè)候選人,每個(gè)選民對(duì)這n個(gè)候選人投票,最終在n個(gè)候選人中選出最合適、最符合民意、也符合邏輯的那個(gè)人。
方案1:一票制,每人一票,選出自己最喜歡的候選人,對(duì)結(jié)果進(jìn)行統(tǒng)計(jì),得票最多的那個(gè)人當(dāng)選。
這樣做的問題是會(huì)導(dǎo)致作者定義的一種“鷸蚌困局”,舉例說,如果有ABC三個(gè)候選人,其中BC政見比較類似,支持B的人也比較支持C,反之亦然,在全民中,喜歡BC的人占多數(shù),A的政見和BC相反,支持A的人在全民中占少數(shù)。這樣導(dǎo)致的后果就是,BC獲得的票會(huì)比較分散,而A獲得的票比較集中從而獲得勝利,如果BC中有1人不參加選舉,票就會(huì)集中到B或者C一個(gè)人的手中,從而使多數(shù)選民的支持者當(dāng)選。前面按下不表的戈?duì)柺〉牧硪粋�(gè)原因,就是有人認(rèn)為有跟戈?duì)栒婎愃频哪偷碌膮⑴c,他分散了部分戈?duì)柕倪x票。
可以對(duì)此問題有所改善的方案叫做“二選制”。
方案2:二選制,每人一票,如果無人獲得大于50%的支持,則將得票最高的兩個(gè)候選人拿出來,再進(jìn)行一輪選舉,得票多的人獲勝。
法國總統(tǒng)選舉就是這樣的二選制,但是這樣的方法只能改善“鷸蚌困局”,而不能徹底解決,2002年的法國總統(tǒng)大選就出現(xiàn)了類似的情況,當(dāng)時(shí)支持左派政見的民眾較多,然而在二選制下,最終的前兩名卻是一個(gè)右派和一個(gè)極右派。出現(xiàn)這種情況的原因是當(dāng)年有16個(gè)總統(tǒng)候選人,且多數(shù)是持左派政見者,這樣就導(dǎo)致左派的票極端分散。
方案3:n選制,每人一票,如果無人獲得大于50%的支持,則去掉支持最少的候選人,再進(jìn)行一輪投票,若依舊無人獲得大于50%的支持,再去掉得票最少的候選人,直到有人大于50%支持為止。
2001年奧委會(huì)決定北京為2008年奧運(yùn)會(huì)主辦城市的時(shí)候,就是用的這樣的制度,在第一輪投票里大阪被淘汰,北京在第二輪就獲得了半數(shù)以上的支持,從而當(dāng)選。
n選制的問題在于不實(shí)用,如果是奧委會(huì)這種只有幾百個(gè)人投票的情況還可以使用,如果類似前面法國總統(tǒng)選舉,有16個(gè)候選人,舉國上下最多可能進(jìn)行15次投票,成本太高。
方案4:即刻復(fù)選制,每個(gè)民眾對(duì)候選人進(jìn)行排序,如果某個(gè)候選人獲得了50%以上的首選,則直接獲得勝利,否則淘汰票數(shù)最低的候選人,并且把票數(shù)最低候選人的得票中的第二候選人拿出來,分給對(duì)應(yīng)的候選人,如果有人獲得50%以上,則當(dāng)選,否則再淘汰一位最低的,并且把他票分給里面排序最高的且未被淘汰的候選人,如此往復(fù)。
愛爾蘭總統(tǒng)選舉和倫敦市長選舉采用的是類似的方案,此方案也有問題,試想如此場(chǎng)景:選民共10人,中間派候選人是3人的首選,左派和右派的候選人分別是4人的首選,當(dāng)然左派選民最討厭右派候選人,而右派選民也最討厭左派候選人,而左派右派的民眾對(duì)中間派候選人倒是都可以接受,不管是即可復(fù)選制還是n選制,中間派候選人都會(huì)在第一輪被淘汰。而中間派候選人則是全體民眾都可以接受的人,也最能調(diào)和各派之間矛盾,最和諧。
這個(gè)方案的本質(zhì)問題是,雖然每個(gè)選民可以對(duì)候選人排序,但是在第一輪的時(shí)候卻只考慮了第一選,沒有考慮選民的二、三選。
方案5:上行復(fù)選制,跟方案4類似,只不過第一輪淘汰的不是支持最少,而是反對(duì)最多的候選人(獲得最多末選票的候選人)
再看上面提到的情況,中間派候選人由于不是任何人的末選,所以第一輪淘汰的是左派或者右派,再第二輪選舉中,中間派的候選人就可以獲勝了。
方案5也有方案5的問題,考慮這樣一種情況,只有兩個(gè)候選人AB參選,選民9人,其中6人喜歡A而討厭B,3人喜歡B而討厭A,無論按照之前的哪種方式,都會(huì)是A獲勝。但是現(xiàn)在又多了兩個(gè)候選人C和D,喜歡B的3人中,都是把A列在最后一個(gè)候選的,而喜歡A的6人的末選,卻是BCD各2票,這樣,在第一輪選舉中,A就由于獲得了最多的末選票被淘汰了,而通過精心的構(gòu)造例子,完全可以使B最終當(dāng)選。僅僅由于CD參選或者不參選,A和B之間的勝負(fù)關(guān)系就發(fā)生了大逆轉(zhuǎn)。
實(shí)際使用此方案的例子不多,只有在公元前507年的雅典有類似的方案,不是讓民眾投支持票,而是投反對(duì)票,把反對(duì)最多的人投出局。
方案6:多賽制,民眾對(duì)候選人排序,然后候選人之間兩兩pk,統(tǒng)計(jì)每一張選票上看候選人A在候選人B前面還是B在A前面,如此找到獲勝場(chǎng)次最多的候選人來贏得選舉。
這樣的問題是可能導(dǎo)致循環(huán)勝負(fù),如ABC三個(gè)候選人,有3個(gè)民眾,投票分別是ABC,BCA,CAB,可以看出AB之間A獲勝兩次,A>B;BC之間B獲勝兩次,B>C,AC之間C獲勝兩次,C>A,這樣就構(gòu)成了一個(gè)A>B>C的循環(huán)。這個(gè)是不是有點(diǎn)像足球聯(lián)賽的記分制啊,如果積分相同,足球比賽中可以再看凈勝球、進(jìn)球、勝負(fù)關(guān)系等,但是作者并沒有在這個(gè)方面進(jìn)行展開,而是介紹了另一種方式:博達(dá)制。
方案7:博達(dá)制,民眾對(duì)候選人排序,假如有n個(gè)候選人,第一位的候選人得n分,第二位得n-1分,以此類推,然后統(tǒng)計(jì)每個(gè)候選人的總分,獲得最多分的獲勝。
有人對(duì)博達(dá)制的批評(píng)是:可能有選民會(huì)利用這種方式進(jìn)行作弊(投“策略票”),最支持B的候選人本來心目中的排序是B>A>C,但是由于相對(duì)A,他們還是更喜歡B,因此,為了把B拉上來,就得把A拉下去,他們的投票就變成了B>C>A。博達(dá)對(duì)此批評(píng)的回應(yīng)是:我的制度只適用于誠實(shí)的投票者。
而這本書的作者卻認(rèn)為博達(dá)制的“策略票”問題沒那么嚴(yán)重,如果無法準(zhǔn)確預(yù)測(cè)民意和精確控制策略票的投法,有可能因?yàn)橛昧^猛,不但把A拉下來了,反而讓C獲得的支持票增加,這樣就使得最支持B的那些人的“策略票”反而使得他們最討厭的C當(dāng)選了,當(dāng)年在IMDB上就發(fā)生過類似一幕:
電影《蝙蝠俠6》上映后,蝙蝠俠的粉絲們覺得這部片太酷了,于是就想把蝙蝠俠6投成IMDB第一位,于是他們瘋狂的給蝙蝠俠6打高分,而同時(shí),也紛紛的給當(dāng)時(shí)的IMDB第一《教父》投低分,導(dǎo)致的結(jié)果就是用力過猛,教父變成了第三名,原來的第二肖申克的救贖(TSR)變成了第二(原來的第二是排在教父后面,新的第二是排在蝙蝠俠6后面),而后來,隨著瘋狂粉絲的熱情消退,理性的意見占據(jù)了上風(fēng),蝙蝠俠6的得分逐漸下降,跌到了第10。而教父還是在肖申克的救贖后面,很久沒有回去了。
博達(dá)制是否有其他問題呢?
以上只是對(duì)這本書第14章的一個(gè)筆記,也僅僅針對(duì)“多候選人單職位”問題進(jìn)行了討論,書的后面還會(huì)對(duì)“多候選人多職位”的情況繼續(xù)探討,也就是根據(jù)每個(gè)人對(duì)候選人的排序,來決定最終的候選人排序。
回到搜索引擎領(lǐng)域來,如上策略的變遷會(huì)給我們一些啟示,先看看之前抽象出來的問題:
有n個(gè)候選人,每個(gè)選民對(duì)這n個(gè)候選人投票,最終在n個(gè)候選人中選出最合適、最符合民意、也符合邏輯的那個(gè)人。
這很像搜索引擎在解決的問題:
系統(tǒng)里有n個(gè)網(wǎng)頁,有m個(gè)特征(頁面質(zhì)量、頁面內(nèi)容豐富度、頁面超鏈、文本相關(guān)性等)對(duì)n個(gè)網(wǎng)頁有不同的打分,如何根據(jù)這些特征的“投票”,選出最適合放在第一位的網(wǎng)頁呢?
從選舉的例子中,我們可以得到的幾個(gè)啟示:
1. 設(shè)計(jì)算法時(shí),要避免出現(xiàn)“贏者通吃”帶來的信息丟失問題。
2. 不要因?yàn)槟硯讉�(gè)特征特別好,就把某個(gè)網(wǎng)頁排到最前,或者因?yàn)槟硯讉�(gè)特征特別差,就把某個(gè)網(wǎng)頁拋棄。
3. 最合適放在首位的網(wǎng)頁不一定是在每個(gè)特征上都最好,而應(yīng)該是能夠兼顧所有特征,綜合表現(xiàn)最好的那個(gè)。
4. 搜索引擎使用者對(duì)搜索結(jié)果的點(diǎn)擊行為,可以看成是對(duì)搜索結(jié)果進(jìn)行的“投票”,這樣的“投票”信息的使用方式,也要注意考慮是否會(huì)帶來選舉過程中出現(xiàn)的種種不合理。
以上提到的種種選舉方案,僅僅是對(duì)“多候選人單職位的”的情況進(jìn)行討論,而搜索引擎面對(duì)的問題,則更類似于“多候選人排序”的情況,也即:
系統(tǒng)里有n個(gè)網(wǎng)頁,有m個(gè)特征(頁面質(zhì)量、頁面內(nèi)容豐富度、頁面超鏈、文本相關(guān)性等)對(duì)n個(gè)網(wǎng)頁有不同的打分,如何根據(jù)這些特征的“投票”,決定n個(gè)網(wǎng)頁的順序?
而這個(gè)“多候選人排序”問題,是有一個(gè)“不可能的民主”的理論的,該理論的大意是,“合理”的民主應(yīng)該滿足3個(gè)條件:
1. 如果選民都認(rèn)為A比B好,那么最終結(jié)果應(yīng)該也是A比B好
2. 沒有“獨(dú)裁者”,也即,不存在這樣一個(gè)人,無論別人怎么排序,最終結(jié)果的排序都和這個(gè)人的排序一致
3. 無關(guān)因素獨(dú)立性,也即,在第一次投票完成后,A排在B前面,現(xiàn)在進(jìn)行第二次投票,如果所有人都沒有改變自己投票中A和B的相對(duì)順序,那最終結(jié)果應(yīng)該也是A在B前面
而通過數(shù)學(xué)的證明,可以得出結(jié)論:如果某種選舉方式滿足條件1和3,則必然不滿足2,也即必然存在“獨(dú)裁者”,這個(gè)問題的證明,可以參考這篇博客:roba.rushcj.com/?p=509
根據(jù)“不可能的民主”理論,和搜索引擎結(jié)合起來看,似乎搜索引擎很難給出一個(gè)合理的網(wǎng)頁排序,但是搜索引擎和投票又似乎有所不同,有兩個(gè)角度可以破解
1. 認(rèn)為條件3過于強(qiáng),需要弱化。
2. 也許在網(wǎng)頁排序問題上,真的存在這樣一個(gè)“獨(dú)裁特征”,這個(gè)“獨(dú)裁特征”從目前看來,最適合的應(yīng)該就是“用戶滿意度”了,按照用戶的滿意程度來排序網(wǎng)頁,就是最合理的網(wǎng)頁排序。如何衡量“用戶滿意度”呢?這就是我們一直在努力的。
by liangaili
文章編輯: 365webcall網(wǎng)上客服軟件(www.365webcall.com)
我的評(píng)論
| 登錄賬號(hào)： | 密碼： | 快速注冊(cè) | 找回密碼 |  |
