CodeZine(コードジン)

特集ページ一覧

話題の「ランキング学習」とは? 回帰法・分類法との違いからモデル構築まで

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2018/12/17 11:00

目次

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

 まずは感覚的な違いですが、機械学習の中でも比較的一般的な回帰法や分類法では、ある文書の特徴量は学習器と抽出方法が変わらなければ基本的には変わりません。

 それに対してランキング学習では、クエリとそれに対する文書のリストという形でなければなりません。ある文書が複数のクエリでヒットする可能性がありますが、クエリによってその文書の特徴量が違います。実際に使う特徴量はクエリ従属でなければ、クエリに対してランクをつけられません。

 つまり、同じ文書であっても、クエリが異なれば異なる文書として扱われます。例えば、クエリを占める単語が文書中での出現頻度を表す「TF(Term Frequency)」という特徴量があります。以下はTFの一例です。

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

一般的な回帰法や分類法とランキング学習の関係

 従来の機械学習の分類法や回帰法の考え方を、ある程度ランキング学習に応用できます。

 回帰法では、出力されたスコア・測定値を関連度と捉え、スコアの高い順で表示すればランキングを得られます。一方分類法では、5つ星が最も関連度の高い文書、1つ星が全く関連性がない、といった風にクエリに対して文書を1~5つ星に分類し、星の数の高い順で表示すればランキングを得られます。

 しかしランキング学習では、スコアそのもの、星の数そのものよりも、文書間の相対的なスコアが重要です。例えば以下の2つのケースを考えましょう。A, B, C, D, Eの5つの文書があり、以下の表では回帰学習器によって計算されたスコア(推定値)の高い順でソートされています。

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

評価手法

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

MRR

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

NDCG

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

 「j」は「文書j」の順位で、「y」は「文書j」の本当のスコア・クラス(数字が高い方が関連度が高いというもの)です。例えば「j=5」は「5位の文書」のことを指し、「y5」はその文書のスコアを表します。ηはDiscount Factor(DCGのD)でGはCumulative Gain(DCGのCG)です。まずはηですが、jが大きい方が分母が大きいのでDCGが小さくなります。

 つまり、下位になるほどDCG への影響が小さくなります。Gの方ですが、関連度が高い方が大きくなります。DCGが一番大きくなるには、文書リストが高い順でなければなりません。この理想のDCGをZと表すと、NDCGを以下のように表せます。

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

LTR の3つの手法(ポイントワイズ、ペアワイズ、リストワイズ)

 上記のランキング評価手法とともに一般的な機械学習の回帰アルゴリズムや分類アルゴリズムを用いれば、ランキング学習を実現できます。これはランキング学習の「ポイントワイズ手法」に相当します。

 ただし、評価手法を変えるだけで学習器が評価的にいい具合に学習するわけではありません。ポイントワイズ手法では、たとえNDCGでモデルを評価しても、個別の文書の推定スコアに対して MSEやClassification Accuracyなどの損失関数を用いるため、個々の文書が独立した正解スコアへと誘導されてしまいます。前述の表で示したとおり、個別の文書の推定スコアを改善しても、文書集合で考えた場合に、必ずしも良いランキングを得られるとは限りません。

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

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

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

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


  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • Kamuela Lau(カムエラ ラウ)

     米国ハワイ州出身。2014年に米国マサチューセッツ州の Williams College を物理学と日本語学の二重専攻で卒業後来日。株式会社ロンウイットでランキング学習など機械学習を中心に、製品開発や顧客コンサルティングの業務に従事。米国の Georgia Institute of Technol...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5