Zdyskontowany skumulowany zysk (ang. discounted cumulative gain, DCG) – miara skuteczności rankingu stosowana w wyszukiwaniu informacji, w szczególności do oceny wyników wyszukiwarek internetowych i systemów rekomendacyjnych. Miara ocenia użyteczność (zysk, ang. gain) dokumentów na liście wyników na podstawie ich stopniowanych ocen relewancji (ang. graded relevance), przy czym zysk dokumentów na dalszych pozycjach jest zmniejszany (dyskontowany) logarytmicznie względem pozycji. W praktyce najczęściej stosuje się wariant znormalizowany, nDCG (zapisywany też NDCG, ang. normalized discounted cumulative gain, znormalizowany zdyskontowany skumulowany zysk), przyjmujący wartości z przedziału od 0 do 1, co umożliwia porównywanie jakości rankingu między zapytaniami.

Miarę zaproponowali w 2000 roku Kalervo Järvelin i Jaana Kekäläinen z Uniwersytetu w Tampere. W polskojęzycznej literaturze naukowej używana jest zarówno nazwa polska, jak i nazwa angielska oraz akronimy DCG i nDCG.

Definicja DCG opiera się na dwóch założeniach: dokumenty o wysokiej relewancji są bardziej użyteczne, gdy znajdują się wyżej na liście wyników, dokumenty o wysokiej relewancji są bardziej użyteczne niż dokumenty o relewancji niskiej, a te z kolei bardziej niż dokumenty nierelewantne.

Punktem wyjścia jest skumulowany zysk (ang. cumulative gain, CG) – suma ocen relewancji dokumentów od pierwszej do -tej pozycji listy:

gdzie oznacza ocenę relewancji dokumentu na pozycji . Zamiana kolejności dokumentów w obrębie pierwszych pozycji nie zmienia wartości CG, więc miara ta nie odzwierciedla jakości samego uporządkowania.

DCG usuwa tę wadę, dyskontując wkład dokumentów na dalszych pozycjach za pomocą logarytmu o podstawie 2:

W uczeniu maszynowym, zwłaszcza w zadaniach uczenia rankingu (ang. learning to rank), rozpowszechniona jest alternatywna postać, w której zysk rośnie wykładniczo z oceną relewancji, przez co silniej premiowane są dokumenty o najwyższych ocenach:

Dla binarnych ocen relewancji () obie postacie są identyczne. Logarytmiczną funkcję dyskontującą autorzy miary uzasadniali początkowo jedynie tym, że zapewnia ona łagodne zmniejszanie wkładu kolejnych pozycji. Później wykazano teoretycznie, że przy takim dyskoncie nDCG zachowuje zdolność rozróżniania funkcji rankingujących również dla bardzo długich list wyników, podczas gdy przy wolniej malejących funkcjach dyskontujących wartości nDCG wszystkich funkcji rankingujących zbiegają do tej samej granicy.

Znormalizowany DCG Liczba dokumentów relewantnych i rozkład ich ocen zależą od zapytania, więc wartości DCG dla różnych zapytań nie są bezpośrednio porównywalne. Dlatego wartość DCG normalizuje się, dzieląc ją przez IDCG (ang. ideal DCG) – wartość DCG rankingu idealnego, czyli listy wszystkich znanych dokumentów relewantnych uporządkowanych nierosnąco według ocen relewancji:

gdzie

a oznacza listę dokumentów relewantnych uporządkowaną nierosnąco według relewancji i obciętą do pozycji. W obliczeniach IDCG stosuje się tę samą funkcję zysku (liniową lub wykładniczą), co w DCG. Ranking idealny ma nDCG równe 1. W ocenie systemu wartości nDCG wyznacza się dla każdego zapytania testowego i uśrednia po zbiorze zapytań.

Przykład Niech w odpowiedzi na zapytanie wyszukiwarka zwróci sześć dokumentów , którym oceniający przypisali oceny relewancji w skali 0–3 (0 – nierelewantny, 3 – w pełni relewantny):

Skumulowany zysk tej listy wynosi:

Zamiana dowolnych dwóch dokumentów miejscami nie zmienia CG. Wartość DCG uwzględnia natomiast pozycje dokumentów:

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

Do obliczenia nDCG potrzebna jest wartość IDCG. Załóżmy, że oprócz sześciu zwróconych dokumentów znane są jeszcze dwa dokumenty relewantne dla tego zapytania, których wyszukiwarka nie zwróciła: jeden z oceną 3 i jeden z oceną 2. Ranking idealny wszystkich znanych dokumentów ma wówczas postać:

a po obcięciu do sześciu pozycji:

skąd:

Ograniczenia Z definicji wynika, że dokument nierelewantny (o ocenie 0) nie wnosi wkładu do sumy, więc dopisanie do listy dodatkowych nierelewantnych wyników nie obniża jej nDCG. Miara nie karze też za brak dokumentów relewantnych na liście: dwie listy zwracające te same dokumenty w tej samej kolejności, lecz różnej długości, mogą uzyskać identyczne nDCG. Z tych powodów nDCG oblicza się zwykle dla ustalonej liczby pierwszych pozycji , co zapisuje się jako nDCG@k.

Wiarygodność nDCG zależy ponadto od kompletności ocen relewancji. W kolekcjach testowych oceniana jest tylko część dokumentów, a dokumenty nieocenione traktuje się zwykle jak nierelewantne, co może zaniżać wynik systemów zwracających relewantne, lecz nieocenione dokumenty.

Przypisy

Linki zewnętrzne – implementacja nDCG w bibliotece scikit-learn Kategoria:Uczenie maszynowe Kategoria:Zachowania informacyjne