Edited at

Learning to rank (LTR) とは何か

ElasticsearchやSolrで検索システムを構築する際に、ドキュメント-クエリペアの特徴量とクリックデータ等のラベルを用いて機械学習を適用し、Top-kに対して再ランクすることを「LTR」または「順序学習」と呼ばれています。ここでは、LTRについての全体像を説明します。


検索のフロー

まず、ユーザがクエリを投げ、通常の情報検索を行います。「通常の」とは、例えば形態素解析やngramによる検索のことです。

次に、上位k件に対してLTRの機械学習モデルでスコアリングをします。特徴量は、「クエリ」と「ドキュメント」のペアから抽出できるものです。例えば、クエリとドキュメントのタイトルのベクトル表現のコサイン類似度とか、ページランク、TF, IDF, あるクエリで出てきた各々のドキュメントのクリック回数、など様々です。

最後に、re-rankされた結果が取得されます。


LTRの特徴量設計

MicrosoftからLTR用のデータセットが公開されています。

https://www.microsoft.com/en-us/research/project/mslr/

上記ページの"Feature List"では、136の特徴量があります。

しかし、これらの特徴量だけにこだわる必要はありません。例えば、SpamRankやTrustRankといったリンクベース特徴量を追加しても良いですし、URL内の/の数(深さ)みたいな独自の特徴量を付け加えても良いです。

このあたりは、データサイエンス的に特徴量設計を行うことができるフェーズです。

重要なのは、「クエリ」と「ドキュメント」のペアから取得できる特徴量を定義することです。特徴量には「動的なもの」と「静的なもの」がありますが、動的なものはクエリに依存します。静的なものはドキュメントのみに依存します。また、システムによってはユーザ属性を付け加えたいと思うかもしれませんが、その場合はユーザごとにLTRを訓練することもできます。


機械学習アルゴリズム

RankSVMが一番有名だと思いますが、LTRでは様々なアルゴリズムが開発されています。

アルゴリズムの分類としては3種類あります。

pointwise: 各クエリ-ドキュメントペアには数値スコアが付与されます。単一の値をラベルとして持つ回帰または分類の問題になります。

pairwise: ドキュメントxとyに対し、どちらが良いドキュメントなのかを学習します。

listwise: クエリに対し、最適順序のリストを学習します。

https://en.wikipedia.org/wiki/Learning_to_rank

クリックデータを用いてラベルを定義し、これらのアルゴリズムを使うことができます。しかし、質のよいラベルを定義しようと思った場合は手作業のアノテーションが必要になるかもしれません。


クリックデータを用いたLTRの社会心理学的問題点

検索エンジンでLTRを用いる場合、社会心理学的な問題が発生します。

(1) position bias

人間は、最初と最後だけを見て、中央を無視することがあります。

(2) presentation bias

表示された結果以外のフィードバックが受け取れません。

(3) trust bias

ユーザがTopに表示されたものを無批判に信用しがちです。

これらのバイアスは選択バイアスの一種ですが、例えば「見られやすいものはより見られるようになる」という現象が起きてしまいます。この現象が起きると、文書全体に対して正しい評価を与えることができません。


具体的な実装

Solr: https://lucene.apache.org/solr/guide/6_6/learning-to-rank.html

Elasticsearch LTR plugin: https://github.com/o19s/elasticsearch-learning-to-rank


ElasticsearchのLTRプラグインのデモ

デモを見れば、おおよその使い方はわかります。

prebuiltバージョンをダウンロードし、以下コマンドを実行します:

./bin/elasticsearch-plugin install http://es-learn-to-rank.labs.o19s.com/ltr-1.0.0-es6.1.2.zip

これでインストールは完了です。

まず、demoディレクトリへ移動し、必要ライブラリとデモデータをダウンロードします:

python prepare.py

データをElasticsearchへインデクシングします:

python index_ml_tmdb.py

LTRを訓練します。この訓練ではRankLibが使われます:

python train.py

訓練されたLTRでデモデータを検索します。ここでは、映画の「ランボー」をサーチしてみます:

python search.py Rambo

特徴量設計したい場合は、以下の手順をとります:


  1. 特徴量または特徴量に関係するフィールドを当該ドキュメントと一緒にElasticsearchへインデクシング。

  2. クエリ形式で特徴量を定義。

  3. train.pyで訓練。

例えば、特徴量を定義するjsonファイルを以下のように定義します。



{
"query": {
"match_explorer": {
"type": "max_raw_df",
"query": {
"match": {
"title": "{{keywords}}"
}
}
}
}
}

このような特徴量のリストを、1.json, 2.jsonという形式でdemoディレクトリへ保存していきます。train.pyを実行すれば、定義されているjsonリストが特徴量として使われます。

特徴量設計の詳細は以下のドキュメントを見てください:

https://elasticsearch-learning-to-rank.readthedocs.io/en/latest/feature-engineering.html


参考

[1] https://en.wikipedia.org/wiki/Learning_to_rank

[2] https://www.microsoft.com/en-us/research/project/mslr/

[3] https://medium.com/@nikhilbd/80a8fe8fadfd

[4] https://ai.google/research/pubs/pub45286


RankLib

RankLibとは、ランキングアルゴリズムを複数実装したライブラリです。

https://sourceforge.net/p/lemur/wiki/RankLib/

xml形式でモデルが出力されるので、このxmlをElasticsearchのLTRプラグインに対して使うことが可能です。train.py内で使われています。