Automatic Text Processing
Ing. Leonardo Rigutini
Dipartimento di Ingegneria dell’Informazione
Università di Siena
Via Roma 53
53100 – SIENA – ITALY
[email protected]
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Outlines
L’era dell’informazione
Information Retrieval
I documenti di testo
Rappresentazione del testo:
Vettori di feature
Rappresentazione Bag-OF-Word
Importanza di un termine
Misura di similarità
Normalizzazione del testo:
Tokenization
Conversion to lower case
Lemming
Stop-Word
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
L’ era dell’ informazione
Documento inteso come contenitore di informazione di qualunque tipo
Varie forme di informazione: Testo, Radio, Televisione, INTERNET
Vari tipi di documenti: Testo, Audio, Immagini e Video, Tutti
Incredibile il numero di documenti esistenti oggi:
Nel 2000 si stima la dimensione del web in più di 1 BILIONE di pagine
I motori di ricerca classici (Google, AltaVista, Yahoo) indicizzano
centinaia di milioni di documenti
Gli archivi delle aziende raggiungono milioni di documenti
Moltissime anche le pubblicazioni memorizzate nei database dei
search-engine specializzati (citeseer, cora, IEEE, ecc…)
Newsgroup, forum, le e-mail …
Archivi fotografici
Ecc..
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Information Retrieval
Necessità di organizzare questa informazione
Aziende:
– documenti relativi all’azienda, regolamento interno, bollettini interni,
comunicazioni varie, workflow, ecc..
Enti pubblici:
– Regolamenti, modulistica, notizie, bandi ecc..
WEB:
– Qualunque informazione
Altro…
Necessità di studiare tecniche per un recupero “intelligente”
dell’informazione:
IR (Information Retrieval)
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Information Retrieval
Disciplina che studia tecniche per il recupero dell’informazione
Es. Motori di ricerca
Scopo:
Recupero dei documenti “giusti” durante la ricerca da parte dell’utente
Misure per l’ IR:
RECALL:
n° relevant items retrieved
n° relevant items in collection
PRECISION: n° relevant items retrieved
total n° items retrieved
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Information Retrieval
Misurare la similarità tra due o più documenti in modo da restituire
all’utente i documenti più significativi:
Trovare una rappresentazione adeguata dei documenti
Definire una metrica (distanza) per tale rappresentazione
La macchina determina la similarità tra la query e tutti i documenti
nel database, restituendo i documenti con punteggio più elevato.
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Documenti di testo
La maggioranza di documenti presenti sulla rete sono
documenti di testo
La maggioranza delle tecniche di classificazione e di recupero
dell’informazione sono relative al testo
La maggioranza delle ricerche effettuate sul web riguarda
documenti di testo
Le ultime due affermazioni sono strettamente correlate:
Ad oggi pochi sono i motori per immagini che funzionano, quasi nessuno
per i video o audio, ciò spiega perché l’utente si muove su documenti di testo
Inoltre molte ricerche multimediali si risolvono in ricerche testuali in appositi
campi
– un video viene etichettato con un insieme di keyword e la sua ricerca
avviene per tali parole
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Text-IR
Text Information Retrival raccoglie:
Text Retrieval:
– Data una query, recuperare i documenti più attinenti
Text Segmentation:
– Dato un documento, suddividerlo in sub-topic
Text Classification:
– Determinare la classe del documento tra un insieme di classi prestabilito
Document Clustering:
– Dato un database documentale, determinare l’insieme delle
classi e gli abbinamenti classe-doumento
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Rappresentazione del testo
Documento di testo:
Sequenza (flusso) di parole contenente uno o più topic
(argomenti, concetti ecc..)
Feature:
Parole
Punteggiatura
Stile del testo (Grassetto, Corsivo, ecc…)
Struttura del testo (Titolo, paragarafo, nota ecc…)
Bi-grammi o tri-grammi
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Vettori - 1
Un punto in uno spazio può essere rappresentato come un insieme
di valori, ognuno dei quali si riferisce ad una dimensione dello spazio
stesso
Es.
P (x1,x2)
x2
2-D :
P = ( x1 , x2 )
x1
x3
3-D :
P = ( x1 , x2 , x3 )
P (x1,x2,x3)
x1
x2
Formalmente:
Un vettore è una n-pla di valori dove n è la dimensione
dello spazio
P = ( x1 , x2 , … , xn )
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Vettori - 2
Rappresentazione alternativa di un vettore in R2:
Modulo: misura del vettore
Angolo: angolo che il vettore forma con le ascisse
x2
N.B. sempre due dimensioni (cambia la base)
P (x1,x2)
P
α
x1
Operazioni:
Modulo:
– Per calcolare il modulo si utilizza il teorema di pitagora:
– E si indica con P
Prodotto scalare
–  A, B   a · b  a · b
1
1
2
2
– Il prodotto scalare tra A e B si indica con < A,B> o A•B
P  (x 1 ) 2  (x 2 ) 2
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Vettore differenza
Dati due punti (vettori) è possibile calcolare il vettore differenza:
a2
A (a1,a2)
b2
B (b1,b2)
a1
b1
Quanto vale A-B ?
A-B= C (a1-b1 , a2-b2 )
C (a1-b1 , a2-b2)
a2-b2
a1-b1
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Distanza - 1
Possiamo definire due tipi di distanze:
Distanza euclidea :
– modulo del vettore differenza A  B  (a 1  b1 ) 2  (a 2  b 2 ) 2
Distanza del coseno:
 A, B 
– Angolo formato dai due vettori: cos  
AB
– Se due vettori hanno “pendenze” vicine allora l’angolo che essi
formano è piccolo ed il coseno tende ad 1
A (a1,a2)
a2
b2
B (b1,b2)
α
a1
b1
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Distanza - 2
La seconda formula è 0 quando α = 90°
In tale situazione infatti il prodotto scalare è 0
Ed i due vettori si dicono ortogonali
a2
A (0,a2)
α =90°
B (b1,0)
b1
Infatti: < A ,B > = 0·b1 + a2·0 = 0
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Vector Space Model
Un documento è visto come un punto (vettore) nello spazio delle parole
del dizionario (feature):
Di = ( wi,1, wi,2 , wi,3 , … , wi,n)
Ogni termine wi,k è il peso della parola k nel documento i:
1. wi ,k  1 se il termine k appare nel documento i
0 altrimenti
2. w  n numero di volte che il termine k appare nel documento i
i ,k
i
3. tf.tdf: wi ,k 
frequenza del termine k nel documento i
frequenza del termine k nell' intera collezione
4. …altri
Tale rappresentazione è detta comunemente Bag-of-Word
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Es. BOW (Bag-of-Word)
Supponiamo di avere due documenti:
D1 = “ingredienti pizza: farina, acqua, lievito, olio”
D2 = “descrizione computer: CPU, RAM, Hard disk”
Il dizionario è l’unione dei due insiemi:
T = {ingredienti,pizza,farina,acqua,lievito,olio,descrizione,computer,CPU,RAM,Hard Disk}
n=11 dimensione dello spazio
La rappresentazione BOW dei due documenti:
D1 = (1,1,1,1,1,1,0,0,0,0,0)
D2 = (0,0,0,0,0,0,1,1,1,1,1)
Se un utente esegue una query Q= “ingredienti pizza” essa viene
rappresentata come:
Q = (1,1,0,0,0,0,0,0,0,0,0)
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Grado di similarità
Il calcolo della similitudine tra due documenti diventa il calcolo della
distanza tra due vettori:
– Sim(Di , Dj) = d (Di , Dj)
Normalmente si utilizza la distanza del coseno:
– Sim(Di , Dj) = cos (Di , Dj) =
 Di , D j 
Di  D j
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Es. (reprise)
Nell’ esempio precedente avevamo:
D1 = (1,1,1,1,1,1,0,0,0,0,0)
D2 = (0,0,0,0,0,0,1,1,1,1,1)
Q = (1,1,0,0,0,0,0,0,0,0,0)
Calcolando sim( ) avremo:
Sim (D1, D2) = 0
Sim (Q , D1) = 0.37
Sim (Q , D2) = 0
Ed il sistema restituisce il documento D1
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Soglia di similarità
Nella realtà:
Databases con milioni di documenti
Dizionario formato da migliaia di parole (vettori di ~10.000 componenti)
Conseguenze:
Molti confronti con un valore di similarità prossimo a zero ma non zero
Soluzione:
Soglia di similarità
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Bag-Of-Word
Limiti:
Rappresentazione cruda del testo (non viene analizzata la semantica)
Parole uguali che assumono nel documento significati differenti
sono trattate come la stessa parola
Presenza di elevato rumore (vedremo più avanti)
Vantaggi:
Semplice e veloce
Relativamente bassa complessità computazionale
Buoni risultati (60 % – 70 % in classificazione)
Studiata da 15 anni
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Rumore
Con rumore si intende qualunque cosa che disturba il buon
comportamento del sistema
In questo caso:
Parole poco informative sul topic del documento
(articoli, congiunzioni, avverbi)
Parole diverse con significati simili (sinonimi)
Parole uguali con significati diversi (es. àncora e ancòra)
Verbi coniugati (vado e andare)
Per limitare alcuni di questi problemi sono stati studiati
metodi di pre-processing
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Normalizzazione del testo
Consiste in quattro step di cui due opzionali:
1.
2.
3.
4.
Tokenization
Conversion to lowercase
Lemming
Stop-word
Tali operazioni tentano di ridurre il rumore introdotto
dalla rappresentazione bag-of-word del documento
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Tokenization
Evita che parole e punteggiatura siano incorporate in un
unico termine, separandoli come due parole disgiunte
Es.
“ Today, stocks closed higher on heavy trading. Many stocks,
despite early losses, reached all time highs.”
“ Today , stocks closed higher on heavy trading . Many stocks ,
despite early losses , reached all time highs . ”
Ovviamente non è tutto così semplice:
Se il punto fa parte del termine deve rimanere tale
(es. nomi di società, indirizzi e-mail ecc…)
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Conversion to lower case
Evita che termini scritti totalmente o parzialmente in
maiuscolo e in minuscolo vengano considerati diversamente
Es.
“today , stocks closed higher on heavy trading . many stocks ,
despite early losses , reached all time highs . ”
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Stemming
Riporta i termini alla loro radice:
Verbi coniugati
Plurale e singolare
Maschile e femminile
Es.
“Today, stocks closed higher on heavy trading. Many stocks,
despite early losses, reached all time highs.”
“Today, stock close high on heavy trade. Many stock, despite
early loss, reach all time high.”
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Stop Words
Elimina le parole comuni con un grado di informazione
minimo sul topic del documento:
Articoli
Congiunzioni
Avverbi
Verbi ausiliari
Verbi che non portano informazione (es. potere, fare, ecc…)
I termini sono così suddivisi in due tipi:
Stop Words: inutili all’individuazione del topic
Function Words: importanti per “capire” il topic
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Text-IR
Avevamo visto che Text Information Retrival raccoglie:
Text Retrieval:
– Data una query, recuperare i documenti più attinenti
Text Segmentation:
– Dato un documento, suddividerlo in sub-topic
Text Classification:
– Determinare la classe del documento tra un insieme di classi prestabilito
Document Clustering:
– Dato un database documentale, determinare l’insieme delle classi e
gli abbinamenti classe-doumento
Vediamo come analizzare tali problemi utilizzando la filosofia
Bag-Of-Word
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Text-IR - 1
Text Retrieval:
La query Q è vista come un documento
Calcolo di sim(Q , Dj) per ogni documento Dj
Documenti con sim(Q , Dj) abbastanza elevato vengono ritenuti
significativi per la ricerca e restituiti all’utente
Text Segmentation:
Si definiscono unità testuali atomiche lunghe k word dette sentenze: Si
Si calcola la similarità tra ogni unità e la sua successiva: sim( Sj , Sj+1 )
Si considera un taglio quando tale valore scende sotto una soglia
Nomi eccellenti: Salton, Hearst, Reinar, Beeferman
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Text-IR - 2
Text Classification:
Ogni classe Ci è vista come un documento (vettore)
Dato un documento Dj , si calcola sim(Ci , Dj) per ogni Ci
Dj viene inserito nella classe per cui sim(Ci , Dj) è massimo
Document Clustering:
Si prendono due o più punti a caso detti centroidi Ci
Per ogni documento Dj si calcola la sua similarità con i centroidi Ci : sim(Ci , Dj)
Si assegna Dj al centroide per cui sim(Ci , Dj) è massimo
Si calcola di nuovo i centroidi come media dei vettori che vi appartengono
Si ripete il procedimento fino a che il centroide non si stabilizza
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Text-IR conclusioni
Come si vede si può riportare ogni problema al calcolo di sim(Ci , Dj)
Utilizzando il Bag-Of-Word si possono risolvere tutti i problemi relativi
al IR in maniera semplice ed elegante
Ovviamente vi sono altre tecniche (specialmente per la segmentazione
ed il clustering) ma si rifanno comunque ad una rappresentazione
BOW del testo
Segmentazione: dot-plot, entropiche, a regole, ecc..
Clustering: gerarchico
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione
Altri approcci
Considerando il testo come sequenza temporale di parole:
HMM
Reti Neurali
Si cerca di:
Sfruttare l’informazione sulla posizione della parola
Individuare contesti
Scopo:
Determinare i topic all’interno dei documenti (segmentazione)
Classificare un documento in base ai sub-topic
Restituire documenti della classe desiderata
Rigutini Leonardo – Dipartimento di Ingegneria dell’Informazione