Дисконтированная совокупная прибыль

Дисконтированный совокупный выигрыш ( DCG ) является мерой качества ранжирования при поиске информации . Его часто нормализуют, чтобы его можно было сравнивать по запросам, что дает нормализованный DCG (nDCG или NDCG) . NDCG часто используется для измерения эффективности поисковых систем алгоритмов и связанных с ними приложений. Используя градуированную шкалу релевантности документов в наборе результатов поисковой системы, DCG суммирует полезность или выгоду от результатов, дисконтированных по их положению в списке результатов. NDCG — это DCG, нормализованный по максимально возможному DCG набора результатов при ранжировании от наибольшего к наименьшему коэффициенту усиления, что обеспечивает поправку на различное количество релевантных результатов для разных запросов.

Обзор

При использовании DCG и связанных с ним показателей сделаны два предположения.

1. Высокорелевантные документы более полезны, если появляются раньше в списке результатов поисковой системы (имеют более высокий рейтинг).
2. Высокорелевантные документы более полезны, чем малорелевантные документы, которые, в свою очередь, более полезны, чем нерелевантные документы.

Совокупный выигрыш

DCG — это усовершенствованная версия более простой меры — совокупного прироста (CG). Совокупный прирост — это сумма градуированных значений релевантности всех результатов в списке результатов поиска. CG не учитывает ранг (позицию) результата в списке результатов. CG на определенной позиции ранга $p$ определяется как:

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

Где $rel_{i}$ - это градация релевантности результата в позиции $i$.

На значение, вычисленное с помощью функции CG, не влияют изменения порядка результатов поиска. То есть перемещение весьма актуального документа $d_{i}$ выше более высокого ранга, менее релевантного документа $d_{j}$ не меняет вычисленное значение ЦТ (при условии, что $i,j\leq p$). На основании двух сделанных выше предположений о полезности результатов поиска, (N)DCG обычно предпочтительнее CG. Совокупное усиление иногда называют ступенчатой ​​точностью.

Дисконтированная совокупная прибыль

Идея DCG заключается в том, что высокорелевантные документы, находящиеся ниже в списке результатов поиска, должны подвергаться штрафам, поскольку значение градационной релевантности уменьшается логарифмически пропорционально положению результата.

Обычная формула DCG, накопленного на определенной ранговой позиции. $p$ определяется как:

$\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 года не было теоретически обоснованного обоснования использования логарифмического коэффициента приведения. кроме того факта, что он обеспечивает плавное сокращение. Но Ван и др. (2013) дал теоретическую гарантию использования логарифмического коэффициента приведения в нормализованной DCG (NDCG). Авторы показывают, что для каждой пары существенно различных функций ранжирования NDCG может последовательно решить, какая из них лучше.

Альтернативная формулировка DCG уделяет больше внимания поиску соответствующих документов:

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

Последняя формула обычно используется в промышленных приложениях, включая крупные поисковые компании в Интернете. и платформы для соревнований по науке о данных, такие как Kaggle.

Эти две формулировки DCG одинаковы, когда значения релевантности документов являются двоичными ; $rel_{i}\in \{0,1\}$.

Обратите внимание, что Крофт и др. (2010) и Берджес и др. (2005) представили второй DCG с логарифмом по базе e, в то время как обе версии DCG, приведенные выше, используют логарифм по основанию 2. При вычислении NDCG с первой формулировкой DCG база логарифма не имеет значения, но база журнал действительно влияет на значение NDCG для второй формулировки. Очевидно, что база журнала влияет на значение DCG в обеих формулировках.

Также были разработаны выпуклые и гладкие аппроксимации DCG для использования в качестве целевой функции в методах обучения на основе градиента.

Нормализованный DCG

Списки результатов поиска различаются по длине в зависимости от запроса . Сравнение производительности поисковой системы от одного запроса к другому не может быть последовательно достигнуто с использованием только DCG, поэтому совокупный прирост на каждой позиции для выбранного значения $p$ должны быть нормализованы по запросам. Это делается путем сортировки всех соответствующих документов в корпусе по их относительной релевантности, создавая максимально возможную DCG по позиции. $p$, также называемый Ideal 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$

Изменение порядка любых двух документов не влияет на показатель CG. Если $D_{3}$ и $D_{4}$ переключаются, CG остается прежним, 11. DCG используется для выделения наиболее релевантных документов, появляющихся в начале списка результатов. Используя логарифмическую шкалу приведения, DCG для каждого результата по порядку составит:

$i$	$rel_{i}$	$\log _{2}(i+1)$	${\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

Итак, $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, необходим идеальный порядок для данного запроса. В данном примере такой порядок будет представлять собой монотонно убывающую разновидность всех известных суждений о релевантности. Предположим, что помимо шести из этого эксперимента мы также знаем, что существует документ $D_{7}$ с релевантностью 3 к тому же запросу и документу $D_{8}$ со степенью релевантности 2 для этого запроса. Тогда идеальный порядок:

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

Идеальный рейтинг снова сокращается до длины 6, чтобы соответствовать глубине анализа рейтинга:

$3,3,3,2,2,2$

DCG этого идеального порядка, или IDCG (Ideal DCG) , вычисляется до ранга 6:

$\mathrm {IDCG_{6}} =8.740$

Итак, nDCG для этого запроса задается как:

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

Ограничения

1. Нормализованный DCG не наказывает за наличие в результате неверных документов. Например, если запрос возвращает два результата с оценками 1,1,1 и 1,1,1,0 соответственно, оба будут считаться одинаково хорошими, даже если последний содержит плохой документ. Для рейтинговых оценок «Отлично», «Удовлетворительно», «Плохо » можно использовать числовые оценки 1,0,-1 вместо 2,1,0 . Это приведет к снижению оценки в случае возврата плохих результатов, при этом точность результатов будет отдаваться приоритету над отзывом; однако этот подход может привести к получению общей отрицательной оценки.
2. Нормализованный DCG не наказывает недостающие документы в результате. Например, если запрос возвращает два результата с оценками 1,1,1 и 1,1,1,1,1 соответственно, оба будут считаться одинаково хорошими, при условии, что идеальный DCG рассчитан до ранга 3 для первого и ранга 5 для последний. Один из способов принять во внимание это ограничение — установить фиксированный размер набора результатов и использовать минимальные оценки для отсутствующих документов. В предыдущем примере мы бы использовали оценки 1,1,1,0,0 и 1,1,1,1,1 и обозначили nDCG как nDCG@5.
3. Нормализованный DCG может оказаться непригодным для измерения производительности запросов, которые могут иметь несколько одинаково хороших результатов. Это особенно верно, когда эта метрика ограничивается только несколькими первыми результатами, как это часто бывает на практике. Например, для таких запросов, как «рестораны», nDCG@1 учитывает только первый результат. Если один набор результатов содержит только 1 ресторан из близлежащего района, а другой — 5, оба в конечном итоге получат одинаковую оценку, даже если последний является более полным.

См. также

• Меры оценки (поиск информации)
• Учимся ранжировать