Накопленная прибыль со скидкой

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

• 1 Обзор
  • 1.1 Суммарный прирост
  • 1.2 Дисконтированный совокупный прирост
  • 1.3 Нормализованный DCG
• 2 Пример
• 3 Ограничения
• 4 См. Также
• 5 Ссылки

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

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

DCG берет свое начало от более ранней, более примитивной меры, называемой совокупным усилением.

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

Совокупный выигрыш (CG) - это сумма оцененных значений релевантности всех результатов в списке результатов поиска. Этот предшественник DCG не учитывает ранг (положение) результата в списке результатов при рассмотрении полезности набора результатов. CG на определенной позиции ранга $p\; \{\backslash \; displaystyle\; p\}$определяется как:

$CG\; p\; =\; \sum \; i\; =\; 1\; preli\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{CG\_\; \{p\}\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{p\}\; rel\_\; \{i\}\}$

Где $reli\; \{\backslash \; displaystyle\; rel\_\; \{i\}\}$- это оцененная релевантность результата в позиции $i\; \{\backslash \; displaystyle\; i\}$.

На значение, вычисленное с помощью функции CG, не влияют изменения в порядке результатов поиска. То есть перемещение высокорелевантного документа $di\; \{\backslash \; displaystyle\; d\_\; \{i\}\}$выше более ранжированного, менее релевантного документа $dj\; \{\backslash \; displaystyle\; d\_\; \{j\}\}$не изменяет вычисленное значение для CG (при условии, что $i,\; j\; \le \; p\; \{\backslash \; displaystyle\; i,\; j\; \backslash \; leq\; p\}$). Основываясь на двух сделанных выше предположениях о полезности результатов поиска, (N) DCG обычно предпочтительнее CG.

Совокупный прирост иногда называют оцененной точностью, поскольку он идентичен метрике точности, если шкала оценок является двоичной.

Дисконтированный совокупный выигрыш

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

Традиционная формула DCG, накопленная на определенной позиции ранга $p\; \{\backslash \; displaystyle\; p\}$, определяется как:

$DCG\; p\; =\; \sum \; i\; =\; 1\; preli\; log\; 2\; \; (я\; +\; 1)\; знак\; равно\; отн\; 1\; +\; \sum \; я\; знак\; равно\; 2\; журнал\; 2\; \; (я\; +\; 1)\; \{\backslash \; Displaystyle\; \backslash \; mathrm\; \{DCG\_\; \{p\}\}\; =\; \backslash \; сумма\; \_\; \{я\; =\; 1\}\; ^\; \{p\}\; \{\backslash \; гидроразрыва\; \{\; rel\_\; \{i\}\}\; \{\backslash \; log\; \_\; \{2\}\; (i\; +\; 1)\}\}\; =\; rel\_\; \{1\}\; +\; \backslash \; sum\; \_\; \{i\; =\; 2\}\; ^\; \{p\}\; \{\backslash \; frac\; \{rel\_\; \{i\}\}\; \{\backslash \; log\; \_\; \{2\}\; (i\; +\; 1)\}\}\}$

Ранее не было теоретически обоснованного обоснования для использования коэффициента уменьшения логарифмического, кроме того факта, что он обеспечивает плавное уменьшение. Но Ван и др. (2013) дают теоретическую гарантию использования коэффициента логарифмического сокращения в нормализованном DCG (NDCG). Авторы показывают, что для каждой пары существенно различных функций ранжирования NDCG может согласованно решать, какая из них лучше.

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

$DCG\; p\; =\; \sum \; i\; =\; 1\; p\; 2\; reli\; -\; 1\; log\; 2\; \; (i\; +\; 1)\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{DCG\_\; \{\; p\}\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{p\}\; \{\backslash \; frac\; \{2\; ^\; \{rel\_\; \{i\}\}\; -\; 1\}\; \{\backslash \; log\; \_\; \{2\}\; (i\; +\; 1)\}\}\}$

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

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

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

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

Списки результатов поиска различаются по длине в зависимости от запроса. Сравнивать производительность поисковой системы от одного запроса к другому невозможно, используя только DCG, поэтому совокупный выигрыш в каждой позиции для выбранного значения $p\; \{\backslash \; displaystyle\; p\}$должен быть нормализован по запросы. Это выполняется путем сортировки всех релевантных документов в корпусе по их относительной релевантности с получением максимально возможного DCG через позицию $p\; \{\backslash \; displaystyle\; p\}$, также называемую Ideal DCG ( IDCG) через эту должность. Для запроса нормализованная дисконтированная совокупная выгода, или nDCG, вычисляется как:

$n\; DCG\; p\; =\; DCG\; p\; IDCG\; p\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{nDCG\_\; \{p\}\}\; =\; \{\backslash \; frac\; \{DCG\_\; \{p\}\}\; \{\; IDCG\_\; \{p\}\}\}\}$,

где IDCG - идеальная дисконтированная совокупная прибыль,

$IDCG\; p\; =\; \sum \; i\; =\; 1\; |\; R\; E\; L\; p\; |\; 2\; reli\; -\; 1\; журнал\; 2\; \; (я\; +\; 1)\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{IDCG\_\; \{p\}\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{|\; REL\_\; \{p\}\; |\}\; \{\backslash \; frac\; \{2\; ^\; \{rel\_\; \{\; i\}\}\; -\; 1\}\; \{\backslash \; log\; \_\; \{2\}\; (i\; +\; 1)\}\}\}$

и $REL\; p\; \{\backslash \; displaystyle\; REL\_\; \{p\}\}$представляет список соответствующих документов (упорядочены по релевантности) в корпусе до позиции p.

Значения nDCG для всех запросов можно усреднить, чтобы получить меру средней производительности алгоритма ранжирования поисковой системы. Обратите внимание, что в идеальном алгоритме ранжирования $DCG\; p\; \{\backslash \; displaystyle\; DCG\_\; \{p\}\}$будет таким же, как $IDCG\; p\; \{\backslash \; displaystyle\; 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\; \{\backslash \; displaystyle\; D\_\; \{1\},\; D\_\; \{2\},\; D\_\; \{3\},\; D\_\; \{4\; \},\; D\_\; \{5\},\; D\_\; \{6\}\}$

пользователь предоставляет следующие оценки релевантности:

$3,\; 2,\; 3,\; 0,\; 1,\; 2\; \{\backslash \; displaystyle\; 3,2,3,0,1,\; 2\}$

То есть: документ 1 имеет релевантность 3, документ 2 имеет релевантность 2 и т. Д. Совокупный выигрыш этого списка результатов поиска составляет:

$CG\; 6\; =\; \sum \; i\; =\; 1\; 6\; reli\; =\; 3\; +\; 2\; +\; 3\; +\; 0\; +\; 1\; +\; 2\; =\; 11\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{CG\_\; \{6\}\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{6\}\; rel\_\; \{i\}\; =\; 3\; +\; 2\; +\; 3\; +\; 0\; +\; 1\; +\; 2\; =\; 11\}$

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

.

$i\; \{\backslash \; displaystyle\; i\}$	$reli\; \{\backslash \; displaystyle\; rel\_\; \{i\}\}$	$log\; 2\; \; (i\; +\; 1)\; \{\backslash \; displaystyle\; \backslash \; log\; \_\; \{2\}\; (я\; +\; 1)\}$	$reli\; log\; 2\; \; (я\; +\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{rel\_\; \{i\}\}\; \{\backslash \; log\; \_\; \{2\}\; (я\; +\; 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\; \{\backslash \; displaystyle\; DCG\_\; \{6\}\}$из этого рейтинга:

$DCG\; 6\; =\; \sum \; i\; =\; 1\; 6\; reli\; log\; 2\; \; (i\; +\; 1)\; =\; 3\; +\; 1.262\; +\; 1.5\; +\; 0\; +\; 0,387\; +\; 0,712\; =\; 6,861\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{DCG\_\; \{6\}\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{6\}\; \{\backslash \; frac\; \{rel\_\; \{i\}\}\; \{\backslash \; log\; \_\; \{2\}\; (i\; +\; 1)\}\}\; =\; 3\; +\; 1,262\; +\; 1,5\; +\; 0\; +\; 0,387\; +\; 0,712\; =\; 6,861\}$

Теперь переключение $D\; 3\; \{\backslash \; displaystyle\; D\_\; \{3\}\}$и $D\; 4\; \{\backslash \; displaystyle\; D\_\; \{4\}\}$приводит к сокращению DCG, поскольку менее релевантный документ занимает более высокое место в рейтинге; то есть более релевантный документ больше обесценивается, будучи помещенным в более низкий ранг.

Производительность этого запроса с другим запросом несопоставима в этой форме, поскольку другой запрос может иметь больше результатов, что приводит к большему общему DCG, который не обязательно может быть лучше. Для сравнения значения DCG должны быть нормализованы.

Чтобы нормализовать значения DCG, необходим идеальный порядок для данного запроса. В этом примере это упорядочение будет представлять собой монотонно убывающий вид всех известных оценок релевантности. В дополнение к шести из этого эксперимента, предположим, мы также знаем, что существует документ $D\; 7\; \{\backslash \; displaystyle\; D\_\; \{7\}\}$с 3-й степенью релевантности для того же запроса и документ $D\; 8\; \{\backslash \; displaystyle\; D\_\; \{8\}\}$со степенью релевантности 2 этому запросу. Тогда идеальный порядок следующий:

$3,\; 3,\; 3,\; 2,\; 2,\; 2,\; 1,\; 0\; \{\backslash \; displaystyle\; 3,3,3,2,2,2,1,0\}$

Без D7 и D8, идеальный порядок следующий:

$3,\; 3,\; 2,\; 2,\; 1,\; 0\; \{\backslash \; displaystyle\; 3,3,2,2,1,0\}$

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

$IDCG\; 6\; =\; 7.141\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{IDCG\_\; \{6\}\}\; =\; 7.141\}$

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

$n\; DCG\; 6\; =\; DCG\; 6\; IDCG\; 6\; =\; 6,861\; 7,141\; =\; 0,961\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{nDCG\_\; \{6\}\}\; =\; \{\backslash \; frac\; \{DCG\_\; \{6\}\}\; \{IDCG\_\; \{6\}\}\}\; =\; \{\backslash \; frac\; \{6.861\}\; \{7.141\}\}\; =\; 0,961\}$

1. Нормализованная метрика DCG не наказывает за плохие документы в результате. Например, если запрос возвращает два результата с оценками 1,1,1 и 1,1,1,0 соответственно, оба будут считаться одинаково хорошими, даже если последний содержит плохой документ. Для рейтинговых оценок «Отлично», «Удовлетворительно», «Плохо» можно использовать числовые баллы 1,0, -1 вместо 2,1,0. Это приведет к снижению оценки, если будут возвращены плохие результаты, при этом точность результатов будет важнее отзыва. Обратите внимание, что этот подход может привести к общей отрицательной оценке, которая сместит нижнюю границу оценки с 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, оба будут иметь одинаковую оценку, даже если последний является более полным.

• Меры оценки (поиск информации)
• Обучение ранжированию