Skip to content

Basi di Information Retrieval

L’Information Retrieval (IR) è una materia studiata fin dagli anni ’70 ma è sono negli anni ’90, con la diffusione di internet e della web search, che è cresciuto l’interesse in questo settore.

L’IR si occupa della rappresentazione, memorizzazione e organizzazione dell’informazione non strutturata (testuale), al fine di rendere agevole all’utente il soddisfacimento dei propri bisogni informativi.

Sebbene l’IR sia nata per l’analisi di dati non strutturati, negli ultimi anni è nata la necessità di applicare tecniche di IR anche a dati semi-strutturati, in particolare a documenti XML; si parla allora allora di Structured Information Retrieval (SIR).

  • Dati strutturati: sono i dati conservati all’interno di un database, organizzati secondo schemi e tabelle. Questa è la tipologia di dati più indicata per i modelli di gestione relazionale delle informazioni.
  • Dati non strutturati: sono i dati conservati senza alcuno schema. Un esempio possono essere i file contenenti testi oppure un file multimediale come un file audio o video.
  • Dati semi-strutturati: nei dati semi strutturati si trovano alcune caratteristiche dei dati strutturati e alcune caratteristiche dei dati non strutturati. Un esempio esplicativo di questa tipologia di organizzazione di informazioni è il file compilato con sintassi XML. Nonostante non vi siano limiti strutturali all’inserimento dei dati, le informazioni vengono, comunque, organizzate secondo logiche strutturate e interoperabili.

Data una collezione di documenti e un bisogno informativo dell’utente, lo scopo di un sistema di IR è di trovare informazioni che potrebbero essere utili, o rilevanti, per l’utente. I due modelli classici di Information Retrieval sono il Modello booleano e il Modello vettoriale.

Come è possibile valutare quale di questi due sistemi di IR sia il migliore?

L’IR è nata per gestire collezioni statiche e ben conosciute: testi di legge, enciclopedie ecc., ma quando la collezione di riferimento diventa il Web con i suoi miliardi di documenti in costante aggiornamento, be, le cose cambiano completamente:

  • La collezione è dinamica, molto variabile nel tempo;
  • Le dimensioni sono enormi;
  • I documenti non sono sempre disponibili;
  • Le query degli utenti sono ancora più imprecise e vaghe.
  • Le tecniche utilizzate dai Motori di Ricerca possono quindi differire, ad esempio Pagerank (una cui variante è usata da Google) utilizza criteri diversi dalla IR standard.

Vediamo come applicare le regole di questi due modelli ad un semplice motore di ricerca (quindi non stiamo parlando di Google), al fine di identificare i documenti più rilevanti data una query di partenza.

L’IR può coinvolgere il Web, in questo caso la collezione è la parte visibile (cioè pubblica) del Web. L’obiettivo è trovare risultati di qualità e rilevanti per i bisogni dell’utente, che a loro volta possono essere:

  • Informazionali: l’utente vuole sapere qualcosa su un certo argomento (~40%); ad es.:”influenza”;
  • Navigazionali: l’utente vuole andare ad un certa pagina (~25%); ad es.:”Rianair”;
  • Transazionali: l’utente vuole eseguire una certa operazione con la mediazione del web (~35%); ad es. accedere ad un servizio (“Previsioni meteorologiche Milano”), scaricare degli oggetti (“Immagini Marte”), effettuare un acquisto (“Samsung S5”);
  • Misti: ad es. cercare un buon punto di partenza per ricerche su un certo argomento (“Bed and Breakfast Milano”)

  • Dati distribuiti: i documenti sono sparsi su milioni di server differenti
  • Dati Volatili e variabili: molti documenti appaiono e spariscono (dead links), o sono semplicemente modificati con frequenza non nota.
  • Enormi volumi di dati: miliardi di documenti diversi
  • Dati non strutturati e ridondanti: non esiste una struttura uniforme, ci sono errori html, circa30% di documenti duplicati.
  • Qualità dei dati: non ci sono controlli editoriali, le informazioni possono essere false, possono esserci errori, testi mal scritti..
  • Dati eterogenei: multimediali (immagini, video, suoni..) diversi linguaggi, diversi formati (pdf, ps..)

Inoltre le query poste sono scarsamente definite:

  • Corte (in media 2.54 termini/query);
  • Imprecise (errori ortografici);
  • Con una sintassi povera (80% delle query senza operatori).
  • Scarsa disponibilità a”perdere tempo” nel cercare la risposta più valida:
  • l’85% degli utenti cercano solo nella prima pagina dei risultati;
  • il 75% delle query non vengono raffinate dopo il risultato iniziale

Questi sono i problemi che un motore di ricerca deve affrontare ad ogni richiesta, ma partiamo dalle basi. Prima di poter mostrare dei risultati di ricerca il motore deve aver immagazzinato ed ordinato le informazioni, per questo scopo in informatica (e letteratura) si usano gli indici.

Indicizzazione full-text: inverted indexes

Nei sistemi relazionali, ovvero modelli per la gestione dei dati, gli indici permettono di recuperare efficientemente da una relazione i record contenenti uno o più valori di interesse. Analogamente, possiamo utilizzare indici per recuperare efficientemente documenti testuali di interesse. In questo caso, le interrogazioni che vogliamo supportare sono del tipo:

  • Restituire i documenti che contengono l’insieme di parole k1, …, kN.
  • Restituire i documenti che contengono la sequenza di parole k1, …, kN.

Indici che supportano queste operazioni si chiamano indici invertiti, in quanto invece di rappresentare tutte le parole presenti in documento (indici) rappresentano tutti i documenti in cui appare una specifica parola. In pratica ad ogni termine del vocabolario viene associata una lista di documenti, ordinati per rilevanza. Ecco un esempio di indice invertito:

indice-invertito

La costruzione dell’inverted index è più complessa, come visto infatti, gli indici invertiti lavorano su “termini”, ma cos’è un termine? Anche in questo caso un motore di ricerca deve fare attenzione a termini e casi particolari:

  • Principi → Prìncipi? Princìpi?
  • Emilia Romagna → un termine o due?
  • Semi-strutturati → Semistrutturati? Semi-strutturati? Semi e Strutturati?
  • La, e, and, or, 192.168.0.1, 25/12/2014… → vanno indicizzati?
  • Moto e Motocicletta → lo stesso termine o due termini diversi?
  • Sono, Siamo, E’ → lo stesso termine o tre termini diversi?

Prima della fase di costruzione dell’indice, si devono quindi trasformare i documenti della collezione in un elenco di termini.

Processo di indicizzazione

indicizzazione

La prima fase è quella di tokenizzazione, in cui il tokenizer trasforma uno stream di testo (“Amici, Toscani, Contadino”) in un elenco di token (“Amici”, “Toscani”, “Contandino”) candidati a diventare entry dell’indice. Durante la tokenizzazione vengono applicate alcune trasformazioni:

  • Eliminazione delle parole contenenti cifre;
  • Divisione in più parole dove è presente un trattino (de-hyphenation);
  • Trasformazione delle maiuscole in minuscole;
  • Eliminazione della punteggiatura.

Ma è necessario gestire alcune eccezioni:

  • Trattini che sono parti integranti di unaparola (es.B-49);
  • Parole che se scritte in maiuscolo assumono un diverso significato (es.MIT vs la parola tedesca mit);
  • Punteggiatura che è parte integrante di unaparola (es.510D.C.).

Successivamente, entrano in azione i moduli linguistici, il cui scopo è prendere i token e validarli, operazione che dipende dalla lingua utilizzata (anche se alcuni criteri sono generali). Le operazioni effettuate da i moduli sono:

  • Eliminazione delle stopword
  • Stemming
  • Thesauri
  • Lemmatization

Eliminazione delle stopwords: alcune parole sono più importanti di altre per comprendere il contenuto di un documento. Le parole che non hanno un significato proprio e sono eliminate sono le stopwords: articoli, congiunzioni, particelle pronominali, verbi frequenti ecc. Eliminare le stop words attenua il rumore che disturba la ricerca di informazioni e riduce la dimensione dell’indice.

Lo stemming riduce i termini alla loro “radice”, rimuovendo prefissi e suffissi, ad esempio:

  • automate, automatic, automation→ automat;
  • for example compressed and compression are both accepted as equivalent to compress” → “for example compres and compres are both accept as equival to compres“.

Esistono vari algoritmi di stemming; il più comune per l’inglese è l’algoritmo di Porter, che opera trasformazioni come:

  • sses→ss(witnesses→witness);
  • s→Ø(cars→car);
  • tional→tion(national→nation).

Con i thesauri si gestiscono i sinonimi tramite classi di equivalenza predefinite, ad esempio car=automobile. Due possibili tecniche:

  • Espansione dell’indice: se un documento contiene car, lo inseriamo nei posting sia di car che di automobile;
  • Espansione della query: se una query contiene car, cerchiamo anche i documenti contenenti automobile (preferibile).
  • L’utilizzo delle classi di equivalenza può però portare a risultati scorretti; ad es. puma e jaguar sono sinonimi, ma rischio di trovare informazioni relative alle automobili piuttosto che all’animale…

La lemmatization riduce una parola alla sua radice grammaticale, ad esempio:

  • am, are, is → be;
  • car, cars, car’s, cars’ → car;
  • the boy’s cars are different colors → the boy car be different color.

Come visto, i moduli linguistici sono dipendenti dal linguaggio usato nel testo. Possono crearsi problemi se il testo contiene parole scritte in diversi linguaggi. Alcuni linguaggi creano inoltre problemi aggiuntivi: pensiamo al giapponese, cinese, arabo etc.

I moduli linguistici portano dei benefici in termini di precisione della ricerca e dimensione dell’indice. Ma trasformare il testo può rendere più difficile la ricerca all’utente: pensiamo alla ricerca “to be or not to be”. Per questo motivo non tutti sono concordi sull’opportunità di usarli (molti Web Search Engine non lo fanno).

Modelli per IR

Formalmente un modello di Information Retrieval è una quadrupla (D, Q, F, R), dove:

  • D è un insieme di viste logiche dei documenti della collezione;
  • Q è un insieme di viste logiche (dette query) dei bisogni informativi dell’utente;
  • F è un sistema per modellare documenti, query e le relazioni tra loro;
  • R(qi, dj) è una funzione di ranking che associa un numero reale non negativo ad una query qj e un documento dj, definendo un ordinamento tra i documenti con riferimento alla query qj.

I due modelli classici di Information Retrieval sono il Modello booleano e quello vettoriale.

Il modello booleano ed i suoi limiti

Il modello booleano è il modello più semplice; si basa sulla teoria degli insiemi e l’algebra booleana. Storicamente, è stato il primo ed il più utilizzato per decenni.

I documenti vengono rappresentati come insiemi definiti di termini. Le query vengono specificate come espressioni booleane, cioè come un elenco di termini connessi dagli operatori booleani AND, OR e NOT. La strategia di ricerca è basata su un criterio di decisione binario, senza alcuna nozione di grado di rilevanza: un documento è considerato rilevante oppure non rilevante.

Nel modello booleano, un documento soddisfa le condizioni di ricerca oppure no, non ci sono vie di mezzo o scale di grado.

Il risultati di una espressione boleana sono detti pesi binari: wkj ∈{0,1}. Questo modello può essere ragionevole solo per degli utenti esperti che conoscano perfettamente la collezione di documenti e le proprie necessità.

Una query può restituire migliaia di risultati, ma la maggior parte degli utenti non vuole scorrere migliaia di voci. Inoltre una eventuale riformulazione della query provoca il ricalcolo dell’intero risultato, con evidenti problemi prestazionali lato hardware.

Per questa serie di motivi, il modello booleano di fatto non viene utilizzato, preferendo invece il modello vettoriale.

Il modello vettoriale

Il modello vettoriale è giustificato dall’osservazione che assegnare un giudizio binario ai documenti (1=rilevante, 0=non rilevante) è troppo limitativo. Nel modello vettoriale ad ogni termine nei documenti o nelle query viene assegnato un peso (un numero reale positivo). I documenti e le query sono rappresentati come vettori in uno spazio n-dimensionale (n = # di termini indicizzati).

Rappresentazione di documenti tramite vettori

Come già visto, l’appartenenza di una parola ad un certo documento può essere valutata rappresentando il documento come un vettore {0,1}M, dove M è la dimensione del dizionario.

rappresentazione-vettoriale-documento

Misura della sovrapposizione

Allo stesso modo, anche una query può essere rappresentata tramite un vettore {0,1}M. Lo score di un documento può essere quindi misurato come la sovrapposizione tra i due vettori.

Ad esempio, relativamente alla query “idi di marzo”:

  • il documento “Giulio Cesare” avrà uno score pari a 3 (poichè contiene tutte e tre le parole contenute nella query);
  • Qualche documento avrà uno score pari a 2 (poichè contiene le parole “di” e “marzo”);
  • Tutti gli altri documenti avranno uno score pari a 1 (poichè contengono la parola “di”). Problemi della misura della sovrapposizione
  • La misura della sovrapposizione non può essere considerata soddisfacente, poiché non considera:
  • Quante volte un documento contiene un certo termine;
  • Quanti documenti contengono un certo termine (ad es. “di” è molto più comune di “idi”);
  • La lunghezza dei documenti e delle query (quindi gli score non sono normalizzati).

Documenti come vettori di interi

Il primo problema può essere risolto rappresentando i documenti come vettori di interi, invece che di booleani: – T[i,j] = w se il documento dj contiene il termine ti w volte.

rappresentazione-vettori-interi

Frequenza dei termini

Non abbiamo ancora risolto il problema dei termini più comuni: se calcoliamo lo score sommando il numero di occorrenze di ogni parola all’interno di un documento, probabilmente lo score più alto sarà quello del documento che contiene più volte il termine “di”.

Inoltre i documenti più lunghi sono favoriti, perché hanno maggiori possibilità di contenere i termini della query (e di contenerli più volte).

La situazione migliora utilizzando come misura, invece del conteggio dei termini, la frequenza dei termini – tft,d (term frequency) = numero di occurrenze di t in d diviso per il numero totale di parole in d.

Calcolo del matching

Rappresentiamo la collezione di documenti e la query di ricerca tramite dei vettori ℕM. Esprimiamo il matching tra un documento e la query come il prodotto scalare dei relativi vettori: – q * d = Σ(i) tf(i,q) * tf(i,d)

Al posto di tf è spesso utilizzata un’altra misura, chiamata weighted term frequency (wf), che tiene conto del fatto che, sebbene l’importanza di un documento cresca col numero di occorrenze di un certo termine, tale crescita non è (probabilmente) direttamente proporzionale: – wf(t,d) = tf(t,d) > 0 ? 1 + log tf(t,d) : 0

Ma come risolvere il problema dei termini comuni?

Ogni documento può essere visto come un vettore di valori in uno spazio vettoriale (n-dimensionale), i cui assi sono i termini, contenente i documenti. Le query possono essere viste come dei brevi documenti, e quindi anch’esse sono dei vettori appartenenti a questo spazio, esempio:

rappresentazione-vettoriale-documenti

Per esprimere il concetto di similitudine fra documenti e la query, quindi per rispondere ad una query, si introduce una metrica, ossia una distanza fra vettori, che banalmente potrebbe essere quella degli spazi lineari, ossia il coseno dell’angolo fra i vettori, che di fatto viene calcolato usando le coordinate. I documenti saranno poi ordinati (ranking) in base alla minore distanza dalla query

La ricerca quindi viene svolta calcolando il grado di similarità tra il vettore che rappresenta la query e i vettori che rappresentano ogni singolo documento: i documenti con più alto grado di similarità con la query hanno più probabilità di essere rilevanti per l’utente.

Il grado di similarità viene quantificato utilizzando una qualche misura, ad esempio il coseno dell’angolo tra i due vettori (che esprime la “vicinanza” fra i vettori).

similarita-documenti

Similarità cosenica

Esprimiamo la distanza tra i vettori d1 e d2 tramite il coseno dell’angolo tra loro. Per tenere conto della lunghezza dei documenti ed evitare che i documenti più lunghi ottengano un peso maggiore, normalizziamo il risultato dividendo per la lunghezza dei vettori.

similarita-cosenica

Proprietà auspicabili della nozione di prossimità

  1. Se d1 è vicino a d2, allora d2 è vicino a d1 (commutatività).
  2. Se d1 è vicino a d2 e d2 è vicino a d3, allora d1 è vicino a d3 (transitività).
  3. Nessun documento è più vicino a d1 di d1 stesso.

Calcolo efficiente del ranking

Riepilogando, per rispondere ad una query utilizzando il modello vettoriale dobbiamo trovare i k documenti appartenenti alla collezione che sono più “vicini” alla query, cioè dobbiamo trovare i k valori più alti del coseno tra i vettori della query e del documento.

Vogliamo rendere tale operazione efficiente, cioè vogliamo:

  • Calcolare efficientemente un singolo coseno;
  • Scegliere efficientemente i k valori più alti del coseno: riusciamo a farlo senza calcolare tutti gli N valori?

Calcolo efficiente di un singolo coseno

Per ogni termine, memorizziamo nel dizionario il Document Frequency. Per ogni termine in ogni documento, memorizziamo nei posting il Term Frequency (in realtà di solito si memorizza la semplice frequenza).

  • abacus 8 –> 1,2 7,3 83,1 87,2 …
  • aargh 2 –> 1,1 5,1 13,1 17,1 …
  • acacia 35 –> 7,1 8,2 40,1 97,3 …

Ciò comporta uno spreco di spazio; si possono utilizzare le tecniche di compressione già viste.

ordinamento-risultatiScelta efficiente dei k valori di coseno più alti

Il metodo più semplice è ordinare i valori e successivamente prendere i primi k. In realtà non è necessario ordinare completamente gli N risultati; possiamo scegliere i k valori più alti costruendo un albero binario avente la proprietà che il valore di ogni nodo è maggiore dei valori dei nodi figli.

Costo: 2N (costruzione dell’albero) + 2klogN (scelta dei migliori k); per N = 1M e k = 100: ~ 10% del costo dell’ordinamento.

Diminuzione del numero di candidati

Il collo di bottiglia del processo è però il calcolo del coseno per gli N documenti. Possiamo accelerare questa fase evitando di calcolare il coseno per quei documenti che sicuramente avranno un valore uguale a zero, cioè quei documenti che non contengono alcuna delle parole richieste nella query. Dobbiamo cioè calcolare il valore del coseno solo per i documenti appartenenti all’unione dei posting dei termini contenuti nella query.

Possiamo ulteriormente migliorare le prestazioni riducendo il calcolo del coseno solo ai documenti contenenti almeno una parola “rara” (cioè con un alto valore di idf). Un’altra tecnica si basa sul calcolo a priori degli m documenti più simili per ognuno degli M termini indicizzati, scegliendo m > k. In pratica si “simulano” M query composte da un solo termine, ottenendo così una “lista dei preferiti” per ogni termine.

Quando si deve eseguire una query di lunghezza t, si procede come segue:

  • Calcoliamo l’insieme S dato dall’unione delle t “liste dei preferiti”, |S| < mt;
  • Calcoliamo il coseno solo per i documenti contenuti in S e scegliamo i migliori k.

Un’altra tecnica: cluster pruning

Fase di pre-processing:

  • Scelta casuale di √N documenti, chiamati leader;
  • Per ognuno degli altri documenti, calcoliamo il leader più simile;
  • I documenti associati ad un leader vengono chiamati follower; mediamente avremo √N follower per ogni leader.

Esecuzione di una query:

  • Calcolo del leader più simile;
  • Scelta dei k documenti da mostrare tra i follower del leader scelto.

I problemi principali di questo approccio sono:

  • Olio appare due volte nel primo documento, il che può indicare una maggiore importanza della parola.
  • Perdere appare in tutti i documenti, per cui non serve a discriminare tra più o meno rilevanti.

Invece di segnalare la presenza o meno di un termine in un documento, vogliamo dunque assegnarvi un peso. Un approccio tipico consiste nell’utilizzare pesi ottenuti dal prodotto tra la term frequency (tf, ovvero, quante volte o in che percentuale un termine appare nel documento) e l’inverse document frequency (idf, ovvero, quanto è rara l’occorrenza di un termine).

Document Frequency e misura tf / idf

Avevo già parlato del fattore TF-IDF in questo articolo. Per Document Frequency si intende il numero di documenti che contengono un certo termine.

L’inverso del Document Frequency (Inverse Document Frequency, idf), cioè la rarità di un termine all’interno della collezione, è una buona misura della significatività di un termine.

Solitamente viene usata la seguente formula: idfi = 1 / log (N / dfi) dove: – N = numero totale di documenti della collezione; – dfi = numero di documenti che contengono il termine i. • Ad ogni termine della query viene assegnato un peso in base ad una misura combinata di tf e idf (tf / idf): wi,d = tfi,d x log (N / dfi)

Problemi dell‟approccio vettoriale:

  • La lunghezza dei documenti incide sul calcolo
    della rilevanza.
  • Il numero di documenti incide sul calcolo della rilevanza.
  • Non viene considerato l‟ordine dei termini.

Collezione come spazio vettoriale

Ogni documento può essere quindi visto come un vettore di valori tf / idf (o wf / idf). Di conseguenza, l’intera collezione può essere vista come uno spazio vettoriale, i cui assi sono i termini, contenente i documenti. Le query possono essere viste come dei brevi documenti, e quindi anch’esse sono dei vettori appartenenti a questo spazio.

Abbiamo quindi bisogno di una nozione di prossimità tra vettori, sulla quale basarci per assegnare uno score ad ogni documento. Tale nozione di prossimità ci permetterebbe anche, dato un documento, di trovare altri documenti “simili”: documenti che sono “vicini” nello spazio vettoriale parlano “più o meno” della stessa cosa.

Valutazione IR

Un sistema tradizionale di Data Retrieval può essere valutato utilizzando svariate misure:

  • Velocità di indicizzazione (numero di documenti indicizzati all’ora);
  • Velocità di ricerca (in funzione della dimensione dell’indice);
  • Espressività del linguaggio di interrogazione.

Tutte queste proprietà (performance evaluation) sono misurabili. Ma la vera e più importante misura delle prestazioni di un motore di IR è un’altra: la soddisfazione dell’utente (retrieval performance evaluation), visto il meccanismo ranking based. Come misurare la soddisfazione di un utente?La velocità di ricerca è sicuramente un fattore importante, ma una risposta velocissima ma inutile non renderà felice l’utente!

Misurare il grado di soddisfazione di un utente tuttavia non è cosa facile, la scelta più valida infatti dipende dal tipo di utente e di applicazione:

  • Motore di ricerca: se un utente è soddisfatto delle prestazioni di un motore di ricerca tornerà ad utilizzarlo, quindi potremmo misurare la percentuale di utenti che “tornano”;
  • Sito eCommerce: dal punto di vista dell’utilizzatore del sito, il motore è valido se il tempo necessario per effettuare un acquisto è basso; dal punto di vista del proprietario del sito, il motore è buono se un’alta percentuale di ricerche si concludono con un acquisto;
  • Azienda: una valida misura può essere il tempo risparmiato dai dipendenti nella ricerca di informazioni

In generale allora il modo migliore per valutare un motore di IR è considerare la rilevanza dei risultati. Occorre definire una metodologia ed abbiamo bisogno di una serie di strumenti:

  • Una collezione di documenti di test; esistono diverse collezioni, tra cui ricordiamo lacollezione TREC, sviluppata da NIST (National Institute of Standards and Technology): circa 700 K documenti, dimensione 2GB
  • Un elenco di esempi di richieste di informazioni (query), solitamente definite informalmente, in linguaggio naturale (si parla perciò più precisamente di retrieval task), e da esperti del settore
  • Una valutazione di rilevanza, cioè un giudizio rilevante/non rilevante per ogni coppia query/documento, definita da esperti del settore

Data una strategia di IR, la misura della valutazione quantifica la similarità tra l’insieme dei documenti ritornati e l’insieme dei documenti classificati come rilevanti. La metodologia di valutazione più utilizzata si basa su due misure:

  • Precision: percentuale di documenti ritornati (in risposta ad una query) che sono rilevanti;
  • Recall: percentuale di documenti rilevanti che sono ritornati
precision-recall

In conclusione, l’utilizzo di Precision e Recall per la valutazione di un motore di IR pone alcuni problemi:

  • I documenti della collezione devono essere valutati manualmente da persone esperte: non sempre il giudizio è completamente veritiero;
  • La valutazione dei documenti è binaria (rilevante / non rilevante): non sempre è facile catalogare così nettamente un documento;
  • Le misure sono pesantemente influenzate dal dominio di applicazione, cioè dalla collezione e dalle query: un motore di IR potrebbe avere delle ottime prestazioni in un determinato dominio ma non in un’altro.

IR avanzata

Per incrementare l’efficiacia dell‟IR, diverse
tecniche sono utilizzate:

  • Ranking probabilistico
  • Latent Semantic Indexing
  • Relevance FeedBack e Query Expansion

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|documento i, query)

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. In base al teorema di Bayes:

Il teorema di Bayes si usa quando un evento B può verificarsi sotto diverse condizioni sulle quali si possono faren ipotesi. Se si conosce la probabilità delle ipotesi nonché le probabilità condizionate, si potrà verificare se le ipotesi iniziali erano corrette o se devono essere modificate.

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.

Come si calcolano le probabilità condizionate?

  • Si usano “stimatori”
  • Il modello più semplice è il Binary Independence Retrieval (BIR)
  • Alternativamente, sono usate le Reti Bayesiane

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, 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

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

Latent Semantic Indexing

I metodi di ranking tradizionali calcolano l’attinenza di un documento ad una query sulla base della presenza o meno di parole contenute nella query: un termine o è presente o non lo è. Nella LSI (di cui avevo parlato in questo articolo) la ricerca avviene per concetti: ma un concetto non è l’astrazione-generalizzazione di un termine (es: golf –> vestiario) ma un insieme di termini correlati (golf, maglia, vestito) detti co-occorrenze o dominio semantico.

Data una collezione di documenti, LSI è in grado di rilevare che alcune n-uple di termini co-occorrono frequentemente (es: gerarchia, ordinamento e classificazione). Se viene fatta una ricerca con gerarchia, ordinamento vengono “automaticamente” recuperati documenti che contengono anche (e eventualmente solo!) classificazione.

Relevance Feedback

Il Relevance Feedback e Query Expansion sono tecniche per migliorare il recall di una query. Nel Relevance Feedback l’idea è che dopo la presentazione di un set iniziale di documenti, si chiede all’utente di selezionare i più rilevanti, usando questo feedback per riformulare la query, nuovamente quindi si presentano nuovi risultati all’utente, eventualmente, iterando il processo.

Nella Query expansion, si aggiungono termini oltre quelli iniziali, con l’obiettivo di migliorare la qualità della ricerca. Come tener conto del feedback?

  • Query Expansion: aggiunge alla query nuovi termini estratti dai documenti prescelti dall’utente
  • Term Reweighting: aumenta il peso dei termini che compaiono nei documenti rilevanti e diminuisce il peso di quelli che non vi compaiono

Il feedback esplicito non è molto usato: gli utenti sono a volte riluttanti ed è più difficile capire perché un documento sia stato selezionato (l’utente può rendersi conto di aver mal formulato la query e le sue selezioni appaiono inconsistenti con i primi risultati proposti). Per questo motivo si introduce il Pseudo Feedback:

  • non chiedere esplicito aiuto all’utente.
  • Assumi che i primi m top-ranked siano i più interessanti.
  • Espandi la query includendo termini correlati con i termini della query, usando gli m top-ranked.
  • Il metodo si è dimostrato efficace

Query Expansion

La Query expansion incrementa i termini utilizzati nella query, e a tale scopo può attingere da un glossario (thesaurus), che fornisce informazioni di sinonimia e correlazione fra termini (ad esempio WordNet) oppure utilizzare le co-occorrenze. Ma Iponimi e sinonimi migliorano la Ricerca? In generale:

  • NO se i termini della ricerca sono pochi e poco specifici (ambiguità genera rumore)
  • SI se i termini non sono ambigui (domini tecnici)
  • NI se si applicano algoritmi di word sense disambiguation: SI per query lunghe (molto “contesto” migliora WSD) NO per query corte e generiche (poca precisione nella disambiguazione)

Usando un thesaurus, per ogni termine t, in una query, si espande la query con sinonimi e termini correlati nel thesaurus. In genere i pesi dei termini aggiunti sono più bassi. Questo metodo aumenta la recall ma diminuisce la precisione, per via dell‟ambiguità semantica (aggiungere sinonimi con AND in Google quindi in genere peggiora, un pò meglio se si espande con OR)

Nel caso delle co-occorrenze, si determina anzitutto la similarità fra termini usando delle statistiche pre-calcolate sull’intera collezione di documenti (global analysis). Si calcolano matrici associative (matrici di co-occorrenze) che quantificano la correlazione fra termini. Si espande infine la query con i termini più simili.

Poiché i termini sono in ogni caso altamente correlati, l’espansione potrebbe non aggiungere molti nuovi documenti! Se L’analisi dei termini correlati non è basata sull’intera collezione, ma solo sui documenti “localmente” recuperati sulla base della query iniziale, si parla di local analysis. Questo riduce il problema della ambiguità semantica, perché i documenti, essendo recuperati solo localmente, molto probabilmente contengono ogni termine nel senso corretto per l’utente. L’analisi globale richiede di fare dei calcoli una volta per tutte, l’analisi locale va fatta in tempo reale sulla base di ogni query ma fornisce risultati migliori.

Google query expansion opera con:

  • Word stemming: translator -> translator, translation
  • Acronimi: NATO -> North Atlantic Treaty Organization (pericoloso… Northern Arts Tactical Offensive)
  • Errori di digitazione: wigets ->widgets
  • Sinonimi: solo se appare evidente che la parola è usata in modo improprio (information lost ->loss)
  • Traduzione (organizzazione mondiale sanità -> world health organization)
  • Related Search (migliorata dal 2009 dopo l‟accordo con Orion)
query-expansion


Conclusioni

Abbiamo visto come, attraverso l’Information Retrieval, i primi motori di ricerca raccoglievano e mostravano le informazioni agli utenti e come negli anni successivi gli algoritmi sono diventati sempre più intelligenti, precisi ed affidabili.

Lo scopo di questa importante area dell’informatica è infatti quello di soddisfare il bisogno di informazioni dell’utente, in altre parole, fornire a quest’ultimo tutti i documenti e le informazioni rilevanti per quella che è stata la richiesta effettuata.

Queste leggi matematiche venivano usate in passato e da esse si sono sviluppate nuove formule e algoritmi che regolano oggi i più famosi motori di ricerca.

Perchè ne ho parlato se non sono nozioni attuali? Perchè penso che, per chi svolge il mio lavoro, sia molto importante capire le logiche che regolano un motore di ricerca. Soltanto comprendendo le basi si possono capire le evoluzioni ed i futuri sviluppi di questa importante materia.

Se non sai da dove arrivi difficilmente capirai dove stai andando!

Fonti:

Articoli correlati

Autore

Commenti |3

Lascia un commento Lascia un commento
  1. Daniele 1 commento

    Questa risorsa è una bomba! Complimenti veramente!

    1. Giovanni Sacheli 754 risposte

      Ciao Daniele, grazie mille per il commento!

  2. Massimo Liani 1 commento

    Molto interessante, mi sembrava di seguire un corso all’università.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Ultimi articoli aggiornati

Richiedi un preventivo SEO e Google Ads

Porta il tuo sito web al livello successivo con l’expertise di EVE Milano. La nostra agenzia di Search Marketing ha ricevuto oltre 1123 richieste di preventivo, un segnale chiaro della fiducia che imprenditori e manager, come te, ripongono nella nostra specializzazione tecnica e verticale nella SEO e PPC. Se la tua organizzazione cerca competenze specifiche per emergere nei risultati di Google, noi siamo pronti a fornire quel valore aggiunto. Affidati alla nostra esperienza per fare la differenza.
Richiedi un preventivo

Non perderti altre guide, iscriviti per ricevere un avviso mensile con gli aggiornamenti del blog!

Iscriviti alla newsletter!

Informativa sui cookies

Noi e terze parti selezionate utilizziamo cookie o tecnologie simili per finalità tecniche e, con il tuo consenso, anche per le finalità di esperienza e misurazione come specificato nella cookie policy. Puoi liberamente prestare, rifiutare o revocare il tuo consenso, in qualsiasi momento, accedendo al pannello delle preferenze. Il rifiuto del consenso può rendere non disponibili le relative funzioni. Usa il pulsante “Accetta” per acconsentire. Usa il pulsante “Rifiuta” per continuare senza accettare.