Hoorcollege 1 Aantekeningen 28-10-2024 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, rechtsza...

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 Afbeelding met tekst, diagram, Plan, schermopname Automatisch gegenereerde beschrijving **Latency** (van snel naar langzaam)  Afbeelding met tekst, schermopname, zwart-wit, Lettertype Automatisch gegenereerde beschrijving 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  Afbeelding met tekst, schermopname, Lettertype, lijn Automatisch gegenereerde beschrijving **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) Afbeelding met tekst, schermopname, nummer, Lettertype Automatisch gegenereerde beschrijving **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]: Afbeelding met tekst, schermopname, Lettertype, lijn Automatisch gegenereerde beschrijving 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 Afbeelding met tekst, Lettertype, schermopname, algebra Automatisch gegenereerde beschrijving Mergen van de onderdelen:  Afbeelding met tekst, schermopname, Lettertype Automatisch gegenereerde beschrijving Oplossing:  Afbeelding met schermopname, diagram, lijn, Perceel Automatisch gegenereerde beschrijving - 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 - 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" - Friends - Romans - Countryman Maar kan soms problemen geven: Afbeelding met tekst, schermopname, Lettertype Automatisch gegenereerde beschrijving **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 - **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 - **Standard lexicon**: zoals woordenboek of "industrie specifiek" - **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 - **Edit distance (levenshtein distance)**: minimum operations (insert, delete of replace (transpose = omwisselen)) to convert S1 to S2. - **Weighted edit distance**: - **N-gram overlap**: enumerate all the n-gram (n = nummer) zoals bij biwords maar dan met verschillend aantal woorden - Nu mogelijk om distance te bepalen door overlap en verschillen te meten - Ratio overlap: Afbeelding met Lettertype, wit, tekst, lijn Automatisch gegenereerde beschrijving Voorbeeld Jaccard coefficient:  Antwoord: 3/6 voor woord HOP want komt op 3 van de 6 onderdelen overeen. - **Phonetic similarity** **Context-sensitive correction**: Afbeelding met tekst, schermopname, Lettertype, algebra Automatisch gegenereerde beschrijving - 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 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 1^e^ of 2^e^ 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 \ sneller - Snellere data transfer van disk naar memory - Zo kan je index runnen op divice met beperkte ruimte (vb. telefoon) - Snel compressie/algoritme nodig - Eerst is onderzoek nodig naar hoe de input er uit ziet Structuur van input data - **Collection size**: aantal documenten - Reuters: 800.000 docs - Common Crawl 3 bil docs - Google 100- bil docs - **Nuber of tokens and terms** Afbeelding met tekst, Lettertype, schermopname, nummer Automatisch gegenereerde beschrijving - Per rij worden er meer dingen weggehaald - Grootte van dictionary, proberen te voorspellen  Snelheid van toename neemt af - **Heaps law**:\ Afbeelding met tekst, schermopname, Lettertype Automatisch gegenereerde beschrijving - Dict size blijft toenemen met meer documenten ipv een maximum - Dict size kan erg groot worden bij grote collecties Woord distributie in een document: - **Zipf's law**: gegeven een natural language tekst, de frequentie van een woord is omkeerbaar proportioneel naar de rank in de frequency tabel - Het meest voorkomende woord is twee keer zo frequent als het tweede meest voorkomende woord etc. -  Afbeelding met tekst, schermopname, scherm, software Automatisch gegenereerde beschrijving  - Geen termen meer in dict maar pointers naar een hele lange string met alle terms Afbeelding met tekst, schermopname, Lettertype Automatisch gegenereerde beschrijving College 7 18-11 --------------- Waarom evalueren? - Kijken of het doet wat het zou moeten doen - Gebruikerstevredenheid is subjectief Je zou systemen willen kunnen vergelijken [Hoe kan je gebruikerstevredenheid meten]? - Web search engine: observeren en kijken of gebruikers vinden wat ze willen - Web shop: kijken of gebruikers vinden wat ze willen en een aankoop doen - Controlled experiment: gebruiker een taak geven om uit te voeren - Zelf userqueries testen Waarom information retrieval -\> mensen hebben information needs [Wanneer is zoek resultaat goed]? - Information need is statisfied - Relevante documenten worden gevonden hoe bepaal je relevantie? -\> gevonden document moet zoekvraag beantwoorden - De query is hierbij niet bepalend, het gaat om de uitkomst Relevance benchamark measuremnt requires: - A benchmark document collection - A benchmark set of information needs expressed as queries - A relevance assesment for each query -document pair- - Zo kan assessments automatisch plaatsvinden door automatische vergelijking **Standard relevance benchamarks**: - **Human experts**: bepalen of elk document relevant of irrelevant is - **Measuring Rater Agreement**: twee beoordelaars 1 als ze overeen komen, 0 als ze niet overeen -1 volledig oneens komen met bepaling relevantie - **Cohen's kappa**: 2 beoordelaars - **Fleiss' kappa**: meer dan 2 beoordelaars [What makes a result set better or worse]? - **Precision**: fractie van gevonden documenten die relevant zijn - TP/(TP+FP) - **Recall**: fractie van relevante documenten die gevonden zijn - TP/(TP+FN)  Wanneer is wat belangrijker? - Web search -\> precision - Corporate database -\> beide - Search interface for patents -\> Recall **F-measure**: harmonisch gemiddelde van precision en recall Afbeelding met Lettertype, wit, nummer, tekst Automatisch gegenereerde beschrijving - Kan verschillende gewichten hebben, maar hoef je niet echt te weten **Accuracy**:  - Ieder document is relevant of niet relevant. Hierdoor wordt accuracy de fractie van correcte classificatie. Daarom is Accuracy niet handig om te gebruiken - Bijvoorbeeld 0 resultaten is 100% accuraat [Evaluation of ranked results]: Afbeelding met tekst, Lettertype, schermopname, lijn Automatisch gegenereerde beschrijving - Meer documenten: - Recall neemt toe - Precision neemt af -  - We willen een soort gemiddelde vinden -\> we willen 1 waarden (geen curve) - **Interpolated precision**: hoogste precision bij hoogste recall - Afbeelding met diagram, lijn, Technische tekening, Plan Automatisch gegenereerde beschrijving Andere manieren (betere):  **Mean Average Precision (MAP)**: Afbeelding met tekst, Lettertype, schermopname, wit Automatisch gegenereerde beschrijving [ook naar de statistische variantie kijken]: - Een systeem kan anders reageren op verschillende zoektermen - Variantie tussen queries geeft de variantie tussen systemen weer College 8 21-11-2024 -------------------- Wanneer term-ranking breaks: - Wanneer we zoeken voor "ibm" onderscheid maken in:' - IBM's copyright page (hoge term frequenty) - Spam page van concurrent (ook hoge term frequenty) - IBM's homepage (termen komen vooral voor in foto's etc) **Links and Anchors**: - Idea 1: hyperlink tussen pagina's, kan gezien worden als **Quality Signal** - **Anchor Tekst**: allemaal verschillende inputs, zoals: "IBM", "ibm" etc. - **Crowd annotation**: een link leggen tussen anchor tekst en pagina, zodat als op een bepaalde term wordt gezocht soortgelijken kunnen returnen omdat ze een link hebben. **Citation frequency**: hoe vaak is een document gelinkt (je kan naar citaties kijken) **Co-citation**: docuementen of artikels worden vaak samen gelinkt [vanuit] een artikel(omdat er samenhang is tussen de verschillende documenten of artikelen) **Shared references**: artikelen die samen linken [naar] het zelfde artikel (of documenten) Sores op basis van link analysis: - Page rank (google) - HITS (hyperlink-induced Topic Search) - TrustRank (Yahoo!) [Idee achter page rank]: Hoe kunnen we gebruik maken van de informatie van hyperlink - Recommendations from important persons are more impressive - Link van belangrijke pagina is belangrijker - Daarmee kunnen we de belangrijkheid van de pagina bepalen Berekening achter page rank:  Afbeelding met tekst, schermopname, Lettertype Automatisch gegenereerde beschrijving Voorbeeld:  Doorgaan met iteraties tot dat er geen verschil meer ontstaat **Source**: pagina zonder inkomende link (zie voorbeeld 2) **Sink**: pagina zonder uitkomende link (zie voorbeeld 3) **Simplified pagerank**: Link leak pagrank, sources worden niet meegenomen **Full pageRank**: teleport Uitgaande van een ranom web "surfer" standaard berekeing: Afbeelding met tekst, Lettertype, schermopname Automatisch gegenereerde beschrijving Voorbeeld:  ------------------------------------------------------------------------------------------------------------------ Je kan ook model PageRank met behulp van **Markov Chains**: Afbeelding met tekst, schermopname, Lettertype, informatie Automatisch gegenereerde beschrijving Voorbeeld: makov Cain en adjacency matrix  Termen binnen Markov Chain: - **Strongly connected**: wanneer ieder punt uit ieder punt bereikbaar is - **Aperiodic**: voor iedere punten i en j er is een k zo dat voor iedere K\>k er is een pad van i naar j ter lengte K - Teleport connects ieder twee punten - **Stationary solution**: na een bepaald aantal stappen de verandering in distributie word kleiner (convergent) - Stationary solutions do not depend on initial probabilities Van **adjacency matrix** naar **Markov chain**: - Als rij een 1 bevat verang ieder element voor 1/N - Anders deel iedere 1 door aantal 1'en in rij - Vermenigvuldig matrix met (1-a) - \+ a/N voor iedere entry van de matrix om P te krijgen (uiteindelijke matrix) Voorbeeld: Afbeelding met Lettertype, schermopname, nummer, lijn Automatisch gegenereerde beschrijvingAfbeelding met tekst, Lettertype, schermopname, nummer Automatisch gegenereerde beschrijving Afbeelding met tekst, Lettertype, schermopname, lijn Automatisch gegenereerde beschrijving  **Lim-\> inf** = gaat naar (0,475 0,475 0,05) College 9 25-11-2024 -------------------- Page rank: - **hoge** **autoriteit** als er veel links naar jou zijn idee: - list pages (hub) bevatten goede information - hubs verwijzen naar pagina's met hoge autoriteit - twee waarden voor een pagina: - autority: aantal links die wijzen naar de pagina - hub value: aantal links die vertrekken van de pagina - bij pagerank wordt hub value gestraft - aanvullen hoe werkt het: - gegeven een tekst query, krijg je een index naar alle pagina's die deze query bevatten -\> dit geeft de **Root set** - voeg alle pagina's toe die: - verwijzen naar een pagina in de root set - aanvullen Grap G = (S,E) waar S is de base set - formules toevoegen - hub score is gebaseerd op autority score - Autority score is gebaseerd op hub score - Normalisatie is nodig omdat er anders oneindige iteraties ontstaan Je kan HITS toepassen maar dan moeten alle pagina's in de baseset staan Waarom gebruikt Google page rank en niet HITS? - Zo gebruiksvriendelijk mogelijk. Page rank geeft een makkelijk overzicht met beste keuze boven aan Hoeveel inkomende links verwacht je bij pagina's? - Distributie: Snelle afname en steeds minder - Voeg figuur toe - Wegen meer een puissant distributie - Vliegvelden een andere distributie **Small-world network**: - Het aantal mensen wat bijvoorbeeld nodig is om iedereen te bereiken Aanvullen Jj College 10 28-11-2024 --------------------- Netwerk van het web toevoegen **Crawler**: tool om webpagina's uit te lezen Web engines moeten hun documenten crawlen Stappenplan crawlen: - URL's initializeren - Herhalen: - **Aanvullen** Problemen simpele crawler: - Je moet heel veel pagina's door - Onmogelijk zonder **parallellisatie** (meerdere crawlers) - Niet iedere crawl van een pagina is succesvol **Politeness**: - Vermijden van denial of service attack: Sommige kleinere sites kunnen niet zo veel vraag aan - volg robots.txt van de site op, dit zijn een soort huishoud regels voor de crawler hoe te gedragen op de site -\> deze catchen van iedere site die je crawlt - site/robot.txt **freshness**: - sommige websites (zoals nieuws sites) moeten vaker gecrawld worden - andere pagina's hoeven niet zo vaak opnieuw gecrawld te worden **Robustness**: - We willen geen duplicatie in de content - Bijvoorbeeld max 3 kopieën accepteren in de index Kwaliteiten van goede crawler: - Scalable: crawl vergroten door meer machines (parallalisation) - Polite: niet te vaak een site bezoeken en robots.txt - Fresh: refresh belangrijke pagina's - Robust: niet de index overblowen met de veel kopieën Hoe controleer je of contex al in index zit? - Document **vingerpring** -\> je maakt een soort samenvatting, als deze overeen komen dan zie je het als dezelfde content - Documenten overslaan die al in de index staan - Je kan ook een timestamp toevoegen, alleen toevoegen als timesamp is ouder dan... bijvoorbeeld Distributie van crawlers: - Wereldwijd verspreiding van crawlers - url opslaan het dichts bij locatie, vb.nl indexen in een crawler in NL - figuur toevoegen verschillende crawlers in systeem taak waar url frontier op moet letten: - politness - freshness f (front queue) que en b (back queue) que aanvullen hh