IR - 07 - Ranking II

In questa lezione abbiamo continuato a trattare il problema del ranking introdotto nella lezione precedente.

Nella precedente lezione avevamo introdotto la weight matrix, costruita tramite la pesatura \(\text{tf-idf}\) calcolata per ogni termine in ogni documento.

Come già discusso, a partire dalla weight matrix è possibile costruire un vector space model, ovvero uno spazio vettoriale i cui punti rappresentano documenti e/o query e la cui dimensione è data dal size del vocabolario \(|V|\).

Una possibile soluzione al problema del ranking consiste dunque nel prendere la query fornita dall'utente, calcolare la sua rappresentazione in questo particolare spazio vettoriale tramite la pesatura tf-idf, e ritornare i documenti la cui rappresentazione nel medesimo spazio vettoriale risulti essere simile alla rappresentazione della query fornita. Per fare questo però necessitiamo di avere una buona misura di similarità.

Un primo approccio potrebbe essere quello di utilizzare la distanza euclidea, ma abbiamo già visto al termine della precedente lezione che questa misura non è ottimale. Un approccio migliore consiste di considerare non la distanza tra i vettori, ma bensì l'angolo sotteso tra i vettori come misura di similarità. Utilizzare l'angolo rispetto alla distanza ha vari vantaggi, come mostra il seguente esempio concettuale:

Esempio: Supponiamo di prendere un documento \(d\) e di appenderlo a se stesso, ottenendo un nuovo documento \(d'\). Anche se il documento \(d'\) è "due volte" il documento originale \(d\), il contenuto semantico dei due documenti è essenzialmente invariato. Notiamo però come si comportano le due metriche introdotte: la loro distanza euclidea non è \(0\), mentre l'angolo sotteso tra i due vettori lo è.

L'idea quindi è quella di utilizzare l'angolo sotteso tra due vettori per stabilire quanto questi sono simili tra loro: più simili due vettori sono, e più piccolo è l'angolo sotteso tra i due.

Notiamo però che prendendo l'angolo sottesso, abbiamo che più l'angolo decresce e più la similarità cresce. Per avere una misura di similarità che cresce con il crescere della similarità possiamo utilizzare la funzione \(\cos(\theta)\) al posto del semplice angolo \(\theta\). Infatti, nell'intervallo \([0, \pi]\), più l'angolo cresce, e più il coseno decresce, ovvero più due documenti sono distanti (\(\theta\) grande), e più il coseno dell'angolo sotteso tra i documenti (o meglio, tra le rappresentazioni vettoriali dei documenti) diminuisce. Il valore massimo è poi assunto per \(\theta = 0\), ovvero quando i due vettori hanno esattamente lo stesso angolo. In altre parole, effettuando la seguente trasformazione

\[\theta \to \cos(\theta)\]

siamo in grado di definire una misura di similarità il cui valore è più grande tanto più simili sono i documenti misurati.

Al fine di calcolare il coseno di ogni coppia di vettori una procedura utile è la normalizzazione, che ci permette di mappare lo spazio vettoriale nel cerchio centrato nell'origine di raggio \(1\). In particolare, utilizzando la norma \(L_2\), definita come segue

\[\left\Vert x \right\Vert_2 := \sqrt{ \sum\nolimits_{i} x_i^2 }\]

abbiamo che per normalizzare il vettore \(x\) ci basta dividerlo per la sua norma

\[x' := \frac{x}{\Vert x \Vert_2} = \frac{x}{\sqrt{\sum\nolimits_{i} x_i^2}}\]

In questo modo la lunghezza del vettore \(x'\) sarà, per definizione, uguale ad \(1\)

\[\Vert x' \Vert_2 = \Bigg\Vert \frac{x}{\Vert x \Vert_2} \Bigg\Vert_2 = \Bigg\Vert \frac{1}{\Vert x \Vert_2} \cdot x \Bigg\Vert_2 = \frac{1}{\Vert x \Vert_2} \cdot \Vert x \Vert_2 = 1\]

Per calcolare il coseno sotteso tra i due angoli possiamo calcolare il prodotto scalare dei due vettori. A tale fine, sia \(q_i\) il peso \(\text{tf-idf}\) del termine \(i\) nella query \(q\), e sia \(d_i\) il peso \(\text{tf-idf}\) del termine \(i\) nel documento \(d\). La cosine similarity di \(q\) e \(d\) è quindi calcolata come segue

\[\cos(q, d) = \text{sim}(q, d) = \frac{q}{\left\Vert q \right\Vert_2} \cdot \frac{d}{\left\Vert d \right\Vert_2} = \frac{q \cdot d}{\left\Vert q \right\Vert_2 \left\Vert d \right\Vert_2} = \frac{\sum\limits_{i = 1}^{|V|} q_i d_i }{\sqrt{\sum_i q_i^2} \sqrt{\sum_i d_i^2}}\]

Se poi i vettori \(q\) e \(d\) sono stati normalizzati, la formula si semplifica e diventa più semplice da calcolare, in quanto diventa il semplice prodotto scalare dei due vettori.

\[\cos(q, d) = \text{sim}(q, d) = q \cdot d = \sum\limits_i q_i d_i\]

Esistono almeno due approcci per calcolare il cosine score, e questi sono:

  • TAAT (Term-At-A-Time): Questo metodo consiste nello scorrere i termini della query uno alla volta. Per ciascun termine poi ci si scorre la posting list del termine e si aggiorna lo score di ogni documento. Segue uno pseudocodice che implementa questo calcolo

  • DAAT (Document-At-A-Time).

Per rendere più efficiente la risposta del sistema poi, al posto di calcolare la similarità rispetto a tutti i documenti, una struttura dati più intelligente come una coda di priorità può essere utilizzata per gestire solamente i \(K\) documenti più simili alla query, permettendoci quindi di non dover riordinare tutti i documenti, che risulta essere una operazione molto dispendiosa.

La pesatura tf-idf può essere implementata in svariati modi. Per implementare una particolare pesatura tf-idf possiamo muoverci rispetto ai tre seguenti campi:

  • Term frequency: Esistono varie funzioni per stabilire come la term frequency dovrà pesare nel risultato finale. Tra queste troviamo:

    • natural (a)

      \[\text{tf}_{t,d}\]

    • logarithm (l)

      \[1 + \log{\text{tf}_{t,d}}\]

    • augmented (a)

      \[0.5 + \frac{0.5 \cdot \text{tf}_{t, d}}{\max_t{\text{tf}_{t, d}}}\]

    • boolean (b)

      \[\begin{cases} 1 &,\,\, \text{if } \text{tf}_{t, d} > 0 \\ 0 &,\,\, \text{otherwise} \end{cases}\]

    • log average (L)

      \[\frac{1 + \log{\text{tf}_{t, d}}}{1 + \log{\text{ave}_{t \in d} \text{tf}_{t, d}}}\]

  • Document frequency. Possiamo anche cambiare il modo in cui viene pesata la "rarità" dei vari termini. In questo contesto troviamo

    • no (n)

      \[1\]

    • idf (t)

      \[\log{\frac{N}{\text{df}_t}}\]

    • prob idf (p)

      \[\max\Big\{0, \,\,\, \log{\frac{N - \text{df}_t}{\text{df}_t}}\Big\}\]

  • Normalization. Infine, possiamo cambiare il modo in cui normalizziamo i vari vettori. Qui abbiamo le seguenti possibilità

    • none (n)

      \[1\]

    • cosine (c)

      \[\frac{1}{\sqrt{w_1^2 + w_2^2 + \ldots + w_M^2}}\]

    • pivoted unique (u)

      \[\frac{1}{u}\]

    • byte size (b)

      \[\frac{1}{\text{CharLength}^{\alpha}}, \,\,\, \alpha < 1\]

L'idea in generale è comunque quella di mischiare un modo per stimare il peso della term frequency, un modo per stimare il peso della document frequency e infine un eventuale modo per normalizzare il tutto. Gli attuali sistemi di information retrieval utilizzando un particolare tipo di pesatura tf-idf.

Esiste una notazione, chiamata notazione SMART, che permette di denotare lo schema particolare utilizzato in una IR engine.

La notazione SMART è compost da \(6\) caratteri, \(3\) per il documento e \(3\) per la query, che specificano come vengono trattati rispettivamente la term-frequency, la document-frequency, e la normalizzazione.

Ad esempio un tipico schema di pesatura utilizzato è \(\text{lnc.ltn}\).

Nel vector space model appena descritto la rilevanza che assegniamo ad un documento dipende principalmente dalla term-frequency e dalla document frequency, che sono quantita di natura strettamente deterministica. Andiamo adesso a descrivere un modello probabilistico in cui non si definisce in modo specifico come poter calcolare la rilevanza, ma bensì si delega questo problema in un contesto più esterno, e si lavora assumendo che ci sia una variabile booleana esterna che ci dice se il documento è rilevante o no per una data query.

L'idea è quindi quella di modellare una situazione di incertezza in cui non sappiamo esattamente se un documento è rilevante o no per una data query. Notiamo che anche utilizzando lo space vector model non sapevamo esattamente se i documenti più simili sono effettivamente quelli più rilevanti per la query dell'utente. Quello che stiamo facendo adesso è utilizzare un modello matematico che utilizzata formalmente questa incertezza.

Esistono vari modelli probabilistici per fare pesatura di documenti. Tra questi troviamo:

  • Binary Independence Model.

  • BestMatch25 (Okapi).

Data una collezione di documenti, e date delle variabili aleatorie binarie \(R_{d, q}\) definite nel seguente modo

\[R_{d, q} := \begin{cases} 1 \,\,\,\,&,\,\,\,\, \text{if document } d \text{ is relevant for query} q \\ 0 \,\,\,\,&,\,\,\,\, \text{else} \\ \end{cases}\]

il ranking probabilistico cerca di ordinare i documenti utilizzando la loro probabilità di rilevanza, ovvero il valore di \(P(R = 1 | d, q)\). Nella trattazione che segue si assume quindi che la rilevanza di un documento è indipendente dalla rilevanza degli altri documenti.

La tesi sottostante questo modello, che prende il nome di probabilistic ranking principle (PRP) è la seguente: se i documenti vengono ordinati in base alla loro probabilità di essere rilevanti rispetto alla query, allora il sistema si comporta nel modo migliore possibile.

Come conseguenza di questo principio abbiamo che, se fossimo in grado di calcolare in modo esatto questa probabilità di rilevanza, ci basterebbe ritornare i documenti ordinandoli rispetto ai valori di probabilità ottenuti per ottenere il comportamento migliore. Dato però che non è possibile calcolare direttamente questa probabilità, dobbiamo stimarla utilizzando dei dati.

Per cercare di ottenere più dati un possibile modo potrebbe essere quello di osservare il comportamento degli utenti.

In questo modello sia i documenti che le query vengono rappresentati come vettori a valori binari che hanno una componente per termine e la componente associata al termine \(t\) è uguale a \(1\) se e solo se il termine \(t\) occorre nel documento (e quindi è \(0\) altrimenti).

Diversi documenti possono avere quindi la stessa rappresentazione binaria vettoriale, anche se magari la frequenza dei termini nei documenti è molto diversa. Si assume inoltre che i termini siano indipendenti tra loro. Questa ipotesi non è vera, ma funziona nella pratica.

Utilizzando questo modello per cercare di stimare la rilevanza di un documento data una query dobbiamo trovare delle statistiche adeguate e combinarle nel modo giusto. In particolare vogliamo stimare \(P(R | d, q)\), dove \(d\) è il documento, e \(q\) è la query. Per fare questo modelliamo il documento \(d\) e la query \(q\) tramite due vettori \(x\) e \(q\).

Valgono quindi le seguenti formule

\[\begin{align} P(R = 1 \,\,|\,\, x, q) &= \frac{P(x \,\,|\,\, R = 1, q) \cdot P(R = 1 \,\,|\,\, q)}{P(x \,\,|\,\, q)} \\ \\ P(R = 0 \,\,|\,\, x, q) &= \frac{P(x \,\,|\,\, R = 0, q) \cdot P(R = 0 \,\,|\,\, q)}{P(x \,\,|\,\, q)} \\ \end{align}\]

dove,

  • \(P(x \,\,|\,\, R = 1, q)\) è la probabilità che, se un documento rilevante per la query \(q\) è stato ottenuto, allora la sua rappresentazione è data da \(x\).

  • \(P(x \,\,|\,\, R = 0, q)\) è la probabilità che, se un documento non-rilevante per la query \(q\) è stato ottenuto, allora la sua rappresentazione è data da \(x\).

  • \(P(R = 1 \,\,|\,\, q)\) è la probabilità di ottenere un documento rilevante per la query \(q\)

  • \(P(R = 0 \,\,|\,\, q)\) è la probabilità di ottenere un documento non-rilevante per la query \(q\)

L'idea quindi è quella di utilizzare delle statistiche riguardanti il documento per stimare queste probabilità. Notiamo a tale fine che dato che un termine o è rilevante oppure non lo è, ovvero abbiamo che

\[P(R = 1 \,\,|\,\, x, q) + P(R = 0 \,\,|\,\, x, q) = 1\]

Secondo il modello \(\text{BIM}\), data una query \(q\), fare il ranking dei documenti in base alla loro rilevanza equivale a fare il ranking dei documenti in base alla probabilità \(P(R = 1 \,\,|\,\, x, q)\).

Al posto di rankare in base al valore di \(P(R = 1 \,\,|\,\, x, q)\), possiamo effettuare il ranking basandoci sulla odds of relevance, definita come segue

\[O(R \,\,|\,\, x, q) := \frac{P(R = 1 \,\,|\,\, x, q)}{P(R = 0 \,\,|\,\, x, q)}\]

calcolando troviamo poi

\[\begin{split} O(R \,\,|\,\, x, q) = \frac{P(R = 1 \,\,|\,\, x, q)}{P(R = 0 \,\,|\,\, x, q)} &= \frac{\frac{P(R=1\,\,|\,\,q) \cdot P(x\,\,|\,\,R=1, q)}{P(x\,\,|\,\,q)}}{\frac{P(R=0\,\,|\,\,q) \cdot P(x\,\,|\,\,R=0, q)}{P(x\,\,|\,\,q)}} \\ &= \frac{P(R = 1 \,\,|\,\, q)}{P(R = 0 \,\,|\,\, q)} \cdot \frac{P(x \,\,|\,\, R = 1, q)}{P(x \,\,|\,\, R = 0, q)} \\ \end{split}\]

Notiamo che così facendo il calcolo è stato semplificato, in quanto non devo più andare a stimare la probabilità \(P(x \,\,|\,\, q)\).

Continuando a semplificare, notiamo che \(P(R = 1 \,\,|\,\, q) / P(R = 0 \,\,|\,\, q)\) è una quantità costante fissata la query, che quindi può essere ingorata.

Dunque, per ricapitolare quanto fatto, possiamo concentrarci sullo stimare solo la seguente quantità

\[\frac{P(x \,\,|\,\, R = 1, q)}{P(x \,\,|\,\, R = 0, q)}\]

I risultati ottenuti facendo il rank dei documenti in base a quest'ultima quantità sarà equivalente a fare il rank dei documenti in base agli odds, che a sua volta era equivalenta a fare il ranking dei documenti rispetto alla probabilità di rilevanza \(P(R = 1 \,\,|\,\, x, q)\).

A questo punto possiamo utilizzare l'ipotesi di indipendenza tra i vari termini per spezzare queste probabilità come segue

\[\frac{P(x \,\,|\,\, R = 1, q)}{P(x \,\,|\,\, R = 0, q)} = \prod\limits_{t = 1}^M { \frac{P(x_t \,\,|\,\, R = 1, q)}{P(x_t \,\,|\,\, R = 0, q)} }\]

Dato poi che i vari \(x_t\) assumono un valore booleano \(1\) o \(0\), possiamo spezzare questo prodotto in due parti

\[\prod\limits_{t = 1}^M { \frac{P(x_t \,\,|\,\, R = 1, q)}{P(x_t \,\,|\,\, R = 0, q)} } = \prod\limits_{t: x_t = 1} {\frac{P(x_t \,\,|\,\, R = 1, q)}{P(x_t \,\,|\,\, R = 0, q)}} \cdot \prod\limits_{t: x_t = 0} {\frac{P(x_t \,\,|\,\, R = 1, q)} {P(x_t \,\,|\,\, R = 0, q)}}\]

Per ogni documento e per ogni termine ho quindi quattro probabilità di interesse, che sono:

  • \(p_t := P(x_t = 1 | R = 1, q)\), che rappresenta la probabilità che il termine \(t\) appare in un documento rilevante rispetto alla query \(q\).

  • \(u_t := P(x_t = 1 | R = 0, q)\), che rappresenta la probabilità che il termine \(t\) appare in un documento non-rilevante rispetto alla query q.

  • \(1 - p_t\), che rappresenta la probabilità che il termine \(t\) non appare in un documento rilevante rispetto alla query \(q\).

  • \(1 - u_t\), che rappresenta la probabilità che il termine \(t\) non appare in un documento non rilevante rispetto alla query \(q\).

In modo schematizzato possiamo quindi rappresentare i valori di probabilità nella seguente tabella di contingenza

\[\begin{array}{c | c | c} & \textbf{rilevante} & \textbf{non rilevante}\\ \hline \textbf{presente} & p_t & u_t & \\ \textbf{assente} & 1 - p_t & 1 - u_t & \\ \end{array}\]

Procediamo adesso effettuando un'ulteriore assunzione semplificante: assumiamo in particolare che i termini che non compaiono nella query sono distribuiti in modo uniforme tra documenti rilevanti e non rilevanti. Da questa assunzione segue che dobbiamo considerare solamente i termini che compaiono nella query

\[\prod_{t: x_t = 1} {\frac{p_t}{u_t}} \cdot \prod_{t: x_t = 0} {\frac{(1 - p_t)}{(1 - u_t)}} = \prod_{t: x_t = 1, q_t = 1} {\frac{p_t}{u_t}} \cdot \prod_{t: x_t = 0, q_t = 1} {\frac{(1 - p_t)}{(1 - u_t)}}\]

Effettuando una operazione algebrica poi otteniamo

\[\prod_{t: x_t = 1, q_t = 1} {\frac{p_t}{u_t}} \cdot \prod_{t: x_t = 0, q_t = 1} {\frac{(1 - p_t)}{(1 - u_t)}} = \prod_{t: x_t = 1, q_t = 1} {\frac{p_t}{u_t} \cdot \frac{(1 - u_t)}{(1 - p_t)}} \cdot \prod_{t: q_t = 1} {\frac{(1 - p_t)}{(1 - u_t)}}\]

Notiamo che nell'ultima formula il prodotto di destra è relativo solo ai termini della query, ed è quindi costante per una fissata query e può essere ignorato. L'unico valore che dipende dal documento, ovvero l'unico valore che dobbiamo stimare, è quindi il prodotto a sinistra

\[\prod_{t: x_t = q_t = 1} \frac{p_t(1 - u_t)}{u_t(1 - p_t)}\]

Siamo quindi in grado di definire il Retrieval Status Value (RSV) rispetto al documento \(d\), che è definito come il logaritmo della grandezza appena ottenuta

\[\text{RSV}_d = \log \prod\limits_{t: x_t = q_t = 1} \frac{p_t(1 - u_t)}{u_t(1 - p_t)} = \sum\limits_{t: x_t = q_t = 1} \log{\frac{p_t(1 - u_t)}{u_t(1 - p_t)}}\]

Un modo equivalente per ottenere il valore \(\text{RSV}_d\) per un dato documento consiste nel definire l'odds ratio come il rapporto di due odds, l'odds che il termine appare se il documento è rilevante \((p_t/(1-p_t))\) e l'odds che il termine appare se il documento non è rilevante \((u_t/(1-u_t))\)

\[c_t := \log{ \frac{p_t \cdot (1 - u_t)}{u_t \cdot (1 - p_t)}}\]

Notiamo che a seconda del valore di \(c_t\) ho i seguenti casi:

  • Se \(c_t = 0\), allora il termine ha equal odds di apparire in documenti rilevanti o non-rilevanti.

  • Se \(c_t > 0\), allora il termine ha più odds di apparire in documenti rilevanti.

  • Se \(c_t < 0\), allora il termine ha meno odds di apparire in documenti rilevanti.

Definito \(c_t\) possono quindi pensare al \(\text{RSV}\) di un documento \(d\) come la somma dei \(c_t\) dei termini che compaiono nella query e nel documento

\[\text{RSV}_d = \sum_{t: x_t = q_t = 1} c_t\]

Osservazione: Da un punto di vista "operazionale", il modello \(\text{BIM}\) e il vector space model con pesatura tf-idf funzionano nello stesso modo. La differenza si trova nel valore dei pesi scelti. Questo significa che possiamo utilizzare le stesse strutture dati per i due modelli.

Notiamo che per calcolare il valore \(\text{RSV}_d\) bisogna stimare il valore di \(p_t\) e \(u_t\) per ogni termine \(t\).

Assumendo che sia in grado di distinguere il numero di documenti rilevanti e non-rilevanti rispetto ad una data query, posso stimare \(p_t\) e \(u_t\) utilizzando la seguente tabella di contingenza

\[\begin{array}{c | c | c | c} & \textbf{# of relevant docs} & \textbf{# of non-relevant docs} & \textbf{total #}\\ \hline \textbf{term present} (x_t = 1) & s & \text{df}_t - s & \text{df}_t \\ \textbf{term present} (x_t = 1) & S - s & (N - \text{df}_t) - (S - s) & N - \text{df}_t \\ \textbf{total #} & S & N - S & N \\ \end{array}\]

dove \(\text{df}_t\) è il numero di documenti che contengono il termine \(t\). Si ha infatti

\[\begin{align} p_t &= \frac{s}{S} \\ \\ u_t &= \frac{\text{df}_t - s}{N - S}\\ \end{align}\]

Così facendo però abbiamo solo spostato il problema. Adesso infatti siamo in grado di stimare \(p_t\) e \(u_t\) utilizzando i valori di \(s\) e \(S\). Nasce dunque un nuovo problema: come stimo i valori di \(s\) e \(S\)? Questa problematica verrà affrontata nella prossima lezione in cui si parla di ranking.