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

検索のフロー

まず、ユーザがクエリを投げ、通常の情報検索を行います。「通常の」とは、例えば形態素解析や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