ランキングSVM

機械学習において、ランキングSVMはサポートベクターマシンアルゴリズムの変形であり、特定のランキング問題を解決するために使用されます（ランキング学習を介して）。ランキングSVMアルゴリズムは、2002年にThorsten Joachimsによって公開されました。^{[1]このアルゴリズムの本来の目的は、}インターネット検索エンジン のパフォーマンスを向上させることでした。しかし、ランキングSVMはRank SIFTなどの他の問題を解決するためにも使用できることがわかりました。^[2]

ランキング SVM アルゴリズムは、ペアワイズ ランキング メソッドを使用して、特定のクエリに対する「関連性」に基づいて結果を適応的に並べ替える学習検索機能です。ランキング SVM 機能は、マッピング機能を使用して、検索クエリと各可能な結果の特徴との一致を記述します。このマッピング機能は、各データ ペア (検索クエリとクリックされた Web ページなど) を特徴空間に投影します。これらの特徴は、対応するクリックスルー データ (特定のクエリに対するページの関連性のプロキシとして機能します) と組み合わされ、ランキング SVM アルゴリズムのトレーニング データとして使用できます。

一般的に、ランキング SVM のトレーニング期間には次の 3 つのステップが含まれます。

1. クエリとクリックされたページ間の類似性を特定の特徴空間にマッピングします。
2. ステップ 1 で取得した任意の 2 つのベクトル間の距離を計算します。
3. これは、標準の SVM 分類に類似した最適化問題を形成し、通常の SVM ソルバーを使用してこの問題を解決します。

が要素を含むデータセットであるとします。はに適用されるランキングメソッドです。の はバイナリマトリックスとして表すことができます。 のランクがのランクよりも高い場合、つまり の場合、このマトリックスの対応する位置は値「1」に設定されます。 それ以外の場合、その位置の要素は値「0」に設定されます。 ${\displaystyle \mathbb {C} }$${\displaystyle N}$${\displaystyle c_{i}}$${\displaystyle r}$${\displaystyle \mathbb {C} }$${\displaystyle r}$${\displaystyle \mathbb {C} }$${\displaystyle N\times N}$${\displaystyle c_{i}}$${\displaystyle c_{j}}$${\displaystyle r\ c_{i}$

Kendall の Tau はKendall の Tau 順位相関係数とも呼ばれ、同じデータ セットの 2 つのランキング方法を比較するためによく使用されます。

と がデータ セット に適用された 2 つのランキング メソッドであるとすると、との間の Kendall の Tau は次のように表すことができます。 ${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle \mathbb {C} }$${\displaystyle r_{1}}$${\displaystyle r_{2}}$

${\displaystyle \tau (r_{1},r_{2})={PQ \over P+Q}=1-{2Q \over P+Q}}$

ここで、は一致するペアの数であり、は一致しないペア（反転）の数です。 と のペアは、との順序と の仕方が一致する場合に一致します。 と が異なる場合は不一致です。 ${\displaystyle P}$${\displaystyle Q}$${\displaystyle d_{i}}$${\displaystyle d_{j}}$${\displaystyle r_{a}}$${\displaystyle r_{b}}$${\displaystyle d_{i}}$${\displaystyle d_{j}}$

情報検索の品質は通常、次の 3 つの測定によって評価されます。

1. 精度
2. 想起
3. 平均精度

データベースへの特定のクエリについて、データベース内の関連する情報要素のセットを 、取得した情報要素のセットを とします。上記の 3 つの測定値は次のように表すことができます。 ${\displaystyle P_{relevant}}$${\displaystyle P_{取得済み}}$

${\displaystyle {\begin{aligned}&{\text{精度}}={\frac {\left|P_{\text{関連}}\cap P_{\text{取得}}\right|}{\left|P_{\text{取得}}\right|}};\\[6pt]&{\text{リコール}}={\frac {\left|P_{\text{関連}}\cap P_{\text{取得}}\right|}{\left|P_{\text{関連}}\right|}};\\[6pt]&{\text{平均精度}}=\int _{0}^{1}{\text{Prec}}({\text{リコール}})\,d{\text{リコール}},\\\end{aligned}}}$

の はどこですか。 ${\displaystyle {\text{Prec}}({\text{Recall}})}$${\displaystyle {\text{精度}}}$${\displaystyle {\text{思い出す}}}$

と をそれぞれデータベースの予想されるランキング方法と提案されたランキング方法とすると、方法の平均精度の下限は次のように表すことができます。 ${\displaystyle r^{*}}$${\displaystyle r_{f(q)}}$${\displaystyle r_{f(q)}}$

${\displaystyle \operatorname {AvgPrec} (r_{f(q)})\geqq {1 \over R}\left[Q+{\binom {R+1}{2}}\right]^{-1}\left(\sum _{i=1}^{R}{\sqrt {i}}\right)^{2}}$

ここで、は、およびの行列の上三角部分にある異なる要素の数であり、はデータセット内の関連する要素の数です。 ${\displaystyle Q}$${\displaystyle r^{*}}$${\displaystyle r_{f(q)}}$${\displaystyle R}$

がトレーニング データ セットの要素であり、が特徴ベクトル、がラベル (のカテゴリを分類する) であるとします。このようなデータ セットの一般的な SVM 分類器は、次の最適化問題の解として定義できます。 ${\displaystyle ({\vec {x}}_{i},y_{i})}$${\displaystyle {\vec {x}}_{i}}$${\displaystyle y_{i}}$${\displaystyle {\vec {x}}_{i}}$

${\displaystyle {\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+CF\sum \xi _{i}^{\sigma }\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\sigma \geqq 0;\\\forall y_{i}({\vec {w}}{\vec {x}}_{i}+b)\geqq 1-\xi _{i}^{\sigma };\end{array}}\\[6pt]&\mathrm {where} \\[6pt]&{\begin{array}{l}b{\text{ is a scalar;}}\\\forall y_{i}\in \left\{-1,1\right\};\\\forall \xi _{i}\geqq 0;\\\end{array}}\end{aligned}}}$

上記の最適化問題の解は、特徴ベクトル s の線形結合として表すことができます。 ${\displaystyle x_{i}}$

${\displaystyle {\vec {w}}^{*}=\sum _{i}\alpha _{i}y_{i}x_{i}}$

ここで、決定する係数です。 ${\displaystyle \alpha _{i}}$

期待されるランキング方法と提案された方法の間のケンドールのタウを とすると、を最大化することで の平均精度の下限を最小化できることが証明できます。 ${\displaystyle \tau _{P(f)}}$${\displaystyle r^{*}}$${\displaystyle r_{f(q)}}$${\displaystyle \tau _{P(f)}}$${\displaystyle r_{f(q)}}$

• 期待損失関数^[9]

負の値は、平均精度の下限を最小化する損失関数として選択することができる。${\displaystyle \tau _{P(f)}}$${\displaystyle r_{f(q)}}$

${\displaystyle L_{\text{expected}}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})\,dPr(q,r^{*})}$

ここで、特定のクエリに対するの統計分布です。 ${\displaystyle Pr(q,r^{*})}$${\displaystyle r^{*}}$${\displaystyle q}$

• 経験的損失関数

期待損失関数は適用できないため、実際にはトレーニング データに対して次の経験的損失関数が選択されます。

${\displaystyle L_{\text{empirical}}=-\tau _{S}(f)=-{1 \over n}\sum _{i=1}^{n}\tau (r_{f(q_{i})},r_{i}^{*})}$

${\displaystyle n}$ iidクエリはデータベースに適用され、各クエリはランキング方法に対応します。トレーニング データ セットには要素があります。各要素には、クエリと対応するランキング方法が含まれます。 ${\displaystyle n}$

各クエリとデータベースの要素を特徴空間にマッピングするには マッピング関数^{[10] [11]が必要であり、特徴空間内の各ポイントはランキング法によって特定のランクでラベル付けされます。}${\displaystyle \Phi (q,d)}$

トレーニング データによって生成されたポイントは特徴空間にあり、ランク情報 (ラベル) も保持します。これらのラベル付きポイントは、それらの順序を指定する境界 (分類子) を見つけるために使用できます。線形の場合、このような境界 (分類子) はベクトルです。

と がデータベース内の 2 つの要素であり、 のランクが特定のランキング方法 よりも高いかどうかを表すものとします。 ベクトル を特徴空間内の線形分類器候補とします。この場合、ランキング問題は次の SVM 分類問題に変換できます。1 つのランキング方法が 1 つのクエリに対応することに注意してください。 ${\displaystyle c_{i}}$${\displaystyle c_{j}}$${\displaystyle (c_{i},c_{j})\in r}$${\displaystyle c_{i}}$${\displaystyle c_{j}}$${\displaystyle r}$${\displaystyle {\vec {w}}}$

${\displaystyle {\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+{\text{constant}}\cdot \sum \xi _{i,j,k}\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\forall \xi _{i,j,k}\geqq 0\\\forall (c_{i},c_{j})\in r_{k}^{*}\\{\vec {w}}(\Phi (q_{1},c_{i})-\Phi (q_{1},c_{j}))\geqq 1-\xi _{i,j,1};\\\,\,\,\vdots \\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\{\text{where }}k\in \left\{1,2,\ldots ,n\right\},\ i,j\in \left\{1,2,\ldots \right\}.\end{array}}\end{aligned}}}$

上記の最適化問題は、古典的な SVM 分類問題と同一であるため、このアルゴリズムは Ranking-SVM と呼ばれます。

訓練サンプルによって得られた 最適ベクトルは${\displaystyle {\vec {w}}^{*}}$

${\displaystyle {\vec {w}}^{*}=\sum \alpha _{k,\ell }^{*}\Phi (q_{k},c_{i})}$

したがって、検索関数は、このような最適な分類子に基づいて形成できます。
新しいクエリの場合、検索関数は最初にデータベースのすべての要素を特徴空間に投影します。次に、これらの特徴点を最適ベクトルとの内積の値で順序付けます。そして、各特徴点のランクは、クエリのデータベースの対応する要素のランクです。 ${\displaystyle q}$${\displaystyle q}$

ランキング SVM は、クエリに応じてページをランク付けするために適用できます。このアルゴリズムは、クリックスルー データを使用してトレーニングできます。クリックスルー データは次の 3 つの部分で構成されます。

1. クエリ。
2. 検索結果の現在のランキング
3. ユーザーがクリックした検索結果

2 と 3 の組み合わせでは、完全な SVM アルゴリズムを適用するために必要な完全なトレーニング データの順序を提供できません。代わりに、トレーニング データのランキング情報の一部が提供されます。そのため、アルゴリズムは次のように少し修正できます。

${\displaystyle {\begin{aligned}&{\text{minimize }}V({\vec {w}},{\vec {\xi }})={1 \over 2}{\vec {w}}\cdot {\vec {w}}+{\text{constant}}\cdot \sum \xi _{i,j,k}\\[6pt]&{\text{subject to}}\\[6pt]&{\begin{array}{l}\forall \xi _{i,j,k}\geqq 0\\\forall (c_{i},c_{j})\in r_{k}'\\{\vec {w}}(\Phi (q_{1},c_{i})-\Phi (q_{1},c_{j}))\geqq 1-\xi _{i,j,1};\\\,\,\,\vdots \\{\vec {w}}(\Phi (q_{n},c_{i})-\Phi (q_{n},c_{j}))\geqq 1-\xi _{i,j,n};\\{\text{where }}\ k\in \left\{1,2,\ldots ,n\right\},\ i,j\in \left\{1,2,\ldots \right\}.\end{array}}\end{aligned}}}$

この方法はデータセット全体のランキング情報を提供するものではなく、完全なランキング方法のサブセットです。そのため、最適化問題の条件は、元の Ranking-SVM と比較して緩和されます。 ${\displaystyle r'}$