Learning to Rank: From Pairwise Approach to Listwise Approach (ListNet), Cao+, ICML'2007

[AkihikoWatanabe]

http://www.machinelearning.org/proceedings/icml2007/papers/139.pdf

[AkihikoWatanabe]

解説スライド：http://www.nactem.ac.uk/tsujii/T-FaNT2/T-FaNT.files/Slides/liu.pdf 解説ブログ：https://qiita.com/koreyou/items/a69750696fd0b9d88608

[AkihikoWatanabe]

従来行われてきたLearning to Rankはpairwiseな手法が主流であったが、pairwiseな手法は2つのインスタンス間の順序が正しく識別されるように学習されているだけであった。 pairwiseなアプローチには以下の問題点があった：

• インスタンスのペアのclassification errorを最小化しているだけで、インスタンスのランキングのerrorを最小化しているわけではない。
• インスタンスペアが i.i.d な分布から生成されるという制約は強すぎる制約
• queryごとに生成されるインスタンスペアは大きく異なるので、インスタンスペアよりもクエリに対してバイアスのかかった学習のされ方がされてしまう

これらを解決するために、listwiseなアプローチを提案。 listwiseなアプローチを用いると、インスタンスのペアの順序を最適化するのではなく、ランキング全体を最適化できる。 listwiseなアプローチを用いるために、Permutation Probabilityに基づくloss functionを提案。loss functionは、2つのインスタンスのスコアのリストが与えられたとき、Permutation Probability Distributionを計算し、これらを用いてcross-entropy lossを計算するようなもの。 また、Permutation Probabilityを計算するのは計算量が多すぎるので、top-k probabilityを提案。 top-k probabilityはPermutation Probabilityの計算を行う際のインスタンスをtop-kに限定するもの。 論文中ではk=1を採用しており、k=1はsoftmaxと一致する。 パラメータを学習する際は、Gradient Descentを用いる。

[AkihikoWatanabe]

k=1の設定で計算するのが普通なようなので、普通にoutputがsoftmaxでlossがsoftmax cross-entropyなモデルとほぼ等価なのでは。