Boole'owski model wyszukiwania informacji - Boolean model of information retrieval

(Standardowy) Boole'owski model wyszukiwania informacji (BIR) jest klasycznym modelem wyszukiwania informacji (IR) i jednocześnie pierwszym i najczęściej stosowanym modelem. Jest używany przez wiele systemów IR do dziś. BIR opiera się na logice Boole'a i klasycznej teorii mnogości, ponieważ zarówno dokumenty, które mają być przeszukiwane, jak i zapytanie użytkownika, są rozumiane jako zbiory terminów (model bag-of-words ). Pobieranie opiera się na tym, czy dokumenty zawierają terminy zapytania.

Definicje

Keyword to słowo lub wyrażenie , które mogą być łodygach , opisując lub charakteryzowania dokumentu, takich jak hasła do danego artykułu w czasopiśmie. Pozwolić

{\ Displaystyle T = \ {t_ {1}, t_ {2} \ \ ldots \ t_ {m} \}}

być zbiorem wszystkich takich terminów indeksowych.

Dokument jest dowolny podzbiór . Pozwolić ${\ Displaystyle T}$

{\ Displaystyle D = \ {D_ {1} \ \ ldots \ D_ {n} \}}

być zbiorem wszystkich dokumentów.

Zapytanie jest logiczna ekspresja w normalnych postać: ${\textstyle Q}$

{\ Displaystyle Q = (W_ {1} \ \ Lor \ W_ {2} \ \ Lor \ \ cdots) \ Ziemia \ \ cdots \ \ Ziemia \ (W_ {i} \ \ Lor \ W_ {i + 1} \ \lub \ \cdots )}

gdzie jest prawdziwe dla kiedy . (Równoważnie można wyrazić w rozłącznej postaci normalnej .)

{\textstyle W_{i}}

D_{j}

{\ Displaystyle t_ {i} \ w D_ {j}}

{\textstyle Q}

Staramy się znaleźć komplet dokumentów, które spełniają . Ta operacja nazywa się

pobieraniem i składa się z następujących dwóch kroków:

{\textstyle Q}

1. Dla każdego w , znajdź zestaw dokumentów, które spełniają :

{\textstyle W_{j}}

{\textstyle Q}

{\textstyle S_{j}}

{\textstyle W_{j}}

{\ Displaystyle S_ {j} = \ {D_ {i} \ mid W_ {j} \}}

2. Wtedy zbiór dokumentów spełniających Q określa się wzorem:

{\ Displaystyle (S_ {1} \ filiżanka S_ {2} \ filiżanka \ cdots) \ czapka \ cdots \ czapka (S_ {i} \ filiżanka S_ {i + 1} \ filiżanka \ cdots)}

Przykład

Niech zbiór oryginalnych (prawdziwych) dokumentów będzie na przykład

{\ Displaystyle O = \ {O_ {1}, \ O_ {2}, \ O_ {3} \}}

gdzie

${\textstyle O_{1}}$ = „Zasada Bayesa: zasada, zgodnie z którą przy szacowaniu parametru należy wstępnie założyć, że każda możliwa wartość ma równe prawdopodobieństwo (jednorodny rozkład a priori).”

${\textstyle O_{2}}$ = " Bayesowska teoria decyzji : Matematyczna teoria podejmowania decyzji, która zakłada funkcje użyteczności i prawdopodobieństwa, i zgodnie z którą aktem do wyboru jest akt Bayesa, tj. taki, który ma najwyższą subiektywną oczekiwaną użyteczność. moc, z jaką można podejmować każdą decyzję, ta procedura byłaby najlepszym sposobem na podjęcie jakiejkolwiek decyzji”.

${\textstyle O_{3}}$ = „ Epistemologia bayesowska : teoria filozoficzna, która utrzymuje, że epistemiczny status zdania (tj. jak dobrze jest udowodnione lub dobrze ugruntowane) najlepiej mierzyć prawdopodobieństwem i że właściwy sposób rewizji tego prawdopodobieństwa jest podany przez warunkowość bayesowską lub podobną. Bayesowski epistemolog wykorzystałby prawdopodobieństwo do zdefiniowania i zbadania relacji między pojęciami, takimi jak status epistemiczny, wsparcie lub moc wyjaśniająca”.

Niech zbiór terminów będzie następujący: ${\textstyle T}$

T=\{t_{1}={\text{zasada Bayesa}},t_{2}={\text{prawdopodobieństwo}},t_{3}={\text{podejmowanie decyzji}}, t_{4}={\text{epistemologia bayesowska}}\}

Następnie zestaw dokumentów wygląda następująco: ${\textstyle D}$

{\ Displaystyle D = \ {D_ {1}, \ D_ {2}, \ D_ {3} \}}

gdzie

{\ Displaystyle {\ zacząć {wyrównany} D_ {1}& = \ {{\ tekst {prawdopodobieństwo}}, \ {\ tekst {zasada Bayesa}} \} \ \ D_ {2}& = \ {{\ tekst {prawdopodobieństwo}},\ {\text{podejmowanie decyzji}}\}\\D_{3}&=\{{\text{prawdopodobieństwo}},\ {\text{epistemologia bayesowska}}\}\end{wyrównane }}}

Niech zapytanie będzie: ${\textstyle Q}$

{\ Displaystyle Q = {\ tekst {prawdopodobieństwo}} \ ziemia {\ tekst {podejmowanie decyzji}}}

Następnie, aby pobrać odpowiednie dokumenty:

W pierwszej kolejności uzyskuje się (odzyskiwane) następujące komplety i dokumenty : ${\textstyle S_{1}}$ ${\textstyle S_{2}}$ ${\textstyle D_{i}}$ ${\ Displaystyle {\ zacząć {wyrównany} S_ {1} i = \ {D_ {1}, \ D_ {2}, \ D_ {3} \} \ \ S_ {2}& = \ {D_ {2} \ }\end{wyrównany}}}$
Wreszcie, następujące dokumenty są pobierane w odpowiedzi na: ${\textstyle D_{i}}$ ${\textstyle Q}$ ${\ Displaystyle Q: \ {D_ {1}, \ D_ {2}, \ D_ {3} \} \ \ cap \ \ {D_ {2} \} \ = \ \ {D_ {2} \}}$

Oznacza to, że oryginalny dokument (odpowiadający ) jest odpowiedzią na . ${\textstyle O_{2}}$ ${\textstyle D_{2}}$ ${\textstyle Q}$

Oczywiście, jeśli istnieje więcej niż jeden dokument z tą samą reprezentacją, każdy taki dokument jest pobierany. Takie dokumenty są nie do odróżnienia w BIR (innymi słowy równoważne).

Zalety

Czysty formalizm
Łatwy do wdrożenia
Intuicyjna koncepcja
Jeśli wynikowy zestaw dokumentów jest albo za mały, albo za duży, jest bezpośrednio jasne, którzy operatorzy wytworzą odpowiednio większy lub mniejszy zestaw.
Daje (ekspertom) użytkownikom poczucie kontroli nad systemem. Natychmiast staje się jasne, dlaczego dokument został pobrany z powodu zapytania.

Niedogodności

Dokładne dopasowanie może spowodować pobranie za mało lub za dużo dokumentów
Trudno przetłumaczyć zapytanie na wyrażenie logiczne
Wszystkie terminy mają jednakową wagę
Bardziej przypomina pobieranie danych niż wyszukiwanie informacji
Pobieranie oparte na binarnych kryteriach decyzyjnych bez pojęcia częściowego dopasowania
Brak rankingu dokumentów (brak skali ocen)
Potrzeba informacji musi zostać przetłumaczona na wyrażenie logiczne, które większość użytkowników uważa za niewygodne
Zapytania logiczne formułowane przez użytkowników są najczęściej zbyt uproszczone
Model często zwraca za mało lub za dużo dokumentów w odpowiedzi na zapytanie użytkownika

Struktury danych i algorytmy

Z czysto formalnego matematycznego punktu widzenia BIR jest prosty. Z praktycznego punktu widzenia należy jednak rozwiązać kilka dalszych problemów, które dotyczą algorytmów i struktur danych, takich jak np. wybór terminów (wybór ręczny lub automatyczny lub oba), stemming , tablice haszujące , odwrócona struktura

plików , i tak dalej.

Zestawy haszujące

Inną możliwością jest użycie zestawów skrótów . Każdy dokument jest reprezentowany przez tablicę mieszającą, która zawiera każdy pojedynczy termin tego dokumentu. Ponieważ rozmiar tablicy mieszającej zwiększa się i zmniejsza w czasie rzeczywistym wraz z dodawaniem i usuwaniem terminów, każdy dokument zajmie znacznie mniej miejsca w pamięci. Spowoduje jednak spowolnienie wydajności, ponieważ operacje są bardziej złożone niż w przypadku wektorów bitowych . W najgorszym przypadku wydajność może spaść z O( n ) do O( n ² ). W przeciętnym przypadku spowolnienie wydajności nie będzie dużo gorsze niż wektorów bitowych, a wykorzystanie przestrzeni jest znacznie bardziej efektywne.

Plik podpisu

Każdy dokument może być podsumowany przez filtr Bloom reprezentujący zestaw słów w tym dokumencie, przechowywany w ciągu bitów o stałej długości, zwanym podpisem. Plik podpisu zawiera jeden taki nałożony ciąg bitów

kodu dla każdego dokumentu w kolekcji. Każde zapytanie może być również podsumowane przez filtr Bloom reprezentujący zestaw słów w zapytaniu, przechowywany w ciągu bitów o tej samej stałej długości. Ciąg bitów zapytania jest testowany pod kątem każdej sygnatury.

Podany plik podpisu jest używany w BitFunnel .

Odwrócony plik

Plik indeksu odwróconego składa się z dwóch części: słownika zawierającego wszystkie terminy użyte w kolekcji oraz dla każdego odrębnego terminu indeks odwrócony, który zawiera listę wszystkich dokumentów, w których występuje ten termin.

Bibliografia

Laszkari, AH; Mahdavi, F.; Ghomi, V. (2009), "A Boolean Model in Information Retrieval for Search Engines", 2009 Międzynarodowa Konferencja Zarządzania Informacją i Inżynierii , s. 385-389, doi : 10.1109/ICIME.2009.101 , ISBN 978-0-7695-3595-1

Languages

In other projects