POLITECNICO DI MILANO
Polo Regionale di Como
Facoltà di Ingegneria dell’Informazione
Corso di Studi in Ingegneria Informatica on line
Riconoscitori di lingua in documenti testuali
Tutor universitario: Prof. Giuseppe Pozzi
Elaborato finale
di:
Andrea Serighelli
matr. 679850
A.A. 2007-2008
Riconoscitori di lingua in documenti
testuali
1
Sommario
Metodologie di riconoscimento della
lingua di un testo
 Software di implementazione
 Misure di prestazione
 Confronto tra le diverse metodologie
implementate

Riconoscitori di lingua in documenti
testuali
2
Definizione di riconoscitore
linguistico
FileTesto1.txt
LinguaTesto1
FileTesto2.txt
LinguaTesto2
FileTesto3.txt
LinguaTesto3
Testi
Più formalmente:
Lingua
Riconoscitore
CL : D x C → {0,1}
dove:
CL: algoritmo di riconoscimento linguistico
D: dominio dei documenti di testo
C: dominio delle lingue
se CL (dЄD,cЄC) = 1 allora secondo CL d è scritto nella lingua c
se CL (dЄD,cЄC) = 0 allora secondo CL d non è scritto nella lingua c
Riconoscitori di lingua in documenti
testuali
problema decisionale
3
Strategia di implementazione

Abbiamo adattato tecniche applicate al più
ampio problema della categorizzazione di
un documento testuale
•Base di
conoscenza
•Base di
regole
Sistema esperto
vs
Apprendimento
automatico
•Supervisore
•Set di training
•Ipotesi di induzione
e generalizzazione
•Set di test
Riconoscitori di lingua in documenti
testuali
4
Funzionamento del riconoscitore
•Fase di apprendimento
Training set
Index – term
[the,un,et,il,y]
Indicizzazione
Index-Vector
Apprendimento
M odello
Riconoscitori di lingua in documenti
testuali
5
Funzionamento del riconoscitore
•Fase di riconoscimento
IndexVector
Categorization Status
Value
Modello
Index – term
[the,un,et,il,y]
Indicizzazione
Riconoscimento
Decisione
Lingua
riconosciuta
Documento
Test
Riconoscitori di lingua in documenti
testuali
6
Misure di prestazione


Tecniche basate sul conteggio dei casi
Vero/Falso Positivo e Vero/Falso Negativo
Tabelle di contingenza
Lingua ci
Decisione esperto
Si
No
Si
VPi
FPi
No
FNi
VNi
Decisione
riconoscitore



Calcolo della precisione Pri = VPi / (VPi+FPi)
Calcolo della recall Rei = VPi / (VPi+FNi)
Calcolo delle medie (micro e macro averaging)
Riconoscitori di lingua in documenti
testuali
7
L’applicazione software

Paradigma di programmazione a oggetti:
linguaggio JAVA
Riconoscitori di lingua in documenti
testuali
8
Testing dei riconoscitori
implementati




Implementati tre differenti metodologie di
riconoscimento
Addestrati i riconoscitori con Training-set
costituito da 30 documenti
Totale di 10 lingue europee apprese
Index term costituito da 11 elementi:
index term
il

y
the
der
et
på
o
aa
ã
ö
i
Testati i riconoscitori con Testing-set costituito
da 60 documenti
Riconoscitori di lingua in documenti
testuali
9
Metodologia Naive Bayes

Stima della probabilità che il documento
sia scritto nella lingua Ci
ricavati in fase di addestramento
CSVi(d) = P(ci|d) = Π [P(ci|ty)•P(ty|d) + P(ci|ty)•P(ty|d)]
y=1...r
ricavati dall’indicizzazione di d
Nel calcolo della stima percentuale concorrono le probabilità condizionate (Bayes) legate alla
presenza e assenza di un particolare termine dell’index-vector....e tali probabilità concorrono
come r fattori indipendenti (Naive)!
Riconoscitori di lingua in documenti
testuali
10
Metodologia Naive Bayes - soglie


La lingua relativa alla componente di CSV maggiore,
potrebbe non rappresenta la decisione migliore !!!
Soglie decisionali differenti
componente i del vettore csv di dtrain
τi = Σ csvitrain / |{dtrain}|
dtrainЄ ci

E’ scelta la lingua avente rapporto CSVi / i maggiore
Riconoscitori di lingua in documenti
testuali
11
Metodologia Naive Bayes - prestazioni

Nessun errore di riconoscimento
 Necessario l’utilizzo delle soglie
decisionali !
Metodologia Naive Bayes
senza soglia
con soglia
italiano
spagnolo
francese
catalano
suomi
/
PrM (%)
69.12*
100
ReM (%)
85.24*
100
Pr = Re (%)
45.00
100
lingue non
riconosciute
Riconoscitori di lingua in documenti
testuali
12
Metodologia profile-based


Ad ogni lingua è associato un profilo
Il profilo è un vettore di dimensione pari all’index-term
componente y del vettore wi
wiy = β ·d ΣЄ cvytrain/|{dtrain}| + γ ·d ΣЄvc ytrain/|{dtrain}|
train
i
train
i
β+γ=1
β>0, γ <= 0
componente y dell’index-vector di dtrain


Ad ogni lingua è associato un profilo
E’ scelta la lingua avente profilo più simile all’index-vector
del documento di test: CSVi (dtest) = d (index-dtest , wi)
Riconoscitori di lingua in documenti
testuali
13
Metodologia profile-based

Rappresentazione geometrica
t1
W0 = (0.5, 0.1, 0.4)
w1 = (0.1, 0.7, 0.2)
w1
t2


w2 = (0.4, 0, 0.6)
d

d = (0.2, 0.6, 0.2)
w2
w0
t0
Index-term a tre elementi:
spazio 3-dim
Riconoscitore riconosce
tre lingue: 3 profili
d è più vicino a w1 (la
distanza d(d,w1) è minore
di tutte le altre): d è scritto
nella lingua rappresentata
da w1
t0
Riconoscitori di lingua in documenti
testuali
14
Metodologia profile-based - prestazioni


Buone prestazioni
Nessuna sensibile differenza con l’utilizzo della
formula completa
Metodologia profile-based
 =1 e  = 0
 =1.2 e  = -0.2
/
/
PrM (%)
98.33
97.08
ReM (%)
98.33
96.67
Pr = Re (%)
98.33
96.67
lingue non
riconosciute
Riconoscitori di lingua in documenti
testuali
15
Metodologia example-based




L’index-vector del documento di test è
confrontato con gli index-vector dei documenti di
training
È scelta la lingua del documento di training
avente index-vector più simile
Lazy classifier: non è costruito alcun modello!
Come funzione di confronto è stata utilizzata la
distanza euclidea tra vettori
Riconoscitori di lingua in documenti
testuali
16
Metodologia example-based

Evoluzione: si confronta il documento di test con
i K documenti di training più simili (K=1 è il caso
precedente)
Retrieval Status Value: misura di quanto dtest e dtrain sono simili (es: distanza degli index-vector,
ma anche indici di correlazione, relazioni semantiche....)
CSVi = Σ RSV (dtest, dtrain)
dtrainЄ k-best ci|
k documenti di training classificati in ci con max valore RSV (dtest, dtrain)

Per K=1 e RSV intesa come distanza euclidea si
torna al caso precedente
Riconoscitori di lingua in documenti
testuali
17
Metodologia example-based - prestazioni



Nessun errore di riconoscimento per K=2
Molto buono anche nella versione semplice con
K=1
Ottimo rapporto costo/prestazioni
Metodologia example-based
K=1
K=2
lingue non riconosciute
/
/
PrM (%)
98.33
100
ReM (%)
98.33
100
Pr = Re (%)
98.33
100
Riconoscitori di lingua in documenti
testuali
18
Conclusioni



L’approccio basato sull’apprendimento
automatico supervisionato si è mostrato valido
Tale approccio permette di modificare il dominio
applicativo riaddestrando i riconoscitori (es:
diverse lingue, differenti ambiti, ....)
Temi aperti: riconoscimento della lingua dei
documenti web, ottimizzazione dell’index-term,
estensione delle metodologie implementate in
ambiti più vasti (categorizzazione dei testi,
sistemi in cascata).
Riconoscitori di lingua in documenti
testuali
19
Materiale

Volume tesi e applicazione scaricabili al
seguente indirizzo web:
http://digilander.libero.it/Pietrino71as/
Riconoscitori di lingua in documenti
testuali
20