Metodi di ranking probabilistici IR probabilistico Il modello probabilistico: Il principio di pesatura probabilitico, o probability ranking principle (Naïve) Bayesian Text Categorization Bayesian network L’idea chiave è di classificare i documenti in ordine di probabilità di rilevanza rispetto all’informazione richiesta: P(relevante|documentoi, query) Richiami Date due variabili aleatorie a e b: Regola di Bayes p (a, b) p (a b) p (a | b) p (b) p (b | a ) p(a ) p (a | b) p (b) p (b | a ) p (a ) p (b | a ) p(a ) p ( a | b) p (b) Probabilità a posteriori Odds: Probabilità a priori p (b | a) p (a ) xa,a p(b | x) p( x) p(a) p(a) O(a ) p(a ) 1 p(a) Probability Ranking Principle •Sia x un documento della collezione. •Sia R la rilevanza di un documento rispetto ad una (specifica) query e sia NR la non-rilevanza. Si vuole stimare p(R|x) - la probablità che x sia rilevante. p( x | R) p( R) p( R | x) p( x) p( x | NR) p( NR) p( NR | x) p( x) p(R),p(NR) - prob. a priori di recuperare un documento (non) rilevante p ( R | x) p( NR | x) 1 p(x|R), p(x|NR) - probabilità che, se si trova un documento rilevante (non-rilevante), sia x. Probability Ranking Principle (PRP) Bayes’ Optimal Decision Rule x è rilevante iff p(R|x) > p(NR|x) 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 inieme iniziale di risultati può aiutare l’utente a raffinare la sua query Strategia di Retrieval probabilistico Si stima quanto i singoli termini contribuiscano alla rilevanza Si combinano queste stime per assegnare una stima all’intero documento Si ordinano i documenti per probabilità decrescente Binary Independence Model “Binary” = Boolean: i documenti vengono rappresentati mediante un vettore booleano x ( x1 ,, xn ) xi 1 iff wi è contenuto in dj. “Indipendenza”: i termini occorrono nei documenti indipendentemente Documenti diversi possono essere rappresentati mediante lo stesso vettore! Binary Independence Model q di R P(R/q,di) Rank(di)=P(R/q,di) Binary Independence Model Query: vettore booleano Data una query q, Per ogni documento d calcola p(R|q,d). Sostituisci con il calcolo di p(R|q,x) dove x è il vettore booleano che rappresenta d 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) 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 ) Binary Independence Model: effetto dell’inversione 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 ) 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); • Si assume, per tutti i termini che non occorrono nella query: pi ri allora... 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 i i qi 1 pi (1 ri ) 1 pi O( R | q) x q 1 ri (1 pi ) q 1 1 ri i i i i qi 0 Esempio Q= 1 1 1 0 0 0 D= 1 1 0 0 0 1 p1 p 2 (1 p3) (1 p 4) (1 p5) p 6 r1 r 2 (1 r 3) (1 r 4) (1 r 5) r 6 p1 p 2 (1 p3) r1 r 2 (1 r 3) p1 p 2 (1 p3) (1 p3) (1 r1) (1 p1) (1 r 2) (1 p 2) r1 r 2 (1 r 3) (1 r 3) (1 p1) (1 r1) (1 p 2) (1 r 2) p1 (1 r1) p 2 (1 r 2) (1 p1) (1 p 2) (1 p3) r1 (1 p1) r 2 (1 p 2) (1 r1) (1 r 2) (1 r 3) qi=1,xi=1 qi=1 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 ) 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 Come calcoliamo i ci dai dati a disposizione ? 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. 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)?? 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 ri (1 pi ) pi (probabilità di occorrenza di wi in documenti rilevanti, data la query) si può stimare in vari modi: i 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) 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 ciIDF! 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 21 Aggiustamenti della stima Per piccoli valori di V e Vi (ex. Rispettivamente 0 e 1) si usano degli aggiustamenti: ni ni Vi ni Vi N ,r N pi i V 1 N V 1 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. Conclusioni 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 Rimuovere l’assunzione di indipendenza dei termini In generale i termini non occorrono indipendentemente Ma la stima delle dipendenze può essere molto complessa (catene di Markov) van Rijsbergen (1979) propose un semplice modello di dipendenza Ogni termine dipende da uno più termini Reti Bayesiane per IR I modelli probabilistici standard assumono che non si possa stimare P(R|D,Q) Assumono l’indipendenza fra D e Q e stimano P(D|R) Con le Reti Bayesiane è possibile modellare una forma di dipendenza 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 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 Bayesian Networks LINK MATRIX (matrice dei collegamenti) a b p(b) p(a) P(c=1/a=1,=1) c c/ab 1 0 00 01 10 11 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 fd fd 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) Assunzioni di Indipendenza Esame (f) Notte insonne (n) Consegna progetto (d) Depressione (g) Cioccolata e panna (t) • Assunzione di indipendenza: P(t|g, f)=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) 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 o Predittiva Complessità computazionale Per una generica rete: NP-hard Le reti ad albero sono più facilmente trattabili Alcuni autori propongono metodi approssimati (ad esempio basati su programmazione dinamica) 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) fd fd 0.8 0.3 0.2 0.7 vero falso 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 Modello di Retrieval Modella i documenti come una rete (document network) Modella il bisogno informativo come una query network 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) nt un vettore associato ad ogni concetto u tale che gi(k)=1 ki u (pesi unitari) ki una variabile aleatoria binaria (cioè ki0,1 ) associata al termine indice ki , t.c. ki = 1 gi(k)=1 ki u 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 Belief Network Model Topologia della rete q k1 cq lato query ki k2 kt ku k u lato documento cd cd1 d1 dj dn n 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. 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 ku Ogni vettore k definisce un concetto u d1 dj dn 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. Sussumendo un modello vettoriale per i pesi: Definisci il vettore ki come segue: ki = k | ((gi(k)=1) (ji 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. 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) i1 (wi,q / |q|) una versione normalizzata del peso del termine indice ki nella query q Belief Network Model Per il modello vettoriale Definisci dj t (wi, j ) 2 i1 (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 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. Reti Bayesiane per IR (un modello più complesso) di -documenti ti - rappresentazioni dei documenti dn ri - “concetti” Document Network d1 d2 t1 t2 r1 r2 c1 c2 q1 Query Network E’ una rete complessa, ma i calcoli vanno fatti una volta per tutte r3 tn rk cm ci - query concepts Rete piccola, va calcolata per ogni query q2 qi - high-level concepts I I - goal node Bayesian nets per IR P(di) Documenti d1 d2 Document Network P(ti/di) t1 P(ci/ti) P(qj/ci) t3 Termini t2 c1 c2 c3 q1 q2 i Concetti Query Network Operatori booleani della query (AND/OR/NOT) Bisogno informativo Esempio Macbeth Amleto Document Network tormento tormento ambizione ambizione OR doppiezza ambiguità NOT User query Query Network Bayesian Nets per IR Costruisci la rete dei Documenti (una sola volta !) Per ogni query Costruisci la migliore Query Network Collegala alla Document Network Trova un sottoinsieme di documenti di’ che massimizza il valore di probabilità del nodo I (best subset). Restituisci i di’s come risposta alla query. argmax P(I /Dk ) Dk D Stima delle probabilità Prob. a priori dei doc: P(d) = 0,5 P(t|d) Es: basata su tf.idf 1 1 P (ti true / d j true) ntfij nidfi 2 2 N log( ) tfij ni ntfij nidf max(tf j ) log( N ) P(c|t) Caso semplice: =1 Si può usare un thesaurus (dipende dall’ambiguità del termine). Per s “sensi”, 1/s P(Q|c): dipende dalla forma della query booleana Es: pi P(ci true) POR (Q) 1 (1 p1) (1 p2)...(1 pn) PAND(Q) p1 p2 .... pn PNOT (Q) 1 pi Dettagli: http://citeseer.ist.psu.edu/turtle91inference.html H.R. Turtle and W.B. Croft. 1990. Inference Networks for Document Retrieval. Proc. ACM SIGIR: 1-24. Macbeth Amleto Document Network tormento tormento ambizione ambizione OR doppiezza ambiguità NOT User query Query Network