割引累積利益

割引累積ゲイン（DCG ）は、情報検索におけるランキング品質の尺度です。クエリ間で比較できるように正規化されることが多く、正規化DCG（nDCGまたはNDCG）となります。NDCGは、検索エンジンアルゴリズムと関連アプリケーションの有効性を測定するためによく使用されます。検索エンジンの結果セットにある文書の段階的関連度スケールを使用して、DCGは、結果リスト内の位置によって割引された結果の有用性、つまりゲインを合計します。 [ 1 ] NDCGは、最高ゲインから最低ゲインまでランク付けした場合の結果セットの最大可能DCGによって正規化されたDCGであり、異なるクエリの異なる関連結果の数に合わせて調整されます。

概要

DCG とその関連尺度を使用する際には、2 つの仮定が立てられます。

  1. 関連性の高いドキュメントは、検索エンジンの検索結果リストの上位に表示されるとより役立ちます（ランクが高くなります）。
  2. 関連性の高いドキュメントは、関連性がわずかに高いドキュメントよりも有用であり、関連性がわずかに低いドキュメントは、関連性の低いドキュメントよりも有用です。

累積利益

DCGは、よりシンプルな指標である累積ゲイン（CG）を改良したものです。[ 2 ]累積ゲインとは、検索結果リスト内の全ての結果の段階的関連性値の合計です。CGは、検索結果リストにおける結果の順位（位置）を考慮しません。特定の順位におけるCGは以下のように定義されます。 p{\displaystyle p}

CGp＝∑私＝1prel私{\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}

位置 の結果の段階的関連性はどこですか。 rel私{\displaystyle rel_{i}}私{\displaystyle i}

CG関数で計算される値は、検索結果の順序変更の影響を受けません。つまり、関連性の高い文書を、上位にランク付けされているものの関連性の低い文書の上に移動しても、CGの計算値は変わりません（ と仮定）。検索結果の有用性に関する上記の2つの仮定に基づくと、通常はCGよりも(N)DCGが優先されます。累積ゲインは段階的精度と呼ばれることもあります。 d私{\displaystyle d_{i}}dj{\displaystyle d_{j}}私、j≤p{\displaystyle i,j\leq p}

割引累積利益

DCG の前提は、段階的な関連性の値が結果の位置に比例して対数的に減少するため、検索結果リストの下位に表示される関連性の高いドキュメントにはペナルティを課すべきであるというものです。

特定のランク位置で蓄積されたDCGの通常の式は次のように定義されます: [ 1 ]p{\displaystyle p}

DCGp＝∑私＝1prel私ログ2⁡（私+1）＝rel1+∑私＝2prel私ログ2⁡（私+1）{\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {rel_{i}}{\log _{2}(i+1)}}=rel_{1}+\sum _{i=2}^{p}{\frac {rel_{i}}{\log _{2}(i+1)}}}

2013年までは、対数削減係数[ 3 ]を用いることについて、滑らかな削減効果が得られるという以外に、理論的に十分な根拠はありませんでした。しかし、Wang et al. (2013) [ 2 ]は、正規化DCG（NDCG）における対数削減係数の使用を理論的に保証しました。著者らは、大きく異なるランキング関数のペアに対して、NDCGがどちらが優れているかを一貫した方法で判断できることを示しています。

DCGの別の定式化[ 4 ]では、関連文書の検索に重点が置かれています。

DCGp＝∑私＝1p2rel私−1ログ2⁡（私+1）{\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}

後者の式は、大手ウェブ検索会社[ 5 ]やKaggleなどのデータサイエンス競争プラットフォームを含む産業用アプリケーションで一般的に使用されています。[ 6 ]

DCGのこれらの2つの定式化は、文書の関連値が2値の場合に同じです。[ 3 ]：320 。 rel私∈{0、1}{\displaystyle rel_{i}\in \{0,1\}}

Croft et al. (2010) と Burges et al. (2005) は、2つ目のDCGを底eの対数で表しているのに対し、上記の2つのDCGは底2の対数を使用していることに注意してください。DCGの最初の定式化でNDCGを計算する場合、対数の底は重要ではありませんが、2つ目の定式化では対数の底がNDCGの値に影響を与えます。明らかに、両方の定式化において、対数の底はDCGの値に影響を与えます。

DCGの凸近似と滑らかな近似も開発されており、勾配ベースの学習法における目的関数として使用されています。[ 7 ]

正規化されたDCG

検索結果リストの長さはクエリによって異なります。検索エンジンのパフォーマンスをクエリごとにDCGのみで一貫して比較することはできません。そのため、選択した の値に対する各位置の累積ゲインをクエリ間で正規化する必要があります。これは、コーパス内のすべての関連文書を相対的な関連性で並べ替え、位置までの可能な限り最大のDCG（理想DCG（IDCG）とも呼ばれます）を生成することによって行われます。クエリの場合、正規化された割引累積ゲイン（nDCG）は次のように計算されます。 p{\displaystyle p}p{\displaystyle p}

nDCGp＝DCGp私DCGp{\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}、

ここでIDCGは理想的な割引累積利得であり、

私DCGp＝∑私＝1|RELp|2rel私−1ログ2⁡（私+1）{\displaystyle \mathrm {IDCG_{p}} =\sum _{i=1}^{|REL_{p}|}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}

コーパス内の位置 p までの関連文書のリスト（関連度順に並べられた）を表します 。RELp{\displaystyle REL_{p}}

すべてのクエリのnDCG値を平均化することで、検索エンジンのランキングアルゴリズムの平均パフォーマンスを測ることができます。完璧なランキングアルゴリズムでは、 nDCG値が1.0となるのと同じ値になります。すべてのnDCG計算は0.0から1.0の範囲における相対値となるため、クエリ間で比較可能です。 DCGp{\displaystyle DCG_{p}}私DCGp{\displaystyle IDCG_{p}}

nDCG を使用する際に遭遇する主な困難は、部分的な関連性フィードバックしか利用できない場合に、結果の理想的な順序付けが利用できないことです。

例

実験参加者は、検索クエリに対する文書リストを提示され、各文書のクエリへの関連性を判断するよう求められます。各文書は0～3の尺度で評価され、0は関連性なし、3は関連性が非常に高い、1と2は「その中間」を意味します。ランキングアルゴリズムによって以下のように順序付けられた文書については、

D1、D2、D3、D4、D5、D6{\displaystyle D_{1}、D_{2}、D_{3}、D_{4}、D_{5}、D_{6}}

ユーザーは次の関連性スコアを提供します。

3、2、3、0、1、2{\displaystyle 3,2,3,0,1,2}

つまり、ドキュメント 1 の関連性は 3、ドキュメント 2 の関連性は 2 などです。この検索結果リストの累積ゲインは次のようになります。

CG6＝∑私＝16rel私＝3+2+3+0+1+2＝11{\displaystyle \mathrm {CG_{6}} =\sum _{i=1}^{6}rel_{i}=3+2+3+0+1+2=11}

2つの文書の順序を変えても、CG指標は変化しません。とを入れ替えても、CGは変わりません。11. DCGは、結果リストの先頭に表示される関連性の高い文書を強調するために使用されます。対数スケールを使用して縮小すると、各結果のDCGは次のようになります。 D3{\displaystyle D_{3}}D4{\displaystyle D_{4}}

私{\displaystyle i}rel私{\displaystyle rel_{i}}ログ2⁡（私+1）{\displaystyle \log _{2}(i+1)}rel私ログ2⁡（私+1）{\displaystyle {\frac {rel_{i}}{\log _{2}(i+1)}}}
1 3 1 3
2 2 1.585 1.262
3 3 2 1.5
4 0 2.322 0
5 1 2.585 0.387
6 2 2.807 0.712

このランキングの 結果は次のようになります。DCG6{\displaystyle DCG_{6}}

DCG6＝∑私＝16rel私ログ2⁡（私+1）＝3+1.262+1.5+0+0.387+0.712＝6.861{\displaystyle \mathrm {DCG_{6}} =\sum _{i=1}^{6}{\frac {rel_{i}}{\log _{2}(i+1)}}=3+1.262+1.5+0+0.387+0.712=6.861}

ここで、とを切り替えると、関連性の低いドキュメントがランキングの上位に配置されるため、DCG が減少します。つまり、関連性が高いドキュメントは、より低いランクに配置されることで、より割引されます。 D3{\displaystyle D_{3}}D4{\displaystyle D_{4}}

この形式では、このクエリと他のクエリのパフォーマンスを比較することはできません。他のクエリの方が結果が多く、全体的なDCGが大きくなる可能性があるためです。これは必ずしも優れているとは限りません。比較するには、DCG値を正規化する必要があります。

DCG値を正規化するには、与えられたクエリに対する理想的な順序付けが必要です。この例では、既知の関連性判断すべてを単調減少順に並べたものが理想的な順序付けとなります。この実験で得られた6つの文書に加えて、同じクエリに対して関連性グレード3の文書と関連性グレード2の文書が存在することが分かっているとします。この場合、理想的な順序付けは次のようになります。 D7{\displaystyle D_{7}}D8{\displaystyle D_{8}}

3、3、3、2、2、2、1、0{\displaystyle 3,3,3,2,2,2,1,0}

理想的なランキングは、ランキングの分析の深​​さに合わせて、長さ 6 に再度短縮されます。

3、3、3、2、2、2{\displaystyle 3,3,3,2,2,2}

この理想的な順序の DCG、つまりIDCG (理想的な DCG)は、ランク 6 まで計算されます。

私DCG6＝8.740{\displaystyle \mathrm {IDCG_{6}} =8.740}

したがって、このクエリの nDCG は次のように表されます。

nDCG6＝DCG6私DCG6＝6.8618.740＝0.785{\displaystyle \mathrm {nDCG_{6}} ={\frac {DCG_{6}}{IDCG_{6}}}={\frac {6.861}{8.740}}=0.785}

制限事項

  1. 正規化DCGは、結果に不良文書が含まれていてもペナルティを課しません。例えば、クエリがそれぞれスコア1,1,1と1,1,1,0の2つの結果を返した場合、後者に不良文書が含まれていても、どちらも同等に良好とみなされます。Excellent 、Fair、Badのランク付け判定では、 2,1,0ではなく1,0,-1といった数値スコアを使用する場合もあります。これにより、不良な結果が返された場合にスコアが下げられ、再現率よりも結果の精度が優先されます。ただし、このアプローチは全体的なスコアがマイナスになる可能性があります。
  2. 正規化DCGは、結果に欠落したドキュメントがあってもペナルティを課しません。例えば、クエリがそれぞれスコア1,1,1と1,1,1,1,1という2つの結果を返した場合、理想的なDCGが前者のランク3、後者のランク5と計算されると仮定すると、どちらも同等に優れているとみなされます。この制限を考慮する1つの方法は、結果セットのサイズを固定し、欠落したドキュメントには最小スコアを使用することです。前の例では、スコア1,1,1,0,0と1,1,1,1,1を使用し、nDCGをnDCG@5と引用符で囲みます。
  3. 正規化DCGは、同等に優れた結果が複数存在する可能性があるクエリのパフォーマンス測定には適さない場合があります。特に、この指標が最初の数件の結果のみに限定されている場合、これは実際によく見られる現象です。例えば、「レストラン」のようなクエリの場合、nDCG@1は最初の結果のみを考慮します。一方の結果セットには近隣地域のレストランが1件しか含まれておらず、もう一方の結果セットには5件含まれている場合、後者の方がより包括的であるにもかかわらず、両方の結果セットのスコアは同じになります。

参照

参考文献

  1. ^ a b Kalervo Järvelin、Jaana Kekäläinen、「IR 技術の累積ゲインベース評価」。情報システムに関する ACM トランザクション20 (4)、422–446 (2002)
  2. ^ a b Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Wei Chen, Tie-Yan Liu . 2013. 「正規化割引累積利得（NDCG）ランキング尺度の理論的分析」第26回学習理論年次会議（COLT 2013）の議事録。
  3. ^ a b B. Croft、D. Metzler、T. Strohman (2010). 『検索エンジン：実践的な情報検索』Addison Wesley.
  4. ^ Chris Burges、Tal Shaked、Erin Renshaw、Ari Lazier、Matt Deeds、Nicole Hamilton、Greg Hullender. 2005. 勾配降下法を用いたランキング学習. 第22回国際機械学習会議 (ICML '05) 論文集. ACM, ニューヨーク, ニューヨーク州, 米国, 89-96. DOI=10.1145/1102351.1102363 http://doi.acm.org/10.1145/1102351.1102363
  5. ^ 「情報検索入門 - 評価」(PDF)スタンフォード大学 2013年4月21日. 2014年3月23日閲覧。
  6. ^ 「正規化割引累積利得」 。 2014年3月23日時点のオリジナルよりアーカイブ。2014年3月23日閲覧。
  7. ^ D. Cossock、T. Zhang、「ベイズ最適サブセットランキングの統計分析」、 IEEE Transactions on Information Theory、vol. 54、no. 11、pp. 5140-5154、2008年11月、doi: 10.1109/TIT.2008.929939。
「 https://en.wikipedia.org/w/index.php?title=Discounted_cumulative_gain&oldid=1223546723」より取得