Risoluzione di ambiguità semantiche per la ricerca di similarità tra frasi
-
Upload
lawrence-bullock -
Category
Documents
-
view
19 -
download
1
description
Transcript of Risoluzione di ambiguità semantiche per la ricerca di similarità tra frasi
Risoluzione di ambiguità semantiche per la Risoluzione di ambiguità semantiche per la ricerca di similarità tra frasiricerca di similarità tra frasi
Erika StefaniniErika Stefanini
Università degli Studi di Modena e Reggio EmiliaUniversità degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria - Corso di Laurea in Ingegneria InformaticaFacoltà di Ingegneria - Corso di Laurea in Ingegneria Informatica
Relatore:Relatore:
Prof. Paolo TiberioProf. Paolo Tiberio
Correlatori:Correlatori:
Dott. Federica MandreoliDott. Federica Mandreoli
Ing. Riccardo MartogliaIng. Riccardo Martoglia
Anno Accademico 2002/2003Anno Accademico 2002/2003
Obiettivi della tesi: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:Sistema EXTRA:
Ricerca approssimata Ricerca approssimata di frasi di frasi
(Pre-traduzione)(Pre-traduzione)
Testo da Testo da tradurretradurre
Suggerimenti per la Suggerimenti per la traduzionetraduzione
AllineamentoAllineamento
Testo Testo tradottotradotto
TraduttoreTraduttore professionistaprofessionista
The white cat is hunting the mouse
The white feline is catching the rodentThe white computer is detecting a mouse
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.
Edit distance = 3Sim =1- ed/lung = 0,57
• è 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
La risoluzione di ambiguità semantiche dei termini (word sense disambiguation):
WordNet è stato realizzato presso il Cognitive Science Laboratory della Princeton University da un gruppo di psicologi e linguisti coordinati dal prof. George A. Miller.
• 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
WordNetWordNet
È 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 rosy-colored fruit resembling a small peach
X
A shade of pink tinged with yellow X
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.
IPERONIMIA
Un concetto rappresentato dal synset {y, y’,…} è un iperonimo del concetto rappresentato dal synset {x, x’,…} se si può costruire una frase del tipo An x is a (kind of) y.
L’iperonimia genera una gerarchia simile alle gerarchie di specializzazione presente nei modelli E/R.
Substance, matter
Natural object
Plant part
Reproductive structure
Fruit
Solid
Food
Produce,green goods,…
Edible fruit Pome, false fruit
Apple (significato numero 1)
Object, physical object
Entity, physical thing
Gli algoritmi implementati tengono conto solo dei nomi e dei verbi.
TRASFORMAZIONE PRELIMINARE DELLA FRASE
frase originale
parsing
frase “parserizzata”
stemming
frase “stemmizzata”
lista nomi , lista verbi
estrazione di nomi e verbi
The white cat is hunting the mouse
The/DT white/JJ cat/NN is/VBZ hunting/VBG the/DT mouse/NN
white cat be hunt mouse
nomi = {cat, mouse}, verbi = {be, hunt}
Algoritmo wsd
nomi nomi = {cat,mouse}
Algoritmo wsd
verbi verbi = {be,hunting}nomi = {cat,mouse}
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI NOMIALGORITMO DI WORD SENSE DISAMBIGUATION DEI NOMI
Osservazione: se un insieme di parole polisemiche sono simili, il loro concetto comune dà informazioni su quale significato di ognuna delle parole sia quello più adatto.
Calcolo della SIMILARITÀ SEMANTICA di due nomi:
si basa sulla lunghezza del cammino necessario a percorrere la distanza che li separa dal loro concetto minimo comune
Dato un insieme di nomi W = { w1, w2,…} considero tutte le possibili coppie (wi, wj)
Placental mammal
Carnivore Rodent
Feline, felid
Cat(significato 1)
Mouse(significato 1)
1
2
3 4
5
len(cat#1, mouse#1) = 5
sim(cat#1,mouse#1) = 1,856
sim(w1, w2) = - ln len(w1, w2)
2*D
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI NOMIALGORITMO DI WORD SENSE DISAMBIGUATION DEI NOMI
Dati: • un insieme di nomi w1, w2, …, wn
• sim(wi, wj) per ogni coppia di nomi
• c[i,j] = concetto minimo comune a wi e wj
Si vuole determinare:
φ(w,k) funzione che indica la confidenza con cui si può dire che la parola w ha il significato k
PASSI
se c[i,j] è un iperonimo di sense (wi , k)
allora support[i,k] += v[i,j]
normalization[i] += v[i,j]; normalization[j] += v[i,j];
calcolo della confidenza coppia di nomi wi e wj si determina v[i,j] = sim(wi, wj) * G(di – dj)
0
0,2
0,4
0,6
0,8
1
1,2
-10
-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10x
Il significato migliore di un nome è quello che ha il più alto valore di φ.
oppure
φ (i,k) = α * support[i,k]
normalization[i] + β * R(z) , se normalization[i] != 0
φ (i,k) = α * 1
num_senses(w[i]) + β * R(z) , se normalization[i] = 0
+ = 1
0
0,2
0,4
0,6
0,8
1
1,2
0 2 4 6 8 10 12
z
R(z
)
R(z) = 1 – 0.8 * z
numsenses - 1
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBIALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBI
Per i verbi approccio di tipo diverso:
definizioni dei significati di WordNet
Sense 2look, 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 VERBIALGORITMO 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;
• sim(nomei, nome_esj) , nomei N e nome_esj nomi_es(v,k)
Si vuole determinare:
φ(v,k) funzione che indica la confidenza con cui si può dire che il verbo v ha il significato k
PASSImaxi = max{ sim(nomei , nome_esj), con j = 1,2, ..., m} nomei NCalcolo della confidenza
φ(v, k) = R(k) * ii
i
ii
dG
dG
)(
max*)(
Il significato migliore del verbo v è quello con il valore più alto di φ.
0
0,2
0,4
0,6
0,8
1
1,2
-10
-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10x
G(x)
0
0,2
0,4
0,6
0,8
1
1,2
0 2 4 6 8 10 12
k
R(k
)
R(k) = 1 – 0.9 * k
numsenses - 1
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)
ALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBIALGORITMO DI WORD SENSE DISAMBIGUATION DEI VERBI
GENERAZIONE CODICIGENERAZIONE CODICI
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.
WordNet assegna ad ogni significato un codice numerico univoco.
The white cat is hunting the mouse
white cat be hunt mouse
Frase originale:
Frase “stemmizzata”:
Frase con codici:
white 1788952 2058045 903354 1993014
The white feline is catching the rodent
white feline be catch rodent
Frase originale:
Frase “stemmizzata”:
Frase con codici:
white 1788952 2058045 837447 1993014
The white computer is detecting a mouse
white computer be detect mouse
Frase originale:
Frase “stemmizzata”:
Frase con codici:
white 7846548 2058045 658546 85657
70 68,6
79,5
0
10
20
30
40
50
60
70
80
media
% s
uccesso
DPaint
elettrodomestici
op.letterarie
Media delle percentuali di successo
caso primaedopo = 0
casi primaedopo = 0 e primaedopo > 0 a confronto
7073,4
68,6
77 79,5
90,7
0
10
20
30
40
50
60
70
80
90
100
media
% s
uccesso
1 2 3
primaedopo=0
primaedopo>0
1=DPaint2=elettrodom.3=op.letterarie
RISULTATI ALGORITMO WSD NOMIRISULTATI ALGORITMO WSD NOMI
Collezioni dati di tipo tecnico e di tipo generico (da opere letterarie)
RISULTATI ALGORITMO WSD VERBIRISULTATI 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 :Obiettivi raggiunti :
Sviluppi futuri :Sviluppi futuri :
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
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