【情報検索】Learning to Rank の基礎

Learning to Rank について調べたことを備忘録として残しておきます。初学者のため, 詳細や不明な点は参考文献をご覧下さい。

ランキング問題

ランク学習の典型的なアプリケーションに文書検索システムがある。
システムは文書集合 D = {d_1, d_2, …, d_n} を保持している。クエリ集合を Q = {q_1, q_2, …, q_m} として, クエリ q_i が与えられると, システムはクエリを含む文書を検索しランク付けした文書のリストを返す。これはクエリと文書を引数に取る関数 f(q, d) でランキングモデル (ranking model) と呼ぶ。

ランク学習

ランク学習 (Learning to Rank; LTR) は一般にランキング問題を教師あり機械学習を用いて解く方法で, ランキング学習とも呼ばれる。
ランク学習と似ている概念として, 順序学習 (Preference learning) がありこちらは優先度学習とも呼ばれる。

ランク学習は情報検索 (IR) や自然言語処理 (NLP) を初め多くの分野に応用されている。実践的なアプリケーションとして以下がある。

  • 文書検索 (Document retrieval)
  • 協調フィルタリング (Collaborative filtering)
  • キーワード抽出 (Key term extraction)
  • 文書要約 (Document summarization)
  • 重要メールの振り分け (Important email routing)
  • センチメント分析 (Sentiment analysis)
  • 製品評価 (Product rating)

ラベル集合を Y = {1, 2, …, l} とする。各ラベルはクエリと文書の適合度 (relevance grade, relevance level) を表す。
Relevance の表現は, 適合しているか否かの二値表現 {0,1} や Perfect > Excellent > Good > Fair > Bad のように grade (level) を用いた表現がある。複数の文書の関係として, 文書 d_i より 文書 d_j の方が適合しているという Pairwise preference や, Total order (全順序) が与えられる場合がある。

ランク学習で用いるデータセット S は, クエリ q_i と関連付けられた文書 D_i, ラベル y_i ∈ Y で構成され S = {(q_i, D_i), y_i} である。

素性ベクトル (feature vector) は素性関数 φ を用いて x_i,j = φ(q_i, d_i,j) で表す。(q_i, d_i,j) はクエリ-文書ペア (query-document pair) である。つまり, 素性ベクトル x_i,j はクエリと文書の両方に依存する。素性ベクトルを用いるとデータセットは S’ = {x_i, y_i} と表現できる。
ランク学習においても他の一般的な教師あり機械学習と同様に特徴エンジニアリングが重要となる。

ランク学習におけるデータラベリングは主に人間による判定 (human judgments) とクリックログのようなデータから求める方法の2つがある。前者は明示的フィードバック (explicit feedback), 後者は暗黙的フィードバック (implicit feedback) に分類される。人間による判定の場合は平均的なユーザの視点で判定を行う。

モデルの評価は情報検索で広く使われる以下の評価尺度を用いて行う。

  • DCG (Discounted Comulative Gain)
  • NDCG (Normalized Discounted Comulative Gain)
  • MAP (Mean Average Precison)
  • kendall’s Tau

全体的なランキングの評価はテストデータ全体のクエリに対する評価値を平均化などにより要約し得られる。

ランク学習のアプローチ

一般にランキング問題は分類タスクや回帰タスクとはやや異なる。
F(・) を素性ベクトルのリストを取りスコアのリストに写像する関数とする。F(x) = (f(x_1), f(x_2), …, f(x_n)) である。
このとき, 損失関数は L(F(x), y) と表現できる。情報検索の分野で真の損失関数は NDCG や MAP を用いて定義される。例えば以下となる。

    \begin{eqnarray*} L(F(x), y) = 1.0 - NDCG \end{eqnarray*}

しかし, DCG は凸関数でも滑らかでもないので勾配法に基づく教師あり学習では問題になる場合があるため, 代理損失 (surrogate loss function) を用いる。ランク学習では代理損失の定義の仕方により3つの異なるアプローチに分かれる。いずれの代理損失も 1.0 – NDCG の上界 (upper bounds) であるため, 代理損失の最小化は DCG の最適化に役立つ。

Pointwise approach

Pointwise loss は単一のデータに対して定義される。

    \begin{eqnarray*} L'(F(x), y) = \sum_{i=1}^{n} (f(x_i) - y_i)^2 \end{eqnarray*}

Pointwise approach では順序回帰や整数回帰などの回帰手法や分類手法が用いられる。全ての文書に対して整数のランクを予測できなくても, 文書 d_i を d_j d_j より先に順序付けなければならないという半順序制約さえ学習できれば十分な場合がある。

Pointwise approach のアルゴリズムには以下がある。

  • Subset Ranking (2006)
  • McRank (2007)
  • Pranking with Ranking (2002)

Pointwise Approach ではそれぞれのデータを個別に扱っており, q に対して d_i よりも d_j の方が関連性が高いという情報が分かっていても全順序までは分からないことがある。

Pairwise approach

Pairwise approach は半順序関係を直接的に扱いランク学習を行う。入力のペア (x_i, x_j) に対して Preference (y_i,j ∈ {-1,1}) を出力する。
Pairwise loss はデータのペアに対して定義される。

    \begin{eqnarray*} L'(F(x), y) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \phi(sign(y_i - y_j), f(x_i) - f(x_j)) \end{eqnarray*}

Pairwise approach のアルゴリズムには以下がある。

  • RankNet (2005)
  • FRank (2007)
  • RankBoost (2003)
  • Ranking SVM (2000)
  • IR SVM (2006)

Pairwise approach は半順序から必ずしも矛盾しない全順序が作れない場合もある。また, 全順序を含むデータセットに対して Pairwise approach を適用するには Pair の生成が学習の効率性やスケーリングの観点で問題となる場合がある。

Listwise approach

Listwise approach は q に対して n 個の文書が全順序付けられている場合に適用可能なアプローチ。
Listwise loss はデータのリストに対して定義される。AdaRank の損失関数は Listwise loss で以下である。

    \begin{eqnarray*} L'(F(x), y) = exp(-NDCG) \end{eqnarray*}

Listwise approach のアルゴリズムには以下がある。

  • SoftRank (2008)
  • SVM-MAP (2007)
  • AdaRank (2007)
  • ListNet (2007)
  • ListMLE (2008)

検索エンジンのように全順序を返すようなアプリケーションでは学習段階から全順序の情報を扱う Listwise approach が良い精度を示すことが知られている。

LETOR

LETOR (LEarning TO Rank) は Microsoft Research が公開しているランク学習で広く使われているベンチマークデータセットである。最近の論文を見ても提案手法の検証によく使われている。クエリID, 文書ID, ラベルに加えて素性ベクトルが含まれている。
教師あり学習用の MQ2007 以外にも半教師あり学習用の MQ2007-semi や Listwise approach 用の MQ2007-list などがある。

MQ2007 には 1700 のクエリが含まれる。train.txt の最初の数行をみてみる。

0 qid:7968 1:0.000000 2:0.000000 3:0.000000 4:0.000000 5:0.000000 6:0.000000 7:0.000000 8:0.000000 9:0.000000 10:0.000000 11:0.000000 12:0.000000 13:0.000000 14:0.000000 15:0.000000 16:0.005175 17:0.000000 18:0.181818 19:0.000000 20:0.003106 21:0.000000 22:0.000000 23:0.000000 24:0.000000 25:0.000000 26:0.000000 27:0.000000 28:0.000000 29:0.000000 30:0.000000 31:0.000000 32:0.000000 33:0.000000 34:0.000000 35:0.000000 36:0.000000 37:0.000000 38:0.000000 39:0.000000 40:0.000000 41:0.000000 42:0.000000 43:0.055556 44:0.000000 45:0.000000 46:0.000000 #docid = GX000-00-0000000 inc = 1 prob = 0.0214125
1 qid:7968 1:0.205882 2:0.000000 3:0.000000 4:0.000000 5:0.205882 6:0.000000 7:0.000000 8:0.000000 9:0.000000 10:0.000000 11:0.200330 12:0.000000 13:0.000000 14:0.000000 15:0.200332 16:0.035576 17:0.103448 18:0.136364 19:0.500000 20:0.034295 21:0.928681 22:0.776598 23:0.751439 24:0.779643 25:0.000000 26:0.000000 27:0.000000 28:0.000000 29:0.000000 30:0.000000 31:0.000000 32:0.000000 33:0.000000 34:0.000000 35:0.000000 36:0.000000 37:0.916516 38:0.686669 39:0.674704 40:0.708795 41:0.217889 42:0.272727 43:0.000000 44:0.333333 45:0.420000 46:0.000000 #docid = GX000-78-12152116 inc = 1 prob = 0.728769
0 qid:7968 1:0.000000 2:0.000000 3:0.000000 4:0.000000 5:0.000000 6:0.000000 7:0.000000 8:0.000000 9:0.000000 10:0.000000 11:0.000000 12:0.000000 13:0.000000 14:0.000000 15:0.000000 16:0.022639 17:0.275862 18:0.272727 19:0.875000 20:0.022777 21:0.000000 22:0.000000 23:0.000000 24:0.000000 25:0.000000 26:0.000000 27:0.000000 28:0.000000 29:0.000000 30:0.000000 31:0.000000 32:0.000000 33:0.000000 34:0.000000 35:0.000000 36:0.000000 37:0.000000 38:0.000000 39:0.000000 40:0.000000 41:0.031069 42:0.090909 43:0.092593 44:0.500000 45:0.680000 46:0.000000 #docid = GX001-08-12129710 inc = 1 prob = 0.0345924
...

各行はクエリ-文書ペア (query-document pair) で, 最初の列はラベル (relevance grade), 2つ目の列はクエリID, それ以降の列は46個の素性が続く。各行の最後には文書IDを含むコメントが記述されている。libsvm format によく似ている形式である。

素性ベクトルは46次元で以下の素性で構成される。

  • TF
  • IDF
  • TF*IDF
  • Document Length
  • BM25
  • LMIR (Language Model for IR)
  • page features (PageRank, Inlink, outlink, URL length etc.)

WWW2009 での LTR のチュートリアル [2] では, LETOR を用いた複数のアルゴリズムの評価実験で Listwise approach が他のアプローチよりも特に上位のランキング結果で利点があることが示されている。

おわりに

参考文献は主に [1,2,3] で, 参考書籍は『AIアルゴリズムマーケティング』 (第4章 検索) です。

[1] A Short Introduction to Learning to Rank
[2] Learning to Rank for Information Retrieval (A tutorial at WWW 2009)
[3] Introducing LETOR 4.0 Datasets
[4] Learning to Rank for Information Retrieval
[5] Support Vector Learning for Ordinal Regression
[6] GitHub: Python learning to rank (LTR) toolkit
[7] 情報検索のための Learning to Rank の概要
[8] ランク学習（Learning to Rank） Advent Calendar 2018