論文紹介 Rank Aggregation Methods for the Web Dandapani Sivakumar 　論文紹介 Rank Aggregation Methods for the Web Dandapani Sivakumar IBM Almaden Research Center,650 Harry Road,San Jose,CA 95120. collaborators: C.Dwork(Compaq System Research Center) R.Kumar(IBM Almaden Research Center) M.Naor(Weizmann/IBM Almaden/Stanford) winner of the best paper award in the category searching,querying and indexing WWW10 conference,HongKong,may 2001

Rank Aggregation Problemとは ---the social choice scenario N:候補者人数(candidates) c1,……,cN K:投票者人数(voters)　　v1,……,vK C1 Cm . cN Cn Cm . cp Ci Cj . ck =N <N Partial list Full list …………... ……….. 候補者合意（consensus）リスト(full list)を作成 Ci Cj . Ck cm

WEBとの関連は ----meta-search engine 候補者 投票者 WWW google infoseek …… Yahoo Meta-search engine 複数のサーチエンジンを横断的に検索するシステムのこと検索結果を独自に分析して分かりやすい形で出力するもの 最終の検索結果

Rank Aggregationとは データ収集法、ランキング法が異なる検索エンジンのランキング結果をまとめたランキングを生成する技術 特定の検索エンジンだけで不当なほど高順位を得ている spam の除去に役立つ 　　 Spam: 上位にページランキングされるためのトリック 検索頻度の大きい語句の使用 小さなフォント、文字の無色化、METAタグの悪用 　検索エンジン間の比較

予備---ランキング 定義1: U:全体，S U, ordered listτ=[x1 x2 ,…．x|S|] s.t. 定義1: 　 U:全体，S　　U, ordered listτ=[x1 x2 ,…．x|S|] s.t. each xi S , を集合Sのrankingという。 註：ランキングの高い方は添え字が小さい. 以下： x Uかつx τに対し,τ(x)：the position of x 　　　　|τ|: # of elements in τ

予備---ランキング 定義２： S=Uのとき、τはfull list S Uのとき、 τはpartial list (τcontains all elements in U) S Uのとき、 τはpartial list (τcontains elements,which are a strict subset of U)

予備---ランキング間の距離 σ、τ：集合Sの full list に対して、 (two popular distance measures) 定義3: The Spearman footrule 距離（ランクの差の総和） 定義4: The Kendall tau 距離（ランクが逆転するペアの総数）

予備---ランキング間の距離 例： 1 A C 2 C A 3 E B S={A,B,C,D,E} 4 D D 　　　　　　　　 予備---ランキング間の距離 例： ランク 　σ 　τ 　1 　A 　C 　2 　C 　A 　3 　E 　B 　4 　D 　D 　5 　B 　E S={A,B,C,D,E} sのfull list σ、τ=＞ Spearman footrule　距離 　F(σ,τ)=1+2+1+0+2 = 6 Kendall tau 距離 　K(σ,τ)=|{(A,C), (B,D), (B,E), (D,E)}| = 4

F(τ,σ)=F(τ| σ，σ)， K(τ,σ)=K(τ| σ，σ)． 予備---ランキング間の距離 例： ランク 　σ 　τ 　1 　A 　C 　2 　E 　A 　3 　B 　B 　4 　 　D 　5 　 　E S={A,B,C,D,E} sのpartial list τ とfull list σ　=> 単射τ|σ=[A,B,E]はτの 代わりに、 F(τ,σ)=F(τ| σ，σ)， K(τ,σ)=K(τ| σ，σ)．

予備---ランキング間の距離 定義5: full list σとτ1、τ2、……τk間の footrule 距離： 　 同様に、Kendall 距離：

Optimal Rank Aggregation 例：The social choice の場合、 最終結果に対する不満を感じる投票者の人数を最少にするようなfull list 定義6: 　 ランキングτ1,τ2,……τkが与えられたとき， F(σ，τ1,τ2,……,τk) or K(σ，τ1,τ2,……,τk)を最小化するようなσをOptimal Rank Aggregationという。 ただし、σはτ1　τ2　……　τkに関するfull list

Optimal Rank Aggregation Kendall 距離を最小化することを Kemeny optimal aggregation(KOA)と呼ぶ しかし、KOAはNP-hard (証明は割愛) (N人の候補者に対し、投票者が４人の場合でも)

Extended Condorcet Criterion(ECC) *定義７： τ1∨τ2 ∨ ……∨ τkに関するfull list π：{1,……n} πはECCを満足するとは： ∀パーティション(T,U) T,U∈{1,……n} s.t. ∀i∈T,j∈U,τ-majority prefer i to jに対し、π(T)<π(U) 例：π =[x1≧x2 ≧ x3 ≧ x4 ≧ x5] *M.Truchon. An extension of the Condorcet criterion and 　 　 Kemeny orders. Cahier 98-15 du Centre de Recherche en 　Economie et Finance Appliquees,1998.

ECC---fighting spam Spam pageは大多数検索エンジンにサポートされない。(でないと、garbage in,garbage out.) ECCを満足するrank aggregation メソッドはspam pageをrankingの底部に置くはず。 シンプルな方法はないのかな？

Local KOA 定義８： σ： τ1 τ2 …… τkに関するfull list (例：σ＝[X1>…>Xi>Yi+1>…..]) σ’:σの隣り合ってる要素を逆転することによって生成される。 (例：σ’＝[X1>…>Yi>Xi+1>…..]) K(σ’， τ1　τ2　……　τk)< K(σ， τ1　τ2　……　τk)を満 足するようなσ’が存在しないとき、 σをτ1,τ2,……,τk のLocal KOAである。

Local KOA 例： τ1=[1,2] τ2=[2,3] τ3= τ4＝ τ5＝[3,1] σ＝[1,2,3]はLocal KOA.(K(σ,τ1,τ2,τ3,τ4,τ5)=3,) (although σ’=[3,2,1] will decreases the distance to 2)

Local KOA 補題９： Local KOA satisfy ECC. σ=[….d…c….] 証明： τ1　τ2　……　τkに関するfull list σ:{1,…n} はLocal KOA,ECCを満足しないと仮定． ∃パーティション(T,U) of {1,….n} s.t. all a T, all b U, τ-majority prefer a to b 仮定により、 c T, d U:σ(d)<σ(c) σ=[….d…c….]

Local KOA---補題9の証明 (d,c)はこのようなペアの中で一番近いとする。 σ={….de…c….} e=c ⇒ σ’s.t. (フリップ(d,c)) K(σ’， τ1　τ2　……　τk)< K(σ， τ1　τ2　……　τk) (フリップ(d,c)) σはLocal KOAと矛盾

Local KOA---補題9の証明 (ii) e ≠ c ①e T, ⇒ ペア(d,e)は(d,c)より近いはず． ②e U, ⇒ ペア(e,c)は(d,c)より近いはず． ①と②はペア(d,c)の選択と矛盾

Local Kemenization---予備 定義10:consistency partial list : τ1,τ2,……,τk full list :μ（τ1　τ2　……　τk ） full list πはconsistent with μand 　とは π(i)<π(j)⇒(i)μ(i)<μ(j) or (ii)τ-majority prefer i to j τ1,τ2,……,τk π(i)<π(j)∧ μ(i)>μ(j)⇒ τ-majority prefer i to j K(π， τ1　τ2　……　τk)< K(μ， τ1　τ2　……　τk)

Local Kemenization---予備 補題11: μ=[x1 x2 ,…．xn], k: Sk=[x1 ,…. ,xk] πはconsistent with μand 　 ⇒π| Skはconsistent with μ| Sk and τ1,τ2,……,τk τ1| Sk,τ2 | Sk,……,τk | Sk 定義10により、μの全体について言えたので、μ部分にも当然言える。

Local Kemenization---定義 定義12: partial list : τ1,τ2,……,τk と full list :μ（τ1　τ2　……　τk ）が与えられた時、 πはμのLocal Kemenization とは、 (i)πはconsistent with μ (ii) μ=[x1 ,…．xn],　k: Sk=[x1 ,…. ,xk]に対し π| Skは のLocal KOA τ1| Sk,τ2 | Sk,……,τk | Sk

Local Kemenization---定理 定理13: πはユニークである。 証明：|μ|に関する帰納法。 |μ|=1 , 成り立つ。 |μ|=n-1,定理13は成立と仮定。 |μ|=nのとき，μn-1=μー{x}、μ=[…………≧x] 仮定により、∃πn-1 : μn-1のユニークなLocal Kemenization xをπn-1の要素 i の直後に挿入　s.t. ①∀ｊ: πn-1(i)< πn-1(j)に対して、τ-majority prefer x to j. ②no τ-majority prefer x to i. πnはLocal KOA , xを挿入する場所は一つしかない。

小結 τ1,τ2,……,τk ①Borda’s method ②Markov chain method 既知のaggregation方法 　　　　　　　　　小結 ①Borda’s method ②Markov chain　 method 　　 τ1,τ2,……,τk 既知のaggregation方法 full list μ Local Kemenization 最終結果