Zoekmachines LIX019B05

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: 31 oktober 2013, 14:00-16:45. Academiegebouw zaal 3.
• hertentamen: 20 januari 2014, 14:00-16:45, Harmoniegebouw 12.0025.

Overzicht (voorlopig)

1. Hoofdstuk 1: introduction; boolean retrieval; posting lists
2. Hoofdstuk 2: decoding, tokenization and normalization; sub-linear posting list intersection; phrase queries
3. Hoofdstuk 3: dictionaries; wildcard queries; spell correction
4. Hoofdstuk 6: scoring and term weighting; term and document frequency weighting; vector space model
5. Hoofdstuk 8: evaluation
6. Hoofdstuk 21: link analysis: page rank
7. 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

1. opdrachten uit het boek:
   1. 1.1
   2. 1.2
   3. 1.3
   4. 1.4
   5. 1.7
   6. 1.13
2. opdrachten Python:

   Voor het werken met python gebruiken we de Mongo database implementatie. De allereerste keer dat je mongo met python wilt gebruiken, moet je de mongo library installeren. Voeg eerst een directory toe aan de variabele voor Python die bepaalt waar de libraries zich bevinden. Deze regel moet je elke sessie opnieuw uitvoeren. Als je deze regel in een bestand zoals .bash_profile plaatst, gaat dat automatisch.

   export PYTHONPATH=$HOME/.local/lib/python3.1/site-packages
   

   Vervolgens moet je eenmalig een directory aanmaken voor je eigen Python paketten, en dan kun je pymongo installeren:

         
   mkdir -p $PYTHONPATH
   easy_install3 --prefix=$HOME/.local pymongo
   

   De Mongo database werkt altijd met een server-client architectuur. Per sessie moet je de database server starten, en uiteindelijk ook weer stoppen. De allereerste keer maken we eerst een directory waar Mongo zijn troep kwijt kan. Vanwege problemen met het file-systeem doen we dit op een lokale schijf (voorlopig...). Dit geldt alleen op de LWP-machines.

   mount /mnt/D
   mkdir -p /mnt/D/$USER/mongod
   

   Vervolgens starten we de Mongo server als volgt. We vertellen waar de directory voor Mongo zich bevindt. Verder sturen we alle output van Mongo naar een log bestand. Dat kun je raadplegen als er onverwachte dingen gebeuren:

   mongod --dbpath /mnt/D/$USER/mongod --logpath /mnt/D/$USER/mongod/log &
   

   Je vindt hier een eenvoudig tutorial. De volledige documentatie van Mongo vind je onder andere hier.

   Hier is een minimaal script om met de server contact te maken, en vervolgens een database te construeren, en een query uit te voeren. Dan volgen nu de daadwerkelijke opdrachten:

   1. Probeer het eenvoudige python script uit, en zorg dat het voor jou werkt.
   2. Construeer nu twee eenvoudige python scripts, zodat de functionaliteit van het eenvoudige voorbeeld in twee delen wordt gesplitst. Het eerste script bouwt de database, het tweede script bevraagt de database.
   3. 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 script dat op basis van deze input een database bouwt. Schrijf vervolgens nog een python script waarmee je kunt zoeken naar tweets die woorden bevatten die in de "words" kolom voorkomen. Voor deze tweets toon je de id, gebruiker, en tekst. Het tweede script leest van standard input en beschouwt elke regel als een zoekterm. Hint: zolang je script voor het bouwen van de database nog niet goed werkt, gebruik dan een klein deel van bovenstaande tekst. Het is al wat langzaam om een database voor alle 137042 tweets te maken.
   4. Breid je query script uit, zodat je een queries aankunt waarbij je twee zoektermen krijgt. Je moet alle tweets teruggeven die beide zoektermen bevatten.
   5. Breid je query script uit, zodat je een queries aankunt waarbij je twee zoektermen krijgt. Je moet alle tweets teruggeven die een van beide zoektermen bevatten.
   6. Breid je query script 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

1. 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
2. programmeeropdracht. We gebruiken dezelfde Twitter-data als voor de laatste opdrachten van vorige week. Schrijf een python-script dat een database opbouwt voor de tweets waarbij je nu per term ook de posities in een tweet bijhoudt. Vervolgens schrijf je een query script 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. Tip: In Mongo kun je zowel de punt als het dollar-teken niet gebruiken als onderdeel van een key. Deze python-functie is wellicht handig om deze tekens te vermijden:

   def escape(key):
       return key.replace("$", "\uFF04").replace(".", "\uFF0E")
       

   Hoe het niet moet:

   poslist1 = pos[query1]
   poslist2 = pos[query2]
   
   for pos1 in poslist1:
       if pos2 + 1 in poslist2:
           hits.append(pos1)
   

Week 3

1. opdrachten uit het boek:
   1. 3.1
   2. 3.2
   3. 3.4
   4. 3.8
2. programmeeropdracht: bouw een variant van je Twitter-zoek-script van de afgelopen twee weken die zogenaamde "trailing wildcard queries" ondersteunt.
3. 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.
4. programmeeropdracht: pas je Twitter-zoek-script 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. Je kunt alle termen uit de database krijgen met volgende stukje Python:

     for t in db['Tweets'].distinct("terms"):
     

     Dit is de naieve, 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

1. Opdrachten uit het boek:
   1. 6.9
   2. 6.10
   3. 6.11
   4. 6.15
   5. 6.17
2. 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
3. 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.
4. Programmeeropdracht: als de vorige opdracht, maar nu eisen we slechts dat één van de gegeven query-termen in de tweet voor moet komen.
5. 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?
6. 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

1. 8.1
2. 8.2
3. 8.4
4. 8.8
5. 8.10
6. 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 script eventueel ook meer dan twee mogelijke judgementswaarden aankan.

week 6

1. 21.5
2. 21.6
3. 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]
4. Idem, maar nu met x_0 waarbij alle waarschijnlijkheden gelijk zijn, dus: [1/3, 1/3, 1/3]
5. 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
   

6. 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?