NLP SEMINAR: NLP SEMINAR Question Answering Tal Hoory Slides are based on articles and a PPT from Stanford’s university NLP course


Lecture Outline: Lecture Outline Motivation How does it work Full Blown System System Architecture Question Proccesing Question Types Keyword Extraction Passage Retrieval Answer Extraction The Web Approach and the ASK MSR system


Motivation: Motivation People ask questions.. Examples from various query logs Which english translation of the bible is used in official Catholic liturgies? How tall is the sears tower? 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


So.. How does it work: So.. How does it work Not a new idea… (Simmons et al 1963) Take an encyclopedia and load it onto a computer. Take a question and parse it into a logical form Perform simple information retrieval to get relevant texts Parse those into a logical form Match and rank


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


Question Processing: Question Processing Two main tasks Determining the type of the answer Extract keywords from the question and formulate a query


Question Proccesing stage 1: Answer Types: Question Proccesing stage 1: Answer Types Factoid questions… Who, where, when, how many… The answers fall into a limited and somewhat predictable set of categories Who questions are going to be answered by… Where questions…


Answer Types: Answer Types Of course, it isn’t that easy… Who questions can have organizations as answers Who sells the most hybrid cars? Which questions can have people as answers Which president went to war with Mexico?


Sometimes this is not enough. We need question focus: Sometimes this is not enough. We need question focus “What” questions type says nothing about the information asked by the questions. Solution: capture the question’s focus. A focus is a word or a sequence of words which define the question and disambiguate it in the sense that it indicates what the question is looking for, or what the question is all about.


Question Focus Examples: Question Focus Examples “What is the largest city in Germany?”  largest city “In 1990, what day of the week did Christmas fall on?”  day of the week Now, it’s easier to know what we look for. Also, assists us in keyword selection (next slides)


Qustion proccessing stage 2: Keyword Selection: Qustion proccessing stage 2: Keyword Selection Answer Type indicates what the question is looking for, but that doesn’t really help in finding relevant texts (i.e. Ok, let’s look for texts with people in them) Lexical terms (keywords) from the question, possibly expanded with lexical/semantic variations provide the required context.


Keyword Extraction: Keyword Extraction


Keyword Selection Algorithm / heuristics: Keyword Selection Algorithm / heuristics Select all words in quotations (“ I think , Therefore I am” ) 2. Select all recognized named entities (London) Select all complex nominals with their adjectival modifiers ( - ( ביטוי שם עצם מורכב עם שמות תואר )the best tour guide) 4. Select all other complex nominals (tour guide ) 5. Select all nouns with adjectival modifiers (best guide) 6. Select all other nouns (guide) 7. Select all verbs (walked) 8. Select the answer type word / question focus (day of the week)


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


Passage Extraction Loop: Passage Extraction Loop Passage Extraction Component Extracts passages that contain all selected keywords 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 Scoring: Passage Scoring Passage ordering is performed using a sort that involves three scores: The number of words from the question that are recognized in the same sequence in the window The number of words that separate the most distant keywords in the window The number of unmatched keywords in the window


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


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...” Q066: Name the first private citizen to fly in space.


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.


Heuristics for Answer Ranking in the Lasso System: Heuristics for Answer Ranking in the Lasso System Same_Word_Sequence_score – number of words from the question that are recognized in the same sequence in the passage. Punctuation_sign_score – a flag set to 1 if the candidate answer is followed by a punctuation sign Comma_3_word_score – measure the number of question words that follow the candidate, if the candidate is followed by a coma. Same_parse_subtree_score – number of question words found in the parse sub-tree of the answer Same_sentence_score – number of question words found in the answer’s sentence.


Heuristics for Answer Ranking in the Lasso Systemcontinued: Heuristics for Answer Ranking in the Lasso System continued Distance – score – adds the distance (measured in number of words) between the answer candidate and the other keywords in the window.


Heuristics for Answer Ranking in the Lasso Systemcontinued: Heuristics for Answer Ranking in the Lasso System continued Finally..


Evaluation: Evaluation Evaluation of this kind of system is usually based on some kind of TREC-like metric. In Q/A the most frequent metric is Mean reciprocal rank You’re allowed to return N answers. Your score is based on 1/Rank of the first right answer. Averaged over all the questions you answer.


Is the Web Different?: Is the Web Different? In TREC (and most commercial applications), retrieval is performed against a smallish closed collection of texts.


The Web is Different: The Web is Different On the Web popular factoids are likely to be expressed in a gazzilion different ways. At least a few of which will likely match the way the question was asked. So why not just grep (or agrep) the Web using all or pieces of the original question.


AskMSR: AskMSR Process the question by… Simple rewrite rules to rewriting the original question into a statement Involves detecting the answer type Get some results Extract answers of the right type based on How often they occur


AskMSR: AskMSR


Results: Results Standard TREC contest test-bed (TREC 2001): 1M documents; 900 questions Technique does ok, not great (would have placed in top 9 of ~30 participants) MRR = 0.507 But with access to the Web… They do much better, would have come in second on TREC 2001


Harder Questions: Harder Questions Factoid question answering is really pretty silly. A more interesting task is one where the answers are fluid and depend on the fusion of material from disparate texts over time. Who is Condoleezza Rice? Who is Mahmoud Abbas? Why was Arafat flown to Paris?


That’s all Folks..: That’s all Folks.. References: An article about the Lasso QA system: http://www.stanford.edu/class/linguist180/Lasso.pdf An article about the Ask – MSR QA system: http://www.stanford.edu/class/linguist180/EMNLP2002.pdf Orginial version of this presentation , from Stanford’s NLP course website: http://www.stanford.edu/class/linguist180/180.05.lec16.ppt Wikipedia http://en.wikipedia.org/wiki/Question_answering Try it yourself.. http://www.ask.com