Introduction to Information
Retrieval

Wyszukiwanie Informacji



Wyszukiwanie informacji (IR) jest
wyszukaniem obiektów (zwykle
dokumentów) niestrukturalnych (zwykle
tekstu), które odpowiadają

potrzebie

informacyjnej

z dużych

kolekcji

(zwykle

pamiętanych w komputerach).

Introduction to Information
Retrieval

Niestrukturalne (tekst) vs.
strukturalne (bazy danych) dane
w 1996

Introduction to Information
Retrieval

Niestrukturalne (tekst) vs.
strukturalne (bazy danych) dane
w 2009

Introduction to Information
Retrieval

Dane niestrukturalne w 1680
roku



Które sztuki Szekspira zawierają słowa
Brutus AND Caesar ale NOT Calpurnia?



Można przeszukać wszystkie sztuki Szekspira
dla Brutus and Caesar następnie usunąć linie
zawierające Calpurnia?



Dlaczego nie jest to dobry sposób?



Bardzo wolne (dla dużych zbiorów)



NOT Calpurnia nie jest trywialne



Inne operacje (np.: znaleźć słowo Romans blisko
countrymen) niemożliwe do wykonania



Ranking (zwracanie najlepszych dokumentów)



Dalsze wykłady

Introduction to Information
Retrieval

Term

-dokument

występowanie

Antony and Cleopatra

J ulius Caesar The Tempest

Hamlet

Othello

Macbeth

Antony

Brutus

Caesar

Calpurnia

Cleopatra

mercy

worser

1 jeśli sztuka
zawiera słowo, 0 w
przeciwnym
przypadku

Brutus AND Caesar ale
NOT Calpurnia

Introduction to Information
Retrieval

Wektory incydencji



Mamy więc 0/1 wektory dla każdego
termu.



Budowa odpowiedzi na pytanie: wykonać
dla Brutus, Caesar and Calpurnia
(dopełnione)  bitowe AND.



110100 AND 110111 AND 101111 =
100100.

Introduction to Information
Retrieval

Odpowiedzi na pytanie



Antony and Cleopatra, Act III,
Scene ii

Agrippa [Aside to DOMITIUS ENOBARBUS]: Why, Enobarbus,
When Antony found Julius Caesar dead,
He cried almost to roaring; and he wept
When at Philippi he found Brutus slain.



Hamlet, Act III, Scene ii

Lord Polonius: I did enact Julius Caesar I was killed i' the
Capitol; Brutus killed me.

Introduction to Information
Retrieval

Podstawowe założenia przy
wyszukiwaniu informacji

 Kolekcja

: Ustalony zbiór dokumentów



Cel

: Wyszukanie dokumentów

zawierających informację relewantną do

potrzeby informacyjnej użytkownika i

pomóc użytkownikowi zrealizować

zadanie

Introduction to Information
Retrieval

Klasyczny model wyszukiwania

Corpus

Zadanie

Potrzeba

inform.

Pytanie

Postać

Verbalna

Results

SEARCH

ENGINE

Query

Refineme

Get rid of mice in a
politically correct
way

Info about removing mice

without killing them

How do I trap mice alive?

mouse trap

Misconception?

Mistranslation
?

Misformulation?

Introduction to Information
Retrieval

Jak dobre są wyszukane
dokumenty?



Precyzja

: Ułamek wyszukanych

dokumentów, który jest relewantny do
potrzeby informacyjnej użytkownika



Kompletność

: Ułamek relewantnych

dokumentów w kolekcji, które zostały
wyszukane



Dokładniejsze definicje i miary w
przyszłości

Introduction to Information
Retrieval

Większe kolekcje



Rozpatrzmy N = 1 million documentów,
każdy z około 1000 słowami.



Średnio 6 bajtów/słowo licząc
spacje/interpunkcję.



6GB danych w dokumentach.



Niech będzie M = 500K

różnych

termów w

tej kolekcji.

Introduction to Information
Retrieval

Nie możemy zbudować tablicy



500K x 1M tablica ma pół -tryliona 0 i 1.



Ale ma ona nie więcej niż milion 1.



Tablica jest bardzo rzadka.



Jaka jest lepsza reprezentacja?



Możemy pamiętać tylko pozycje 1.

Dlaczego?

Introduction to Information
Retrieval

Indeks odwrotny (lista
inwersyjna)



Dla każdego termu t, musimy pamiętać
listę wszystkich dokumentów, które
zawierają t.



Oznaczyć każdy przez docID - kolejny numer
dokumentu



Czy możemy użyć do tego tablic o stałej
długości?

Brutus

Calpurnia

Caesa
r

16 57 132

4 11 31 45 173

Co się stanie jeśli słowo Caesar
będzie dodane do dokumentu
14?

174

54101

Introduction to Information
Retrieval

Indeks odwrotny



Potrzebujemy listy wystąpień o zmiennej
długości



Na dysku ciągi wystąpień są normalne i
najlepsze



W pamięci użyjemy połączone listy lub tablice
zmiennej dł.



Kompromis rozmiar/łatwość wstawiania

Słownik

Wystąpieni
awystostin
gs

Sortowane po docID (w przyszłości).

wystąpienie

Brutus

Calpurnia

Caes
ar

16 57 132

4 11 31 45 173

174

54101

Introduction to Information
Retrieval

Tokenizer

Strumień tokenów.

FriendsRomansCountrymen

Konstrukcja indeksu
odwrotnego

Moduły

lingwistyczne

Zmodyfikowane tokeny

friend roman countryman

Indekser

Indeks odwrotny.

friend

roman

countryman

Indeksowane
dokumenty

Friends, Romans, countrymen.

Introduction to Information
Retrieval

Kroki indeksera: Sekwencja
Tokenów



Sekwencja par (Zmodyfikowany token,

Dokument ID)

I did enact Julius

Caesar I was killed

i' the Capitol;

Brutus killed me.

Dok 1

So let it be with

Caesar. The noble

Brutus hath told you

Caesar was ambitious

Dok 2

Introduction to Information
Retrieval

Kroki indeksera: Sortowanie



Sortowanie wg termów



Następnie wg docID

Podstawowy krok indeksera

Introduction to Information
Retrieval

Kroki indeksera: Słownik &
Wystąpienia



Wielokrotne

wystąpienie termu w

dokumencie jest

łączone.



Podział na Słownik i

wystąpienia



Częstość dokumentów

jest dodawana.

później

Introduction to Information
Retrieval

Co obciąża pamięć?

Pointers

Term

liczni

później:
•Jak
indeksować
efektywnie?
•Ile pamięci
potrzebujemy
?

Listy

docID

Introduction to Information
Retrieval

Indeks jest zbudowany



Jak przetwarzamy pytanie?



Później – jakie rodzaje pytań możemy
przetwarzać?

obecni

Introduction to Information
Retrieval

Przetwarzanie pytań: AND



Rozpatrzmy przetwarzanie pytania:

Brutus AND Caesar



Znajdź Brutus w Słowniku;



Wyszukaj jego wystąpienia.



Znajdź Caesar w słowniku;



Wyszukaj jego wystąpienia.



“Merge” te dwa wystąpienia:

128

1
3

Brutus

Caesar

Introduction to Information
Retrieval

Łączenie



Przejdź przez oba wystąpienia
jednocześnie, w czasie liniowym od
całkowitej liczby wejść wystąpień

128

Brutus

Caesar

Jeśli długości list list są x i y, to łączenie wymaga O(x+y)
operacji.

Decydujące: wystąpienia sortowane wg docID.

Introduction to Information
Retrieval

Przecięcie dwóch list wystąpień
( “merge” algorytm)

Introduction to Information
Retrieval

Boolowskie pytania: Dokładne
dopasowanie



Boolowski model

wyszukiwania może odpowiadać

na pytania będące wyrażeniami Boolowskimi:



Boolowskie Pytania to pytania używające AND, OR and
NOT do łączenia termów



Przegląda każdy dokument jako zbiór słów



Jest precyzyjny: dokument spełnia warunki lub nie.



Być może najprostszy model do budowy systemów
wyszukiwania



Główne komercyjne narzędzie wyszukiwawcze
przez 3 dekady.



Wiele systemów dalej używa model Boolowski:



Email, library catalog, Mac OS X Spotlight

Introduction to Information
Retrieval

Przykład: WestLaw

http://www.westlaw.com/



Największy komercyjny (użytkownicy płacą)
prawny serwis wyszukiwawczy (start 1975;
ranking dodany 1992)



Dziesiątki terabajtów danych; 700,000 użytk.



Większość użytkowników ciągle używa
boolowskie pytania



Przykładowe pytanie:



What is the statute of limitations in cases
involving the federal tort claims act?



LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3
CLAIM



/3 = w 3 słowach, /S = w tym samym zdaniu

Introduction to Information
Retrieval

Przykład: WestLaw

http://www.westlaw.com/



Kolejne pytanie przykładowe:



Requirements for disabled people to be able to access
a workplace



disabl! /p access! /s work-site work-place
(employment /3 place



Uwaga SPACE jest dysjunkcją nie koniunkcją!



Długie precyzyjne pytana; operatory bliskości;
stopniowo rozbudowywane; inaczej niż web
search



Wielu profesionalistów ciągle lubi wyszukiwanie
boolowskie



Wiesz dokładnie co dostajesz



Ale to nie znaczy, że to dobrze pracuje….

Introduction to Information
Retrieval

Łączenie

Co będzie z wyrażeniem boolowskim?
(Brutus OR Caesar) AND NOT
(Antony OR Cleopatra)



Czy możemy zawsze łączyć w „liniowym”
czasie?



Liniowym od czego?



Jak możemy ulepszać?

Introduction to Information
Retrieval

Optymalizacja zapytań



Jaki jest najlepszy porządek
przetwarzania zapytań?



Rozpatrzmy pytanie AND z n termami.



Dla każdego z n termów, weź jego
wystąpienia, następnie AND wszystkich.

Brutus

Caesar

Calpurnia

16 21 34

8 16 32 64 128

13 16

Pytanie:

Brutus AND Calpurnia AND Caesar

Introduction to Information
Retrieval

Przykład optymalizacji pytania



Przetwarzaj w porządku rosnacej częstości:



Startuj od najmniejszego zbioru, następnie
przechodź dalej.

Dlatego pamiętamy

częstości dok. słowniku

Przetwarzaj pytanie jako (Calpurnia AND Brutus) AND Caesar.

Brutus

Caesar

Calpurnia

16 21 34

8 16 32 64 128

13 16

Introduction to Information
Retrieval

Bardziej ogólna optymalizacja



Np.:, (madding OR crowd) AND
(ignoble OR strife)



Weź częstości dla wszystkich termów.



Oceń rozmiar każdego OR przez sumę
ich częstości dokumentów.



Przetwarzaj wg rosnącego rozmiaru OR.

Introduction to Information
Retrieval

Co poza szukaniem termów?



Co z frazami?



Stanford University



Bliskość: znajdź Gates NEAR Microsoft.



Potrzebny jest indeks do pamiętania pozycji
informavcji w dokumentach.



Strefy w dokumentach: wyszukaj
dokumenty z (author = Ullman) AND (text
contains automata).

Introduction to Information
Retrieval

Pamiętanie cech dokumentów



1 vs. 0 wystąpień termu



2 vs. 1 wystąpienie



3 vs. 2 wystąpienia, itd.



Zwykle więcej to lepiej



Potrzebujemy informacje o częstościach
termów w dokumentach

Introduction to Information
Retrieval

Ranking wyników
wyszukiwania



Pytania boolowskie dają w wynik zbiór
dokumentów.



Często potrzebujemy ranking/grupowanie
wyników



Potrzebna miara odległości pytania od każdego
dokumentu.



Musimy decydować czy dokumenty są
oddzielone czy ich grupy pokrywają pewne
aspekty pytania.

Introduction to Information
Retrieval

Wyszukiwanie informacji a bazy
danych:
Strukturalne a niestrukturalne
dane



Strukturalne dane zwykle podają
informacje w „tablicach”

Employee

Manager

Salary

Smith

Jones

50000

Chang

Smith

60000

50000

Ivy

Smith

Zwykle pozwalają na pytania o zakres numeryczny i
dokładne szukanie dla tekstu, np,
Salary < 60000 AND Manager = Smith.

Introduction to Information
Retrieval

Niestrukturalne dane



Zwykle chodzi o dowolny tekst.



Można



Słowa kluczowe w pytaniach i operatory



Bardziej skomplikowane koncepcyjnie pytania
np.:,



Wyszukaj wszystkie web pages na temat drug abuse



Klasyczny model przeszukiwania
dokumentów tekstowych

Introduction to Information
Retrieval

Semi-strukturalne dane



Faktycznie prawie nie ma danych
niestrukturalnych



Np.: ten slajd ma dwie oddzielnie
oznaczone strefy Tytuł i Treść



Daje to możliwość „semi-strukturalnego”
jak np.:



Tytuł zawiera data AND Treść zawiera search

… Nie mówimy obecnie o strukturze

lingwistycznej

Introduction to Information
Retrieval

Bardziej zaawansowane
wyszukiwanie semi-
strukturalne



Tytuł jest o Object Oriented Programming
AND Autor jest jak nie*czak



gdzie * to wild-card operator



Problemy:



Jak przetwarzać „o”?



Jak tworzyć ranking wyników?



Wyszukiwanie dla XML później

Introduction to Information
Retrieval

Klastering (grupowanie),
klasyfikacja i ranking



Grupowanie:

Dla danego zbioru

dokumentów, utworzyć grupy bazując na
zawartości dokumentów.



Klasyfikacja:

Dla danego zbioru tematów i

nowego dokumentu D, zdecydować do
którego tematu( tematów) D należy.



Ranking:

Tworzenie najlepszego porządku

dokumentów np.: dla zbioru wyników
wyszukiwania.

Introduction to Information
Retrieval

Web i jego wyzwania



Niezwykłe i rozproszone dokumenty



Niezwykli i rozproszeni użytkownicy, pytania,
potrzeby informacyjne



Poza termami, idee dotyczące sieci
społecznych



Analiza linków, przetwarzanie strumieniowe

...



Jak pracują search engines (silniki
wyszukiwawcze)? Jak je doskonalić?

Introduction to Information
Retrieval

Bardziej zaawansowane
wyszukiwanie informacji



Wyszukiwanie wielojęzyczne Cross-
language information retrieval (CLER)



Odpowiadanie na pytania



Streszczenia



Eksploracja tekstu (Text mining)



…

Document Outline

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40

Sys Inf 03 Manning w 01

Document Outline