Combining General Hand-Made and Automatically Constructed Thesauri for Query Expansion in Information Retrieval

1 Introduction

The task of the information retrieval system is to match the query against the document collection and return relevant documents to the user. Retrieval performance is usually express in terms of recall, the proportion of relevant document retrieved, and precision, the propor­ tion of retrieved document that is relevant. Whereas a perfect retrieval run will have a value of 1.0 for. both recall and precision, in practice precision and recall are inversely related.

A critical problem in informat ion retrieval is the case of different words being used to describe the same thing, either in queries or in documents. This require some kind of knowledge base which can equate or relate the terms used in language, i.e., a thesaurus. A thesaurus is a data structure which groups synonymous terms and relates them as either broader or narrower. A thesaurus can be used to expand a query to include all synonymous or related terms. This method has been known as query expansion method [Schutze and Pederson, 1997].

WordNet is currently the most large, hand-crafted, general-purpose, machine-readable, and publically avail­ able thesaurus. It is the product of a research project at Princeton University which has attempted to model the lexical knowledge of English [Miller, 1990]. WordNet has been used in numerous natural language process­ ing, such as semantic tagging [Segond et al., 97], word sense disambiguation [Resnik, 1995a], text categoriza­ tion [Gomez-Hidalgo and Rodriguez, 1997], information extraction [Chai and Biermann, 1997], and so on with considerable success. However, the use of WordNet in information retrieval have not been very successful.

Two sets of experiments using the TREC collection were performed to investigate the effectiveness of using WordNet for query expansion by Voorhees [1994]. The first set used handpicked synsets and the second set ex­ tends the expansion strategy to include automatically selecting the starting synsets. When the concepts were chosen manually, her method could improve the retrieval effectiveness for short queries, but failed to improve the retrieval effectiveness for long queries. When the con­ cepts were chosen automatically, none of the expansion methods produced significant improvement as compared with an unexpanded run. She further tried to use Word­ Net as a tool for word sense disambiguation [Voorhees, 1993] and applied it to text retrieval , but the perfor­ mance of retrieval was degraded.

Stairmand [1997] used WordNet to investigate the computational analysis of lexical cohesion in text using lexical chain method [Morris and Hirst , 1991] . Because lexical chains are associated with topics, he suggested that information retrieval, where the notion of topic is very pertinent, is a suitable application domain. He con­ cluded that his method only succeed in small-scale eval­ uation, but a hybrid approach is required to scale-up to real-word information retrieval scenarios.

Smeaton and Berrut [1995] tried to expand the queries of the TREC-4 collection with various strategies of weighting expansion terms, along with manual and auto­ matic word sense disambiguation techniques. Unfortu­ nately all strategies degraded the retrieval performance.

Instead of matching terms in queries and documents, Richardson [1995] used WordNet to compute the seman­ tic distance between concepts or words and then used this term distance to compute the similarity between a query and a document . Although he proposed two meth­ ods to compute semantic distances, neither of them in­ creased the retrieval performance.

2 Limitations of WordNet

In this section we analyze why WordNet has failed to im­ prove information retrieval performance. We ran exact­ match retrieval against 9 small standard test collections [Fox, 1990] in order to observe this phenomenon. An in­ formation retrieval test collection consists of a collection of documents along with a set of test queries. The set of relevant documents for each test query is also given, so that the performance of the information retrieval system can be measured. We expand queries using a combina­ tion of synonyms, hypernyms, and hyponyms in Word­ Net. The results are shown in Table 1.

In Table 1 we show the name of the test collection (Collection), the total number of documents (#Doc) and queries (#Query), and all relevant documents for all queries (#Rei) in that collection. For each document collection, we indicate the total number of relevant documents retrieved (Rei-ret) , the recall (~k~1t), the to­ tal number of documents retrieved (Ret-docs), and the precision ( RR~ldet ) for each of no expansion (Base) , e- ocs expansion with synonyms (Exp. I), expansion with synonyms and hypernyms (Exp. II), expansion with syn­ onyms and hyponyms (Exp. III), and expansion with synonyms, hypernyms, and hyponyms (Exp. IV).

From the results in Table 1, we can conclude that query expansion can increase recall performance but un­ fortunately degrades precision performance. We thus turned to investigation of why all the relevant documents could not be retrieved with the query expansion method above. Some of the reasons are stated below :

• Two terms that seem to be interrelated have differ­ ent parts of speech in WordNet. This is the case be­ tween stochastic (adjective) and statistic (noun). Since words in WordNet are grouped on the ba­ sis of part of speech in WordNet, it is not possible to find a relationship between terms with different parts of speech.
• Most of relationships between two terms are not found in WordNet. For example how do we know that Sumitomo Bank is a Japanese company?
• Some terms are not included in WordNet (proper name, etc).

To overcome all the above problems, we propose a method to enrich WordNet with an automatically con­ structed thesaurus. The idea underlying this method is that an automatically constructed thesaurus could com­ plement the drawbacks of WordNet. For example, as we stated earlier, proper names and their interrelations among them are not found in WordNet, but if proper names and other terms have some strong relationship, they often co-occur in the document, so that their re­ lationship may be modeled by an automatically con­ structed thesaurus.

Polysemous words degrade the precision of informa­ tion retrieval since all senses of the original query term are considered for expansion. To overcome the prob­ lem of polysemous words, we apply a restriction in that queries are expanded by adding those terms that are most similar to the entirety of query terms, rather than selecting terms that are similar to a single term in the query.

3 Method

In this section, we first describe the construction method for each type of thesaurus utilized in this research, and then describe a term weighting method using similarity measure based on these thesauri .

3.1 WordNet

In WordNet, words are organized into taxonomies where each node is a set of synonyms (a synset) representing a single sense. There are 4 different taxonomies based on parts of speech and also there are many relationships defined within it [Fellbaum, 1998]. In this experiment we use only noun taxonomy with hyponymy /hypernymy (or the is-a relation), which relates more general and more specific senses.

The similarity between word w1 and w2 is defined as a shortest path from each sense of w1 to each sense of w2 , as below [Resnik, 1995b]:

where Np is the number of nodes in path p from w1 to w2 and D is the maximum depth of the taxonomy.

3.2 Co-occurrence-based Thesaurus

The general idea underlying the use of term co­ occurrence data for thesaurus construction is that words that tend to occur together in documents are likely to have similar, or related, meanings [Qiu and Frei, 1993]. Co-occurrence data thus provides a statistical method for automatically identifying semantic relationships that are normally contained in a hand-made thesaurus. Sup­ pose two words (A and B) occur fa and fb times, respec­ tively, and co-occur fc times, then the.similarity between A and B can be calculated using a similarity coefficient such as the Tanimoto Coefficient :

3.3 Predicate-Argument-based Thesaurus

In contrast with the previous section, this method at­ tempts to construct a thesaurus according to predicate­ argument structures [Hindle, 1990; Grafenstette, 1994; Ruge, 1992]. The use of this method for thesaurus con­ struction is based on the idea that there are restrictions on what words can appear in certain environments, and in particular, what words can be arguments of a certain predicate. For example, a dog may walk, bite, but can not fly. Each noun may therefore be characterized ac­ cording to the verbs or adjectives that it occurs with.

Nouns may then be grouped according to the extent to which they appear in similar constructions.

First, all the documents are parsed using the Apple Pie Parser, which is a probabilistic chart parser devel­ oped by Sekine and Grishman [1995] . Then the following syntactic structures are extracted :

• Subject-Verb
• Verb-Object
• Adjective-Noun

Each noun has a set of verbs and adjective that it occurs with, and for each such relationship, a Tanimoto coefficient value is calculated.

• c (v· n·)- ! . ub(v,,nj) sub " J - f(v;)+f.ub(nj)-f,ub(Vi,nj)' where fsub(Vi,nj) is the frequency of noun nj oc­ curring as the subject of verb v;, fsub(nj) is the frequency of the noun nj occurring as subject of any verb, and j(vi) is the frequency of the verb Vi
• e c ·(V· n ·) _ fobj(Vi ,nj) ob] '' J - f(v;)+fobj(n;) ! ob;(vi,nj)' where !obj(vi,nj) is the frequency of noun nj oc­ curring as the object of verb vi, fobj(nj) is the fre­ quency of the noun nj occurring as object of any verb, and f(vi) is the frequency of the verb Vi
• c ·(a· n ·) - /adj(a,,nj) ad] " J - f(ai)+!adj(nt) !adj(ai,nj)' where f ( ai, nj) is the frequency of noun nj occur­ ring as argument of adjective ai, !adj(nj) is the fre­ quency of the noun nj occurring as argument of any adjective, and f(ai) is the frequency of the adjective ai

We define the similarity of two nouns with respect to one predicate as the minimum of each Tanimoto coefficient with respect to that predicate, i.e.,

Finally the overall similarity between two nouns is de­ fined as the average of all the similarities between those two nouns for all predicate-argument structures.

3.4 Expansion Term Weighting Method

A query q is represented by a vector q = (q1, q2, ... , qn), where the q; 's are the weights of the search terms t; contained in query q.

The similarity between a query q and a term ti can be defined as belows [Qiu and Frei, 1993]:

Where the value of sim( t;, ti) can be defined as the average of the similarity values in the three types of the­ saurus.

With respect to the query q, all the terms in the col­ lection can now be ranked according to their simqt. Ex­ pansion terms are terms ti with high simqt(q, tj)·

The weight(q, tj) of an expansion term ti is defined as a function of simqt(q,tj):

where 0 ~ weight(q, tj) ~ 1.

An expansion term gets a weight of 1 if its similarity to all the terms in the query is 1. Expansion terms with similarity 0 to all the terms in the query get a weight of 0. The weight of an expansion term depends both on the entire retrieval query and on the similarity between the terms. The weight of an expansion term can be in­ terpreted mathematically as the weighted mean of the similarities between the term tj and all the query terms. The weight of the original query terms are the weighting factors of those similarities.

Therefore the query q is expanded by adding the fol­ lowing query :

where aj is equal to weight(q, tj) if tj belongs to the top r ranked terms. Otherwise aj is equal to 0.

The resulting expanded query is :

where the o is defined as the concatenation operator.

The method above can accommodate the polysemous word problem, because an expansion term which is taken from a different sense to the original query term is given very low weight.

4 Experimental Results

In order to evaluate the effectiveness of the proposed method in the previous section we conducted experi­ ments using the TREC-7 information retrieval test col­ lection [Voorhees and Harman, to appear 1999]. TREC-7 documents consists of the Financial Times (FT), Fed­ eral Register (FR94), Foreign Broadcast Information Service (FBIS) and the LA Times. Table 2 gives its document statistics, Table 3 give topic statistics, and Table 4 is one example out of 50 topics. As a base­ line we used SMART [Salton, 1971] without expansion. SMART is an information retrieval engine based on the vector space model in which term weights are calcu­ lated based on term frequency, inverse document fre­ quency and document length normalization. The re­ sults are shown in Table 5. This table shows the aver­ age of non-interpolated recall-precision for each of base­ line, expansion using only WordNet, expansion using only predicate-argument-based thesaurus, expansion us­ ing only co-occurrence-based thesaurus, and expansion using all of them. For each method we give the percent­ age of improvement over the baseline. It is shown that the performance using the combined thesauri for query expansion is better than both SMART and using just one type of thesaurus.

Title :

journalist risks

Description :

Identify instances where a journalist has been put at risk (e.g., killed, arrested or taken hostage) in the performance of his work.

Narrative:

Any document identifying an instance where a jour­ nalist or correspondent has been killed, arrested or taken hostage in the performance of his work is rel­ evant.

Figure 1: Topic Example

5 Discussion

In this section we discuss why our method of using Word­ Net is able to improve the performance of information retrieval. The important points of our method are :

• the coverage of WordNet is broadened
• weighting method

The three types of thesaurus we used have different characteristics. Automatically constructed thesauri add not only new terms but also new relationships not found in WordNet. If two terms often co-occur together in a document then those two terms are likely bear some relationship. Why not only use the automatically con­ structed thesauri ? The answer to this is that some relationships may be missing in the automatically con­ structed thesauri [Grafenstette, 1994]. For example, con­ sider the words tumor and tumour. These words cer­ tainly share the same context, but would never appear in the same document, at least not with a frequency recognized by a co-occurrence-based method. In gen­ eral, different words used to describe similar concepts may never be used in the same document, and are thus missed by the co-occurrence methods. However their re­ lationship may be found in the WordNet thesaurus.

The second point is our weighting method. As already mentioned before, most attempts at automatically ex­ panding queries by means of WordNet have failed to im­ prove retrieval effectiveness. The opposite has often been true: expanded queries were less effective than the origi­ nal queries. Beside the "incomplete" nature of WordNet, we believe that a further problem, the weighting of ex­ pansion terms, has not been solved. All weighting meth­ ods described in the past researches of query expansion using WordNet have been based on "trial and error" or ad-hoc methods. That is, they have no underlying jus­ tification.

The advantages of our weighting method are:

• the weight of each expansion term considers the similarity of that term with all terms in the original query, rather than to just one or some query terms.
• the weight of the expansion term accommodates the polysemous word problem.

This method can accommodate the polysemous word problem, because an expansion term taken from a dif­ ferent sense to the original query term sense is given very low weight. The reason for this is that, the weight­ ing method depends on all query terms and all of the thesauri. For example, the word bank has many senses in WordNet . Two such senses are the financial institu­ tion and the river edge senses. In a document collection relating to financial banks, the river sense of bank will generally not be found in the co-occurrence-based the­ saurus because of a lack of articles talking about rivers. Even though (with small possibility) there may be some documents in the collection talking about rivers, if the query contained the finance sense of bank then the other terms in the query would also concerned with finance and not rivers. Thus rivers would only have a relation­ ship with the bank term and there would be no relation­ ships with other terms in the original query, resulting in a low weight. Since our weighting method depends on both query in its entirety and similarity in the three thesauri, the wrong sense expansion terms are given very low weight.

We also experimented this method using other sim­ ilarity coefficient method and Roget thesaurus, and found significant improvement of retrieval performance although the contribution of Roget thesaurus is very lim­ ited [Mandala et al., to appear 1999].

6 Conclusion

This paper analyzed why the use of WordNet, a large and hand-made publically available thesaurus was not so succesful in improving the retrieval effectiveness in information retrieval applications. We found that the main reason is that most relationships between terms are not found in WordNet, and some terms, such as proper names, are not included in WordNet. To overcome this problem we proposed a method to enrich the WordNet with automatically constructed thesauri.

Another problem in query expansion is that of polyse­ mous words. Instead of using a word sense disambigua­ tion method to select the appropriate sense ofeach word, we overcame this problem with a weighting method. Ex­ periments proved that our method of using WordNet in query expansion could improve information retrieval ef­ fectiveness.

In the future, we will use anaphora resolution to ac­ curately determine the nature of relationships involving proper names. We will also investigate the effect of using different similarity coefficient method to build thesauri to the retrieval performance.

7 Acknowledgements

The authors would like to thank Mr. Timothy Baldwin (TIT, Japan) and three anonymous reviewers for useful comments on the earlier version of this paper. We also thank to Dr. Chris Buckley (SabiR Research) for the SMART support, and Dr. Satoshi Sekine (New York University) for providing the Apple Pie Parser program. This research is partially supported by the JSPS project number JSPS-RFTF96P00502.