トップ > 機械学習 > SIGIR Learning to Rank sessionから見るランク学習研究の動向（１）

SIGIR Learning to Rank sessionから見るランク学習研究の動向（１）

機械学習

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

この記事は何？

情報検索分野のトップカンファレンスであるSIGIR (Special Interest Group on Information Retrieval) では、毎回ランク学習に関する研究を集めたセッションが開催されています。

SIGIR 2007からSIGIR 2018までのランク学習セッションで発表された論文をざっくり見ていって、ランク学習研究がどのように発展してきたのかを紹介します。

この記事では、SIGIR 2007・2008・2009について見ていこうと思います。

注意→読んでもよく分からなかった論文がいくつかあります。ごめんなさい；；


SIGIR 2007

SIGIR'07 - Conference Schedule

SIGIR 2007のランク学習セッションは、MAP・NDCGといった検索精度評価指標を直接最適化するような手法が多く出ているように見えます。
個人的には、ランク学習手法乱立期…といったところでしょうか。

以下のAcceptされた論文とざっくりした紹介です。
（タイトルクリックで論文ページに飛べます）

A Support Vector Method for Optimizing Average Precision

  • 検索評価指標ではMAPがよく使われる
  • MAPを最適化するSVM mapを提案
  • 既存のROC最適化SVMや普通のSVMよりも高い精度

Ranking with Multiple Hyperplanes

  • RankSVMはよく使われるが、シンプル過ぎて"definitely relevant" > "partially relevant" > "irrelevant"のような関係をうまく学習できない
  • ラベルがK段階関連度で表されるとして、K\times (K - 1) / 2の各組み合わせでRankSVMを学習し、複数のランキングモデルをアンサンブルする手法を提案
  • 既存のRankSVMより高い精度

A Regression Framework for Learning Ranking Functions Using Relative Relevance Judgments

FRank: A Ranking Method with Fidelity Loss

  • RankNetではクロスエントロピー損失が用いられているが、「P(d_i \succ d_j)=0.5かつ出力スコアo_{ij}=0の時でも非ゼロの損失を与える」「損失の上限が無い」という問題がある
  • これらの問題を解決したFidelity Lossを提案
  • 既存のRankSVMやRankNetよりも高い精度

AdaRank: A Boosting Algorithm for Information Retrieval

  • 検索評価指標ではMAPやNDCGがよく使われる
  • Boostingを用いてMAPやNDCGを直接最適化するAdaRankを提案
  • 既存のRankSVMやRankBoostよりも高い精度

A Combined Component Approach for Finding Collection-Adapted Ranking Functions based on Genetic Programming

（論文見つかりませんでした）

Feature Selection for Ranking

  • ランク学習における特徴選択問題
  • 「ある特徴でソートした際に得られるNDCGやMAP」「ある特徴と検索ランキングの順位相関」をfeature importanceと定義
  • 適切に特徴選択することでランク学習の精度向上


SIGIR 2008

http://www.sigir2008.org/program_details.html#s5:Learning-to-rank 1
http://www.sigir2008.org/program_details.html#s11:Learning-to-rank 2

この年のTutorial Sessionでは、"Learning to Rank for Information Retrieval"というまさにうってつけのtutorialがありました。
SIGIR 2008で使われていたスライドは見つけられなかったのですが、WWW 2009でも同じようなtutorialをやっていたようで、そのスライドを見つけることができました。

SIGIR 2008のランク学習セッションは、半教師付きや複数ランキングモデルの導入など、なんとかして精度を上げていきたいという気持ちに溢れた論文が出ています。
情報検索の多くの問題では、ラベル無しデータが大量にあるし、ラベリング大変なので、半教師付き学習のモチベーションは個人的にはよく分かります。

ところで、当時は半教師付き学習が機械学習分野で流行ってた。。。んですかね？

以下のAcceptされた論文とざっくりした紹介です。
（タイトルクリックで論文ページに飛べます）

A Boosting Algorithm for Learning Bipartite Ranking Functions with Partially Labeled Data

  • 半教師付き+ランク学習問題
  • ラベルの付いてないデータにはNearest Neighborで擬似ラベリング
  • ラベルの付いてないデータも学習に用いることで精度向上

Directly Optimizing Evaluation Measures in Learning to Rank

  • MAPやNDCGを最適化する手法としてSVM-mapとAdaRankが提案されている
  • SVM-mapとAdaRankの性質を整理・一般化
  • 一般化に合わせて、新たにPermuRankという手法を提案

Query Dependent Ranking Using K-Nearest Neighbor

  • 全ての検索クエリで同じランキングモデルを使うのではなく、検索クエリに合わせて複数のランキングモデルを使いたい
  • 入力された検索クエリに対して、簡単なモデル（BM25）でヒットした文書群からクエリ特徴を作り、K-NNでクエリ・ランキングモデルを選択
  • 複数のランキングモデルを扱うことで精度向上

Learning to Rank with Partially-Labeled Data

  • 半教師付き+ランク学習問題
  • トランスダクティブ学習の枠組みに落として、KernelPCAを用いてテストデータの情報を学習に組み込む
  • RankBoostと組み合わせて精度向上

Learning to Rank with SoftRank and Gaussian Processes

（論文がダウンロードできませんでした）

Learning to Rank at Query-Time using Association Rules

  • ルールベースな手法（Association Rules）でランキング問題を解く
  • （いまいち何やってるのかよく分からないし、なんで上手くいってるのかも分からない。。。）

Learning to Rank with Ties

（論文がダウンロードできませんでした）


SIGIR 2009

Schedule of paper presentations | SIGIR'09

SIGIR 2009もSIGIR 2008と同じように、機械学習分野の話題（スパース学習や能動学習など）を輸入してランク学習に応用している例を見かけます。
個人的には、Learning in a Pairwise Term-Term Proximity Framework for Information Retrievalが、ランク学習における特徴量を考える上で、現在でも参考になる論文だと思っています。

以下のAcceptされた論文とざっくりした紹介です。
（タイトルクリックで論文ページに飛べます）

Learning to Rank for Quantity Consensus Queries

  • 数量表現を問うクエリ（e.g. "driving time from Paris to Nice"）に関する検索問題
  • ガッツリ自然言語処理をするのではなく、ランク学習で応答を返す

Learning in a Pairwise Term-Term Proximity Framework for Information Retrieval

  • クエリに含まれる単語が、文書のタイトルor文書中でどの程度隣接して出現するかを測る指標を提案
  • BM25などのスコアリング指標と隣接指標を組み合わせることで、検索精度向上

Robust Sparse Rank Learning for Non-Smooth Ranking Measures

  • スパース学習（特徴量削減）とNDCG・MAP最適化を組み合わせた
  • 精度をそこまで落とすことなく、ランキングモデルの特徴量を効率的に削減できている

On the Local Optimality of LambdaRank

（いまいち何やってるのかよく分からず。。。LambdaRankはすごいよってことを言っている？）

Document Selection Methodologies for Efficient and Effective Learning-to-Rank

  • ランク学習における学習データ選択問題
  • ランダム選択や能動学習に基づく手法+様々なランク学習手法を網羅的に調査

An Improved Markov Random Field Model for Supporting Verbose Queries

（いまいち何やってるのかよく分からず。。。マルコフ確率場をうにゃうにゃしてる）


まとめ

この記事ではSIGIR 2007・2008・2009のランク学習セッションの論文を見ていきました。
さすがに10年前なので今では見ないようなランク学習手法や問題設定がありますが、この頃には既にNDCG・MAP最適化手法がガンガン研究されているのは非常に面白かったです。