検索アルゴリズムの１つ、ローカルランク理論について。
検索アルゴリズムについてです。今日は Ranking Search Results By Reranking the Results Based on Local Inter-Connectivity という論文です。これは簡単に「ローカルランク理論」とも呼ばれるもので、Google が特許を取得しているものです。考案者は Krishna Bharat 氏。
内容は次の通りです。
A search engine for searching a corpus improves the relevancy of the results by refining a standard relevancy score based on the interconnectivity of the initially returned set of documents. The search engine obtains an initial set of relevant documents by matching a user's search terms to an index of a corpus. A re-ranking component in the search engine then refines the initially returned document rankings so that documents that are frequently cited in the initial set of relevant documents are preferred over documents that are less frequently cited within the initial set.
例をあげて説明しましょう。たとえば「ひな祭り」で検索をします。
まず「ひな祭り」という言葉を含む文書を見つけ出します（テキストマッチですね）。一連の「ひな祭り」文書を見つけたら、それぞれの文書とキーワードとの適合性スコア（ Relevancy Score）を算出します。つまりキーワードとの適合度を計算して「ひな祭り」というキーワードに最も合致するページを選択するのです（"PageRankなしの Google" を想像して下さい）。
この計算が終わったら、これら一連のひな祭り文書内でのリンク状況を分析、参照元が多い文書ほど重要であると評価するローカルランクのスコアリングを行います。つまり一連の文書内の中で他からたくさんリンクされているページほど重要だと判断するのです（一連の文書内の中でのPageRank を出すことを想像して下さい）。この算出結果を先の適合性スコアに反映させ修正することで「ひな祭り」に関する文書で最も適切なものを選択できるのです（PageRank の代わりに「ひな祭り」を含んだ文書内で算出した PageRank を適用することを想像して下さい）。
PageRank がインターネット上に存在する全てのWebページ間の相互関連性（リンクのつながり）をスコアリングしようとするのに対して、この検索アルゴリズムは最初に採りだしたある集合内の文書内での相互関連性をスコアリングしようとすることから、「ローカル」（＝PageRank のインターネットの全世界に対する"ローカル"）と呼んでいるのです。
さて、このローカルスコア理論ですが現在の Google にこのアルゴリズムが実装されているか否かは意見が分かれるところです。私個人的には、まだ Google はこのアルゴリズムを利用していないと考えています。このアルゴリズムが作用していると思われる適当な証拠がないからです。
Ranking Search Results By Reranking the Results Based on Local Inter-Connectivity
※ Krishna Bharat氏・・・Google上級研究員。米ジョージア工科大学にてコンピュータサイエンス博士号を取得
※ アルゴリズムの仕組みをイメージしやすくすることを優先するため、本来のアルゴリズムの仕組みとは異なる説明がある点をご了承下さい
