Matematicki fakultet

Univerziteta u Beogradu

Odsek za racunarstvo

Sistemi za pretrazivanje informacija
(Information Retrieval Systems)

Novembar 2006

Cilj kursa

Ovaj kurs je primeren talentovanim studentima cetvrte godine kao i studentima na postdiplomskim studijama iz sledecih oblasti: racunarstvo, informatika, informaticke nauke, lingvistika i interaktivni mediji.

Cilj samog kursa je da pripremi studente za dizajn, implementaciju i evaluaciju sistema za pretrazivanje informacija. Polaznici ce takodje steci opšte razumevanje u vezi internog funkcionisanja automatizovanih sistema pretrage kao i korisnicke interakcije s istima.

U širem smislu, namera je da se povezu nastavnici, studenti i istrazivaci s zajednickim interesom za kombinovanjem racunarstva s društvenim naukama koje se bave istrazivanjem interakcija izmedju ljudi i društva s informacijama.

 

Opis kursa

Ovaj kurs ce prodiskutovati teoriju i praksu pretrage teksta i bibliografskih informacija. Teme koje ce biti pokrivene ukljucuju automatsko indeksiranje, statisticke i lingvisticke modele, klasifikaciju teksta, Bulovske i probabilisticke pristupe indeksiranju, formulaciji upita i rangiranju outputa, filtraciju i usmeravanje informacija, detekciju i pracenje tematika, kao i metrike efikasnosti pretrage (relevantnost, korisnost, kvantitet laznih alarma). Tehnike za poboljšanje efikasnosti pretrage diskutovane u ovom kursu ukljucuju fidbek o relevantnosti, reformulaciju upita, leksikone, ekstrakciju koncepata i automatsku sumarizaciju. Eksperimentalni algoritmi (Text Retrieval Conferences (TREC)) i savremeni sistemi za pretrazivanje (Google, Yahoo,, itd.) se takodje razmatraju u kontekstu gore spomenutih tematika.

 

Preduslov za pohadjanje kursa

Osnovni preduslov za buduce studente ovog kursa su dva sekvencijalna uvodna kursa iz programiranja (obicno opisana kao Programiranje 1 i 2). Za studente koji nisu studenti racunarstva, potrebno je ekvivalentno i dokumentovano poznavanje osnovnih kontrolnih struktura i OO struktura podataka u programiranju. Akademsko iskustvo koje je pozeljno za ovaj kurs ukljucuje familijarnost s elementarnom algebrom, osnovnim statistickim i probabilistickim metodama, elementarnom matematickom logikom i teorijom skupova, kontrolnim i strukturama podataka, kao i osnovno znanje u vezi korišcenja bibliotekarskih kataloga i internetskih sistema pretrazivanja.

Instruktor

Dr. Miroslav Martinovic
Kratka biografija

Doktorat matematike / racunarstva, 1993

Univerzitet u Beogradu / New York University.

Vanredni profesor racunarstva, 2000-2006, TCNJ

Vanredni profesor racunarstva i matematike, 1989-2000, Wagner College

Asistent profesor racunarstva i matematike, 1983-1988, Univerzitet u Beoradu

Istrazivac, 1989-2006.

Istrazivacki interes  
                        Upitnicki sistemi

Racunarska lingvistika
            Sistemi za pretrazivanje informacija
            Teorija igara

Veštacka inteligencija

                        Ekspertni sistemi
            Sponzori
                        NSF
                        DARPA
                        NIST

                        Microsoft

E-mejl adresa :

          mmmartin@tcnj.edu

 

Telefon :

         +1 609 771-2789.

 

Kancelarija : 

          Holman Hall 230.

Dan i vreme predavanja i vezbi:

Lekcije

3., 4., 10., 11., 17., 18., 24., i 25.-i novembar

petak 16-20

subota 10-2

Racunarska sala

Laboratorijske vezbe

360 minuta po nedelji.

Racunarska sala

Literatura za kurs:  

Glavni udzbenik

 

 

Modern Information Retrieval

R. Baeza-Yates, B. Ribeiro-Neto

Published by Addison Wesley,  2000.

ISBN 0-201-39829-X

Dodatna literature

 

 

1.

Introduction to Information Retrieval

Christopher D. Manning, Prabhakar Raghavan,

Hinrich Schütze

Cambridge University Press. 2007

http://www-csli.stanford.edu/cschuetze/information-retrieval-book.html

2.

Readings in Information Retrieval

Karen Sparck-Jones and Peter Willett (editors)

Morgan-Kaufmann Publishers, 1997.

 

3.

Natural Language Information Retrieval

Tomek Strzalkowski (editor)

Kluwer Academic Publishers, 1999.

 

4.

Information retrieval: data structures & algorithms

William B. Frakes and Ricardo Baeza-Yates

Englewood Cliffs, N.J.: Prentice Hall, 1992.

 

5.

Mathematical Foundations of Information Retrieval

by: S. Dominich

Published by Kluwer Publishing, 1999.

ISBN 0-7923-6861-4

 

Konsultacije :

Petak

Subota

14-16

3-5

Algoritam za izracunavanje završne ocene:

Prisustvovanje nastavi, ucešce u diskusijama i ulozeni napor

20%

Prezentacija tematika s kritikama 
         Lista clanaka / tematika
         Uputstvo za prezentacije i pisanje kritika

40%

Završni rad / projekat s prezentacijom i demonstracijom 
         Uputstvo u vezi završnog projekta s resursima

40%

(1)    Tematike iz kursa bice istrazivane kroz fokusirani pregled literature, diskusije, iskustva iz prakse korišcenja i evaluacije razlicitih algoritama za pretrazivanje na raznim kolekcijama teksta.
(2)    Kurs ce sadrzati periodicne domace zadatke i završni rad / projekat.
(3)    Prezentacije za vreme casa ce zahtevati solidnu pripremu koja ukljucuje nalazenje materijala izvan osnovnih materijala prikazanih u toku nastave.

Završni rad mora biti u obliku tehnickog clanka u vezi neke IR teme. Teme za projekat ukljucuju :
  - detekciju tematike pomocu ekstrakcije koncepata ili pracenje tematika
  - pivotirana normalizacija tezinskih koeficijenata u SMART sistemu.
  - dizajn i implementacija modula za ekspanziju upita
  - samouceci pronalazac koncepta
  - automatska sumarizacija
  - sub-kategorizacija dobijenog skupa dokumenata
  - upitnicki sistem.

 

Preliminarni raspored

 

 

Nedelja #1

Sistemi za pretrazivanje informacija - Uvod

Poglavlje 1 i 2

Lekcija

 

 

 

A. [ta su to sistemi za pretrazivanje informacija? 
B. Pojam relevantnosti 
   1.     Konceptualni 
   2.     Izracunljivi
   3.     Metricki - mere slicnosti dokumenata.
V. Specijalizacije sitema za pretrgu informacija:
   1.     Ad-hok upiti.
   2.     Filtracija i usmeravanje informacija
   3.     Detekcija i pracenje tematika
   4.     Upitni sistemi.
   5.     Automatska sumarizacija.
   6.     Stapanje informacija.
G. Konceptualni modeli sistema za pretragu.
   1.     Bulovski
   2.     Vektorski
   3.     Probabilisticki
   4.     Prošireni modeli
   5.     Modeli za obradu prirodnog jezika
D. Karakteristike tekst kolekcija.
   1.     Struktuirani tekst i bibliografski zapisi.
   2.     Multimedijalni dokumenti.
   3.     Kompletni tekst.

 

 

Nedelja #2

Koncepcijski modeli. Diskusija.



Studentska prezentacija: IR sistemi

 

 

 

A. Bulovski i prošireni Bulovski modeli; Pregled

            (instalacija)
B. Vektorski modeli; SMART, WAIS, Prise sistemi 
            (instalacija), 
V. Probabilisticki modeli; InQuery, Cheshire, Inktomi 
           (instalacija), 
G. Modeli za obradu prirodnog jezika. (DR.LINK; Evans; Topic)

 

 


 

 

Nedelja #3

Evaluacija

Poglavlje 3
Lekcija i diskusija

Vezba: evaluacija pretrazivackih sistema s Interneta korišcenjem pooling metode

 

 

 

A. Pretpostavke pri evaluaciji performansi pretrazivackih sistema. 
   1.     Potpuno automatizovani ili interaktivni sistemi? 
   2.     Ko odredjuje relevantnost? 
B. Evaluacione metrike 
   1.     Povracaj i preciznost 
   2.     Promašaji i lazne uzbune 
   3.     ROC krive 
   4.     Druge mere
V. Referentne kolekcije 
   1.     Klasicne kolekcije: Cranfield, CACM, ISI, INSPEC, ... 
   2.     Tipster/TREC

  3.    TDT kolekcije 
G. Evaluacione metodologije 
   1.     [ta se smatra dobrim IR eksperimentom? 
   2.     Eksperimentalni dizajn. 
   3.     Izbor kolekcija teksta. 
   4.     Izvodjenje eksperimenata i sakupljanje rezultata. 
   5.     Standardna analiza i sredstva za analizu. 
   6.     Graficko i tabularno prikazivanje rezultata. 
D. Standardne evaluacije i rezultati 
   1.     TREC 
   2.     MUC 
   3.     SUMMAC 
   4.     TDT 

 

Nedelje #4 & 5 

Automatsko indeksiranje

Poglavlja 7, 8 + ostala literatura 


2 lekcije i studentske prezentacije

 

 

A. Osnovne osobine jezickih kolekcija. 
   1.     Statisticke distribucije; Zipf-ov zakon, 
   2.     Stohasticki modeli za jezik. 
   3.     Meta podaci i anotacioni jezici (SGML, HTML, XML) 
   4.     Multimediji 
   5.     Potpuni tekst ili bibliografski zapis. 
B. Strukture podataka i fajlova u pretrazivackim sistemima. 
   1.     Inverzni fajlovi. 
   2.     Signaturni fajlovi. 
   3.     Druge fajlovske strukture (PAT drveta, Grid fajlovi, Hash). 
   4.     Sistemi pretrage zasnovani na bazama podataka. 
V. Indeksiranje. 
   1.     Pasaz ili citav dokumenat. 
   2.     Algoritmi segmentacije 
   3.     Salton-ov algoritam za automatsko indeksiranje.
G. Indeksiranje i memorija. 
   1.     Kompresija indeksa. 
   2.     Automatizovano hajpertekst linkovanje. 
   3. Poziciona informacija u indeksima. 
D. Analiza teksta (studentske prezentacije & diskusija) 
   1.     Stop liste i algoritmi za nalazenje korena reci. 
   2.     Fraze i kolokacije 
   3.     Eliminacija dvoznacnosti.
\. Indeksiranje motivisano lingvistikom 
           (studentske prezentacije) 
   1.     Pronalazenje korena reci i morfološka analiza. 
   2.     Anotacija vrste reci i sintaksna analiza 
   3.     Prepoznavanje frazi i varijanti 
   4.     Ekstrakcija koncepata 
   5.     Teme: MUC, SCISOR, FERRET, NLIR 
E. Konstrukcija leksikona 
           (studentske prezentacije) 
   1.     Kolekcijsko-senzitivni leksikoni. 
   2.     Manuelno razvijeni leksikoni 
            (WordNet, Snomed, MESH, LCSH). 
   3.     Automatska derivacija leksikona. 
           a. Asocijacije termina
               (Spark Jones, Grefenstette, Strzalkowski). 
           b. Latentno semanticko indeksiranje.

 

 

Nedelja #6

Upitni jezici i operacije

Poglavlja 4 i 5 + ostala literature

Lekcija 

 

 

 

A.  Upitni kljucevi 
B.   Upiti po principu torbe reci 
V.   Bulovski upiti
G.   Poboljšani torba reci upiti 
D.   Fidbek o relevantnosti 
\.  Ekspanzija upita i interakcija s korisnikom 
E.   Višejezicki sistemi za pretrazivanje informacija

 

 

Nedelja #7 

Moduli za obradu prirodnih jezika (NLP Tools): Parseri (parser za engleski jezik)

Prezentacije i kritike s demonstracijama 

clanci : Papers/APParser/manual.ps, Papers/APParser/APParser.htm
 

 

 

Nedelja #8 

Moduli za obradu prirodnih jezika: Elektronski leksikoni (WordNet)

Prezentacije i kritike s demonstracijama Dokumentacija: http://www.cogsci.princeton.edu/cwn/doc.shtml 
Resurs direktorijum: cmmmartin/ CMSC485/Papers/WordNet/

 

 

 

Nedelja #9 

Automatska klasifikacija

Lekcija i prezentacije
Projekat: detekcija tematika i ekstrakcija koncepta

 

A. Manuelna klasifikacija. 
   1.     Klasifikacione šeme. 
   2.     Zadatak manuelne klasifikacije. 
B. Automatizovana klasifikacija - filtracija i usmeravanje informacije 
   1.     Staticni upiti i profili 
   2.     Usmeravanje informacija 
   3.     Filtracija informacija.
V. Automatizovana klasifikacija - grupisanje dokumenata. 
   1.     Hipoteza klastera (grupa). 
   2.     Hijerarhijska klasifikacija 
           a. Jedinstveni link. 
           b. Potpuni link. 
   3.     Heuristicka klasifikacija. 
           a.   Rocchio-ov metod. 
           b.  Datola metod. 
           v.  Rasipanje-skupljanje. 
G. Korišcenje klasifikacije za pretragu. (student presentation) 
   1. Bibiografska klasifikacija kao organizacioni princip 
   2. Yahoo i WWW klasifikacija. 
   3. Cheshire 2-fazna pretraga. 
D. Detekcija i pracenje tematika

 

 

Nedelje #10 & 11 

Upitnicki sistemi

Student/instruktor - ska prezentacija; Diskusija

Vezba: TREC Q&A task

 

 

 

A. Klasicni Q&A problem (studentska prezentacija) 
B.  Internet Q&A moduli 
V.  Interaktivni Q&A 
     Projekti: MURAX; AskJeeves

     Projekti: AnswerBus, QASTIIR 

 

Nedelje #12 & 13 

Pretraga Interneta


Instruktor: uvod 
Studentska prezentacija

 

 

A. O mrezama i hajper tekstu
B. Tipovi pretraznih sistema na mrezama
V. Diskusija o specificnim sistemima iz prošlost ii sadašnjosti 
    1.     Alta Vista 
    2.     Infoseek 
    3.     Yahoo 
    4.     Google

 

 

 

 

Prezentacije projekata s demonstracijama

Nedelja #14

Dopunska literatura:

1.   Gerard Salton. Automatic text processing: the transformation, analysis, and retrieval of information by computer. Reading, Mass. : Addison-Wesley, 1988.

2.   C. J. van Rijsbergen. Information retrieval. London : Butterworths, 1975.

3.   Text Retrieval Conference (TREC) proceedings

4.   ACM SIGIR Conference Proceedings

5.   Technical journals:

a.         Information Processing & Management, Pergamon Press

b.         Information Retrieval, Kluwer Academic Publishers

c.         Computational Linguistics, MIT Press

d.         Journal of the ASIS

 

Prilošci :

Lista clanaka / tematika

Tematika 

clanci i demonstracije

Prezentor(i)

Datum prezentacije 

1.   Obrada prirodnog jezika - raspoloziva sredstva - SMART sistem za pretragu informacija: Prezentacija clanka i demonstracija

clanak: SMART/Tutorial/Smart/hands.html

 

10. 11. 2006.

2.   Pretrazivanje po Internetu: Google-ov uspeh 

Paper : Papers/Google/Google.pdf

 

11. 11. 2006.

3.   Ekstenzija vektorskog modela: latentno semanticko indeksiranje

clanak: Papers/LSI.ppt

 

17. 11. 2006.

4.  Tehnike anotacije teksta

    Paper : Papers/TAT/TAT.ppt

 

17. 11. 2006.

5.   Pretrazivanje slika i grafika

clanak: Papers/ImageIR/ImageRetrieval.html

 

18. 11. 2006.

6.   Leksikoni, pretrazivacki sistemi i automatska   derivacija: WordNet kao primer

     clanci i resursi: http://wordnet.princeton.edu/ 

 Papers/IRThesauri/AutoDerofThes.ppt

 

18. 11. 2006.

7.   Fuzzy logika i model za pretrazivacki sistem

     clanak: Papers/FuzzyLogicIRM/FuzzyLogic.ppt

 

24. 11. 2006.

8.  Automatska sumarizacija

clanak: Papers/Summarization/AutoSum.ppt

 

24. 11. 2006.

9.  MURAX i ASKJEEVES

clanak: Papers/MurAskJ/MurAskJ.ppt

 

25. 11. 2006.

10.   Detekcija i pracenje tematika

clanak: Papers/TDT/TDT2.ppt

 

25. 11. 2006.

Uputstvo za pisanje kritika

Kritika ne treba da je duza od jedne stranice. Nešto manje od stranice je takodje prihvatljivo. Svrha kritike nije sumarizacija clanka vec izbor jedne ili dve znacajne i interesantne tacke iz rada i komentar o istom(ima).

Pozitivni primeri:

  • Za koji problem ovaj clanak nudi rešenje i koje su jake i slabe strane algoritma koji se koristi?
  • Da li je evaluacija metode bila fer? Da li rezultati evaluacije idu u prilog navedenih tvrdnji i ciljeva clanka?
  • Da li opisani metod izgleda dovoljno solidan i pouzdan da bi se koristio u svakodnevnim aplikacijama? Zašto ili zašto ne? U kojim bi aplikacijama ovaj metod bio posebno primenljiv?
  • Koje korisne ideje iz clanka a u vezi formulacije problema, predlozenog rešenja, algoritma ili istrazivacke metode mogu da se iskoriste u nekim drugim kontekstima?
  • [ta bi bio najprirodniji projekat za nastavak predlozenog rada i zašto?
  • Da li su pretpostavke iz rada valjane ili ne?
  • Koje je vazne probleme iz ove oblasti clanak posebno osvetlio i kako?
  • Da li je clanak predstavio dovoljno jasan i detaljan opis predlozenog metoda koji bi sada mogao da se i implementira? Ako to nije slucaj, u vezi cega su potrebna pojašnjenja ili dopunski detalji?

Kritika mora da bude printovana. Ona treba da sadrzi naslov clanka, ime njegovog(ih) autora, zajedno s imenom prezentora na vrhu dokumenta.

Treba izbegavati vrednosne sudove bez potpore (napr. ‘dopalo mi se što je...’ ili ‘Ne slazem se...’ bez supstance). Ovakvi sudovi su opravdani samo ako se mogu poduprti cinjenicama iz samog clanka, iz nekog drugog autoritativnog izvora ili se mogu izvesti nekim logickim rasudjivanjima.

Komentari u vezi stila pisanja moraju se odvojiti od komentara koji se ticu tehnickog sadrzaja clanka.

Uputstvo u vezi stila prezentacije

Duzina              :           60-80 minuta

Medijum                       :           PowerPoint, HTML, ili PDF slajdovi.

 

 

Uputstvo u vezi stila prezentacije kritike clanaka

Duzina              :           20-25 minuta

(15-20 minuta prezentacije s 5-10 minuta diskusije)

Medijum                       :           PowerPoint, HTML, ili PDF slajdovi.

Primedba u vezi pripremljenosti za prezentacije drugih studenata utice na ocenu:

(1)        Svi clanci iz liste moraju da se procitaju od strane svakog studenta ovog kursa.

(2)        Diskusija posle prezentacija i kritika sluzi da demonstruje da je student procitao clanak.

(3)        Ucešce u diskusijama i nivo kompetentnosti u istima direktno ce uticati na 20% konacne ocene (stavka: Prisustvovanje nastavi, ucešce u diskusijama i ulozeni napor).


Sugestije u vezi završnog projekta / rada

 

1.      Dizajn i implementacija pretrazivackog sistema

1.         Izbor kolekcije dokumenata.

2.         Anotacija / unifikacija postojecih anotacija u dokumentima.

3.         Priprema racunarskog sistema za kolekciju dokumenata.

4.         Kreacija specifikacijskih fajlova za SMART sistem.

5.         Procesiranje kolekcije dokumenata korišcenjem SMART sistema i specifikacijskih fajlova iz 4 (Compile-time).

6.         Egzekucija pretraga po datim upitima korišcenjem SMART sistema po specifikacijskim fajlovima iz 4 (Run-time).

7.         Referisanje o fazama 1.-6. i evaluacija performansi izgradjenog sistema za pretragu informacija.

 

2.      Istrazivacki projekat

Ovaj projekat se bavi istrazivanjem nekog otvorenog problema iz oblasti pretrazivackih sistema. On takodje podrazumeva pripremu odgovarajuceg istrazivackog rada za publikovanje koji ce dati pregled postojecih pristupa, njihovih slabosti i vrlina, kao i predlog i obrazlozenje autorovog novog i originalnog pristupa datom problemu.

 

1.         Algoritmi za obradu prirodnih jezika korišteni u pretrazivackim  sistemima

 

2.         Upitnicki sistemi
3.         Evaluacija performansi sistema za pretragu informacija
4.         Metode za automatsku sumarizaciju
5.         Automatizovana klasifikacija dokumenata
6.         Mašinsko ucenje u pretrazivackim sistemima
7.         Kros-jezicna pretraga informacija
8.         Kros-jezicna sumarizacija
9.         Multi-medijska pretraga (govor, video, Internet)
10.       Stapanje (fuzija) informacija

M. Martinovic


12. 10. 2006