Question Answering What  is  Ques?on   Answering?   Dan  Jurafsky   2   Ques?on  Answering   What do worms eat? worms eat what worms eat grass Worms eat grass worms eat grass Grass is eaten by worms birds eat worms Birds eat worms horses eat grass Horses with worms eat grass with worms !"#$%&'( )&*#'%+,-.'$/#0$( One  of  the  oldest  NLP  tasks  (punched  card  systems  in  1961)   Simmons,  Klein,  McConlogue.  1964.  Indexing  and   Dependency  Logic  for  Answering  English  Ques⬬ns.   American  Documenta?on  15:30,  196-­‐204   Dan  Jurafsky   Ques?on  Answering:  IBM’s  Watson   •  Won  Jeopardy  on  February  16,  2011!   3   WILLIAM WILKINSON’S “AN ACCOUNT OF THE PRINCIPALITIES OF WALLACHIA AND MOLDOVIA” INSPIRED THIS AUTHOR’S MOST FAMOUS NOVEL Bram  Stoker   Dan  Jurafsky   Apple’s  Siri   4   Dan  Jurafsky   Wolfram  Alpha   5   Dan  Jurafsky   6   Types  of  Ques?ons  in  Modern  Systems   •  Factoid  ques?ons   •  Who  wrote  “The  Universal  Declara?on  of  Human  Rights”?   •  How  many  calories  are  there  in  two  slices  of  apple  pie?   •  What  is  the  average  age  of  the  onset  of  au?sm?   •  Where  is  Apple  Computer  based?   •  Complex  (narra?ve)  ques?ons:   •  In  children  with  an  acute  febrile  illness,  what  is  the                               efficacy  of  acetaminophen  in  reducing  fever?   •  What  do  scholars  think  about  Jefferson’s  posi?on  on                       dealing  with  pirates?   Dan  Jurafsky   Commercial  systems:     mainly  factoid  ques┦ns   Where  is  the  Louvre  Museum  located?   In  Paris,  France   What’s  the  abbrevia?on  for  limited   partnership?   L.P.   What  are  the  names  of  Odin’s  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   University?   650-­‐723-­‐2300   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   11   IR-­‐based  Factoid  QA   Document DocumentDocument Docume nt Docume nt Docume nt Docume nt Docume nt Question Processing Passage Retrieval Query Formulation Answer Type Detection Question Passage Retrieval Document Retrieval Answer Processing Answer passages Indexing Relevant Docs Document Document Document 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?fic  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  classifica?on   14   Question Answering What  is  Ques?on   Answering?   Question Answering Answer  Types  and   Query  Formula?on   Dan  Jurafsky   Factoid  Q/A   17   Document DocumentDocument Docume nt Docume nt Docume nt Docume nt Docume nt Question Processing Passage Retrieval Query Formulation Answer Type Detection Question Passage Retrieval Document Retrieval Answer Processing Answer passages Indexing Relevant Docs Document Document Document Dan  Jurafsky   Ques?on  Processing   Things  to  extract  from  the  ques┦n   •  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  classifica?on   •  Is  this  a  defini?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   •  Find  rela?ons  between  en??es  in  the  ques?on  18   Dan  Jurafsky   Question Processing They’re the two states you could be reentering if you’re crossing Florida’s 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  popula?on?   •   CITY.   Dan  Jurafsky   Answer  Type  Taxonomy   •  6  coarse  classes   •  ABBEVIATION,  ENTITY,  DESCRIPTION,  HUMAN,  LOCATION,   NUMERIC   •  50  finer  classes   •  LOCATION:  city,  country,  mountain…   •  HUMAN:  group,  individual,  ?tle,  descrip?on   •  ENTITY:  animal,  body,  color,  currency…   21   Xin  Li,  Dan  Roth.  2002.  Learning  Ques⬬n  Classifiers.  COLING'02   Dan  Jurafsky   22   Part  of  Li  &  Roth’s  Answer  Type  Taxonomy   LOCATION NUMERIC ENTITY HUMAN ABBREVIATION DESCRIPTION country city state date percent money sizedistance individual title group food currency animal definition reason expression abbreviation Dan  Jurafsky   23   Answer  Types   Dan  Jurafsky   24   More  Answer  Types   Dan  Jurafsky   Answer  types  in  Jeopardy   •  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,  film,  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   Ferrucci  et  al.  2010.  Building  Watson:  An  Overview  of  the  DeepQA  Project.  AI  Magazine.  Fall  2010.  59-­‐79.   Dan  Jurafsky   Answer  Type  Detec?on   •  Hand-­‐wri?en  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  first  noun  phrase  a?er  the  wh-­‐word)     •  Which  city  in  China  has  the  largest  number  of   foreign  financial  companies?   •  What  is  the  state  flower  of  California?   Dan  Jurafsky   Answer  Type  Detec?on   •  Most  o?en,  we  treat  the  problem  as  machine  learning   classifica?on     •  Define  a  taxonomy  of  ques?on  types   •  Annotate  training  data  for  each  ques?on  type   •  Train  classifiers  for  each  ques?on  class                               using  a  rich  set  of  features.   •  features  include  those  hand-­‐wri?en  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   30   Document DocumentDocument Docume nt Docume nt Docume nt Docume nt Docume nt Question Processing Passage Retrieval Query Formulation Answer Type Detection Question Passage Retrieval Document Retrieval Answer Processing Answer passages Indexing Relevant Docs Document Document Document Dan  Jurafsky   Keyword  Selec?on  Algorithm   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  modifiers   4.  Select  all  other  complex  nominals   5.  Select  all  nouns  with  their  adjec?val  modifiers   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  Moldovan,  Sanda  Harabagiu,  Marius  Paca,  Rada  Mihalcea,  Richard  Goodrum,   Roxana  Girju  and  Vasile  Rus.  1999.  Proceedings  of  TREC-­‐8.   Dan  Jurafsky   Choosing keywords from the query 32 Who coined the term “cyberspace” in his novel “Neuromancer”? 1 1 4 4 7 cyberspace/1 Neuromancer/1 term/4 novel/4 coined/7 Slide  from  Mihai  Surdeanu   Question Answering Answer  Types  and   Query  Formula?on   Question Answering Passage  Retrieval  and   Answer  Extrac?on   Dan  Jurafsky   Factoid  Q/A   35   Document DocumentDocument Docume nt Docume nt Docume nt Docume nt Docume nt Question Processing Passage Retrieval Query Formulation Answer Type Detection Question Passage Retrieval Document Retrieval Answer Processing Answer passages Indexing Relevant Docs Document Document Document Dan  Jurafsky   36   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   Dan  Jurafsky   Features  for  Passage  Ranking   •  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   Either  in  rule-­‐based  classifiers  or  with  supervised  machine  learning   Dan  Jurafsky   Factoid  Q/A   38   Document DocumentDocument Docume nt Docume nt Docume nt Docume nt Docume nt Question Processing Passage Retrieval Query Formulation Answer Type Detection Question Passage Retrieval Document Retrieval Answer Processing Answer passages Indexing Relevant Docs Document Document Document 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 Victoria’s second son?? •  Answer  Type:    Person   •  Passage:   The  Marie  biscuit  is  named  a?er  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 Victoria’s second son?? •  Answer  Type:    Person   •  Passage:   The  Marie  biscuit  is  named  a?er  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.   Pa娣rn  match :  Regular  expression  pa?ern  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┦n  loca┦n :  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   •  taxonomic  classifica?on  43   Dan  Jurafsky   44   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  first  correct  answer     •  If  first  answer  is  correct:  1     •  else  if  second  answer  is  correct:  ½   •  else  if  third  answer  is  correct:    ⅓,    etc.   •  Score  is  0  if  none  of  the  M  answers  are  correct   •  Take  the  mean  over  all  N  queries   MRR = 1rankii=1N!N 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.”)? (granddaughter-of ?x ?y)?47   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┴l  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┦n    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”   •  Clarifica?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