Question
Answering
What
is
Ques+on
Answering?
Dan
Jurafsky
Ques%on
Answering
One
of
the
oldest
NLP
tasks
(punched
card
systems
in
1961)
Simmons,
Klein,
McConlogue.
1964.
Indexing
and
!"#$%&'( )&*#'%+,-.'$/#0$( Dependency
Logic
for
Answering
English
Ques+ons.
American
Documenta+on
15:30,
196-204
What do worms eat? Worms eat grass Horses with worms eat grass
worms horses
worms
eat with eat
eat
grass worms grass
what
Birds eat worms Grass is eaten by worms
birds worms
eat eat
2
worms grass
Dan
Jurafsky
Ques%on
Answering:
IBMs
Watson
Won
Jeopardy
on
February
16,
2011!
WILLIAM WILKINSONS
AN ACCOUNT OF THE PRINCIPALITIES OF
WALLACHIA AND MOLDOVIA Bram
Stoker
INSPIRED THIS AUTHORS
MOST FAMOUS NOVEL
3
Dan
Jurafsky
Apples
Siri
4
Dan
Jurafsky
Wolfram
Alpha
5
Dan
Jurafsky
Types
of
Ques%ons
in
Modern
Systems
Factoid
ques+ons
Who
wrote
The
Universal
Declara4on
of
Human
Rights?
How
many
calories
are
there
in
two
slices
of
apple
pie?
What
is
the
average
age
of
the
onset
of
au4sm?
Where
is
Apple
Computer
based?
Complex
(narra+ve)
ques+ons:
In
children
with
an
acute
febrile
illness,
what
is
the
ecacy
of
acetaminophen
in
reducing
fever?
What
do
scholars
think
about
Jeersons
posi4on
on
dealing
with
pirates?
6
Dan
Jurafsky
Commercial
systems:
mainly
factoid
ques%ons
Where
is
the
Louvre
Museum
located?
In
Paris,
France
Whats
the
abbrevia+on
for
limited
L.P.
partnership?
What
are
the
names
of
Odins
ravens?
Huginn
and
Muninn
What
currency
is
used
in
China?
The
yuan
What
kind
of
nuts
are
used
in
marzipan?
almonds
What
instrument
does
Max
Roach
play?
drums
What
is
the
telephone
number
for
Stanford
650-723-2300
University?
Dan
Jurafsky
Paradigms
for
QA
IR-based
approaches
TREC;
IBM
Watson;
Google
Knowledge-based
and
Hybrid
approaches
IBM
Watson;
Apple
Siri;
Wolfram
Alpha;
True
Knowledge
Evi
8
Dan
Jurafsky
Many
ques%ons
can
already
be
answered
by
web
search
a
9
Dan
Jurafsky
IR-based
Ques%on
Answering
a
10
Dan
Jurafsky
IR-based
Factoid
QA
Document
DocumentDocument
Document
Document Document
Indexing Answer
Passage
Question Retrieval
Processing Docume
Docume
Query Document nt
Docume
nt
Docume
nt
Passage Answer
Docume
Formulation Retrieval Relevant
nt
nt Retrieval passages Processing
Question Docs
Answer Type
Detection
11
Dan
Jurafsky
IR-based
Factoid
QA
QUESTION
PROCESSING
Detect
ques+on
type,
answer
type,
focus,
rela+ons
Formulate
queries
to
send
to
a
search
engine
PASSAGE
RETRIEVAL
Retrieve
ranked
documents
Break
into
suitable
passages
and
rerank
ANSWER
PROCESSING
Extract
candidate
answers
Rank
candidates
using
evidence
from
the
text
and
external
sources
Dan
Jurafsky
Knowledge-based
approaches
(Siri)
Build
a
seman+c
representa+on
of
the
query
Times,
dates,
loca+ons,
en++es,
numeric
quan++es
Map
from
this
seman+cs
to
query
structured
data
or
resources
Geospa+al
databases
Ontologies
(Wikipedia
infoboxes,
dbPedia,
WordNet,
Yago)
Restaurant
review
sources
and
reserva+on
services
Scien+c
databases
13
Dan
Jurafsky
Hybrid
approaches
(IBM
Watson)
Build
a
shallow
seman+c
representa+on
of
the
query
Generate
answer
candidates
using
IR
methods
Augmented
with
ontologies
and
semi-structured
data
Score
each
candidate
using
richer
knowledge
sources
Geospa+al
databases
Temporal
reasoning
Taxonomical
classica+on
14
Question
Answering
What
is
Ques+on
Answering?
Question
Answering
Answer
Types
and
Query
Formula+on
Dan
Jurafsky
Factoid
Q/A
Document
DocumentDocument
Document
Document Document
Indexing Answer
Passage
Question Retrieval
Processing Docume
Docume
Query Document nt
Docume
nt
Docume
nt
Passage Answer
Docume
Formulation Retrieval Relevant
nt
nt Retrieval passages Processing
Question Docs
Answer Type
Detection
17
Dan
Jurafsky
Ques%on
Processing
Things
to
extract
from
the
ques%on
Answer
Type
Detec+on
Decide
the
named
en%ty
type
(person,
place)
of
the
answer
Query
Formula+on
Choose
query
keywords
for
the
IR
system
Ques+on
Type
classica+on
Is
this
a
deni+on
ques+on,
a
math
ques+on,
a
list
ques+on?
Focus
Detec+on
Find
the
ques+on
words
that
are
replaced
by
the
answer
Rela+on
Extrac+on
18
Find
rela+ons
between
en++es
in
the
ques+on
Dan
Jurafsky
Question Processing
Theyre the two states you could be reentering if youre crossing
Floridas northern border
Answer
Type:
US
state
Query:
two
states,
border,
Florida,
north
Focus:
the
two
states
Rela+ons:
borders(Florida,
?x,
north)
19
Dan
Jurafsky
Answer
Type
Detec%on:
Named
En%%es
Who
founded
Virgin
Airlines?
PERSON
What
Canadian
city
has
the
largest
popula4on?
CITY.
Dan
Jurafsky
Answer
Type
Taxonomy
Xin
Li,
Dan
Roth.
2002.
Learning
Ques+on
Classiers.
COLING'02
6
coarse
classes
ABBEVIATION,
ENTITY,
DESCRIPTION,
HUMAN,
LOCATION,
NUMERIC
50
ner
classes
LOCATION:
city,
country,
mountain
HUMAN:
group,
individual,
+tle,
descrip+on
ENTITY:
animal,
body,
color,
currency
21
Dan
Jurafsky
Part
of
Li
&
Roths
Answer
Type
Taxonomy
country city state
reason
expression
LOCATION
definition
abbreviation
ABBREVIATION
DESCRIPTION
individual
food ENTITY HUMAN title
currency NUMERIC
group
animal date money
percent
distance size 22
Dan
Jurafsky
Answer
Types
23
Dan
Jurafsky
More
Answer
Types
24
Dan
Jurafsky
Answer
types
in
Jeopardy
Ferrucci
et
al.
2010.
Building
Watson:
An
Overview
of
the
DeepQA
Project.
AI
Magazine.
Fall
2010.
59-79.
2500
answer
types
in
20,000
Jeopardy
ques+on
sample
The
most
frequent
200
answer
types
cover
<
50%
of
data
The
40
most
frequent
Jeopardy
answer
types
he,
country,
city,
man,
lm,
state,
she,
author,
group,
here,
company,
president,
capital,
star,
novel,
character,
woman,
river,
island,
king,
song,
part,
series,
sport,
singer,
actor,
play,
team,
show,
actress,
animal,
presiden+al,
composer,
musical,
na+on,
book,
+tle,
leader,
game
25
Dan
Jurafsky
Answer
Type
Detec%on
Hand-wrioen
rules
Machine
Learning
Hybrids
Dan
Jurafsky
Answer
Type
Detec%on
Regular
expression-based
rules
can
get
some
cases:
Who
{is|was|are|were}
PERSON
PERSON
(YEAR
YEAR)
Other
rules
use
the
ques%on
headword:
(the
headword
of
the
rst
noun
phrase
ater
the
wh-word)
Which
city
in
China
has
the
largest
number
of
foreign
nancial
companies?
What
is
the
state
ower
of
California?
Dan
Jurafsky
Answer
Type
Detec%on
Most
oten,
we
treat
the
problem
as
machine
learning
classica+on
Dene
a
taxonomy
of
ques+on
types
Annotate
training
data
for
each
ques+on
type
Train
classiers
for
each
ques+on
class
using
a
rich
set
of
features.
features
include
those
hand-wrioen
rules!
28
Dan
Jurafsky
Features
for
Answer
Type
Detec%on
Ques+on
words
and
phrases
Part-of-speech
tags
Parse
features
(headwords)
Named
En++es
Seman+cally
related
words
29
Dan
Jurafsky
Factoid
Q/A
Document
DocumentDocument
Document
Document Document
Indexing Answer
Passage
Question Retrieval
Processing Docume
Docume
Query Document nt
Docume
nt
Docume
nt
Passage Answer
Docume
Formulation Retrieval Relevant
nt
nt Retrieval passages Processing
Question Docs
Answer Type
Detection
30
Dan
Jurafsky
Keyword
Selec%on
Algorithm
Dan
Moldovan,
Sanda
Harabagiu,
Marius
Paca,
Rada
Mihalcea,
Richard
Goodrum,
Roxana
Girju
and
Vasile
Rus.
1999.
Proceedings
of
TREC-8.
1.
Select
all
non-stop
words
in
quota+ons
2.
Select
all
NNP
words
in
recognized
named
en++es
3.
Select
all
complex
nominals
with
their
adjec+val
modiers
4.
Select
all
other
complex
nominals
5.
Select
all
nouns
with
their
adjec+val
modiers
6.
Select
all
other
nouns
7.
Select
all
verbs
8.
Select
all
adverbs
9.
Select
the
QFW
word
(skipped
in
all
previous
steps)
10.
Select
all
other
words
Dan
Jurafsky
Choosing keywords from the query
Slide
from
Mihai
Surdeanu
Who coined the term cyberspace in his novel Neuromancer?
1 1
4 4
7
cyberspace/1 Neuromancer/1 term/4 novel/4 coined/7
32
Question
Answering
Answer
Types
and
Query
Formula+on
Question
Answering
Passage
Retrieval
and
Answer
Extrac+on
Dan
Jurafsky
Factoid
Q/A
Document
DocumentDocument
Document
Document Document
Indexing Answer
Passage
Question Retrieval
Processing Docume
Docume
Query Document nt
Docume
nt
Docume
nt
Passage Answer
Docume
Formulation Retrieval Relevant
nt
nt Retrieval passages Processing
Question Docs
Answer Type
Detection
35
Dan
Jurafsky
Passage
Retrieval
Step
1:
IR
engine
retrieves
documents
using
query
terms
Step
2:
Segment
the
documents
into
shorter
units
something
like
paragraphs
Step
3:
Passage
ranking
Use
answer
type
to
help
rerank
passages
36
Dan
Jurafsky
Features
for
Passage
Ranking
Either
in
rule-based
classiers
or
with
supervised
machine
learning
Number
of
Named
En++es
of
the
right
type
in
passage
Number
of
query
words
in
passage
Number
of
ques+on
N-grams
also
in
passage
Proximity
of
query
keywords
to
each
other
in
passage
Longest
sequence
of
ques+on
words
Rank
of
the
document
containing
passage
Dan
Jurafsky
Factoid
Q/A
Document
DocumentDocument
Document
Document Document
Indexing Answer
Passage
Question Retrieval
Processing Docume
Docume
Query Document nt
Docume
nt
Docume
nt
Passage Answer
Docume
Formulation Retrieval Relevant
nt
nt Retrieval passages Processing
Question Docs
Answer Type
Detection
38
Dan
Jurafsky
Answer
Extrac%on
Run
an
answer-type
named-en+ty
tagger
on
the
passages
Each
answer
type
requires
a
named-en+ty
tagger
that
detects
it
If
answer
type
is
CITY,
tagger
has
to
tag
CITY
Can
be
full
NER,
simple
regular
expressions,
or
hybrid
Return
the
string
with
the
right
type:
Who is the prime minister of India (PERSON)
Manmohan Singh, Prime Minister of India, had told
left leaders that the deal would not be renegotiated.!
How tall is Mt. Everest? (LENGTH)
The official height of Mount Everest is 29035 feet!
Dan
Jurafsky
Ranking
Candidate
Answers
But
what
if
there
are
mul+ple
candidate
answers!
Q: Who was Queen Victorias second son?!
Answer
Type:
Person
Passage:
The
Marie
biscuit
is
named
ater
Marie
Alexandrovna,
the
daughter
of
Czar
Alexander
II
of
Russia
and
wife
of
Alfred,
the
second
son
of
Queen
Victoria
and
Prince
Albert
Dan
Jurafsky
Ranking
Candidate
Answers
But
what
if
there
are
mul+ple
candidate
answers!
Q: Who was Queen Victorias second son?!
Answer
Type:
Person
Passage:
The
Marie
biscuit
is
named
ater
Marie
Alexandrovna,
the
daughter
of
Czar
Alexander
II
of
Russia
and
wife
of
Alfred,
the
second
son
of
Queen
Victoria
and
Prince
Albert
Dan
Jurafsky
Use
machine
learning:
Features
for
ranking
candidate
answers
Answer
type
match:
Candidate
contains
a
phrase
with
the
correct
answer
type.
PaZern
match:
Regular
expression
paoern
matches
the
candidate.
Ques%on
keywords:
#
of
ques+on
keywords
in
the
candidate.
Keyword
distance:
Distance
in
words
between
the
candidate
and
query
keywords
Novelty
factor:
A
word
in
the
candidate
is
not
in
the
query.
Apposi%on
features:
The
candidate
is
an
apposi+ve
to
ques+on
terms
Punctua%on
loca%on:
The
candidate
is
immediately
followed
by
a
comma,
period,
quota+on
marks,
semicolon,
or
exclama+on
mark.
Sequences
of
ques%on
terms:
The
length
of
the
longest
sequence
of
ques+on
terms
that
occurs
in
the
candidate
answer.
Dan
Jurafsky
Candidate
Answer
scoring
in
IBM
Watson
Each
candidate
answer
gets
scores
from
>50
components
(from
unstructured
text,
semi-structured
text,
triple
stores)
logical
form
(parse)
match
between
ques+on
and
candidate
passage
source
reliability
geospa+al
loca+on
California
is
southwest
of
Montana
temporal
rela+onships
43
taxonomic
classica+on
Dan
Jurafsky
Common
Evalua%on
Metrics
1. Accuracy
(does
answer
match
gold-labeled
answer?)
2. Mean
Reciprocal
Rank
For
each
query
return
a
ranked
list
of
M
candidate
answers.
Query
score
is
1/Rank
of
the
rst
correct
answer
If
rst
answer
is
correct:
1
N
1
else
if
second
answer
is
correct:
! rank
else
if
third
answer
is
correct:
,
etc.
i
i=1 MRR =
Score
is
0
if
none
of
the
M
answers
are
correct
N
Take
the
mean
over
all
N
queries
44
Question
Answering
Passage
Retrieval
and
Answer
Extrac+on
Question
Answering
Using
Knowledge
in
QA
Dan
Jurafsky
Rela%on
Extrac%on
Answers:
Databases
of
Rela+ons
born-in(Emma
Goldman,
June
27
1869)
author-of(Cao
Xue
Qin,
Dream
of
the
Red
Chamber)
Draw
from
Wikipedia
infoboxes,
DBpedia,
FreeBase,
etc.
Ques+ons:
Extrac+ng
Rela+ons
in
Ques+ons
Whose
granddaughter
starred
in
E.T.?
(acted-in ?x E.T.)!
47
(granddaughter-of ?x ?y)!
Dan
Jurafsky
Temporal
Reasoning
Rela+on
databases
(and
obituaries,
biographical
dic+onaries,
etc.)
IBM
Watson
In
1594
he
took
a
job
as
a
tax
collector
in
Andalusia
Candidates:
Thoreau
is
a
bad
answer
(born
in
1817)
Cervantes
is
possible
(was
alive
in
1594)
48
Dan
Jurafsky
Geospa%al
knowledge
(containment,
direc%onality,
borders)
Beijing
is
a
good
answer
for
Asian
city
California
is
southwest
of
Montana
geonames.org:
49
Dan
Jurafsky
Context
and
Conversa%on
in
Virtual
Assistants
like
Siri
Coreference
helps
resolve
ambigui+es
U:
Book
a
table
at
Il
Fornaio
at
7:00
with
my
mom
U:
Also
send
her
an
email
reminder
Clarica+on
ques+ons:
U:
Chicago
pizza
S:
Did
you
mean
pizza
restaurants
in
Chicago
or
Chicago-style
pizza?
50
Question
Answering
Using
Knowledge
in
QA
