ナード戦隊データマン

データサイエンスを用いて悪と戦うぞ

LTR ( learning to rank, 順序学習 ) とは何か

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

検索のフロー

Untitled drawing.png

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

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

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

LTRの特徴量設計

MicrofostからLTR用のデータセットが公開されています。 https://www.microsoft.com/en-us/research/project/mslr/

Feature List of Microsoft Learning to Rank Datasets
feature id    feature description      stream comments
1    covered query term number      body
2      anchor
3      title
4      url
5      whole document
6    covered query term ratio      body
7      anchor
8      title
9      url
10      whole document
11    stream length      body
12      anchor
13      title
14      url
15      whole document
16    IDF(Inverse document frequency)      body
17      anchor
18      title
19      url
20      whole document
21    sum of term frequency      body
22      anchor
23      title
24      url
25      whole document
26    min of term frequency      body
27      anchor
28      title
29      url
30      whole document
31    max of term frequency      body
32      anchor
33      title
34      url
35      whole document
36    mean of term frequency      body
37      anchor
38      title
39      url
40      whole document
41    variance of term frequency      body
42      anchor
43      title
44      url
45      whole document
46    sum of stream length normalized term frequency      body
47      anchor
48      title
49      url
50      whole document
51    min of stream length normalized term frequency      body
52      anchor
53      title
54      url
55      whole document
56    max of stream length normalized term frequency      body
57      anchor
58      title
59      url
60      whole document
61    mean of stream length normalized term frequency      body
62      anchor
63      title
64      url
65      whole document
66    variance of stream length normalized term frequency      body
67      anchor
68      title
69      url
70      whole document
71    sum of tf*idf      body
72      anchor
73      title
74      url
75      whole document
76    min of tf*idf      body
77      anchor
78      title
79      url
80      whole document
81    max of tf*idf      body
82      anchor
83      title
84      url
85      whole document
86    mean of tf*idf      body
87      anchor
88      title
89      url
90      whole document
91    variance of tf*idf      body
92      anchor
93      title
94      url
95      whole document
96    boolean model      body
97      anchor
98      title
99      url
100      whole document
101    vector space model      body
102      anchor
103      title
104      url
105      whole document
106    BM25      body
107      anchor
108      title
109      url
110      whole document
111    LMIR.ABS      body Language model approach for information retrieval (IR) with absolute discounting smoothing
112      anchor
113      title
114      url
115      whole document
116    LMIR.DIR      body Language model approach for IR with Bayesian smoothing using Dirichlet priors
117      anchor
118      title
119      url
120      whole document
121    LMIR.JM      body Language model approach for IR with Jelinek-Mercer smoothing
122      anchor
123      title
124      url
125      whole document
126    Number of slash in URL
127    Length of URL
128    Inlink number
129    Outlink number
130    PageRank
131    SiteRank Site level PageRank
132    QualityScore The quality score of a web page. The score is outputted by a web page quality classifier.
133    QualityScore2 The quality score of a web page. The score is outputted by a web page quality classifier, which measures the badness of a web page.
134    Query-url click count The click count of a query-url pair at a search engine in a period
135    url click count The click count of a url aggregated from user browsing data in a period
136    url dwell time The average dwell time of a url aggregated from user browsing data in a period

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

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

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

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

機械学習アルゴリズム

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

Year Name Type Notes
1989 OPRF [16] 2 pointwise Polynomial regression (instead of machine learning, this work refers to pattern recognition, but the idea is the same)
1992 SLR [17] 2 pointwise Staged logistic regression
1999 MART (Multiple Additive Regression Trees) 2 pairwise
2000 Ranking SVM (RankSVM) 2 pairwise A more recent exposition is in,[3] which describes an application to ranking using clickthrough logs.
2002 Pranking[18] 1 pointwise Ordinal regression.
2003 RankBoost 2 pairwise
2005 RankNet 2 pairwise
2006 IR-SVM 2 pairwise Ranking SVM with query-level normalization in the loss function.
2006 LambdaRank pairwise/listwise RankNet in which pairwise loss function is multiplied by the change in the IR metric caused by a swap.
2007 AdaRank 3 listwise
2007 FRank 2 pairwise Based on RankNet, uses a different loss function - fidelity loss.
2007 GBRank 2 pairwise
2007 ListNet 3 listwise
2007 McRank 1 pointwise
2007 QBRank 2 pairwise
2007 RankCosine 3 listwise
2007 RankGP[19] 3 listwise
2007 RankRLS 2 pairwise

Regularized least-squares based ranking. The work is extended in [20] to learning to rank from general preference graphs.

2007 SVMmap 3 listwise
2008 LambdaSMART/LambdaMART pairwise/listwise Winning entry in the recent Yahoo Learning to Rank competition used an ensemble of LambdaMART models. Based on MART (1999)[21] “LambdaSMART”, for Lambda-submodel-MART, or LambdaMART for the case with no submodel (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2008-109.pdf).
2008 ListMLE 3 listwise Based on ListNet.
2008 PermuRank 3 listwise
2008 SoftRank 3 listwise
2008 Ranking Refinement[22] 2 pairwise A semi-supervised approach to learning to rank that uses Boosting.
2008 SSRankBoost[23] 2 pairwise An extension of RankBoost to learn with partially labeled data (semi-supervised learning to rank)
2008 SortNet[24] 2 pairwise SortNet, an adaptive ranking algorithm which orders objects using a neural network as a comparator.
2009 MPBoost 2 pairwise Magnitude-preserving variant of RankBoost. The idea is that the more unequal are labels of a pair of documents, the harder should the algorithm try to rank them.
2009 BoltzRank 3 listwise Unlike earlier methods, BoltzRank produces a ranking model that looks during query time not just at a single document, but also at pairs of documents.
2009 BayesRank 3 listwise A method combines Plackett-Luce Model and neural network to minimize the expected Bayes risk, related to NDCG, from the decision-making aspect.
2010 NDCG Boost[25] 3 listwise A boosting approach to optimize NDCG.
2010 GBlend 2 pairwise Extends GBRank to the learning-to-blend problem of jointly solving multiple learning-to-rank problems with some shared features.
2010 IntervalRank 2 pairwise & listwise
2010 CRR 2 pointwise & pairwise Combined Regression and Ranking. Uses stochastic gradient descent to optimize a linear combination of a pointwise quadratic loss and a pairwise hinge loss from Ranking SVM.
2017 ES-Rank listwise Evolutionary Strategy Learning to Rank technique with 7 fitness evaluation metrics

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

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

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

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

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

クリックデータを基にpointwiseやpairwiseを使うのが一般的です。 (listwiseはちょっと難しい)

クリックデータを用いた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

参考

[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