Ranking (wyszukiwanie informacji)

Ranking zapytań jest jednym z podstawowych problemów wyszukiwania informacji (IR), dyscypliny naukowo-inżynierskiej stojącej za wyszukiwarkami . Biorąc pod uwagę zapytanie q i zbiór dokumentów D pasujących do zapytania, problem polega na uszeregowaniu, to znaczy posortowaniu dokumentów w D według jakiegoś kryterium, tak aby „najlepsze” wyniki pojawiały się na początku listy wyników wyświetlanej użytkownik. Ranking pod względem wyszukiwania informacji jest ważną koncepcją w informatyce i jest używany w wielu różnych zastosowaniach, takich jak zapytania w wyszukiwarkach i systemy rekomendacyjne . Większość wyszukiwarek korzysta z algorytmów rankingowych, aby zapewnić użytkownikom dokładne i trafne wyniki.

Historia

Pojęcie page rank sięga lat 40. XX wieku i zrodziło się na gruncie ekonomii. W 1941 roku Wassily Leontief opracował iteracyjną metodę wyceny sektora kraju w oparciu o znaczenie innych sektorów, które dostarczały mu zasoby. W 1965 roku Charles H. Hubbell z Uniwersytetu Kalifornijskiego w Santa Barbara opublikował technikę określania ważności jednostek na podstawie ważności ludzi, którzy je popierają.

Gabriel Piński i Francis Narin opracowali podejście do rankingu czasopism. Kierowali się zasadą, że czasopismo jest ważne, jeśli cytują je inne ważne czasopisma. Jon Kleinberg , informatyk z Cornell University , opracował niemal identyczne podejście do PageRank , które nazwano Hypertext Induced Topic Search lub HITS i traktowało strony internetowe jako „centra” i „autorytety”.

Algorytm Google PageRank został opracowany w 1998 roku przez założycieli Google, Sergeya Brina i Larry'ego Page'a i stanowi kluczowy element metody Google służącej do ustalania rankingu stron internetowych w wynikach wyszukiwania . Wszystkie powyższe metody są nieco podobne, ponieważ wszystkie wykorzystują strukturę łączy i wymagają podejścia iteracyjnego.

Modele rankingowe

Funkcje rankingowe są oceniane na różne sposoby; jednym z najprostszych jest określenie precyzji pierwszych k wyników z najwyższej półki dla pewnego ustalonego k ; na przykład odsetek 10 najważniejszych wyników, które są średnio trafne w przypadku wielu zapytań.

Modele IR można ogólnie podzielić na trzy typy: modele logiczne lub BIR, modele przestrzeni wektorowej i modele probabilistyczne . W literaturze można znaleźć różne porównania modeli wyszukiwania (np.).

Modele logiczne

Model Boolean (BIR) to prosty bazowy model zapytań, w którym każde zapytanie jest zgodne z podstawowymi zasadami algebry relacyjnej z wyrażeniami algebraicznymi i w którym dokumenty nie są pobierane, jeśli nie są do siebie całkowicie dopasowane. Ponieważ zapytanie albo pobiera dokument (1), albo nie pobiera dokumentu (0), nie ma metodologii umożliwiającej ich uszeregowanie.

Model przestrzeni wektorowej

Ponieważ model Boolean pobiera tylko kompletne dopasowania, nie rozwiązuje problemu częściowego dopasowania dokumentów. Model przestrzeni wektorowej rozwiązuje ten problem poprzez wprowadzenie wektorów elementów indeksowych, z których każdy ma przypisaną wagę. Wagi wahają się od dodatnich (jeśli pasują całkowicie lub w pewnym stopniu) do ujemnych (jeśli nie pasują lub są całkowicie odwrotnie dopasowane), jeśli istnieją dokumenty. Częstotliwość terminów - odwrotna częstotliwość dokumentów ( tf-idf ) to jedna z najpopularniejszych technik, w której wagami są terminy (np. słowa, słowa kluczowe, frazy itp.), a wymiary to liczba słów w korpusie.

Wynik podobieństwa między zapytaniem a dokumentem można znaleźć, obliczając wartość cosinus między wektorem wagi zapytania a wektorem wagi dokumentu, korzystając z podobieństwa cosinus . Pożądane dokumenty można pobrać, uszeregowując je według wyniku podobieństwa i pobierając k najlepszych dokumentów, które mają najwyższe wyniki lub są najbardziej odpowiednie dla wektora zapytania.

Model probabilistyczny

W modelu probabilistycznym teoria prawdopodobieństwa została wykorzystana jako główny sposób modelowania procesu wyszukiwania w kategoriach matematycznych. Model prawdopodobieństwa wyszukiwania informacji został wprowadzony przez Marona i Kuhnsa w 1960 r., a następnie rozwinięty przez Roberstona i innych badaczy. Według Spacka Jonesa i Willetta (1997): Powody wprowadzenia koncepcji probabilistycznych są oczywiste: systemy IR zajmują się językiem naturalnym, który jest zbyt nieprecyzyjny, aby umożliwić systemowi określenie z całą pewnością, który dokument będzie odpowiedni dla konkretnego zapytania.

Model stosuje teorię prawdopodobieństwa do wyszukiwania informacji (zdarzenie ma możliwość wystąpienia od 0 do 100 procent). tj. w modelu prawdopodobieństwa istotność wyraża się w kategoriach prawdopodobieństwa. Tutaj dokumenty są uszeregowane według malejącego prawdopodobieństwa przydatności. Uwzględnia element niepewności w procesie IR. czyli niepewność, czy dokumenty pobrane przez system są istotne dla danego zapytania.

Model prawdopodobieństwa ma na celu oszacowanie i obliczenie prawdopodobieństwa, że ​​dokument będzie odpowiedni dla danego zapytania w oparciu o pewne metody. „Zdarzenie” w tym kontekście wyszukiwania informacji odnosi się do prawdopodobieństwa powiązania zapytania z dokumentem. W przeciwieństwie do innych modeli IR, model prawdopodobieństwa nie traktuje trafności jako dokładnego pomiaru braku lub dopasowania.

W modelu zastosowano różne metody określania prawdopodobieństwa powiązania zapytań i dokumentów. Trafność w modelu prawdopodobieństwa ocenia się na podstawie podobieństwa zapytań i dokumentów. Ocena podobieństwa zależy ponadto od częstotliwości terminów.

Zatem dla zapytania składającego się tylko z jednego hasła (B) prawdopodobieństwo, że dany dokument (Dm) zostanie uznany za istotny, to stosunek użytkowników, którzy podali zapytanie (B) i uznali dokument (Dm) za istotny w w stosunku do liczby użytkowników, którzy zgłosili termin (B). Jak przedstawiono w modelu Marona i Kuhna, można to przedstawić jako prawdopodobieństwo, że użytkownicy wprowadzający określone hasło zapytania (B) uznają indywidualny dokument (Dm) za istotny.

Według Gerarda Saltona i Michaela J. McGilla istota tego modelu polega na tym, że jeśli można obliczyć szacunki prawdopodobieństwa wystąpienia różnych terminów w odpowiednich dokumentach, to prawdopodobieństwo, że dokument zostanie odnaleziony, pod warunkiem, że jest on istotny, lub że tak nie jest, można oszacować.

Kilka eksperymentów wykazało, że model probabilistyczny może dawać dobre wyniki. Jednak takie wyniki nie były wystarczająco lepsze niż te uzyskane przy użyciu modelu Boole'a lub przestrzeni wektorowej.

Środki oceny

Najczęstszymi miarami oceny są precyzja, zapamiętywanie i wynik f. Obliczane są przy użyciu nieuporządkowanych zbiorów dokumentów. Należy rozszerzyć te miary lub zdefiniować nowe miary, aby ocenić rankingowe wyniki wyszukiwania, które są standardem we współczesnych wyszukiwarkach. W kontekście wyszukiwania rankingowego odpowiednie zestawy odzyskiwanych dokumentów są w sposób naturalny udostępniane przez k najczęściej pobieranych dokumentów. Dla każdego takiego zestawu precyzji i przypominania, uzyskując krzywą precyzji przypominania.

Precyzja

Precyzja mierzy dokładność procesu wyszukiwania. Jeżeli rzeczywisty zbiór odpowiednich dokumentów oznaczono jako I, a wyszukany zbiór dokumentów oznaczono jako O, wówczas dokładność wyraża się wzorem:

$${\ Displaystyle {\ tekst {Precyzja}} = {\ Frac {|\ {{\ tekst {I}} \} \ czapka \ {{\ tekst {O}} \} |} |} | \ {{\ tekst {\ O}}\}|}}}$$

Przypomnienie sobie czegoś

Przywołanie jest miarą kompletności procesu IR. Jeżeli faktyczny zbiór odpowiednich dokumentów oznaczono jako I, a pobrany zbiór dokumentów oznaczono O, wówczas wycofanie następuje poprzez:

$${\ Displaystyle {\ tekst {Przypomnijmy}} = {\ Frac {|\ {{\ tekst {I}} \} \ czapka \ {{\ tekst {O}} \} |} |} | \ {{\ tekst {\ ja}}\}|}}}$$

Wynik F1

Wynik F1 próbuje połączyć miarę precyzji i zapamiętywania. Jest to średnia harmoniczna tych dwóch. Jeśli P to precyzja, a R to wycofanie, wówczas wynik F jest określony wzorem:

$_ } }}}$

Algorytm rankingu strony

Algorytm PageRank generuje rozkład prawdopodobieństwa używany do przedstawienia prawdopodobieństwa, że ​​osoba losowo klikająca łącza trafi na określoną stronę. PageRank można obliczyć dla zbiorów dokumentów dowolnej wielkości. W kilku pracach naukowych przyjęto założenie, że na początku procesu obliczeniowego rozkład jest równomiernie rozłożony pomiędzy wszystkimi dokumentami w zbiorze. Obliczenia PageRank wymagają kilku przejść przez kolekcję w celu dostosowania przybliżonych wartości PageRank tak, aby lepiej odzwierciedlały teoretyczną wartość prawdziwą. Poniżej podano formuły:

${\ Displaystyle PR (u) = \ suma _ {v \ w B_ {u}} {\ Frac {PR (v)} L(v)}}}$

czyli wartość PageRank dla strony u jest zależna od wartości PageRank dla każdej strony v zawartej w zbiorze B _u (zbiór zawierający wszystkie strony linkujące do strony u ), podzielonej przez ilość L ( v ) linków ze strony v .

Algorytm HIT

Podobnie jak PageRank , HITS wykorzystuje analizę linków do analizy trafności stron, ale działa tylko na małych zestawach podgrafów (a nie na całym wykresie internetowym) i jest zależny od zapytania. Podwykresy są uszeregowane według wag w centrach i autorytetach, z których pobierane i wyświetlane są strony o najwyższej randze.

Zobacz też

• Nauka rankingu : zastosowanie uczenia maszynowego do problemu rankingu