| Index A I | ランキング学習 |
|
ランキング学習 手法 ポイントワイズ ペアワイズ リストワイズ 学習データ 特徴量 評価指標 nDCG NNRank RankNet LambdaRank LambdaMART ListNet フレームワーク NN機能・要件 NN構成・方式 構成・方式など タスク 導入 Sample 用語 |
ランキング学習 ・データ \(x\) が集合 \(\mathbb{ R }\) の要素の場合 （\(x \in \mathbb{ R }\)） ・\(f_{ w }(x):\mathbb{ R }^n → \mathbb{ R }\) を定義し、その大きさの 順序 を出力するアルゴリズム 優れた 順番 を生成するパラメータ \(w\) を得る目的で使用する。ランキング学習の手法 ・目的関数 （文書の並び順を予測する場合に最適化する 損失関数 ）の定義方法で分ける。 ポイントワイズ ペアワイズ リストワイズ・損失を計算できるようにし、それを最少化して行き、良いランキングモデルを得る。 ポイントワイズ（pointwise） ・1つのサンプルから損失を定義する。 ・ポイントワイズの損失関数 \(L_{ 0 }\) = \(\sum_{q,d}^{} L(f(x_{ q,d }),y_{ q,d })\)・二乗誤差 を用いた場合の最少化問題 \(L(f(x_{ q,d }),y_{ q,d })\) = \((y_{ q,d } - f(x_{ q,d }))^2\) 回帰問題、多クラスの分類問題を解くと同じだが、ランキングが旨く出ればよい。・主な方法 NNRankペアワイズ（pairwise） ・2つのサンプルペアから損失を定義する。 ペア間の関係を考慮した損失関数の損失を最小化・ペアワイズの損失関数 \(L_{ 0 }\) = \(\sum_{q}^{}\sum_{i,j:y_{ q,i }>y_{ q,j }}^{m_{ q }} L(f(x_{ q,i }),f(x_{ q,j }))\)・スコアの差に指数関数に通した誤差を用いた場合の最少化問題 \(L(f(x_{ q,i }),f(x_{ q,j }))\) = \(exp( f(x_{ q,j }) - f(x_{ q,i }))\) ・主な方法 RankNetリストワイズ（listwise） ・複数のサンプルリストから損失を定義する。 ・リストワイズの損失関数 \(L_{ 0 }\) = \(\sum_{q}^{} L(f(x_{ q,1 }),y_{ q,1 }),...,f(x_{ q,m_{ q } }),y_{ q,m_{ q } }))\)・ランキング問題の評価指標が存在する場合、直接それを最適化する。という発想 ・主な方法 ListNet学習データ ・学習データの単位はランキングされる一つ一つの要素 （q=1,2...,Q, d=1,...,\(m_{ q }\)） 検索の場合は、検索キーワード（Q個）と、それに対応する検索結果のリストのペア レースなどでは、レースコード（Qレース）と、出る物の持つ情報のリストのペア・各リストの数（\(m_{ q }\)：ランキングの単位を表すQueryデータ） （どこからどこまでのデータを一纏まりとして扱うかを表す。） 検索の場合は、検索結果の各文書（d）リストの数 都道府県を対象する場合は、47 競争の場合は、出走する物の数・各文書（d）にはラベル（\(y_{ q,d }\)：ランキングの数値、学習ターゲット） 関連度の高い方が上位へ来るように設定する。 各「検索結果」には「検索キーワード」との関連度を表すラベルが付く。 5種類の値をとるカテゴリ値の例 Perfect（4）、Excellent（3）、Good（2）、Fair（1）、Bad（0） レースなどでは、順位・学習データの形式 （\(x_{ q,d }\),\(y_{ q,d }\)）,q=1,2...,Q, d=1,...,\(m_{ q }\)特徴量 （\(x_{ q,d }\)：文書の並び順を予測する場合） ・文書から得られる特徴量 文書に含まれる単語数や特定の単語が文書に含まれるかのone-hot表現など EC（Eコマース）サイトでは、商品の価格や商品の購入数など・検索キーワードから得られる特徴量 検索キーワードの長さ その検索キーワードの過去1週間分のリクエスト数・文書と検索キーワードのペアから与えられる特徴量 文書と検索キーワードマッチングスコア TF-IDF、BM25など評価指標（評価関数） ・ランキング予測結果の評価指標として nDCG を使うことが多い。 損失関数の直接最適化が難しい場合の緩和した問題を解くアルゴリズム 予測値の差分にしか着目していない場合など （上位1、3位と上位51、53位の組合せの予測値の差分が等しい場合に同じ損失値）nDCG （Normalized Discounted Cumulative Gain、割引累積ゲインの正規化） ・ランキング予測結果の評価指標 上位が正解するとスコアが高くなる評価指標・Discounted Cumulative Gain（DCG）を正規化した値 ・関連度の高いデータをより上位に予測できたときに値が大きくなる。 ・nDCGは 0 から 1 の値を取る。1に近いほど正しいランキング予測結果 ・ランキング予測からのDCGを正しいランキングを用いて得られるDCGで割って正規化 ・DCGの計算方法は二つある。（二つの定義、正規化する方法は同じ） ・DCG定義1 = \(rel_{1}\) + \(\sum_{i=2}^{k}\frac{rel_{i}}{log_{2}\ i}\) そこそこの適合度でも良いからたくさん当てたいケース・DCG定義2 = \(\sum_{i=1}^{k}\frac{2^{rel_{i}}-1}{log_{2}(i+1)}\) 適合度を 2 のべき乗で扱う点がDCG定義1と異なる。 どれか1つでも良いから高い適合度の要素を当てたいケース・\(rel_{i}\) レイティング（適合度、基準に基づき等級分けや数値化を行ったもの） \(rel_{i}\) はランキング中のi番目の要素の適合度・\(k\) は評価に用いる要素数 検索エンジンなどでは k=10 が多い。・参考（DCG） ・検索結果リストの上位何件を評価に用いるかというパラメータを持つ場合もある。 ndcg_eval_at = 1,3,5 （LightGBMの場合） NNRank ・ポイントワイズ 関連度のようなスコアは得られない。・多層パーセプトロン を用いたアルゴリズム 文書を分類 出力ノード数は分類の数 - 1、活性化関数 は シグモイド関数 出力ノードにしきい値がある。RankNet ・ペアワイズ 二つの文書の中でどちらの方が関連度が高い（ランクが高い）かを予測 出力値（スコア）が、ランクの高いデータは低いデータより大きくなるように学習 出力されるのはは１個の文書関連度のようなスコア・多層パーセプトロンのアルゴリズム ペアワイズの損失を最小化する。 ペアワイズの損失が下がるからといって必ずしも精度が上がるわけではない。・交差エントロピー誤差を最小化してランキングを正確化 モデルが出力した確率と真の確率のクロスエントロピーを最小化・データ \(x_{ i }\) とデータ \(x_{ j }\) の順序を比べる。（ 2つのデータのスコア差 \(o_{ ij }\) ） \(o_{ ij }\) = \( f(x_{ i }) - f(x_{ j })\) が 0より大きいならば前者がより順位が高い。（確率が高い。）・その確率が \(o_{ ij }\) にのみ依っていると仮定したモデルにする。 \(P_{ ij }\) = \(sigmoid(o_{ ij })\) = \( \frac{1}{1 + exp(−o_{ij})} \)・真の確率を \(\overline{ P }_{ ij }\) とし、\(P_{ ij }\) に関する交差エントロピー誤差は \(C_{ ij }\) = \(−\overline{ P }_{ ij }logP_{ ij } − (1 − \overline{ P }_{ ij })log(1 − P_{ ij })\) = \(−o_{ ij }\overline{ P }_{ ij } + log(1 + exp(−o_{ij}))\)・真の確率を 「 \(x_{ i }\) の方が順位が高いので 1 」 とすると \(C_{ ij }\) は \(C_{ ij }\) = \(log(1 + exp(−o_{ij}))\)・真の確率を 「 \(x_{ j }\) の方が順位が高いので 0 」 とすると \(C_{ ij }\) は \(C_{ ij }\) = \(log(1 + exp(o_{ij}))\)・真の確率を 「順位が同じなので 1/2」 とすると Cij は \(C_{ ij }\) = \(log(exp(\frac{1}{2}o_{ij}) + exp(−\frac{1}{2}o_{ij}))\)・データ（ I ）で、与えられた \(x_{ i }\) と \(x_{ j }\) の比較で \(x_{ i }\) の方が順位が高い場合 最小化したい損失は \(C_{}\) = \(\sum_{(i,j)∈I}C_{ij}\)・C についてパラメータ \(w\) の微分を求め、 確率的勾配降下法 （ 勾配降下法 ）で C を最小化 \(\frac{∂C}{∂w}\) = \(\sum_{(i,j)∈I}\frac{∂C_{ij}}{∂w}\) =\(\sum_{(i,j)∈I}\frac{∂C_{ij}}{∂o_{ij}}(\frac{∂f_{w}(x_{i})}{∂w} − \frac{∂f_{w}(x_{j})}{∂w})\) = \(\sum_{i} λ_{i} \frac{∂f_{w}(x_{i})}{∂w}\)
（\(λ_{i}\) = \(\sum_{j:(i,j)∈I}\frac{∂C_{ij}}{∂o_{ij}}\) - \(\sum_{j:(j,i)∈I}\frac{∂C_{ji}}{∂o_{ji}}\)・\(Σ\) が \((i,j)\)に関する和から \(i\) に関する和に変わるとモデルの微分計算はデータ数分に減る。 ・PyTorchを用いたRankNetの実装 （ sample ） LambdaRank ・ペアワイズ （ランクのリストが必要） ・多層パーセプトロンのアルゴリズム RankNetの拡張 NDCG や MRR など精度評価指標を直接最適化する。 損失を最小化して精度があがる。・上位N位までの正確性を重視したい場合の損失関数を工夫 \(L((f(x_{1}),f(x_{2}),...,f(x_{m})),(l_{1},l_{2},...,l_{m}))\) \(f(x_{i})\)：モデルの出力、\(l_{i}\)：実際の順位 交差エントロピー誤差以外の指標を最小化したいケースで使える。 但し、順位が関係する損失関数は一般的に連続値を取らない。 微分を用いた最適化が出来ない。・ペアワイズ の RankNet を改変した微分を使用 \(\frac{∂C}{∂w}\) = \(\sum_{(i,j)∈I}\frac{∂C_{ij}}{∂o_{ij}}(\frac{∂f_{w}(x_{i})}{∂w} − \frac{∂f_{w}(x_{j})}{∂w})\) 次のように改変（\( |Δ_{ ij }|\) 倍する。） \(\frac{∂C'}{∂w}\) = \(\sum_{(i,j)∈I}\frac{∂C_{ij}}{∂o_{ij}} |Δ_{ij}| (\frac{∂f_{w}(x_{i})}{∂w} − \frac{∂f_{w}(x_{j})}{∂w})\) \( |Δ_{ ij }| \) は、\(f(x_{i})\) と \(f(x_{j})\) の値を逆にしたときの損失の差 \(L(...,f(x_{i}),...,f(x_{j}),...),(l_{1},l_{2},...,l_{m}))\) ― \(L(...,f(x_{j}),...,f(x_{i}),...),(l_{1},l_{2},...,l_{m}))\) \( |Δ_{ ij }| \) を計算するためクエリに対する文書のリストの情報が必要 ペアワイズだがリストの情報が必要 損失関数 \(C'\) が存在する場合、勾配降下法で \(L\) を小さくできる。・勾配の計算方法を与えているので、微分可能なモデルに適用できる。（勾配のモデル化） LambdaRank では損失関数の勾配を直接定義 損失関数そのものがどういう形をしているかは不明 損失を最小化、最大化するために損失関数そのものではなくその勾配が必要 損失関数が不明でも正確なモデルを得られる。 勾配の積分である損失関数は必ず存在しなければならないという条件を満たす必要あり。・Queryデータ 当該ランキングに含まれている学習データの数 Queryデータの合計は学習データの数と一致LambdaMART ・LambdaRankをGradient Boostingに適用 MART
（GBDT）に LambdaRank の勾配を入れる。・\(f(x_{i})\) に関する損失の勾配 \(\frac{∂C'}{∂f(x_{i})}\) = \(\sum_{(i,j)∈I}\frac{∂C_{ij}}{∂o_{ji}} |Δ_{ ij }| - \sum_{(j,i)∈I}\frac{∂C_{ij}}{∂o_{ji}} |Δ_{ ij }| \)
= \((\sum_{(i,j)∈I} - \sum_{(j,i)∈I})\frac{∂C_{ij}}{∂o_{ji}} |Δ_{ ij }| \)
= \((\sum_{(i,j)∈I} - \sum_{(j,i)∈I}) \frac{-|Δ_{ ij }|}{1 + exp(f(x_{i}) - f(x_{j}))} \)ListNet ・リストワイズ リストワイズのネットワーク構造は RankNet と同様 エントロピーの損失関数がペアワイズではなくリストワイズ・多層パーセプトロンのアルゴリズム リストワイズの損失を最小化する。・RankNet の損失関数では文書i,j で文書i の方が関連度が高い確率を用いる。 ListNet では文書i が１位になる確率を用いる。フレームワーク ・XGBoost ・LightGBM |
| All Rights Reserved. Copyright (C) ITCL | |