Как сравнить два алгоритма ранжирования?

Я хочу сравнить два алгоритма ранжирования. В этих алгоритмах клиент указывает некоторые условия в своем поиске. В соответствии с требованиями клиента, этот алгоритм должен назначать оценку для каждого элемента в базе данных и извлекать элементы с наивысшими оценками.

Я прочитал различные темы, связанные с моим вопросом на этом сайте, и искал в сети. Согласно моим поискам, наиболее релевантная статья, в которой объясняются некоторые метрики для сравнения алгоритмов ранжирования, была такова : Брайан Макфи и Герт Р.Г. Ланкриет, «Метрика обучения рангу», ICML 2010 ( https://bmcfee.github.io/papers/mlr .pdf ). Я думаю, что prec @ k, MAP, MRR и NDCG - хорошие показатели для использования, но у меня есть проблема:

Мой алгоритм сортирует результаты, поэтому первый элемент в моем списке результатов является лучшим с самым высоким показателем, второй результат имеет второй лучший результат и так далее. Я ограничиваю свой алгоритм поиска, например, чтобы найти 5 лучших результатов. Результаты - самые лучшие 5 пунктов. Таким образом, точность будет равна 1. Когда я ограничиваю свой поиск, чтобы найти лучший результат, он находит лучший. Опять же, точность будет 1. Но проблема в том, что это неприемлемо для людей, которые видят этот результат.

Что я могу сделать? Как я могу сравнить эти алгоритмы и показать, что один лучше другого?

Ответы:

Discount Cumulative Gain (DCG) является одним из самых популярных показателей, используемых для оценки рейтинга любой поисковой системой. Это показатель качества рейтинга. В поиске информации, он часто используется для измерения эффективности поисковой системы в Интернете.

Он основан на следующих предположениях:

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

Формула для DCG выглядит следующим образом:

\begin{matrix} (1) & D C G_{p} = \sum_{i = 1}^{p} \frac{r e l_{i}}{l o g_{2} (i + 1)} = r e l_{1} + \sum_{i = 2}^{p} \frac{r e l_{i}}{l o g_{2} (i + 1)} \end{matrix}

$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)} \tag{1}$

Куда:

i - это возвращаемая позиция документа в результатах поиска.
$rel_i$ - ступенчатая релевантность документа
суммирование по p (количество возвращаемых результатов), следовательно, накопленный совокупный выигрыш дает показатели производительности возвращаемого результата.

DCG является производным от CG (Cumulative Gain) , определяемой как:

\begin{matrix} (2) & C G_{p} = \sum_{i = 1}^{p} r e l_{i} \end{matrix}

$CG_p = \sum_{i=1}^p rel_i \tag{2}$

Из (2) видно, что не изменяется при изменении порядка результатов. Таким образом, чтобы преодолеть эту проблему, была введена DCG. Существует другая форма DCG, которая популярна тем, что уделяет большое внимание поиску документов. Эта версия DCG предоставляется: $CG_p$

\begin{matrix} (3) & D C G_{p} = \sum_{i = 1}^{p} \frac{2^{r e l_{i}} - 1}{l o g_{2} (i + 1)} \end{matrix}

$DCG_p = \sum_{i=1}^p \frac {2^{rel_i} - 1} {log_2 (i+1)} \tag{3}$

Один очевидный недостаток уравнения DCG, представленного в (1) и (3), состоит в том, что алгоритмы, возвращающие различное количество результатов, не могут быть эффективно сопоставлены. Это связано с тем, что чем выше значение тем выше значение . $p$ $DCG_p$

Чтобы преодолеть эту проблему, предлагается нормализованная DCG (nDCG) . Это дано,

n D C G_{p} = \frac{D C G_{p}}{I D C G_{p}}

$nDCG_p = \frac {DCG_p} {IDCG_p}$

где - идеальный , заданный $IDCG_p$ $DCG_p$

I D C G_{p} = \sum_{i = 1}^{| R E L |} \frac{2^{r e l_{i}} - 1}{l o g_{2} (i + 1)}

$IDCG_p = \sum_{i=1}^{|REL|} \frac {2^{rel_i} - 1} {log_2 (i+1)}$

Где | REL | список документов, упорядоченных по релевантности в корпусе до позиции с.

Для идеального алгоритма ранжирования,

D C G_{p} = I D C G_{p}

$DCG_p = IDCG_p$

Поскольку значения nDCG масштабируются в пределах диапазона [0,1], сравнение этих запросов возможно с использованием этих показателей.

Недостатки: 1. nDCG не штрафует за поиск плохих документов в результате. Это можно исправить путем корректировки значений релевантности, приписываемых документам. 2. nDCG не штрафует недостающие документы. Это можно исправить, установив размер поиска и используя минимальный балл для отсутствующих документов.

Обратитесь к этому, чтобы увидеть пример расчета nDCG.

Ссылка

m1cro1ce
источник

Полезные ресурсы:

http://www.cs.utexas.edu/~mooney/ir-course/slides/Evaluation.ppt
http://www.nii.ac.jp/TechReports/05-014E.pdf
http://www.stanford.edu/class/cs276/handouts/EvaluationNew-handout-6-per.pdf
http://hal.archives-ouvertes.fr/docs/00/72/67/60/PDF/07-busa-fekete.pdf
Обучение рангу для поиска информации (Tie-Yan Liu)

Renaud
источник