lecture18

SIMS 290-2: Applied Natural Language Processing: 

SIMS 290-2: Applied Natural Language Processing Marti Hearst November 15, 2004    

Question Answering: 

Question Answering Today: Introduction to QA A typical full-fledged QA system A very simple system, in response to this An intermediate approach Wednesday: Using external resources WordNet Encyclopedias, Gazeteers Incorporating a reasoning system Machine Learning of mappings Other question types (e.g., biography, definitions)

A of Search Types: 

A of Search Types What is the typical height of a giraffe? What are some good ideas for landscaping my client’s yard? What are some promising untried treatments for Raynaud’s disease?

Beyond Document Retrieval: 

Document Retrieval Users submit queries corresponding to their information needs. System returns (voluminous) list of full-length documents. It is the responsibility of the users to find information of interest within the returned documents. Open-Domain Question Answering (QA) Users ask questions in natural language. What is the highest volcano in Europe? System returns list of short answers. … Under Mount Etna, the highest volcano in Europe, perches the fabulous town … A real use for NLP Beyond Document Retrieval

Questions and Answers: 

Questions and Answers What is the height of a typical giraffe? The result can be a simple answer, extracted from existing web pages. Can specify with keywords or a natural language query However, most web search engines are not set up to handle questions properly. Get different results using a question vs. keywords

The Problem of Question Answering: 

The Problem of Question Answering What is the nationality of Pope John Paul II? … stabilize the country with its help, the Catholic hierarchy stoutly held out for pluralism, in large part at the urging of Polish-born Pope John Paul II. When the Pope emphatically defended the Solidarity trade union during a 1987 tour of the… When was the San Francisco fire? … were driven over it. After the ceremonial tie was removed - it burned in the San Francisco fire of 1906 – historians believe an unknown Chinese worker probably drove the last steel spike into a wooden tie. If so, it was only… Where is the Taj Mahal? … list of more than 360 cities around the world includes the Great Reef in Australia, the Taj Mahal in India, Chartre’s Cathedral in France, and Serengeti National Park in Tanzania. The four sites Japan has listed include…

The Problem of Question Answering: 

The Problem of Question Answering What is the nationality of Pope John Paul II? … stabilize the country with its help, the Catholic hierarchy stoutly held out for pluralism, in large part at the urging of Polish-born Pope John Paul II. When the Pope emphatically defended the Solidarity trade union during a 1987 tour of the… Natural language question, not keyword queries Short text fragment, not URL list

Question Answering from text: 

Question Answering from text With massive collections of full-text documents, simply finding relevant documents is of limited use: we want answers QA: give the user a (short) answer to their question, perhaps supported by evidence. An alternative to standard IR The first problem area in IR where NLP is really making a difference.

People want to ask questions…: 

People want to ask questions… Examples from AltaVista query log who invented surf music? how to make stink bombs where are the snowdens of yesteryear? which english translation of the bible is used in official catholic liturgies? how to do clayart how to copy psx how tall is the sears tower? Examples from Excite query log (12/1999) how can i find someone in texas where can i find information on puritan religion? what are the 7 wonders of the world how can i eliminate stress What vacuum cleaner does Consumers Guide recommend

A Brief (Academic) History: 

A Brief (Academic) History In some sense question answering is not a new research area Question answering systems can be found in many areas of NLP research, including: Natural language database systems A lot of early NLP work on these Problem-solving systems STUDENT (Winograd ’77) LUNAR (Woods & Kaplan ’77) Spoken dialog systems Currently very active and commercially relevant The focus is now on open-domain QA is new First modern system: MURAX (Kupiec, SIGIR’93): Trivial Pursuit questions Encyclopedia answers FAQFinder (Burke et al. ’97) TREC QA competition (NIST, 1999–present)

AskJeeves : 

AskJeeves AskJeeves is probably most hyped example of “Question answering” How it used to work: Do pattern matching to match a question to their own knowledge base of questions If a match is found, returns a human-curated answer to that known question If that fails, it falls back to regular web search (Seems to be more of a meta-search engine now) A potentially interesting middle ground, but a fairly weak shadow of real QA

Question Answering at TREC: 

Question Answering at TREC Question answering competition at TREC consists of answering a set of 500 fact-based questions, e.g., “When was Mozart born?”. Has really pushed the field forward. The document set Newswire textual documents from LA Times, San Jose Mercury News, Wall Street Journal, NY Times etcetera: over 1M documents now. Well-formed lexically, syntactically and semantically (were reviewed by professional editors). The questions Hundreds of new questions every year, the total is ~2400 Task Initially extract at most 5 answers: long (250B) and short (50B). Now extract only one exact answer. Several other sub-tasks added later: definition, list, biography.

Sample TREC questions: 

Sample TREC questions 1. Who is the author of the book, "The Iron Lady: A Biography of Margaret Thatcher"? 2. What was the monetary value of the Nobel Peace Prize in 1989? 3. What does the Peugeot company manufacture? 4. How much did Mercury spend on advertising in 1993? 5. What is the name of the managing director of Apricot Computer? 6. Why did David Koresh ask the FBI for a word processor? 7. What is the name of the rare neurological disease with symptoms such as: involuntary movements (tics), swearing, and incoherent vocalizations (grunts, shouts, etc.)?

TREC Scoring: 

TREC Scoring For the first three years systems were allowed to return 5 ranked answer snippets (50/250 bytes) to each question. Mean Reciprocal Rank Scoring (MRR): Each question assigned the reciprocal rank of the first correct answer. If correct answer at position k, the score is 1/k. 1, 0.5, 0.33, 0.25, 0.2, 0 for 1, 2, 3, 4, 5, 6+ position Mainly Named Entity answers (person, place, date, …) From 2002 on, the systems are only allowed to return a single exact answer and the notion of confidence has been introduced.

Top Performing Systems: 

Top Performing Systems In 2003, the best performing systems at TREC can answer approximately 60-70% of the questions Approaches and successes have varied a fair deal Knowledge-rich approaches, using a vast array of NLP techniques stole the show in 2000-2003 Notably Harabagiu, Moldovan et al. ( SMU/UTD/LCC ) Statistical systems starting to catch up AskMSR system stressed how much could be achieved by very simple methods with enough text (and now various copycats) People are experimenting with machine learning methods Middle ground is to use large collection of surface matching patterns (ISI)

Example QA System: 

Example QA System This system contains many components used by other systems, but more complex in some ways Most work completed in 2001; there have been advances by this group and others since then. Next slides based mainly on: Paşca and Harabagiu, High-Performance Question Answering from Large Text Collections, SIGIR’01. Paşca and Harabagiu, Answer Mining from Online Documents, ACL’01. Harabagiu, Paşca, Maiorano: Experiments with Open-Domain Textual Question Answering. COLING’00

QA Block Architecture: 

QA Block Architecture Question Processing Passage Retrieval Answer Extraction WordNet NER Parser WordNet NER Parser Document Retrieval Keywords Passages Question Semantics Q A

Question Processing Flow: 

Question Processing Flow Q Question parsing Construction of the question representation Answer type detection Keyword selection Question semantic representation AT category Keywords

Question Stems and Answer Types: 

Question Stems and Answer Types Other question stems: Who, Which, Name, How hot... Other answer types: Country, Number, Product... Identify the semantic category of expected answers

Detecting the Expected Answer Type: 

Detecting the Expected Answer Type In some cases, the question stem is sufficient to indicate the answer type (AT) Why  REASON When  DATE In many cases, the question stem is ambiguous Examples What was the name of Titanic’s captain ? What U.S. Government agency registers trademarks? What is the capital of Kosovo? Solution: select additional question concepts (AT words) that help disambiguate the expected answer type Examples captain agency capital

Answer Type Taxonomy: 

Answer Type Taxonomy Encodes 8707 English concepts to help recognize expected answer type Mapping to parts of Wordnet done by hand Can connect to Noun, Adj, and/or Verb subhierarchies

Answer Type Detection Algorithm: 

Answer Type Detection Algorithm Select the answer type word from the question representation. Select the word(s) connected to the question. Some “content-free” words are skipped (e.g. “name”). From the previous set select the word with the highest connectivity in the question representation. Map the AT word in a previously built AT hierarchy The AT hierarchy is based on WordNet, with some concepts associated with semantic categories, e.g. “writer”  PERSON. Select the AT(s) from the first hypernym(s) associated with a semantic category.

Answer Type Hierarchy: 

Answer Type Hierarchy PERSON PERSON

Evaluation of Answer Type Hierarchy: 

Evaluation of Answer Type Hierarchy This evaluation done in 2001 Controlled the variation of the number of WordNet synsets included in the answer type hierarchy. Test on 800 TREC questions. 0% 0.296 3% 0.404 10% 0.437 25% 0.451 50% 0.461 Precision score (50-byte answers) Hierarchy coverage The derivation of the answer type is the main source of unrecoverable errors in the QA system

Keyword Selection: 

Keyword Selection Answer Type indicates what the question is looking for, but provides insufficient context to locate the answer in very large document collection Lexical terms (keywords) from the question, possibly expanded with lexical/semantic variations provide the required context.

Lexical Terms Extraction: 

Lexical Terms Extraction Questions approximated by sets of unrelated words (lexical terms) Similar to bag-of-word IR models

Keyword Selection Algorithm: 

Keyword Selection Algorithm Select all non-stopwords in quotations Select all NNP words in recognized named entities Select all complex nominals with their adjectival modifiers Select all other complex nominals Select all nouns with adjectival modifiers Select all other nouns Select all verbs Select the AT word (which was skipped in all previous steps)

Keyword Selection Examples: 

Keyword Selection Examples 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

Passage Retrieval: 

Passage Retrieval Question Processing Passage Retrieval Answer Extraction WordNet NER Parser WordNet NER Parser Document Retrieval Keywords Passages Question Semantics Q A

Passage Extraction Loop: 

Passage Extraction Loop Passage Extraction Component Extracts passages that contain all selected keywords Passage size dynamic Start position dynamic Passage quality and keyword adjustment In the first iteration use the first 6 keyword selection heuristics If the number of passages is lower than a threshold  query is too strict  drop a keyword If the number of passages is higher than a threshold  query is too relaxed  add a keyword

Passage Retrieval Architecture: 

Passage Retrieval Architecture Passage Extraction Passage Quality Keyword Adjustment Passage Scoring Passage Ordering Keywords No Passages Yes Documents Document Retrieval Ranked Passages

Passage Scoring: 

Passage Scoring Passages are scored based on keyword windows For example, if a question has a set of keywords: {k1, k2, k3, k4}, and in a passage k1 and k2 are matched twice, k3 is matched once, and k4 is not matched, the following windows are built: k1 k2 k3 k2 k1 Window 1 k1 k2 k3 k2 k1 Window 2 k1 k2 k3 k2 k1 Window 3 k1 k2 k3 k2 k1 Window 4

Passage Scoring: 

Passage Scoring Passage ordering is performed using a radix sort that involves three scores: SameWordSequenceScore (largest) Computes the number of words from the question that are recognized in the same sequence in the window DistanceScore (largest) The number of words that separate the most distant keywords in the window MissingKeywordScore (smallest) The number of unmatched keywords in the window

Answer Extraction: 

Answer Extraction Question Processing Passage Retrieval Answer Extraction WordNet NER Parser WordNet NER Parser Document Retrieval Keywords Passages Question Semantics Q A

Ranking Candidate Answers: 

Ranking Candidate Answers 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...” Best candidate answer: Christa McAuliffe Q066: Name the first private citizen to fly in space.

Features for Answer Ranking: 

Features for Answer Ranking relNMW number of question terms matched in the answer passage relSP number of question terms matched in the same phrase as the candidate answer relSS number of question terms matched in the same sentence as the candidate answer relFP flag set to 1 if the candidate answer is followed by a punctuation sign relOCTW number of question terms matched, separated from the candidate answer by at most three words and one comma relSWS number of terms occurring in the same order in the answer passage as in the question relDTW average distance from candidate answer to question term matches SIGIR ‘01

Answer Ranking based on Machine Learning: 

Answer Ranking based on Machine Learning Relative relevance score computed for each pair of candidates (answer windows) relPAIR = wSWS  relSWS + wFP  relFP + wOCTW  relOCTW + wSP  relSP + wSS  relSS + wNMW  relNMW + wDTW  relDTW + threshold If relPAIR positive, then first candidate from pair is more relevant Perceptron model used to learn the weights Scores in the 50% MRR for short answers, in the 60% MRR for long answers

Evaluation on the Web: 

Evaluation on the Web test on 350 questions from TREC (Q250-Q600) extract 250-byte answers

Can we make this simpler?: 

Can we make this simpler? One reason systems became so complex is that they have to pick out one sentence within a small collection The answer is likely to be stated in a hard-to-recognize manner. Alternative Idea: What happens with a much larger collection? The web is so huge that you’re likely to see the answer stated in a form similar to the question Goal: make the simplest possible QA system by exploiting this redundancy in the web Use this as a baseline against which to compare more elaborate systems. The next slides based on: Web Question Answering: Is More Always Better? Dumais, Banko, Brill, Lin, Ng, SIGIR’02 An Analysis of the AskMSR Question-Answering System, Brill, Dumais, and Banko, EMNLP’02.

AskMSR System Architecture: 

AskMSR System Architecture 1 2 3 4 5

Step 1: Rewrite the questions: 

Step 1: Rewrite the questions Intuition: The user’s question is often syntactically quite close to sentences that contain the answer Where is the Louvre Museum located? The Louvre Museum is located in Paris Who created the character of Scrooge? Charles Dickens created the character of Scrooge.

Query rewriting: 

Query rewriting Classify question into seven categories Who is/was/are/were…? When is/did/will/are/were …? Where is/are/were …? a. Hand-crafted category-specific transformation rules e.g.: For where questions, move ‘is’ to all possible locations Look to the right of the query terms for the answer. “Where is the Louvre Museum located?”  “is the Louvre Museum located”  “the is Louvre Museum located”  “the Louvre is Museum located”  “the Louvre Museum is located”  “the Louvre Museum located is” b. Expected answer “Datatype” (eg, Date, Person, Location, …) When was the French Revolution?  DATE Nonsense, but ok. It’s only a few more queries to the search engine.

Query Rewriting - weighting: 

Query Rewriting - weighting Some query rewrites are more reliable than others. +“the Louvre Museum is located” Where is the Louvre Museum located? Weight 5 if a match, probably right +Louvre +Museum +located Weight 1 Lots of non-answers could come back too

Step 2: Query search engine: 

Step 2: Query search engine Send all rewrites to a Web search engine Retrieve top N answers (100-200) For speed, rely just on search engine’s “snippets”, not the full text of the actual document

Step 3: Gathering N-Grams: 

Step 3: Gathering N-Grams Enumerate all N-grams (N=1,2,3) in all retrieved snippets Weight of an n-gram: occurrence count, each weighted by “reliability” (weight) of rewrite rule that fetched the document Example: “Who created the character of Scrooge?” Dickens 117 Christmas Carol 78 Charles Dickens 75 Disney 72 Carl Banks 54 A Christmas 41 Christmas Carol 45 Uncle 31

Step 4: Filtering N-Grams: 

Step 4: Filtering N-Grams Each question type is associated with one or more “data-type filters” = regular expression When… Where… What … Who … Boost score of n-grams that match regexp Lower score of n-grams that don’t match regexp Details omitted from paper…. Date Location Person

Step 5: Tiling the Answers: 

Step 5: Tiling the Answers Dickens Charles Dickens Mr Charles Scores 20 15 10 merged, discard old n-grams Mr Charles Dickens Score 45 N-Grams tile highest-scoring n-gram N-Grams Repeat, until no more overlap

Results: 

Results Standard TREC contest test-bed (TREC 2001): ~1M documents; 900 questions Technique doesn’t do too well (though would have placed in top 9 of ~30 participants) MRR: strict: .34 MRR: lenient: .43 9th place

Results: 

Results From EMNLP’02 paper MMR of .577; answers 61% correctly Would be near the top of TREC-9 runs Breakdown of feature contribution:

Issues: 

Issues Works best/only for “Trivial Pursuit”-style fact-based questions Limited/brittle repertoire of question categories answer data types/filters query rewriting rules

Intermediate Approach:Surface pattern discovery: 

Intermediate Approach: Surface pattern discovery Based on: Ravichandran, D. and Hovy E.H. Learning Surface Text Patterns for a Question Answering System, ACL’02 Hovy, et al., Question Answering in Webclopedia, TREC-9, 2000. Use of Characteristic Phrases "When was <person> born” Typical answers "Mozart was born in 1756.” "Gandhi (1869-1948)...” Suggests regular expressions to help locate correct answer "<NAME> was born in <BIRTHDATE>” "<NAME> ( <BIRTHDATE>-”

Use Pattern Learning: 

Use Pattern Learning Examples: “The great composer Mozart (1756-1791) achieved fame at a young age” “Mozart (1756-1791) was a genius” “The whole world would always be indebted to the great music of Mozart (1756-1791)” Longest matching substring for all 3 sentences is "Mozart (1756-1791)” Suffix tree would extract "Mozart (1756-1791)" as an output, with score of 3 Reminiscent of IE pattern learning

Pattern Learning (cont.): 

Pattern Learning (cont.) Repeat with different examples of same question type “Gandhi 1869”, “Newton 1642”, etc. Some patterns learned for BIRTHDATE a. born in <ANSWER>, <NAME> b. <NAME> was born on <ANSWER> , c. <NAME> ( <ANSWER> - d. <NAME> ( <ANSWER> - )

QA Typology from ISI: 

QA Typology from ISI Typology of typical question forms—94 nodes (47 leaf nodes) Analyzed 17,384 questions (from answers.com)

Experiments: 

Experiments 6 different question types from Webclopedia QA Typology BIRTHDATE LOCATION INVENTOR DISCOVERER DEFINITION WHY-FAMOUS

Experiments: pattern precision: 

Experiments: pattern precision BIRTHDATE: 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> - INVENTOR 1.0 <ANSWER> invents <NAME> 1.0 the <NAME> was invented by <ANSWER> 1.0 <ANSWER> invented the <NAME> in

Experiments (cont.): 

Experiments (cont.) DISCOVERER 1.0 when <ANSWER> discovered <NAME> 1.0 <ANSWER>'s discovery of <NAME> 0.9 <NAME> was discovered by <ANSWER> in DEFINITION 1.0 <NAME> and related <ANSWER> 1.0 form of <ANSWER>, <NAME> 0.94 as <NAME>, <ANSWER> and

Experiments (cont.): 

Experiments (cont.) WHY-FAMOUS 1.0 <ANSWER> <NAME> called 1.0 laureate <ANSWER> <NAME> 0.71 <NAME> is the <ANSWER> of LOCATION 1.0 <ANSWER>'s <NAME> 1.0 regional : <ANSWER> : <NAME> 0.92 near <NAME> in <ANSWER> Depending on question type, get high MRR (0.6–0.9), with higher results from use of Web than TREC QA collection

Shortcomings & Extensions: 

Shortcomings & Extensions Need for POS &/or semantic types "Where are the Rocky Mountains?” "Denver's new airport, topped with white fiberglass cones in imitation of the Rocky Mountains in the background , continues to lie empty” <NAME> in <ANSWER> NE tagger &/or ontology could enable system to determine "background" is not a location

Shortcomings... (cont.): 

Shortcomings... (cont.) Long distance dependencies "Where is London?” "London, which has one of the busiest airports in the world, lies on the banks of the river Thames” would require pattern like: <QUESTION>, (<any_word>)*, lies on <ANSWER> Abundance & variety of Web data helps system to find an instance of patterns w/o losing answers to long distance dependencies

Shortcomings... (cont.): 

Shortcomings... (cont.) System currently has only one anchor word Doesn't work for Q types requiring multiple words from question to be in answer "In which county does the city of Long Beach lie?” "Long Beach is situated in Los Angeles County” required pattern: <Q_TERM_1> is situated in <ANSWER> <Q_TERM_2> Does not use case "What is a micron?” "...a spokesman for Micron, a maker of semiconductors, said SIMMs are..." If Micron had been capitalized in question, would be a perfect answer

Question Answering: 

Question Answering Today: Introduction to QA A typical full-fledged QA system A very simple system, in response to this An intermediate approach Wednesday: Using external resources WordNet Encyclopedias, Gazeteers Incorporating a reasoning system Machine Learning of mappings Alternative question types