Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence
Maximum Entropy Context Models for Ranking
Biographical Answers to Open-Domain Definition Questions
Alejandro Figueroa John Atkinson
Yahoo! Research Latin America, Department of Computer Sciences
Av. Blanco Encalada 2120, Universidad de Concepción
4th floor, Santiago, Chile Concepción, Chile
afi
Abstract and/or knowledge base (KB) articles such as W ikipedia
(Katz et al. 2007), Merriam-Webster dictionary (Hilde-
In the context of question-answering systems, there are
several strategies for scoring candidate answers to def-
brandt, Katz, and Lin 2004), and W ordN et (Echihabi et al.
inition queries including centroid vectors, bi-term and 2003; Wu et al. 2005). The selection stage entails an exper-
context language models. These techniques use only imental threshold that cuts off candidate answers, and the
positive examples (i.e., descriptions) when building summarisation applies a redundancy removal strategy.
their models. In this work, a maximum entropy based Nowadays, there are two promising trends for scoring
extension is proposed for context language models so methods: one is based on Language Models (LMs) which
as to account for regularities across non-descriptions mainly rates biographical1 answers (Chen, Zhon, and Wang
mined from web-snippets. Experiments show that this 2006), whereas the other is based on discriminant mod-
extension outperforms other strategies increasing the els which distinguishes short general descriptions (Androut-
precision of the top five ranked answers by more
sopoulos and Galanis 2005; Lampouras and Androutsopou-
than 5%. Results suggest that web-snippets are a cost-
efficient source of non-descriptions, and that some rela- los 2009).
tionships extracted from dependency trees are effective
to mine for candidate answer sentences. Related Work
There are numerous techniques designed to cope with def-
Introduction inition queries. One of the most prominent involves the ex-
Generally speaking, definition questions are found in the traction of nuggets from KBs, and their further projection
form of strings like “What is a <concept>?” and “What into the set of candidate answers (Cui, Kan, and Xiao 2004;
does <concept> mean?”. This specific class of query cov- Sacaleanu, Neumann, and Spurk 2008). More specifically,
ers indeed more than 20% of the inputs within query logs, these nuggets are used for learning frequencies of words that
hence their research relevance (Rose and Levinson 2004). correlate with the definiendum, in which a centroid vector is
Unlike other kinds of question types, definition questions formed so that sentences can be scored according to their
expect a list of pieces of information (nuggets) about the cosine distance to this vector. The performance of this kind
concept being defined (a.k.a. the definiendum) as an answer. of strategy, however, falls into a steep drop when there is not
More precisely, the response is composed of, but not exclu- enough coverage for the definiendum across KBs (Zhang et
sively, of relevant biographical facts. A question-answering al. 2005; Han, Song, and Rim 2006). In other words, it fails
(QA) system must therefore process several documents so to capture correct answers verbalised with words having low
as to uncover this collection of nuggets. To illustrate this, correlation with the definiendum across KBs, generating a
a good response to the question “What is ZDF?” would in- less diverse outcome and so decreasing the coverage.
volve -sentences embodying- facts such as “Second German In general, centroid vector-based approaches rate candi-
Television”, “public service” and “based in Mainz”. date answers in congruence with the degree in which their
A general view of the question-answering process points respective words typify the definiendum. The underlying
to a pipeline commonly composed of the following steps: principle is known as the Distributional Hypothesis (Har-
candidate answer retrieval, ranking, selection and summari- ris 1954; Firth 1957) in which KBs yield reliable charac-
sation. In the first step, candidate answers are fetched from a terising terms. An additional aspect that makes this method
target corpus, and singled out by some definiendum match- less attractive is that term co-occurrences do not necessarily
ing technique and/or a fixed set of definition patterns. The guarantee a meaningful syntactic dependency, causing the
second phase typically involves a scoring function based on selection of manifold spurious answers.
the accuracy of the previous alignments (H. Joho and M. In order to address this issue, (Chen, Zhon, and Wang
Sanderson 2000; 2001), keywords learnt from web-snippets 1
The term “biographical”, in a broader sense, is used as a
Copyright c 2011, Association for the Advancement of Artificial synonym of content found in encyclopedias for different sorts of
Intelligence (www.aaai.org). All rights reserved. definienda such as companies and countries.
1173
, 2006) extended the centroid vector based method to in- attributes extracted from a web corpus. In addition, SVM
clude word dependencies. First, they learn frequent stemmed classifiers have also been exploited with surface features to
co-occurring terms derived from top-ranked web snippets, rank sentences and paragraphs about technical terms (Xu et
which were fetched via a purpose-built query reformula- al. 2005). Incidentally, (Androutsopoulos and Galanis 2005;
tion method. By retaining their original order, these words Lampouras and Androutsopoulos 2009) automatically gath-
are then used for building an ordered centroid vector rep- ered and annotated training material from the Internet,
resentation of the sentences, wherewith unigram, bigram whereas (Xu et al. 2005) manually tagged a corpus orig-
and biterm LMs were constructed. Experiments indicate that inated from an Intranet. Nevertheless, these techniques do
biterm LMs significantly improve the performance in rela- not benefit from context models.
tion to the original centroid vector method. Thus, the flexi-
bility and relative position of lexical terms are observed to Maximum Entropy Context Models for
encapsulate shallow information about their syntactic rela- Definitional Questions
tion (Belkin and Goldsmith 2002).
A related work (Figueroa and Atkinson 2009) built con- In a nutshell, our work extends context models to account
textual models to tackle the narrow coverage provided by for regularities across non-descriptions, which are collected
KBs. Unlike previous methods, context models mine sen- from sentences extracted from web-snippets. This collection
tences from all W ikipedia pages that align the pre-defined of sentences is limited in size and takes advantage of context
rules in table 1. These matched sentences are then clustered models splitting the positive data into small training sets. A
in accordance with their context indicator (e.g., “author”, portion of these web sentences was manually labeled so as to
“player” and “song”), which is generally given by the root obtain non-descriptions, while an extra proportion of nega-
of the dependency tree: tive samples was automatically tagged by a LM built on top
of these manually annotated samples. Finally, a Maximum
author:
Entropy (ME) Model is generated for each context, where-
CONCEPT is an accomplished author.
CONCEPT, a bestselling childrens author. with unseen testing instances of candidate answers are rated.
player:
CONCEPT is a former ice hockey player. Corpus Acquisition
CONCEPT, a jazz trumpet player. In our approach, negative and positive training sets are ex-
song: tracted differently. The former was acquired entirely from
CONCEPT, the title of a song for voice and piano. the Web (i.e., web snippets), while the latter came from
CONCEPT is a rap song about death. W ikipedia and web snippets.
Next, an n-gram (n = 5) LM is constructed for each This web training data is obtained by exploiting a defini-
context, in which unseen instances bearing the same con- tion QA system operating on web-snippets (Figueroa 2008).
text indicator are rated. This constituted a key difference to In order to generate the final outcome, the model takes ad-
earlier techniques, which predicate largely on knowledge re- vantage of conventional properties such as word correla-
garding each particular definiendum found across KBs. An- tions, and the manually-built definition patterns shown in
other advantage of context models is their bias in favour of table 1, and redundancy removal tasks. The average F(3)-
candidate answers carrying more relevant indicators across score of the model is 0.51 on a small development set, and
both KBs and candidate answers (e.g., “band” in the event this system ran for more than five million definienda origi-
of the definiendum “The Rolling Stones”). This method ex- nated from a combination of W ikipedia and F reeBase2 ,
ploits contextual semantic and syntactic similarities across randomly selected. This model collects a group of diverse
lexicalised dependency trees of matched sentences. As a re- and unlabelled web snippets bearing lexical ambiguities
sult, context models cooperate on improving precision and with genuine definitions, which would discard “easy-to-
ranking with respect to bi-term LMs. detect” non-descriptions. Overall, this corpus involves about
One common drawback between previous strategies (Cui, 23,500,000 web snippets concerning about 3,700,000 differ-
Kan, and Xiao 2004; Chen, Zhon, and Wang 2006; Figueroa ent definienda, for which at least one sentence was produced
and Atkinson 2009) arises from the absence of informa- by the system. Note that web-snippets were preferred to
tion about non-descriptions, accounting solely for posi- full-documents in order to avoid their costly processing, and
tive samples. This has an impact on the ranking as many due to the fact that they convey localised context about the
words, bi-terms or dependency paths that are predominant definiendum. The average length of sentences mined from
in definitions can also appear within non-descriptions (e.g. web-snippets was 125 characters.
band→metal in “definiendum is a great metal band.”).
As for discriminant models for definition ranking, max- Extracting Positive Examples
imum entropy models have been preferred as (Fahmi and First of all, unlike previous methods (Xu et al. 2005;
Bouma 2006) showed that for a language different from Androutsopoulos and Galanis 2005; Fahmi and Bouma
English they achieve good performance. Other QA meth- 2006; Lampouras and Androutsopoulos 2009), entries from
ods (Miliaraki and Androutsopoulos 2004; Androutsopoulos W ikipedia were taken into consideration when acquiring
and Galanis 2005) have also been promising to score 250- a positive training set. These are then split into sentences
characters open-domain general definitions using a Sup-
2
port Vector Machine (SVM) trained with mostly surface http://www.freebase.com/
1174
Maximum Entropy Context Models for Ranking
Biographical Answers to Open-Domain Definition Questions
Alejandro Figueroa John Atkinson
Yahoo! Research Latin America, Department of Computer Sciences
Av. Blanco Encalada 2120, Universidad de Concepción
4th floor, Santiago, Chile Concepción, Chile
afi
Abstract and/or knowledge base (KB) articles such as W ikipedia
(Katz et al. 2007), Merriam-Webster dictionary (Hilde-
In the context of question-answering systems, there are
several strategies for scoring candidate answers to def-
brandt, Katz, and Lin 2004), and W ordN et (Echihabi et al.
inition queries including centroid vectors, bi-term and 2003; Wu et al. 2005). The selection stage entails an exper-
context language models. These techniques use only imental threshold that cuts off candidate answers, and the
positive examples (i.e., descriptions) when building summarisation applies a redundancy removal strategy.
their models. In this work, a maximum entropy based Nowadays, there are two promising trends for scoring
extension is proposed for context language models so methods: one is based on Language Models (LMs) which
as to account for regularities across non-descriptions mainly rates biographical1 answers (Chen, Zhon, and Wang
mined from web-snippets. Experiments show that this 2006), whereas the other is based on discriminant mod-
extension outperforms other strategies increasing the els which distinguishes short general descriptions (Androut-
precision of the top five ranked answers by more
sopoulos and Galanis 2005; Lampouras and Androutsopou-
than 5%. Results suggest that web-snippets are a cost-
efficient source of non-descriptions, and that some rela- los 2009).
tionships extracted from dependency trees are effective
to mine for candidate answer sentences. Related Work
There are numerous techniques designed to cope with def-
Introduction inition queries. One of the most prominent involves the ex-
Generally speaking, definition questions are found in the traction of nuggets from KBs, and their further projection
form of strings like “What is a <concept>?” and “What into the set of candidate answers (Cui, Kan, and Xiao 2004;
does <concept> mean?”. This specific class of query cov- Sacaleanu, Neumann, and Spurk 2008). More specifically,
ers indeed more than 20% of the inputs within query logs, these nuggets are used for learning frequencies of words that
hence their research relevance (Rose and Levinson 2004). correlate with the definiendum, in which a centroid vector is
Unlike other kinds of question types, definition questions formed so that sentences can be scored according to their
expect a list of pieces of information (nuggets) about the cosine distance to this vector. The performance of this kind
concept being defined (a.k.a. the definiendum) as an answer. of strategy, however, falls into a steep drop when there is not
More precisely, the response is composed of, but not exclu- enough coverage for the definiendum across KBs (Zhang et
sively, of relevant biographical facts. A question-answering al. 2005; Han, Song, and Rim 2006). In other words, it fails
(QA) system must therefore process several documents so to capture correct answers verbalised with words having low
as to uncover this collection of nuggets. To illustrate this, correlation with the definiendum across KBs, generating a
a good response to the question “What is ZDF?” would in- less diverse outcome and so decreasing the coverage.
volve -sentences embodying- facts such as “Second German In general, centroid vector-based approaches rate candi-
Television”, “public service” and “based in Mainz”. date answers in congruence with the degree in which their
A general view of the question-answering process points respective words typify the definiendum. The underlying
to a pipeline commonly composed of the following steps: principle is known as the Distributional Hypothesis (Har-
candidate answer retrieval, ranking, selection and summari- ris 1954; Firth 1957) in which KBs yield reliable charac-
sation. In the first step, candidate answers are fetched from a terising terms. An additional aspect that makes this method
target corpus, and singled out by some definiendum match- less attractive is that term co-occurrences do not necessarily
ing technique and/or a fixed set of definition patterns. The guarantee a meaningful syntactic dependency, causing the
second phase typically involves a scoring function based on selection of manifold spurious answers.
the accuracy of the previous alignments (H. Joho and M. In order to address this issue, (Chen, Zhon, and Wang
Sanderson 2000; 2001), keywords learnt from web-snippets 1
The term “biographical”, in a broader sense, is used as a
Copyright c 2011, Association for the Advancement of Artificial synonym of content found in encyclopedias for different sorts of
Intelligence (www.aaai.org). All rights reserved. definienda such as companies and countries.
1173
, 2006) extended the centroid vector based method to in- attributes extracted from a web corpus. In addition, SVM
clude word dependencies. First, they learn frequent stemmed classifiers have also been exploited with surface features to
co-occurring terms derived from top-ranked web snippets, rank sentences and paragraphs about technical terms (Xu et
which were fetched via a purpose-built query reformula- al. 2005). Incidentally, (Androutsopoulos and Galanis 2005;
tion method. By retaining their original order, these words Lampouras and Androutsopoulos 2009) automatically gath-
are then used for building an ordered centroid vector rep- ered and annotated training material from the Internet,
resentation of the sentences, wherewith unigram, bigram whereas (Xu et al. 2005) manually tagged a corpus orig-
and biterm LMs were constructed. Experiments indicate that inated from an Intranet. Nevertheless, these techniques do
biterm LMs significantly improve the performance in rela- not benefit from context models.
tion to the original centroid vector method. Thus, the flexi-
bility and relative position of lexical terms are observed to Maximum Entropy Context Models for
encapsulate shallow information about their syntactic rela- Definitional Questions
tion (Belkin and Goldsmith 2002).
A related work (Figueroa and Atkinson 2009) built con- In a nutshell, our work extends context models to account
textual models to tackle the narrow coverage provided by for regularities across non-descriptions, which are collected
KBs. Unlike previous methods, context models mine sen- from sentences extracted from web-snippets. This collection
tences from all W ikipedia pages that align the pre-defined of sentences is limited in size and takes advantage of context
rules in table 1. These matched sentences are then clustered models splitting the positive data into small training sets. A
in accordance with their context indicator (e.g., “author”, portion of these web sentences was manually labeled so as to
“player” and “song”), which is generally given by the root obtain non-descriptions, while an extra proportion of nega-
of the dependency tree: tive samples was automatically tagged by a LM built on top
of these manually annotated samples. Finally, a Maximum
author:
Entropy (ME) Model is generated for each context, where-
CONCEPT is an accomplished author.
CONCEPT, a bestselling childrens author. with unseen testing instances of candidate answers are rated.
player:
CONCEPT is a former ice hockey player. Corpus Acquisition
CONCEPT, a jazz trumpet player. In our approach, negative and positive training sets are ex-
song: tracted differently. The former was acquired entirely from
CONCEPT, the title of a song for voice and piano. the Web (i.e., web snippets), while the latter came from
CONCEPT is a rap song about death. W ikipedia and web snippets.
Next, an n-gram (n = 5) LM is constructed for each This web training data is obtained by exploiting a defini-
context, in which unseen instances bearing the same con- tion QA system operating on web-snippets (Figueroa 2008).
text indicator are rated. This constituted a key difference to In order to generate the final outcome, the model takes ad-
earlier techniques, which predicate largely on knowledge re- vantage of conventional properties such as word correla-
garding each particular definiendum found across KBs. An- tions, and the manually-built definition patterns shown in
other advantage of context models is their bias in favour of table 1, and redundancy removal tasks. The average F(3)-
candidate answers carrying more relevant indicators across score of the model is 0.51 on a small development set, and
both KBs and candidate answers (e.g., “band” in the event this system ran for more than five million definienda origi-
of the definiendum “The Rolling Stones”). This method ex- nated from a combination of W ikipedia and F reeBase2 ,
ploits contextual semantic and syntactic similarities across randomly selected. This model collects a group of diverse
lexicalised dependency trees of matched sentences. As a re- and unlabelled web snippets bearing lexical ambiguities
sult, context models cooperate on improving precision and with genuine definitions, which would discard “easy-to-
ranking with respect to bi-term LMs. detect” non-descriptions. Overall, this corpus involves about
One common drawback between previous strategies (Cui, 23,500,000 web snippets concerning about 3,700,000 differ-
Kan, and Xiao 2004; Chen, Zhon, and Wang 2006; Figueroa ent definienda, for which at least one sentence was produced
and Atkinson 2009) arises from the absence of informa- by the system. Note that web-snippets were preferred to
tion about non-descriptions, accounting solely for posi- full-documents in order to avoid their costly processing, and
tive samples. This has an impact on the ranking as many due to the fact that they convey localised context about the
words, bi-terms or dependency paths that are predominant definiendum. The average length of sentences mined from
in definitions can also appear within non-descriptions (e.g. web-snippets was 125 characters.
band→metal in “definiendum is a great metal band.”).
As for discriminant models for definition ranking, max- Extracting Positive Examples
imum entropy models have been preferred as (Fahmi and First of all, unlike previous methods (Xu et al. 2005;
Bouma 2006) showed that for a language different from Androutsopoulos and Galanis 2005; Fahmi and Bouma
English they achieve good performance. Other QA meth- 2006; Lampouras and Androutsopoulos 2009), entries from
ods (Miliaraki and Androutsopoulos 2004; Androutsopoulos W ikipedia were taken into consideration when acquiring
and Galanis 2005) have also been promising to score 250- a positive training set. These are then split into sentences
characters open-domain general definitions using a Sup-
2
port Vector Machine (SVM) trained with mostly surface http://www.freebase.com/
1174
