Aantekeningen Hoorcollege 1 PDF

Aantekeningen Hoorcollege 1 28-10-2024 Geschiedenis: Information Retrieval werd meestal gedaan door archivarissen en bibliothecarissen die werkten voor overheidsinstellingen (bijv. eigendomsrechten, scheepsjournalen, nationaliteiten, statistieken, rechtszaken enz.), militaire en geheime diensten, w...

Aantekeningen Hoorcollege 1 28-10-2024 Geschiedenis: Information Retrieval werd meestal gedaan door archivarissen en bibliothecarissen die werkten voor overheidsinstellingen (bijv. eigendomsrechten, scheepsjournalen, nationaliteiten, statistieken, rechtszaken enz.), militaire en geheime diensten, wetenschappelijke instellingen (universiteiten, bureaus voor de statistiek), religieuze geestelijken en culturele instellingen. Information retrieval: het vinden van materiaal (meestal een document) van ongestructureerde aard (meestal tekst) dat voorziet in een informatiebehoefte vanuit grote collecties (meestal opgeslagen in een computer) Vroeger werd information retrieval vooral gedaan in de vorm van bibliotheken en archivering. Eerst werken met kaarten -> automatisch “Memex” met scans van de boeken (hyperlinks) -> boolean retrieval kwam -> first space vector model -> large document database systems run by companies -> FTP search and the dwn of Web search and UseNet Boolean retrieval: AND en OR etc. Vector space model: afstand tussen verschillende modellen (zoals hond en kat dichter bij elkaar dan muis) Large document system: data sience Vanaf 2000:  Linkanalyse & Ranking (Google)  Vraag beantwoorden  Multimedia IR (beeld- en videoanalyse)  Taaloverstijgende IR  Semantische Webtechnologieën (DBpedia) Sinds 2010:  Categorisatie, clustering en aanbevelingen Belangrijkste verschillen tussen IR en databases: nformation Retrieval:  (meestal) ongestructureerde data  set trefwoorden (losse semantiek)  onvolledige query specificatie, gedeeltelijke matching  relevante items voor resultaat, fouten zijn tolereerbaar  probabilistische modellen Databases:  gestructureerde data   goed gedefinieerde query (reguliere expressie, SQL)  volledige query specificatie, exacte match  enkele fout resulteert in een mislukking  deterministische modellen Latency (van snel naar langzaam) College 2 31-10-2024 kan zo worden weergegeven: Bigger collection: (1 mil docs, 1000 woorden per doc, 6 bytes/word) = totaal van 6GB of data, en 500.000 woorden De matrix is sparse (schaars), veel 0 en weinig 1. Omdat er maar 1000 woorden zijn Betere representatie: alleen de 1-en presenteren. Door een list te maken van hoe vaak het woord voorkomt -> posting lists Inverted indexin: heeft een dict met alle doc nummers waar het woord in voorkomt Normalization: woorden afkorten naar de stam. Extra stap Stap 1: Lijst van termen en in welk document ze voorkomen Step 2: sorteren op term (alfabetisch) en daarna op ID (oplopend) Step 3: split in dictionary en posting (de frequentie wordt ook toegevoegd) Voorbeeld:  query: brus and Index  Je wil de posting lists van beide, je voegt deze samen (merge)  O(x+y) Boolean retrieval:  Kijk niet naar duplicatie  Houd rekening met and, or en not  Is hierdoor heel precies, komt overeen of niet, geen tussen weg  Je begint met de kortste lijst, dit weet je door de bijgehouden doc. Frequentie A token is an instance of a sequence of characters in some particualr document that are grouped together as a useful semenatic unit for processing (Een token is een opeenvolging van tekens in een bepaald document die worden gegroepeerd als een bruikbare semantische eenheid voor verwerking.) A type is the class of all tokens consisting of actualy the same character sequence (Een type is de klasse van alle tokens die bestaan uit feitelijk dezelfde tekenreeks) A term is a (perhaps normalized) type that is included in the IR system’s dictionary (Een term is een (misschien genormaliseerd) type dat is opgenomen in het woordenboek van het IR-systeem.)  Bijvoorbeeld: type friend en friends -> term = friend Positings: tokens, counted once per document Bytes per token is vaak lager dan per term, omdat de korte worden niet voorkomen in de terms, waardoor de gemiddelde lengte van de woorden langer is. Common Crawl: een website die de tokens etc. van een sites kan bepalen (google doet dit ook maar dan nog voor veel meer webpagina’s) Berekeningen: Bytes-> hoeveel nodig is om reversed index op een disk te kunnen zetten Reuters kan nog op geheugen worden opgeslagen, maar de andere moeten op een disk of SSD  Wanneer er gebruikt wordt van een disk of SSD kan het sorteren niet op de normale manier  Voorbeeld voor de common crawl: Dus het sorteren gebeurt in kleine delen in de memory en wordt later weer teruggeplaatst op de disk Mergen van de onderdelen: Oplossing:  De Map-fase maakt een lijst van woorden in elk document en geeft het document-ID als waarde aan elk woord.  De Shuffle-fase verzamelt alle dezelfde woorden (sleutels) samen.  De Reduce-fase combineert de document-ID's in een lijst voor elk uniek woord, waardoor een omgekeerde index ontstaat waarin je snel kunt opzoeken in welke documenten een bepaald woord voorkomt. Hoorcollege 3 04-11 Phrase querie: twee woorden gescheiden door een spati. Bijvoorbeeld: “information retrieval”. De precieze tekst moet terug te vinden zijn  biwords: samenvoegen van woorden -> ieder biwoord is nu een dictionary. - Bij langere queries kan met Boolean: Stanford University AND university Palo AND Palo Alto -> geeft fout positieve - Snel fout bij woorden die veel voorkomen, zoals “beer of the month” (of en the) - Index blowup - Infeasable for mor than biwords  Positional indexes: in the positings store je de positie van waar de term voorkomt Voorbeeld: 4 is de beste Volgorde van position moet overeen komen: 430 en 434 klopt met de 2x be in de zin “to be or not to be” - Kost veel memory - Wordt nu als standaard gebruikt Vuistregels:  Positional index 2-4 keer groter dan non-positional indexing  Positional index is 35-50% van de orginele tekst, kan daarom als compression techniek van de tekst worden gezien Combinatie van Biword en positional index:  Eerst biword  Voor langere zinnen positional index  26% meer ruimte nodig dan alleen positional index Tokanization: afbreken in losse woorden:  “friends, Romans, countryman” o Friends o Romans o Countryman Maar kan soms problemen geven: Compound splitting: lange woorden zoals: ziektekostenverzekeringsmaatschappij opsplitsen in losse woorden Normalisatie:  Alle letters naar lower-case  Per land verschillend, zoals résumé en resume Stop words: korte veel voorkomende woorden, zoals ‘of’ and ‘the’  Maak een lijst en verwijden deze woorden voor het indexen  Deze woorden hebben weinig semantische context  Bij positional index moet deze dan ook uit de querie gehaald worden Lemmatization: algemeen woord kiezen voor groep soortgelijken woorden, kan alleen met dictionary Voorbeeld:  Am, ar is, were, being -> be  Car, cars, car’s, cars’ -> car Stemming: reduceren tot ‘roots’ = stam, geen dictionairy nodig maar regels Voorbeeld:  Automate, automates, automatic en automation -> automate  Meest gebruikte algoritme: Porters Algorithm (voor Engelse taal): Spelling correction: Twee manieren:  Corrigeren van documenten die worden geïndext   Corrigeren van userquery Twee soorten:  Isolated word: ieder woord apart checken, ziet typo’s niet  Context-sensitive: kijkt naar omgeven woorden Document correction:  Nodig voor OCR documenten: gescande documenten  Maar ook web-sites kunnen typo’s hebben  Representatie van de documenten wordt niet veranderd maar de query Query Miss-Spellings:  Retrieve documents met de correcte spelling  Return suggesties, zoals google doet: “bedoelt u ….” Isolated word correction:  Lexicon met correcte spelling word gebruikt: Twee soorten o Standard lexicon: zoals woordenboek of “industrie specifiek” o Lexicon of the indexed tekst collection: zoals woorden gevonden op het weg. (zelf een soort woordenboek bijhouden)  Geeft woord terug wat meest in de buurt komt Verschillende manieren voor afstand: o Edit distance (levenshtein distance): minimum operations (insert, delete of replace (transpose = omwisselen)) to convert S1 to S2. Bijvoorbeeld: cat to act is 2 transpoce o Weighted edit distance: o N-gram overlap: enumerate all the n-gram (n = nummer) zoals bij biwords maar dan met verschillend aantal woorden Voorbeeld: Bigram voorbeeld: Voorbeeld trigram:   Nu mogelijk om distance te bepalen door overlap en verschillen te meten  Ratio overlap: Voorbeeld Jaccard coefficient: Antwoord: 3/6 voor woord HOP want komt op 3 van de 6 onderdelen overeen. o Phonetic similarity Context-sensitive correction:  Erg inefficiënt maar minst gecompliceerd Hoorcollege 4 07-11 soorten zoekmethoden Hashtable hashtable.put(“key”, pointer_to_postinglist) -> toevoegen aan lijst Hashtable.get(“key”) -> geeft point tot postinglist Geeft: table met links key en rechts postinglist Voordelen: + compuational complexity O(1) for insert and serach Nadelen: - Mogelijk clashes - Redundant space in array Zoektijd word per 10x vergroten verdubbelen van tijd  Voorbeeld: 10 is 1 en 100 is 2  Dit is sneller dan bij andere manieren dan hash Nadelen:  Varianten van woorden als judgment/judgement is niet te vinden  Geen prefix search  Als de vocabulair blijft groeien moet alles ge rehashed worden, dit kost veel tijd Binary tree search Zoekt op letters, kiest tussen linker of rechter pad B-trees Meerdere paden om tussen te kiezen. Er kunnen bijvoorbeeld 3 of meer takken zijn. Anders dan bij binary tree waar slechts twee takken kunnen zijn  Minder unbalance problems (een hele lange tak) Skip list Elke element wordt los toegevoegd en heeft een eigen positie. Zoekt de kortste weg van beginpunt naar het element wat je zoekt. Bijvoorbeeld als tussen 3 en 4 wordt toegevoegd. Dan eerst naar 3. Op basis van kans in de 1e of 2e lijst toegevoegd. Overstappen op verschillende “perons” kan je soms een deel van de list “skippen” hierdoor kom je sneller op de bestemming zonder alle perrons af te gaan O(1) -> in 1 keer zoeken gevonden Nummers zijn op volgorde van sorted string Een toren bevat: string en pointers naar data Wild-Card queries Om dit te uit de kunnen is binary tree of skiplist nodig Wat zijn wild-card queries:  Als je zoekt op “Counter* “ worden alle woorden gegeven in de range van counter