IIR21章まとめ

21章はリンク解析について。PageRankやHITSについて説明している。

Webをグラフとして考える。

以下の点から、リンク解析は重要である。

  • あるページのみを見るよりも、そのページのリンク情報も一緒に見るほうが効果がある。
  • アンカーテキストは、そのページの内容を特徴付けてくれるものであることが多い。

※ただし、常に上記のことが成立するとは限らない。

(例)Google bombs(グーグル爆弾)

ページとは関連性のないキーワードのアンカーテキストを用いた大量のリンクを与えることでGoogle検索エンジンで上位表示させる手法。

有名な例としては、“miserable failure”(みじめな失敗)というキーワードで検索すると、ブッシュ大統領の経歴ページが上位に出ていたことがあった。

引用文分析

引用文分析とは、科学文献の引用文を分析する手法。

共引用類似度

引用文がオーバーラップしている2つの文献の類似度を、共引用類似度(cocitation similarity)といい、特徴の類似性を示してくれる。

引用数による重み付け

他の文献からの引用頻度によって重み付けすることにより、文献のインパクを考える。

これがPageRankの基礎となっている。

PageRank

Web上で、Webサーファーがランダムウォークすることを考える。

あるページからスタートし、リンクをたどりながら他のページへ移動する。

PageRank(ページランク)とは、そのような場合に、サーファーが各ページにいる確率の極限値でランキングする手法である。

ドキュメント i からドキュメント j にリンクされていることを、以下のグラフで表す。

各ページに有用度(1)を割り当て、その有用度をリンクに沿って他のページへと普及させる。

また、ページから複数のリンクが出ている場合は、そのページへの有用度をそれらに均等に分割する。すなわち、以下の式が成立する。

例として、以下のグラフを考える。

まず、リンクされている行に1を入れる。

次に、各列の合計を1にする。

このようにして行列を生成する。

しかし、このままでは以下のような問題が生じる。

Dead end

以下のようにリンクを全くしていないページが存在する場合、ランダムウォークはそこで止まってしまう。

これをDead endといい、これが生じると、PageRank値がうまく定まらない。

これを回避するために、ランダムウォークだけでなく、他ページへランダムにジャンプする確率も考えることにする。

そのページがDead endなら、等しい確率でいずれかのページにジャンプ、そうでなければ、基本的にはランダムウォークを行うが、ある小さな確率(例えば10%など)で、いずれかのページにランダムジャンプすると考える。

これによりDead endは回避される。

しかし、実はこれ以外にもPageRank値がうまく定まらない場合があり、さらに以下のように一般化して考える必要がある。

エルゴード的マルコフ連鎖

マルコフ連鎖が以下の性質を持つ時、エルゴード的であるという。

  • 可約性

全てのページへのパスがある

  • 非振動性

ランダムウォークに周期性がない

このようにすると、例えば以下のグラフは周期性があるために非エルゴード的であり、不適切となる。

Webグラフ上に、このエルゴード的マルコフ連鎖を適用したのがPageRankである。

以下にPageRankの問題点をあげる。

例えば、バックボタンやブックマークを使ったり、検索を行ったりするため、実際にはランダムウォークにならない。

しかし、ページのランキングという目的で考えれば、マルコフモデルで十分であるいえる。

  • 単純にPageRankを用いるだけでは、結果はよくならない。

例えば、"video service"というクエリを考える。

この場合、PageRank値が高く、クエリのタームを含んでいるページが上位にランキングされるので、例えばYahooのようなページ("video"も"service"も含んでいる)が上位にランキングされる。

しかし、これは情報ニーズを完全に無視しており、望んでいる結果ではない。

PageRankだけではこのような問題点が生じるため、実際は他の手法と組み合わせて用いられている。

まとめると、PageRankは完全ではないが、Webランキングにおいてかなり重要な要素の1つであるといえる。

HITS

HITS(Hyperlink-Induced Topic Search)は、PageRankとは異なるランキング手法であり、以下の2つの概念を考える。

  • ハブ…よいリンクを持つページ
  • オーソリティ…よい情報を持つページ

以下が定義である。

  • 多くのよいオーソリティをリンクしているページは、よいハブである。
  • 多くのよいページからリンクされているページは、よいオーソリティである。

このように、相互再帰的に定義されている。

以下にハブとオーソリティの計算手法をあげる。

  • まず、普通にWeb検索を行う。これで得られた検索結果をルートセットと呼ぶ。

  • 次に、ルートセット内のページのリンク先、リンク元情報を全て見付ける。

これで得られた、より大きなセットをベースセットと呼ぶ。

  • ベースセット内で、以下を用いてハブとオーソリティを計算する。

以下に、HITSの問題点をあげる。

トピックドリフト(topic drift)

ベースセット内に情報ニーズとは全く関係のないページが密なリンク構造をもつ場合、情報ニーズに合ったハブ・オーソリティを抽出することができない。

PageRankとHITSの比較

PageRankとHITSの違いを説明する。

  • PageRankは静的なグラフ構造であるため、前もって計算しておけるが、HITSは動的なグラフ構造であるため、クエリが投げられる度に計算しなければならず、コストがかかる。
  • HITSでは、ハブとオーソリティという2つの概念に分けてるが、Web上では、よいハブはだいたいよいオーソリティである。

また、PageRankとHITSのアプローチは異なるが、実際の違いはそこまで大きくない。