Query Expansion With ConceptNet and WordNet An Int
Query Expansion With ConceptNet and WordNet An Int
net/publication/225163223
CITATIONS READS
65 3,795
3 authors, including:
All content following this page was uploaded by Ming-Feng Tsai on 31 May 2014.
1 Introduction
Query expansion has been widely used to deal with paraphrase problem in information
retrieval. The expanded terms may come from feedback documents, target document
collection, or outside knowledge resources [1]. WordNet [2], an electronic lexical da-
tabase, has been employed to many applications [9], where query expansion is an im-
portant one. Voorhees [14] utilized lexical semantic relations in WordNet to expand
queries. Smeaton et al [13] added WordNet synonyms of original query terms with half
of their weights. Liu et al [7] used WordNet to disambiguate word senses of query
terms, and then considered the synonyms, the hyponyms, and the words from defini-
tions for possible additions to a query. Roberto and Paola [10] utilized WordNet to ex-
pand a query and suggested that a good expansion strategy is to add those words that
often co-occur with the words of the query. To deal with short queries of web users,
Moldovan and Mihalcea [8] applied WordNet to improve Internet searches.
In contrast to WordNet, commonsense knowledge was only explored in retrieval in
a few papers. Liu and Lieberman [5] used ConceptNet [4] to expand query with the
related concepts. However, the above work did not make formal evaluation, so that
we were not sure if the effects of introducing common sense are positive or negative.
Hsu and Chen [3] introduced commonsense knowledge into IR by expanding con-
cepts in text descriptions of images with spatially related concepts. Experiments
*
Corresponding author.
H.T. Ng et al. (Eds.): AIRS 2006, LNCS 4182, pp. 1 – 13, 2006.
© Springer-Verlag Berlin Heidelberg 2006
2 M.-H. Hsu, M.-F. Tsai, and H.-H. Chen
showed that their approach was more suitable for precision-oriented tasks and for
“difficult” topics. The expansion of this work was done at document level instead of
query level. Document contributes much larger contextual information than query.
In the past, few papers have touched on the comparison of ConceptNet and Word-
Net in query expansion under the same benchmark. We are interested in what effects
of these two resources have. If we know which resource is more useful in a certain
condition, we are able to improve the retrieval performance further. In this paper, we
design some experiments with evaluation criteria to quantitatively measure WordNet
and ConceptNet in the aspect of query expansion. We employ the same algorithm,
spreading activation [12], to select candidate terms from ConceptNet and WordNet
for the TREC topics 301-450, which were used in TREC-6, TREC-7 and TREC-8. To
compare the intrinsic characteristics of these two resources, we propose three types
of quantitative measurements including discrimination ability, concept diversity, and
retrieval performance.
This paper is organized as follows. In Section 2, we give brief introduction to
WordNet and ConceptNet. The comparison methodology is specified in Section 3.
Section 4 introduces the experiment environment and discusses the experimental re-
sults. Section 5 concludes the remarks.
2.1 WordNet
WordNet appeared in 1993 and has been developed by linguistic experts at Princeton
University’s Cognitive Science Laboratory since 1985. It is a general-purpose know-
ledgebase of words, and it covers most English nouns, adjectives, verbs and adverbs.
WordNet’s structure is a relational semantic network. Each node in the network is a
lexical unit that consists of several synonyms, standing for a specific “sense”. Such
lexical unit is called as ‘synset’ in WordNet terminology. Synsets in WordNet are
linked by a small set of semantic relations such as ‘is-a’ hierarchical relations and
‘part-of’ relations. For its simple structure with words at nodes, WordNet’s success
comes from its ease of use [2][9].
2.2 ConceptNet
ConceptNet is developed by MIT Media Laboratory and is presently the largest com-
monsense knowledgebase [6]. ConceptNet is a relational semantic network that is
automatically generated from about 700,000 English sentences of the Open Mind
Common Sense (OMCS) corpus. Nodes in ConceptNet are compound concepts in the
form of natural language fragments (e.g. ‘food’, ‘buy food’, ‘grocery store’, and ‘at
home’). Because the goal of developing ConceptNet is to cover pieces of common-
sense knowledge to describe the real world, there are 20 kinds of relations categorized
as causal, spatial, functional, etc. ConceptNet has been adopted in many interactive
Query Expansion with ConceptNet and WordNet: An Intrinsic Comparison 3
applications [4]. Hsu and Chen [3] utilized ConceptNet to expand image annotations
and got improvement for some difficult topics. As commonsense knowledge is deeply
context-sensitive, the suitability of ConceptNet for query expansion is still not clear.
WordNet and ConceptNet have several similarities: (1) their structures are both rela-
tional semantic networks; (2) both of them are general-purpose (that is, not domain-
specific) knowledgebase; and (3) concepts in the two resources are both in the form of
natural language. On the other hand, WordNet and ConceptNet differ from each other
in some aspects: (1) as their processes of development differ (manually handcrafted
vs. automatically generated), intuitively WordNet has higher quality and robustness;
(2) while WordNet focuses on formal taxonomies of words, ConceptNet focuses on a
richer set of semantic relations between compound concepts [6]; and (3) WordNet dif-
ferentiates ambiguous meanings of a word as synsets, however, ConceptNet bears
ambiguity of commonsense knowledge in its concepts and relations.
3 Comparison Methodologies
To compare the two knowledgebase in the aspect of query expansion intrinsically, we
perform the same algorithm to expand queries. As WordNet and ConceptNet are both
relational semantic networks, i.e., useful concepts for expansion in the network are
usually those related to the concepts of the query, spreading activation [12] is adopted.
Figure 1 shows the overall procedure of the comparison. Given an original query,
we perform spreading activation on WordNet and ConceptNet, respectively. Then, the
two expanded queries are compared with three quantitative measurements. The first
measurement computes the discrimination ability in information retrieval. The second
measurement calculates the concept diversity in relevant documents. The third di-
rectly evaluates the performance of retrieval, including two typical evaluation criteria
for ad hoc retrieval. All of these measurements are described in Section 3.4.
When we perform spreading activation in a semantic network to expand a query, the
node of activation origin represents the concept of the given query. The activation ori-
gin is the first to be activated, with an initial activation score (e.g., 1.0). Next, nodes
one link away from the activation origin are activated, then two links away, and so on.
Equation (1) shown below determines the activation score of node j by three fac-
≦
tors: (i) a constant Cdd 1 (e.g., 0.5), which is called distance discount that causes a
node closer to the activation origin to get a higher activation score; (ii) the activation
score of node i; (iii) W(i,j), the weight of the link from i to j. Different relations in the
semantic network are of different weights. Neighbor(j) represents the nodes connected
to node j.
= .
Activation_score( j ) Cdd
i∈Neighbor( j )
.
∑ Activation_score(i) W(i, j ) (1)
Since most traditional IR systems are of bag-of-words model, we select the top N
words with the higher activation scores as the expanded query. For a word w, its acti-
vation score is the sum of scores of the nodes (i.e., synsets in WordNet) that contain w.
4 M.-H. Hsu, M.-F. Tsai, and H.-H. Chen
3.1 Pre-processing
Each query was lemmatized and POS-tagged by Brill tagger. Stop-words were re-
moved and each of the remaining words with POS-tags was considered as a concept
at the following stages.
Since each node in WordNet is a synset that contains synonyms of certain sense,
spreading activation in WordNet is surely performed on the unit of synset. Because
ConceptNet covers most relations in WordNet, we determine the weights of relations
in WordNet, shown in Table 1, by referring to the settings in ConceptNet. For each
concept (a word with POS-tag) in the query, we choose its most frequent sense (syn-
set) as the activation origin from the corresponding POS. In other words, we do not
disambiguate the sense of query terms in this paper for simplicity.
Query Expansion with ConceptNet and WordNet: An Intrinsic Comparison 5
The following proposes three types of measurements to investigate the intrinsic dif-
ferences between WordNet and Concept. They provide different viewpoints for the
comparison.
(1) Discrimination Ability (DA). Discrimination ability is used to measure how
precisely a query describes the information need. In IR, the inverse document fre-
quency (IDF) of a term denotes if it occurs frequently in individual documents but
rarely in the remainder of the collection. For IR systems as the state of the art, dis-
crimination ability of a term can be estimated by its IDF value. Hence the discrimina-
tion ability of a query is measured and contributed by the IDFs of the terms in the
query. For a query q composed of n query terms (q1, q2, …, qn), we define its dis-
crimination ability (DA) as follows.
n
∑ log( df(q ) )
1 NC
DA(q) = (2)
n i =1 i
where NC is the number of documents in a collection, and df(qi) is the document fre-
quency of query term qi.
(2) Concept Diversity (CD). This measurement helps us observe the concept di-
versity of an expanded query, relative to the relevant documents. That is, we measure
how much an expanded query covers the concepts occurring in the relevant docu-
.
ments. Let tm( ) denote the function that maps the parameter (a document or a
query) to the set of its index terms. Let {dq(1), dq(2), …, dq(m)} denote the set of m
documents which are relevant to the query q in the collection. The concept diversity
(CD) of a query q is defined as follows.
m
| tm(q) ∩ tm(d q (i ) ) |
∑
1
CD( q) = (3)
m i =1
| tm(d q (i ) ) |
We adopted the topics and the document collections in the ad hoc track of TREC-6,
TREC-7 and TREC-8 as the experimental materials for the comparison. There are
556,077 documents in the collection of TREC-6 and 528,155 documents in TREC-7
and in TREC-8. Only the “title” part was used to simulate short query, since web
6 M.-H. Hsu, M.-F. Tsai, and H.-H. Chen
users often submit short queries to search engines. There are totally 150 topics with
identifiers 301-450. However, 4 of them (i.e., topics 312, 379, 392 and 423) are un-
able to be expanded by spreading activation either in WordNet or in ConceptNet, so
that these 4 topics are neglected in the experiments. For each short query, the top 100
words with the higher activation scores form the expanded query. The IR system
adopted for the measurement of retrieval performance is Okapi’s BM25 [11]. The re-
trieval performance is measured on the top 1000 documents for each topic.
Figures 2, 3, 4, and 5 show the results of the quantitative measurements, where the
x-axis represents topic number, and 301-350, 351-400, and 401-450 are topics of
TREC-6, TREC-7 and TREC-8, respectively. To compare the differences between
WordNet and ConceptNet, the result presented for each topic is the difference be-
tween the two expanded queries, i.e., the measurement of the WordNet-expanded
query subtracts that of the ConceptNet-expanded query.
Difference of DA (W-C)
6
-1
310 320 330 340 350 360 370 380 390 400 410 420 430 440 450
Topic Number
0.05
Difference of CD (W-C)
0.04
0.03
0.02
0.01
-0.01
-0.02
-0.03
-0.04
-0.05
310 320 330 340 350 360 370 380 390 400 410 420 430 440 450
Topic Number
0.1
-0.1
-0.2
-0.3
310 320 330 340 350 360 370 380 390 400 410 420 430 440 450
Topic Number
The average concept diversity (CD) is 0.037 and 0.048 for the WordNet-expanded
and the ConceptNet-expanded queries, respectively. In contrast to the result of dis-
crimination ability, Figure 3 shows that ConceptNet-expanded queries have higher
8 M.-H. Hsu, M.-F. Tsai, and H.-H. Chen
0.4
0.3
0.2
0.1
-0.1
-0.2
-0.3
-0.4
310 320 330 340 350 360 370 380 390 400 410 420 430 440 450
Topic Number
concept diversity than WordNet-expanded ones do. Note that the concept diversity of
an expanded query is computed according to the relevant documents. As the terms in
ConceptNet-expanded queries are usually more general than those in WordNet-
expanded queries, Figure 3 shows that ConceptNet-expanded queries cover more of the
concepts that would usually co-occur with the kernel words in the relevant documents.
We call the concepts that co-occur with the kernel words as cooperative concepts.
Expanding a short query with the kernel words will help IR systems to find more
relevant documents. On the other hand, co-occurrence of the cooperative concepts and
the kernel words will help the IR system to rank truly relevant documents higher than
those containing noise. Here we take topic 335 (“adoptive biological parents”) as an
example to illustrate this idea. The kernel words of this topic may be “pregnancy”,
“surrogate”, etc, and the cooperative concepts may be “child”, “bear”, etc. Of these,
“surrogate” and “child” are suggested by WordNet and ConceptNet, respectively. The
pair (child, surrogate) has stronger collocation in the relevant documents than in the
irrelevant documents. The detail will be discussed in Section 4.2.
The overall retrieval performances of the WordNet-expanded queries in AP and
P@20 are 0.016 and 0.0425, respectively. For the ConceptNet-expanded queries, the
performances are 0.019 and 0.0438, in AP and P@20, respectively. These retrieval
performances are low because the expanded queries are formed by the top 100 words
with the higher activation scores. The simple expansion method introduces too much
noise. Figure 4 and Figure 5 show the differences of AP and of P@20 for each topic.
We observed that WordNet-expanded queries perform better for some topics, but
ConceptNet-expanded queries perform better for some other topics. While WordNet
and ConceptNet are different in discrimination ability (Figure 2) and in concept diver-
sity (Figure 3), the two resources can complement each other in the task of ad hoc
retrieval. Hence, we made further experiments in the following subsection.
Query Expansion with ConceptNet and WordNet: An Intrinsic Comparison 9
0.24
0.22
0.2
MAP
0.18
0.16
0.14 WC+CC
CC
WC
Original
0.12
1 2 3 4 5 6 7 8
Degree
Fig. 6. Performances of the four expansion strategies vs. the weights of the original query term
10 M.-H. Hsu, M.-F. Tsai, and H.-H. Chen
0.7 Original
WC+CC
CC
0.6 WC
0.5
Average Precision
0.4
0.3
0.2
0.1
0
302 306 307 308 310 319 335 336
Topic Number
While Figure 6 shows the result averaged over all topics of TREC-6, Figure 7
shows some more strong evidences supporting the argument that WordNet and Con-
ceptNet can complement each other. Using different expansion strategies with the de-
gree 6, the performances (AP) of eight topics are presented. While CC only or WC
only improve the performance of each of the eight topics, it’s obvious that all the
eight topics benefit from the combination of WC and CC. Therefore, the overall im-
provement (refer to Figure 6) of combination of WC and CC is mostly exhibited in
the eight topics.
We verify the complementary of WordNet and ConceptNet, i.e., frequent co-
occurrence of WC terms and CC terms in relevant documents, by the following way.
For each pair of CC term tc and WC term tw, we calculate LRP(tc, tw) using Equation
Query Expansion with ConceptNet and WordNet: An Intrinsic Comparison 11
(4). LRP(tc, tw) is a value of logarithm of the ratio of two conditional probabilities: (1)
the co-occurrence probability of tc and tw in the relevant documents; and (2) the co-
occurrence probability of tc and tw in the irrelevant documents.
P(tc, tw | R)
LRP(tc, tw) = log (4)
P(tc, tw | IRR)
where R and IRR represent relevant and irrelevant documents, respectively.
Table 2 shows the title, the CC terms, the WC terms and the term pairs having high
LRP values for each topic in Figure 7. The term pairs with high LRP in the eight top-
ics are the major evidences to support that combination of WC and CC is effective as
shown in Figures 6 and 7. Note that the pairs (child, surrogate), (life, surrogate) and
(human, surrogate) of topic 335 have high LRP values. They also confirm the idea of
kernel words and cooperative concepts mentioned in Section 4.1.
Acknowledgements
Research of this paper was partially supported by National Science Council, Taiwan,
under the contracts NSC94-2752-E-001-001-PAE and NSC95-2752-E-001-001-PAE.
References
1. Baeza-Yates, Ricardo and Ribeiro-Neto, Berthier: Modern Information Retrieval, Addi-
son-Wesley (1999).
2. Fellbaum, C. (ed.). WordNet: An Electronic Lexical Database. MIT Press (1998).
3. Hsu, Ming-Hung and Chen, Hsin-Hsi: Information Retrieval with Commonsense Knowl-
edge. In: Proceedings of 29th ACM SIGIR International Conference on Research and De-
velopment in Information Retrieval (2006).
4. Lieberman, H., Liu, H., Singh, P., and Barry, B. Beating Common Sense into Interactive
Applications. AI Magazine 25(4) (2004) 63-76.
5. Liu, H. and Lieberman, H: Robust Photo Retrieval Using World Semantics. In: Proceed-
ings of LREC2002 Workshop: Using Semantics for IR (2002) 15-20.
6. Liu, H. and Singh, P.: ConceptNet: A Practical Commonsense Reasoning Toolkit. BT
Technology Journal 22(4) (2004) 211-226.
7. Liu, S., Liu, F., Yu, C.T., and Meng, W.: An Effective Approach to Document Retrieval
via Utilizing WordNet and Recognizing Phrases. In: Proceedings of the 27th Annual
International ACM SIGIR Conference on Research and Development in Information Re-
trieval (2004) 266-272.
8. Moldovan, D.I. and Mihalcea, R.: Using WordNet and Lexical Operators to Improve
Internet Searches. IEEE Internet Computing 4(1) (2000) 34-43.
9. Morato, Jorge, Marzal, Miguel Ángel, Lloréns, Juan and Moreiro, José.: WordNet Appli-
cations. In: Proceedings of International Conference of the Global WordNet Association
(2004) 270-278.
10. Navigli, Roberto and Velardi, Paola: An Analysis of Ontology-based Query Expansion
Strategies. In: Proceedings of Workshop on Adaptive Text Extraction and Mining at the
14th European Conference on Machine Learning (2003).
Query Expansion with ConceptNet and WordNet: An Intrinsic Comparison 13
11. Robertson, S.E., Walker, S. and Beaulieu, M.: Okapi at TREC-7: Automatic Ad Hoc, Fil-
tering, VLC and Interactive. In: Proceedings of the Seventh Text Retrieval Conference
(1998) 253-264.
12. Salton, G. and Buckley, C.: On the Use of Spreading Activation Methods in Automatic In-
formation Retrieval. In: Proceedings of the 11th CM-SIGIR Conference on Research and
Development in Information Retrieval (1988) 147-160.
13. Smeaton, Alan F., Kelledy, Fergus, and O'Donell, Ruari: TREC-4 Experiments at Dublin
City University: Thresholding Posting Lists, Query Expansion with WordNet and POS
Tagging of Spanish. In: Proceedings of TREC-4 (1994) 373-390.
14. Voorhees, Ellen M.: Query Expansion Using Lexical-Semantic Relations. In: Proceedings
of the 17th Annual ACM SIGIR Conference on Research and Development in Information
Retrieval (1994) 61-69.