情報検索のための Learning to Rank の概要

この記事では以下の文献の第一章の最初の方をざっと読んで得た知識を簡単にメモしています。事前に断っておくと、私は情報検索 (Information Retrieval, IR) の専門家でもありませんし、機械学習の専門家でもありません。誤り等ありましたらコメント欄にてご教示ください。

Tie-Yan Liu
Learning to Rank for Information Retrieval
Foundations and Trends in Information Retrieval: Vol. 3: No. 3, pp 225-331. (2009)
http://www.nowpublishers.com/article/Details/INR-016

導入

情報検索とは情報のデータ群の中からクエリ (query) に合う要素を取り出すことだそうです。
情報検索 - Wikipedia

情報検索には

協調フィルタリング (collaborative filtering)
質問応答システム (question answering)
マルチメディア検索 (multimedia retrieval)
文書要約 (text summarization)

など様々な応用があり得ますが、この文献では特にウェブページの検索エンジンを想定して議論を進めています。

この情報検索について、近年急速に流行っているのが Learning to Rank というアプローチだそうです。特に 2005 年以降

SIGIR
ICML
NIPS
WWW

などの国際会議において流行っていることが丁寧に説明されています。

ちなみにこの Learning to Rank はどうやら日本語ではランキング学習などと訳されるようです。

従来の情報検索

Learning to Rank の定義について説明する前に、それ以前の情報検索手法について簡単に説明を加えています。

Relevance Ranking Models (関連度によるモデル)

このモデルではクエリとデータの関連度を計算し、関連度の高いものを検索結果として提示するというアプローチをとります。

関連度の計算としては、ベクトル空間モデル (Vector Space Model, VSM) がまず取り上げられています。VSM ではクエリとデータの両方がベクトルとして表されており、その関連度は例えば両者の内積などによって計算するというものです。

VSM の具体的な実装として、ここでは TF-IDF モデルが紹介されていました。
tf-idf - Wikipedia

別のアプローチとして Latent Semantic Indexing (LSI) や Probabilistic Ranking Models についても言及されていましたが、ここでは省略します。

Importance Ranking Models (重要度によるモデル)

このモデルではデータそのものの重要度を計算し、重要度の高いものを優先的に検索結果として採用するというアプローチをとります。

その具体例として、PageRank が紹介されていました。
ページランク - Wikipedia

ちなみに私の理解では以下の論文が PageRank を提案しているということになっているのですが、この文献の中では何も引用されていませんでした。PageRank はもはや引用なしで議論できるほど有名になっているということでしょうか。

Brin, S. and Page, L.
The Anatomy of a Large-Scale Hypertextual Web Search Engine
WWW '98
The Anatomy of a Large-Scale Hypertextual Web Search Engine - Stanford InfoLab Publication Server

Learning to Rank による情報検索

さて、従来の情報検索手法における問題点を挙げるとするなら、それはパラメタのチューニングが必要であるという点でした。例えば PageRank では damping factor と呼ばれるパラメタを適切にチューニングしてやる必要があります。

そこで登場するのが、機械学習を活用した情報検索という流れです。機械学習によって、パラメタの自動チューニングや、複数の手法を適切な重みで組み合わせるといったことが可能となります。

Learning to Rank の定義

一般的には、情報検索の問題を機械学習の手法によって解決することを目指すような一連の手法を Learning to Rank と呼んでしまうことが多いことが指摘されています。例えば機械学習によるパラメタの自動チューニングなども Learning to Rank に含まれることがあります。

しかしながら、この文献ではより狭い定義で Learning to Rank という言葉を使おうとしています。より具体的には、以下の 2 つの特徴を持つ手法を Learning to Rank であると定義しています：

Feature Based: データが全て特徴量を用いて表現されていること。
Discriminative Training: 学習のプロセスが一般的な (教師付き) 機械学習のフレームワークによく沿っていること。

この辺りの読み込みが甘く、厳密な理解はできていませんが、簡単に言って、Learning to Rank は「(教師付き) 機械学習によって特徴量の最適な組み合わせ方を発見する一連の手法群」と考えることができそうです。

Learning to Rank のフレームワーク

ここから先はよく読み込めていないので省略しますが、多くの手法は以下の 3 種類に大別できるそうです：

The Pointwise Approach
The Pairwise Approach
The Listwise Approach