Ravichandran and Hovy, ACL 2002: Learning Surface Text Patterns for a Question Answering System

Citation

Ravichandran, D. and Hovy, E. 2002. Learning Surface Text Patterns for a Question Answering System. Proceedings of the 40th Annual Meeting on Association for Computational Linguistics. 41--47

Online version

An online version of this paper is available [1].

Summary

This paper introduces a method to learn surface patterns from text and use them to answer factoid style questions.

Motivation

The authors consider the problem of answering factoid questions (e.g. When was X born?). Some possible approaches for this problem include using NER, WordNet, parsers, hand-tagged corpora, and ontology lists. It turns out that a very powerful approach is to use surface text patterns, e.g. “<NAME> was born in <BIRTHDATE>”, “<NAME> (<BIRTHDATE>–”. One could create such patterns manually, but this is time-consuming, and one needs to create patterns afresh for each new attribute. Also, there's a limit on how much data can be looked at, and the method is not very accurate. The authors therefore try to learn such patterns automatically and with high precision.

Big Picture

• Use bootstrapping to build a large set of patterns starting with only a few examples of QA pairs.

• Rank learned patterns in order of precision

• Use patterns to answer unseen questions

Algorithm 1: Learning patterns

• Select an example QA pair e.g. “Mozart 1756”
• Submit to search engine; download top 1k hits
• Retain only sentences that contain both terms

• • Pass each sentence through suffix tree constructor. This finds all substrings, of all lengths, along with their counts

• • 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: “Mozart (1756–1791)”, which the suffix tree would extract as one of the outputs, with score 3

• For each phrase in suffix tree, retain only those phrases that contain both terms
• Replace the word for Q term by “<NAME>” and for A term by “<ANSWER>”.
• Examples of learned patterns for Birthyear:
  • born in <ANSWER> , <NAME>
  • <NAME> was born on <ANSWER> ,
  • <NAME> ( <ANSWER> -
  • <NAME> ( <ANSWER - )

In Maximum Entropy Markov models (MeMMs), the HMM transition and observation functions are replaced by a single function that provides the probability of the current state given the previous state and the current observation. In contrast to HMMs, in which the current observation only depends on the current state, the current observation in an MEMM may also depend on the previous state. In other words, the observations can be thought of as being associated with state transitions rather than with states. Moreover, for each state, such a transition function is given by a distinct Maxent model.

The paper illustrates a modification of the HMM Viterbi inference algorithm to perform inference for MeMMs. It also provides a Generalized Iterative Scaling (GIS) algorithm to train MeMMs, which is guaranteed to converge to a global maximum as long as there is at most one state per label.

For cases where training label sequences are unknown or ambiguous, the paper also gives a modification of the standard Baum-Welch training algorithm for HMMs.

Variations of MeMMs

The paper produces several variations of the basic MeMM architecture explained above:

• Factored state representation

To deal with data sparseness problem in standard MeMMs (due to $O(|S|^{2})$ transition parameters), one can avoid having S different transition functions (one for each state), and just maintain one function, which uses information about the previous state as features. This reduces the expressive power of the model but allows sharing of information across states and alleviates sparseness problems.

• Observations in states instead of transitions

Rather than combining transition and emission parameters into a single function, one could represent the transition probabilities as a standard multinomial, and P(S|O) using a Maxent model. This may also help with sparseness.

• Environmental model for reinforcement learning

The transition function can also include an action, resulting in a model suitable for representing the environment of a reinforcement agent.

Experiments

The authors trained 4 different types of models to classify lines from Usenet files into one of 4 categories: head, question, answer and tail. They used a set of 24 boolean features. The types of models they trained were: ME-Stateless (non-sequential Maxent), TokenHMM (a standard 4-state fully connected HMM), FeatureHMM (an HMM where the lines i.e. obsevations were replaced by their corresponding features), and the MeMM model described above. They found that the MeMM outperformed the other approaches.

Related papers

The original CRF (Lafferty 2001 Conditional Random Fields) papers, published just one year after this paper, introduces an even more expressive model, and CRFs are now considered state-of-the-art for sequential labeling tasks. For a background on exponential models and maximum entropy, the Berger et al CL 1996 paper that introduced the maximum entropy approach to NLP is suggested. The Ratnaparkhi, 1996 paper on Maxent POS tagging also introduces a closely related model.