Text Processing
Question Answering
Basi di Dati Multimediali - Giugno 2005
Marco Ernandes: [email protected]
Motivazioni
L’accesso alle informazioni diventa sempre più
complesso quando:



Information Overload: la collezione di dati diventa sempre
più grande, e la velocità con cui cresce è superiore al
miglioramento della tecnologia di accesso.
L’informazione è spesso duplicata.
L’informazione è spesso falsa o non esatta.
 Accesso tradizionale:


Information Retrieval (IR)
Information Extraction (IE)
Il Question Answering (QA) si pone come
approccio alternativo.
2
Motivazioni
 Gli utenti vogliono porre domande.
 Gli utenti vogliono delle risposte concise, senza dover
leggere liste di documenti.
 Circa il 15% delle query nei motori di ricerca è formulato
come domanda.
 Grande interesse industriale & commerciale.



ES: “How much money does Pirelli invest on research?”
Google non trova un buon documento-risposta
Neanche con: “money Pirelli invest research”
3
QA vs. IR
L’Information Retrieval sostituisce il concetto di
“informazione” con quello di “documento”.



Risponde con documenti completi
Ordina i documenti per rilevanza
Sfrutta metodi statistici considerando la frequenza
delle parole nella query, nel documento e nella
collezione.
Limiti:


Risponde alle domande in modo indiretto
Non cerca di interpretare il “senso” della query
dell’utente o dei documenti (NLP assente).
4
QA vs. IE
L’Information Extraction si prefigge l’obiettivo di
riempire dei Template predefiniti.
I topic di interesse sono conosciuti in anticipo,
mentre il Question Answering è online.
I template sono creati “a mano” da esperti.
I Template non sono molto portabili da un
dominio all’altro.
Il QA si prefigge di ridurre l’intervento umano.
5
Relazioni tra QA e IR/IE
QA deriva da IR in quanto:



Può essere visto come un “Passage Retrieval”
portato al limite.
E’ stato creato dalla comunità di Information Retrieval
Si appoggia su sistemi di IR per la gestione della
base documentale.
QA deriva da IE in quanto:


Le domande possono essere viste come versioni
semplificate, ma non pre-definite, di Template.
Le risposte vengono normalmente “estratte” dal testo.
Sia il QA che l’IE si discostano dal full-text
understanding: non c’è comprensione, ma
localizzazione e riorganizzazione dell’info.
6
QA: gli obiettivi
 Rispondere direttamente alle domande dell’utente,
usando una frase compiuta in linguaggio naturale.
 Rispondere in modo preciso e conciso, così da
minimizzare il tempo impiegato per “trovare” la risposta.
 Rispondere motivando la risposta: fornendo il contesto
nel quale si è identificata la risposta, oppure fornendo
link ai documenti in cui è stata trovata.
 Rispondere fornendo un grado di confidenza:

Chi è l’attuale Cancelliere tedesco?: Gherard Schroeder al 70%
7
Riassumendo: cos’è il QA?
 Input: domande espresse in linguaggio naturale,
non queries.
 Output: risposte in linguaggio naturale, non
documenti.
 Attenzione particolare su fact-based (factoids)
questions:





Quanto è alto il Monte Everest?
Quando ha scoperto l’America Cristoforo Colombo?
Con chi era sposato il Conte di Cavour?
Quante specie di ragni velenosi ci sono in Italia?
Elenca 4 nazioni che producono diamanti sintetici.
8
Lo stato dell’arte
 Alcuni sistemi di QA sono già prodotti commerciali.
 AskJeeves: http://www.askjeeves.com/



Database di domande risposte “a mano”
Se una domanda è sconosciuta cerca nel Web
Non fa vero Question Answering: prestazioni scarse
AnswerBus: http://www.answerbus.com/
 Language Computer: http://www.languagecomputer.com
AskMSR (Microsoft):

Ha dato buoni risultati usando la semplice: inversione
interrogativaaffermativa (es: Dove si trova il Taj Mahal?  Il
Taj Mahal si trova …)
9
Lo stato dell’arte
Esempi di “buone” risposte:


Who won Wimbledon in 1953?  “In 1953, Little Mo won
all four Slams.”
“How many people live in Paris?”  “The population of
Paris is 2152423 people.”
Esempi di cattive risposte:






Where do lobsters like to live?  ”On a Canadian airline”
Where do hyenas live?  “In the back of pick-up trucks”
Where are zebras most likely found?  “In the dictionary”
Why can’t ostriches fly?  “Because of American
economic sanctions”
What’s the population of Maryland?  “Three”
What is the height of a typical Giraffe?  AskJeeves:
“Michael Jordan is a typical giraffe”
10
Un po’ di storia del QA
 Sistemi di dialogo e QA sono nati fin dagli anni ’60!


Nel 1965 se ne contavano già una quindicina
BASEBALL (1961): primo sistema, front end NL per accesso a
database

SHRDLU (1972): dialog&action nel mondo dei blocchi

BORIS(1972): story comprehension


LUNAR(1973): front end NL per accesso a informazione
geologica per le missioni Apollo
JUPITER(MIT-2000): QA vocale telefonico sul meteo
 Sistemi di QA open-domain sono recenti:

MURAX (1993): risposte da enciclopedia
11
Storia del QA: SHRDLU (es.)
Person
Computer
Person
Computer
Person
PICK A BIG RED UP BLOCK.
OK. (does it)
GRASP THE PYRAMID.
I DON'T UNDERSTAND WHICH PYRAMID YOU MEAN.
FIND A BLOCK WHICH IS TALLER THAN THE ONE YOU ARE
HOLDING AND PUT IT INTO THE BOX.
Computer
BY "IT", I ASSUME YOU MEAN THE BLOCK WHICH IS TALLER
THAN THE ONE I AM HOLDING.
Computer
OK. (does it)
Person
WHAT DOES THE BOX CONTAIN?
Computer
THE BLUE PYRAMID AND THE BLUE BLOCK.
Person
WHAT IS THE PYRAMID SUPPORTED BY?
Computer
THE BOX.
Person
HOW MANY BLOCKS ARE NOT IN THE BOX?
Computer
FOUR OF THEM.
Person
IS AT LEAST ONE OF THEM NARROWER THAN THE ONE WHICH I
TOLD YOU TO PICK UP?
Computer
YES, THE RED CUBE.
Person
IS IT SUPPORTED?
Computer
YES, BY THE TABLE.
Person
CAN THE TABLE PICK UP BLOCKS?
12
Computer
NO
TREC: la competizione
Text REtrieval Conference



Serie di workshops sull’Information Retrieval
Iniziato nel 1992, sponsor NIST (National Institute of
Standard and Technology), DARPA
Il QA è uno dei 6 track (ora 7) della conferenza, iniziato
con il TREC-8 (1999), 20 partecipanti
Il TREC fornisce una collezione di articoli come
base testuale (> 1milione nel 2002, 3Gb) e poi i
team competono sulle stesse domande.


Newswire delle agenzie di stampa e articoli giornalistici
I team inseriscono proprie basi di conoscenza addizionali
13
TREC: le domande
 Domande Open-Domain, negli anni difficoltà cresciuta
 Estratte dai log-files di motori di ricerca (MSNSearch,
Excite), motori QA (AskJeeves), enciclopedie (Encarta).
 Factoid questions: Who, When, Where, Why, …



Who invented the telephone?
In what year was the telephone invented?
Why did President Clinton risk impeachement?
 List Questions:

Name 4 people from Massachussets who were candidates for
vice-president.
 Definition Questions (What is):

What is epilepsy?
14
TREC: valutazione
Prime 3 edizioni, da TREC-8 (’99) a
TREC-10 (’01):




2 tipologie di risposte: 50-byte e 250-byte passage
La risposta doveva essere “trovata” all’interno del
passage da due arbitri umani (valutazione molto
soggettiva)
200, 689 e 500 domande: per ogni domanda
potevano essere date 5 risposte, ordinate.
Punteggio: Mean Reciprocal Rank (MRR)
• MRR = 1/pos(correct_answer).
15
TREC: valutazione
Dal TREC-11 (’02):





Il sistema deve fornire solo 1 risposta
La risposta deve essere corredata di uno score di
confidenza
L’output deve essere NO_ANSWER se la collezione usata
non contiene la risposta.
La risposta di lunghezza variabile, ma contenente solo
l’informazione corretta e formulata in modo sintatticamente
coerente (la correttezza di una risposta rimane comunque
un’opinione degli arbitri). Nel 2003 è stato introdotto il
Passage Task.
ES: What is the longest river in the USA?
 E’ errata: “2.348 miles long, the Mississipi River is the
longest river in the US”.
16
TREC 2003: risultati
FACTOID QUESTIONS
LIST QUESTIONS
DEFINITIONS
17
QA: architettura generale
 Tutti i sistemi che partecipano al TREC
possiedono almeno 4 moduli fondamentali:
1) Question Analysis: cerca di capire la natura della
domanda
2) Document Retrieval: cerca di ottenere dei
documenti rilevanti (quindi c’è anche bisogno di una
repository di documenti)
3) Document Processing: analizza il contenuto dei
documenti
4) Answer Extraction: cerca di ottenere la risposta a
partire dai documenti selezionati
18
QA: architettura generale 2
Estrarre e fare il ranking delle porzioni
dei documenti più promettenti.
Question Semantics
Q
Question
Analysis
Keywords
Catturare la semantica di una
domanda. Formulare la miglior
query possibile.
Document
Processing
Document
Retrieval
Passages
Answer
Extraction
A
Estrarre e fare il ranking delle
risposte candidate
19
QA: architettura generale 3
Question Parsing
Answer Type
Question Classification
Query Formulation
Info-Retrieval
Document processing
Answer Extraction
Answer Selection
Answer Construction
Generazione albero sintattico: ai nodi si trovano i
termini e il loro valore grammaticale (aggettivo,
sost,…).
Stabilire il tipo di domanda: nominale (where),
numerica (how many, how tall…), temporale (when), …
Trasforma la domanda in una o varie keywordquery da inviare al sistema di IR.
Modulo di IE: seleziona le porzioni utili dei docs
(passaggi), estrae i NE e ne definisce le relazioni.
Estrae le risposte candidate dai documenti e dalle
strutture prodotte dal modulo di IE.
Sceglie le risposte migliori da dare in uscita al sistema
e ne fa il ranking (eventualmente confidenza).
20
QA: question analysis
E’ una fase di grande importanza: determina il
successo o meno del sistema! E’ la causa della
maggior parte di errori irreversibili.
Costruzione di una nuova
question representation
Q
Question
parsing
Question
semantic
representation
Question Classification:
Riconoscimento Answer Type
AT category
Query Reformulation &
Expansion: Keyword selection
Keywords
21
QA: question analysis
Question Classification - 2 approcci:


Knowledge engineering: AT detection
determinata da regole e da database lessicali
Machine Trainable: apprendimento da esempi
(es: SVM sul parse tree della domanda).
22
QA: AT detection
 Per identificare la categoria semantica di una
domanda si cercano le Question Stems
Question
Question stem Answer type
What was the name of Titanic’s captain?
What
Person
What U.S. Government agency registers
trademarks?
What
Organization
What is the capital of Kosovo?
What
City
How much does one ton of cement cost?
How much
Quantity
 Altre question stems: Who, Which, Name, How hot...
 Altri answer type: Country, Number, Product...
23
QA: AT detection
 Capire l’answer type a partire dalle Question
Stems può essere immediato:



Why  REASON
When  DATE
Who  PERSON
Alle volte la question stem invece è ambigua:

Per esempio:
• What was the name of Titanic’s captain ? (PERSON)
• What U.S. Government agency registers trademarks? (ORG)
• What is the capital of Kosovo? (CITY)


Soluzione: seleziona un’ altra parola della domanda
(AT words) che aiuta a disambiguare l’answer type
Per esempio:
• captain, agency, capital
24
QA: AT detection
 Per collegare un termine della domanda ad un answer
type si definisce una tassonomia di answer type.
 Quando il termine non si trova nella tassonomia AT si
usa una tassonomia di concetti (generale): WordNet.
 migliaia di
concetti per
l’inglese
 C’è anche
per l’Italiano.
 Realizzato a
mano!
25
QA: AT taxonomy
La tassonomia di AT di WebClopedia
26
QA: AT detection
Algoritmo di Answer Type Detection:



Rimuovi dalla domanda le parole “content-free”
(es:“name”)
Delle rimanenti seleziona la parola più riccamente
connessa nella question representation (derivante
dall’albero sintattico)
A partire da questa parola risali la tassonomia (WordNet)
fino a che non trovi un’Answer Type
 ES: What is the name of the French oceanographer who
owned Calypso?
PERSON
NAME
OCEANOGR.
FRENCH
OWNED
CALIPSO
scientist,
man of science
chemist
researcher
oceanographer
27
QA: AT detection
 Valutazione Tassonomia AT:


Test fatto variando in modo automatico la copertura (in numero
di concetti usati) WordNet della tassonomia AT.
800 domande usate
Copertura della gerarchia
Precision 50-byte answer
0%
0.296
3%
0.404
10%
0.437
25%
0.451
50%
0.461
 E’ utile possedere una vasta gerarchia di AT, ma oltre
un certo limite (300/500 concetti) il contributo è minimo.
28
QA: Query Formulation 1
 Le domande devono essere approssimate con una
bag of word di parole con un lessico rilevante
 Tipico algoritmo di scelta del lessico:
1.
2.
3.
4.
5.
6.
7.

Seleziona le non-stopwords tra apici (nella dom.): “Promessi Sposi”
Seleziona i Named-Entities: “Alessandro Manzoni”, Peugeot
Seleziona i nomi più insoliti
Seleziona i modifiers (aggettivi) dei nomi insoliti
Seleziona tutti gli altri nomi (con modifiers)
Seleziona tutti i verbi
Seleziona la AT word (evitata negli step precedenti)
ES:
 What researcher discovered the vaccine against Hepatitis-B?
Hepatitis-B, vaccine, discover, researcher
 What is the name of the French oceanographer who owned
Calypso? Calypso, French, own, oceanographer
 What U.S. government agency registers trademarks? U.S.,
government, trademarks, register, agency
 What is the capital of Kosovo? Kosovo, capital
29
QA: Query Formulation 2
 Se il numero di keyword non supera il limite (es: 10
per Google)  QUERY EXPANSION
 La query può essere espansa in due modi:


Inserendo derivazioni (forme flesse di un certo lemma)
Inserendo sinonimi
 La query viene quindi gestita con catene AND OR:
 ES:

What researcher discovered the vaccine against Hepatitis-B?
(Hepatitis-B OR Hepatitis) AND (vaccine OR vaccines OR
cure OR cures) AND (discover OR discovered OR discovers)
AND (researcher OR scientist)
30
QA: Query Formulation 3
 Si può rispondere con successo ad una porzione di
domande in un modo estremamente semplice:



Riformulare la domanda in modo affermativo (lavorando
sull’albero sintattico).
Mettere l’affermazione ottenuta tra apici
Considerare come potenziali risposte tutto ciò che nei
documenti si trova a destra (o in certi casi a sinistra)
dell’affermazione.  Approccio di AskMSR
 ES: Where is the Louvre Museum located?
 “The Louvre Museum is located”
The Louvre Museum is
located in Paris Cedex n° 01
… and the Louvre Museum is
located next to the river
31
QA: Query Formulation 4
 Il modulo di query formulation può dialogare con
quello di Information Retrieval: Keyword Adjustment
1. Nella prima iterazione usa un numero “intermedio” di
keywords (6 keyword è una regola del pollice efficace)
2. Se il numero di hit (documenti ottenuti) è sotto una
certa soglia allora la query è troppo selettiva: riduci la
query di una keyword (l’ultima)
3. Se il numero di hit è sopra una certa soglia allora
inserisci una keyword per rendere la query più selettiva.
4. Se con tutte le keywords la query rimane poco
selettiva: combina le keywords usando gli apici
32
QA: IR and Document Processing
 L’approccio tipicamente usato è quello del Passage
Retrieval: si cerca di estrarre le porzioni di documenti
che con alta probabilità contengano la risposta.
1. Un sistema di IR ritorna la lista di docs associati alla query.
2. Un sistema di PR seleziona le porzioni interessanti.
3. Si fa lo scoring dei passaggi ottenuti
 I sistemi di Web-Based QA usano generalmente le
snippets di Google per risolvere i punti 1 e 2.
33
QA: Passage Ranking
 Da un passaggio (o snippet) vengono estratte delle finestre usando
le keywords della query
 Per esempio, con le keywords: {k1, k2, k3, k4}, otteniamo un passage
in cui k1 e k2 sono presenti 2 volte, k3 una volta, e k4 è assente. Si
definiscono le finestre della figura sotto.
 Lo scoring definitivo lo si calcola
sulla base di alcune metriche:



Same Word Sequence Score:
# di parole della domanda
ritrovate nello stesso ordine
all’interno della finestra
Missing Keyword Score:
# di keyword mancanti
all’interno della finestra
Distance Score: # di parole
intercorrenti tra le keyword
più distanti nella finestra
Window 1
Window 2
k1
k2
k2
k1
k2
k2
k3
k1
Window 4
Window 3
k1
k2
k3
k1
k2
k1
k3
k1
k2
k2
k1
34
k3
QA: Answer Extraction 1
Si tratta di un modulo che riceve in input:


delle porzioni rilevanti dei documenti
un answer type da ricercare in questi estratti
Step necessari:



Analisi IE del passage in modo da ottenere tutte le Named
Entities (la maggior parte delle domande sono relative a NE).
Selezione delle NE della categoria corretta: Candidate Answers
Ranking delle risposte candidate.
 Lo score delle risposte candidate può essere ottenuto:


Grazie ad un sistema addestrato
Con delle euristiche legate alla Candidate-Query Distance
35
QA: Answer Extraction 2
 Name the first private citizen to fly in space.


Answer type: Person
Text passage: “Among them was Christa McAuliffe, the
first private citizen to fly in space. Karen Allen, best known for
her starring role in “Raiders of the Lost Ark”, plays McAuliffe.
Brian Kerwin is featured as shuttle pilot Mike Smith...”
 Miglior risposta candidata: Christa McAuliffe
 Conferma intuitiva: è infatti la NE “person” più
vicina ai i question-terms della domanda
(l’unica contenuta nella stessa frase dove si
trovano tutti i question terms).
36
QA: Answer Extraction 3
 Approccio Machine-Learning.

Si estraggono delle feature particolari relative al passage e
alla parola candidata, ad esempio:





# question terms nel passage
# question terms nella stessa frase della candidata
# question terms, fuori dalla frase, ma vicine (es: 3 parole)
# question terms che si trovano nell’ordine della domanda
distanza media tra la candidata e le question terms

Si usa una tecnica di machine-learning (un Percettrone
funziona già bene) per associare un peso a ciascuna di
quelle features e attribuire uno score ad ogni candidata.

Si addestra il sistema su un set di answer passage con le
risposte corrette poste come output desiderato 1 e le altre
0 (oppure -1).
37
QA: Answer Extraction 4
 Pattern Learning (WebClopedia ’02)
 Webclopedia: 6 Question Types


BIRTHDATE, LOCATION, INVENTOR
DISCOVERER, DEFINITION, WHY-FAMOUS
 WebClopedia costruisce automaticamente dei pattern
osservando le frequenze dei contesti delle risposte.
 ES: BIRTHDATE table:
•
•
•
•
•
•
•
1.0 <NAME> ( <ANSWER> - )
0.85 <NAME> was born on <ANSWER>,
0.6 <NAME> was born in <ANSWER>
0.59 <NAME> was born <ANSWER>
0.53 <ANSWER> <NAME> was born
0.50 - <NAME> ( <ANSWER>
0.36 <NAME> ( <ANSWER> -
38
QA: Answer Extraction 5
 Approccio Candidate-Query Distance:

Funziona bene la mean square distance

dist ( wk , Q, Pi ) 
# termsQ
t=0
dist ( wk , wQt , Pi ) 2
 Dove: dist ( wk , wQ , Pi ) è il minimo numero di
parole che separa wk da wQt
t
Among them was Christa McAuliffe, the first private citizen to fly in space
3
4
5
7
39
QA: Answer Construction
 Enumera tutte le candidate per N-grams (N=1,2,3)
 Associa un peso a ciascun N-gram = # occ.* score
 Example: “Who created the character of Scrooge?”


Dickens: 117, Charles Dickens: 75, Disney: 72,
Carl Banks: 54, Uncle: 31, Mr Charles: 10
 Rimuovi gli overlap
Scores
Charles Dickens
75
Dickens
117
10
merging,
rimuovi n-grams vecchi
Mr Charles
Score 202
Mr Charles Dickens
combina il miglior n-gram
N-Grams
N-Grams
ripeti finchè ci sono overlap
40