Information Retrieval and Web Search まとめ(20): ランク学習

前回は Word2vec, BERT などの単語埋め込み手法と、それらの情報検索への応用について説明した。今回は、ランク学習について紹介する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の20日目の記事です。

adventar.org

情報検索のための機械学習

• これまでに検索における文書のランキング手法をいくつか見てきた
  • コサイン類似度、BM25...
• また、教師ありの機械学習を使った文書分類（クラス分類）の方法も見てきた
  • ロッキオの方法、kNN、決定木...
• 文書のランク付けにも機械学習を使えないか？
  • "machine-learned releance", "learning to rank" として知られている

歴史

• 検索ランキングのための機械学習はアクティブに研究されてきた
  • また、この10年で主要な検索エンジンにデプロイされている
• 過去の研究
  • Wong, S.K. et al. 1988. Linear structure in information retrieval. SIGIR 1988.
  • Fuhr, N. 1992. Probabilistic methods in information retrieval. Computer Journal.
  • Gey, F. C. 1994. Inferring probability of relevance using the method of logistic regression. SIGIR 1994.
  • Herbrich, R. et al. 2000. Large Margin Rank Boundaries for Ordinal Regression. Advances in Large Margin Classifiers.
• 初期の研究はそれほどうまくいっていなかった
  • 訓練データが少なかった
    • 特に実世界のデータ
    • クエリログ、適合性判定のデータを集めるのは大変
  • 機械学習手法もまだ発展していなかった
  • 情報検索の問題への適用が不十分だった
  • 特徴量が十分ではなかった

機械学習の必要性

• 現代的な（Web の）システムは大量の特徴量を扱う
  • ターム頻度などの古典的な特徴量だけではなく、ページ中の画像の数、リンクの数、PageRank、URL、更新日時、ページの表示速度...
• Google は 2008 年には 200 以上の特徴量（シグナル）を使っており、今日では 500 以上になっているだろう

ランク学習

• クラス分類はアドホック検索への適切なアプローチではない
  • クラス分類 (classification)：順序がないクラスへのマッピングを行う
  • 回帰 (regression)：実数へのマッピングを行う
  • 順序付き回帰 (ordinal regression)、あるいはランキング (ranking)：順序付きのクラスへのマッピングを行う
• ランキング問題では、文書が他の文書に対してよいかどうかを議論する
  • よさの絶対的な尺度は必要ない
• ランク学習 (learning to rank)
  • 以下のような適合性のカテゴリの集合 C が存在すると仮定する
    • C のすべてのカテゴリ ci$c_i$ には全順序がついている (totally ordered)
      • c1>c2>...>cJ$c_1>c_2>...>c_J$
    • （これは順序付き回帰の問題設定と同じ）
  • 以下のような文書とクエリのペア (d, q) からなる訓練データを仮定する
    • (d, q) は特徴量ベクトル xi$x_i$ で表され、それに適合ランキング ci$c_i$ がついている

検索ランキングのためのアルゴリズム

• SVM (Vapnik 1995) のランキングへの適用：Ranking SVM (Joachims 2002)
• ニューラルネット：RankNet (Burges et al. 2006)
• Tree Ensemble
  • ランダムフォレスト (Breiman and Schapire 2001)
  • Boosted Decision Tree
    • Multiple Additive Regression Trees (Friedman, 1999)
    • Gradient-boosted decision trees: LambdaMART (Burges, 2010)
    • AltaVista, Yahoo!, Bing, Yandex などの検索エンジンで採用事例あり
  • 2010 年の Yahoo! Learning to Rank Challenge ではすべてのトップチームが Tree Ensemle の手法の組み合わせを使った

Yahoo! Learning to Rank Challenge

• [Chapelle and Chang, 2011]
• 以下のような Yahoo! Webscope のデータセットを使って行われた
  • クエリ数：36,251
  • 文書数：883k
  • 特徴量:700種類
  • ランキング：5段階
• 優勝したモデル (Burges et al. 2011) は 12 のモデルの線形結合だった：
  • 8 つの Tree Ensemble (LambdaMART)
  • 2 つの LambdaRank ニューラルネットワーク
  • 2 つのロジステック回帰

回帰木

• 回帰木 (regression tree) は、実数を予測できる決定木
• 葉ノードには、その葉ノードに含まれるすべてのサンプルの平均値 (mean) を保持する
  • γk=f(xi)=xi¯¯¯¯¯${\gamma }_k=f(x_i)=\overline{x_i}$
• 分割規準：標準偏差 (standard deviation; SD) の最小化
  • 値の分散（標準偏差 SD）を最小化するように分割 A$A$ を選択する
  • 標準偏差、サンプル数、もしくは木の深さのいずれかが閾値を下回ったら分割を止める
• 学習時には、分割する変数 x1$x_1$ と、その変数上での分割点 v1$v_1$ を探索する
  • それらは予測誤差 ∑i(yi−f(xi))2${\displaystyle \sum _i{(y_i-f(x_i))}^2}$ を最小化するように選ぶ

回帰木の分割の例(1)。予測誤差を最小化する分割を選択

回帰木の分割の例(2)。予測誤差が0になるまで分割を進めた

勾配ブースティング

ブースティングのモチベーション

• Q:「独立な弱い (weak) 分類器を組み合わせて、高い精度の分類器を構築できるか？」
• 古典的なアプローチ: AdaBoost
• すべての木の重み付きの投票で分類する

ブースティングによる関数の推定

• ほしいもの：損失関数 L(y,F(x))$L(y,F(x))$ の期待値を最小化する、以下のような関数 F∗(x)$F^{\ast }(x)$

F∗(x)=argminF(x)Ey,xL(y,F(x))$F^{\ast }(x)={\text{argmin}}_{F(x)}{\mathbb{E}}_{y,x}L(y,F(x))$

• ブースティングでは、 F∗(x)$F^{\ast }(x)$ を以下のような形で近似する
  • h(x;a)$h(x;a)$ は a=a1,a2,...,an$a=a_1,a_2,...,a_n$ でパラメータ化された関数
  • β$\beta$ は重み係数

F(x)=∑m=1Mβmh(x;am)$F(x)={\displaystyle \sum _{m=1}^M{\beta }_{m}h(x;a_m)}$

• 関数のパラメータはイテレーションにより訓練データにフィットさせる

勾配ブースティングの学習

• 勾配ブースティング (gradient boosting) は、任意の微分可能な損失関数に対して関数 F(x)$F(x)$ を推定できる
• 関数 h(x;a)$h(x;a)$ を最小二乗法でフィッティングする

am=argmina∑i[yim~−h(xi,a)]2$a_m={\text{argmin}}_a\sum _i[\widetilde{y_{im}}-h(x_i,a){]}^2$

• ただし yim~$\widetilde{y_{im}}$ は「疑似残差 (pseudo-residual)」であり

yim~=−[∂L(yi,F(xi))∂F(xi)]F(x)=Fm−1(x)$\widetilde{y_{im}}=-{\left[{\displaystyle \frac{\mathrm{\partial }L(y_i,F(x_i))}{\mathrm{\partial }F(x_i)}}\right]}_{F(x)=F_{m-1}(x)}$

• 勾配ブースティングは、どんな損失関数であっても最小二乗法に単純化する
  • ニュートン法などで逐次的にモデルを改善できる

Gradient Boosted Regression Tree (GBRT)

• Gradient Boosted Regression Tree (GBRT) は、この勾配ブースティングのアプローチを回帰木 (regression tree) に適用する
  • それぞれの回帰木は通常 1-8 の分割しか持たない
• GBRT の学習
  • 最初に、すべての xi$x_i$ に対して定数をとる、最もシンプルな予測器を学習する（[tex: F_0(x)）
    • 訓練データの誤差を最小化する定数
  • 木のルートノードの値 γkm${\gamma }_{km}$ を探索する
  • 最小二乗法によりルートノードを分割する
  • さらに誤差を最小化する木を追加する

MART

• Multiple Additive Regression Trees (MART) [Friedman 1999]

MART の学習アルゴリズム

RankNet

• RankNet [Burges et al. 2005] はニューラルネットによる ranker
• モデルパラメータ w に対して微分可能な関数 f(x;w)$f(x;w)$ をスコア関数とする
  • f(xi;w)=si$f(x_i;w)=s_i$ が xi$x_i$ のスコア
• クエリ q に対して、各文書の組 (di,dj)$(d_i,d_j)$ に対するランキングのクラスの確率 Pij$P_{ij}$ を学習する
  • Pij$P_{ij}$ は、文書 di$d_i$ が dj$d_j$ よりランキングが上である確率
  • σ$\sigma$ はシグモイド関数の傾きを決めるパラメータ

Pij=P(di≻dj)=11+e−σ(si−sj)$P_{ij}=P(d_i\succ d_j)={\displaystyle \frac{1}{1+e^{-\sigma (s_i-s_j)}}}$

• 損失関数 C はクロスエントロピー損失
  • Pij$P_{ij}$ はモデルの確率
  • Pij¯¯¯¯¯¯¯$\overline{P_{i}j}$ は実際の確率（各カテゴリに対して0/1で与えられる適合性の判定）

C==−Pij¯¯¯¯¯¯logPij−(1−Pij¯¯¯¯¯¯¯)log(1−Pij)12(1−Sij)σ(si−sj)+log(1+e−σ(si−sj))$\begin{array}{rcl}C& =& -\overline{P_{ij}}\log P_{ij}-(1-\overline{P_{i}j})\log (1-P_{i}j)\\ & =& \frac{1}{2}(1-S_{ij})\sigma (s_i-s_j)+\log (1+e^{-\sigma (s_i-s_j)})\end{array}$

• ただし、Sij∈0,+1,−1$S_{ij}\in 0,+1,-1$
  • di$d_i$ が dj$d_j$ よりも適合しているとき Sij=1$S_{ij}=1$
  • dj$d_j$ が di$d_i$ よりも適合しているとき Sij=−1$S_{ij}=-1$
  • di$d_i$ と dj$d_j$ が同じラベルのとき Sij=0$S_{ij}=0$

RankNet の Lambda

∂C∂si=σ(12(1−Sij)−11+eσ(si−sj))=−∂C∂sj${\displaystyle \frac{\mathrm{\partial }C}{\mathrm{\partial }{s}_i}}=\sigma ({\displaystyle \frac{1}{2}}(1-S_{ij})-{\displaystyle \frac{1}{1+e^{\sigma (s_i-s_j)}}})=-{\displaystyle \frac{\mathrm{\partial }C}{\mathrm{\partial }{s}_j}}$

• これを使って損失関数の wk$w_k$ に対する微分は以下のようにできる

∂C∂wk===∂C∂si∂si∂wk+∂C∂sj∂sj∂wkσ(12(1−Sij)−11+eσ(si−sj))(∂si∂wk−∂sj∂wk)λij(∂si∂wk−∂sj∂wk)$\begin{array}{rcl}{\displaystyle \frac{\mathrm{\partial }C}{\mathrm{\partial }{w}_k}}& =& {\displaystyle \frac{\mathrm{\partial }C}{\mathrm{\partial }{s}_i}}{\displaystyle \frac{\mathrm{\partial }{s}_i}{\mathrm{\partial }{w}_k}}+{\displaystyle \frac{\mathrm{\partial }C}{\mathrm{\partial }{s}_j}}{\displaystyle \frac{\mathrm{\partial }{s}_j}{\mathrm{\partial }{w}_k}}\\ & =& \sigma ({\displaystyle \frac{1}{2}}(1-S_{ij})-{\displaystyle \frac{1}{1+e^{\sigma (s_i-s_j)}}})({\displaystyle \frac{\mathrm{\partial }{s}_i}{\mathrm{\partial }{w}_k}}-{\displaystyle \frac{\mathrm{\partial }{s}_j}{\mathrm{\partial }{w}_k}})\\ & =& {\lambda }_{ij}({\displaystyle \frac{\mathrm{\partial }{s}_i}{\mathrm{\partial }{w}_k}}-{\displaystyle \frac{\mathrm{\partial }{s}_j}{\mathrm{\partial }{w}_k}})\end{array}$

• この式を使って重み wk$w_k$ を更新できる
• λij${\lambda }_{ij}$ は、文書 di$d_i$ と dj$d_j$ の組に対しての、変更したいスコアを表している
• クエリ-文書ベクトル xi$x_i$ の λij${\lambda }_{ij}$ と
  • λji${\lambda }_{ji}$ の総和 λi${\lambda }_i$ を定義する

λi=∑j:{i,j}∈Iλij−∑k:{k,i}∈Iλki${\lambda }_i={\displaystyle \sum _{j:\{i,j\}\in I}{\lambda }_{ij}-{\displaystyle \sum _{k:\{k,i\}\in I}{\lambda }_{ki}}}$

• この λi${\lambda }_i$ は、クエリ-文書ベクトル xi$x_i$ のペアワイズ損失の勾配を表している
  • (a) は最適なランキング
  • (b) は 10 のペアワイズ誤差をもつランキング
  • (c) は 8 のペアワイズ誤差をもつ
  • 青の矢印は最後の文書の勾配 λi${\lambda }_i$

ランキングの損失とそれらの λi の例(1)

• 青の矢印でペアワイズ誤差は減り、2値の適合性評価指標は改善する
• しかし、NDCG や ERR のような、上位により大きい重みをつける指標では、以下の赤の矢印のような勾配のほうが望ましい

ランキングの損失とそれらの λi の例(2)

LambdaRank

• LambdaRank [Burges et al. 2006]
• RankNet のようなペアワイズ誤差ではなく、NDCG の効果を入れる
• アイデア： lambda$lambda$ を |ΔZ|$|\mathrm{\Delta }Z|$ 倍する
  • |ΔZ|$|\mathrm{\Delta }Z|$ は、文書 di$d_i$ と dj$d_j$ を交換したときの差分
• |ΔZ|$|\mathrm{\Delta }Z|$ として |ΔNDCG|$|\mathrm{\Delta }NDCG|$ （NDCG の変化）を使って λ$\lambda$ を以下のようにする

λij=∂C(si−sj)∂si=−σ1+eσ(si−sj)|ΔNDCG|${\lambda }_{ij}={\displaystyle \frac{\mathrm{\partial }C(s_i-s_j)}{\mathrm{\partial }{s}_i}}={\displaystyle \frac{-\sigma }{1+e^{\sigma (s_i-s_j)}}}|\mathrm{\Delta }NDCG|$

• Burges et al. は、この変更によって NDCG に対して十分に最適化できることを示した

LambdaMART

• LambdaRank は勾配をモデル化している
• MART は勾配（勾配ブースティング）によって学習できる
• この2つを組み合わせたのが LambdaMART [Burges 2010]
  • MART に LambdaRank の勾配を入れた

([Burges 2010] Algorithm: LambdaMART) LambdaMART のアルゴリズム

• 前述の通り、Yahoo! Learning to Rank Challenge で LambdaMART （と他のモデルとの線形結合）を使ったチームが優勝 [Burges et al. 2011]
• 結合されたモデルと、それぞれの単体でのスコアは以下の通り

([Burges et al. 2011 Table 2]) 使用されたモデルと単体でのスコア

• 多くのモデルを組み合わせなくても十分に高い性能を示す

([Burges et al. 2011 Table 3]) モデルの組み合わせとそれぞれのスコア

• 他のチームも僅差
  • ペアワイズの Logistic Rank もいい結果を残している

([Burges et al. 2011 Table 4]) Yahoo! Learning to Rank Challenge の最終スコア。1位のチームが LambdaMART

• だが、決定木ベースの手法は検索エンジンの会社では必要不可欠になっているようだ
  • ビッグデータに対しては少し優位なのかもしれない

講義資料

• Learning to Rank (with GBDTs)

参考資料

• IIR sections 6.1.2-6.1.3
• IIR section 15.4
• Discriminative models for information retrieval (Nallapati 2004)
• Adapting ranking SVM to document retrieval (Cao et al. 2006)
• A support vector method for optimizing average precision (Yue et al. 2007)
• LETOR benchmark datasets
• C. J. C. Burges. From RankNet to LambdaRank to LambdaMART: An Overview. Microsoft TR 2010.
• O. Chapelle and Y. Chang. Yahoo! Learning to Rank Challenge Overview. JMLR Proceedings 2011.
• Why is machine learning used heavily for Google's ad ranking and less for their search ranking? What led to this difference? - Quora
• Raw example of xgboost for ranking with LambdaMART
  • xgboost/demo/rank at master · dmlc/xgboost
• Statistical Consulting: Multiple Additive Regression Trees (MART)