Implementationsfrågor

 
 
 
  1. Indexering
  2. Dokumentrepresentation
  3. Sökfrågerepresentation
  4. Skalärprodukt
  5. Längdnormalisering
  6. Dimensionsreduktion - statistisk homeosemi
  7. Hopvägning av flera kunskapskällor
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Index - hur ser den ut?

  1. Plocka ut ord, med pekare till plats i databasen.
  2. Invertera ordlistan, från platsordning till alfabetisk ordning, med lista på förekomster ("postings") vid varje term.
  3. Termviktning.
Ganska processtungt.
 
  1. Bygg första strukturen i ett binärt träd; löven håller förekomsterna.
  2. Omforma trädet till en alfabetisk lista med idf, antal förekomster och lista på förekomsterna tillsammans med en viktning.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

 

Dokumentrepresentation

Dokumenten är i princip vektorer med termvikter i bestämda positioner: en position per term.

Ofta ingen idf; ofta idf satt till 1 + log(N/n) eller log(N/n)

Ofta tf satt till tillexempel 1 + log(tf) (SMART i TREC) eller bara log(tf) (PRISE).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

 

Representation av sökfrågor

Vektorerna är likaså likadana vektorer med samma termpositioner; här är dock typiskt termvikterna binära.

Termvikterna komponeras av tf och idf med till exempel enkel multiplikation.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

 

Skalärprodukter

Dessa två representationer ska nu kombineras så att dokumenten kan ordnas efter trolig relevans; till exempel genom att tillordna varje dokument ett numeriskt värde som mått för likhet med sökfrågan.

likhet(q[],d[]) ~ Summa(q[term]*d[term])
                  termer
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

Längdnormalisering

Dokumentlängd påverkar vikterna, och termvektorerna bör normaliseras därefter.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

Längdnormalisering

Kosinus

Standardmåttet kallas kosinusmåttet, där vikterna normaliseras med kvadratsumman av termfrekvenserna. Ett stort antal termer påverkar vikten för alla termer negativt, liksom stora vikter för några termer.
 

likhet(q[],d[]) ~ 1/Summa(d[term]^2)^(1/2)
                   termer
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

Längdnormalisering

Max tf

Ett alternativt mått normaliserar bara för höga termfrekvenser för några termer, och penaliserar inte längre dokument, som kosinusmåttet gör.
 

augtf =  0,5 + 0,5 * tf / max_tf  (SMART)

augtf =  0,4 + 0,6 * tf / max_tf  (INQUERY)
 

Dock är det så att riktigt långa dokument inte bara innehåller ointressanta termer. Såsom Katz visat går ju inte termfrekvenserna hand i hand med dokumentlängd.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga

Längdnormalisering

Antal förekomster

likhet(q[],d[]) ~ 1/antal termer i dokumentet

eller till och med
 

likhet(q[],d[]) ~ 1/antal tecken i dokumentet
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Matchning mellan index och sökfråga  

Flerordsfrågor

Hur väga samman flera ord? Är några få ord en text?

Flera termer i en sökfråga kan vara överlappande termer en användare angett för att täcka in synonymi

eller för att undvika polysemi,

eller helt oberoende termer - hur ska de vägas då?

Sökfras:         "Chips"         "Wafer"

                    5               5

                   10               0

                    0              10
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Homeosemi

Observation: ord är opålitliga ledtrådar till dokumentinnehåll språkets ordförråd plågas:

dels av delvis synonymi, vilket reducerar täckningsgraden i indexering;
dels av polysemi, vilket reducerar precision i sökning.

Likaväl som statistisk semantik går det att implementera statistisk homeosemi

Observation: matrisen av ordförekomster i dokument är gles

Hur kan man reducera dimensionaliteten utan att förlora information?
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Latent Semantic Indexing

Tanken är att hitta en underliggande ("latent") semantisk struktur i ordförekomsterna.

Försök förutsäga vilka termer impliceras av en sökfråga, som får betraktas bara som ett stickprov på termer som förekommer i texter om ett visst ämne.

Använd den glesa matrisen som kunskapskälla för att estimera underliggande struktur.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

En tänkbar teknik är SVD.

SVD tar en matris av term-dokument-likheter och delar upp den i tre matriser: en termmatris, en dokumentmatris och en term-dokument-dimensionsmatris som är diagonal. Den går att ordna så att de viktigaste elementen är först på diagonalen: sedan kan dimensionaliteten reduceras.

X (txd)  =  T0 (txm) x S0 (mxm) x D0'(mxt)

m = min(t,d)

Xestimat (txd) = T (txk) x S (kxk) x D (kxd)

där k är lägre än m.

k väljs så att systemet ger bästa resultat, inte för att vara lättbegripligt.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Merging - vägning av flera kunskapskällor

 

Exempel: tre informationskällor om en text

A plockar ut några väldigt pålitligt, men bara i början på sin lista
B har en jämn och regelbunden medioker kvalitet
C är opålitlig, men ibland glimrande
  1. Medelprecision
  2. Precision vid varierande rank
  3. Unikhet över relevanta dokument
  4. Unikhet över alla dokument
  5. Konsekvens