Ranking – jedno z podstawowych zadań wyszukiwania informacji, dyscypliny naukowej i inżynierskiej zajmującej się wyszukiwaniem informacji w dużych zbiorach danych, wykorzystywanej m.in. w wyszukiwarkach internetowych. Dla zapytania q oraz zbioru dokumentów D, wyłonionych we wcześniejszym etapie wyszukiwania, zadanie polega na uporządkowaniu dokumentów z D według przyjętego kryterium, tak aby „najlepsze” wyniki znalazły się na początku listy prezentowanej użytkownikowi. Klasycznie kryterium to formułuje się w kategoriach relewancji (trafności) dokumentu względem potrzeby informacyjnej wyrażonej w zapytaniu.

Ranking sprowadza się zwykle do wyznaczenia liczbowej oceny (ang. score) dla każdej pary zapytanie-dokument, a następnie posortowania dokumentów według malejącej oceny. Funkcją oceniającą może być podobieństwo cosinusowe między wektorami wag TF-IDF w modelu wektorowym, wartość funkcji BM25 albo prawdopodobieństwo relewancji w modelu probabilistycznym. Alternatywne podejście polega na zdefiniowaniu funkcji określonej na parach dokumentów, wskazującej, który z dwóch dokumentów jest bardziej relewantny. Wyznaczana w ten sposób relacja preferencji nie musi być przechodnia – mogą w niej występować cykle. Z tego powodu metody uczone na parach dokumentów ustalają ostateczną kolejność, trenując skalarną funkcję oceny pojedynczych dokumentów.

Poza wyszukiwarkami internetowymi ranking stosuje się m.in. w systemach rekomendacyjnych, w wewnętrznych wyszukiwarkach serwisów internetowych oraz w bibliometrii. W statystyce terminu „rangowanie” używa się w innym znaczeniu – jako zastąpienia wartości zmiennej jej rangą.

Historia Wagi terminów Podstawy oceniania dokumentów na podstawie wag przypisanych terminom powstały w latach 60. i 70. XX wieku. W 1972 Karen Spärck Jones wprowadziła odwrotną częstość dokumentową (IDF), czyli ważenie terminów miarą ich rzadkości w kolekcji – składnik obecny do dziś w TF-IDF i w BM25. W 1975 Gerard Salton, A. Wong i C.S. Yang sformalizowali model wektorowy, w którym dokumenty i zapytania są wektorami wag terminów, a ich podobieństwo mierzy się w przestrzeni wielowymiarowej.

Analiza odsyłaczy Idea rankingu obiektów na podstawie struktury powiązań między nimi, z iteracyjnym wyznaczaniem wyniku, wywodzi się z ekonomii lat 40. XX wieku. W 1941 Wassily Leontief zaproponował iteracyjną metodę oceny znaczenia sektorów gospodarki, w której znaczenie sektora zależy od znaczenia sektorów dostarczających mu zasobów. W 1965 Charles H. Hubbell przeniósł ten schemat na grunt socjologii, określając znaczenie osoby na podstawie znaczenia osób, które ją popierają.

W 1976 Gabriel Pinski i Francis Narin zastosowali analogiczne rozumowanie do rankingu czasopism naukowych, wyznaczając znaczenie czasopisma jako wektor własny macierzy cytowań: czasopismo jest tym ważniejsze, im częściej cytują je inne ważne czasopisma. W 1998 Sergey Brin i Larry Page przedstawili algorytm PageRank, stanowiący podstawę rankingu w prototypie wyszukiwarki Google rozwijanym wówczas na Uniwersytecie Stanforda. Niezależnie, w pracach opublikowanych w latach 1998-1999, Jon Kleinberg opisał algorytm HITS, w którym strony internetowe rozpatruje się jednocześnie jako „koncentratory” (hubs) i „autorytety” (authorities). Wszystkie te metody łączy wykorzystanie struktury powiązań oraz iteracyjny sposób wyznaczania wyniku.

Modele rankingu Modele wyszukiwania informacji dzieli się zwykle na modele boolowskie, wektorowe, probabilistyczne oraz podejścia oparte na uczeniu maszynowym. W literaturze porównywano skuteczność klasycznych modeli w zadaniach wyszukiwania tekstu.

Model boolowski Model boolowski jest najprostszym modelem wyszukiwania: zapytania zapisuje się jako wyrażenia algebry Boole’a, a dokument zostaje zwrócony wtedy i tylko wtedy, gdy spełnia to wyrażenie. Ponieważ wynikiem dopasowania jest wartość binarna, model ten sam z siebie nie dostarcza podstawy do rankingu wyników. Ranking umożliwiają dopiero jego rozszerzenia, takie jak model boolowski rozszerzony lub rozmyty.

Model wektorowy Model wektorowy rozwiązuje problem dopasowań częściowych, reprezentując dokumenty i zapytania jako wektory wag przypisanych terminom indeksowym. Jedną z najpopularniejszych metod wyznaczania wag jest TF-IDF, w której waga terminu rośnie wraz z częstością jego wystąpień w dokumencie i maleje wraz z liczbą dokumentów w korpusie, w których termin ten występuje. Ocena podobieństwa dokumentu do zapytania jest wyznaczana jako podobieństwo cosinusowe wektora zapytania i wektora dokumentu. Dokumenty zwraca się w kolejności malejącego podobieństwa.

Model probabilistyczny W modelu probabilistycznym relewancję traktuje się jako zdarzenie losowe, a proces wyszukiwania modeluje się narzędziami rachunku prawdopodobieństwa. Podejście to wprowadzili w 1960 Melvin E. Maron i John L. Kuhns, a następnie rozwijali m.in. Stephen Robertson i Karen Spärck Jones. Uzasadnieniem jest nieostrość języka naturalnego: system nie może z całkowitą pewnością wskazać, które dokumenty są relewantne dla danego zapytania, może natomiast szacować prawdopodobieństwo relewancji.

Sformułowana przez Robertsona w 1977 zasada porządkowania według prawdopodobieństwa (ang. probability ranking principle) mówi, że uszeregowanie dokumentów według malejącego prawdopodobieństwa relewancji jest optymalne przy podanych założeniach. Najbardziej rozpowszechnioną praktyczną realizacją tego podejścia jest funkcja rankingowa BM25.

Uczenie rankingu Uczenie rankingu (ang. learning to rank, LTR) obejmuje metody, w których funkcję rankingową wyznacza się za pomocą uczenia maszynowego. Pary zapytanie-dokument reprezentuje się wektorami cech, a wytrenowany model przypisuje każdemu dokumentowi ocenę, według której powstaje końcowe uporządkowanie.

Algorytmy LTR dzieli się ze względu na postać funkcji straty na: punktowe (pointwise) – oceniające każdy dokument niezależnie, jako zadanie regresji lub klasyfikacji, parowe (pairwise) – optymalizujące poprawność kolejności w parach dokumentów, listowe (listwise) – optymalizujące uporządkowanie całej listy wyników.

Klasyczne metody oceniają dokumenty pojedynczo, co nie pozwala uwzględnić zależności między dokumentami z tej samej listy wyników. Aby to obejść, opracowano metody oceniające listę jako całość, w tym modele niezależne od permutacji wejściowej, które można stosować bezpośrednio do zbioru dokumentów, bez wstępnego uporządkowania.

Modele neuronowe Od końca drugiej dekady XXI wieku w rankingu stosuje się modele oparte na wstępnie wytrenowanych sieciach transformerowych. Wyróżnia się dwa zasadnicze schematy: modele dwukodujące (ang. bi-encoder), w których zapytanie i dokument są kodowane niezależnie do postaci gęstych wektorów, a ocenę wyznacza się jako ich podobieństwo. Osadzenia dokumentów można wyznaczyć z wyprzedzeniem i zaindeksować, co pozwala stosować to podejście do całej kolekcji (wyszukiwanie gęste, ang. dense retrieval), modele kodujące łącznie (ang. cross-encoder), w których zapytanie i dokument przetwarzane są razem, co pozwala modelować interakcje między ich fragmentami. Ze względu na koszt obliczeniowy stosuje się je tylko do ponownego uporządkowania niewielkiej liczby kandydatów.

Z ograniczeń tych wynika architektura kaskadowa: pierwszy etap zawęża kolekcję do kilkuset kandydatów tanią metodą (BM25 lub wyszukiwanie gęste), a kolejne etapy porządkują ich coraz dokładniej, lecz coraz kosztowniej.

Miary oceny Miary skuteczności wyszukiwania wyznacza się dla pojedynczego zapytania na podstawie ocen trafności przygotowanych przez sędziów, a następnie uśrednia po zbiorze zapytań testowych. Niech I oznacza zbiór dokumentów relewantnych dla danego zapytania, a O – zbiór dokumentów zwróconych przez system. Podstawowe miary – precyzję, pełność i miarę F1 – definiuje się dla zbiorów nieuporządkowanych, dlatego ocena uporządkowanych list wyników wymaga rozszerzenia tych miar albo zdefiniowania miar dodatkowych.

Precyzja Precyzja P określa, jaka część dokumentów zwróconych jest relewantna:

Pełność Pełność R (ang. recall) określa, jaka część dokumentów relewantnych została zwrócona:

Miara F1 Miara F1 jest średnią harmoniczną precyzji i pełności:

Miary dla list uporządkowanych Precyzja na pozycji k, oznaczana P@k, to udział dokumentów relewantnych wśród k pierwszych wyników Ok:

Wyznaczając dla kolejnych wartości k zarówno precyzję, jak i pełność, otrzymuje się punkty krzywej precyzja–pełność, którą zwykle wygładza się przez interpolację do ustalonych poziomów pełności. Uśredniona po zapytaniach precyzja liczona w punktach, w których pojawiają się kolejne dokumenty relewantne, daje miarę MAP (ang. mean average precision).

Średnia odwrotność rangi (MRR) uwzględnia tylko pozycję pierwszego trafnego wyniku, co jest przydatne przy zapytaniach o jedną poprawną odpowiedź. Dla zbioru zapytań Q, gdzie ri jest pozycją pierwszego dokumentu relewantnego dla i-tego zapytania:

Znormalizowany zdyskontowany zysk kumulacyjny (NDCG) uwzględnia dodatkowo stopniowaną relewancję: wkład dokumentu zależy od przypisanego mu stopnia relewancji reli i jest dyskontowany logarytmicznie wraz z pozycją na liście, a suma jest normalizowana wartością IDCGk uzyskaną dla uporządkowania idealnego, co pozwala porównywać wyniki między zapytaniami. W najczęściej stosowanej obecnie postaci:

W pierwotnym sformułowaniu zysk był proporcjonalny do stopnia relewancji, a nie wykładniczy.

Algorytmy oparte na analizie odsyłaczy W przeciwieństwie do funkcji oceniających dopasowanie dokumentu do zapytania, algorytmy analizy odsyłaczy wyznaczają ocenę niezależną od zapytania (PageRank) albo zależną od niego tylko przez wybór podgrafu (HITS). W wyszukiwarkach oceny takie łączy się z ocenami relewancji, a nie stosuje samodzielnie.

PageRank

PageRank opisuje prawdopodobieństwo, że użytkownik klikający losowo w odsyłacze dotrze do danej strony. W wersji z teleportacją, stosowanej w praktyce, wartości PageRank spełniają układ równań

gdzie Bu jest zbiorem stron odsyłających do strony u, L(v) – liczbą odsyłaczy wychodzących ze strony v, a d – współczynnikiem tłumienia, dla którego Brin i Page przyjęli wartość 0,85. Bez składnika stałego proces iteracyjny nie musi zbiegać do jednoznacznego rozwiązania: prawdopodobieństwo „wycieka” na stronach bez odsyłaczy wychodzących, a zamknięte grupy stron mogą je kumulować.

Stosuje się też wariant znormalizowany, w którym składnik stały wynosi (1 − d)/N, gdzie N jest liczbą stron w grafie, wtedy wartości sumują się wtedy do jedności i można je interpretować jako rozkład prawdopodobieństwa:

Po uzupełnieniu wierszy odpowiadających stronom bez odsyłaczy wychodzących macierz przejścia jest nieprzywiedlna i aperiodyczna, co zapewnia istnienie i jednoznaczność rozkładu stacjonarnego. Wartości nie są wyznaczane bezpośrednio, lecz iteracyjnie: zwykle przyjmuje się początkowo rozkład równomierny, a w kolejnych przebiegach wartości są korygowane.

HITS

Podobnie jak PageRank, algorytm HITS wykorzystuje analizę odsyłaczy, jednak działa na niewielkich podgrafach wyznaczanych dla konkretnego zapytania, a nie na całym grafie sieci. Każdej stronie przypisuje się dwie wagi – koncentratora i autorytetu – wyznaczane iteracyjnie; strony o najwyższych wagach trafiają na początek listy wyników.

Ponowne uporządkowanie wyników Ponowne uporządkowanie (ang. re-ranking) to korekta wstępnej listy wyników, mająca pogodzić relewancję z dodatkowymi kryteriami. Jednym z nich jest różnorodność wyników – ograniczanie redundancji między dokumentami zajmującymi kolejne pozycje. W metodzie MMR (ang. maximal marginal relevance) do listy S dołącza się kolejno dokument maksymalizujący

gdzie pierwszy składnik jest podobieństwem dokumentu do zapytania, drugi – jego największym podobieństwem do dokumentów już wybranych, a parametr λ określa proporcję między relewancją a różnorodnością. Innym kryterium jest sprawiedliwy podział ekspozycji między dokumenty lub dostawców treści.