Metodi per il trattamento avanzato di
documenti
Quanta analisi del testo nei sistemi di accesso a
documenti?
• Motori di ricerca, sistemi di IR classici (parole chiave)
– Query: un elenco di parole
– Risposta: un elenco di documenti contenenti le parole
• Sistemi di Document Classification & Retrieval
– Query: un elenco di parole con operatori booleani
– Risposta:un elenco di documenti pertinenti
• Sistemi di Information Extraction
– Query: una specifica formale del “tipo” di informazioni di interesse
– Risposta:una base di dati strutturata
• Sistemi di “Open-Domain” Question Answering
– Query: una domanda qualsiasi in linguaggio naturale
– Risposta:una risposta in linguaggio naturale
Influenza delle metodologie di AI
nei sistemi di reperimento di
informazioni
Document
Classification:
NLP(+) Classif.
Algorithms (++)
Information Extraction :
NLP(++) KR&Inference (+)
Query Answering: NLP (+++) KR&Inference (++)
Metodi di Classificazione di
Documenti (1)
• Obiettivo:
– A partire da:
• Un insieme di categorie C: {C1,..Cn}(es: articoli di sport,
finanza, medicina..) eventualmente strutturate in una
tassonomia
• Un insieme di documenti appartenenti a ciascuna classe
Di1.. Din.(learning set)
– Apprendi un modello formale hi di ciascuna classe
tale che hi(Dik)= Ci(Dik)
Metodi di Classificazione di
Documenti (2)
• Metodo
– Rappresenta ogni D mediante un vettore di
caratteristiche f(D)=(<w1,p1>…<wm,pm>)
– Le caratteristiche sono coppie parola/peso
– Vari metodi (statistici+NLP) per selezionare le
parole rilevanti e determinare i pesi
– Per ogni classe Ci e set di documenti Dik genera
insieme di esempi S: x = <f(Djk), Ci(Djk)>
doveCi(Djk)=1 se Djk  Ci
Esempio:
Documento (Reuter’s collection): Colombia opened coffee
export registrations for April and May with the National
Coffee Growers' Federation setting no limit, Gilberto
Arango, president of the private exporters' association, said.
Vettore delle caratteristiche: (Colombia, open, coffee,
export, registr, April/date, May/date,
National_Coffee_Growers’_Federation/org,
president_Gilberto_Arango/pers, exporter_association)
(in realtà il vettore contiene V attributi binari ai, dove V è la
taglia del vocabolario, ai=1 se la parola i-esima di V è
presente, inoltre gli attributi possono essere “pesati”, come
abbiamo visto nei modelli IR classici)
Metodi di Classificazione di
Documenti (3)
• Per ogni classe Ci ed ogni set di esempi D si apprende un
modello della classe h(Ci)
• Metodi di apprendimento/ classificazione:
– Modello “bag of words” o vector space model h (Ci) è
un cluster di vettori, centr(Ci) è il “centroide” del
cluster
– Le parole sono pesate con tf-idf, la similarità fra un
nuovo documento e i modelli delle classi è la cosine
similarity già vista per IR
Metodi di Classificazione di
Documenti (4)
• Metodi di apprendimento/ classificazione
(cont’d)
– Funzioni lineari
h(Ci )  a1w1  a 2 w 2  .....a m w m
– Alberi di decisione
pij<valk
pin>valn
Ci
Metodi di Classificazione di
Documenti (5)
• Utilizzo di tecniche di NLP per migliorare la
classificazione:
– Rimpiazzare i termini con la radice (categorizzare, categorizziamo,
categorizzazione)
– Disambiguazione morfologica (es: piano/agg o piano/nome)
– Identificare termini complessi: nomi propri (president Bill Clinton)
terminologia ( real estate) espressioni regolari (date, numeri,
espressioni monetarie)
– Espansione semantica: rimpiazzare (alcuni) termini con liste di
sinonimi o categorie semantiche (es: money (money,currency,monetary
system))
Estrazione di Informazioni (1)
•Obiettivo: creazione di una rappresentazione
strutturata (template) da informazioni
“selezionate” estratte da archivi di testi
Es: Sam Swartz retired as executive vice president of the
famous hot dog manifacturer, Hupplewhite Inc.
He will be succeeded by Harry Himmelfarb.
EVENT
PERSON
POSITION
COMPANY
leave job
Sam Swartz
Executive vice president
Hupplewhite Inc
EVENT
PERSON
POSITION
COMPANY
start job
Harry Himmelfarb
Executive vice president
Hupplewhite Inc
Architettura di un sistema di IE
documenti
Analisi locale
analisi lessicale
riconoscimento di nomi propri
analisi sintattica parziale
pattern matching
Analisi del discorso
analisi di co-referenze
inferenze
generazione di templates
informazioni
strutturate
Analisi del testo nei sistemi di IE (1)
• Identificazione dei costituenti : il testo viene
segmentato in costrituenti sintattici semplici (vp e np)
cui possono eventualmente essere aggiunte
informazioni morfo-sintattiche
np e1: Sam Swartz  vp: retired  as np e2:executive vice
president  of np e3: the famous hot-dog manifacturer  np e4:
Hupplewhite Inc.. np e5:He vp: will be succeeded by np e6:
Harry Himmelfab 
Analisi del testo nei sistemi di IE (2)
• Classificazione dei segmenti:
e1
e2
e3
e4
e5
e6
type: person name "Sam Schartz"
type: human role "executive vice
president"
type: human org "manifacturer"
type: company name : "Hupplewhite Inc."
type: person "He"
type: person name "Harry Himmelfarb"
Analisi del testo nei sistemi di IE (3)
•Pattern matching: L'obiettivo di questa fase è di
identificare segmenti di frase che siano istanze di
segmenti generalizzati, o patterns.
person retires as position
person is succeded by person
….
•I patterns possono essere definiti mediante
espressioni regolari, equivalenti ad automi a stati
finiti.
Analisi del testo nei sistemi di IE (4)
•Coreference resolution L'obiettivo di questa fase
è identificare istanze dello stesso concetto,
espresse con forme superficiali diverse nel testo.
Ad esempio, nella frase di esempio fin qui
analizzata, i gruppi nominali e1 (Sam Swartz) e
e5 (He) si riferiscono alla stessa entità.
•I modelli di risoluzione di co-referenze fanno uso
di informazioni sintattiche (ad esempio, "He" deve
corrispondere ad una persona maschile singolare)
e semantiche.
KR & reasoning nei sistemi di IE (1)
•Inferenze e riempimento dei templates
L'obiettivo di questa fase è di riempire i templates
con porzioni di testo rilevanti.
Perché ciò sia possibile, è necessario effettuare
alcune inferenze il cui obiettivo è stabilire un
collegamento -altrimenti non evidente - fra
patterns e "slot-fillers" dei templates (o valori
degli attributi, se si vuol vedere un template come
un vettore di attributi)
KR & reasoning nei sistemi di IE (2)
Ad esempio se il template è:
e se i patterns catturati sono:
Sam Schwartz]person retires as
IN:
executive vice president]position
EVENT leave job
Harry Himmelfarb]person succeeds Sam
PERSON
leave-job person
Schwartz]person
POSITION
leave-job position
COMPANY
leave-job companyuna necessaria regola di inferenza è:
leave_job(X-person,YOUT:
position)succeed(Z-person,XEVENT start job
person)  start-job(Z-person, YPERSON
start-job person
position)
POSITION
start-job position
COMPANY
start-job company
e simmetricamente:
start_job(X-person,Yposition)succeed(X-person,Zperson)  leave-job(Z-person, Yposition)
Valutazione dei Sistemi di IE
• Uno dei vantaggi dei sistemi di IE consiste nell'esistenza di
procedure consolidate di valutazione, rappresentate dalle
Message Understanding Conferences (MUC)
• http://www.muc.saic.com/proceedings/muc_7_toc.html
• Queste conferenze sono in realtà "gare" di prestazione di
sistemi di IE, in cui le prestazioni vengono valutate sulla
base di:
- Test set comuni
- Indici di prestazione pre-stabiliti dagli organizzatori
- Procedure di valutazione comuni, preventivamente
predisposte
Sistemi di “Open-Domain” Question
Answering
•Obiettivo: rispondere in LN a domande in LN
di argomento qualsiasi
Es (le prime due da TREC-9
http://trec.nist.gov/pubs.html):
What tourist attractions are there in Reims?
When was the Brandeburg gate in Berlin built?
I would like to know if ACE has in its DB candidates in the financial area,
with 10 years of experience and fluency in English?
•La tecnologia dei sistemi di QA è ancora in
fase di definizione/assestamento
Architettura del “miglior” sistema:
“FALCON”, della SMU (1)
Knowledge-based Question
Processing
Shallow Document Processing
Knowledge-based Answer generation
Fase 1: analisi e trasformazione della
domanda
Query
Query
Taxonomy
Query Parsing &
Logic Form
Transformation
Lexico-semantic
patterns
Query Class
Recognition
Expanded Query 1
Word-sense
Taxonomy
Query
Expansion
Expanded Query n
Alcuni metodi utilizzati in questa
fase in FALCON
•Identificare riformulazioni di domande simili e mantenere una
“cache” di risposte (es: What are tourist attractions in Reims?
What can one see in Reims?)
•Dettagliata tassonomia delle Domande( e tipi di Risposta) (es.
di “top” classes: DATE, TIME, REASON, MANNER…),
collegata con una tassonomia generale (WordNet)
•Stabilire collegamenti fra i termini nella domanda e
tassonomia (es: What is the wingspan of a condor?(wingspan
 QUANTITY)
•Rappresentazione semantica e logica della domanda
Wingspan
QUANTITY
condor
wingspan(x)condor(y) QUANTITY(x)
Esempio:
Question: why did David Koresh ask the FBI for a
word processor?
Logic representation:
[REASON(x)&David(y)&Koresh(y)&ask(e,x,y,z,p)
&FBI(z)&processor(p)&word(p)]
Semantic expansion:
ask  ask, enquire, request,make a request
word processor  word processor , word processing
system
Fase 2: Estrazione di porzioni
rilevanti dai documenti
Classified
Documents
Expandeded
Queries
Document
Retrieval Engine
Answer 1
Answer
Extraction
Answer m
Metodi utilizzati in questa fase in
FALCON
• Espansione della query:
– Espansioni morfologiche: invent:
inventORinventorOR invent
– Espansioni lessicali e semantiche (killer:
assassinORkiller, like: likeORprefer)
Fase 3: generazione della risposta
Answer set
Parser
Semantic &
Logic Form
Transformation
false?
World Knowledge
Axioms
Theorem
Prover
True?
ANSWER
relax
Abductive
Rules
Metodi usati in questa fase in
FALCON
• Generazione di una forma semantica per il testo della
risposta
• Dapprima tenta di unificare domanda e risposta
• IF fail, applica espansioni lessicali finché
l’unificazione non ha successo
• Infine, genera una prova abduttiva dalla risposta alla
domanda, eventualmente applicando ulteriori
espansioni semantiche.
Esempio
•Testo estratto: “Over the week-end Mr Koresh sent a request
for a word processor to enable him to record his revelations”
•Forma logica ottenuta:
Mr(71)&Koresh(71)&word(72)&processor(72)&&revelati
ons(74)&record(73 74 75)&enable(75 73
76)&request(76)&sent(77 76 78
71)&weekend(78)&_PERSON(71)&DATE(78)
•Esempio di dimostrazione ( e assiomi utilizzati):
Proving:David(1)&Koresh(1)&word(2)&processor(2)&
FBI(4)&ask(34215)&_REASON(5)&_PERSON(1)&ORG(4)
unifying axioms: David(1):=Mr(1)..
ask(12345):=sent(1674)&request(6)
_ORG(1):=FBI(1)…..
•Se la dimostrazione fallisce, alcune regole di abduzione
consentono di unificare costanti che sono differenti ma che
sono argomenti dello stesso predicato
Performance di FALCON a TREC-9
• 79% risposte corrette
• Il secondo miglior sistema intorno al 55%
• I moduli di abduzione e espansione semantica hanno
avuto un ruolo determinante nel 25% dei casi
• I progettisti di FALCON sostengono che il ruolo di una
“open-domain linguistic ontology such as WordNet” è
stato determinante
Per concludere (sulle tecniche di
elaborazione dei testi)
• L’uso di tecniche di AI-intensive è fortemente crescente nei
sistemi di accesso a informazioni testuali
• Comunità Europea e DARPA spingono progetti orientati al
reperimento, manipolazione, presentazione di contenuti sulla
rete (e-content, Semantic web., Open-domain question
answering..)
• La disponibilità di “open-domain” Ontologies e linguaggi di
formattazione “intermedia” di documenti (XML etc.) potrà
avere un forte impatto sulle prestazioni dei sistemi di DC/IE/QA