割引累積利益

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

概要

DCGとその関連指標を用いる際には、2つの前提条件が設けられています。

関連性の高い文書は、検索エンジンの結果リストの上位に表示される（ランキングが高い）ほど有用性が高い。
非常に関連性の高い文書は、関連性がやや低い文書よりも有用であり、関連性がやや低い文書は、関連性のない文書よりも有用である。

累積利益

DCGは、より単純な指標である累積ゲイン（CG）を改良したものです。^{[ 3 ]}累積ゲインは、検索結果リスト内のすべての結果の関連度評価値の合計です。CGは、結果リスト内の結果のランク（位置）を考慮しません。特定のランク位置でのCGは、 $p$ は次のように定義されます。

\mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}

どこ $rel_i$ 位置における結果の段階的関連性 $i$ 。

CG関数で計算された値は、検索結果の順序変更の影響を受けません。つまり、関連性の高いドキュメントを移動しても、値は変わりません。 $d_i$ 上位の、関連性の低い文書 $d_j$ CG の計算値は変更されません ( $i,j\leq p$ ）。検索結果の有用性に関する上記の2つの仮定に基づくと、(N)DCGは通常CGよりも好まれます。累積利得は、段階的精度と呼ばれることもあります。

割引累積利益

DCGの前提は、検索結果リストの下位に表示されるほど関連性の高い文書はペナルティを受けるべきであり、関連性の度合いを示す値は結果の順位に比例して対数的に減少するというものである。

特定の順位で蓄積されたDCGの通常の計算式 $p$ は次のように定義されます。^{[ 4 ]}

\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年までは、滑らかな減少をもたらすという事実以外に、対数減少係数^{[ 5 ]}を使用する理論的に妥当な根拠はなかった。しかし、Wangら（2013） ^{[ 3 ]は}、正規化DCG（NDCG）で対数減少係数を使用することの理論的保証を与えた。著者らは、実質的に異なるランキング関数の任意のペアに対して、NDCGが一貫した方法でどちらが優れているかを決定できることを示した。

^{DCG [ 6 ]}の別の定式化では、関連文書の取得に重点が置かれています。

\mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}

後者の式は、大手ウェブ検索企業^{[ 7 ]}やKaggleなどのデータサイエンスコンペティションプラットフォーム^{[ 8 ]を含む産業用途で一般的に使用されています。}

文書の関連性値がバイナリの場合、これら2つのDCGの定式化は同じである。^{[ 5 ]}^{： 320} $rel_{i}\in \{0,1\}$ 。

Croft et al. (2010) と Burges et al. (2005) は、底が e の対数を用いた 2 番目の DCG を示していますが、上記の 2 つのバージョンの DCG はどちらも底が 2 の対数を使用しています。最初の DCG の定式化で NDCG を計算する場合、対数の底は関係ありませんが、2 番目の定式化では対数の底が NDCG の値に影響します。明らかに、対数の底はどちらの定式化でも DCG の値に影響します。

勾配ベースの学習方法における目的関数として使用するために、DCGの凸型および滑らかな近似も開発されている。^{[ 9 ]}

正規化DCG

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

\mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}

、

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

\mathrm {IDCG_{p}} =\sum _{i=1}^{|REL_{p}|}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}

そして $REL_{p}$ これは、コーパス内の p の位置までの関連文書のリスト (関連性の順に並べられています) を表します。

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

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

例

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

D_{1},D_{2},D_{3},D_{4},D_{5},D_{6}

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

3,2,3,0,1,2

つまり、文書1の関連性は3、文書2の関連性は2、といった具合です。この検索結果リストの累積ゲインは次のとおりです。

\mathrm {CG_{6}} =\sum _{i=1}^{6}rel_{i}=3+2+3+0+1+2=11

2つの文書の順序を変更しても、CG の測定値には影響しません。 $D_{3}$ そして $D_{4}$ が入れ替わっても、CGは同じままです。11. DCGは、結果リストの早い段階で表示される関連性の高い文書を強調するために使用されます。対数スケールを使用して削減すると、各結果のDCGは次のようになります。

だから $DCG_{6}$ このランキングの上位項目は以下のとおりです。

\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

スイッチ $D_{3}$ そして $D_{4}$ その結果、関連性の低い文書がランキングの上位に配置されるため、DCGが低下します。つまり、より関連性の高い文書は、低いランクに配置されることで、より大きく軽視されることになります。

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

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

3,3,3,2,2,2,1,0

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

3,3,3,2,2,2

この理想的な順序付けのDCG、すなわちIDCG（理想DCG）は、ランク6と計算される。

\mathrm {IDCG_{6}} =8.740

したがって、このクエリに対するnDCGは次のようになります。

\mathrm {nDCG_{6}} ={\frac {DCG_{6}}{IDCG_{6}}}={\frac {6.861}{8.740}}=0.785

制限事項

正規化DCGは、結果に不良文書が含まれていてもペナルティを与えません。たとえば、クエリがそれぞれスコア $1,1,1$ と $1,1,1,0$ の2つの結果を返した場合、後者に不良文書が含まれていても、両方とも同等に良いとみなされます。Excellent $、Fair、Badのランキング判定には、$ $2,1,0の$ 代わりに数値スコア $1,0,-1を$ 使用することもできます。これにより、不良な結果が返された場合にスコアが低下し、再現率よりも結果の精度が優先されます。ただし、このアプローチでは、全体的なスコアがマイナスになる可能性があります。
正規化 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 と表記します。
正規化DCGは、同等に優れた結果が複数存在するクエリのパフォーマンスを測定するのに適さない場合があります。これは、この指標が最初の数件の結果のみに限定されている場合に特に当てはまります。実際、このような制限はよく行われます。たとえば、「レストラン」のようなクエリの場合、nDCG@1は最初の結果のみを考慮します。ある結果セットには近隣地域のレストランが1件しか含まれておらず、別の結果セットには5件含まれている場合、後者の方がより包括的な結果であるにもかかわらず、両者のスコアは同じになってしまいます。

参考文献

↑カレルヴォのヤルヴェリン。ケカライネン、ヤーナ (2000)。「関連性の高い文書を検索するためのIR評価手法」シギル。 ACM: 41–48 .土井: 10.1145/345508.345545。ISBN 978-1-58113-226-7。
↑カレルヴォのヤルヴェリン。ケカライネン、ヤーナ (2002)。「IR技術の累積ゲインベース評価」。情報システム上の ACM トランザクション。20 (4): 422–446 .土井: 10.1145/582415.582418。ISSN 1046-8188。
1 2 Yining Wang、Liwei Wang、Yuanzhi Li、Di He、Wei Chen、 Tie-Yan Liu。2013。正規化割引累積利得（NDCG）ランキング尺度の理論的分析。第26回学習理論年次会議（COLT 2013）議事録。
↑ Kalervo Järvelin、Jaana Kekäläinen、「IR 技術の累積ゲインベース評価」。情報システムに関する ACM トランザクション20 (4)、422–446 (2002)
1 2 B. Croft; D. Metzler; T. Strohman (2010). Search Engines: Information Retrieval in Practice . Addison Wesley.
↑ 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
↑ 「情報検索入門 - 評価」(PDF)。スタンフォード大学。2013年4月21日。 2014年3月23日取得。
↑ 「正規化された割引累積利益」。2014年3月23日にオリジナルからアーカイブされました。2014年3月23日に取得。
↑ D. Cossock および T. Zhang、「ベイズ最適部分集合ランキングの統計分析」、 IEEE Transactions on Information Theory、第 54 巻、第 11 号、pp. 5140-5154、2008 年 11 月、doi: 10.1109/TIT.2008.929939。

[1] カレルヴォのヤルヴェリン。ケカライネン、ヤーナ (2000)。「関連性の高い文書を検索するためのIR評価手法」シギル。 ACM: 41–48 .土井: 10.1145/345508.345545。ISBN 978-1-58113-226-7。

[2] カレルヴォのヤルヴェリン。ケカライネン、ヤーナ (2002)。「IR技術の累積ゲインベース評価」。情報システム上の ACM トランザクション。20 (4): 422–446 .土井: 10.1145/582415.582418。ISSN 1046-8188。

[:0-3] 1 2 Yining Wang、Liwei Wang、Yuanzhi Li、Di He、Wei Chen、 Tie-Yan Liu。2013。正規化割引累積利得（NDCG）ランキング尺度の理論的分析。第26回学習理論年次会議（COLT 2013）議事録。

[jarvelin_2002_cumulated-4] Kalervo Järvelin、Jaana Kekäläinen、「IR 技術の累積ゲインベース評価」。情報システムに関する ACM トランザクション20 (4)、422–446 (2002)

[CMS2009-5] 1 2 B. Croft; D. Metzler; T. Strohman (2010). Search Engines: Information Retrieval in Practice . Addison Wesley.

[6] 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

[stanfordireval-7] 「情報検索入門 - 評価」(PDF)。スタンフォード大学。2013年4月21日。 2014年3月23日取得。

[8] 「正規化された割引累積利益」。2014年3月23日にオリジナルからアーカイブされました。2014年3月23日に取得。

[9] D. Cossock および T. Zhang、「ベイズ最適部分集合ランキングの統計分析」、 IEEE Transactions on Information Theory、第 54 巻、第 11 号、pp. 5140-5154、2008 年 11 月、doi: 10.1109/TIT.2008.929939。

[ 1 ]

[ 2 ]

[ 4 ]

[ 5 ]

DCG [ 6 ]

[ 7 ]

[ 8 ]を含む産業用途で一般的に使用されています。

[ 9 ]

割引累積利益

概要

累積利益

割引累積利益

正規化DCG

例

制限事項

関連項目

参考文献

関連するトピック

は、情報検索

検索エンジンの

アルゴリズム

関連性の段階的尺度を使用して、DCG は、結果リスト内の位置によって割引された結果の有用性、つまり