Using Word Embeddings for Automatic Query Expansion

Dwaipayan Roy, Debjyoti Paul, Mandar Mitra, Utpal Garain

Introduction

Since the objective of Query Expansion (QE) is to find words that are semantically related to a given user query, it should be possible to leverage word embeddings in order to improve QE effectiveness. Let $Q$ be a given user query consisting of the words $q_{1},q_{2},\ldots,q_{m}$ . Let $w^{(i)}_{1},w^{(i)}_{2},\ldots,w^{(i)}_{k}$ be the $k$ nearest neighbours (kNN) of $q_{i}$ in the embedding space. Then, these $w^{(i)}_{j}$ s constitute a set of obvious candidates from which terms may be selected and used to expand $Q$ . Of course, instead of considering terms that are proximate neighbours of individual query words, it is generally preferable to consider terms that are close to the query as a whole.This idea has been used in a number of traditional, effective QE techniques, e.g., LCA and RM3 . In these techniques, expansion terms are selected on the basis of their association with all query terms.

While word embeddings have been shown to be useful in some specialised applications (e.g., clinical decision support and sponsored search ) and for cross-lingual retrieval , the obvious way of using embeddings for QE seems not to have been explored within the standard ad hoc retrieval task setting. Our goal in this work is to study how word embeddings may be applied to QE for ad hoc retrieval. Specifically, we are looking for answers to the following questions.

Does QE, using the nearest neighbours of query terms, improve retrieval effectiveness?

If yes, is it possible to characterise the queries for which this QE method does / does not work?

How does embedding based QE perform compared to an established QE technique like RM3 ?

We try a few different embedding based QE methods. These methods are described in more detail in the next section. Experiments on a number of TREC collections (Section 3) show that these QE methods generally yield significant improvements in retrieval effectiveness when compared to using the original, unexpanded queries. However, they are all significantly inferior to RM3. We discuss these results in greater detail in Section 4. Section 5 concludes the paper.

Word Embedding based Query Expansion

In this section, we first describe three QE methods using the individual embeddings of the terms. The first method is a simple, kNN based QE method that makes use of the basic idea outlined in Section 1. Unlike pseudo relevance feedback (PRF) based QE methods, this method does not require an initial round of retrieval. The second approach we tried is a straightforward variation of the first approach that uses word embeddings in conjunction with a set of pseudo relevant documents. In the third method, we propose an approach that is inspired by . In this approach, the nearest neighbours are computed in an incremental fashion as elaborated below. Next, we describe how we obtain an extended query term set by using compositionality of terms. In all our methods, we used word2vec for computing word embeddings.

Let the given query $Q$ be $\{q_{1},\ldots,q_{m}\}$ . In this simple approach, we define the set $C$ of candidate expansion terms as

where $\mathit{NN}(\mathbf{q})$ is the set of $K$ terms that are closest to $q$ in the embedding space.Bold-faced notation $\mathbf{w}$ denotes the embedded vector corresponding to a word $w$ For each candidate expansion term $t$ in $C$ , we compute the mean cosine similarity between $t$ and all the terms in $Q$ following Equation 2.

The terms in $C$ are sorted on the basis of this mean score, and the top $K$ candidates are selected as the actual expansion terms.

2 Post-retrieval kNN based approach

In our next approach, we use a set of pseudo-relevant documents (PRD) — documents that are retrieved at top ranks in response to the initial query — to restrict the search domain for the candidate expansion terms. Instead of searching for nearest neighbours within the entire vocabulary of the document collection, we consider only those terms that occur within PRD. The size of PRD may be varied as a parameter. The rest of the procedure for obtaining the expanded query is the same as in Section 2.1.

3 Pre-retrieval incremental kNN based approach

The incremental nearest neighbour method is a simple extension of the pre-retrieval kNN method that is based on . Instead of computing the nearest neighbours for each query term in a single step, we follow an incremental procedure. The first assumption in this method is that, the most similar neighbours have comparatively lower drift than the terms occurring later in the list in terms of similarity. Since the most similar terms are the strongest contenders for becoming the expansion terms, it may be assumed that these terms are also similar to each other, in addition to being similar to the query term. Based on the above assumption, we use an iterative process of pruning terms from $\mathit{NN}(q)$ , the list of candidates obtained for each term $q$ in EQTS.

We start with $\mathit{NN}(q)$ . Let the nearest neighbours of $q$ in order of decreasing similarity be $t_{1},t_{2},\ldots,t_{N}$ . We prune the $K$ least similar neighbours to obtain $t_{1},t_{2},\ldots,t_{N-k}$ . Next, we consider $t_{1}$ , and reorder the terms $t_{2},\ldots,t_{N-k}$ in decreasing order of similarity with $t_{1}$ . Again, the $K$ least similar neighbours in the reordered list are pruned to obtain $t^{\prime}_{2},t^{\prime}_{3},\ldots,t^{\prime}_{N-2k}$ . Next, we pick $t^{\prime}_{2}$ and repeat the same process. This continues for $l$ iterations. At each step, the nearest neighbours list is reordered based on the nearest neighbour obtained in the previous step, and the set is pruned. Essentially, by following the above procedure, we are constraining the nearest neighbours to be similar to each other in addition to being similar to the query term. A high value of $l\geq 10$ may lead to query drift. A low value of $l\leq 2$ essentially performs similar to the basic pre-retrieval model. We empirically choose $l=5$ as the number of iterations for this method. Let $\mathit{NN}_{l}(q)$ denote the iteratively pruned nearest neighbour list for $q$ . The expanded query is then constructed as in Section 2.1, except that $\mathit{NN}_{l}(q)$ is used in place of $\mathit{NN}(q)$ in Equation 1.

4 Extended Query Term Set

Considering NNs of individual query word makes a generalization towards the process of choosing expansion terms since a single term may not reflect the information need properly. For example, consider the TREC query Orphan Drugs where the respective terms may have multiple associations, not related to the actual information need. The conceptual meaning of conposition of two or more words can be achieved by simple addition of the constituent vectors.

Given a query $Q$ consisting of $m$ terms $\{q_{1},\ldots,q_{m}\}$ , we first construct $Q_{c}$ , the set of query word bigrams.

We define the embedding for a bigram $\langle q_{i},q_{i+1}\rangle$ as simply $\mathbf{q_{i}}+\mathbf{q}_{i+1}$ , where $\mathbf{q_{i}}$ and $\mathbf{q}_{i+1}$ are the embeddings of words $q_{i}$ and $q_{i+1}$ . Next, we define an extended query term set (EQTS) $Q^{\prime}$ as

For the proposed approaches, the effect of compositionality can be integrated by considering $Q^{\prime}$ of Equation 3 in place of $Q$ in Equation 1 and 2.

5 Retrieval

For our retrieval experiments, we used Language Model with Jelinek Mercer smoothing . The query model for the expanded query is given by

where $Q_{exp}$ is the set of top $K$ terms from $C$ , the set of candidate expansion terms. As described in Section 2.4, we can use $Q$ or $Q^{\prime}$ in Equation 4. The expansion term weights are assigned by normalizing the expansion term score (mean similarity with respect to all the terms in EQTS) by the total score obtained by summing over all top $K$ expansion terms. $\alpha$ is the interpolation parameter to use the likelihood estimate of a term in the query, in combination with the normalized vector similarity with the query.

Evaluation

We explored the effectiveness of our proposed method on the standard ad-hoc task using TREC collection as well as on the TREC web collection. Preciously, we use the documents from TREC disk 4 and 5 with the query sets TREC 6, 7, 8 and Robust. For the web collection, we use WT10G collection. The overview of the dataset used is presented in Table 1. We implemented our method Available from https://github.com/dwaipayanroy/QE_With_W2V using the Apache licensed Lucene search enginehttps://lucene.apache.org/core/. We used the Lucene implementation of the standard language model with linear smoothing .

Indexing and Word Vector Embedding. At the time of indexing of the test collection, we removed the stopwords following the SMARTftp://ftp.cs.cornell.edu/pub/smart/ stopword-list. Porter stemmer is used for stemming of words. The stopword removed and stemmed index is then dumped as raw text for the purpose of training the neural network of Word2Vec framework. The vectors are embedded in an abstract 200 dimensional space with negative sampling using 5 word window on continuous bag of words model. For the training, we removed any words that appear less than three times in the whole corpus. These are as par the parameter setting prescribed in .

Parameter setting. In all our experiments, we only use the ‘title’ field of the TREC topics as queries. The linear smoothing parameter $\lambda$ was empirically set to $0.6$ , which is producing the optimal results, after varying it in the range $[0.1,0.9]$ . The proposed methods have two unique parameters associated with them; $K$ , that is the number of expansion terms choosen from $Q_{exp}$ for QE, and the interpolation parameter $\alpha$ . In addition, the feedback based method (Section 2.2) has one more parameter, the number of documents to use for feedback. To compare the best performance of the proposed methods, we explored all parameter grids to find out the best performance of the individual approaches. The corresponding parameters, which are producing the optimal results, are reported in Table 3 along with the evaluation metrics.

2 Results

As an early attempt, we compared the effect of applyting composition, when computing the similarity between an expansion term and the query, for the pre-retrieval kNN based approach (Section 2.1). The relative performance is presented in Table 2. It is clear from the result that applying composition indeed affects the performance positively. Hence, we applied composition (for the similarity computation) in the rest of the approaches.

Table 3 shows the performance of the proposed method, compared with the baseline LM model and feedback model RM3 . It can be seen that the QE methods based on word embeddings almost always outperform the LM baseline model (often significantly). There does not seem to be a major difference in performance between the three variants, but the incremental method seems to be the most consistent in producing improvements. However, the performance of RM3 is significantly superior for all the query sets.

A more detailed query-by-query comparison between the baseline, incremental and RM3 methods is presented in Figure 1. Each vertical bar in the figure corresponds to a query, and the height of the bar is the difference in AP for the two methods for that query. The figures show that, as an expansion method, the incremental method is generally safe: it yields improvements for most queries (bars above the X axis), and hurts performance for only a few queries (bars below the X axis). However, RM3 “wins” more often than it loses compared to the incremental method. While these experiments provide some answers to questions 1 and 3 listed in the Introduction, question 2 is harder to answer, and will require further investigation.

Discussion

Distributed neural language model word2vec, possesses the semantic and contextual information. This contributes to the performance improvement over text similarity based baseline for each of the three methods. Query expansion intuitively calls for finding terms which are similar to the query, and terms which occurs frequently in the relevant documents (captured from relevance feedback). In the proposed embedding based QE techniques, the terms which are similar to the query terms in the collection-level abstract space are considered as the expansion terms. Precisely, in the K-NN based QE method, expansion terms are chosen from the entire vocabulary, based on the similarity with query terms (or, composed query forms). When the same K-NN based method is applied with feedback information, the search space is minimized, from the entire vocabulary, to the terms of top documents. However the underlying similarity measure, that is the embedded vector similarity in the abstract space, remains the same. This is the reason why K-NN and post-retrieval K-NN performs identically. It is found that there is no significant difference between the performance between the two K-NN based QE methodsUsing paired t-test with 95% confidence measure.. However those techniques fails to capture the other features of potential expansion terms, such as terms, frequently co-occurring with query terms. Experiments on the TREC ad-hoc and web datasets shows that the performance of RM3 is significantly better than the proposed methods which indicates that the co-occurrence statistics is more powerful than the similarity in the abstract space.

A drawback of the incremental KNN computation compared with post-retrieval KNN and pre-retrieval KNN QE is that the former takes more time, due to iterative pruning step involved.

Conclusion and Future Work

In this paper, we introduced some query expansion methods based on word embedding technique. Experiments on standard text collections show that the proposed methods are performing better than unexpanded baseline model. However, they are significantly inferior than the feedback based expansion technique, such as RM3, which uses only co-occurrence based statistics to select terms and assign corresponding weights. The obvious future work, in this direction, is to apply the embeddings in combination with co-occurrence based techniques (e.g. RM3). In this work, we restrict the use of embeddings only to select similar words in the embedded space. Thus a possible future scope is to use the embeddings exhaustively for utilizing other aspects of the embedded forms. In our experiments, we trained the neural network over the entire vocabulary. A possible future work is thus the investigation of local training of word2vec from pseudo-relevance documents which might get rid of the generalization effect when trained over the whole vocabulary.