ランキング学習〜情報検索への機械学習の応用〜

はじめに

本記事は CodeZine に掲載されました。こちらで読めます。

近年、「AI」という言葉をよく見かける背景には、機械学習を使った様々な手法と飛躍的進歩があります。

この機械学習の大きな手法の１つに「教師あり学習」と呼ばれる手法があります。この教師あり学習には大きく分けて２つのタイプがあります。１つは、ある画像を「犬か否か」推定したり、「犬、猫、鳥」のどれに分類されるか推定するといった「分類」です。もう１つは、ある出来事が起こる確率を推定するといった「回帰」です。

どちらのタイプも教師あり学習ではよく用いられますが、本記事で紹介する「ランキング学習」は一般的な「分類」や「回帰」とは少し異なります。ランキング学習は近年発展してきた技術のため、特に日本語の情報が非常に少なく、英語の情報がほとんどです。そのため、本記事では日本語でランキング学習を詳細に解説していきたいと思います。

モチベーション

検索エンジンに対して、ユーザがクエリを投げて検索する場面を考えましょう。下の図は、検索エンジンが管理する文書を全体集合とするベン図です。右側の円は、ユーザがクエリQ を検索したときに、検索エンジンから返して欲しいと考える文書集合を表します。一方左側の円はクエリQを検索したときに実際に検索エンジンから返される文書集合です。

右側と左側の円が重なっている部分 B はシステムが正しく返せた文書集合と言えます。左側の円で、右側の円と重なっていない部分 A はシステムが誤って返してしまった文書集合で検索誤りといい、逆に C は検索漏れといいます。

検索漏れと検索誤りを完全になくすのが理想的ですが、それは非常に難しいことです。検索システムができるのは (A + B) を大きく、または小さくすることです。例えば小さくすると、検索誤りを減らすことができますが、検索漏れが悪化します。

それに対して大きくすると、ユーザの要らない文書が多くなり、求めている文書が見つかりにくくなるので検索誤りが悪化します。

検索漏れと検索誤りはトレードオフの関係にあり、この関係は適合率と再現率のトレードオフで説明できます。適合率（P, Precision) と再現率 (R, Recall)は以下のように表現できます。

再現率も適合率も１が最大値です。A >> B >> C という風に左側の円を大きくすると、(A+B) >> B なので適合率が下がりますが、(B + C) 〜 B　なので再現率が上がります（1に近づきます）。一方、A << B << C という風に左側の円を小さくすると、(A + B) 〜 B なので適合率が上がり、(B + C) >> B なので再現率が下がります。

A が大きくなることでユーザの求めている情報が見つかりにくくなる問題の解決策として、ランキング学習が使えます。B に含まれる文書を上位に表示されるようにランキングを調整すれば、ユーザが求めている情報が見つかりやすくなります。

ランキング学習では、まず通常の検索結果の上位 N 件を抽出します。次にランキング学習によって得られたモデルを使ってこの N 件をリランクすることでランキングをさらに改善します。ECサイトはランキングの精度が1パーセント上がるだけで売り上げが大きく変わることもあります。そのため、上位 N 件のリランクといった、わずかな検索精度の向上であってもそれに挑む価値はあります。

一般的な機械学習との違い

まずは感覚的な違いですが、一般的な回帰法や分類法では、ある文書の特徴量は学習器と抽出方法が変わらなければ基本的には変わりません。それに対して LTR ではクエリとそれに対する文書のリストという形でなければなりません。ある文書が複数のクエリでヒットする可能性がありますが、クエリによってその文書の特徴量が違います。実際に使う特徴量はクエリ従属でなければ、クエリに対してランクをつけられません。つまり、同じ文書であっても、クエリが異なれば異なる文書として扱われます。例えば、クエリを占める単語の文書中での出現頻度を表す TF (Term Frequency) という特徴量があります。以下は TF の一例です。

上記の式のd は文書d のことを表し、t は単語t のことを表します。分母では単語の出現頻度を文書の単語数で正規化しています。TF の値は選ぶ単語によって変わります。ある文書に「iPad」と「iPhone」という単語が両方あるかもしれませんが、「iPhone」の方が出現頻度が多ければ、「iPhone」というクエリの方が TF の特徴量の値が高いです。

一般的な回帰法や分類法と LTR の関係

従来の機械学習の分類法や回帰法の考え方を、ある程度 LTR に応用できます。回帰法の方は、出力されたスコア・測定値を関連度という風に捉え、スコアの高い順で表示すればランキングを得られます。分類法の方は、５つ星が最も関連度の高い文書、１つ星が全く関連性がないという風にクエリに対して文書を１つ星〜５つ星に分類し、星の数の高い順で表示すればランキングを得られます。しかしランキング学習では、スコアそのもの、星の数そのものよりも、文書間の相対的なスコアが重要です。例えば以下の二つのケースを考えましょう。A, B, C, D, E という5つの文書があり、以下の表では回帰学習器によって計算されたスコア（推定値）の高い順でソートされています。

上記の左側の場合は、それぞれの文書の推定値は正解とかなり違いますが、正解に基づいたランキング（スコアの高い順）と完全一致しています。それに対して右側の推定値は比較的スコアに近いですが、ランキングはズレています。回帰学習器の精度を評価するときは、MSE (Mean Squared Error, 平均二乗誤差)が多用されていますが、この場合それを使えば右側の学習器の方が精度が良いと判断されてしまいます。

評価手法

ランキング学習では、MSE、 Classification Accuracy、Logarithmic Loss などの一般的な機械学習で多用されている評価手法よりも、より適切にランキングの良さを評価できる手法を利用します。例として以下二つの評価手法を紹介します。

MRR

シンプルな例としては MRR というものがあります。MRR は Mean Recipricol Rank の略で、学習器によるランキングで一番上位の関連している文書のランクを表します。そのランクが上位なほど MRR が大きくなり、１位ならば MRR の最大値（１）になります。MRR は、関連している文書をできるだけ１位にしたいときには使えますが、デメリットは関連度（スコア・星の数）と２位以下の文書を一切考慮しないというところです。MRRは以下の式で計算できます（以下の式は Q 個のクエリの平均値を計算しています）。

NDCG

LTR で多用されている NDCG という評価手法があります。NDCG は Normalized Discounted Cumulative Gain の略で、正規化された DCG という意味です。そこでまず DCG を説明します。

j は文書j の順位で y は文書j の本当のスコア・クラス（数字が高い方が関連度が高いというもの）です。例えば j=5 は５位の文書のことを指し、y₅ はその文書のスコアを表します。η は Discount Factor (DCG の D)で G は Cumulative Gain (DCG の CG)です。まずはηですが、j が大きい方が、分母が大きいので DCG が小さくなります。つまり、下位になるほど、DCG への影響が小さくなります。G の方ですが、関連度が高い方が大きくなります。DCG が一番大きくなるには、文書リストが高い順でなければなりません。この理想の DCG を Z と表すと、NDCG を以下のように表せます。

NDCG@k はランキングのk位まで計算するという意味で、例えばトップ１０のランキングを評価したいという場合は、NDCG@10 で評価できます。

LTR の３つの手法（ポイントワイズ、ペアワイズ、リストワイズ）

上記のランキング評価手法とともに一般的な機械学習の回帰アルゴリズムや分類アルゴリズムを用いれば、ランキング学習を実現できます。これは LTR の「ポイントワイズ手法」に相当します。ただし、評価手法を変えるだけで学習器が評価的にいい具合に学習するわけではありません。ポイントワイズ手法では、たとえ NDCG でモデルを評価しても、個別の文書の推定スコアに対して MSE や Classification Accuracy などの損失関数を用いるため、個々の文書が独立した正解スコアへと誘導されてしまいます。前述の表で示したとおり、個別の文書の推定スコアを改善しても、文書集合で考えた場合に、必ずしもよいランキングを得られるとは限りません。

良いランキングを得るために、この後に説明する「ペアワイズ手法」と「リストワイズ手法」が開発されました。２つの手法はポイントワイズ手法よりも性能が高いですが、ポイントワイズ手法のメリットは比較的単純（実装しやすい）というところと教師データは入手（作成）しやすいというところです。

「ペアワイズ手法」では、モデルから良いランキングが出力されるように文書のペアの間の関係性を考慮する損失関数を使います。例えば文書B よりも文書A の方が関連度が高い場合は、(文書A, 文書B, 1) または (文書B, 文書A, 0)という感じに表現します。様々なアルゴリズムや損失関数がありますが、一つの例を挙げると、LTR で有名な RankNet というニューラルネットワークのアルゴリズムがあり、ペアワイズのクロスエントロピー誤差（交差エントロピー誤差）を用いています。ペアワイズは文書間の関係性を考慮するので、理屈ではポイントワイズより精度が高いはずですが、訓練データはポイントワイズよりも入手しにくいです。また、理想的には文書間の関係性ではなく、各文書の絶対ランクを考慮した方が精度が高いでしょう。

「リストワイズ手法」では、クエリに対するランキングに基づいた損失関数を使います。ペアワイズよりも少しイメージしづらいと思いますが、一つの例としては ListNet という RankNet に基づいたリストワイズのアルゴリズムがあります。実装はほぼ同じですが、損失関数は RankNet と異なり、ある文書が１位になる確率を用いたクロスエントロピー誤差を使っています。リストワイズの訓練データの入手は３つの手法の中で最も難しいでしょう。

一般的な回帰法や分類法の機械学習のアルゴリズムを LTR に適応するには上記の３つの手法と評価手法を考えて、ちょっとした工夫が必要ですが、学習する部分は他の機械学習のアルゴリズムと変わりません。

LTR のモデルを構築してみよう

ペアワイズの LTR アルゴリズムを使ってモデルを構築しましょう。モデル構築に利用するツールは Learning to Rank for Apache Lucene (LTR4L) という著者も開発に携わっているオープンソースのランキング学習フレームワークです。LTR4L を使うには、Apache Ant、Ivy と Java 8 以上のインストールが必要です。

モデル構築に利用する学習データは Microsoft社が提供している LETOR4.0 の MQ2008 というランキング学習用のデータです。MQ2008 のデータは以下のような形になっています。

0 qid:10056 1:0.179567 2:0.000000 3:0.000000 4:0.000000 5:0.174455 ...
2 qid:10056 1:0.114551 2:1.000000 3:0.666667 4:0.000000 5:0.143302 ...
1 qid:10056 1:0.065015 2:0.111111 3:0.333333 4:0.000000 5:0.065421 ...

各行は1つの文書です。一番左の数値は正解（ラベル）で、{0, 1, 2} の3段階になっています。2 はクエリに対して最も関連している文書を指し、0 はクエリに対して関連していない文書を指します。qid はクエリの id を表し、`1:0.179567 2:0.000000` は1番目の特徴量（本文の TF）と2番目の特徴量（anchor の TF）の値を表現します。

以下のリンクよりデータセットをダウンロードできます（Download のところに "download here" というリンクをクリックして、MQ2008.rarをダウンロードします）。データセットの詳細な仕様も書かれています。

https://www.microsoft.com/en-us/research/project/letor-learning-rank-information-retrieval/#!letor-4-0

上記リンクより学習データをダウンロードして解凍した上で以下を実行します。

git clone https://github.com/LTR4L/ltr4l.git
cd ltr4l
ant ivy-bootstrap
ant package
mkdir data
mv /path/to/MQ2008 data

これで LETOR 4.0 の MQ2008 のデータセットで学習を行えます。今回は LambdaRank という LTR アルゴリズムで実行します。LambdaRank はペアワイズのニューラルネットワークベースのアルゴリズムです。 LambdaRank のコンフィグファイルのパスは ltr4l/confs/lambdarank.json であり、中身を見るとデフォルトのエポック数、学習データのパス、隠れ層の活性化関数などの設定が見られます。デフォルトの評価手法は、NDCG@10 となっています。

  "evaluation" : {
    "evaluator" : "NDCG",
    "params" : {
      "k" : 10
    }
  }

以下のように MQ2008 のデータセットを使って、LambdaRank で学習を行えます。

./train lambdarank

上記コマンドを実行すると、以下のような出力が表示されます。

1 tr_loss: 0.715475 va_loss: 0.718519 evaluation: 0.253901
2 tr_loss: 0.678584 va_loss: 0.677052 evaluation: 0.488971
3 tr_loss: 0.676376 va_loss: 0.672630 evaluation: 0.458577
4 tr_loss: 0.674833 va_loss: 0.670501 evaluation: 0.432308
5 tr_loss: 0.654248 va_loss: 0.649956 evaluation: 0.448449
6 tr_loss: 0.626821 va_loss: 0.624697 evaluation: 0.466102
7 tr_loss: 0.610173 va_loss: 0.613599 evaluation: 0.466770
8 tr_loss: 0.601708 va_loss: 0.610180 evaluation: 0.469990
9 tr_loss: 0.592280 va_loss: 0.602943 evaluation: 0.474676
10 tr_loss: 0.576621 va_loss: 0.586273 evaluation: 0.485357
11 tr_loss: 0.555400 va_loss: 0.562118 evaluation: 0.497641
12 tr_loss: 0.532048 va_loss: 0.535077 evaluation: 0.512376
13 tr_loss: 0.511615 va_loss: 0.511221 evaluation: 0.526410
14 tr_loss: 0.497519 va_loss: 0.494673 evaluation: 0.529280
15 tr_loss: 0.490013 va_loss: 0.487210 evaluation: 0.531615
16 tr_loss: 0.488278 va_loss: 0.488166 evaluation: 0.530681
17 tr_loss: 0.490726 va_loss: 0.496021 evaluation: 0.531085
18 tr_loss: 0.496008 va_loss: 0.508311 evaluation: 0.529209
19 tr_loss: 0.501833 va_loss: 0.520882 evaluation: 0.526741
20 tr_loss: 0.505837 va_loss: 0.529824 evaluation: 0.524291

上記出力の tr_loss と va_loss は学習データ（tr）と評価データ（va）で計算された損失です。 evaluation は評価値で評価データにおいて計算されます。上記出力では学習が進むと損失が下がるのに対し，評価値は上がっていることが確認できます。学習が終わると、構築したモデルは model/lambdarank-model.json に保存されます。

学習データと評価データの他に、テストデータもあります。テストデータとは構築したモデルを評価するためのデータで、モデル構築時に全く使わないデータです。モデル構築時に一切使っていないデータなので、モデルが未知データにどれほど強いか評価するために使います。以下のコマンドでテストデータを用いて構築したモデルを NDCG@10 で評価します。

./predict lambdarank
# 出力
Evaluation score: 0.465339

おわりに

ランキング学習は検索エンジンにおけるランキング改善を目的として研究・開発が始まりましたが、それ以外にもいろいろな場面で応用できると考えられます。たとえば、

アマゾンや楽天市場などのインターネット通販で見られるオススメの商品リストの作成・改善
パーソナライズ検索
検索語のオートコンプリート

など、文書などの集合に順序をつける問題に広く応用できます。実際に上記のようなアプリケーションにランキング学習のモデルをデプロイしている企業はいくつかあります。

ランキング学習用の公開されているデータセットがあり、自分でランキング学習をやってみたい人は、前章で用いた Microsoft社提供の LETOR や OHSUMEDなどをお勧めします。

Search This Blog

カムのブログ