Bayesian Reranking

Preprocessing

Doe per topic (d.w.z. per ranking):

  • Vector met counts voor alle keywords in alle resultaten
    • Zie scikit's CountVectorizer
  • Elk document is een lijst met keywords (dus kan dubbele woorden bevatten)
    • Anserini index heeft al een DocVector
  • Alle gerankte documenten samen kun je dan representeren als een matrix, met elke row een document en de columns alle keywords.

Initialiseren en prior

k = N = 1000

Want het is gebruikelijk in TREC om 1000 documenten in een ranking te zetten. We beginnen met één hidden property $\theta_k$ per resultaat, dus we hebben k=N.

Initialiseer theta's:

We beginnen dus met een theta per passage. De theta voor die passage is een verdeling over de woorden in die passage.

Dus als we een docuement "Rosa is een rare aap, toch Rosa?" hebben, dan zou een theta kunnen zijn:

{ "rosa" = 0.5, "raar"=0.25, "aap"=0.25, "Edwin"=0, "Lilian"=0, ... = 0 }

De lengte van die vector is het hele vocabulaire :-) Dus de meeste entries zullen 0 zijn.

Prior:

De prior van $\theta_j$ is een Poisson verdeling over $\theta_j$. We hebben:

1) het aantal counts per keyword over alle resultaten (die countVectorizer van boven) 2) en we weten dat elk topic een bepaalde verwachting uitdrukt over de frequentie van keywords

Dat wil zeggen dat we per keyword een verwachting hebben (de entry voor dat keyword in $\theta_j)$ en ook weten hoe vaak hij daadwerkelijk in alle resultaten samen voorkomt. We gooien die vectors door de Poisson verdeling heen, d.w.z. voor elk keyword krijgen we een waarde uit die verdeling. De output is dan dus een Poisson verdeling over theta.

Nee, misschien toch fout: dat is een Poisson over $\theta_j$. Voor $\theta_j$ willen we denk ik toch een vast nummer;

Één dingetje: als een topic een verdeling is, moeten we dat nu uitdrukking in termen van het verwachte aantal counts. Dat kan dus als p(keyword) x een bepaald interval (bijv. lengte van een document).

Maar de Poisson is dedefinieerd over één hetzelfde interval, dus we moeten die wel gelijktrekken. Dus als "n" voorvallen van een keyword is gedefinieerd op alle resultaten, moeten we denk ik ook de verwachte counts volgens $\theta_j$ uitdrukken op alle resultaten, zodat we ze kunnen vergelijken.

Marginal over data:

$p(x_i)$

Weet niet of we deze nodig hebben, denk het niet. Het belangrijke is dat deze gelijk blijft aangezien de data gelijk blijft. In de MAP kunnen het daarom negeren, aangezien we alleen in een maximum geintereseerd zijn en deze "normalisatie" stap dus kunnen vergeten.

Likelihood $l(\theta_j|x_i) = P(x_i|\theta_j)$:

De likelihood van een parameter is gedefinieerd in termen van hoe waarschijnlijk de data (die we observeren) is geven $\theta$. We hebben al een hidden property $\theta$ die een verdeling over woorden is. D.w.z. voor woord a zegt die topic p=0.04, voor woordje b zegt die topic p=0.05. Als we dan een document $x_i$ hebben (een lijst keywords), dan is de probabability van dat document geven de verdeling van $\theta$ voor een document ['a', 'b'], p=0.04x0.05. Zo "waarschijnlijk" is de data als $theta$ inderdaad het geval is.

Om kleine gevallen (numerical underflow) te voorkomen gebruiken we de log-likelihood.

$$P(x_i) = P(x_{i1})x, ... ,x P(x_{in})$$

d.w.z. de probability van een passage (begrepen als een lijst keywords) is dus gewoon de probability van al die keywords vermenigvuldigd:

$$ P(x_i) = \prod_{j}^{#words} P(x_{ij})$$

Omdat een logarithme van producten, hetzelfde is als een som van logarithmes ( log(axb)=log(a)+log(b) ), hebben we:

$$log( P(x_i|\theta_j)) = \sum_{j}^{J} log(P(x_{ij}))$$

Argmax operatie per iteration

Idee: als we posterior $p(\theta_j|x_i)$ hebben, dan betekent de argmax operatie dat we het document (dus keyword vector) vinden waarvoor de probability van die hidden property het hoogste is. De argmax operatie geeft dus een van de documentvectors terug!

Als bijvoorbeeld $\theta_1$ en $\theta_5$ allebei argmax $x_3$ hebben, dan kunnen we $\theta_1$ en $\theta_5$ groeperen.

Waarom Poisson?

Poisson gedefinieerd op zeldzame gevallen op een interval. Als een interval een vector met alle keywords is, dan komen voor een gegeven passage de meeste keywords niet voor. De keywords die dus wel voorkomen kunnen gezien worden als een "zeldzame gebeurtenis". ( 0 entries zouden ook geen probleem moeten zijn voor Poisson! ) Dus bijvoorbeeld een topic voorspelt voor 100 woorden (van de 100.000) een bepaalde count/frequency en het voorkomen van elk van die woorden is een zeldzame "gebeurtenis".