Zoekmachines LIX019B05 Not fully up to date yet!

This course focuses on methods and techniques used in information systems for unstructured text, such as search engines. Text preparation and indexing, boolean and vector models for search systems, user feedback, interfaces and evaluation of search systems will be discussed. To support theory, experimentation with one or more systems in lab sessions is included.

Details

docent: Gertjan van Noord
studiepunten: 5
plek in studieprogramma: deel van de Bachelor Informatiekunde
literatuur: Manning, Raghavan, Schütze, Introduction to Information Retrieval. Cambridge University Press 2008.
roostering: hoorcollege op maandag, 13:00-14:45, zaal Harmonie 1313.0338
roostering: werkcollege/practicum op donderdag, 13:00-14:45, zaal Harmonie 1312.0107 MB
opdrachten: 30%, schriftelijk tentamen 70%
tentamen staat nu gepland voor donderdag 6 november 2014, 14:00-17:00, A3 Academiegebouw.

Overzicht (voorlopig)

Hoofdstuk 1: introduction; boolean retrieval; posting lists
Hoofdstuk 2: decoding, tokenization and normalization; sub-linear posting list intersection; phrase queries
Hoofdstuk 3: dictionaries; wildcard queries; spell correction
Hoofdstuk 6: scoring and term weighting; term and document frequency weighting; vector space model
Hoofdstuk 8: evaluation
Hoofdstuk 21: link analysis: page rank
Hoofdstuk 9: relevance feedback and query expansion

Opdrachten

De waardering van de opdrachten is te vinden op Nestor. In beginsel moeten de opdrachten steeds vóór het eerstvolgende hoorcollege worden ingeleverd, via Nestor.

Week 1

opdrachten uit het boek:
1. 1.1
2. 1.2
3. 1.3
4. 1.4
5. 1.7
6. 1.13
opdrachten Python:
1. De volgende UNIX pipe levert je tweets in een tabular formaat waarbij elke regel een tweet bevat. Elke regel bevat vier velden, gescheiden door TAB, en die representeren de ID van de tweet, de USER, de TEXT en een getokenizeerde versie van de TEKST.
```
zcat /net/corpora/twitter2/Tweets/2013/08/20130807:14.out.gz |
      /net/corpora/twitter2/tools/tweet2tab id user text words
```
  Schrijf een python programma dat op basis van deze input een database bouwt: je moet een dictionary maken, waarbij je de "id" van de tweet als key gebruikt, en waarbij je de andere velden ("user","text","words") als waarde gebruikt. De dictionary bewaar je op de harde schijf door middel van de "pickle" module. Hiermee kun je Python data-structuren opslaan, en later weer terug inlezen. Dit kan bijvoorbeeld op de volgende manier, om de waarde van "docs" op te slaan in het bestand "docs.pickle":
```
import pickle

with open('docs.pickle','wb') as f:
    pickle.dump(docs,f)
```
2. Schrijf een python programma dat de in de vorige opdracht gemaakte dictionary inleest, en vervolgens van standard input regels leest. Elke regel moet een "id" van een tweet bevatten. De desbetreffende tweet wordt door het programma naar standard output geprint. Het lezen van een ge-pickle-de datastructuur kan bijvoorbeeld zo:
```
import pickle

docs = pickle.load(open('docs.pickle','rb'))
```
3. Schrijf vervolgens nog een python programma (een variant van het eerste programma) dat niet alleen een dictionary van de tweets bouwt, maar ook een "postings list". Dus voor elk woord bouw je een dictionary waarbij de waarde een gesorteerde lijst van tweet id's is.
4. Schrijf nog een programma (een variant van het tweede programma), dat de data gebruikt van programma 3, en dat steeds regels leest van standard input, waarbij elke regel een woord is. Het programma print steeds alle tweets naar standard output die het gegeven woord bevatten.
5. Breid je query programma uit, zodat je een queries aankunt waarbij je twee zoektermen krijgt. Elke regel van standard input bevat de twee zoekwoorden, gescheiden door een TAB. Je moet alle tweets teruggeven die een van beide zoektermen bevatten.
6. Breid je query programma uit, zodat je een queries aankunt waarbij je twee zoektermen krijgt. Je moet alle tweets teruggeven die beide zoektermen bevatten.
7. Breid je query programma uit, zodat je een queries aankunt waarbij je twee zoektermen krijgt. Je moet alle tweets teruggeven die wel de eerste, maar niet de tweede zoekterm bevatten.

Week 2

opdrachten uit het boek:
1. 2.1
2. 2.2
3. 2.3
4. 2.4
5. 2.6
6. 2.8
7. 2.9
programmeeropdrcht. Schrijf een Python-programma dat steeds tweets leest van standard input, in het bekende formaat, en dat voor elk woord in de tweet een gesorteerde positielijst genereert en op standard-output toont.
programmeeropdracht. Schrijf een Python-functie, die als argumenten twee gesorteerde lijsten van posities geeft. De functie moet "True" teruggeven als in de eerste lijst een positie p voorkomt, zodat er in de tweede lijst een positie p+1 voorkomt. Zo niet, moet de functie "False" teruggeven. Je moet proberen gebruik te maken van het feit dat de lijsten gesorteerd zijn.
```
bigram([1,6,8],[4,7,10])
```
moet "True" opleveren.
```
bigram([1,16,18],[4,7,10,20])
```
moet "False" teruggeven. Hint: het kan gemakkelijk zijn om gebruik te maken van expliciete iterators, lees hiervoor de uitleg van de functies "iter()" en "next()".
programmeeropdracht. We gebruiken dezelfde Twitter-data als voor de programmeeropdrachten van vorige week. Schrijf een python-programma dat een database opbouwt voor de tweets waarbij je nu per term ook de posities in een tweet bijhoudt. Vervolgens schrijf je een query programma dat steeds twee query termen q1 en q2 van standard input inleest. Je moet in de tweets die documenten teruggeven waar term q1 direct vooraf gaat aan q2.

Week 3

opdrachten uit het boek:
1. 3.1
2. 3.2
3. 3.4
4. 3.8
1. programmeeropdracht: implementeer een Python functie die voor twee gegeven woorden de Levenshtein afstand bepaalt (zie figuur 3.5 in het boek)
2. Om de opdracht een beetje interessant te maken bouw je nu een variant waarbij we aannemen dat het inserteren of deleren van een klinker slechts een halve strafpunt kost. Het vervangen van een klinker door een andere klinker kost ook slechts een halve punt. Bijvoorbeeld, de afstand tussen "face" and "facade" zou in het normale geval 2 bedragen, maar voor onze definitie is het slechts anderhalf.
programmeeropdracht: pas je Twitter-zoek-programma zo aan, dat er je voor een query term waarvoor geen hits bestaan, een query wordt uitgevoerd met een term die wel bestaat en die (eventueel bij benadering) de laagste Levenshtein afstand heeft. Bonuspunten voor een effectieve en efficiënte oplossing! Suggesties in oplopende moeilijkheidsgraad - maar je mag ook een heel andere aanpak kiezen:
- Vergelijk de query-term met alle mogelijke termen uit de database en bepaal de Levenshtein afstand. Dit is een naieve, want zeer inefficiente, baseline methode.
- Iets moeilijker. Vaak zijn er meerdere kandidaten die bijvoorbeeld een Levenshtein afstand van 1 krijgen. Zorg dat je een query uitvoert voor elk van de kandidaten met een minimale score.
- Bouw een index van trigrammen naar termen zodat je voor elke trigram in je zoekwoord een aantal mogelijke termen terugkrijgt. Bepaal de Levenshtein afstand alleen voor deze set van termen.
- Bouw een index van trigrammen naar termen zodat je voor elke trigram in je zoekwoord een aantal mogelijke termen terugkrijgt. Bepaal van elke term de Jaccard score, en vervolgens bereken je de Levenshtein afstand voor die termen die een minimale Jaccard score behalen.

week 4

Opdrachten uit het boek:
1. 6.9
2. 6.10
3. 6.11
4. 6.15
5. 6.17
Programmeeropdracht: voor de twitter-zoek-machine van de afgelopen weken, implementeer een variant die voor een gegeven reeks van twee zoektermen alle tweets teruggeeft die beide zoektermen bevatten, en bovendien aangeeft wat de tf-idf score van elk document is.
- bij het maken van de database: je moet bijhouden - voor elke term - in hoeveel documenten die term voorkomt
- bij het maken van de database: je moet bijhouden hoeveel documenten er zijn
Programmeeropdracht: als de vorige opdracht, maar geef nu de beste drie documenten terug in volgorde van de hoogste tf-idf score. Sorteren is niet toegestaan, in plaats daarvan is het de bedoeling dat je de module heapq gebruikt.
Programmeeropdracht: als de vorige opdracht, maar nu eisen we slechts dat één van de gegeven query-termen in de tweet voor moet komen.
Vraag: kun je een voorbeeld vinden van een query van twee zoektermen zodat er een tweet is die slechts één van de twee zoektermen bevat en een hogere tf-idf score krijgt dan een tweet waarin beide termen voorkomen?
Vraag: ik heb een voorbeeld query waarbij de tf-idf waarde 36.7 is van een matchende tweet waar slechts één zoekterm in voorkomt - kun je voorbeeld bedenken met een hogere waarde? Zo ja -> bonuspunt. Inmiddels staat het record op 139!

week 5

8.1
8.2
8.4
8.8
8.10
programmeeropdracht: definieer een Python functie die voor een gegeven lijst judgements van twee judges (input ziet er dus uit zoals bij opdracht 8.10 uit het boek) de kappa waarde uitrekent. Zorg dat je programma eventueel ook meer dan twee mogelijke judgementswaarden aankan. Beschrijf kort wat er moet gebeuren om de functie uit te proberen voor een andere lijst judgements.

week 6

21.5
21.6
Bekijk figuur 21.3: de sequentie van vectoren van waarschijnlijkheid. Herhaal dit voorbeeld, maar met dit verschil dat je begin-vector x_0 er zo uit ziet: [0.5, 0.3, 0.2]
Idem, maar nu met x_0 waarbij alle waarschijnlijkheden gelijk zijn, dus: [1/3, 1/3, 1/3]
Schrijf een Python programma dat de PageRank vector uitrekent voor een gegeven matrix P. Het programma moet de vectoren x_1, x_2, x_3, ... opsommen, totdat geen verdere veranderingen plaatsvinden. Neem hierbij aan dat je input matrix, P, al op de juiste manier de waarschijnlijkheid van teleports representeert. Denk erom, je programma moet de matrix P van standard input inlezen. Hier is een eenvoudig voorbeeld van zo'n matrix in het formaat dat je programma moet kunnen behandelen. Het resultaat moet uiteindelijk zoiets worden:
```
0.3635 0.1141 0.1949 0.2028 0.1247 
```
Tip: de waarschijlijkheden per rij moeten optellen tot 1. Zie wat er gebeurt als dit niet het geval is:
```
0.33	0.33	0.33
0.33	0.33	0.33
0.33	0.33	0.33
```
In zulke gevallen kun je er beter zoiets van maken:
```
0.34	0.33	0.33
0.33	0.34	0.33
0.33	0.33	0.34
```
Hier is nog een voorbeeld van een matrix:
```
0.25	0.25	0.25	0.25
0.25	0.25	0.25	0.25
0.25	0.25	0.25	0.25
0.25	0.25	0.25	0.25
```
In dit voorbeeld gebeurt er niet veel, alle sites zijn even "goed". Stel dat we de pagerank van de vierde site willen verbeteren. We bouwen vier "nep"-sites. Elke nep-site linkt alleen naar de vierde site. Onze vierde site linkt naar elk van de nep-sites. Hoe ziet de resulterende matrix eruit (je hoeft hierbij geen rekening te houden met teleports, ofwel de teleport-rate is gelijk aan 0)? Leidt deze aanpassing inderdaad tot een verhoging van de pagerank van onze site?