Sistemi avanzati di Web
Information retrieval
e
Elaborazione del linguaggio
Naturale
Sistemi Avanzati di IR
• Sistemi di classificazione automatica
• Sistemi di Information Extraction
• Sistemi di Question Answering
NLP,
IA
• Information Extraction
– Viene specificato un argomento (avvicendamenti
di managers in aziende di informatica)
– Vengono filtrate notizie rilevanti
– Vengono riempiti dei “templates” (simili a basi di
dati)
• Question answering
– Lezioni di J. Bos
Fasi nell’analisi automatica di
testi
Elaborazione linguaggio naturale
Analisi frasi
Morfologia
Analisi discorso
Sintassi
generazione
Semantica
Metodologie
•
•
•
•
Linguaggi regolari (automi)
Grammatiche context-free
Grammatiche estese
+ apprendimento automatico, metodi
probabilistici
Analisi Morfologica
Problema: identificare la categoria
morfosintattiche di un te rmine (nome, verbo..) e
le sue parti componenti. POS+inflessione
Es:
A L or illard
sto r y."
parte "T
delhis
discorso
(POS)
radicesp okewoma n said,
is an o ld
am_(_, 1 ,[ 93 ,'A ' ],a,a,art icle,'indefinite_singular').
am_(_, 2 ,[ 94 ,'L o rillard ' ], ' #u # ',a,'#u # ', ' #u#' ) .
am_(_, 3 ,[ 95, spok ewo man],'s p oke + wo man',a,'co m mo n_noun '
,singular).
am_(_, 4 ,[ 96,said ] ,say,a,v erb,' simple_past').
am_(_, 4 ,[ 96,said ] ,say,a,v erb, 'p ast_part iciple').
am_(_, 5 ,[ 97 ,', ' ], ' ,',a,'pu nct _ co mma',i nvariable).
am_(_, 6 ,[ 98 ,'" ' ], ' "',a,'pu nct _ d ouble_ q uotes ' ,inv ariable).
am_(_, 7 ,[ 99 ,'This ' ],this,a,'d em ons t rativ e_det er mine r ',singula
r).
am_(_, 7 ,[ 99 ,'This ' ],this,a,'d em ons t rativ e_ p ro noun',sin g ular).
am_(_, 8 ,[ 1 0 0,'is ' ],be,a,'auxiliary _ v erb' ,'simple_ p resen t _ 3r d_
singular').
am_(_, 8 ,[ 1 0 0, 'is ' ],be,a ,v erb ,'simple_ p resen t _ 3r d_singula r ').
am_(_, 9 ,[ 1 0 1,an],an,a,article,'
indefinite_singular').
am_(_, 1 0 ,[ 1 02 ,ol d ],old,a,adje c tive ,'posit ive_ for m').
am_(_, 1 1 ,[ 1 03, st o ry ], st o ry,a, ' co m m on_nou n',singular).
am_(_, 1 2 ,[ 1 04 ,'" ' ], ' "',a,'pu nct _do uble_q uotes', invariable).
Approcci all'analisi morfologica:
1.Grammatiche libe re dal contesto (Context Free
Grammars): ogni rego la di riscrittura ha nella
parte sinistra un unico simbolo non terminale e
nella parte destra una lista di simboli terminali o
non terminali
Es. di regola: S a S b Es. di stringa : anbn
Es:
Parola prefisso n radice R1
R1 suffisso n alterazionen R2
R1 desinenza suffis son alterazionen R2
R2 desinenza enclitican
Ex: super-bel-issim-issim-o :
prefisso 1 radice alterazione2 desinenza
Strutture dati necessarie
Lemmario, o dizionario morfologico:
Elenco dei Lemmi,
Prefissi, Suffissi, Altera zioni, Desinenze,
Enclitiche, Radici
Es:
Radice(andare,and,1_coniug,verbo)
Radice(andare,vad, 1_coniug,verbo)
…
Approcci (2): linguaggi regolari
Grammatiche regolari (2)
Esempio
Fox, bat, fly
Esempio complesso di regola
di inflessione per Inglese
Apprendimento di Analizzatori
Morfologici
• Metodi stocastici (specialmente per POS
tagging)
– si etichettano con il POS archivi documentali di
grandi dimensioni (learning set)
– Si utilizza il learning set per imparare delle
probabilità (es: P(N/V,art) = probabilità di
osservare un nome dopo che si siano osservati un
verbo ed un articolo)
– Treetagger usa metodi probabilistici aumentati con
alberi di decisione
– http://www.ims.unistuttgart.de/projekte/corplex/TreeTagger/DecisionTreeTagger
.html
Esempio
Analisi Sintattica
Metodologie
• Grammatiche libere da contesto
• Grammatiche ad attributi
• Lexical Grammars (le “regole” sono
associate ai termini di un lessico)
• Trasduttori (le transizioni vengono
“apprese” utilizzando metodi stocastici,
come per il caso del POS tagging)
Grammatiche ad Attributi
Esempio:
NP  Determiner Noun
Attribute conditions :
Determiner.gender = Noun.gender
Determiner.numb er = Noun.number
Attribute Synthesis
NP.gender = Noun. gender
NP.number = Noun.number
NP.type = Noun.type
NP.head = Noun.lemma
Grammatiche ad attributi (2)
- regole di sotto-categorizzazione (verbi)
VP Verb Adjective
Verb.subcat.right. = Adj
(ex. Apparire subcat.left=NP subcat.right=Adj)
- restrizioni semantiche
VP Verb NP
Verb.semcat.subcat.righ t= NP.head.semcat
(ex. Mangiare semcat.subcat.right=food)
Parser sintattico
Un parser un programma che, data una frase F
espressa come sequenza di simboli terminali
(ogni terminale in realtuna stringa prodotta
dall'analizzatore morfologico) , una grammatica
G ed un insieme di simboli non terminali,
restituisce una rap presentazione strutturata di F.
Esempio
S
NP
VP
Det
Noun
Verb
Il
bimbo
mangia
PP
Prep
NP
NP
Det
Noun
con Det Noun la minestra
il
cucchiaio
Parsers e Chunkers
• Un parser tenta di produrre una
struttura completa della frase,
evidenziando le dipendenze fra
“phrases” (NP, VP, S, CONJ..)
• Un “chunker” si limita a riconosce i
costituenti principali (in genere, gruppi
nominali e verbali)
Esempio:
• The/DT cat/N eats/V the/DT mouse/N
• <NP> The/DT cat/N </NP> <VP>
eats/V</VP> <NP> the/DT mouse/N
</NP>
Analisi Semantica
• L'obiettivo dell'analisi semantica è comprendere il
significato di una frase.
• Da un punto di vista pratico questo vuol dire:
• per una frase dichiarativa, provarne la verità, o inferire da essa
nuove informazioni
• per una frase imperativa, eseguire l'azione richiesta
• per una frase interrogativa, rispondere al quesito
Approccio Composizionale
• Approccio composizionale: evidenzia il significato
di ogni concetto in termini di concetti più
specifici, o primitive
DESTINATION
• GO
ENTITY  MOVE
SOURCE
Approccio relazionale
• evidenzia la semantica superficiale, ovvero la
natura delle relazioni fra i termini che appaiono
nella frase.
• Es: (John goes home)
• person:
JohnAGENTGODESThome
Analisi Semantica
• Formalismo di rappresentazione (es: FOL)
• Algoritmo di analisi
• Base di conoscenza semantica
– Esempi:
• Ontologia
• Corpora annotati
• Basi di dati statistiche sulle associazioni fra concetti
Word Sense Disambiguation
• L’analisi semantica comporta la
trasformazione di un testo (o documento) in
una struttura formale (es. un grafo, o una
espressione FOL)
• Es:
[John]agent [go] dest[city:Boston]
manner[bus]
WSD (2)
• La Word Sense Disambiguation è un
compito più semplice.
• Data un frase o contesto, l’obiettivo è
associare ad ogni parola il concetto, o
senso, appropriato rispetto ad un
lessico semantico (catalogo di sensi,
esempio, WordNet, CYC, ..)
Esempio
• The river banks are green
•
•
•
•
•
•
River: * S: (1) river (a large natural stream of water (larger than a
creek)) "the river was navigable for 50 miles”
Bank# S: (1) depository financial institution, bank, banking concern,
banking company (a financial institution that accepts deposits and
channels the money into lending activities) "he cashed a check at the
bank"; "that bank holds the mortgage on my home"
# S: (2) bank (sloping land (especially the slope beside a body of
water)) "they pulled the canoe up on the bank"; "he sat on the bank of
the river and watched the currents"
# S: (3) bank (a supply or stock held in reserve for future use
(especially in emergencies))
# S: (4) bank, bank building (a building in which the business of
banking transacted) "the bank is on the corner of Nassau and
Witherspoon”
……(in totale 10 sensi)
Metodi per WSD
• Metodi probabilistici
– Apprendono contesti probabili per i vari
sensi, basandosi su corpora o dizionari online
• Metodi basati su conoscenza
– Utilizzano basi di conoscenza (ontologie)
Word Sense Disambiguation:
esempio
The
waiter
served
white
port
intermediate node
Word Sense Disambiguation:
esempio
The
player#1
N
N
N
waiter#2
N
N
wine#1 N
N
V
serve#15N
port#2
N
N white
N
N
A
alcohol#1
white#1
N
serve#5
waiter#1
N
N
N
V
#2
N
beverage#1
N
N
word sense of interest
N
N
person#1
port
waiter #1 served#5 white #3
N
fortified wine#1
N
N
wine#1
A
N
white#3
N
port#1
Structural Semantic
Interconnections (SSI)
• Un metodo di WSD basato su pattern matching strutturato
• A partire da un elenco di termini (il contesto) genera un elenco di
concetti (i sensi dei termini) e associate relazioni . Usa wordNet
come catalogo di concetti.
T = [t1, t2, …, tn ]
SSI
I = [St1, St2, …, Stn]
semantica
contesto
giustificazione
per la scelta
dei sensi
interpretazione
SSI è un algoritmo basato su
conoscenza
• Lexical Knowledge Base (LKB) generato integrando
diverse risorse:
– WordNet
– Oxford Collocations
– Longman Language Activator
– SemCor e LDC-DSO (semantically annotated
corpora)
– Siti on-line di collocazioni
• L’integrazione delle risorse è ottenuta semiautomaticamente
– I’inventario di sensi è quello di WordNet
Structural Representations
Def. Una rappresentazione strutturale di un senso S è un
grafo ottenuto applicando un taglio al LKB, centrato in S, che
includa tutti i nodi a distanza massima d da S
f
-o
nd
ki
transport#1
person#1
traveler#1
f
o
d
n
ki
f
of
dd-o
n
n
i
i
k
k
passenger#1
public
protection#2
instrumentation#1
transport#1
glo bus#1
f
o
s
s
has-kind
express#2
rt
nd
-pa
ki
s
a
g lo s s
h
vehicle#1
roof#2
nd
i
covering#2
(a)
k
school bus#1
has
window#2 framework#3
rt
plate glass#1
pa
f
s
kindd-o
ha
of
kin
pane#1
window frame#1
ha s
f
-o
nd
ki
g
ki los
nd s
-o
f
Bus (transport)
-pa
rt
ha s
-pa
rt
pert
electricity#1
of
rtpa
gloss
of
union#4
ss
glo
ind
s-k
ha
k in d -
s
electrical#2
os
device#1
gl
inter
kind -o f
f
s
s
lo
d-o
g
n
instrumentality#3
connection#1
i
k
state#4
of
d
bus#2
n
ki
conductor#4
gloss
machine#1
f
d-o
has-kind
f
kin connection#2
o
d
kind-of
Bus (connector)
connected#6
k in
computer#1
haselectrical device#1 d-of
kind
wiring#1
kin circuit#1
calculator#2
(b)
Selezione e pesatura dei cammini
semantici
• E’ definita una grammatica context Free che riconosce cammini
significativi (es. sequenze di iperonimia, iperonimia + part_of..)
S1  E1S1 | E1
(hyperonymy/meronymy)
E1  ekind-of | epart-of
S2  E2S2 | E2
(hyponymy/holonymy)
E2  ehas-kind | ehas-part
S3  ekind-ofS3ehas-kind | ekind-ofehas-kind
(parallelism)
• I percorsi vengono pesati sulla base della rilevanza e della
lunghezza :
kind-of
kind-of
kind-of
redundancy#3
configuration#1
topology#4
bus#2
• fI(S, t) è una funzione di pesatura dei patterns
w( pathSS ' )   pathS ' 
S

length pathS '
S
Formalizzazione del problema
• T (il context) è un elenco di termini correlati
• t  T è un termine ambiguo
• S1t, S2t, …, Snt sono specifiche strutturali
(grafi) dei possibili senti di t
• I (il semantic context) è una lista di specifiche
strutturali del contesto T (inizialmente vuota)
• G è una grammatica che descrive correlazioni
rilevanti fra specifiche strutturali
• Determina il senso S1t, S2t, …, Snt che si
correla meglio con I, usando G
• Seleziona il senso migliore Sit
Tre implementazioni
• Ricerca esaustiva
– Precision e recall alte
– Molto lento (non adatto a contesti ampi)
• Implementazione greedy iterativa
– Abbastanza veloce
– Un errore può influenzare tutte le scelte successive
• Iterativa basata su link analysis (Kleinberg’s HITS)
– La più veloce
– Affidabile
Un esempio dell’implementazione greedy
• “A retrospective is an exhibition of a
representative selection of an artist's life
work”
• Inizializzazione:
– T = [ retrospective, exhibition,
representative, selection, artist, life, work ]
– I = [ retrospective#1, -, -, -, artist#1, -, -]
Esempio (2)
• Iterazione 1:
– T = [ retrospective, exhibition,
representative, selection, artist, life, work ]
– I = [ retrospective#1, exhibition#2, -, -,
artist#1, -, -]
Esempio (3)
• Iterazione 2:
– T = [ retrospective, exhibition,
representative, selection, artist, life, work ]
– I = [ retrospective#1, exhibition#2, -, -,
artist#1, -, work#5]
Esempio (4)
• Iterazione 3:
– T = [ retrospective, exhibition,
representative, selection, artist, life, work ]
– I = [ retrospective#1, exhibition#2, -, -,
artist#1, life#8, work#5]
Implementazione con HITS
• Applica HITS per ottenere un ranking dei concetti
• dato T = [ w1, w2, …, wn ], costruiamo G = (V, E), dove:
– V è il set dei possibili sensi delle parole in T rispetto a WordNet
V
– E è il set delle interconnessioni fra coppie {Sw, S’w} dove

2 

w’; e:
w≠
• Interconnesioni multiple fra le stesse coppie vengono collassate in un
unico arco il cui peso è calcolato come somma normalizzata dei
singoli pesi
• le interconnessioni sono simmetriche (sia “hubs” che “authorities” )
• Applichiamo HITS iteraticvamente
Implementing SSI with HITS
• T = [ w1, w2, w3, w4]
• I = [ -, -, -, - ]
1
w1
2
3
1
2
w2
1
3
3
2
3
1
2
w4
4
1
a
( )

1
2
1
1
3
w3
2
3
4
Implementing SSI with HITS
• T = [ w1, w2, w3, w4]
• I = [ -, -, -, #1 ]
2
w1
2
3
1
3
w2
1
1
3
2
3
1
2
w4
4
1
a
( )

2
1
1
2
3
w3
3
4
1
Implementing SSI with HITS
• T = [ w1, w2, w3, w4]
• I = [ -, #2, -, #1 ]
1
w1
2
3
1
3
w2
1
2
3
2
3
1
2
w4
4
1
a
( )

1
2
1
1
3
w3
2
3
4
Implementing SSI with HITS
• T = [ w1, w2, w3, w4]
• I = [ -, #2, #1, #1 ]
3
w1
2
3
1
1
w2
1
2
3
2
3
1
2
w4
4
1
a
( )

1
2
1
1
3
w3
2
3
4
Implementing SSI with HITS
• T = [ w1, w2, w3, w4]
• I = [ #3, #2, #1, #1 ]
3
w1
2
3
1
1
w2
1
2
3
2
3
1
2
w4
4
1
a
( )

1
2
1
1
3
w3
2
3
4
• On-line su
• http://lcl.di.uniroma1.it/ssi/