Topic-Sensitive PageRank - 日々の勉強の航跡

Taher H. Haveliwala.
Topic-Sensitive PageRank
Proceedings of the Eleventh International World Wide Web Conference, 2002.

PDFへのリンク

概要

Topic-Sensitive PageRankという、PageRankというアルゴリズムを改善したものの提唱

アルゴリズムの特徴

検索の結果にqueryやquery context(文脈、前後関係）を反映させる。
query contextを反映させる場合、この論文の実験ではuserがqueryを含む文章を指定しているが、文章ではなくcontextを反映させる方が良い結果を得られる。何をcontextにするかにはいろいろなアイディアがある（後述）。
PageRankはもともとウェブページにofflineでランク付けして(rank vector)、その順番に検索結果を出すアルゴリズムだが、Topic-Sensitive PageRankではrank vectorを複数用意し、その合成によって結果を出す。vectorはODPのトップカテゴリーに準じた１６本（わかりやすいようにそれぞれにトピック（カテゴリー）の名前を付ける）。

アルゴリズムの詳細

biased PageRank vectorの作り方

PageRankでのrank vectorは以下の式で与えられる。
　　　 $\vec{Rank} = (1-\alpha)M \times \vec{Rank} + \alpha\vec{p}$
ここで1-αはdamping factor（日本語訳不明）で、 $\vec{p}=1/N$ （Nはページの総数）。
Topic-Sensitive PageRankでは $\vec{p}$ を以下の式で与えられるように変えたものでvectorを計算する。
　　　 $v_{ji} = \left{\frac{1}{T_j}\hspace{20pt}i\in \hspace{5pt}T_j,\\ 0\hspace{32pt}i\hspace{2pt}\notin \hspace{5pt}T_j,\right$

$T_j$ はODPのカテゴリー $c_j$ に含まれるURLの集合。 $i$ はページを表す。

検索時のvectorの合成方法

まずqueryまたはquery context（qまたはq'）に対して、どのvectorが重要なのかの重みを与える計算を以下の式でする。
　　　 $P(c_j|q') = \frac{P(c_j) \cdot P(q'|c_j)}{P(q')} \propto P(c_j) \cdot \prod\limit_i P(q'_i|c_j)$
次に以下の式で与えられるスコアに従ってすぺてのページをランク付けする。
　　　 $s_{qd}=\sum\limit_j P(c_j|q')\cdot rank_{jd}$
合成の計算方法はいたってシンプル。

実験

・Topic-Sensitive PageRankの特徴を示す実験
・一般のPageRankとの比較実験
・query context利用の効果を示す実験
を行っている。
速度を評価する実験は行っていない。

Topic-Ssnsitive PageRankの特徴を示す実験

まずランキングの類似性を評価するための関数を二つ定義する。
$OSim(\tau_1,\tau_2)=\frac{|A \cap B|}{n}$
$KSim(\tau_1,\tau_2)=\frac{\(u,v):\tau'_1,\tau'_2 \mbox{ agree on order of } (u,v),u\neq v|}{|U||U-1|}$
$OSim$ は単純に二つのランキングの上位nページの重複の度合いを表す関数。今回はn=20で実験。
これだけだと二つのランキングの上位nページの配列が考慮されないのでそれを考慮に入れた関数が $KSim$ 。

αの値によってランキングの偏り具合が調節できるが、α=0.25とα=0.05の二つのランキングを上記の二つの関数を用いて比べてみたところ、どちらの関数もかなり高い数値が出た。よってαは結果にたいした影響を及ぼさないのでより良いαの値を見つけようとすることはせず、今回はα=0.25で実験することとした。

上記の二つの関数を用いて１６個のbiased rankingsと１つのNoBiased rankingとからなる１７のランキングのすべてのペアで類似性を調べたところ、どちらの関数でもすべてかなり低い数値が出た。つまりそれぞれのランキングはまるで似ていないということがわかった。

"bicycling"というqueryに対して１７のランキングのトップ５を比べている。

一般のPageRankとの比較実験

３５のtest queryで $P(c_j|q)$ を計算したところ最も高い値がでたvectorのトピックは直感的に正しかった。またトップ３のvectorを見るとスコア算出の際に４位以降のvectorを考慮に入れる必要がないだろうということがわかったので、実験ではトップ３のvectorだけを使うこととした。

比較実験では３５のtest queryのうち１０を使い、５人のボランティアによって行った。
ボランティアはPageRank Vectorによって算出された結果のトップ１０と、Topic-Sensitive PageRankによって算出された結果のトップ１０が見せられ、１０のURLのうち適切と思われるURLを選び、またどちらの結果がより良いかを答える。
結果、ほとんどのqueryでTopic-Sensitive PageRankの方が良い成績を収めた。

query context利用の効果を示す実験

"blues"という単語がまったく別の意味で使われている２つのWebページから"blues"というqueryで検索するという設定での実験。
query contextにはページ全体の文章を指定し、 $P(c_j|q')$ の値が最も高かったvectorだけを使って結果をだし、一般のPageRankの結果と比べて、良い結果が出ていると判断。

様々なquery contextの提案

・検索履歴
・サーチエンジンの階層との連動（そのときuserがいる階層の情報をcontextにする）
・userのブラウジングパターン
・userのブックマーク
・userのメール

今後の改善点

biased rank vectorを増やしつつも計算速度を落とさないようにすること。
ODPをトレーニングに使い、ゆくゆくはすべてのページをにtopic weightをつけてそれにより計算を行うようにすること。