Metodi per il ritrovamento dell'informazione

Introduzione ai fattori contestuali e gestione dei dati

I fattori contestuali sono dei fattori che influiscono sulla scelta dell'informazione. Per esempio, se sta piovendo e il mio smartphone mi consiglia di andare al parco, allora il sistema non ha considerato il fattore contestuale della pioggia.

Dati strutturati vs. dati non strutturati

Cosa è più facile da gestire tra dati non strutturati e dati strutturati? Non c'è un vero e proprio elemento dei due che surclassa l'altro. In particolare, i dati non strutturati sono scritti in lingua parlata, quindi sono più facili da comprendere, ma dato che non hanno una struttura sono più difficili da organizzare. Viceversa, se si considera un dato strutturato, quest'ultimo sarà più facile da organizzare, ma la comprensione sarà più complessa. Inoltre, nei vari database non c'è ambiguità, mentre nei file di testo è molto probabile che sia presente.

Query-less e paradosso della ricerca

Il query-less è il futuro degli strumenti di ricerca in cui il sistema sarà in grado di prevedere la ricerca che andrò a fare. Il paradosso della ricerca si verifica quando l'utente effettua una ricerca, trova dei risultati ma non sa se quei risultati rispondono correttamente alla ricerca. Oggi abbiamo il problema di filtrare le informazioni poiché se ne trovano in grande quantità; prima il problema era proprio trovare l'informazione.

Gabbia dei filtri e clustering

La gabbia dei filtri è un concetto in cui vieni limitato all'interno di una "bolla" in cui ti viene mostrato solo quello che a te interessa. I maggiori motori di ricerca o altre piattaforme di vendita utilizzano questo sistema per fare in modo che tu rimanga quanto più tempo possibile sul loro sito web.

Dato un insieme di documenti, il clustering è il compito di trovare un buon raggruppamento dei documenti in base al loro contenuto. In sostanza, è come ordinare dei libri in una libreria in base al loro tema.

Classificazione e scale di ricerca

Dato un insieme di argomenti, esigenze di informazioni permanenti o la classificazione di altre categorie è il compito di decidere a quali classi, se del caso, appartiene ciascuno di un insieme di documenti. Le scale in cui opera un sistema di ritrovamento sono:

• Ricerca sul web: il sistema deve fornire la ricerca su miliardi di documenti archiviati su milioni di computer. Problemi distintivi sono la necessità di raccogliere documenti per l'indicizzazione, essere in grado di costruire sistemi che funzionano in modo efficiente su queste scale enormi e gestire aspetti particolari del web come lo sfruttamento dell'ipertesto e non lasciarti ingannare dai fornitori di siti che manipolano il contenuto delle pagine nel tentativo di aumentare il posizionamento nei motori di ricerca e l'importanza commerciale del web.
• Recupero delle informazioni personali: i programmi di posta elettronica di solito non solo forniscono la ricerca ma anche il filtro anti-spam (posta indesiderata) del provider di classificazione del testo e comunemente forniscono anche mezzi manuali o automatici per classificare la posta in modo che possa essere inserita direttamente in cartelle particolari.
• Nel mezzo c'è lo spazio della ricerca aziendale, istituzionale e specifica del dominio, dove il recupero potrebbe essere fornito per raccolte come documenti interni di una società, un database di genitori o articoli di ricerca in biochimica.

Gestire la conoscenza

Gestire la conoscenza significa:

• Raccogliere la conoscenza
• Organizzarla (strutturarla, classificarla)
• Distribuirla
• Renderla accessibile a chi ne ha bisogno (nel momento e nel posto in cui serve)

Tutto questo al fine di:

• Risparmiare tempo
• Migliorare la qualità dei servizi
• Ridurre i tempi di accesso all'informazione ed alla fruizione dei servizi

La conoscenza è un capitale:

• Intangibile
• Volatile
• Difficile da concretizzare e conservare

Obiettivo del corso

L'obiettivo di questo corso è vedere come si gestiscono le informazioni non strutturate o semi-strutturate (ho la suddivisione in capitoli), perché circa il 90% dei dati presenti nei database del mondo è in forma non strutturata.

Automatic knowledge management

Il nostro obiettivo è quello di costruire dei sistemi in grado di processare documenti che sono scritti in linguaggio naturale. Acquisizione/ritrovamento di conoscenza da basi di dati in forma testuale. Dal testo dobbiamo ottenere conoscenza.

Data retrieval e information retrieval

Data retrieval: Dati strutturati, su cui posso fare operazioni di ricerca perché ho uno scopo da raggiungere (es. basi di dati, ritrovamento di record in un database strutturato).

Information retrieval: Dati non strutturati (testi), su cui posso fare operazioni di ricerca perché ho uno scopo da raggiungere (es. motore di ricerca, cercare informazioni rilevanti in una sorgente di dati non strutturato).

Data mining: Dati strutturati; ricerca opportunistica, di scoperta. Io non so a priori cosa sto cercando (es. scoprire una nuova conoscenza attraverso l'analisi dei dati).

Text mining: Dati non strutturati; ricerca opportunistica, di scoperta. Io non so a priori cosa sto cercando (es. scoprire una nuova conoscenza attraverso l'analisi di un testo).

Information retrieval e filter

L'information retrieval si occupa di trovare l'informazione all'interno di un corpus di documenti, mentre l'information filter si occupa di esporre gli utenti alle sole informazioni che per loro sono rilevanti.

Recommended system

Un recommended system è un sistema in grado di consigliare all'utente dei servizi o dei prodotti in base ai suoi interessi.

Processo di knowledge discovery dai database

Il processo che devo seguire per ottenere questo tipo di conoscenza (rif. Data mining) si chiama knowledge discovery process dai database: "processo di identificazione di pattern nei dati che siano non banali, validi, sconosciuti e potenzialmente utili". Si parte dall'analisi dei dati, selezione dei dati, pre-processare i dati, infine con gli algoritmi di data mining vado ad estrarre questi pattern.

Dal data mining al text mining

Text mining = data mining applicato ai dati testuali + linguaggio naturale.

Text mining process

• Pre-processare il testo (con analisi sintattica e semantica)
• Generazione delle features (bag of words, bag è una struttura dati un insieme non ordinato)
• Selezione delle features (es, contiamo una parola in particolare, operiamo delle operazioni)
• Algoritmo di text/data mining
• Analisi dei risultati

Quindi, è un processo che mi permette di scoprire delle gemme di informazioni, prima sconosciute, che siano utili, dall'analisi di una collezione di documenti.

Information extraction

Information extraction: strutturare le informazioni che posso recuperare da dati non strutturati. Permette di organizzare, categorizzare scoprendo tendenze e apprendendo concetti.

Text mining: aree di ricerca correlate

Information Retrieval

• Text Categorization (è un modo per associare a dei documenti delle categorie. Un metodo per attuare questa tecnica è tramite l'apprendimento automatico, es. email spam o no spam)
• Information Extraction
• Natural Language Processing
• Data Mining

Information retrieval (IR) si occupa della rappresentazione, della memorizzazione, dell'organizzazione e dell'accesso ai contenuti informativi (documenti, pagine web, cataloghi, oggetti multimediali). L'information retrieval consiste nel trovare materiale (di solito documenti) di natura non strutturata (solitamente testo) che soddisfa il bisogno di informazione partendo da una grande collezione.

Primi obiettivi dell'area IR

Indicizzazione del testo e ricerca di documenti utili in una raccolta. La ricerca di pagine sul World Wide Web è l'"app killer" più recente. Interessato in primo luogo al recupero di documenti pertinenti a una query. Interessato in secondo luogo con il recupero efficiente da grandi insiemi di documenti.

Task di un sistema IR

Dato un insieme di documenti in linguaggio naturale; devo trovare un insieme di documenti ordinati per rilevanza (in base alla query, che scaturisce da un bisogno informativo). Una descrizione completa della necessità di informazioni dell'utente non è sempre una buona query da sottoporre al sistema IR. L'utente potrebbe voler prima tradurre questa esigenza di informazioni in una query. Questo processo di traduzione produce una serie di parole chiave, o termini di indice, che riassumono le informazioni necessarie all'utente. Data la query dell'utente, l'obiettivo principale del sistema IR è recuperare informazioni utili o rilevanti per l'utente. Cioè, il sistema IR deve classificare le informazioni in base a un grado di pertinenza per la query dell'utente.

Interazione con le interfacce di ricerca

Le persone interagiscono con le interfacce di ricerca in modo diverso, questo dipende da: dal tipo di task, dal dominio di expertise dell'informazione, la quantità di tempo a disposizione.

Information lookup e ricerca esplorativa

Come le persone fanno ricerche -> differenza tra information lookup e ricerca esplorativa.

• I task dell'information lookup:
• Sono simili al question answering, faccio una domanda voglio una risposta
• Possono essere soddisfatti da un discreto pezzo di informazione
• La ricerca esplorativa (exploratory search) si può dividere in due parti: task di learning e task di investigazione.
• Learning search, è una ricerca che richiede più di una sessione di ricerca.
• Task di investigazione, è una ricerca che viene effettuata in lunghi periodi di tempo con valutazione dei risultati. In questo caso viene messo in atto un processo iterativo di SENSEMAKING: cercare di dare un senso alle informazioni che ho trovato.

IR system

Abbiamo un insieme di documenti che deve "entrare" nel sistema di IR. Poi abbiamo l'utente che ha un bisogno informativo, quindi esprime una query al sistema. Il sistema di ritrovamento tira fuori i documenti pertinenti (se è un buon sistema li mostra rankati).

Rilevanza di un documento

Cosa significa dire che un documento è rilevante rispetto alla query? Rilevanza: è sufficiente dire che se un termine presente nella query è presente anche nel documento allora quel documento è rilevante? Si. La rilevanza è un giudizio soggettivo e potrebbe includere: rilevante se è sull'argomento giusto, non è datato (vecchio), soddisfa gli obiettivi dell'utente e la sua intenzione d'uso dell'informazione. Nozione leggermente meno rigida è che le parole nella query appaiono frequentemente nel documento, in qualsiasi ordine (bag of words).

Bisogna fare attenzione ai sinonimi (= termini diversi che hanno lo stesso significato) e alle parole polisemiche (= termine che ha più di un significato). Per sinonimia si intende l'associazione di uno stesso significato a più word-form (ad esempio "casa" ha lo stesso significato semantico di "abitazione"). Nel momento in cui effettuo una query contenente un termine che fa parte di un synset, il sistema non mi restituirà alcuni documenti rilevanti che contengono sinonimi della parola scritta nella query. Per questo motivo, si abbassa il richiamo, essendo il richiamo il rapporto tra i documenti rilevanti ritrovati e i documenti rilevanti nella collezione.

Per polisemia si intende l'associazione di più significati (word-meaning) alla stessa parola (word-form). Nel momento in cui effetto una query contenente una parola polisemica, il sistema IR mi fornirà anche risultati che possono contenere quella parola, ma non con il significato semantico desiderato (se ricerco la parola "pesca", intesa come frutto, il sistema mi restituirà anche documenti in cui si parla di "pesca", intesa come sport). Ovviamente tali documenti non saranno rilevanti per la query e quindi si abbassa la precisione, essendo la precisione il rapporto tra i documenti rilevanti ritrovati e i documenti ritrovati.

Intelligent IR

Tenendo conto del significato delle parole usate. Tenendo conto dell'ordine delle parole nella query. Facciamo un adattamento all'utente sulla base di feedback diretti o indiretti (feedback di pertinenza): raccoglie feedback, genera nuova query, ripetizione del recupero.

Architettura del sistema IR

Text operation servono per formare i token, non semplice. Per diminuire il numero dei token possiamo eliminare le Stop word (es articoli) e possiamo anche ridurre a lemma alcune parole (es bambina/i/e diventa bambino) o ridurre la parola alla radice (stemming) rimuovendo prefissi e suffissi.

Indicizzazione si occupa di costruire un indice invertito (invertito perché abbiamo le parole con i link ai documenti). L'operazione di ricerca prende la query e deve ritrovare i documenti che contendono i token presenti nella query. L'operazione di ricerca viene fatta con la consultazione dell'indice invertito.

Il modulo di ranking che deve assegnare un punteggio tra la query e il documento.

Natural Language Processing

Si focalizza sull'analisi sintattica, semantica e pragmatica dei testi scritti in linguaggio naturale (anche di un discorso).

IR Directions

• Metodi per determinare il senso di una parola ambigua in base al contesto (disambiguazione del senso della parola).
• Metodi per identificare le specificità delle informazioni in un documento (estrazione delle informazioni).
• Metodi per rispondere a domande specifiche di NL da corpora di documenti.

Machine Learning

Focalizzata sullo sviluppo di sistemi computazionali che migliorano le proprie prestazioni con l'esperienza. Classificazione automatizzata di esempi basata su concetti di apprendimento da esempi di formazione etichettati (apprendimento supervisionato). Metodi automatizzati per raggruppare esempi senza etichetta in gruppi significativi (apprendimento non supervisionato).

Distanza di Levenshtein

La distanza di Levenshtein è un valore intero che misura quanto due parole sono differenti tra loro.

Boolean and vector space retrieval models

Un modello di ritrovamento (retrieval model) specifica i dettagli di:

• La rappresentazione dei documenti
• La rappresentazione delle query
• La funzione di ritrovamento.

Deve definire la nozione di relevance, cioè quando un documento è rilevante rispetto alla query. La nozione di relevance può essere binaria o continua (dire se un documento è o non è rilevante; dire che un documento è rilevante al 90%). La funzione di ranking è una funzione che assegna un punteggio ai documenti che si riferiscono ad una determinata query.

Un modello IR è una quadrupla [D, Q, F, R (qi, dj)]:

• D è l'insieme delle viste logiche per i documenti
• Q è l'insieme delle query
• F è un framework di rappresentazione dei documenti e delle query
• R(qi, dj) è la funzione di ranking

Classi di modelli di ritrovamento (per i testi)

• Modello Booleano
• Vector Space Model
• Probabilistic model (che noi non facciamo).

Step comuni di pre-processing

• Eliminare caratteri/markup non necessari (tag HTML, punteggiatura)
• Dividere in token
• Riduco i token alla radice delle parole
• Problemi che si vengono a creare: perdita di contesto. Rimuovo stop-word (gli articoli)
• Rilevare fresi comuni
• Costruire un indice invertito

Boolean model

Un documento è rappresentato come un set di keywords. Le query sono espressioni booleane sulle keywords, connesse da AND, OR, NOT, con la possibilità di usare parentesi. L'output è documento rilevante o documento non rilevante, non abbiamo un match parziale tra query e documento.

Matrice di incidenza termini-documenti, i documenti sono nelle colonne e i termini nelle righe. Per risponde alla query posso utilizzare la tecnica di incidence vectors, in cui prendo i vettori delle parole: questa è la matrice iniziale.

Indice invertito

L'indice invertito è una rappresentazione più efficiente della matrice sparsa formata dalle parole sulle righe e dai documenti sulle colonne. In particolare, l'indice invertito può essere considerato come un dizionario di parole e a ogni parola è associata una lista con l'elenco di documenti in cui è presente la parola che si sta considerando. La lista dei documenti di una parola è detta posting list.

Per ogni termine t, dobbiamo stilare una lista di tutti i documenti che contengono t. Identifichiamo ogni documento con un docID, un numero seriale. Invertito: ad ogni parola vengono linkati tutti i documenti che contengono quella parola. Dizionario: insieme di tutte le parole distinte che sono contenute all'interno della mia collezione. I documenti sono conservati in una lista.

Come trovo i documenti comuni a delle parole? Con un'intersezione, per essere efficiente le liste devono essere ordinate.

Costruzione del inverted index

1. Tokeniziamo
2. Modifichiamo i token (lemmatizziamo, possiamo ordinare i token in ordine alfabetico)
3. Costruiamo l'indice

Come risolvo la query "brutus and caesar": creo la posting list delle due parole e trovo i docID in comune.

Problemi del modello booleano

• Molto rigido: AND significa tutti, quindi ci saranno pochi risultati; OR significa alcuni
• Difficoltà nel creare espressioni complesse
• Difficoltà a controllare il numero di documenti ritrovati
• Difficile classificare l'output (manca il rank)
• Difficoltà fornire un feedback sulla rilevanza

Pre-processing steps

Analisi (parsing) del documento:

• In che formato è? (pdf, word, HTML)
• In che lingua è scritto?
• Quale codifica dei caratteri è utilizzata?

Ognuno di questi è un problema di classificazione che va analizzato e risolto. Possiamo avere complicazioni dovuti al formato/linguaggio: I documenti