品質指標のランキング

GoToサマースクールの入学テストのタスクを準備する過程で、ロシア語では、主なランキングメトリックの定性的な記述は事実上ないことがわかりました（この問題は、ランキング問題の特別なケース-推奨アルゴリズムの構築に関するものです）。 E-Contentaでは、さまざまなランキング指標を積極的に使用しているため、この記事を書くことで誤解を招いてこれを修正することにしました。





ランク付けタスクは、あらゆる場所で発生します。特定の検索クエリに従ってWebページをソートし、ニュースフィードをパーソナライズし、ビデオ、製品、音楽を推奨します。つまり、トピックはホットです。 機械学習には、自己学習ランキングアルゴリズム（ランク付けの学習）を研究する特別な領域もあります。 さまざまなアルゴリズムとアプローチの中から最適なものを選択するには、その品質を定量化できる必要があります。 最も一般的なランキング品質指標については、後で説明します。

ランキングタスクについて簡単に

ランキングは、 関連性の理由で要素のセットをソートするタスクです。 ほとんどの場合、関連性は特定のオブジェクトに関連して理解されます 。 たとえば、情報検索のタスクでは、オブジェクトはリクエストであり、要素はすべての種類のドキュメント（それらへのリンク）であり、関連性はドキュメントとリクエストの対応であり、推奨のタスクでは同じオブジェクトがユーザーであり、要素は1つまたは別の推奨コンテンツ（商品、ビデオ、音楽） ）、および関連性は、ユーザーがこのコンテンツを使用する（購入/いいね/見る）確率です。

正式には、N個のオブジェクトを考慮します およびM要素 。 要素ランキングアルゴリズムの復活 オブジェクト用 マッピングです 各要素にマップする 重さ 、要素とオブジェクトの関連性の程度を特徴付けます（重みが大きいほど、オブジェクトの関連性が高くなります）。 同時に、重みのセット 順列を設定します 一連のアイテム要素 （要素のセットは順序付けられていると考えられます）重みの降順での並べ替えに基づいて 。

ランキングの品質を評価するには、アルゴリズムの結果を比較できる「標準」が必要です。 検討する -特定のオブジェクトの要素の「実際の」関連性を特徴付ける参照関連性関数（ -アイテムは完璧です、 -完全に無関係）、および対応する順列 （降順 ）

取得する主な方法は2つあります ：
1.履歴データに基づきます。 たとえば、コンテンツの推奨の場合、ユーザービュー（いいね！、購入）を取得し、対応する要素の表示された重みに1を割り当てることができます（ ）、およびその他すべて-0。
2.専門家の判断に基づきます。 たとえば、検索タスクでは、リクエストごとに、リクエストに対するドキュメントの関連性を手動で評価する評価者のチームを引き付けることができます。

注目すべきことは 極端な値のみを取ります：0と1、次に順列 通常、関連する要素のセットのみを考慮せず、考慮しません 。

ランキング品質メトリックの目的は 、関連性スコアの関連性を判断することです および対応する順列 真の関連性値に一致 。 基本的な指標を検討してください。

平均精度

K（map @ K）での平均平均精度は、最も一般的に使用されるランキング品質メトリックの1つです。 どのように機能するかを理解するために、「基本」から始めましょう。

注：「*精度」メトリックは、バイナリ問題で使用されます。 0と1の2つの値のみを取ります。

kでの精度

Kでの精度（p @ K） -K要素の精度-単一オブジェクトの基本的なランキング品質メトリック。 ランキングアルゴリズムが各アイテムの関連性評価を生成したとします。 。 それらの中から最初に選択する 最大のアイテム 関連の割合を計算できます。 これは、Kでの精度とまったく同じです。



注：下 理解された要素 順列の結果として 終わった 番目の位置。 だから -最大の要素 、 -2番目に大きい要素 などなど。

Kでの平均精度

Kでの精度-メトリックは理解および実装が簡単ですが、重要な欠点があります-「トップ」の要素の順序を考慮しません。 したがって、10個の要素のうち1つだけを推測した場合、最初の場合でも最後の場合でも、彼がどこにいたかは関係ありません。 。 最初のオプションがはるかに優れていることは明らかです。

この欠点により、 K（ap @ K）でのランキングメトリックの平均精度がなくなります。これは、Kで割った関連要素の 1〜Kのインデックスkでの合計p @ kに等しくなります。


したがって、3つの要素のうち、最後の場所にしかいなかった場合、 最初にあったものだけを推測した場合、 、すべてが推測された場合、 。

さて、地図@ Kは私たちには難しすぎます。

Kでの平均平均精度

K（map @ K）での平均平均精度は、最も一般的に使用されるランキング品質メトリックの1つです。 p @ Kおよびap @ Kでは、ランキングの品質は単一のオブジェクト（ユーザー、検索クエリ）に対して評価されます。 実際には、多くのオブジェクトがあります。数十万のユーザー、数百万の検索クエリなどを扱っています。 map @ Kの考え方は、各オブジェクトと平均についてap @ Kを計算することです。


注：すべてのユーザーが等しく必要であり、同様に重要であると想定する場合、この考えは非常に論理的です。 そうでない場合は、単純な平均化の代わりに、各オブジェクトのap @ Kにその「重要度」に対応する重みを掛けることにより、重み付きの重みを使用できます。

正規化された割引累積ゲイン

正規化された割引累積ゲイン（nDCG）は、別の一般的なランキング品質メトリックです。 map @ Kと同様に、基本から始めましょう。

kでの累積ゲイン

もう一度1つのオブジェクトを見てみましょう。 最大のアイテム 。 Kでの累積ゲイン（CG @ K）は、単純なアイデアを使用する基本的なランキングメトリックです。この最上部の関連要素は、より優れています。


このメトリックには明らかな欠点があります。正規化されておらず、関連する要素の位置を考慮していません。

p @ Kとは異なり、CG @ Kは参照関連性の非バイナリ値の場合にも使用できることに注意してください。 。

Kでの割引累積ゲイン

Kでの割引累積ゲイン（DCG @ K） -位置番号の逆対数に等しい重みで要素の関連性を乗算することにより、リスト内の要素の順序を考慮した、Kでの累積ゲインの変更：


注：場合 値0と1のみを取り、その後 、および式はより単純な形式を取ります。


対数を割引関数として使用することは、次の直観的な考慮事項によって説明できます。ランキングの観点から、リストの先頭の位置は末尾の位置よりもはるかに異なります。 そのため、検索エンジンの場合、位置1と11の間に大きなギャップがあります（100のうちわずかな場合のみ、ユーザーは検索結果の最初のページを超えます）が、位置101と111の間に大きな違いはありません。 これらの主観的な考慮事項は、対数を使用して完全に表現されます。


割引累積ゲインは、関連する要素の位置を考慮に入れる問題を解決しますが、正規化の欠如による問題を悪化させるだけです。 内で変化する それから すでに完全に明確ではないセグメントで値を取得しています。 次のメトリックは、この問題を解決するために設計されています。

Kでの正規化された割引累積ゲイン

名前が示すように、 Kでの正規化された割引累積ゲイン（nDCG @ K）は、DCG @ Kの正規化バージョンにすぎません。


どこで 最大（I-理想）値 。 私たちが同意したので 値を取る それから 。

このように から継承 リスト内の要素の位置を考慮し、同時に0から1の範囲の値を取ります。

注：map @ Kとの類推により、計算できます 、すべてのオブジェクトの平均 。

平均逆数ランク

平均相互ランク（MRR）は、別の一般的に使用されるランキング品質メトリックです。 次の式で定義されます。


どこで -の相互ランク i番目のオブジェクトのは、本質的に非常に単純な値であり、最初に正しく推測された要素の逆の傷に等しい。


範囲[0,1]の平均逆ランクの変化は、要素の位置を考慮に入れます。 残念なことに、彼はこれを1つの要素に対してのみ行います。最初に正しく予測された要素で、以下のすべてに注意を払っていません。

ランク相関メトリック

それとは別に、 ランク相関係数の 1つに基づいてランク付け品質メトリックを強調する価値があります。 統計では、ランク相関係数は、値自体ではなく、ランク（順序）のみを考慮した相関係数です。 最も一般的な2つのランク相関係数、スピアマン係数とカンデル係数を考えます。

ケンドールランク相関係数

これらの最初のものはCandell相関係数です。これは、matchedの計算に基づいています。
（および一貫性のない）置換のペア-置換が同じ（異なる）順序を割り当てた要素のペア：

スピアマンの順位相関係数

2番目のスピアマンのランク相関係数は、本質的にランク値に基づくピアソン相関にすぎません。 ランクから直接それを表現するかなり便利な公式があります：


どこで -ピアソン相関係数。

ランク相関ベースのメトリックには、既知の欠点があります：要素の位置を考慮しません（最高ランクのK要素ではなく、すべての要素に対して相関が計算されるため、p @ Kよりもさらに悪い）。 したがって、実際にはこれらはほとんど使用されません。

カスケード動作メトリック

ここまでは、ユーザーが提案された要素をユーザーがどのように研究するかについては掘り下げませんでした（さらに、オブジェクトの特殊なケースであるユーザーを検討します）。 実際、各要素を表示することは、他の要素を表示することから独立している 、つまり一種の「素朴さ」であると暗黙的に仮定しました。 実際には、要素はユーザーによって一度に1つずつ表示されることが多く、ユーザーが次の要素を表示するかどうかは、前の要素に対する満足度によって決まります。 例について考えてみましょう。検索クエリに応答して、ランキングアルゴリズムはユーザーに複数のドキュメントを提供しました。 位置1と2のドキュメントが非常に関連性が高い場合、ユーザーが位置3のドキュメントを見る可能性は小さいです。 彼は最初の2つに非常に満足しています。

彼に提案された要素の研究が連続して実行され、要素を見る確率は前のものの関連性に依存するユーザー行動の同様のパターンはカスケードと呼ばれます。

期待される相互ランク

期待相反ランク（ERR）は、カスケードモデルのランク付け品質メトリックの例です。 次の式で定義されます。

$$

$$ERR @ K = \ sum \ limits_ {k = 1} ^ K \ frac {1} {k} P（\ textrm {オブジェクトはランク$ k $}の要素で停止します）、$$

ランクは降順で理解されます 。 このメトリックに関する最も興味深いことは、確率です。 それらを計算するとき、カスケードモデルの仮定が使用されます。

$$

$$P（\ textrm {ランク$ k $の要素でオブジェクトが停止します）= p_k \ prod \ limits_ {i = 1} ^ {k-1}（1-p_i）、$$

どこで -ユーザーがランク付きのオブジェクトに満足する確率 。 これらの確率は値に基づいて計算されます 。 私たちの場合 、その後、単純なオプションを検討できます。


次のように読むことができます： 位置にある要素の真の関連性 降順でソートした後 。
一般的な場合、次の式が最もよく使用されます。

ポンド

PFoundは、 同胞によって提案され、次のようなカスケードモデルを使用したランキング品質指標です。


どこで

• 、
• もし それ以外の場合は0
• -ユーザーが外部の理由で表示を停止する可能性。

---

結論として、トピックに関するいくつかの有用なリンクを提供します。
-ウィキペディアの記事： ランキングトレーニング 、 MRR 、 MAP、およびnDCG 。
-ROMIP 2010で使用されるメトリックの公式リスト 。
-kaggle.comのMAPおよびnDCGメトリックの説明。
- カスケードモデルのオリジナル記事、 ERRおよびPFound 。

StackEditを使用して書かれています 。
素晴らしいhabratexの SeptiMに感謝します。