A Query Expansion Method based on a Weighted Word Pairs Approach

Abstract

In this paper we propose a query expansion method to improve accuracy of a text retrieval system. Our technique makes use of explicit relevance feedback to expand an initial query with a structured representation called Weighted Word Pairs. Such a structure can be automatically extracted from a set of documents and uses a method for term extraction based on the probabilistic Topic Model. Evaluation has been conducted on TREC-8 repository and performances obtained using standard WWP and Kullback Leibler Divergency query expansion approaches have been compared.

Keywords

• Text retrieval
• query expansion
• probabilistic topic model

Introduction

Over the years, several text retrieval models have been proposed: set-theoretic (including boolean), algebraic, probabilistic models [ 1 ], etc. Although each method has its own properties, there is a common denominator: the bag of words representation of documents.

The \bag of words" assumption claims that a document can be considered as a feature vector where each element indicates the presence (or absence) of a word, so that the information on the position of that word within the document is completely lost [ 1 ]. The elements of the vector can be weights and computed in di erent ways so that a document can be considered as a list of weighted features. The term frequency-inverse document (tf-idf ) model is a commonly used weighting model: each term in a document collection is weighted by measuring how often it is found within a document (term frequency ), o set by how often it occurs within the entire collection (inverse document frequency ). Based on this model, also a query can be viewed as a document, so it can be represented as a vector of weighted words.

The relevance of a document to a query is the distance between the corresponding vector representations in the features space. Unfortunately, queries performed by users may not be long enough to avoid the inherent ambiguity of language (polysemy etc.). This makes text retrieval systems, that rely on the bags of words model, generally su er from low precision, or low quality document retrieval. To overcome this problem, scientists proposed methods to expand the original query with other topic-related terms extracted from exogenous (e.g. ontology, WordNet, data mining) or endogenous knowledge (i.e. extracted only from the documents contained in the collection) [ 2, 3, 1 ]. Methods based on endogenous knowledge, also known as relevance feedback, make use of a number of labelled documents, provided by humans (explicit) or automatic/semi-automatic strategies, to extract topic-related terms and such methods have demonstrated to obtain performance improvements of up to 40% [ 4 ]

In this paper we propose a new query expansion method that uses a structured representation of documents and queries, named Weighted Word Pairs, that is capable of reducing the e ect of the inherent ambiguity of language so achieving better performance than a method based on a vector of weighted words. The Weighted Word Pairs representation is automatically obtained from documents, provided by a minimal explicit feedback, by using a method of term extraction[ 5 ][ 6 ][ 7 ] based on the Latent Dirichlet Allocation model [ 8 ] implemented as the Probabilistic Topic Model [ 9 ]. Evaluation has been conducted on TREC8 repository: results obtained employing standard WWP and Kullback Leibler divergency have been compared.

This article is structured as follows: Section 2 gives an overview on related works and approaches to query expansion in text retrieval; in Section 3 a general framework for query expansion is discussed; Section 4 describes in detail our feature extraction method; in Section 5 performance evaluation is presented. 2

Related works

It is well documented that the query length in typical information retrieval systems is rather short (usually two or three words) [ 10 ] which may not be long enough to avoid the inherent ambiguity of language (polysemy etc.), and which makes text retrieval systems, that rely on a term-frequency based index, su er generally from low precision, or low quality of document retrieval.

In turn, the idea of taking advantage of additional knowledge, by expanding the original query with other topic-related terms, to retrieve relevant documents has been largely discussed in the literature, where manual, interactive and automatic techniques have been proposed [ 2 ][ 1 ]. The idea behind these techniques is that, in order to avoid ambiguity, it may be su cient to better specify \the meaning" of what the user has in mind when performing a search, or in other words \the main concept" (or a set of concepts) of the preferred topic in which the user is interested. A better specialization of the query can be obtained with additional knowledge, that can be extracted from exogenous (e.g. ontology, WordNet, data mining) or endogenous knowledge (i.e. extracted only from the documents contained in the repository) [ 3, 1 ].

In this paper we focus on those techniques which make use of the Relevance Feedback (in the case of endogenous knowledge) which takes into account the results that are initially returned from a given query and so uses the information about the relevance of each result to perform a new expanded query. In the literature we can distinguish between three types of procedures for the assignment of the relevance: explicit feedback, implicit feedback, and pseudo feedback.

Most existing methods, due to the fact that the human labeling task is enormously annoying and time consuming [ 11 ], make use of the pseudo relevance feedback (top k retrieved are assumed to be relevant). Nevertheless, fully automatic methods su er from obvious errors when the initial query is intrinsically ambiguous. As a consequence, in the recent years, some hybrid techniques have been developed which take into account a minimal explicit human feedback [ 4, 12 ] and use it to automatically identify other topic related documents.

However, whatever the technique that selects the set of documents representing the feedback, the expanded terms are usually computed by making use of well known approaches for term selection as Rocchio, Robertson, CHI-Square, Kullback-Lieber etc [ 13 ]. In this case the reformulated query consists in a simple (sometimes weighted) list of words. Although such term selection methods have proven their e ectiveness in terms of accuracy and computational cost, several more complex alternative methods have been proposed, which consider the extraction of a structured set of words instead of simple list of them: a weighted set of clauses combined with suitable operators [ 14 ], [ 15 ], [ 16 ]. 3

A general Query Expansion framework

A general query expansion framework can be described as a modular system including: { the Information Retrieval (IR) module; { the Feedback (F) module; { the Feature Extraction (FE) module; { the Query Reformulation (QR) module.

Such a framework is represented in Figure 1 and can be described as follows. The user initially performs a search task on the dataset D by inputting a query q to the IR system and obtains a set of documents RS = (d1; ; dN ) as a result. The module F, thanks to the explicit feedback of the user, identi es a small set of relevant documents (called Relevance Feedback ) RF = (d1; ; dM ) from the hit list of documents RS returned by the IR system. Given the set of relevant document RF , the module FE extracts a set of features g that must be added to the initial query q. The extracted features can be weighted words or more complex structures such as weighted word pairs. So the obtained set g must be adapted by the QR module to be handled by the IR system and then added to the initial query. The output of this module is a new query qe which includes both the initial query and the set of features extracted from the RF . The new query is then performed on the collection so obtaining a new result set RS0 = (d01; ; d0N ) di erent from the one obtained before. Considering the framework described above is possible to take into account any technique of feature extraction that makes use of the explicit relevant feedback and any IR systems suitable to handle the resulting expanded query qe. In this way it is possible to implement several techniques and make objective comparisons with the proposed one. 4

WWP feature selection method

The aim of the proposed method is to extract from a set of documents a compact representation, named Weighted Word Pairs (WWP), which contains the most discriminative word pairs to be used in the text retrieval task. The Feature Extraction module (FE) is represented in Fig. 3. The input of the system is the set of documents RF = (d1; ; dM ) and the output is a vector of weighted word pairs g = fw10; ; wj0Tpjg, where Tp is the number of pairs and wn0 is the weight associated to each pair (feature) tn = (vi; vj ).

A WWP structure can be suitably represented as a graph g of terms (Fig. 2). Such a graph is made of several clusters, each containing a set of words vs (aggregates) related to an aggregate root (ri), a special word which represents the centroid of the cluster. How aggregate roots are selected will be clear further. The weight is can measure how a word is related to an aggregate root and can be expressed as a probability: is = P (rijvs). The resulting structure is a subgraph rooted on ri. Moreover, aggregate roots can be linked together building a centroids subgraph. The weight ij can be considered as the degree of correlation between two aggregate roots and can also be expressed as a probability: ij = P (ri; rj ). Being each aggregate root a special word, it can be stated that g contains directed and undirected pairs of features lexically denoted as words. Given the training set RF of documents, the term extraction procedure is obtained rst by computing all the relationships between words and aggregate roots ( is and ij ), and then selecting the right subset of pairs Tsp from all the possible ones Tp.

A WWP graph g is learned from a corpus of documents as a result of two important phases: the Relations Learning stage, where graph relation weights are learned by computing probabilities between word pairs (see Fig. 3); the Structure Learning stage, where an initial WWP graph, which contains all possible relations between aggregate roots and aggregates, is optimized by performing an iterative procedure. Given the number of aggregate roots H and the desired max number of pairs as constraints, the algorithm chooses the best parameter settings = ( 1; : : : ; H ) and de ned as follows: 1. i: the threshold that establishes, for each aggregate root i, the number of aggregate root/word pairs of the graph. A relationship between the word vs and the aggregate root ri is relevant if is i. 2. : the threshold that establishes the number of aggregate root/aggregate root pairs of the graph. A relationship between the aggregate root vi and aggregate root rj is relevant if ij . 4.1

Relations Learning

Since each aggregate root is lexically represented by a word of the vocabulary, we can write is = P (rijvs) = P (vijvs), and ij = P (ri; rj ) = P (vi; vj ). Considering that P (vi; vj ) = P (vijvj )P (vj ), all the relations between words result from the computation of the joint or the conditional probability 8i; j 2 f1; ; jT jg and P (vj ) 8j. An exact calculation of P (vj ) and an approximation of the joint, or conditional, probability can be obtained through a smoothed version of the generative model introduced in [ 8 ] called Latent Dirichlet Allocation (LDA), which makes use of Gibbs sampling [ 9 ]. The original theory introduced in [ 9 ] mainly proposes a semantic representation in which documents are represented in terms of a set of probabilistic topics z. Formally, we consider a word um of the document dm as a random variable on the vocabulary T and z as a random variable representing a topic between f1; ; Kg. A document dm results from generating each of its words. To obtain a word, the model considers three parameters assigned: , and the number of topics K. Given these parameters, the model chooses m through P ( j ) Dirichlet( ), the topic k through P (zj m) M ultinomial( m) and k Dirichlet( ). Finally, the distribution of each word given a topic is P (umjz; z) M ultinomial( z). The output obtained by performing Gibbs sampling on RF consists of two matrixes: 1. the words-topics matrix that contains jT j K elements representing the probability that a word vi of the vocabulary is assigned to topic k: P (u = vijz = k; k); 2. the topics-documents matrix that contains K jRF j elements representing the probability that a topic k is assigned to some word token within a document dm: P (z = kj m).

The probability distribution of a word within a document dm of the corpus can be then obtained as:

K P (um) = X P (umjz = k; k)P (z = kj m): (1)

k=1

In the same way, the joint probability between two words um and ym of a document dm of the corpus can be obtained by assuming that each pair of words is represented in terms of a set of topics z and then:

P (um; ym) =

K X P (um; ymjz = k; k)P (z = kj m) k=1 Note that the exact calculation of Eq. 2 depends on the exact calculation of P (um; ymjz = k; k) that cannot be directly obtained through LDA. If we assume that words in a document are conditionally independent given a topic, an approximation for Eq. 2 can be written as [ 5, 6 ]:

P (um; ym) '

K X P (umjz = k; k)P (ymjz = k; k)P (z = kj m): k=1 (2) (3) Moreover, Eq. 1 gives the probability distribution of a word um within a document dm of the corpus. To obtain the probability distribution of a word u independently of the document we need to sum over the entire corpus: where m is the prior probability for each document (PjmR=F1j m = 1). If we consider the joint probability distribution of two words u and y, we obtain:

M P (u) = X P (um) m m=1

M P (u; y) = X P (um; yv) m

m=1 Concluding, once we have P (u) and P (u; y) we can compute P (vi) = P (u = vi) and P (vi; vj ) = P (u = vi; y = vj ), 8i; j 2 f1; ; jT jg and so the relations learning can be totally accomplished. 4.2

Structure Learning

Once each ij and is is known 8i; j; s, aggregate root and word levels have to be identi ed in order to build a starting WWP structure to be optimized as discussed later. The rst step is to select from the words of the indexed corpus a set of aggregate roots r = (r1; : : : ; rH ), which will be the nodes of the centroids subgraph. Aggregate roots are meant to be the words whose occurrence is most implied by the occurrence of other words of the corpus, so they can be chosen as follows: ri = argmaxvi Y P (vijvj )

j6=i

Since relationships' strenghts between aggregate roots can be directly obtained from ij , the centroids subgraph can be easily determined. Note that not all possible relationships between aggregate roots are relevant: the threshold can be used as a free parameter for optimization purposes. As discussed before, several words (aggregates) can be related to each aggregate root, obtaining H aggregates' subgraphs. The threshold set = ( 1; : : : ; H ) can be used to select the number of relevant pairs for each aggregates' subgraph. Note that a relationship between the word vs and the aggregate root ri is relevant if is i, but the value is cannot be directly used to express relationships' strenghts between aggregate roots and words. In fact, being is a conditional probability, it is always bigger than is which is a joint probability. Therefore, once pairs for the aggregates' subgraph are selected using is, relationships' strenght are represented on the WWP structure through is.

Given H and the maximum number of pairs as constraints (i.e. xed by the user), several WWP structure gt can be obtained by varying the parameters t = ( ; )t. As shown in Fig.3, an optimization phase is carried out in order to search the set of parameters t which produces the best WWP graph (4) (5) (6) [ 6 ]. This process relies on a scoring function and a searching strategy that will be now explained. As we have previously seen, a gt is a vector of features gt = fb1t; : : : ; bjTspjtg in the space Tsp and each document of the training set RF can be represented as a vector dm = (w1m; : : : ; wjTspjm) in the space Tsp. A possible scoring function is the cosine similarity between these two vectors: S(gt; dm) =

PjnT=sp1j bnt wnm qPjnT=sp1j b2nt qPjnT=sp1j wn2m (7) and thus the optimization procedure would consist in searching for the best set of parameters t such that the cosine similarity is maximized 8dm. Therefore, the best gt for the set of documents RF is the one that produces the maximum score attainable for each document when used to rank RF documents. Since a score for each document dm is obtained, we have:

St = fS(gt; d1); ; S(gt; djRFj)g; where each score depends on the speci c set t = ( ; )t. To compute the best value of we can maximize the score value for each document, which means that we are looking for the graph which best describes each document of the repository from which it has been learned. It should be noted that such an optimization maximizes at the same time all jRF j elements of St. Alternatively, in order to reduce the number of the objectives being optimized, we can at the same time maximize the mean value of the scores and minimize their standard deviation, which turns a multi-objective problem into a two-objective one. Additionally, the latter problem can be reformulated by means of a linear combination of its objectives, thus obtaining a single objective function, i.e., Fitness (F ), which depends on t,

F ( t) = E [St] where E is the mean value of all the elements of St and m is the standard deviation. By summing up, the parameters learning procedure is represented as follows, = argmaxtfF ( t)g:

Since the space of possible solutions could grow exponentially, jTspj 300 3 has been considered. Furthermore, the remaining space of possible solutions has been reduced by applying a clustering method, that is the K-means algorithm, to all ij and is values, so that the optimum solution can be exactly obtained after the exploration of the entire space. 5

Method validation

The proposed approach has been validated using IR systems that allow to handle structured queries composed of weighted word pairs. For this reason,the following open source tools were considered: Apache Lucene4 which supports structured 3 This number is usually employed in the case of Support Vector Machines. 4 We adopted the version 2.4.0 of Lucene query based on a weighted boolean model and Indri5 which supports an extended set of probabilistic structured query operators based on INQUERY. The performance comparison was carried out testing the following FE/IR con gurations: { IR only. Unexpanded queries were performed using rst Lucene and then

Lemur as IR modules. Results obtained in these cases are referred as baseline. { FE(WWP) + IR. Our WWP-based feature extraction method was used to expand initial query and feed Lucene and Lemur IR modules. { FE(KLD) + IR. Kullback Leibler Divergency based feature extraction was used to expand initial query and feed Lucene and Lemur IR modules. 5.1

Datasets and Ranking Systems

The dataset from TREC-8 [ 17 ] collections (minus the Congressional Record) was used for performance evaluation. It contains about 520,000 news documents on 50 topics (no.401-450) and relevance judgements for the topics. Word stopping and word stemming with single keyword indexing were performed. Query terms for each topic's initial search (baseline) were obtained by parsing the title eld of a topic. For the baseline and for the rst pass ranking (needed for feedback document selection) the default similarity measures provided by Lucene and Lemur has been used. Performance was measured with TREC's standard evaluation measures: mean average precision (MAP), precision at di erent levels of retrieved results (P@5,10...1000), R-precision and binary preference (BPREF). 5.2

Parameter Tuning

The two most important parameters involved in the computation of WWP, given the number of documents for training, are the number of aggregate roots H and the number of pairs. The number of aggregate roots can be chosen as a trade o between retrieval performances and computational times, our choice was H = 4 since it seemed to be the best compromise (about 6 seconds per topic)6. However, we want to emphasize method e ectiveness more than algorithm e ciency since algorithm coding has not been completely optimized yet.

Fig. 5.2 shows results of baseline and WWP method when changing number of pairs from 20 to 100 where the number of documents is xed to 3: in this analysis, Lucene IR module is used . According to the graph, our system always provides better performances than baseline; the change in number of pairs has a great impact especially on precision at 5 where 60 pairs achieve the best results. Anyway, if we consider precision at higher levels together with map values, 50 pairs seem to be a better choice also for shorter computational times. Fig. 5.2 shows results of baseline and our method when changing number of training documents (Lucene IR Module used): here we can see that the overall behaviour of the system is better when choosing 3 relevant documents for training. 5 We adopted the version 5... that is part of the Lemur Toolkit 6 Results were obtained using an Intel Core 2 Duo 2,40 GHz PC with 4GB RAM with no other process running.

Once again the system outperforms baseline especially at low precision levels. Discussed analysis led us to choose the following settings for the experimental stage: 4 aggregate roots, 50 pairs, 3 training documents.

Comparison with other methods

In Table 1 WWP method is compared with baseline and Kullback-Leibler divergence based method [ 13 ] when using both Lucene and Lemur as IR modules. Here we see that WWP outscores KLD, and baseline especially for low level precision while having good performances for other measures. However these results are obtained without removing feedback documents from the dataset so a big improvement in low level precision may appear a little obvious. Another performance evaluation was carried out using only the residual collection (RSD) where feedback documents are removed. Results for this evaluation are shown in table 2 where we see performance improvements also with residual collection. 6

Conclusions

In this work we have demonstrated that a Weighted Word Pairs hierarchical representation is capable of retrieving a greater number of relevant documents than a less complex representation based on a list of words. These results suggest that our approach can be employed in all those text mining tasks that consider matching between patterns represented as textual information and in text categorization tasks as well as in sentiment analysis and detection tasks. The proposed approach computes the expanded queries considering only endogenous knowledge. It is well known that the use of external knowledge, for instance Word-Net, could clearly improve the accuracy of information retrieval systems and we consider this integration as a future work.

References

1. Christopher D. Manning , P.R. , Schtze , H.: Introduction to Information Retrieval. Cambridge University ( 2008 )

2. Efthimiadis , E.N. : Query expansion . In Williams, M.E., ed.: Annual Review of Information Systems and Technology . ( 1996 ) 121 { 187

3. Bhogal , J. , Macfarlane , A. , Smith , P.: A review of ontology based query expansion . Information Processing & Management 43 ( 4 ) ( 2007 ) 866 { 886

4. Okabe , M. , Yamada , S. : Semisupervised query expansion with minimal feedback . IEEE Transactions on Knowledge and Data Engineering 19 ( 2007 ) 1585 { 1589

5. Napoletano , P. , Colace , F. , De Santo , M. , Greco , L. : Text classi cation using a graph of terms . In: Complex, Intelligent and Software Intensive Systems (CISIS) , 2012 Sixth International Conference on. (july 2012 ) 1030 { 1035

6. Clarizia , F. , Greco , L. , Napoletano , P.: An adaptive optimisation method for automatic lightweight ontology extraction . In Filipe, J., Cordeiro , J., eds. : Enterprise Information Systems. Volume 73 of Lecture Notes in Business Information Processing . Springer Berlin Heidelberg ( 2011 ) 357 { 371

7. Clarizia , F. , Greco , L. , Napoletano , P.: A new technique for identi cation of relevant web pages in informational queries results . In: Proceedings of the 12th International Conference on Enterprise Information Systems: Databases and Information Systems Integration. (8-12 June 2010 ) 70 { 79

8. Blei , D.M. , Ng , A.Y. , Jordan , M.I. : Latent dirichlet allocation . Journal of Machine Learning Research 3 ( 993 {1022) ( 2003 )

9. Gri ths, T.L., Steyvers , M. , Tenenbaum , J.B. : Topics in semantic representation . Psychological Review 114 ( 2 ) ( 2007 ) 211 { 244

10. Jansen , B.J. , Spink , A. , Saracevic , T. : Real life, real users, and real needs: a study and analysis of user queries on the web . Inform. Proces. & Manag . 36 ( 2 ) ( 2000 ) 207 { 227

11. Ko , Y. , Seo , J.: Text classi cation from unlabeled documents with bootstrapping and feature projection techniques . Inf. Process. Manage . 45 ( 2009 ) 70 { 83

12. Dumais , S. , Joachims , T. , Bharat , K. , Weigend , A. : SIGIR 2003 workshop report: implicit measures of user interests and preferences . 37 ( 2 ) ( 2003 ) 50 { 54

13. Carpineto , C. , de Mori , R., Romano , G. , Bigi , B. : An information-theoretic approach to automatic query expansion . ACM Trans. Inf. Syst . 19 ( 2001 ) 1 { 27

14. Callan , J. , Croft , W.B. , Harding , S.M.: The inquery retrieval system . In: In Proceedings of the Third International Conference on Database and Expert Systems Applications , Springer-Verlag ( 1992 ) 78 { 83

15. Collins-Thompson , K. , Callan , J.: Query expansion using random walk models . In: Proceedings of the 14th ACM international conference on Information and knowledge management . CIKM '05 , New York, NY, USA, ACM ( 2005 ) 704 { 711

16. Lang , H. , Metzler , D. , Wang , B. , Li , J.T. : Improved latent concept expansion using hierarchical markov random elds . In: Proceedings of the 19th ACM international conference on Information and knowledge management . CIKM '10 , New York, NY, USA, ACM ( 2010 ) 249 { 258

17. Voorhees , E.M. , Harman , D. : Overview of the eighth text retrieval conference (trec-8) ( 2000 )