RankSVMの気持ちをざっくりと理解してみる

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

この記事は何？

ランク学習の手法は数え切れないくらい提案されていますが、2018年現在のランク学習研究でもbaselineとして使われている手法として、RankSVMがあります。
RankSVMはSVMをランク学習に応用した手法であり、ペアワイズ手法の1つとなります。

次の記事で取り上げますが、RankSVMはお手軽に実行できるツールがあるため、とりあえずランク学習をやってみたいというケースでもオススメです。

この記事では、RankSVMの気持ちをざっくりと紹介します。

SVMの復習

RankSVMを理解する前に、まずはSVMの復習をします。

SVMでは、正例と負例がどのくらい離れているか=マージンがなるべく大きくなるような分類境界を求めます。

PRMLで使われている図が分かりやすいと思います。
f:id:sz_dr:20181210224554p:plain:w400
"Pattern Recognition and Machine Learning", C. Bishop, Fig 7.1a

後でRankSVMの目的関数を紹介しますが、比較のために線形SVMの目的関数を取り上げます。

$\begin{align} \min_{\mathbf{w}, b, \mathbf{\xi}}\frac{1}{2}\|w\|^2+C\sum_{i\in[n]}\xi_i \\ \mathrm{s.t.}\ y_i(\mathbf{w}^T\mathbf{x}_i + b)\ge 1-\xi_i,\ i \in [n] \\ \xi_i \ge 0,i \in [n] \end{align}$

上式は様々な文献で紹介されているので、導出などはそちらを参考にしてください。
私は、機械学習プロフェッショナルシリーズから出ているサポートベクトルマシン本が分かりやすくて好きです。
www.kspub.co.jp

RankSVMを絵で理解する

SVMは正例と負例のマージンを最大化するように学習しました。

RankSVMでも同じようにマージンの考え方が存在します。
"Ranking Support Vector Machine with Kernel Approximation", K. Chen, 2017の図が非常に分かりやすいです。

f:id:sz_dr:20181210225535p:plain
"Ranking Support Vector Machine with Kernel Approximation", K. Chen, 2017. Figure 1.

上の図をじっくり見ていきます。

まず、データ点は $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3, \mathbf{x}_4$ の4つがあり、それぞれ2次元の特徴量で表されています。

ランク学習で用いられるデータ点にはそれぞれ関連度を表すラベルが付与されており、よく「Perfect(4)・Excellent(3)・Good(2)・Fair(1)・Bad(0)」などの5段階評価ラベルが使われます。
上の図では、関連度ラベルに従って、 $\mathbf{x}_4 \succ \mathbf{x}_3 \succ \mathbf{x}_2 \succ \mathbf{x}_1$ という順序関係が与えられています。

さて、RankSVMにおけるマージン最大化の考え方ですが、「全ての順序ペアに関するランキングスコアの差のうち、最小のランキングスコアの差（マージン）を最大化する」というアイデアでパラメータを学習します。

…何言ってんのって感じだと思うので、再度上の図に戻ります。
上の図では2つのパラメータ（重みベクトル） $\mathbf{w}_1, \mathbf{w}_2$ があり、それぞれデータ点の特徴量との内積を取ることでランキングスコアを求めることができます。

$\mathbf{w}_1$ を用いた場合は、全ての順序ペアに関するランキングスコアの差のうち、最小のランキングスコアの差は、 $\mathbf{x}_1$ と $\mathbf{x}_2$ の間で計算される $d_1$ となります。
$\mathbf{w}_2$ を用いた場合は、全ての順序ペアに関するランキングスコアの差のうち、最小のランキングスコアの差は、 $\mathbf{x}_3$ と $\mathbf{x}_4$ の間で計算される $d_2$ となります。

ここで、 $d_1$ と $d_2$ の大きさを比較すると、 $d_1$ の方が大きいので、パラメータ $\mathbf{w}_1$ によるランキングモデルの方がマージンが大きい（汎化性能が優れている）と言えます。

線形RankSVMの目的関数

RankSVMを絵で理解できたところで、線形RankSVMの目的関数を紹介します。
RankSVMの元論文である"Optimizing Search Engines using Clickthrough Data", T. Joachims, 2002.では、以下のように線形RankSVMの目的関数を定義しています。
f:id:sz_dr:20181210231338p:plain:w500

上式ですが、 $n$ 個の検索キーワードに対する検索結果（学習サンプル）のランキングが $r_{1}^{\ast}, \dots, r_{n}^{\ast}$ として与えられています。
それぞれのランキングから関連度に従って得られた文書対 $(d_i, d_j),\ d_i \succ d_j$ から、制約の式が与えられています。