Università degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria - Corso di Laurea in Ingegneria Informatica
Risoluzione di ambiguità semantiche per la
ricerca di similarità tra frasi
Erika Stefanini
Relatore:
Correlatori:
Prof. Paolo Tiberio
Dott. Federica Mandreoli
Ing. Riccardo Martoglia
Anno Accademico 2002/2003
Obiettivi della tesi:
• realizzazione di un modulo indipendente per la
risoluzione di ambiguità semantiche (word sense
disambiguation) di termini appartenenti a frasi di
lingua inglese
• questo modulo verrà poi utilizzato all’interno del
progetto EXTRA
Sistema EXTRA:
Ricerca approssimata
di frasi
(Pre-traduzione)
Suggerimenti per la
traduzione
Testo da
tradurre
Frase originale
Frase Tradotta
The white cat is hunting
the mouse
Il gatto bianco sta
cacciando il topo.
The white feline is
catching the rodent.
Il felino bianco sta
catturando il roditore.
The white computer is
detecting a mouse.
Il computer bianco sta
rintracciando un mouse.
Traduttore
professionista
Testo
tradotto
Allineamento
The white cat is hunting the mouse
Edit=1distance
= 3= 0,57
Sim
ed/lung
The
Thewhite
whitecomputer
feline is catching
is detecting
the arodent
mouse
La risoluzione di ambiguità semantiche dei termini
(word sense disambiguation):
• è stata un tema di grande interesse fin dagli anni
’50
• è stata studiata ed utilizzata in diversi settori:
intelligenza
artificiale
(comprensione
del
linguaggio naturale), traduzione automatica,
information retrieval
• consiste nel determinare in modo automatico il
significato più appropriato di una parola in base al
contesto (frase) in cui si trova
• 2 tipi di approccio per il wsd
WordNet
È un sistema
lessicale basato sulle
teorie
psicolinguistiche
della memoria
lessicale umana
Word
Meanings
Word Forms
apricot
apricot tree
Asian tree having clusters
of usually white
blossoms…
X
X
Downy yellow to rosycolored fruit resembling a
small peach
X
A shade of pink tinged
with yellow
X
• La caratteristica principale di WordNet è l’organizzazione delle
informazioni lessicali delle parole in base al loro significato e non alla
loro forma (lemma)
• Ogni parola è l’associazione tra la sua forma (il modo in cui viene
scritta) ed il significato che esprime; questa corrispondenza viene
espressa tramite la matrice lessicale
WordNet è stato realizzato presso il Cognitive Science Laboratory della Princeton
University da un gruppo di psicologi e linguisti coordinati dal prof. George A.
Miller.
WordNet divide l’insieme delle parole in 4 categorie:
•
•
•
•
Nomi
Aggettivi
Avverbi
Verbi
Ogni categoria è organizzata in insiemi di sinonimi
(synset) che rappresentano un concetto.
I synset sono collegati tra loro da diversi tipi di
relazioni semantiche.
Entity, physical thing
Substance, matter
Object, physical object
IPERONIMIA
Solid
Natural object
Un concetto rappresentato dal synset {y, y’,…}
è un iperonimo del
Plant part
Fooddal synset {x, x’,…} se si può costruire una frase
concetto rappresentato
Reproductive structure
del tipo An x is a (kind of) y.
Produce,green goods,…
Fruit
L’iperonimia genera una gerarchia simile alle gerarchie
di specializzazione
presente nei modelli E/R.
Edible fruit
Pome, false fruit
Gli algoritmi implementati tengono conto solo dei nomi e dei verbi.
Apple (significato numero 1)
TRASFORMAZIONE PRELIMINARE DELLA FRASE
frase originale
The white cat is hunting the mouse
stemming
parsing
frase “parserizzata”
frase “stemmizzata”
The/DT white/JJ cat/NN is/VBZ
hunting/VBG the/DT mouse/NN
estrazione di
nomi e verbi
white cat be hunt mouse
nomi = {cat,mouse}
Algoritmo wsd
nomi
lista nomi , lista verbi
nomi = {cat, mouse}, verbi = {be, hunt}
nomi = {cat,mouse}
verbi = {be,hunting}
Algoritmo wsd
verbi
ALGORITMO DI WORD
SENSE
DISAMBIGUATION DEI NOMI
Placental
mammal
Osservazione:
se un insieme
di parole
3
4 polisemiche sono simili, il loro
concetto comune dà informazioni su quale significato di
ognuna delle parole sia quello più adatto.
Carnivore
Rodent
Dato un insieme di nomi W = { w1, w2,…} considero tutte le possibili coppie (wi,
2
5
w j)
Feline, felid
Mouse
Calcolo della SIMILARITÀ SEMANTICA
di due nomi:
(significato 1)
si basa sulla1lunghezza del cammino necessario a percorrere la distanza che
li separa dal loro concetto minimo comune
len(cat#1, mouse#1) = 5
Cat
(significato 1)
sim(w1, w2) = - ln
len(w1, w2)
2*D
sim(cat#1,mouse#1) = 1,856
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI NOMI
Dati:
• un insieme di nomi w1, w2, …, wn
1,2
• sim(wi, wj) per ogni coppia di nomi
1
R(z) = 1 – 0.8 *
z
numsenses - 1
• c[i,j] = concetto minimo comune a wi e wj
R(z)
0,8
0,6
Si vuole
φ(w,k) funzione che indica la confidenza con cui si può
determinare:
dire che la parola w ha il significato k
0,4
0,2
0
0
2
4
6
8
10
12
Il significato migliore di un nome è quello che ha il più alto valore di φ.
z
PASSI
calcolo

coppia
della
di nomi
confidenza
wi e wj si determina v[i,j] = sim(wi, wj) * G(di – dj)
1,2
G(x)
support[i,k]
se
c[i,j]
è
un
iperonimo
di
sense
(wi, , se
k) normalization[i] != 0
1
φ (i,k) = α *
+ β * R(z)
normalization[i]0,8
allora
support[i,k] += 0,6
v[i,j]
 + = 1
oppure
0,4
normalization[i]
+= v[i,j]; normalization[j] += v[i,j];
1
0,2
φ (i,k) = α *
num_senses(w[i])0
-1 -9 -8 -7 -6 -5 -4 -3 -2 -1
0
+ β * R(z) , se normalization[i] = 0
0
1
2
3
4
5
6
7
8
x
9 10
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBI
Per i verbi approccio di tipo diverso:
definizioni dei significati di WordNet
Sense 2
look, appear, seem -- (give a certain impression or have a certain outward
aspect; "She seems to be sleeping"; "This appears to be a very difficult
problem"; "This project looks fishy"; "They appeared like people who
had not eaten or slept for a long time")
Descrizione del significato + frasi di esempio
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBI
Dati:
• N = insieme nomi presenti nella frase in cui compare verbo v
• nomi_es(v, k) = insieme nomi nella definizione del significato k
del verbo v;
1,2
k
numsenses
-1
• sim(nomei, nome_es
j) ,  nomei  N e  nome_esj  nomi_es(v,k)
R(k) = 1 – 0.9 *
1
R(k)
0,8
0,6
Si vuole
φ(v,k) funzione che indica la confidenza con cui si
0,4
determinare:
dire che il verbo v ha il significato k
può
0,2
Il significato
migliore del verbo v è quello con il valore più alto di φ.
0
0
PASSI
2
4
6
8
10
12
k
Calcolo
 nomeidella
 N confidenza
maxi = max{ sim(nomei , nome_esj), con j = 1,2, ..., m}
1,2
G(x)
1
0,8
φ(v, k) = R(k) *  G(d )G*(max
 d)
i
i
i
i
0,6
0,4
i
0,2
0
-1 -9 -8 -7 -6 -5 -4 -3 -2 -1
0
0
1
2
3
4
5
6
7
8
x
9 10
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBI
Poiché WordNet contiene verbi con oltre 30 significati, si è deciso di
sfruttare l’andamento di R(k) per migliore l’efficienza dell’algoritmo.
La retta R(k) è decrescente
R(k) > R(k+1)
Se risulta vera la condizione φ(v,k) > R(k+1)
φ(v,k) = R(k)*T(v,k) > R(k+1) > R(k+1)*T(v,k+1) = φ(v,k+1)
Si può smettere di calcolare φ(v,k) per k > k+1, visto che in questo
intervallo si otterrebbero valori minori di φ(v,k)
GENERAZIONE CODICI
WordNet assegna ad ogni significato un codice numerico univoco.
Dopo aver eseguito gli algoritmi di word sense disambiguation, ad
ogni nome o verbo della frase “stemmizzata” viene sostituito il
codice del significato che è risultato essere migliore.
Frase originale:
Frase originale:
The white cat is hunting the mouse
The white feline
computer
is catching
is detecting
the rodent
a mouse
Frase “stemmizzata”:
Frase “stemmizzata”:
white cat be hunt mouse
white
white
computer
feline bebecatch
detect
rodent
mouse
Frase con codici:
Frase con codici:
white 1788952 2058045 903354 1993014
white
white1788952
78465482058045
2058045837447
6585461993014
85657
RISULTATI ALGORITMO WSD NOMI
Media delle percentuali di successo
caso primaedopo = 0
79,5
70
68,6
80
70
media % successo
Collezioni dati di tipo tecnico e di
tipo generico (da opere letterarie)
60
DPaint
50
elettrodomestici
40
op.letterarie
30
20
10
0
casi primaedopo = 0 e primaedopo > 0 a confronto
100
90,7
90
media % successo
80
70
73,4
77
79,5
68,6
70
60
primaedopo=0
50
primaedopo>0
40
30
1=DPaint
2=elettrodom.
3=op.letterarie
20
10
0
1
2
3
RISULTATI ALGORITMO WSD VERBI
È molto difficile stabilire con certezza il giusto significato di un verbo
Esempio:
Frase originale:
The great musician Mozart composed nine symphonies
and many other musical composition.
The verb compose has 6 senses (first 5 from tagged texts):
1.
(14) compose -- (form the substance of; "Greed and ambition composed
his personality")
2. (5) compose, write -- (write music; "Beethoven composed nine symphonies")
3. (4) write, compose, pen, indite -- (produce a literary work; "She composed a
poem"; "He wrote four novels")
4. (3) compose, compile -- (put together out of existing material; "compile a list")
5. (1) compose -- (calm (someone, esp. oneself); make quiet; "She had to compose
herself before she could reply to this terrible insult")
6. frame, outline, compose, draw up -- (draw up the plans or basic details for;
"frame a policy")
Obiettivi raggiunti :

definizione della funzione di similarità semantica: fornisce una
misura della somiglianza di significato tra due concetti

tramite questa funzione sono stati sviluppati gli algoritmi di
word sense disambiguation: per ogni significato si è
determinata la confidenza con cui poter giudicare quanto fosse
appropriato
si è aumentata l’efficacia dell’algoritmo relativo ai nomi
valutando anche i nomi delle frasi adiacenti

Sviluppi futuri :



Per i nomi: considerare anche altri tipi di relazioni oltre l’iperonimia
Per i verbi: analizzare le frasi in base all’analisi logica per
determinare soggetto ed eventuale complemento oggetto
Approccio di tipo statistico