NLP Reading List For Building a Question Answering System

• Tagger
• Parser
• Chunker
• NER - Named Entity Recognition
• Word sense disambiguation
• Anaphora (or Reference) Resolution
• Question-type classification
• Logical Form Transformation
• Document Retrieval
• Textual Entailment
• Systems evaluated on Remedia Corpus
• Systems evaluated on TREC
• Answer Evaluation
• Web Information Extraction

Tagger

• Adwait Ratnaparkhi (1996): A Maximum Entropy Model for Part-Of-Speech Tagging uses a MaxEnt model with the prior two tags and prior two and subsequent two words as features for tagging a given word. Rare words also use suffixes and prefixes of length less than 4, while non-rare words use the word itself as a feature. Any feature (other than the word itself) which occurs less than 10 times is ignored in the maxent model. The probability assigned to each tag is multiplied together in a left-to-right scan of the input, keeping a beam of size 5. Specialized features for error-prone words gives the final .1% boost in performance.

  Attains 96.6% POS tagging accuracy on the Penn Treebank WSJ data. However, the division of the treebank into training, dev, and test set is different from that used in subsequent research making comparisons with future work hard.

Parser

• Michael Collins (1997): Three Generative, Lexicalised Models for Statistical Parsing introduced generative lexical parsing. Model 1 first generates the head word and then the left children and the right children. Model 2 generates the categories of the left and the right children between these two steps. Model 3 handles WH-movement better.

  On the Penn Treebank they attains precision and recall of 88.1 and 87.5% respectively.

• Hiroyasu Yamada, Yuji Matsumoto (2003): Statistical Dependency Analysis With Support Vector Machines construct an unlabelled dependency tree in a left-to-right parse of the sentence with three actions: shift, left, and right. The choice of actions is decided by an SVM (actually three binary classifiers making pair-wise decisions) using contextual features: the words and parts-of-speech tags of neighbouring words and their children.

  They train and evaluate on the Penn Treebank (converted to unlabelled dependency trees using a standard set of head rules). The measurements are Dependency Accuracy, Root Accuracy, and Complete Match. The best numbers they get are -- DA .903, RA .916, CM .384. This is not as good as the best previous work which is Charniak's parser modified to output dependency trees -- DA .921, RA .952, CM .452, but the authors claim that 90% accuracy is very good for a parser which doesn't use phrase structure information.

• Joakim Nivre and Mario Scholz (2004): Deterministic Dependency Parsing of English Text extend Yamada 2003's work by considering labelled dependencies. This is also a shift-reduce parser but with four actions: shift, reduce, left-arc, and right-arc.

  They also train and evaluate on the Penn Treebank extracting labels from a combination of the phrase types and the function tags. The accuracy on labels and dependencies seem to be in the range of 84-86% depending on the set of labels chosen. There is no comparable work but for unlabelled dependency trees their numbers are -- DA .873, RA .843, CM .304

• R. McDonald, F. Pereira, K. Ribarov and J. Hajic (2005): Non-Projective Dependency Parsing using Spanning Tree Algorithms They are computing an unlabelled dependency tree using a maximum spanning tree approach. ... MORE ...

  On the Penn Treebank converted using Yamada and Matsumoto's rules (see above) they obtain DA .909, RA .942, CM .375.

• Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning (2006): Generating Typed Dependency Parses from Phrase Structure Parses convert the output of a constituent structure parser into a labelled dependency tree. They have used significantly different head rules than used by previous work on lexicalized parsing. The head rules focus on the semantic head of the phrase rather than the syntactic head. Also, they generate additional edges making the dependency graph no longer a tree, or even acyclic. Interestingly, the depndency types are specifically designed to build a logic-form for question answering or textual entailment systems.

Chunker

• Taku Kudoh and Yuji Matsumoto (2000): Use of Support Vector Learning for Chunk Identification Uses pair-wise SVM classifiers with a polynomial kernel of degree 2. Using as features the 5 words and tags around the target word plus the two prior chunk tags. Beam search with a beam of size 5.

  Achieves an F-score of 93.48 on CoNLL-2000 shared task.

NER - Named Entity Recognition

• GuoDong Zhou, and Jian Su (2002): Named Entity Recognition using an HMM-based Chunk Tagger ...MORE...

  Attains F-measures of 96.8% and 94.2% on MUCs 6 and 7.

Anaphora (or Reference) Resolution

• Jan van Eijck (2005): Discourse Representation Theory describes what nominals a pronoun is allowed to refer to in sentences with quantifiers and conditionals. ...MORE...

Logical Form Transformation

• Jerry R. Hobbs (1986): Overview of the TACITUS Project gives a brief glimpse of the knowledge representation scheme involving predicates for each word of the sentence and thinking of a derivation as the interpretation. Hints also at issues in temporal reasoning.
• John Bear and Jerry R. Hobbs (1988): Localizing Expression of Ambiguity discusses how to capture attachment and other ambiguities in the logical form of a sentence instead of creating multiple logical forms. The ambiguities are captured as a disjunction of possible entity or action variables that special 'y' variables could be identical to.
• Jerry R. Hobbs, Mark Stickel, Paul Martin, Douglas Edwards (1990): Interpretation as abduction describes how abductive reasoning (an unsound logical inference process) can be used to understand natural language. ...MORE...
• Patric Blackburn, Johan Bos, Michael Kohlhase (1998): Automated Theorem Proving for Natural Language Understanding shows how to transform sentences in Discourse Representation Theory to first order logic. ...MORE...
• Ricardo Santos (2000): Donald Davidson On The Logical Form of Action Sentences describes and justifies the Davidsonian view on logical forms. The logical form of a sentence must capture the entailment relation between the sentence and other sentences. Actions (and entities) should be represented by variables and their descriptions by predicates in the logical form - because a single action can have multiple descriptions. Also, prepositions should have their own predicates which modify the action.
• Dan I. Moldovan, Vasile Rus (2001): Logic Form Transformation of WordNet and its Applicability to Question Answering takes glosses found in WordNet, parses them and converts them to a logical form. ...MORE...

Document Retrieval

• M.F.Porter (1980): An algorithm for suffix stripping. ...MORE...

Systems evaluated on Remedia Corpus

• Lynette Hirschman, Marc Light, Eric Breck, and John D. Burger (1999): Deep Read: A Reading Comprehension System uses a bag of words to find the answer sentence which has the best intersection with the question. The bag of words consists of the stemmed words in the sentence along with semantic labels like :PERSON and :LOCATION, and personal pronouns replaced by the last :PERSON named entity. Some other heuristics include preferring longer matching words and preferring sentences which appear earlier in the document.

  Performs at 33% (HumSentAcc) on the Remedia corpus. (36% with perfect name and stem resolution)

• Eugene Charniak, Yasemin Altun, Rodrigo de Salvo Braz, Benjamin Garrett, Margaret Kosrnala, Tomer Moscovich, Lixin Pang, Changbee Pyo, Ye Sun, Wei Wy (2000): Reading Comprehension Programs in a Statistical-Language-Processing Class Same Bag-of-words approach with a few tweaks to push up the numbers a little bit. Specifically, bag-of-verbs, tfidf based matching instead of set intersection, and special rules for each question type. This work shows that down-weighting stop words is better than removing them altogether. Also, many a times, the correct answer is not in the sentence with the best match but in the preceding or the following sentence.

  Performs at 41% (HumSentAcc) on the Remedia corpus.

• Ellen Riloff and Michael Thelen (2000): A Rule-based Question Answering System for Reading Comprehension Tests is also a bag-of-words approach augmented with semantic classes (HUMAN, LOCATION, MONTH, TIME). Specific score rules are hand constructed for different question types.

  Performs at 40% (HumSentAcc) on the Remedia corpus.

• Sanda M. Harabagiu, Steven J. Maiorano, and Marius A Pasca (2003): Open-Domain Textual Question Answering
  • question stem analysis and disambiguation
  • uses 24 named-entity categories
  • answer type detection
  • mapping of named-entity to answer type
  ...MORE...

  Performs at 65.3% (HumSentAcc) on the Remedia Corpus (76.4% with perfect named entity resolution and coreference resolution). There are no results provided for their system's named entity resolution and coreference resolution -- the first number has named entity resolution only.

• Eugene Grois and David C. Wilkins (2005): Learning Strategies for Story Comprehension: A Reinforcement Learning Approach ...MORE...

  Performs at 48% (HumSentAcc) on the Remedia Corpus.

• Ben Wellner, Lisa Ferro, Warren Greiff and Lynette Hirschman (2006): Reading comprehension tests for computer-based understanding evaluation creates a logical form of the question and answer, and uses abductive reasoning ...MORE...

  Performs at 46% (inexact) on the Remedia Corpus.

Systems evaluated on TREC

• Dan Moldovan, Christine Clark, Sanda Harabagiu, and Steve Maiorano (2003): COGEX: A Logic Prover for Question Answering uses a theorem prover on the logical form of the question, text, and world-knowledge axioms to justify an answer. The logical form of a sentence is constructed using syntactic information such as "the subject, object, preposition attachment, complex nominals, and adjectival/adverbial adjuncts." Each word and its part-of-speech becomes a predicate in the logical form. Noun predicates have only one argument while verbs take a subject and an object. The hypernym, instance-of, part-of relations in WordNet supplmented by information in the gloss are used to relate words in the question and answer. NLP axioms effectively help to do anaphora resolution as well.

  In TREC 2002, the COGEX system helped boost the LCC system's performance by 30%.

• Vasin Punyakanok, Dan Roth, and Wen-tau Yih (2004): Natural Language Inference via Dependency Tree Mapping: An Application to Question Answering computes weighted edit distance between the question represented as a tree and each candidate answer, also as a tree. ...MORE...

Answer Evaluation

• Jimmy Lin and Dina Demner-Fushman (2006): Methods for Automatically Evaluating Answers to Complex Questions Describes the evaluation of the "other" questions in TREC by doing an n-gram matching with the answer key. ...MORE...

Web Information Extraction

• Ellen Riloff (AAAI 1996): Automatically generating extraction patterns from untagged text
  [Citations]
  Prior work took explicit instances of entities with the domain marked as training data and constructed generalized patterns for the domain using syntactic features. This work takes as training data only text which are relevant to a particular domain and it extract patterns using relevancy statistics.


• Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam, Seán Slattery (AI 2000):
  Learning to construct knowledge bases from the World Wide Web
  [Citations]
  Starts with an ontology of entities and relations and training data consisting of web pages with the entities and relations marked. It then finds new instances of the entities and relations. It uses faculty and student home pages to learn advisor, course taught relations etc.


• Michele Banko, Michael J Cafarella, Stephen Soderland, Matt Broadhead and Oren Etzioni (IJCAI 2007):
  Open Information Extraction from the Web
  [Citations]
  The TextRunner system uses a Naive Bayes classifier (trained from a syntactic parser) to find arbitrary entity, relation, entity tuples.