Open-Domain Question Answering on the World Wide Web

Sabine Buchholz

Overview

• Introduction
  • What is Question Answering (QA)?
  • Related domains
  • Types of questions, answers and QA systems
• TREC Question Answering Track
• Shapaqa
  • TREC vs. QA on the WWW
  • Design principles
  • Architecture
  • Evaluation
  • Results
  • Possible improvements

• For closed domains: natural language interface to a database e.g.
  

  INVENTORS

  first names	last name	born	died
  Alexander Graham	Bell	...	...

  INVENTIONS

  inventor	invention	date	place	use
  Bell	telephone	1876	...	...

  • much update work for changing data, e.g. news
  • database structure not suited for open domain

• Information Retrieval (IR)
  • User has a concept/topic etc. in mind
  • Usually specifies some keywords, e.g. "Java tutorial" or "hotel Antwerp"
  • System has to return documents that deal with the topic
  -> internet search engines like Google: results, or AltaVista: results

• Information Extraction (IE)
  • There is a pre-specified template with open slots, e.g. about company acquisitions: "who bought what, from whom, when, for which price". The slots vary depending on the topic, e.g. accidents: "how many people killed/injured"
  • System has to fill the slots on the basis of a document
  • Can be used to fill database

• Reading Comprehension Tests (Ng et al. 2000)
  • Given a text
  • System has to be able to answer questions about the text

• Answer Finding (Berger et al. 2000)
  • There is a list of questions and answers, e.g. Frequently Asked Questions (FAQs), Customer Support or Software Help Files
  • User has a question
  • System has to select the answer that best answers the question
  -> FAQ Finder (http://infolab.cs.uchicago.edu/faqfinder/), AskJeeves: results1, 2

• Some online QA systems
  • START natural language system (http://www.ai.mit.edu/projects/infolab/globe.html): results
  • The IO search engine (http://www.ionaut.com:8400/): results
  • Webclopedia (http://www.isi.edu/natural-language/projects/webclopedia/)

• Factual vs. non-factual questions/answers:
  • When did Mozart die?
  • When should I buy Shell stock options?

• Questions about the world or about the web?
  • Where did Mozart die?
  • Where can I find information about Alicante?

• Linguistic categories
  • Yes/No-question: e.g. "Did Bell invent the telephone?"
    What to do with texts that contain the following sentences?
    • Bell invented the telephone.
    • Bell did not invent the telephone.
    • Bell invented the phonograph.
    • Elisha Gray invented the telephone.
  • List question/instance finding question
    
    • Tell me/Name a hotel in Antwerp.
    • Which hotels are there in Antwerp?
  • Wh-question
    • Questions that ask for entities: cf. Answer type hierarchy by Breck et al. 2000
    • Questions that do not ask for entities (answers are often clauses, sentences etc.):
      • Why did X do that?
      • How did X do that?
      • What did X say when ...?
      • What did X do when ...?
      • What are the Valdez Priciples? (asks for a definition)

• Some questions are "tricky", e.g. "What is the capital of Congo?"
  There are two Congos: the Republic of the Congo, and the Democratic Republic of the Congo, the former Zaire ...

• For some questions, the answer is far less likely to be found in the same wordings:
  • What is the name of the rare neurological disease with symptoms such as: involuntary movements (tics), swearing, and incoherent vocalizations (grunts, shouts, etc.)? (contains a definition)
  • What is the length/temperature/etc. of X? (asks for a property)
  • What type of bridge is the Golden Gate Bridge?

• Taxonomy of QA systems by Moldovan et al. 2000: current systems of class 1 to 3

• For some questions, our collection might contain thousands of documents containing the answer, for others, it might only contain one (or none). These cases pose different problems:
  • sorting/ordering of answers, maybe summarization
  • sophisticated NLP
  • How can a system "know" that the answer is not in the collection?

• Answers change over time
  • Daily:
    • What is the exchange rate from US dollars to ...?
    • How is the weather in ...?
    • What is the cheapest flight to ...?
    START e.g. links to an online weather site
  • Sometimes:
    • How many people live in ...?
    • Who is the president of ...?
  • (Nearly) never:
    • Who invented ...?
    • What is the capital of ...?

• Some answers are better than others:
  August 19, 1974 vs. in the 1970's,
  Ulysses S. Grant was born in a white Allegheny pine house on the banks of the Ohio River twenty-five miles southeast of Cincinnati
  vs. in Point Pleasant , Ohio
  vs. on Earth

• Answers in free text or in table
  • Madrid is the capital of Spain.

  • Country	Capital
    Spain	Madrid
    UK	London

Text REtrieval Conference (TREC) Question Answering Track

Given

• a document collection, ca. 1,000,000 documents/3 GB, all newspaper/newswire, mostly American
• 200-700 fact-based short-answer questions
  Example questions and answers:
  • Who is the author of the book, "The Iron Lady: A Biography of Margaret Thatcher"?
    Hugo Young
  • What was the monetary value of the Nobel Peace Prize in 1989?
    $469,000
  • What does the Peugeot company manufacture?
    cars

• Ranked list of five [document-id,answer-string] pairs per question or (TREC-10) "no answer in collection"
• Answer strings limited to 50 or 250 bytes
• TREC-9/10: Document must support answer

• Human assessors judged whether a string contained an answer to the question in the context provided by the document
  -> system got credit if it correctly extracted an answer from a document that was incorrect!
• Mean reciprocal rank (MRR):
  • For each question:
    receive score equal to reciprocal of rank of first correct response, or 0 if no correct response found.
    
  • Overall system score is mean of individual question scores.

• for TREC-9 (Voorhees 2001)
• best systems: MRR of 0.58 (50 bytes) / 0.76 (250 bytes)
• if correct answer is found at all it is often at first rank
• for systems that did both tasks: better results for 250 bytes

Shapaqa: A prototype system for form-based QA on the World Wide Web using shallow parsing

TREC vs. QA on the World Wide Web

Architecture: global, NLP modules

Sample sentence with treebank annotation:

( (S
    (NP-SBJ (DT The) (NN telephone) )
    (VP (VBD was)
       (VP (VBN invented)
          (PP (IN by)
	     (NP-LGS (NNP Alexander) (NNP Graham) (NNP Bell) ) )
	  (PP-TMP (IN in)
	     (NP (CD 1876) ) ) ) )
    (. .) ))

• The importance of the telephone network as a critical factor in the success of fax cannot be overstated. Alexander Bain invented the fax machine in ...
• [_NPTouch-Map Systems] [_VPinvented] [_NPthe telephone dealer locator] [_Pover] [_NPseventeen years] [_ADVPago] .
• Invented at almost the same time as the telephone to speed data analysis for the 1880 U.S. Census, the tabulating machine was an electromechanical device that ...
• One year after the telephone was invented, its usage was taxed.

• Using the 200 test questions from the TREC-8 QA track
• Hand-fitted into the input form
  • 12 questions do not fit at all
    e.g. "How tall is the Matterhorn?" "What did John Hinckley do to impress Jodie Foster?"
  • 76 questions do not fit well
    e.g. "What two biochemists ...?" -> "Who ...?"
• Humans judged first evidence sentence of first five keyword answers
• Mean reciprocal rank
• Also comparison with just taking first five sentences that contain all phrases (SENT) and using first five text snippets from Google after simple keyword search