Metryki do oceny algorytmów rankingowych

15

Chciałbym przyjrzeć się kilku różnym wskaźnikom algorytmów rankingowych - kilka z nich znajduje się na stronie Wikipedii Uczenie się rangowania, w tym:

• Średnia średnia precyzja (MAP);

• DCG i NDCG;

• Precision @ n, NDCG @ n, gdzie „@n” oznacza, że metryki są oceniane tylko na górnych n dokumentach;

• Średnia ranga wzajemności;

• tau Kendalla

• Spearman's Rho

• Oczekiwany stopień wzajemności

• Fundacja Yandexa

ale nie jest dla mnie jasne, jakie są zalety / wady każdego z nich lub kiedy możesz wybrać jeden nad drugim (lub co by to znaczyło, gdyby jeden algorytm był lepszy od drugiego na NDGC, ale był gorszy, gdy oceniono go za pomocą MAP).

Czy jest gdziekolwiek mogę się dowiedzieć więcej na temat tych pytań?

algorithms ranking

— anthr
źródło

28

Tak naprawdę szukam tej samej odpowiedzi, jednak powinienem być w stanie przynajmniej częściowo odpowiedzieć na twoje pytanie.

Wszystkie wymienione przez Ciebie dane mają różne cechy i, niestety, ten, który powinieneś wybrać, zależy od tego, co naprawdę chcesz zmierzyć. Oto kilka rzeczy, o których warto pamiętać:

Metryka rho Spearmana karze błędy na górze listy z taką samą wagą jak niedopasowania na dole, więc w większości przypadków nie jest to metryka używana do oceny rankingów
DCG i NDCG są jedną z niewielu miar, które uwzględniają niebinarną funkcję narzędzia, więc możesz opisać, jak użyteczny jest rekord, a nie, czy jest użyteczny.
DCG i NDCG mają ustalone wagi pozycji, więc dokument na danej pozycji ma zawsze taki sam zysk i zniżkę niezależnie od dokumentów pokazanych powyżej
Zwykle wolisz NDCG niż DCG , ponieważ normalizuje wartość według liczby odpowiednich dokumentów
MAP ma być klasyczną i „praktyczną” miarą tego problemu i wydaje się być standardem w tej dziedzinie.
(N) DCG należy zawsze obliczać dla określonej liczby rekordów (@k), ponieważ ma długi ogon (wiele nieistotnych rekordów na końcu rankingu mocno przesądza wskaźnik). Nie dotyczy to MAP .
Średnia wzajemna ranga oznacza tylko pozycję pierwszego odpowiedniego dokumentu, więc jeśli zależy ci na jak największej liczbie odpowiednich dokumentów, aby znaleźć się wysoko na liście, nie powinien to być twój wybór
Tau Kendalla obsługuje tylko binarną funkcję użyteczności, należy ją również obliczyć @k (podobnie jak NDCG )

Wartościowe zasoby:

Wykład Victora Lavrenko na YouTube - to tylko link do odcinka MAP vs NDCG, ale cały wykład zawiera znacznie więcej (w tym Tau Kendalla). Zdecydowanie powinieneś to sprawdzić, świetny wykład!
Papier ERR

Nie mogę opublikować więcej linków z powodu świeżego konta :) Jeśli ktoś ma jeszcze jakieś uwagi lub pomysły, chętnie je usłyszę!

— stpk
źródło

Myślę, że teraz masz wystarczającą liczbę punktów, aby zaktualizować tę odpowiedź, jeśli masz więcej linków.

— Yash Kumar Atri

5

W wielu przypadkach, w których stosuje się algorytmy rankingowe (np. Wyszukiwarka Google, rekomendacje produktów Amazon), uzyskuje się setki i tysiące wyników. Użytkownik chce oglądać tylko u góry ~ 20 lub mniej więcej. Reszta jest więc całkowicie nieistotna.

$k$

Jeśli dotyczy to Twojej aplikacji, ma to bezpośredni wpływ na metrykę:

$k$ $k$
$2k$

$k$ $k$

Najwyższa dokładność klasyfikacji do rankingu

Prawdę mówiąc, zdefiniowanie porządku może być trudne. A jeśli rozróżniasz tylko istotne / nieistotne, to tak naprawdę jesteś w przypadku klasyfikacji!

Dokładność Top-n jest miarą klasyfikacji. Zobacz Jaka jest definicja dokładności Top-n? .

top-k accuracy = \frac{how often was at least one relevant element within the top-k of a ranking query?}{ranking queries}

$\text{top-k accuracy} = \frac{\text{how often was at least one relevant element within the top-k of a ranking query?}}{\text{ranking queries}}$

$k$

$k$ $k \in [5, 20]$

$k$

Precision @ k

Precision@k = \frac{number of relevant items within the top-k}{k} \in [0, 1], higher is better

$\text{Precision@k} = \frac{\text{number of relevant items within the top-k}}{k} \in [0, 1], \text{ higher is better}$

Co ci mówi:

jeśli jest wysoki -> Duża część tego, co pokazujesz użytkownikowi, jest dla niego istotna
jeśli jest niski -> Marnujesz czas użytkowników. Wiele z tego, co im pokazujesz, nie ma dla nich znaczenia

Recall @ k

Recall@k = \frac{number of relevant items within the top-k}{total number of relevant items} \in [0, 1], higher is better

$\text{Recall@k} = \frac{\text{number of relevant items within the top-k}}{\text{total number of relevant items}} \in [0, 1], \text{ higher is better}$

Co to znaczy:

Jeśli jest wysoki: pokaż, co masz! Dajesz im wszystkie odpowiednie przedmioty.
Jeśli jest niski: w porównaniu z całkowitą ilością odpowiednich elementów, k jest małe / odpowiednie elementy w górnym k są małe. Z tego powodu samo odwołanie @ k może nie być tak znaczące. Jeśli jest to połączone z wysoką precyzją @ k, wówczas zwiększenie k może mieć sens.

— Martin Thoma
źródło

3

Niedawno musiałem wybrać metrykę do oceny algorytmów rankingowych na wielu etykietach i doszedłem do tego tematu, co było bardzo pomocne. Oto kilka dodatków do odpowiedzi stpk, które były pomocne przy dokonywaniu wyboru.

MAP można przystosować do problemów związanych z wieloma etykietami, kosztem przybliżenia
MAP nie trzeba obliczać przy k, ale wersja wielopłaszczyznowa może nie zostać dostosowana, gdy klasa negatywna jest przeważająca
MAP i (N) DCG można przepisać jako średnią ważoną wartości trafności w rankingu

Detale

Skupmy się na średniej precyzji (AP), ponieważ średnia średnia precyzja (MAP) to tylko średnia AP na kilka zapytań. AP jest poprawnie zdefiniowane na danych binarnych jako obszar pod krzywą dokładnego przywołania, który może być przepisany jako średnia dokładności dla każdej dodatniej pozycji. (patrz artykuł w Wikipedii na temat MAP ) Możliwym przybliżeniem jest zdefiniowanie go jako średniej dokładności dla każdego z nichpozycja. Niestety tracimy niezłą właściwość, że negatywne przykłady umieszczone na końcu listy nie mają wpływu na wartość AP. (Jest to szczególnie smutne, jeśli chodzi o ocenę wyszukiwarki, która zawiera znacznie więcej negatywnych przykładów niż pozytywnych przykładów. Możliwym obejściem jest podpróbowanie negatywnych przykładów kosztem innych wad, np. Zapytania zawierające więcej pozytywnych pozycji staną się jednakowo trudne do zapytania z kilkoma pozytywnymi przykładami).

Z drugiej strony, to przybliżenie ma dobrą właściwość, którą dobrze uogólnia na przypadek wielopłaszczyznowy. Rzeczywiście, w przypadku binarnym precyzję w pozycji k można również interpretować jako średnią istotność przed pozycją k, gdzie trafność pozytywnego przykładu wynosi 1, a trafność negatywnego przykładu wynosi 0. Ta definicja rozciąga się całkiem naturalnie na przypadek, w którym istnieją więcej niż dwa różne poziomy istotności. W tym przypadku AP można również zdefiniować jako średnią średnich trafności dla każdej pozycji.

$k$

w_{k}^{A P} = \frac{1}{K} \log (\frac{K}{k})

$w_k^{AP} = \frac{1}{K}\log(\frac{K}{k})$

$K$

w_{k}^{D C G} = \frac{1}{\log (k + 1)}

$w_k^{DCG} = \frac{1}{\log(k+1)}$

Z tych dwóch wyrażeń możemy wywnioskować, że - AP waży dokumenty od 1 do 0. - DCG waży dokumenty niezależnie od całkowitej liczby dokumentów.

W obu przypadkach, jeśli istnieje znacznie więcej nieistotnych przykładów niż odpowiednie przykłady, całkowita waga pozytywu może być nieistotna. W przypadku AP obejściem tego problemu jest podpróbkowanie próbek ujemnych, ale nie jestem pewien, jak wybrać proporcję podpróbkowania, a także czy uzależnić ją od zapytania lub liczby pozytywnych dokumentów. W przypadku DCG możemy to wyciąć o k, ale pojawiają się te same pytania.

Z przyjemnością usłyszę o tym więcej, jeśli ktoś tutaj będzie pracował na ten temat.

— rdbs
źródło