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

Overzicht

  1. Hoofdstuk 1: introduction; boolean retrieval; posting lists; intersectie in python; python code
  2. Hoofdstuk 2: decoding, tokenization and normalization; sub-linear posting list intersection; phrase queries
  3. Hoofdstuk 3: dictionaries; wildcard queries; spell correction; herhaling stdin/stdout/stderr: w3.pdf
  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.

Voor programmeeropdrachten lever je alles in wat ik nodig heb om je programma uit te kunnen proberen. Je mag daarbij aannemen dat ik ook op een LWP machine werk en dus al toegang heb tot alle bestanden in /net. We gebruiken Python3 zoals op de LWP geinstalleerd (dat is nu versie 3.4). Oplossingen in python2 worden niet in behandeling genomen.

Voor opdrachten waarbij je open vragen beantwoordt heb je de keus tussen txt formaat of pdf. Andere bestanden (bijvoorbeel .doc, .docx, .rtf) worden niet geaccepteerd.

Naamgeving van de bestanden: hou het kort, en gebruik geen spaties en andere rare tekens in de bestandsnamen. Je naam, studentnummer etc hoeven *geen* deel uit te maken van je bestandsnaam, dat doet Nestor automatisch voor mij.

Zoals altijd, je levert je eigen werk in. Elkaar helpen is tot op zekere hoogte natuurlijk toegestaan, maar dat is niet hetzelfde als een groepsproject. Dus identieke oplossingen zijn niet toegestaan en worden beoordeeld met een 1.

Naar aanleiding van het nakijken bij week 1. Het is voor de docent veel gemakkelijker indien je alle bestanden die bij 1 opdracht horen in een zip-bestand inpakt, en dat zip-bestand uploadt naar Nestor. Op die manier blijven namelijk de oorspronkelijke bestandsnamen gelijk. Dus vanaf week 2 graag altijd al je bestanden samen in een zip bestand pakken.

Indien je gebruik maakt van de mogelijkheid om een tweede (of derde, vierde...) poging in te leveren, lever dan steeds een volledig zip-bestand in, met alle bestanden, zodat ik altijd kan volstaan met het nakijken van de laatste poging.

Week 1

Voor de opdrachten van week 1 geldt: lever de boek-opdrachten in, in een tekst-bestand via Nestor (txt of pdf). Voor de Python-opdrachten geldt dat je alleen de laatste opdracht inlevert, mét de bijbehorende pickle bestanden!
  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:
    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/2015/08/20150828:15.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". Je bouwt dus een dictionary waarbij je voor elk woord als waarde een datastructuur toekent waarin alle tweet-ids zijn gerepresenteerd. Voordat je deze opdracht implementeert, verdient het aanbeveling om de volgende opdrachten even door te lezen, zodat je de juiste data-structuur kiest.
    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 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 beide zoektermen bevatten. Het is hierbji natuurlijk de bedoeling dat je goed nadenkt over de gebruikte data-structuur, en dat je de queries efficient verwerkt - laat merken dat je het college / het boek begrepen hebt! Hint: Python heeft een "set" datastructuur!

Week 2

Ook voor de opdrachten van week 2 geldt: lever de boek-opdrachten in, in een tekst-bestand via Nestor (txt of pdf). Voor de Python-opdrachten geldt dat je alleen de laatste opdracht inlevert, mét de bijbehorende pickle bestanden!
  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. Schrijf een Python-programma dat steeds tweets leest van standard input, in het bekende formaat. Voor elke tweet moet je een voor elk woord in de tweet de gesorteerde positielijst printen. Voorbeeld:
    $ zcat /net/corpora/twitter2/Tweets/2015/08/20150828:15.out.gz |
           /net/corpora/twitter2/tools/tweet2tab id user text words | head -n2 | python3 ex2.1.py
    het [8]
    En [0]
    bij [4]
    de [5]
    #welweerhandighe [13]
    verstap [1]
    #Jumbo [6]
    been [12]
    schiet [7]
    in [10]
    je [2, 3, 9, 11]
    RT [0]
    ! [16]
    geschonken [14]
    eigen [12]
    worden [15]
    de [11]
    kan [5]
    voor [10]
    @NotarisZelhem [1]
    een [8]
    ton [9]
    woning [13]
    https://t.co/yeWn3MiQPS [17]
    weer [7]
    2017 [4]
    : [2]
    er [6]
    Vanaf [3]
    
  3. programmeeropdracht. Schrijf een Python-functie bigram, die als argumenten twee gesorteerde lijsten van posities heeft. 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 gebruikmaken van het feit dat de lijsten gesorteerd zijn. Bewaar de functie in het bestand bigram.py. Zorg ervoor dat je onderstaande interactie met de Python3 interpreter kunt reproduceren.
    python3
    >>> from bigram import bigram
    >>> bigram([1,6,8],[4,7,10])
    True
    >>> bigram([1,16,18],[4,7,10,20])
    False
    
    Hint: het kan gemakkelijk zijn om gebruik te maken van expliciete iterators, lees hiervoor de uitleg van de functies "iter()" en "next()". Bekijk ook de extra sheets van week 1.
  4. 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 (de twee termen staan op 1 regel, gescheiden door een TAB). Je moet die tweets teruggeven waar term q1 direct vooraf gaat aan q2.

Week 3

  1. 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). Het programma leest steeds een regel van standard input. De regel bestaat uit twee woorden, gescheiden door een tab. Voor elke regel wordt een regel naar standard output geprint bestaande uit dezelfde twee woorden en de gevonden afstand, gescheiden door twee tabs. Dus:
      $ echo "de	die" | python3 lev.py
      de	die	1
      
      Deze opdracht hoef je niet in te leveren.
    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. Let op, dit gaat vrij gemakkelijk fout, controleer je programma dus zorgvuldig aan de hand van eigen voorbeelden. Hier is mijn uitwerking: lev_vowel.py. Commentaar welkom.
  2. programmeeropdracht: pas een versie van 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. Deze versie van het zoekprogramma werkt steeds met queries van slechts een enkel woord. 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. Voer de query vervolgens uit met een term die de minimale afstand heeft. Dit is een naieve, want inefficiente, baseline methode.
    • Iets moeilijker. Vaak zijn er meerdere kandidaten die bijvoorbeeld een Levenshtein afstand van 1 krijgen. Zorg dat je een 'OR' query uitvoert 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.
    Lever alle benodigde bestanden in (ga er niet van uit dat ik jouw bestanden van vorige week nog wel heb).

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. Het is in orde om hiervoor de "lengte" van de posting-list te gebruiken
    • bij het maken van de database: je moet bijhouden hoeveel documenten er zijn
    • je moet bijhouden hoevaak een term in een tweet voorkomt
    Deze opdracht hoef je niet in te leveren, maar gebruik je als opstapje naar de volgende opdracht.
  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. Zie ook de manual. Deze opdracht hoef je niet in te leveren, maar gebruik je als opstapje naar de volgende opdracht.
  4. Programmeeropdracht: als de vorige opdracht, maar nu eisen we slechts dat één van de gegeven query-termen in de tweet voor moet komen. Lever deze opdracht in, met alle benodigde bestanden samengepakt in een zip-bestand. Geef in een bijgesloten tekstbestand ook antwoord op de volgende twee vragen:
    1. 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?
    2. Vraag: verzin een query waarbij je een zo hoog mogelijke tf-idf waarde krijgt. Mijn hoogste waarde tot dusver: 70.4

week 5

  1. Boek:
    1. 8.1
    2. 8.2
    3. 8.4
    4. 8.8
    5. 8.10
  2. 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. Hier is een voorbeeldbestand. Mijn implementatie geeft hiervoor een kappa van 0.5796 waarbij P(A) 0.81 is en P(E) 0.54805. Ga er niet van uit, dat de waardes altijd '0' of '1' zijn, of dat er altijd maar twee mogelijke waardes zijn. Hier is nog een voorbeeldbestand. Mijn implementatie geeft hiervoor een kappa van 0.43 waarbij P(A) 0.636 is en P(E) 0.36.

week 6

  1. Op papier
    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]
  2. 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?
  3. Bonusopdracht. Sommige studenten hebben gevraagd om een opdracht te herkansen. Dat kan niet. In plaats daarvan bestaat de mogelijkheid om deze bonusopdracht (mini-project) te maken voor extra punten.

    In twitter berichten refereren gebruikers vaak aan andere gebruikers met een "mention": @NAAM. We kunnen een heleboel tweets verzamelen, en daarin van alle gebruikers bekijken hoe vaak ze naar andere gebruikers refereren met zo'n mention. De mentions samen definieren een graaf waarop we ook het pagerank algoritme los kunnen laten: we kunnen dan uiteindelijk zien welke gebruiker(s) volgens pagerank het "populairst" zijn.

    In deze opdracht moet je dus de mentions extraheren vanuit onze tweet verzameling (hoe meer data je aan kunt, hoe beter natuurlijk). De volgende pipe genereert alle tweets uit Augustus 2015 waarin mentions voorkomen:

    zcat /net/corpora/twitter2/Tweets/2015/08/*.out.gz | 
          /net/corpora/twitter2/tools/tweet2tab user words |
         grep '@'
    

    Wat lever je in? Voor deze opdracht lever je geen code in, maar lever je een verslag in met daarin kort uitgelegd hoe je de opdracht hebt aangepakt, en welke resultaten je hebt gekregen.

    Voorbehoud: ik heb deze opdracht zelf niet geprobeerd, het zou best eens flink moeilijk kunnen blijken!