Metodi di ranking probabilistici
1
IR probabilistico


Il modello probabilistico: Il principio di pesatura
probabilistico, o probability ranking principle
Metodi di ranking:



Binary Independence Model
Bayesian networks
L’idea chiave è di classificare i documenti in
ordine di probabilità di rilevanza rispetto
all’informazione richiesta:
P(rilevante|documentoi, query)
2
Probability Ranking Principle
•Sia d un documento della collezione.
•Sia R la rilevanza di un documento rispetto ad una (specifica)
query (R=1) e sia NR la non-rilevanza (R=0).
Si vuole stimare p(R|d,q) - la probablità che d sia rilevante,
data la query q.
p(R|q),p(NR|q) - prob. a priori
p(d | R,q) p(R | q)
p(R | d,q) 
di recuperare un
p(d | q)
documento (non) rilevante
p(d | NR,q) p(NR | q)
p(NR | d,q) 
p(R | d,q)  p(NR | d,q)  1
p(d | q)
p(d|R,q), p(d|NR,q) - probabilità che, se si trova un
documento rilevante (non-rilevante), questo sia d.

3
Probability Ranking Principle (PRP)

Bayes’ Optimal Decision Rule
 d è rilevante iff p(R|d,q) >
p(NR|d,q)
Osservate che, modellando il processo di retrieval in
termini probabilistici, l’occorrenza di una query,
la rilevanza o non rilevanza di un documento,
l’occorrenza di un termine in un documento sono tutti
eventi aleatori
4
Probability Ranking Principle

Come si calcolano le probabilità condizionate?



Si usano “stimatori”
Il modello più semplice è il Binary Independence Retrieval
(BIR)
Assunzioni


La “Rilevanza” di ogni documento è indipendente dalla
rilevanza degli altri documenti.
Usare un modello di rilevanza Booleano:
R={0,1}

Osservare un insieme iniziale di risultati può aiutare l’utente
a raffinare la sua query
5
Strategia di Retrieval probabilistico


Si stima quanto i singoli termini contribuiscano alla
rilevanza
n
Es
P(d )  P( x)  P( x  x  ...x ) 
P( x )
1
2
n

i
i 1
assumendo P( x j / x j 1 , x j  2 ...xn )  P( x j )
P(d / R)  P( x / R)   P ( xi / R )

Si combinano queste stime per assegnare una stima
all’intero documento

Si ordinano i documenti per probabilità decrescente
6
In generale per i modelli
probabilistici:


Si modella un problema in termini probabilistici
(es: la rilevanza di un documento rispetto ad una
query è stimata dalla P(R|d,q))
Poiché in generale è difficile stimare una certo
modello probabilistico (stimare??), si effettuano
una serie di passaggi (ad es. invertire variabile
aleatoria condizionante e condizionata con
Bayes) e semplificazioni (ad es. assumere
l’indipendenza statistica di certe variabili) al fine
di rappresentare il modello probabilistico iniziale
in termini di probabilità più facili da stimare su un
campione.
7
Binary Independence Model

“Binary” = Boolean: i documenti d vengono
rappresentati mediante un vettore booleano


x  ( x1 ,, xn )
xi  1 iff wi è contenuto in dj.
“Indipendenza”: i termini occorrono nei
documenti indipendentemente l’uno dall’altro
Questo è implicitamente assunto anche nel
modello vettoriale, ma in un modello
probabilistico si tratta di una assunzione esplicita.



8
Binary Independence Model
documento
query
di
q
R
Obiettivo: stimare P(R/q,di)
Rank(di)=f(P(R/q,di))
La freccia indica
la dipendenza
statistica:
l’evento
aleatorio R
dipende dall’
evento q
9
Binary Independence Model


Query: vettore booleano
Data una query q,
Per ogni documento d calcola p(R|q,d).
2.
Sostituisci con il calcolo di p(R|q,x) dove x è il
vettore booleano che rappresenta d
3.
Si utilizza la regola di Bayes ed il concetto di
“odd”:

p ( R | q ) p ( x | R, q )



p ( R | q, x )
p( x | q)
O ( R | q, x ) 
  p ( NR | q) p ( x | NR, q)
p ( NR | q, x )

p( x | q)
1.
10
I documenti vengono ordinati (ranking) sulla base del valore di O
Binary Independence Model



p ( R | q, x )
p ( R | q ) p ( x | R, q )
O ( R | q, x ) 
 
 
p( NR | q, x ) p( NR | q) p( x | NR, q)
Costante per
ogni query
Va stimato
• Si usa l’assunzione di Indipendenza :

n
p( xi | R, q)
p( x | R, q)


p( x | NR, q) i 1 p( xi | NR, q)
•Dunque :
n p ( x | R, q )

i
O ( R | q, x )  O ( R | q )  
i 1 p ( xi | NR, q )
11
Binary Independence Model: effetto
dell’inversione delle probabilità
d
q
x1
x2
xi
xn
R
n p ( x | R, q )

i
O ( R | q, x )  O ( R | q )  
i 1 p ( xi | NR, q )
12
Binary Independence Model
n
O ( R | q, d )  O ( R | q )  
i 1
p( xi | R, q)
p( xi | NR, q)
• Ma xi (componente del vettore binario associata a wi) è o 0 o 1:
O ( R | q, d )  O ( R | q )  
xi 1
p( xi  1 | R, q)
p( xi  0 | R, q)

p( xi  1 | NR, q) xi 0 p( xi  0 | NR, q)
• Sia pi  p( xi  1 | R, q); ri  p( xi  1 | NR, q);
NOTA:
pi:che
xi=1,
• Si assume, per tutti i termini
non R=1
occorrono nella query:
ri: xi=1, R=0
pi  ri
(1-pi): xi=0, R=1
allora...
(1-ri): xi=0, R=0
13
Esempio
V{information retrieval paper rank set web}
Q: information retrieval paper
D: information retrieval web
14
Binary Independence Model
Q= 1 1 1 0 0 0
D= 1 1 0 0 0 1

O ( R | q, x )  O ( R | q ) 
pi
1  pi
 
  (1)

x q 1 ri x 0 1  ri x ?
i
V{information retrieval paper rank set web}
i
i
qi 1
i
qi 0
Q: information retrieval paper
D: information retrieval web
pi (1  ri )
1  pi
 O( R | q)  
 
x q 1 ri (1  pi ) q 1 1  ri
i
i
i
15

Esempio
Q= 1 1 1 0 0 0
D= 1 1 0 0 0 1
p1 p2 (1 p3) (1 p4) (1 p5) p6

(1 pi)(1 ri)
r1 r2 (1 r3) (1 r4) (1 r5) r6
pi
(1 pi)
(1
pi)(1
ri)


p1 p2 (1 p3)
qi1,xi1
ri qi1,xi0 (1 ri)

xiqi1
r1 r2 (1 r3)
p1 p2 (1 p3) (1 r1) (1 p1) (1 r2) (1 p2)

r1 r2 (1 r3) (1 p1) (1 r1) (1 p2) (1 r2)

p1 (1 r1) p2 (1 r2) (1 p1)(1 p2) (1 p3)
r1 (1 p1) r2 (1 p2) (1 r1) (1 r2) (1 r3)
qi=1,xi=1
qi=1
16
Binary Independence Model

O( R | q, x )  O( R | q) 
pi (1  ri )
1  pi


xi  qi 1 ri (1  pi ) qi 1 1  ri
Costante per
ogni query
• Retrieval Status Value:
Questa è la sola quantità che
va stimata per il ranking
pi (1  ri )
pi (1  ri )
RSV  log 
  log
ri (1  pi )
xi  qi 1
xi  qi 1 ri (1  pi )
17
Binary Independence Model
• Tutto si riduce a stimare RSV.
pi (1  ri )
pi (1  ri )
RSV  log 
  log
ri (1  pi )
xi  qi 1
xi  qi 1 ri (1  pi )
pi (1  ri )
RSV   ci ; ci  log
ri (1  pi )
xi  qi 1
I documenti sono ordinati secondo il RSV. Questo dipende
dall’intersezione fra parole della query e parole del documento
(il set xi=qi=1) ma anche dai valori di pi e ri
Come calcoliamo i ci dai dati a disposizione ?
18
Binary Independence Model
Stimare i coefficienti RSV
• Per ogni termine i della query osserva la tabella dei documenti
rilevanti e non : Documenti Rilevanti Non-Rilevanti Totale
Xi=1
Xi=0
Totale
s
S-s
n-s
N-n-S+s
n
N-n
S
N-S
N
(n  s)
ri 
• Stime:
(N  S)
s ( S  s)
ci  K ( N , n, S , s )  log
(n  s) ( N  n  S  s)
s
pi 
S
Per ora,
assumiamo
non esistano
termini
che non
compaiono mai.
19
Binary Independence Model

Ma come si può riempire la tabella di rilevanza
per ciascun termine della collezione?

Data una collezione di N documenti, posso
calcolare n (il numero di documenti con Xi=1) e
dunque N-n (quelli con Xi=0), ma come si stima il
valore S (numero di documenti
complessivamente rilevanti per la query)??
20
Stima di ri (P(xi=1/NR,q))

Posso approssimare N-S con N (se N>>S  N-S N) .
Allora, ri (prob. di un documento non rilevante data una
query) è stimata da: n/N , e:
p (1  r )
ci  log


log (1– ri)/ri ≈ log (N– ni)/ ni ≈ log N/ ni = IDF!
i
i
ri (1  pi )
pi (probabilità di occorrenza di wi in documenti rilevanti,
data la query) si può stimare in vari modi:



Facendo selezionare all’utente alcuni documenti rilevanti di
esempio
Con una costante, dipendente solo dal valore idf dei termini (i
termini più comuni nella collezione hanno probabilità più
bassa di rilevanza)
Proporzionale all’occorrenza dei termini nella collezione ( i
termini più frequenti in assoluto sono i più rilevanti. In
generale si usa il log della frequenza)
21
+ comuni + frequenti
Stima iterativa di pi (P(xi=1/R,q))
1.
Assumi pi costante per tutti i termini wi della query

2.
Ordina i documenti della collezione sulla base dei ci
(formula RSV) calcolati per tutti i termini della query, e
mostra all’utente i primi |V | :

3.
pi = 0.5 per ogni termine presente nella query
Nota: se pi = 0.5 e ri ni/N allora ciIDF!
Si cerca di migliorare le stime di pi e ri, nel seguente
modo:

Si utilizza la distribuzione dei termini wi nei documenti di V.
Sia Vi il set di documenti in V che contiene wi


pi si approssima con la distribuzione dei
termini della query nei documenti recuperati
Si assume che quelli non in V non siano rilevanti:

4.
pi = |Vi| / |V|
ri = (ni– |Vi|) / (N – |V|)
Torna allo step 2. e continua fino alla convergenza
22
Aggiustamenti della stima

Per piccoli valori di V e Vi (ex. Rispettivamente 0 e 1) si
usano degli aggiustamenti, per evitare che pi e ri (o i
loro complementi) vadano a zero, portando a zero num
o denom dell’argomento del logaritmo :
ni
ni
Vi 
n i  Vi 
N ,r 
N
pi 
i
V 1
N  V 1
Una formula più semplice utilizza 1/2 al posto di ni/N

23
Esempio
D1
w1
w2
w3
w4
w5
w6
w7
w8
w9
w10
w11
w12
D2
1
D3
1
1
D4
1
1
1
1
1
1
D5
D6
1
1
1
1
1
1
1
1
1
D7
Q
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
24
Step 1
STEP 1
w3
w4
w5
D1
RSV
ri=ni/N
pi
0,29
0,57
0,71
D2
0,6902
|V|=2
ci
0,50
0,50
0,50
0,54406804
0,24303805
0,14612804
D3
D4
D5
D6
D7
0 0,389166 0,933234 0,146128 0,389166 0,38916608
pi = 0.5 , ri ni/N ciIDF!
RSV(Di) 

ci
wi(Di,Qi)
25
STEP 2
ni
ni
Vi 
n i  Vi 
N ,r 
N
pi 
i
V 1
N  V 1
pi (1  ri )
ci  log
ri (1  pi )
V=2 N=7 ni= occorrenze di wi nella collezione
Vi=occorrenze di wi in V
STEP 2
w3
w4
w5

ri
0,29/6
3,57/6
4,71/6
pi
2,29/3
1,57/3
2,71/3
ri
pi
0,048
0,59
0,78
ci (no log)
log
0,76
3,16 0,49968708
0,52
1,46 0,16435286
0,93
3,7 0,56820172
RSV
D1
D2
1,067889
D3
D4
D5
D6
D7
0 0,732555 1,2322417 0,5682017 0,732555 0,732555
26
Probabilistic Relevance Feedback
1.
2.
3.
Come prima, assegna un valore costante ai pi ed estrai
un primo set V di documenti.
Interagisci con l’utente e chiedi di selezionare alcuni
documenti rilevanti e non rilevanti in V (in tal modo
ottengo un subset di V’ documenti dei quali conosco S e
V’-S)
Stima nuovamente pi e ri sulla base di questi documenti

Oppure combina questa informazione con la precedente,
aumentando o diminuendo le precedenti stime
( 2)
i
p
4.
| Vi | pi(1)

| V | 
Ripeti, generando una successione di approssimazioni.
27
Conclusioni sul BIM


E’ possibile ottenere delle stime di rilevanza.
Tuttavia è necessario fare delle assunzioni
restrittive:



Indipendenza dei termini
I termini non presenti nella query non
determinano il risultato
Si usa una rappresentazione booleana dei
documenti e delle query
Alcune di queste assunzioni possono essere
rimosse
28
Riferimenti su BIM

http://nlp.stanford.edu/IRbook/html/htmledition/probabilistic-approachesto-relevance-feedback-1.html
29
Rimuovere l’assunzione di
indipendenza dei termini




In generale i termini non
occorrono
indipendentemente
Ma la stima delle
dipendenze può essere
molto complessa
van Rijsbergen (1979)
propose un semplice
modello di dipendenza
Ogni termine dipende da
uno più termini
30
Reti Bayesiane per IR

Cosa è una Bayesian network?



Un grafo aciclico diretto DAG
Nodi:
 Eventi, variabili aleatorie, o variabili
 Possono assumere valori
 Per semplicità, nel modell BN-IR, tali valori
si assumono booleani
Archi:
 Modellano una dipendenza diretta fra nodi
31
Bayesian Networks
a,b,c - nodi
a
• Le reti Bayesiane modellano la
dipendenza fra eventi
p(b)
b
p(a)
c
•Inference in Bayesian Nets:
Dipendenza
condizionale
p(c|ab) per ogni valore
di a,b,c
P(c)  P(c /a)P(a)  P(c /b)P(b)
•note le probabilità a priori per le
radici del grafo
e le probabilità condizionate
(archi) si può calcolare la
probabilità a priori di ogni evento
condizionato.
• Se sono noti i valori di verità di
alcuni nodi (ad esempio,
l’osservazione dell’evento b e di
a) si possono ricalcolare le
probabilità dei nodi
32
Bayesian Networks
LINK MATRIX (matrice dei collegamenti)

a
b
p(b)
p(a)
P(c=1/a=1,=1)
c
c/ab
00
01
10
11
1
0
33
Esempio giocattolo
f
f
0 .3
0 .7
Esame
(f)
f f
n 0.9 0.3
n 0.1 0.7
Notte
insonne
(n)
Consegna progetto d
d
(d)
fd fd
Depressione g 0.99 0.9
g 0.01 0.1
(g)
0. 4
0. 6
fd fd
0.8
0.3
0.2
0.7
LINK MATRIX
t
t
g
0.99
0.01
g
0.1
0.9
Cioccolata e panna
(t)
P(g/ f ,d)
34
Assunzioni di Indipendenza
Esame
(f)
Notte
insonne
(n)
Consegna progetto
(d)
Depressione
(g)
• Assunzione di indipendenza:
P(t|g,f,d)=P(t|g)
• Probabilità congiunte:
P(f d n g t)
=P(f) P(d) P(n|f) P(g|f d) P(t|g)
Cioccolata e panna
(t)
35
Chained inference


Evidenza - si parte dal valore di alcuni nodi (ad es.
radice)
Inferenza

Si calcola la “credenza” o belief (rappresentata
eventualmente da probabilità) degli altri nodi



Probabilità condizionata all’evidenza rappresentata dai nodi
“conosciuti”
Due tipi di inferenza: Diagnostica (dall’evento alla causa) o
Predittiva (date le possibili cause, stimare la prob. di
osservare l’evento causato)
Complessità computazionale

Per una generica rete (grafo ciclico) : NP-hard


Le reti ad albero sono più facilmente trattabili
Alcuni autori propongono metodi approssimati (ad esempio
basati su programmazione dinamica)
36
Esempio giocattolo
f
f
0 .3
0 .7
Esame
(f)
Consegna progetto d
d
(d)
0. 4
0. 6
vera
f f
n 0.9 0.3
n 0.1 0.7
t
t
Notte
insonne
(n)
g
0.99
0.01
g
0.1
0.9
fd fd
0.99 0.9
Depressione g
g 0.01 0.1
(g)
Cioccolata
e panna

(t)
fd fd
0.8 0.3
0.2
0.7
vero
falso
37
P(t)=0,99x0,9+0,1x0,1
Modello bayesiano per IR

Obiettivo


Data una richiesta di informazione da parte di un
utente (evidenza) stima la probabilità che un
documento soddisfi la richiesta (inferenza)
Modello di Retrieval


Modella i documenti come una rete (document
network)
Modella il bisogno informativo come una query
network
38
Belief Network Model: un modello di
ranking basato su Reti Bayesiane
Definizioni:
K={k1, k2, ...,kt} spazio di campionamento (o spazio
dei concetti)
u  K un subset di K (un concetto)
ki un termine indice (concetto elementare)
k=(k1, k2, ...,kn) nt un vettore associato ad ogni
concetto u tale che gi(k)=1  ki  u (pesi unitari)
ki una variabile aleatoria binaria (cioè ki0,1 )
associata al termine indice ki , t.c. ki = 1  gi(k)=1
 ki  u
39
Belief Network Model
Definizioni (2):






un documento dj e una query q sono rappresentati come
concetti in K, composti dai termini indice contenuti in dj e q.
Sia dunque c un concetto generico in K (documento o query)
P(c)=uP(c|u) P(u) è una distribuzione di probabilità P su K
P(c) è il definito come il grado di copertura dello spazio K
mediante c
Questa copertura è stimata confrontando ogni concetto in K (“
u”) con c, e sommando i contributi, pesati con le probabilità dei
singoli concetti u.
Si assume inizialmente equiprobabilità delle sottostringhe u in K
(se ho t termini, ciascuno dei quali può essere presente o
assente in u, ci sono 2t possibili modi di formare concetti u),
cioè: P(u)=(1/2)t
40
Belief Network Model
Topologia della rete
q
k1
cq
lato query
ki
k2
kt
ku
k u
lato documento
cd
cd1
d1
dj
dn
n
41
Q
information calculus retrieval
Information retrieval probability
probability journal finding
information
retrieval
journal
information
finding
d1
d2
probability
retrieval
calculus
d3
information
retrieval
calculus
d4
42
Belief Network Model
Il ranking di un documento dj rispetto ad una query q è interpretato
come una relazione di corrispondenza fra concetti, e riflette il grado di
copertura che il concetto dj fornisce al concetto q.
Documenti e query sono trattati nello stesso modo, cioè sono
entrambi concetti nello spazio K.
Assunzione:
P(dj|q) viene considerato come il rank del documento dj rispetto alla query
q.
http://portal.acm.org/citation.cfm?id=243272 (Ribeiro and Munz,
1996: “A belief network model for IR”)
43
Belief Network Model
Ranking di dj
P(dj|q) = P(dj  q) / P(q)
= P(dj  q)
= u P(dj  q | u) P(u)
~ u P(dj / u) P(q / u) P(u)
~ k P(dj / k) P(q / k) P(k)
q
k1
ki
k2
kt
Questo fattore
compare in tutti i
P(dj/q) dunque può
essere trascurato
Assumendo q e
dj condizionalmente
indipendenti rispetto
a u , come si evince
dal grafo delle
dipendenze nella rete
ku
Ogni vettore k definisce un concetto u
d1
dj
dn
44
Belief Network Model
Dunque: P(dj|q) ~ k P(dj | k) P(q | k) P(k)
Occorre specificare le probabilità condizionate P(dj | k)
e P(q | k) . Differenti strategie per modellare P(dj | k) e
P(q | k) portano a diversi modelli di ranking.
Ad esempio, assumiamo un vocabolario di 3 parole:


Information,retrieval, extraction (I,R,E)
I concetti possibili sono: (I,R,E), (I,R,-), (I,-,E), (-,R,E), (-,,E),(-,R,-),(I,-,-),(-,-,-)
P(d i ,k1,k2 ,k3)
P(k1 / k2 ,k3)P(k2 / k3)P(k3)
Per k concetti, o(k!) stime
stimabile
P(d i / k1,k2 ,k3) 
45
A belief network model for IR
Sussumendo un modello vettoriale (Ribeiro and
Muntz) per i pesi e l’indipendenza dei termini:
 Definisci il vettore ki come segue:
ki = k | ((gi(k)=1)  (ji gj(k)=0))
Il vettore ki si riferisce ad uno stato del vettore k in
cui solo il nodo ki è attivo (g(ki)=1) e tutti gli altri
non lo sono. Questo riflette la strategia di ranking
tf-idf, che somma individualmente il contributo di
ogni keyword. Quindi, si considera il contributo di
ogni termine ki singolarmente.
46
Belief Network Model
P(dj|q) ~ k P(dj | k) P(q | k) P(k)
Per il modello vettoriale:
Definisci
peso tf-idf di ki in q
ki compare in q
(wi,q / |q|)
se (k = ki ) (gi(q)=1)
0
se (k  ki ) (gi(q)=0)
P(q | k) =
q
t

(wi,q )2
P(¬q | k) = 1 - P(q | k)
i1
 (wi,q / |q|) una versione normalizzata del peso del
termine indice ki nella query q
47
Belief Network Model
Per il modello vettoriale
Definisci
dj 
t
(wi, j ) 2
i1

(wi,j / |dj|) se (k = ki ) (gi(dj)=1)
P(dj | k) =
0
se (k  ki ) (gi(dj)=0)
P(¬ dj | k) = 1 - P(dj | k)
 (wi,j / |dj|) una versione normalizzata del peso del
termine indice ki nel documento d,j
48
Belief Network Model


Mettendo tutto assieme..
P(dj|q) ~ k P(dj | k) P(q | k) P(k)=
1 1
( 
q dj

k1,,t
wkq  wkj  t 1)  cossin(q,d j )
Riformulazione probabilistica del modello vettoriale!!
49
Vantaggi del Belief Network
model


Per calcolare il rank di un documento, considera solo
gli stati della rete in cui i nodi attivi sono quelli che
compaiono nella query, quindi il costo è lineare nel
numero dei documenti della collezione
E’ una variante moderna dei metodi di ragionamento
probabilistico, che consente una combinazione di
distinte sorgenti di evidenza. I modelli più avanzati
consentono di incorporare nel modello evidenze
derivate da sessioni precedenti, e feedback
dell’utente.
50
Bayesian Network Retrieval Model
Si può rimuovere l’ipotesi di indipendenza:
 Si rappresentano le principali (più probabili)
relazioni di dipendenza statistica fra i termini
della collezione.
Term subnetwork  Polytree
Ci sono algoritmi efficenti per l’analisi di polytrees.
51
Bayesian Network Retrieval Model
Termini “radice” (indipendenti)
Sottorete dei termini
k5
k2
k1
Sottorete dei
D1
query
k4
k6
k3
D2
D3
D4
documenti
52
Bayesian Network Retrieval Model
Distribuzioni di probabilità:
Distribuzioni “marginali” (dei nodi-termine
radice):
1
p(ki ) 
, p(ki )  1 p(ki )
V
(|V|=t dimensione del vocabolario)
53
Bayesian Network Retrieval Model
Distribuzioni condizionali (basate sul coefficiente
di Jaccard) per i termini dipendenti:
E(p)=valore
atteso di p
J (A,B) 
A B
A B

A B A  B  A B
freq (ki , pa (ki ))
E[ p(ki | pa (ki ))] 

freq (ki )  freq ( pa(ki ))  freq (ki , pa (ki ))
p(ki | pa(ki ))  1 p(ki | pa(ki ))
pa (k) tutti gli n nodi da cui k dipende
condizionalmente (es

p(rank/(information,retrieval,search,index))
54
Bayesian Network Retrieval Model
Un sistema più semplice (“Two Layers” ):
-Si considera solo un sottoinsieme di termini
“condizionanti”
-L’analisi della rete è più veloce
55
Two Layers Bayesian Networks
(Xu et al. 2009)

Si modella la dipendenza fra termini in funzione
della “word similarity”
Ogni concetto ki viene
duplicato (ki’)
p(k i / p(k i ))  

sim(k i , k j )
k j  p(ki )
La dipendenza è stimata in funzione della similarità
56
Dipendenza=f(similarità)
57
Stima di P(dj/u)
58
Stima delle dipendenze
Word Similarity measures:
BOLLEGALA, D.,MATSUO, Y., AND ISHIZUKA,M. 2007. Measuring semantic
similarity between wordsusing web search engines.
In WWW’07: Proceedings of the 16th International Conference onWorld
Wide Web. ACM, New York, 757–766.
Google Set: http://labs.google.com/sets
59
60
61
Per Riassumere
Q=k1 k2
U’=k1k2
U=k1k2kj
k1k2 kj
k2 kj
kj kt
62
Esempio
Q=k1 k2
U’=k1k2
U=k1k2kj
wk1k1 wk2w2  wkjkj
| d1 || u |
wk2w2  wkjkj
P(d 2 /U) 
| d 2 || u |
wkjkj
P(dN /U) 
| dN || u |
P(d1/U) 
k1k2 kj k2 kj
kj kt
p(k1' k2' / k1k2kj) 


1
(P(k'1/ k1,k2)  P(k2' / k2,kj))
2
63
Conclusioni




I modelli probabilistici rappresentano il problema del
retrieval mediante probabilità condizionate (es. P(R/q,d)).
Alcuni modelli consento di “rilassare” l’ipotesi di
indipendenza fra termini
Occorre stimare le probabilità condizionate fra termini (in
genere bigrammi o trigrammi P(ti/tj) o P(ti/tj,tk)
Fra i metodi per determinare correlazioni fra termini c’è il
Latent Semantic Indexing, che è un metodo algebrico per
stimare la similarità fra documenti, e fra documenti e
query (next lesson!)
64