論文紹介 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 1 Rank Aggregation Problemとは ---the social choice scenario c1,……,cN N:候補者人数(candidates) K:投票者人数(voters) Full list C1 Cm . . . . . cN v1,……,vK =N …………... Cn Cm . . . . cp Partial list ……….. Ci Cj <N . . ck 候補者合意（consensus）リスト(full list)を作成 Ci Cj . . . . Ck cm 2 WEBとの関連は候補者 ----meta-search engine WWW google 投票者 infoseek …… Yahoo Meta-search engine 最終の検索結果 3 Rank Aggregationとは • データ収集法、ランキング法が異なる検索エンジンのランキング結果をまとめたランキングを生成する技術 • 特定の検索エンジンだけで不当なほど高順位を得ている spam の除去に役立つ Spam: 上位にページランキングされるためのトリック検索頻度の大きい語句の使用小さなフォント、文字の無色化、METAタグの悪用 • 検索エンジン間の比較 4 予備---ランキング定義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 τ 5 予備---ランキング定義２： S=Uのとき、τはfull list (τcontains all elements in U) S  Uのとき、 τはpartial list (τcontains elements,which are a strict subset of U) 6 予備---ランキング間の距離 σ、τ：集合Sの full list に対して、 (two popular distance measures) 定義3: The Spearman footrule 距離（ランクの差の総和） F ( , )    (i)   (i) iS 定義4: The Kendall tau 距離（ランクが逆転するペアの総数） K ( , )  {(i, j) |  (i)   ( j), (i)   ( j)}　, i, j  S 7 予備---ランキング間の距離例： S={A,B,C,D,E} sのfull list σ、τ=＞ Spearman footrule 距離 F(σ,τ)=1+2+1+0+2 = 6 ランク 1 2 3 4 5 σ A C E D B τ C A B D E Kendall tau 距離 K(σ,τ)=|{(A,C), (B,D), (B,E), (D,E)}| = 4 8 予備---ランキング間の距離例：ランク S={A,B,C,D,E} sのpartial list τ とfull list σ => 単射τ|σ=[A,B,E]はτの代わりに、 1 2 3 4 5 σ A E B τ C A B D E F(τ,σ)=F(τ| σ，σ)， K(τ,σ)=K(τ| σ，σ)． 9 予備---ランキング間の距離定義5: full list σとτ1、τ2、……τk間の footrule 距離： Σ F (σ,τi ) F (σ,τ1 ,τ2 ,....,τk )  k k i 1 同様に、Kendall 距離： Σ K (σ,τi ) K (σ,τ1 ,τ2 ,....,τk )  k k i 1 10 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 11 Optimal Rank Aggregation Kendall 距離を最小化することを Kemeny optimal aggregation(KOA)と呼ぶしかし、KOAはNP-hard (証明は割愛) (N人の候補者に対し、投票者が４人の場合でも) 12 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. 13 ECC---fighting spam Spam pageは大多数検索エンジンにサポートされない。(でないと、garbage in,garbage out.) ECCを満足するrank aggregation メソッドはspam pageをrankingの底部に置くはず。シンプルな方法はないのかな？ 14 Local KOA 定義８： σ： τ1 τ2 …… list  τkに関するfull  (例：σ＝[X1>…>Xi>Yi+1>…..]) σ’:σの隣り合ってる要素を逆転することによって生成される。 (例：σ’＝[X1>…>Yi>Xi+1>…..]) K(σ’， τ1 τ2 …… τk)< K(σ， τ1 τ2 …… τk)を満足するようなσ’が存在しないとき、 σをτ1,τ2,……,τk のLocal KOAである。 15 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) 16 Local KOA 補題９： Local KOA satisfy ECC.  τkに関するfull list σ:{1,…n} 証明： τ1 τ2 …… は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….] 17 Local KOA---補題9の証明 (d,c)はこのようなペアの中で一番近いとする。 σ={….de…c….} (i) e=c ⇒ σ’s.t. (フリップ(d,c)) K(σ’， τ1 τ2 …… τk)< K(σ， τ1 τ2 …… τk) (フリップ(d,c)) σはLocal KOAと矛盾 18 Local KOA---補題9の証明 (ii) e ≠ c ①e  T, ⇒ ペア(d,e)は(d,c)より近いはず． ②e  U, ⇒ ペア(e,c)は(d,c)より近いはず． ①と②はペア(d,c)の選択と矛盾 19 Local Kemenization---予備定義10:consistency partial list : τ1,τ2,……,τk  τk ） full list :μ（τ1 τ2 …… full list πはconsistent with μand τ1,τ2,……,τk とは π(i)<π(j)⇒(i)μ(i)<μ(j) or π(i)<π(j)∧ μ(i)>μ(j)⇒ τ-majority (ii)τ-majority prefer i prefer to j i to j K(π， τ1 τ2 …… τk)< K(μ， τ1 τ2 …… τk) 20 Local Kemenization---予備補題11:   n], k: Sk=[x1  μ=[x1 x2 ,…．x ,…. ,xk] πはconsistent with μand τ1,τ2,……,τk ⇒π| Skはconsistent with μ| Sk and τ1| Sk,τ2 | Sk,……,τk | Sk 定義10により、μの全体について言えたので、 μ部分にも当然言える。 21 Local Kemenization---定義定義12: partial list : τ1,τ2,……,τk と  τk ）が与えられた時、  full list :μ（τ1 τ2 …… πはμのLocal Kemenization とは、 (i)πはconsistent with μ (ii)  μ=[x1 ,…．x ,…. ,x  n], k: Sk=[x1   k]に対し π| Skは τ1| Sk,τ2 | Sk,……,τk | Sk のLocal KOA 22 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を挿入する場所は一つしかない。 23 小結 τ1,τ2,……,τk ①Borda’s method ②Markov chain method 既知のaggregation方法 full list μ Local Kemenization 最終結果 24