College 5-8 Information Retrieval PDF

College 5 Vector space model  Kolommen zijn documenten  Rijen zijn termen Counter vector: een som van alle termen in een document (kolom in matrix)  Hierbij gebruik maken van term-frequency (tf) in de kolommen Je hebt meer aan zeldzame termen dan veel voorkomende. -> zeldzame m...

College 5 Vector space model  Kolommen zijn documenten  Rijen zijn termen Counter vector: een som van alle termen in een document (kolom in matrix)  Hierbij gebruik maken van term-frequency (tf) in de kolommen Je hebt meer aan zeldzame termen dan veel voorkomende. -> zeldzame moeten een hoger gewicht krijgen. Bijvoorbeeld “arachnocentric” is zeldzamer dan “method” dus moet een hoger gewicht krijgen Collection frequency: hoe vaak een bepaalde term voorkomt (een rij in de matrix) in alle documenten als totaal Document frequency: het aantal documenten die de term minstens 1 keer hebben  Welk woord is een betere zoekterm? Collection frequency is bijna gelijk maar de document frequency van “insurance” is veel lager. Hiermee is een document met dit woord zeldzamer en zou een hoger gewicht moeten krijgen  hoe lager de document frequency hoe zeldzamer dus hoger het gewicht moet  gewicht bereken met idf weight Hoe moeten we een gewicht voor een term berekenen?  Door middel van inversed document frequency idf(t)  Df(t) = document frequency  N = totaal aantal documenten  Df(t) ≤ N  inversed df(t) = log 10 (N/df(t))  log 10 wordt gebruikt om het effect te verkleinen, makkelijker om mee te bereken (alleen positieve getallen)  Hoe lager de dft hoe hoger de idft (zie foto) Wanneer termen niet voorkomen in documenten:  Add-one-smoothing: Tf-idf score:  Score is een gewicht van een term en wordt gedefineerd als een product van tf en idf gewicht  tf = term frequency  idf = inversed document frequency  voor final score, voor de gehele score (som van tf-idf scores):  Neemt toe bij hogere frequentie van termen  Neemt toe bij zeldzaamheid in de gehele collectie Effect of idf on ranking:  Idf heeft geen effect op one-term queries ranken(moet om meerdere termen gaan)  Idf heeft effect bij queries met twee of meer termen Tf-idf with logarithmic Term Frequency: wf-idf  Wf-idf is het zelfde als tf-idf maar met logarithmicisch gewogen termen frequencies  Er zijn nog meer verschillende varianten van de tf-idf score: Nu kan de matrix als weight matrix: Documenten als vecors:  V-dimentionaal, waarbij v is vocabulair  Voor bovenstaande matrix, zou het 7 dimentionaal zijn  Termen zijn de axen van de vector  Documenten zijn punten of vecotors in de space Ranken van documenten op hoge en lage relevantie:  Manier 1: Kleinste afstand tussen document en query zoeken o Geeft misschien niet werkelijk de meest overeenkomen  Manier 2: kleinste hoek tussen document en query o Document toevoegen aan zichzelf (2 x document d’) o Bewezen: D en d’ hebben zelfde inhoud, euclidean distance is verschillend maar hoek is 0 o Hoek berekenen:  o Eclidean distance gelijk krijgen, lengte normalisatie:    Voorbeeld hoek berekenen:  Geeft cosine similarity Kan ook met tf als weights: word -> Nu niet alleen het document maar ook de tf vastleggen in dictionary: College 6 14-11-2024 Waarom index compression?  Minder memory/diskspace nodig (75% minder)  Meer informatie in main memory -> 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 o Reuters: 800.000 docs o Common Crawl 3 bil docs o Google 100- bil docs  Nuber of tokens and terms  Per rij worden er meer dingen weggehaald  Grootte van dictionary, proberen te voorspellen Snelheid van toename neemt af o Heaps law:   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 o Het meest voorkomende woord is twee keer zo frequent als het tweede meest voorkomende woord etc. o  Geen termen meer in dict maar pointers naar een hele lange string met alle terms 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 o 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 o TP/(TP+FP)  Recall: fractie van relevante documenten die gevonden zijn o 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  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:  Meer documenten: o Recall neemt toe o Precision neemt af    We willen een soort gemiddelde vinden -> we willen 1 waarden (geen curve)  Interpolated precision: hoogste precision bij hoogste recall  Andere manieren (betere): Mean Average Precision (MAP): 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:’ o IBM’s copyright page (hoge term frequenty) o Spam page van concurrent (ook hoge term frequenty) o 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: 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: Voorbeeld: Je kan ook model PageRank met behulp van Markov Chains: 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: 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: o autority: aantal links die wijzen naar de pagina o 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: o 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