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

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

Обзор

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

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

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

Совокупный прирост

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

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

Где ${displaystyle rel_{i}}$ оценка релевантности результата на позиции ${displaystyle i}$.

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

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

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

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

Традиционная формула DCG, накопленная на определенной позиции ранга ${displaystyle p}$ определяется как:^[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)}}}$

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

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

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

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

Эти две формулировки DCG одинаковы, когда значения релевантности документов двоичный;^[2]:320 ${displaystyle rel_{i}in {0,1}}$.

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

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

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

${displaystyle mathrm {nDCG_{p}} ={frac {DCG_{p}}{IDCG_{p}}}}$,

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

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

и ${displaystyle REL_{p}}$ представляет собой список релевантных документов (упорядоченный по их релевантности) в корпусе до позиции p.

Значения nDCG для всех запросов можно усреднить, чтобы получить меру средней производительности алгоритма ранжирования поисковой системы. Обратите внимание, что в идеальном алгоритме ранжирования ${displaystyle DCG_{p}}$ будет таким же, как ${displaystyle IDCG_{p}}$ производя nDCG 1.0. Тогда все вычисления nDCG являются относительными значениями в интервале от 0,0 до 1,0 и, таким образом, сопоставимы с перекрестными запросами.

Основная трудность, возникающая при использовании nDCG, - это отсутствие идеального упорядочивания результатов, когда только частичное обратная связь по релевантности доступен.

Пример

Участнику эксперимента, представленному в виде списка документов в ответ на поисковый запрос, предлагается оценить релевантность каждого документа запросу. Каждый документ оценивается по шкале от 0 до 3, где 0 означает нерелевантность, 3 означает высокую актуальность, а 1 и 2 означают «где-то посередине». Для документов, упорядоченных алгоритмом ранжирования как

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

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

${displaystyle 3,2,3,0,1,2}$

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

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

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

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

Итак ${displaystyle DCG_{6}}$ в этом рейтинге:

${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}$

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

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

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

${displaystyle 3,3,3,2,2,2,1,0}$

Без D7 и D8 идеальный порядок:

${displaystyle 3,3,2,2,1,0}$

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

${displaystyle mathrm {IDCG_{6}} =7.141}$

Таким образом, nDCG для этого запроса имеет следующий вид:

${displaystyle mathrm {nDCG_{6}} ={frac {DCG_{6}}{IDCG_{6}}}={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, оба получат одинаковую оценку, даже если последнее является более полным.

Смотрите также

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

Рекомендации

1. Калерво Ярвелин, Яана Кекяляйнен: Совокупная оценка IR методов на основе усиления. Транзакции ACM по информационным системам 20 (4), 422–446 (2002)
2. Б. Крофт; Д. Метцлер; Т. Строман (2010). Поисковые системы: поиск информации на практике. Эддисон Уэсли.
3. Инин Ван, Ливэй Ван, Юаньчжи Ли, Ди Хэ, Вэй Чен, Тие-Янь Лю. 2013. Теоретический анализ показателей ранжирования нормализованной дисконтированной совокупной прибыли (NDCG). В материалах 26-й ежегодной конференции по теории обучения (COLT 2013).
4. Крис Берджес, Тал Шакед, Эрин Реншоу, Ари Лазье, Мэтт Дидс, Николь Гамильтон и Грег Халлендер. 2005. Обучение ранжированию с помощью градиентного спуска. В материалах 22-й международной конференции по машинному обучению (ICML '05). ACM, Нью-Йорк, Нью-Йорк, США, 89-96. DOI = 10.1145 / 1102351.1102363 http://doi.acm.org/10.1145/1102351.1102363
5. «Введение в поиск информации - оценка» (PDF). Стэндфордский Университет. 21 апреля 2013 г.. Получено 23 марта 2014.
6. «Нормализованная дисконтированная совокупная прибыль». Архивировано из оригинал 23 марта 2014 г.. Получено 23 марта 2014.