ランク学習ってどうやって学習するの？学習データ・特徴量・損失関数

この記事はランク学習（Learning to Rank） Advent Calendar 2018 - Adventarの2本目の記事です

この記事は何？

前回の記事でランク学習の導入を紹介しました。
www.szdrblog.info

この記事では、実際にランク学習ではどのような学習データを扱うのか、どんな特徴量を使うのか、どんな損失関数を最適化するのかを紹介したいと思います。

ランク学習における学習データ

ランク学習における学習データは、よくある分類問題や回帰問題とはちょっとだけ形式が異なります。

前回の記事でチラッと紹介しましたが、ランク学習では「検索キーワード」・「検索キーワードに対応する検索結果リスト」が学習データとして与えられます。

もう少し形式的に言うと、 $Q$ 個のサンプルを含んだ訓練データがあり、各サンプルは「検索キーワード」と「検索キーワードに対応する検索結果リスト」のペアです。

検索キーワード $q$ の検索結果リストには、 $m_q$ 個の文書が含まれています。

検索結果リストの各文書 $d$ には、ラベル $y_{q,d}$ が付与されており、 $K$ 種類の値を取るカテゴリ値とします。
このラベルは検索キーワードと文書の関連度を表しており、例えば「Perfect(4)・Excellent(3)・Good(2)・Fair(1)・Bad(0)」の5段階評価が用いられます。

また、検索キーワード $q$ と文書 $d$ のペアから、特徴量 $\mathbf{x}_{q,d}$ が作られるとします。

まとめると、
$(\mathbf{x}_{q, d},y_{q, d}),\ q=1, \dots, Q,\ d=1, \dots, m_q$
という学習データを、ランク学習では扱います。

…ということをざっくりと絵にしてみました。

f:id:sz_dr:20181203233922p:plain:w400

よくある分類問題や回帰問題と違って、検索キーワード $q$ に学習データが紐づいているということに注意です。

ランク学習における特徴量

ランク学習における基本的な特徴量として「文書から得られる特徴量」「検索キーワードから得られる特徴量」「文書と検索キーワードのペアから与えられる特徴量」が挙げられます。

文書から得られる特徴量

例えば「文書に含まれる単語数」「特定の単語が文書に含まれるかの1-hot表現」などが挙げられます。
ECサイトでは、「商品の価格」や「商品の購入数」なども特徴量として考えられるでしょう。

検索キーワードから得られる特徴量

例えば「検索キーワードの長さ」「その検索キーワードの過去1週間分のリクエスト数」などが挙げられます。

文書と検索キーワードのペアから与えられる特徴量

例えば文書と検索キーワードのマッチングスコアである「TF-IDF」や「BM25」などが挙げられます。検索では当然キーワードとマッチしている文書を取得したいので、文書と検索キーワードのペアから与えられる特徴量はランキングモデルにとって非常に重要です。

もちろん、上で紹介した以外の特徴量はいくらでも考えることができます。
例えば、ユーザーによって検索結果を変えたい（パーソナライズ）ならば、ユーザーのデモグラ情報を特徴量に追加すれば良いでしょう。
食べログのようなサービスならば、ユーザーの位置情報を特徴量に追加しても良いかもしれません。*1

ランク学習における損失関数

ランク学習で用いられる学習データの形式・基本的な特徴量を確認したところで、実際にランク学習ではどのような目的関数（損失関数）を最適化するのかを紹介します。

ランク学習の損失関数は、「1つのサンプルから損失を定義する」「2つのサンプルペアから損失を定義する」「複数のサンプルリストから損失を定義する」という3つの方法があり、それぞれポイントワイズ（pointwise）・ペアワイズ（pairwise）・リストワイズ（listwise）と呼ばれています。

ポイントワイズ（pointwise）

学習データは $(\mathbf{x}_{q,d}, y_{q, d})$ という形式をしていると紹介しました。
もしランキングモデル $f(\mathbf{x}_{q, d})$ が出力するスコア $\hat{y}_{q,d}$ が、各文書のラベルを正確に当てることができれば、検索結果のランキングも正しいものになるでしょう。

そこで、ポイントワイズの損失関数は
$L_{0}=\sum_{q,d}L(f(\mathbf{x}_{q,d}), y_{q, d})$
という形で定義されます。

例えば二乗誤差を用いれば、
$L(f(\mathbf{x}_{q,d}), y_{q, d})=(y_{q,d}-f(\mathbf{x}_{q,d})^2)$
を最小化する問題となります。

…と、ここまで話すとお気付きの方もいると思いますが、ようするにただの回帰問題、もしくは多クラスの分類問題を解いているだけです。

「だったらランク学習なんて特別なものを考えなくても、分類問題とか回帰問題として解けばいいじゃん！」と思われるかもしれません。
しかし、文書のランキングを正しく当てるモデルさえあれば良くて、文書の関連度を正しく当てるモデルまで必要としていないことに注意が必要です。

例えば、文書の関連度が $(4, 3, 2, 1)$ として与えられているとき、モデルの出力したスコアは $(0.5, 0.3, 0.1, 0.01)$ だったとします。

f:id:sz_dr:20181204002443p:plain:w400

もし単純に二乗誤差を考えると大きい損失が出てきますが、今回出力したスコアでも検索結果ランキングとしては正しい（スコアの順に文書をランキングすれば、関連度の順に並ぶ）ので、ランキングという観点から考えると損失は0であるべきです。

ペアワイズ（pairwise）

ポイントワイズでは1つのサンプルから損失を定義しました。
ここで、2つの文書ペアを正しく順序付けできれば、検索結果は正しいランキングになることを考えると、2つのサンプルペアから損失を定義するという発想が生まれます。

そこで、ペアワイズの損失関数は
$L_{0}=\sum_{q}\sum_{i,j:y_{q,i}>y_{q,j}}^{m_q}L(f(\mathbf{x}_{q,i}), f(\mathbf{x}_{q,j}))$
という形で定義されます。

例えばスコアの差を指数関数に通した誤差を用いれば、
$L(f(\mathbf{x}_{q,i}), f(\mathbf{x}_{q,j}))=\exp(f(\mathbf{x}_{q,j}) - f(\mathbf{x}_{q,i}))$
を最小化する問題となります。

…数式では上のように表されるのですが、簡単な例を紹介します。
2つの文書iとjがあって、iはjよりも良い（関連度が高い）とします。
ここで、ランキングモデルはそれぞれの文書にスコアを1, 3とつけてしまったとします。スコアの大小が関連度と入れ替わっているので、この文書ペアについては順序付けを間違っています。

f:id:sz_dr:20181204004323p:plain:w400

この状況で、上で紹介した指数関数を用いた損失関数を計算すると、 $7.4$ という損失が計算されます。
損失さえ計算できれば、あとはそれを最小化していけば、良いランキングモデルが得られるはずです。

リストワイズ (listwise)

ランク学習（Learning to Rank） Advent Calendar 2018 - Adventarでそのうち紹介しますが、分類問題におけるROC-AUCやf値、回帰問題における二乗誤差のように、ランキング問題においてもいくつかの評価指標が存在します。
ランキング問題の評価指標は、ランキングという問題の性質上、検索結果のリスト全体として良い並び順になっているかどうかを指標として計算します。

「ランキング問題の評価指標が与えられているなら、直接それを最適化すればいいじゃん！」というのがリストワイズの発想です。
評価指標は複数のサンプルから計算されることを考えると、リストワイズの損失関数は
$L_{0}=\sum_{q}L( (f(\mathbf{x}_{q,1}),y_{q,1}), \dots, (f(\mathbf{x}_{q,m_q}),y_{q,m_q}))$
という形で定義されます。

例えばランキング問題の評価指標としてNDCGという値がよく用いられるのですが、NDCGを直接最適化することが考えられます。*2

まとめ

この記事ではランク学習における学習データの形式、特徴量、3つの損失関数のタイプを紹介しました。次の記事では、とりあえずランク学習を動かしてみようという話を紹介します。

参考

"Introduction to Algorithmic Marketing: Artificial Intelligence for Marketing Operations"
DSIRNLP#1 ランキング学習ことはじめ

*1:ランク学習の特徴量として加えるより、ランキングした後にユーザーの位置情報と遠いレストランは除去するみたいなヒューリスティックスの方が良いかもしれませんが。

*2:実際には、NDCGを直接最適化するのは難しいので、緩和した問題を解くアルゴリズムが提案されています。