Zdyskontowany skumulowany zysk — Discounted cumulative gain

Zdyskontowany skumulowany zysk ( DCG ) jest miarą jakości rankingu. W wyszukiwaniu informacji jest często używany do pomiaru skuteczności algorytmów wyszukiwarek internetowych lub powiązanych aplikacji. Używając stopniowanej skali trafności dokumentów w zestawie wyników wyszukiwarki, DCG mierzy użyteczność lub zysk dokumentu na podstawie jego pozycji na liście wyników. Zysk jest kumulowany od góry listy wyników do dołu, przy czym zysk z każdego wyniku jest dyskontowany na niższych pozycjach.

Przegląd

Przy stosowaniu DCG i związanych z nim miar przyjmuje się dwa założenia.

1. Bardzo trafne dokumenty są bardziej przydatne, gdy pojawiają się wcześniej na liście wyników wyszukiwania (mają wyższe pozycje)
2. Bardzo istotne dokumenty są bardziej przydatne niż dokumenty marginalnie istotne, które z kolei są bardziej przydatne niż dokumenty nieistotne.

DCG wywodzi się z wcześniejszej, bardziej prymitywnej miary zwanej Cumulative Gain.

Skumulowany zysk

Łączny zysk (CG) to suma ocenionych wartości trafności wszystkich wyników na liście wyników wyszukiwania. Ten poprzednik DCG nie uwzględnia rangi (pozycji) wyniku na liście wyników pod kątem użyteczności zestawu wyników. CG na danej pozycji w rankingu definiuje się jako: ${\displaystyle p}$

${\ Displaystyle \ operatorname {CG_ {p}} = \ suma _ {i = 1} ^ {p} rel_ {i}}$

Gdzie jest oceniona trafność wyniku na pozycji . ${\displaystyle rel_{i}}$${\displaystyle i}$

Na wartość obliczoną za pomocą funkcji CG nie mają wpływu zmiany kolejności wyników wyszukiwania. Oznacza to, że przeniesienie wysoce istotnego dokumentu nad dokument o wyższej randze, mniej istotny, nie zmienia obliczonej wartości CG (zakładając ). W oparciu o dwa powyższe założenia dotyczące użyteczności wyników wyszukiwania, (N)DCG jest zwykle preferowany w stosunku do CG. ${\displaystyle d_{i}}$${\displaystyle d_{j}}$${\displaystyle ja,j\leq p}$

Kumulacyjny zysk jest czasami nazywany Precyzją stopniowaną, ponieważ jest identyczny z metryką Dokładność, jeśli skala oceny jest binarna.

Zdyskontowany skumulowany zysk

Założeniem DCG jest to, że wysoce istotne dokumenty znajdujące się niżej na liście wyników wyszukiwania powinny być karane, ponieważ oceniona wartość trafności jest zmniejszana logarytmicznie proporcjonalnie do pozycji wyniku.

Tradycyjna formuła DCG akumulowana na danej pozycji rankingowej określana jest jako: ${\displaystyle p}$

${\ Displaystyle \ operatorname {DCG_ {p}} = \ suma _ {i = 1} ^ {p} {\ Frac {rel_ {i}} {\ log _ {2} (i + 1)}} = rel_ { 1}+\sum _{i=2}^{p}{\frac {rel_{i}}{\log _{2}(i+1)}}}$

Wcześniej nie było żadnego teoretycznie rozsądnego uzasadnienia stosowania logarytmicznego współczynnika redukcji poza faktem, że daje on gładką redukcję. Ale Wang i in. (2013) dali teoretyczną gwarancję zastosowania logarytmicznego współczynnika redukcji w znormalizowanym DCG (NDCG). Autorzy pokazują, że dla każdej pary istotnie różnych funkcji rankingowych NDCG może w spójny sposób zdecydować, która z nich jest lepsza.

Alternatywne sformułowanie DCG kładzie większy nacisk na wyszukiwanie odpowiednich dokumentów:

${\ Displaystyle \ operatorname {DCG_ {p}} = \ suma _ {i = 1} ^ {p} {\ Frac {2 ^ {rel_ {i}}} -1} {\ log _ {2} (i + 1 )}}}$

Ta ostatnia formuła jest powszechnie stosowana w przemyśle, w tym w dużych firmach zajmujących się wyszukiwaniem w Internecie i platformach konkurencji data science, takich jak Kaggle.

Te dwa sformułowania DCG są takie same, gdy wartości istotności dokumentów są binarne ; . ${\displaystyle rel_{i}\w \{0,1\}}$

Należy zauważyć, że Croft i in. (2010) oraz Burges i in. (2005) przedstawiają drugi DCG z logiem o podstawie e, podczas gdy obie wersje DCG powyżej używają logu o podstawie 2. Przy obliczaniu NDCG z pierwszym sformułowaniem DCG, podstawa logu nie ma znaczenia, ale podstawa log ma wpływ na wartość NDCG dla drugiego sformułowania. Oczywiście podstawa logarytmu wpływa na wartość DCG w obu formułach.

Znormalizowane DCG

Listy wyników wyszukiwania różnią się długością w zależności od zapytania . Porównanie wydajności wyszukiwarki z jednym zapytaniem do następnego nie może być konsekwentnie osiągnięte przy użyciu samego DCG, więc skumulowany zysk na każdej pozycji dla wybranej wartości powinien być znormalizowany dla wszystkich zapytań. Odbywa się to poprzez sortowanie wszystkich odpowiednich dokumentów w korpusie według ich względnego znaczenia, tworząc maksymalną możliwą pozycję DCG przez pozycję , zwaną również Idealną DCG (IDCG) przez tę pozycję. W przypadku zapytania znormalizowany zdyskontowany skumulowany zysk (nDCG) jest obliczany jako: ${\displaystyle p}$${\displaystyle p}$

${\ Displaystyle \ operatorname {nDCG_ {p}} = {\ Frac {DCG_ {p}} {IDCG_ {p}}}}$,

gdzie IDCG jest idealnym zdyskontowanym skumulowanym zyskiem,

${\ Displaystyle \ operatorname {IDCG_ {p}} = \ suma _ {i = 1} ^ {| REL_ {p} |} {\ Frac {2 ^ {rel_ {i}} -1} {\ log _ {2 }(i+1)}}}$

i przedstawia listę odpowiednich dokumentów (uporządkowanych według ich ważności) w korpusie do pozycji p. ${\displaystyle REL_{p}}$

Wartości nDCG dla wszystkich zapytań można uśrednić w celu uzyskania miary średniej wydajności algorytmu rankingu wyszukiwarki. Zwróć uwagę, że w idealnym algorytmie rankingu będzie to takie samo, jak przy wytwarzaniu nDCG o wartości 1.0. Wszystkie obliczenia nDCG są zatem wartościami względnymi w przedziale od 0,0 do 1,0, a więc są porównywalne z zapytaniami krzyżowymi. ${\ Displaystyle DCG_ {p}}$${\displaystyle IDCG_{p}}$

Główną trudnością napotkaną podczas używania nDCG jest niedostępność idealnej kolejności wyników, gdy dostępna jest tylko częściowa informacja zwrotna o istotności .

Przykład

Przedstawiony z listą dokumentów w odpowiedzi na zapytanie wyszukiwania, uczestnik eksperymentu jest proszony o ocenę związku każdego dokumentu z zapytaniem. Każdy dokument należy oceniać w skali 0-3, gdzie 0 oznacza nieistotny, 3 oznacza bardzo istotny, a 1 i 2 oznacza „gdzieś pomiędzy”. Dla dokumentów uporządkowanych przez algorytm rankingowy jako

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

użytkownik podaje następujące oceny trafności:

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

To znaczy: dokument 1 ma trafność 3, dokument 2 ma trafność 2 itd. Łączny zysk z tej listy wyników wyszukiwania to:

${\ Displaystyle \ operatorname {CG_ {6}} = \ suma _ {i = 1} ^ {6} rel_ {i} = 3 + 2 + 3 + 0 + 1 + 2 = 11}$

Zmiana kolejności dowolnych dwóch dokumentów nie wpływa na miarę CG. Jeśli i są zamienione, CG pozostaje taka sama, 11. DCG służy do podkreślenia bardzo istotnych dokumentów pojawiających się na początku listy wyników. Stosując skalę logarytmiczną do redukcji, DCG dla każdego wyniku w kolejności wynosi: ${\displaystyle D_{3}}$${\displaystyle D_{4}}$

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

Tak więc ten ranking to: ${\ Displaystyle DCG_ {6}}$

${\ Displaystyle \ operatorname {DCG_ {6}} = \ suma _ {i = 1} ^ {6} {\ Frac {rel_ {i}} {\ log _ {2} (i + 1)}} = 3+ 1,262+1,5+0+0,387+0,712=6,861}$

Teraz zmiana i skutkuje zmniejszeniem DCG, ponieważ mniej istotny dokument znajduje się wyżej w rankingu; oznacza to, że bardziej trafny dokument jest bardziej dyskontowany przez umieszczenie go na niższej pozycji. ${\displaystyle D_{3}}$${\displaystyle D_{4}}$

Wydajność tego zapytania w stosunku do innego jest nieporównywalna w tej formie, ponieważ inne zapytanie może mieć więcej wyników, co skutkuje większym ogólnym DCG, który niekoniecznie musi być lepszy. W celu porównania wartości DCG muszą zostać znormalizowane.

Aby znormalizować wartości DCG, potrzebna jest idealna kolejność dla danego zapytania. W tym przykładzie ta kolejność byłaby monotonicznie malejącym rodzajem wszystkich znanych sądów dotyczących istotności. Oprócz sześciu z tego eksperymentu, załóżmy, że wiemy również, że istnieje dokument z oceną trafności 3 do tego samego zapytania i dokument z oceną trafności 2 do tego zapytania. Wtedy idealna kolejność to: ${\ Displaystyle D_ {7}}$${\ Displaystyle D_ {8}}$

${\ Displaystyle 3,3,3,2,2,2,2,1,0}$

Bez D7 i D8 idealna kolejność to:

${\ Displaystyle 3,3,2,2,1,0}$

DCG tego idealnego uporządkowania lub IDCG (idealny DCG) jest obliczany do rangi 6:

${\ Displaystyle \ operatorname {IDCG_ {6}} = 7,141}$

I tak nDCG dla tego zapytania jest podane jako:

${\ Displaystyle \ operatorname {nDCG_ {6}} = {\ Frac {DCG_ {6}} {IDCG_ {6}}} = {\ Frac {6.861}{7.141}} = 0,961}$

Ograniczenia

1. Znormalizowana metryka DCG nie karze za złe dokumenty w wyniku. Na przykład, jeśli zapytanie zwróci dwa wyniki z punktacją odpowiednio 1,1,1 i 1,1,1,0 , oba zostaną uznane za równie dobre, nawet jeśli ten drugi zawiera zły dokument. W przypadku ocen rankingowych Doskonały, Dostateczny, Zły można użyć wyników liczbowych 1,0,-1 zamiast 2,1,0 . Spowodowałoby to obniżenie wyniku w przypadku zwrócenia złych wyników, a precyzja wyników byłaby ważniejsza niż przywoływanie. Należy zauważyć, że takie podejście może skutkować ogólnym wynikiem ujemnym, który przesunie dolną granicę wyniku z 0 do wartości ujemnej.
2. Znormalizowany DCG nie karze za brakujące dokumenty w wyniku. Na przykład, jeśli zapytanie zwróci dwa wyniki z punktacją odpowiednio 1,1,1 i 1,1,1,1,1 , oba zostaną uznane za równie dobre, zakładając, że idealny DCG jest obliczany na pozycję 3 dla pierwszego i pozycję 5 dla ten ostatni. Jednym ze sposobów uwzględnienia tego ograniczenia jest wymuszenie stałego rozmiaru zestawu dla zestawu wyników i użycie minimalnych wyników dla brakujących dokumentów. W poprzednim przykładzie użyjemy ocen 1,1,1,0,0 i 1,1,1,1,1 i zacytujemy nDCG jako nDCG@5.
3. Znormalizowany DCG może nie być odpowiedni do mierzenia wydajności zapytań, które często mogą mieć kilka równie dobrych wyników. Jest to szczególnie ważne, gdy ta metryka jest ograniczona tylko do kilku pierwszych wyników, tak jak ma to miejsce w praktyce. Na przykład, dla zapytań takich jak „restauracje” nDCG@1 uwzględni tylko pierwszy wynik, a zatem jeśli jeden zestaw wyników zawiera tylko 1 restaurację z pobliskiego obszaru, podczas gdy drugi zawiera 5, oba uzyskają ten sam wynik, nawet jeśli ta ostatnia jest bardziej wszechstronna.

Zobacz też

• Środki ewaluacyjne (wyszukiwanie informacji)
• Nauka rangi

Bibliografia