College 5 & 6 Vector Space Model 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