Jak porównać dwa algorytmy rankingu?

12

Chcę porównać dwa algorytmy rankingu. W tych algorytmach klient określa pewne warunki w swoim wyszukiwaniu. Zgodnie z wymaganiami klienta, algorytm ten powinien przypisać ocenę każdemu elementowi w bazie danych i pobrać elementy o najwyższym wyniku.

Na tej stronie przeczytałem różne tematy związane z moim pytaniem i przeszukałem sieć. Według moich wyszukiwań najbardziej odpowiednim artykułem wyjaśniającym niektóre metryki do porównywania algorytmów rankingowych były: Brian McFee i Gert RG Lanckriet, Metric Learning to Rank, ICML 2010 ( https://bmcfee.github.io/papers/mlr .pdf ). Myślę, że prec @ k, MAP, MRR i NDCG są dobrymi miernikami do użycia, ale mam problem:

Mój algorytm sortuje wyniki, więc pierwszy element na mojej liście wyników jest najlepszy z najwyższym wynikiem, drugi wynik ma drugi najwyższy wynik i tak dalej. Ograniczam mój algorytm wyszukiwania do, na przykład, znalezienia 5 najlepszych wyników. Wyniki to 5 najlepszych pozycji. Tak więc precyzja będzie wynosić 1. Gdy ograniczę wyszukiwanie, aby znaleźć najlepszy wynik, znajdzie najlepszy. Znów precyzja będzie wynosić 1. Ale problemem jest to, że jest nie do przyjęcia dla osób, które widzą ten wynik.

Co mogę zrobić? Jak mogę porównać te algorytmy i pokazać, że jeden jest lepszy od drugiego?

6

Zdyskontowany zysk skumulowany (DCG) jest jednym z najpopularniejszych wskaźników wykorzystywanych do oceny rankingu w dowolnej wyszukiwarce. Jest to miara jakości rankingu. Podczas wyszukiwania informacji jest często używany do pomiaru skuteczności wyszukiwarki internetowej.

Opiera się na następujących założeniach:

Bardzo trafne dokumenty są bardziej przydatne, jeśli pojawiają się wcześniej w wynikach wyszukiwania.
Dokumenty o dużym znaczeniu są bardziej przydatne niż dokumenty o marginalnym znaczeniu, które są lepsze niż dokumenty nieistotne.

Wzór na DCG wygląda następująco:

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

Gdzie:

i jest zwróconą pozycją dokumentu w wyniku wyszukiwania.
$rel_i$ to stopniowane znaczenie dokumentu
sumowanie przez p (liczbę zwróconych wyników), zatem skumulowany skumulowany zysk daje miary wydajności zwróconego wyniku.

DCG pochodzi od CG (Skumulowany zysk) , otrzymany przez:

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

Z (2) widać, że nie zmienia się w przypadku zmiany kolejności wyników. Aby rozwiązać ten problem, wprowadzono DCG. Istnieje inna forma DCG, która jest popularna ze względu na bardzo duży nacisk na odzyskiwanie dokumentów. Ta wersja DCG jest dostarczana przez: $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}$

Jedną oczywistą wadą równania DCG przedstawionego w (1) i (3) jest to, że algorytmy zwracające inną liczbę wyników nie mogą być skutecznie porównywane. Jest tak, ponieważ im wyższa wartość tym wyższa wartość zostanie przeskalowana do. $p$ $DCG_p$

Aby rozwiązać ten problem, proponuje się znormalizowany DCG (nDCG) . Daje to

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

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

gdzie jest idealnym , podanym przez, $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)}$

Gdzie | REL | to lista dokumentów uporządkowanych według istotności w korpusie do pozycji p.

Aby uzyskać idealny algorytm rankingu,

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

$DCG_p = IDCG_p$

Ponieważ wartości nDCG są skalowane w zakresie [0,1], porównanie tych zapytań jest możliwe przy użyciu tych wskaźników.

Wady: 1. nDCG nie penalizuje wyników wyszukiwania złych dokumentów. Można to naprawić, dostosowując wartości trafności przypisane dokumentom. 2. nDCG nie penalizuje brakujących dokumentów. Można to naprawić, ustalając rozmiar pobierania i stosując minimalną liczbę punktów dla brakujących dokumentów.

Zobacz to, aby zobaczyć przykładowe obliczenia nDCG.

Odniesienie

m1cro1ce
źródło

0

Przydatne zasoby:

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
Uczenie się rangi dla wyszukiwania informacji (Tie-Yan Liu)

Renaud
źródło

Jak porównać dwa algorytmy rankingu?

Odpowiedzi: