23.2.3 Answer Processing
The final stage of question answering is to extract a specific answer from the passage, so as to be able to present the user with an answer like 300 million to the question "What is the current population of the United States".
Two classes of algorithms have been applied to the answer extraction task, one based on answer-type pattern extraction and one based on N-gram tiling.
In the pattern extraction methods for answer processing, we use information about the expected answer type together with regular expression patterns. For example, for questions with a HUMAN answer type we run the answer type or named entity tagger on the candidate passage or sentence, and return whatever entity is labeled with type HUMAN. Thus in the following examples, the underlined named entities are extracted from the candidate answer passages as the answer to the HUMAN and DISTANCE-QUANTITY questions:
“Who is the prime minister of India”
Manmohan Singh, Prime Minister of India, had told left leaders that the
deal would not be renegotiated.
“How tall is Mt. Everest?”
The official height of Mount Everest is $ \underline{\text{29035 feet}} $
Unfortunately, the answers to some questions, such as DEFINITION questions, don’t tend to be of a particular named entity type. For some questions, then, instead of using answer types, we use handwritten regular expression patterns to help extract the answer. These patterns are also useful in cases where a passage contains multiple examples of the same named entity type. Fig. 23.11 shows some patterns from Pasca (2003) for the question phrase (QP) and answer phrase (AP) of definition questions.
The patterns are specific to each question type, and can either be written by hand or learned automatically.
The automatic pattern learning method of Ravichandran and Hovy (2002), Echihabi et al. (2005), for example, makes use of the pattern-based methods for relation extraction.
| Pattern | Question | Answer |
| --- | --- | --- |
| <AP> such as <QP><QP> (an <AP>) | What is autism? What is a caldera? | ", $ \underline{\text{developmental disorders}} $ such as autism" "the Long Valley caldera, a $ \underline{\text{volcanic crater}} $ 19 miles long" |
| | | |
tion we introduced in Ch. 20 and Ch. 22 (Brin, 1998; Agichtein and Gravano, 2000). The goal of the pattern learning method is to learn a relation between a particular answer type such as YEAR-OF-BIRTH, and a particular aspect of the question, in this case the name of the person whose birth year we want. We are thus trying to learn patterns which are good cues for a relation between two phrases (PERSON-NAME/YEAR-OF-BIRTH, or TERM-TO-BE-DEFINED/DEFINITION, etc). This task is thus very similar to the task of learning hyponym/hyponym relations between WordNet synsets introduced in Ch. 20, or learning ACE relations between words from Ch. 22. Here is a sketch of
the algorithm as applied to question-answer relation extraction:
1. For a given relation between two terms (i.e. person-name $ \rightarrow $year-of-birth), we start with a hand-built list of correct pairs (e.g., “gandhi:1869”, “mozart:1756”, etc).
2. Now query the Web with instances of these pairs (e.g., "gandhi" and "1869", etc) and examine the top X returned documents.
3. Break each document into sentences, and keep only sentences containing both terms (e.g., PERSON-NAME and BIRTH-YEAR).
4. Extract a regular expression pattern representing the words and punctuation that occur between and around the two terms.
5. Keep all patterns that are sufficiently high-precision.
In Ch. 20 and Ch. 22 we discussed various ways to measure accuracy of the patterns. A method used in question-answer pattern matching is to keep patterns which are high-precision. Precision is measured by performing a query with only the question terms, but not the answer terms (i.e. query with just "gandhi" or "mozart"). We then run the resulting patterns on the sentences from the document, and extract a birth-date. Since we know the correct birth-date, we can compute the percentage of times this pattern produced a correct birthdate. This percentage is the precision of the pattern.
For the YEAR-OF-BIRTH answer type, this method learns patterns like the following:
$$
$$ \begin{array}{l}\text{
$$ \begin{aligned}
These two methods, named entity detection and question-answer pattern extraction, are still not sufficient for answer extraction. Not every relation is signaled by unambiguous surrounding words or punctuation, and often multiple instances of the same named-entity type occur in the answer passages. The most successful answer-extraction method is thus to combine all these methods, using them together with other information as features in a classifier that ranks candidate answers. We extract potential answers using named entities or patterns or even just looking at every sentence returned from passage retrieval, and rank them using a classifier with features like the following:
Answer type match: True if the candidate answer contains a phrase with the correct answer type.
Pattern match: The identity of a pattern that matches the candidate answer.
Number of matched question keywords: How many question keywords are contained in the candidate answer.
Keyword distance: The distance between the candidate answer and query keywords (measured in average number of words, or as the number of keywords that occur in the same syntactic phrase as the candidate answer.
Novelty factor: True if at least one word in the candidate answer is novel, i.e. not in the query.
Apposition features: True if the candidate answer is an appositive to a phrase containing many question terms. Can be approximated by the number of question terms separated from the candidate answer through at most three words and one comma Pasca (2003).
Punctuation location: True if the candidate answer is immediately followed by a comma, period, quotation marks, semicolon, or exclamation mark.
Sequences of question terms: The length of the longest sequence of question terms that occurs in the candidate answer.
An alternative approach to answer extraction, used solely in web search, is based on N-gram tiling, sometimes called the redundancy-based approach (Brill et al., 2002; Lin, 2007). This simplified method begins with the snippets returned from the web search engine, produced by a reformulated query. In the first step of the method, N-gram mining, every unigram, bigram, and trigram occurring in the snippet is extracted and weighted. The weight is a function of the number of snippets the N-gram occurred in, and the weight of the query reformulation pattern that returned it. In the N-gram filtering step, N-grams are scored by how well they match the predicted answer type. These scores are computed by hand-written filters built for each answer type. Finally, an N-gram tiling algorithm concatenates overlapping N-gram fragments into longer answers. A standard greedy method is to start with the highest-scoring candidate and try to tile each other candidate with this candidate. The best scoring concatenation is added to the set of candidates, the lower scoring candidate is removed, and the process continues until a single answer is built.
For any of these answer extraction methods, the exact answer phrase can just be presented to the user by itself. In practice, however, users are rarely satisfied with an unadorned number or noun as an answer; they prefer to see the answer accompanied by enough passage information to substantiate the answer. Thus we often give the user an entire passage with the exact answer inside it highlighted or boldfaced.