A discriminative method for global query expansion and term reweighting using co-occurrence graphs

Abstract

This article presents a new query expansion (QE) method aiming to tackle term mismatch in information retrieval (IR). Previous research showed that selecting good expansion terms which do not hurt retrieval effectiveness remains an open and challenging research question. Our method investigates how global statistics of term co-occurrence can be used effectively to enhance expansion term selection and reweighting. Indeed, we build a co-occurrence graph using a context window approach over the entire collection, thus adopting a global QE approach. Then, we employ a semantic similarity measure inspired by the Okapi BM25 model, which allows to evaluate the discriminative power of words and to select relevant expansion terms based on their similarity to the query as a whole. The proposed method includes a reweighting step where selected terms are assigned weights according to their relevance to the query. What’s more, our method does not require matrix factorisation or complex text mining processes. It only requires simple co-occurrence statistics about terms, which reduces complexity and insures scalability. Finally, it has two free parameters that may be tuned to adapt the model to the context of a given collection and control co-occurrence normalisation. Extensive experiments on four standard datasets of English (TREC Robust04 and Washington Post) and French (CLEF2000 and CLEF2003) show that our method improves both retrieval effectiveness and robustness in terms of various evaluation metrics and outperforms competitive state-of-the-art baselines with significantly better results. We also investigate the impact of varying the number of expansion terms on retrieval results.

Keywords

BM25 co-occurrence graph information retrieval query expansion semantic similarity term reweighting

1. Introduction

With the advent of the Web, the volume of information available, particularly textual data, has continued to grow exponentially, and the number of documents storing this information continues to increase. Consequently, it is becoming increasingly difficult to find relevant documents in this large mass of information, especially in the case of short user queries. Indeed, despite the significant growth in data available nowadays, users often issue short queries. In average, users insert about three words in their search query [1,2], which is the same as two decades ago as reported by Lau and Horvitz [3]. Therefore, matching the user’s information need with relevant documents is challenging and complex, although this has always been the main challenge in information retrieval (IR). Besides, the user’s query usually omits important terms which allow the selection of relevant documents that meet the user’s needs. Hence, a poorly expressed query is unlikely to yield satisfactory results. To overcome the term mismatch problem, query expansion (QE) is one of the main tasks in IR, which refers to techniques that reformulate the user query by adding new terms that better express his or her information needs [4].

The aim of QE is to enrich the initial query with additional semantically related terms to enhance retrieval results. Indeed, QE methods are categorised into two main classes, namely local methods and global methods [5]. Local methods use retrieved documents produced by the user’s initial query to select expansion terms. Whereas in global methods, there is no need for an initial retrieval round. The entire data source is explored to extract expansion candidates.

A challenging problem in QE is the selection of relevant expansion terms, which do not harm but improve retrieval effectiveness. Generally, expansion terms are selected based on their similarity to individual query terms [6], that is, each term in the query individually chooses a set of related expansion candidates based on one-to-one associations. However, this does not properly reflect the semantic relatedness of an expansion term to the query as a whole, and thus the global sense of the query may be ignored [4]. It has been shown that the best approach to QE is to choose expansion terms that are related to the entire query [6,7]. This allows to capture the semantic relationships between the candidate expansion terms and the whole query, and then select the most strongly related terms.

Moreover, the effectiveness of the expansion process also depends on the number of selected terms and the way the new terms should be added to the query. Indeed, the expansion candidates do not have the same relevance to the query [8]. Therefore, they should be assigned weights reflecting their degree of similarity to the original query so that the most relevant ones obtain higher weights.

Furthermore, emphasis is mainly placed on measuring the relevance of the expansion terms to select those that are most similar to the initial query. Nevertheless, when a query contains several terms, they do not have equal importance or usefulness in selecting expansion candidates [9]. Indeed, some of the query terms may not be good at identifying relevant expansion candidates [6]. Therefore, we need to evaluate the discriminative power of each term in the query so that the most important ones will contribute more in the expansion process.

In light of the aforementioned points, we can agree that an effective QE strategy should take these different aspects into account to select the most relevant expansion terms that allow improving retrieval performance. The main contributions of this article can be summarised as follows:

We propose a new multi-step method for both QE and term reweighting, which relies on global analysis of the entire corpus using simple co-occurrence statistics.

We present a context window approach to construct term co-occurrence graphs, which allows the extraction of distributional knowledge representing semantic relationships between terms.

We employ a semantic similarity measure inspired by the Okapi BM25 model, which measures term–term similarity in co-occurrence graphs and provides an absolute evaluation of the discriminative power of terms. What’s more, our measure allows to compute one to many similarities.

Extensive experiments have been conducted on two languages to evaluate the performance of the proposed method in terms of both retrieval effectiveness and robustness. Results demonstrate its ability in enhancing the retrieval results and show significant improvements over competitive state-of-the-art baselines.

We also provide detailed interpretations, including a detailed analysis of parameter sensitivity and we investigate the effect of varying the number of expansion terms on retrieval results.

The remainder of the article is organised as follows. Section 2 presents the motivations of this work and posits our research objectives. Section 3 discusses related work. Section 4 outlines the proposed QE method. Experimental setup, test collections and evaluation metrics are presented in section 5. The experimental results are outlined and discussed in section 6. Finally, section 7 concludes the article and provides insights for future work.

2. Motivation and research objective

The main motivation of this work is to investigate how global statistics of term co-occurrence can be used effectively to enhance the process of QE and term reweighting considering the semantics of the whole query. Statistics of term co-occurrences have been widely used in multiple IR tasks to discover and express semantic relationships between terms [4,10]. Indeed, the use of term co-occurrences is one of the earliest approaches for automatic query expansion (AQE) [11,12], in which terms that are statistically related to the query are considered as potential expansion candidates. Nevertheless, a fundamental problem in this approach is the selection of terms that have high frequencies, and thus are not likely to be discriminative. A primary limitation is due to the manner in which the similarity between terms is measured [13]. Besides, terms’ position and proximity, which allow capturing their context, are usually not considered [4]. In this work, we use co-occurrence statistics across the entire document collection to find semantic relationships between query terms and candidate expansion terms. We represent a corpus as a graph, where nodes correspond to terms and edges denote co-occurrence relationships. In fact, text graphs are a well-explored area in IR [14] and the applications of such graphs are multiple (e.g. TextRank [15]). However, building a term co-occurrence graph and exploring its links is a challenging problem, especially for large graphs.

This article proposes a new global QE method which relies on statistical information of term co-occurrences to improve retrieval results. It allows to identify the most informative query terms and to penalise trivial terms. We explore the use of a context window-based approach to build our term co-occurrence graph over the entire corpus. We use a new measure inspired by the state-of-the-art Okapi BM25 model [16], which leverages the performance of this robust model to compute term similarity in co-occurrence graphs. The main objectives of this work are

To select expansion terms using their semantic relatedness to the query as a whole and automatically assign weights to the new terms according to their relevance to the query;

To evaluate the discriminative power of each query term, so that the most important ones will have a higher impact on the expansion process;

To ensure the effectiveness and the robustness of the proposed method in the case of short user queries.

Evaluation has been carried out on four test collections: two French collections provided by CLEF¹ [17,18] and two English collections provided by TREC,² including the standard Robust04 collection [19]. Experimental results show that our proposal significantly outperforms state-of-the-art baselines using various standard evaluation metrics.

In the following section, we provide an overview of related works, discussing their limitations and highlighting the theoretical and practical implications of our work.

3. Related work

QE has received considerable attention for several years. A great deal of effort has been devoted to the development of new QE techniques in the field of IR. In this context, a number of research surveys have been published [2,4,20]. The objective of QE is to reformulate the user’s initial query by adding new terms based on various selection criteria and usually involving a reweighting step. Indeed, the expansion terms are selected from the current document collection (endogenous resources) or from external data sources, such as Wikipedia (exogenous resources). In the literature, QE approaches can be mainly classified into two main categories: (1) local methods and (2) global methods [2,4,9]. In this section, we will mention some efforts on both categories of methods, focusing on statistical ones.

3.1. Local QE approaches

This class of QE approaches relies on the use of a local analysis of top-ranked or identified relevant documents resulting from an initial retrieval round in response to the original (non-reformulated) query. One of the earliest QE methods was proposed by Rocchio [21], who introduced the use of ‘relevance feedback’ for QE. In this technique, the user manually examines the results of the initial query and provides a judgement on the relevance of the retrieved documents. The collected feedback information is then used to reformulate the original query. Indeed, most of the relevance feedback methods are inspired by Rocchio’s algorithm [21]. However, a major drawback of the relevance feedback technique is that it requires time and effort on the part of the user. Pseudo-relevance feedback (PRF) is one of the most effective and popular AQE techniques, which was derived from relevance feedback. In PRF, the top-ranked $k$ documents retrieved by the initial query are assumed to be relevant, instead of user’s feedback. Hence, the QE process is done automatically and transparently to the user, without manual interaction. Croft and Harper [22] were the first to introduce the PRF technique for document retrieval. They made use of this technique in a probabilistic model. Indeed, the majority of local QE methods make use of the PRF technique [23].

Xu and Croft [9] used term co-occurrence statistics in an AQE technique called local context analysis (LCA). In this work, expansion terms are assigned scores based on their co-occurrence with the original query terms in the set of pseudo-relevant documents. Authors proposed a new metric that measures the co-occurrence of terms in the pseudo-relevant documents, taking into account their frequency in the whole collection and the inverse document frequency (IDF) of each query term to measure their importance. The main hypothesis is that terms that tend to co-occur with all query terms are good for expansion. Thereby, terms that co-occur with more query terms are assigned higher scores than those co-occurring with fewer query terms. The highest scoring expansion candidates are selected to construct the new query. The effectiveness of this technique was demonstrated using various test collections in three different languages: English, Spanish and Chinese [9]. Fonseca et al. [24] proposed a concept-based QE method by mining association rules. Using query logs, they extracted query pairs based on their co-occurrences in past user sessions. A directed graph is constructed from query relations to select concepts that are related to the initial query. The user is then asked to provide feedback and select the most related concepts to his or her query. Recently, Colace et al. [25] made use of a minimal relevance feedback to obtain expanded queries. They considered only endogenous resources to build a structured graph of weighted word pairs based on the probabilistic topic model [26]. Authors showed the effectiveness of the proposed method over a Kullback–Leibler divergence (KLD)-based QE method [27] using two different IR systems. More recently, Wang et al. [28] proposed a neural PRF framework, named NPRF, which integrates PRF for neural IR by end-to-end learning. Authors introduced three instantiations of the proposed framework using state-of-the-art neural IR models and demonstrated its ability in improving the performance of neural document retrieval through extensive experiments.

Much research has been conducted recently to improve relevance feedback, for example, using semantic similarity [29,30], matrix factorisation [31], fuzzy logic [32], linear methods [33], word embeddings [34 –36] and external knowledge sources [37]. However, one of the main challenges of the PRF technique is that the set of pseudo-relevant documents may contain a number of irrelevant documents, which will introduce noise into the expanded queries and thus adversely affect retrieval results [9]. Cao et al. [38] observed that many expansion terms that are very frequent in pseudo-relevant documents do not improve but harm retrieval effectiveness.

3.2. Global QE approaches

Global QE allows selecting expansion terms independently of the original query, that is, there is no need for an initial retrieval round. In this case, the entire data source is analysed to discover term associations and co-occurrence relationships [5,37]. Word embeddings have been used recently for AQE [6,39 –41] by exploring word relationships from embedding vectors. In these methods, term co-occurrence statistics computed in a same context window are employed to learn word vector representations based on word embedding algorithms, such as Word2vec [42]. The main assumption is that words in similar contexts are likely to have similar meanings. Fernández-Reyes et al. [6] apply global word embeddings to perform AQE. The word vector representations are computed based on the statistics of word co-occurrences across the entire document collection. A symmetrical similarity matrix is then constructed, which contains the cosine similarities between each pair of word vectors. Authors explored the use of different pooling strategies to capture query-vocabulary semantic closeness and elect semantically related terms according to their cosine similarity to the query as a whole. Their experiments on three CLEF collections showed the effectiveness of the proposed global QE method without using exogenous resources and without relevance feedback. Results also showed a decrease in retrieval effectiveness by increasing the number of expansion terms, meaning that some of the added terms brought noise into the expanded queries. In a similar work, Esposito et al. [41] proposed a hybrid QE approach using word embeddings and lexical resources to effectively address the IR-based question answering (QA) task.

Recently, Azad and Deepak [8] used external data sources in a global QE method by combining Wikipedia and WordNet [43]. A pre-processing step is first applied to extract individual terms and phrases from the initial queries. For QE using Wikipedia, a directed graph is constructed to represent in-links and out-links between Wikipedia articles. Expansion terms are then extracted considering their similarity to the initial query terms and their rareness across the entire Wikipedia dump. WordNet is used to select synonyms and hyponyms of the initial query terms as expansion candidates. A term frequency–inverse document frequency (TF–IDF)-based weighing scheme is proposed to rank the candidate terms. At last, authors used a correlation score to reweight the final set of expansion terms from both data sources with respect to the query as whole. The experiments showed significant improvements over the user’s non-expanded queries using various evaluation metrics. They also analysed the effect of varying the number of expansion terms on retrieval performance.

Bouziri et al. [44] proposed a new AQE method based on learning to rank association rules between terms, which are mined from the entire document collection. The association rules and queries are then represented as 12-dimensional feature vectors computed based on statistical distribution measures of terms, including TF and document frequency across the document collection. The main idea of the proposal is to rank candidate association rules to select the most effective ones to be used in the expansion process. Their experiments using long queries yielded significant improvements against the baseline queries on CLEF and TREC collections. However, results showed that the proposed method is not a valid choice for short queries, as in this case its performances were not good. More recently, promising results have been demonstrated using BERT (a neural network-based contextualised learning model for natural language processing (NLP) pretraining) for QE [45,46].

The use of semantic analysis (or semantic analytics) has received considerable attention to extract meaningful information from unstructured data [47]. In recent years, a great deal of research efforts has been performed to propose new methods incorporating semantic analysis [47 –50], especially with regard to social data content. Indeed, it allows inferring and extracting semantic concepts that help to enrich textual content by leveraging various knowledge structures, such as ontologies and Linked Data [48]. In the context of QE, the use of semantic analysis techniques helps to identify and extract additional query-related concepts, thus enriching the semantics of the query by finding relevant terms and expressions in the text, especially in the case of ambiguous queries. An interesting study discussing the use of ontologies for QE was presented by Bhogal et al. [20]. More recently, Raza et al. [51] presented a taxonomy and a survey of recent approaches to semantic QE that take advantage of various knowledge structures. In our work, we focus on the extraction of semantic information from unstructured textual corpora by analysing the probabilistic distribution of terms using global co-occurrence statistics. That is, our method falls into the category of Corpus-Specific Global QE Methods [4]. We try to extract relevant semantically related features for QE using a new way of exploring statistical information about terms and the contexts in which they appear, which is also known as distributional semantics. Incorporating semantic analysis can further enhance the term selection process and will be considered in future work.

3.3. Query reweighting

The QE process usually involves a reweighting step in which the added terms are assigned weights that reflect their importance. One of the earliest work on query reweighting was proposed by Robertson and Jones [52]. Their proposal relies on the relevance probability. The authors examined the use of statistical techniques to assign weights to the query terms by analysing their distribution in relevant and irrelevant documents. Indeed, the TF–IDF weighting scheme [53] was established based on successive refinements of this work. Kim et al. [54] examined the use of term co-occurrence similarity in a method for QE and term reweighting. They considered the distribution similarity between candidate expansion terms and the initial query within feedback documents. The new weights of the query terms are calculated using fuzzy inference. In our work, we use co-occurrence statistics to expand the queries and reweight the expansion terms.

In many of the aforementioned work, the importance of terms is evaluated using the IDF, which measures whether a term is rare or common and assigns higher values to the less-frequent terms across a set of documents. Our work stands by the fact that we try to evaluate the importance of terms based on co-occurrence statistics. We present a new method of using term co-occurrence statistics effectively for both term selection and reweighting steps while considering the semantic of the whole query. Indeed, our proposal provides an absolute evaluation of the discriminative power of terms by penalising those that tend to co-occur with many other words across the entire collection, which allows identifying the most important query terms. Besides, a main advantage of using a term co-occurrence graph is that it can be easily updated by adding new nodes or updating the weights of edges without having to rebuild the entire graph. Not the least, we investigate the impact of varying the number of expansion terms on retrieval results, showing that emphasis should be placed on selection strategies to generate the most relevant ones rather than seeking their optimal number.

Several measures have been used in the literature to evaluate the similarity of terms for QE, such as Cosine similarity, Dice coefficient, Jaccard coefficient and Mutual Information [23]. These measures consider that the similarity relation between terms is symmetric. That is, given two terms $t_{1}$ and $t_{2}$ , the similarity of $t_{1}$ to $t_{2}$ is equal to the similarity of $t_{2}$ to $t_{1}$ , that is, $sim (t_{1}, t_{2}) = sim (t_{2}, t_{1})$ . However, the similarity of terms is not always a symmetric relation, especially when comparing very frequent terms with less-frequent terms [55,56]. The similarity relation $t_{1}$ is similar to $t_{2}$ does not generally mean that the converse similarity $t_{2}$ is similar to $t_{1}$ is true. Indeed, the use of asymmetric measures is related to the notion of relative salience [55]. For example, we say that a statue resembles a real person but we do not say the inverse. In QE, adding the term Mammalia to a query containing the term Animal may enhance results. However, the term Animal would enlarge the coverage of a query containing the term Mammalia, that is, returning documents which talk about other types of animals. Therefore, there is a need for a measure that handles the asymmetric term–term similarity given a context, for better selection of expansion terms. In our work, we propose a new way to measure the semantic relatedness of terms that allows to effectively incorporate co-occurrence information into both the evaluation of terms’ discriminative power and in measuring one-to-many term similarity given a context. We show that the proposed QE method generates useful expansion terms that are strongly related to the whole query. Besides, the proposed method includes two tuning parameters, which enables to control how relevance changes as the number of co-occurrences increases. This allows to address the limitation of co-occurrence-based approaches in handling highly frequent terms that can unfairly affect the resulting QE model than other terms do. As our results will demonstrate, better performance could be achieved if these parameters are correctly adjusted.

Concisely, our proposal can be classified as a global QE method. We propose a new method for AQE using only endogenous resources without relevance information. We discuss the details of the proposed method in the following section.

4. Proposed QE method

Our QE method consists of two main processes. The objective of the first one, which is executed offline, is the construction of a term co-occurrence graph after pre-processing the input corpus. This process is performed only once for a specific collection. The second process is run online. Its purpose is the construction of an expanded query by selecting expansion terms based on their semantic similarity to all its terms as a whole. The selected terms are reweighted, so that the most important ones receive higher weights. The proposed method can be divided into three steps as illustrated in Figure 1: (1) data pre-processing, (2) graph construction and (3) QE. The three steps are detailed in the following subsections.

4.1. Data pre-processing

Pre-processing of a data source is an essential step in any QE method. The main purpose of this step is to convert the data used for QE into a clean and consistent format that will be easier to process in subsequent steps [4]. Three common pre-processing tasks are involved in our method, as follows:

Tokenisation: the input text corpus is split into sentences, which are then tokenised into individual terms (unigrams). In addition, all terms are lowercased.

Stopword removal: all non-informative words are removed using standard stopword lists.

Stemming: all terms are reduced to their stems using language-specific stemming algorithms. Porter stemmer [57] is widely used for stemming English texts [8], while the Snowball stemmer is commonly employed for other languages [58].

The output of this step is a clean corpus of plain text.

4.2. Corpus-based co-occurrence graph

After performing the various text pre-processing tasks, we build from the resulting corpus a graph representing the co-occurrence relationships between terms. Formally, the textual corpus is modelled as a co-occurrence graph $G = (N, E, w)$ , consisting of the set of nodes $N$ , also called vertices, and the set of edges $E$ , that is, the links that connect the nodes. The nodes in the graph are associated to terms, and the edges represent co-occurrence relations between terms. The edges in the graph are weighted, which means that each edge has an associated weight $w_{ij}$ ( $w_{ij} \geq 1$ ). The weight of an edge represents the overall co-occurrence count of the corresponding pair of terms within the entire corpus. Specifically, edges between nodes are created once the corresponding terms co-occur within a context window of $n$ terms. This approach allows the extraction of distributional knowledge representing statistical relations between terms. The graph is undirected because the edges indicate term–term relationships, meaning that all edges are unordered pairs of terms. The order of a graph is the number of its nodes $| N |$ . Therefore, the order of the co-occurrence graph $G$ is the number of distinct terms in the corpus (i.e. the vocabulary). Given a graph of order $n$ , the maximum number of edges that are incident to each node (degree of a node) is $n - 1$ .

The context window approach allows capturing the semantic relations between terms based on their statistical distribution and co-occurrences [4], which is also known as distributional semantics or distributional similarity. In this approach, the context of a term is simply defined as its neighbouring terms within a specified window. In our method, we use a symmetric sliding window to count the co-occurrence of terms over sentences. Thereafter, the co-occurrence graph is built using the obtained global statistics of term co-occurrence.

Figure 2 shows an example of an undirected weighted co-occurrence graph constructed with a window-size equal to 2 over the following two sentences: The context window approach was applied in multiple IR tasks. Co-occurrences are counted in specified window. For instance, taking ‘approach’ as the target term, its context terms in this case will be {context, window, was, applied}.

4.3. Query Expansion

Once the term co-occurrence graph has been constructed, it is mined to select semantically related terms to a given query. We define the following two constraints for selecting candidate expansion terms:

A good expansion term should be related to the whole query, that is, a term that has semantic relatedness with all query terms.

The impact of a given query term for selecting expansion candidates depends on its discriminative power.

To satisfy these two constraints, we need a similarity measure that considers one-to-many associations [4] and allows to evaluate the discriminative power of terms. To this end, we compute the semantic similarity of candidate expansion terms to the whole query using a new measure called BM $25_{cog}$ (which stands for BM25 for co-occurrence graphs). As its name suggests, this measure is inspired by the Okapi BM25 model [16,59] and leverages the performance of this state-of-the-art model.

Before going into further details, we briefly recall the main properties of the Okapi BM25 model. Given a query $Q$ containing terms $(q_{1}, q_{2}, . . ., q_{m})$ , the BM25 score of a document $D$ to $Q$ is calculated as follows [16]

BM 25 (Q, D) = \sum_{i = 1}^{m} IDF (q_{i}) \times \frac{(k_{1} + 1) \times tf (q_{i}, D)}{k_{1} \times (1 - b + b \times \frac{dl}{avgdl}) + tf (q_{i}, D)}

(1)

where $tf (q_{i}, D)$ is the TF of the query term $q_{i}$ in document $D$ ; $dl$ denotes the length of document $D$ (number of terms in the document); $avgdl$ is the average document length in the whole document collection; $k_{1}$ and $b$ are the free tuning parameters.

$IDF (q_{i})$ represents the IDF of the query term $q_{i}$ . It reflects how much a term is distributed over all of the documents and allows penalising terms that are very common, that is, they will get low values. It is calculated as follows

IDF (q_{i}) = \log \frac{N - df (q_{i}) + 0.5}{df (q_{i}) + 0.5}

(2)

where $N$ is the total number of documents in the collection; $df (q_{i})$ is the number of documents where the query term $q_{i}$ appears. Using 0.5 is a kind of smoothing which is justified by the limits of maximum likelihood estimate (MLE) which penalises rare events [23]. Smoothing allows to avoid assigning a null probability, or zero values, to unseen (non-occurring) terms.

The intuition behind the IDF factor in BM25 is to assign a higher multiplier to the more important query terms, which are relatively infrequent throughout the document collection. They will contribute more to the final score than common terms that are found in almost all documents and thus are less important.

As mentioned previously, the second process of our method is run online to obtain an expanded query. Each term that co-occurs with at least one of the query terms is considered as a candidate expansion term. Therefore, the top $n$ terms with the highest scores are selected to form the new query. These scores are calculated based on the co-occurrence statistics from the constructed graph. In our work, we consider the following properties:

For each term $t$ , the co-occurrence degree of $t$ , denoted $co_degree (t)$ , is the number of edges that are incident to $t$ .

For each connected pair of terms $t_{1}$ and $t_{2}$ , the weight of the edge linking the two terms, denoted $w (t_{1}, t_{2})$ , is the total number of co-occurrences of $t_{1}$ and $t_{2}$ .

For each term $t$ , the total weight of $t$ , denoted $sum_w (t)$ , is the sum of the weights of the edges that are incident to $t$ .

The semantic similarity in the co-occurrence graph is calculated using BM $25_{cog}$ . Let $Q$ be a query with $m$ terms $(q_{1}, q_{2}, . . ., q_{m})$ and $t_{c}$ be a candidate expansion term; the similarity score of $t_{c}$ to $Q$ is calculated as follows

BM 25_{cog} (Q, t_{c}) = \sum_{i = 1}^{m} INF (q_{i}) \times \frac{(k_{1} + 1) \times w (q_{i}, t_{c})}{k_{1} \times (1 - b + b \times \frac{sum_w (t_{c})}{avgsum_w}) + w (q_{i}, t_{c})}

(3)

where $w (q_{i}, t_{c})$ is the number of co-occurrences between the query term $q_{i}$ and the candidate expansion term $t_{c}$ ; $sum_w (t_{c})$ is the sum of the weights of the edges linked to $t_{c}$ , which represents the total number of co-occurrences of the term $t_{c}$ ; $avgsum_w$ is the average number of co-occurrences in the whole graph; $k_{1}$ and $b$ are the free tuning parameters.

The intuition behind the BM $25_{cog}$ score is to capture (1) the semantic relatedness between the initial query terms and the candidate expansion terms and (2) the importance of each query term, that is, whether the current query term is good for selecting relevant expansion terms. As we can see, the above formula contains a number of features.

$w (q_{i}, t_{c})$ indicates how many times the ith query term co-occurs with the expansion candidate $t_{c}$ . By analogy to the TF component in Okapi BM25, a term that tends to co-occur frequently with the query terms is more likely to be related to the query than a term with a small number of co-occurrences. Consequently, the more times the query terms co-occur with a candidate expansion term, the higher its score will be.

The ratio between the parameters $sum_w (t_{c})$ and $avgsum_w$ can be considered as how frequent the total number of co-occurrences of a term is relative to the average number of co-occurrences in the graph. If this factor is higher than the average, the denominator gets bigger (decreasing the score) and if it is lower than the average, the denominator gets smaller (increasing the score). Therefore, the higher the total number of co-occurrences of an expansion candidate (co-occurrences that do not match the query terms), the lower its score will be. Intuitively, if a term $t_{1}$ has a large number of co-occurrences ( $sum_w (t_{1})$ ) and co-occurs with the query term $n$ times, it is less likely to be similar as a term $t_{2}$ having a lower number of co-occurrences ( $sum_w (t_{2})$ ), which co-occurs with the query term the same number of times. This is analogous to document length normalisation with the parameters $dl$ and $avgdl$ in the original BM25 formula for query-document matching.

The importance of each query term is evaluated by the $INF$ factor of our formula. By analogy to the IDF factor in Okapi BM25, $INF (q_{i})$ is the inverse node frequency of the query term $q_{i}$ in the whole co-occurrence graph. It measures how often a term co-occurs with all of the other terms and penalises common terms. $INF$ is calculated as follows

INF (q_{i}) = \log \frac{N - co_degree (q_{i}) + 0.5}{co_degree (q_{i}) + 0.5}

(4)

where $N$ is the total number of terms (or nodes) in the graph and $co_degree (q_{i})$ is the number of terms in the graph that co-occur with the query term $q_{i}$ .

Some of the query terms may not be good for selecting expansion terms [6,9]. The intuition behind the $INF$ factor is to check whether a query term is common or rare across all the other terms. Therefore, terms that tend to co-occur with many other terms will get low values, while the most important query terms will contribute more to the final score of an expansion candidate.

4.3.1. Term Reweighting

After selecting the most relevant expansion terms, which are ranked according to their similarity scores with the initial query, the top $n$ candidates are chosen as the final set of expansion terms that form the new query. A reweighting step is then applied to assign weights to the new query terms. We have shown that the BM $25_{cog}$ scores strongly reflect and capture the semantic relatedness of each expansion term to the query as a whole. Therefore, the scores produced by BM $25_{cog}$ can be used not only to select but also to reweight the expansion terms. A simple way to do this is to attribute normalised weights to the expansion terms based on their similarity scores. Normalisation can be performed by scaling the obtained scores between 0 and 1, so that the expansion terms get lower weights than the original query terms, which have a default weight of 1.

4.3.2. Theoretical interpretation of INF information

According to Shannon’s Information Theory [60], the information content (IC) of an event $x$ having a probability of occurring $P (x)$ is defined as

IC (x) = - \log (P (x)) = \log \frac{1}{P (x)}

(5)

The basic assumption behind this is that events or messages with low probability of occurrence yield more IC than events with high probability of occurrence. For instance, the message The sun will shine contains less information than the message There will be an eclipse of the sun, which is a rare event and we get a lot of information from it.

Intuitively, we can assume that the higher a term co-occurs with other terms, the less information it contains. Suppose a query term $q_{i}$ that co-occurs with $co_degree (q_{i})$ terms. Then a randomly picked term $t$ will co-occur with the term $q_{i}$ with probability $\frac{co_degree (q_{i})}{N}$ , where $N$ is the total number of terms (or nodes) in the co-occurrence graph. Thus, the IC of the message t co-occurs with $q_{i}$ is

- \log \frac{co_degree (q_{i})}{N} = \log \frac{N}{co_degree (q_{i})}

(6)

Now, say that we have two query terms $q_{1}$ and $q_{2}$ . If the two terms co-occur with other terms entirely independently of each other, then the probability of having both $q_{1}$ and $q_{2}$ co-occurring with a randomly picked term $t$ is

\frac{co_degree (q_{1})}{N} \times \frac{co_degree (q_{2})}{N}

(7)

The IC of this event according to Shannon’s definition is

\log \frac{N}{co_degree (q_{1})} + \log \frac{N}{co_degree (q_{2})} = \sum_{i = 1}^{2} \log \frac{N}{co_degree (q_{i})}

(8)

Now having a query with $m$ terms, we get

\sum_{i = 1}^{m} \log \frac{N}{co_degree (q_{i})}

(9)

With a small variation (cf. equation (4)), this is exactly what is expressed by the $INF$ factor of BM $25_{cog}$ .

4.3.3. Illustrative example

As an example, let us consider the query Q = Parkinson disease from the TREC Robust04 test collection, which is composed of the two terms $q_{1}$ = Parkinson and $q_{2}$ = disease. In this query, the term Parkinson is more important than disease as Parkinson occurs 666 times throughout the collection, while disease occurs 17,588 times. We want to give higher scores to terms that will be more useful in identifying relevant expansion terms. The $INF$ factor of our formula is intended to reflect the importance of each term in the query. Thus, the $INF$ value should be higher for the term Parkinson than for the term disease.

The co-occurrence graph built on the Robust04 test collection is made up of 175,759 terms ( $N$ ). In this graph, the term Parkinson co-occurs with 3028 terms $(co_degree (Parkinson) = 3028)$ ³ and the term disease co-occurs with 19,937 terms $(co_degree (disease) = 19, 937)$ . With these values, the $INF$ scores of the two query terms according to equation (4) are

INF (Parkinson) = \log \frac{175, 759 - 3028 + 0.5}{3028 + 0.5} = 4.04

INF (disease) = \log \frac{175, 759 - 19, 937 + 0.5}{19, 937 + 0.5} = 2.05

As can be seen, the term Parkinson has fewer co-occurrences in the graph than the term disease, resulting in a higher $INF$ score. This demonstrates that the $INF$ factor provides an absolute evaluation of the discriminative power of a term, allowing the most important terms in the query to contribute more to the final score for selecting relevant expansion terms.

After calculating the $INF$ score of each query term, we take an example of three terms as potential expansion candidates to illustrate the QE process. As mentioned above in this section, a candidate expansion term is a term that has at least a co-occurrence relationship with one of the query terms. Figure 3 shows a subgraph of the complete co-occurrence graph built on the Robust04 collection. The subgraph represents three terms $t_{1}$ = dopamine, $t_{2}$ = patient and $t_{3}$ = viral, which have relations with the query Q = Parkinson disease and thus are possible expansion query terms. According to Cao et al. [38], we can distinguish three groups of expansion terms: good, bad and neutral. The first candidate term dopamine is highly related to the query and thus represents a good expansion term. The second term patient is a neutral term (i.e. it has a little impact on the retrieval effectiveness). The third term viral is not relevant to the query and thus is a bad expansion term, which brings noise to the results. In this example, stems are restored to their original forms for better readability.

As we can see in Figure 3, the term dopamine co-occurs with the query term Parkinson 14 times (i.e. $w (Parkinson, dopamine) = 14$ ) and with the query term disease 8 times ( $w (disease, dopamine) = 8$ ). In the complete co-occurrence graph built on the Robust04 collection, the total number of co-occurrences of the term dopamine is 884 (i.e. $sum_w (dopamine) = 884$ ). The average number of co-occurrences in the graph is 48,810 (i.e. $avgsum_w = 48, 810$ ). Table 1 summarises the corresponding values of the three candidate terms. With these values, the $BM 25_{cog}$ scores of the three candidate terms according to equation (3)⁴ are calculated as follows

\begin{matrix} \begin{matrix} BM 25_{cog} (Q, t_{1}) = \sum_{i = 1}^{2} INF (q_{i}) \times \frac{(1.2 + 1) \times w (q_{i}, t_{1})}{1.2 \times (1 - 0.75 + 0.75 \times \frac{sum_w (t_{1})}{avgsum_w}) + w (q_{i}, t_{1})} \\ BM 25_{cog} (Q, t_{1}) = 4.04 \times \frac{(1.2 + 1) \times 14}{1.2 \times (1 - 0.75 + 0.75 \times \frac{884}{48810}) + 14} \end{matrix} \\ + 2.05 \times \frac{(1.2 + 1) \times 8}{1.2 \times (1 - 0.75 + 0.75 \times \frac{884}{48810}) + 8} \\ = 8.69 + 4.34 \\ = 13.03 \end{matrix}

Table 1.

Different co-occurrence values of the three candidate expansion terms.

Q = Parkinson disease	$t_{1}$ = dopamine	$t_{2}$ = patient	$t_{3}$ = viral
$q_{1}$ = Parkinson	$w (q_{1}, t_{1}) = 14$	$w (q_{1}, t_{2}) = 30$	$w (q_{1}, t_{3}) = 0$
$q_{2}$ = disease	$w (q_{2}, t_{1}) = 8$	$w (q_{2}, t_{2}) = 280$	$w (q_{2}, t_{3}) = 396$
$sum_w (t_{c})$	$sum_w (t_{1}) = 884$	$sum_w (t_{2}) = 509, 996$	$sum_w (t_{3}) = 164, 077$

Likewise, the $BM 25_{cog}$ scores of the three candidate expansion terms are as follows:

$BM 25_{cog} (Q, t_{1}) = 13.03$

$BM 25_{cog} (Q, t_{2}) = 11.07$

$BM 25_{cog} (Q, t_{3}) = 4.47$

According to the results, we can state the following:

The term dopamine, which is strongly related to the query is scored highest among the other candidate terms. This demonstrates the ability of the proposed measure to capture the semantic relationship between the query terms and good expansion candidates.

Although the neutral term patient has more co-occurrences with the query terms compared with the term dopamine, it gets a lower score because it presents a higher number of co-occurrences with the rest of the terms in the corpus ( $sum_w (patient) = 509, 996 > sum_w (dopamine) = 884$ ) and is therefore penalised. Terms that tend to co-occur with many other terms (co-occurrences not matching the query terms) are not likely to be discriminative and hence should have lower scores.

The irrelevant term viral, which has the highest number of co-occurrences with the query term disease, was penalised because it has no co-occurrence with the query term Parkinson and therefore received the lowest score among the other candidate terms. This shows the advantage of the $BM 25_{cog}$ score for calculating the similarity of the candidate expansion terms with respect to the whole query and thus for capturing the overall sense of the query, which allows to discard bad expansion candidates.

To analyse the quality of the expansion terms generated for topic 406 from the Robust04 collection: Parkinson’s disease, we present in Table 2 the top 10 expansion terms obtained with the proposed algorithm and using two other state-of-the-art algorithms, namely the Bose–Einstein (Bo1) model [61] and the KLD model [27]. The candidate expansion terms are ordered according to their ranking score obtained by each method.

Table 2.

Top 10 expansion terms obtained with our proposed method and two other state-of-the-art models Bo1 and KLD for the TREC Robust04 topic 406 ‘Parkinson disease’.

Proposed method	Bo1	KLD
1-alzheimer	1-alzheimer	1-alzheimer
2-dopamine	2-cell	2-cell
3-udall	3-transplant	3-transplant
4-dementia	4-fetal	4-brain
5-mptp	5-brain	5-fetal
6-fetal	6-tissue	6-tissue
7-degenerative	7-dementia	7-research
8-l-dopa	8-research	8-dementia
9-neurological	9-patient	9-drug
10-neurologists	10-symptom	10-patient

KLD: Kullback–Leibler divergence.

The Bo1 QE model derives the informativeness of candidate expansion terms from the divergence between their distribution in the set of the highest ranked documents and a random distribution. In the KLD model, the most informative terms are those having a high probability distribution in the top-ranked documents and a low probability distribution in the entire corpus.

Observing the top 10 expansion terms generated in Table 2, we can see that many relevant terms that are semantically related to the initial query were only selected by our method. For instance, dopamine (lack of dopamine is the primary factor of Parkinson’s disease),⁵udall (Centres of Excellence carrying out important research on Parkinson’s disease), mptp (a toxic chemical that causes permanent symptoms of Parkinson’s disease), l-dopa (the most effective Parkinson’s disease medication) and even all the other selected terms are semantically related to the query terms. According to Table 2, we notice that the proposed QE method generates terms that are strongly related to the query and are more appropriate than the terms obtained for other methods, where it can be observed that many of the selected terms are general terms that are not discriminative. In summary, this example shows the effectiveness of the proposed QE method in addressing the vocabulary mismatch problem by generating useful expansion terms.

5. Experimental design

5.1. Test collections and evaluation campaigns

Test collections are used to evaluate the effectiveness of IR systems. A test collection consists of three parts: a corpus of documents on which the retrieval is carried out, a set of test queries (called topics), which express the information needs and a set of relevance judgements (called qrels), which includes a list of relevant and irrelevant documents for each test query.

Numerous evaluation campaigns have been organised, providing standard test collections to support research within the IR community, such as TREC and CLEF. TREC is the leading evaluation campaign in the IR field [23]. It was started in 1992 with the aim of supporting large-scale evaluation by providing large test collections. It covers a range of different IR tasks, or tracks, such as ad hoc search, QA, text summarisation, etc. In contrast, CLEF is the European counterpart of TREC, which was launched in 2000 with an emphasis on European languages, monolingual and cross-language IR.

To validate our method, we conducted extensive experiments using four test collections: two French collections provided by CLEF and two English collections provided by TREC. The two French collections from CLEF are CLEF2000 and CLEF2003 [17,18], which were used in the French Ad hoc Monolingual Task in years 2000 and 2003. The CLEF2000 collection, with 34 topics, is made up of 44,013 French news articles from 1994 published by the French journal Le Monde. The CLEF2003 collection is composed of three subcollections containing more than 129,000 documents on 52 topics, which includes newspaper articles (Le_Monde94) and various articles edited by the Swiss news agency (French SDA94 and French SDA95).

The test collections from TREC used in our experiments are the standard Robust04 collection [19] and the new Washington Post collection,⁶ which offer a very large set of documents. The former was used in the TREC 2004 Robust Track focusing on poorly performing topics. This collection contains 249 topics and over 500,000 news articles covering the period 1989–1996. They were collected from different sources (the Financial Times Limited, the Federal Register 94, the Foreign Broadcast Information Service and the Los Angeles Times). For illustration purposes, we show an example of topic 406 from the Robust04 collection in Figure 4. The Washington Post collection was first introduced in the TREC 2018 Common Core Track. It consists of 50 topics and over 600,000 documents comprising 5 years of newswire articles and blog posts published by the American journal Washington Post from January 2012 through August 2017. Detailed statistics about the four test collections are provided in Table 3.

Table 3.

Statistics of test collections.

Collection	Document set	#doc	Size	#vocabulary	#query	#qrels
CLEF2000	Le_Monde94	044,013	0144 MB	041,838	034	00528
CLEF2003	Le_Monde94 + Fr_SDA94 + Fr_SDA95	129,806	0331 MB	060,275	052	00946
Robust04	TREC Disks 4 & 5 minus Congressional Record	528,155	1904 MB	175,759	249	17,412
TREC2018	TREC Washington Post Corpus	608,180	6900 MB	187,173	050	03948

5.2. Pre-processing and indexing

We used the TERRIER⁷ IR platform in all our experiments for indexing and retrieval. We indexed the English and French collections using single keywords as indexing units. English documents and queries were stemmed using the Porter Stemmer, and stopwords were discarded using the standard stopword list from TERRIER. Similarly, for the French collections, the French Snowball Stemmer was applied for stemming and a stopword list containing 463 words⁸ was used. We considered only the title field of all topics as queries in our experiments, which mimics a real-life user need where queries are short [1,2].

5.3. Evaluation metrics

We evaluated the results using standard IR evaluation metrics, namely mean average precision (MAP), geometric mean average precision (GMAP), precision at top 5 ranked documents (P@5), P@10, P@30, binary preference (bpref), R-precision (Rprec) and normalised Discounted Cumulative Gain calculated for the top 10 retrieved documents (nDCG@10) [23]. In addition, statistical significance tests in terms of retrieval effectiveness were conducted using the two-tailed paired Student’s t-test at a 95% confidence level (i.e. $p_value < 0.05$ ). Besides, the robustness of the proposed method was evaluated using the standard robustness index (RI) [62].

5.4. Parameter settings

For each collection, the co-occurrence graph was constructed by considering co-occurrences at the sentence level, that is, using a dynamic context window equal to sentence length. In other words, two terms are considered to be co-occurring if both terms occur in the same sentence.

The model’s free parameters were optimised for each collection according to the MAP evaluation measure. We conducted five-fold cross-validation over the queries in the tuning process as in Huston and Croft [63]. The K-fold cross-validation allows optimising the parameters while avoiding overfitting [63]. To this end, the queries for each test collection were randomly split into five-folds. Then, the parameters were tuned on four-of-five folds and the last fold was used to test the optimal settings. This process is carried out five times, each time using a different fold for testing. We tuned the value of the parameter $b$ from 0.10 to 0.90 in increments of 0.05 and the value of the parameter $k_{1}$ from 0.1 to 3.0 in increments of 0.1, giving a total of 510 combinations.

We also evaluated the effectiveness of the proposed method by varying the number of expansion terms.

6. Experimental results

To evaluate and compare the effectiveness of the proposed method, we used the following strategies:

No Expansion: the non-expanded queries were employed using the state-of-the-art Okapi BM25 model for ranking, which was standardly used as a baseline in the literature [64]. Results obtained in this case are referred as baseline.

Bo1 QE: we employed the Bose–Einstein statistics-based (Bo1) model [61] to expand the initial queries. The Bo1 model is one of the most effective and stable Divergence From Randomness (DFR) term weighting models [65].

KLD QE: the KLD model [27] was employed for expanding the initial queries. KLD is a distribution-based QE method, which relies on the analysis of the probability distributions of terms in the pseudo-relevant documents and in the entire collection [27].

QE with fixed weight: our QE method without applying the reweighting step. In this case, the expansion terms were assigned a fixed weight, so that the sum of their weights is equal to the sum of the weights of the original query terms.

QE + Reweighting: our QE method was applied with reweighting of the expansion terms. The new query consists of the original terms with a weight equal to 1 and the expansion terms with normalised weights calculated by BM $25_{cog}$ .

In all configurations, we used the Okapi BM25 model with TERRIER’s default settings as a ranking model. The top 1000 documents were retrieved for each query.

We conducted several experiments to evaluate the performance of our QE method. Experimental results comparing different configurations are summarised in Tables 4 and 5. The superscript * indicates that the improvements over the non-expanded baselines are statistically significant (Student’s t-test with $p_value < 0.05$ ). Tables 4 and 5 show retrieval results on the four test collections regarding MAP, P@10, nDCG@10 and bpref. We also present the percentage of the MAP increase (within parentheses) against the non-expanded baselines.

Table 4.

Retrieval results for English collections.

Method	Robust04				TREC2018
	MAP(%Chg_.baseline)	P@10	nDCG@10	bpref	MAP(%Chg_.baseline)	P@10	nDCG@10	bpref
Baseline	0.2363	0.4100	0.4218	0.2452	0.2322	0.4240	0.3804	0.2958
Bo1	0.2532* (+7.15)	0.3984	0.4136	0.2519	0.2643 (+13.82)	0.4120	0.3728	0.3083
KLD	0.2509* (+6.18)	0.4068	0.4200	0.2494	0.2653*(+14.25)	0.4180	0.3752	0.3069
BM $25_{cog}$ QE (fixed weight)	0.2543* (+7.62)	0.4165	0.4242	0.2595*	0.2599* (+11.93)	0.4420	0.4144	0.3162*
BM $25_{cog}$ QE	0.2577*(+9.06)	0.4245	0.4329	0.2619*	0.2609* (+12.36)	0.4400	0.4119	0.3178*

MAP: mean average precision; KLD: Kullback–Leibler divergence.

The superscript * denotes that the improvements over the non-expanded baseline are statistically significant (t-test with $p_value < 0.05$ ). The highest value in each column is marked in bold.

Table 5.

Retrieval results for French collections.

Method	CLEF2000				CLEF2003
	MAP(%Chg_.baseline)	P@10	nDCG@10	bpref	MAP(%Chg_.baseline)	P@10	nDCG@10	bpref
Baseline	0.2677	0.2235	0.3289	0.2750	0.3656	0.2808	0.4289	0.3471
Bo1	0.2671 (−00.22)	0.2382	0.3370	0.2553	0.3672 (+00.44)	0.3058	0.4421	0.3375
KLD	0.2669 (−00.30)	0.2471	0.3369	0.2578	0.3686 (+00.82)	0.3000	0.4413	0.3347
BM $25_{cog}$ QE (fixed weight)	0.3078* (+14.98)	0.2941*	0.3941*	0.3032*	0.4055* (+10.91)	0.3096	0.4683	0.3615
BM $25_{cog}$ QE	0.3176*(+18.64)	0.2971*	0.4082*	0.3160*	0.4192*(+14.66)	0.3288*	0.4909*	0.3678

MAP: mean average precision; KLD: Kullback–Leibler divergence.

The superscript * denotes that the improvements over the non-expanded baseline are statistically significant (t-test with $p_value < 0.05$ ). The highest value in each column is marked in bold.

According to Tables 4 and 5, we can see that the proposed QE method outperforms the non-expanded baseline in all cases and across all four test collections. The improvements are always statistically significant in terms of MAP and bpref, reaching 12.36% and 18.64% gains in MAP on the English and French collections, respectively. As for the nDCG and the precision of the top 10 documents, it can be observed that the results are improved on all collections with statistically significant differences on the French collections, where we can notice up to 33% improvement in terms of precision on the CLEF2000 collection. These results highlight the effectiveness of our proposed QE method, leading to significant improvements in retrieval performance of the state-of-the-art Okapi BM25 model on various test collections and two different languages.

Observing the results obtained when assigning fixed weights to the expansion terms, we can see that performance is better when applying the reweighting step of our proposed method. In this case, this means that the most relevant expansion terms are assigned higher weights, which leads to better results.

Compared with Bo1 and KLD, we note that our method achieves better results in all cases regarding P@10, bpref and nDCG@10. Similar increases are also observed in terms of MAP, where we can see that our method performs better on every collection except the Washington Post collection for which we notice a slightly better performance with Bo1 and KLD. Furthermore, when comparing both baseline methods and the non-expanded baseline, we note that precision is hurt for the English collections, which means that the expansion terms in this case negatively affect precision. Similar behaviour is also observed in terms of nDCG@10, which is used to measure the ranking capability of retrieval algorithms [66]. We also see that the results are degraded in terms of bpref for the French collections. This shows that our proposal is better at selecting good and discriminant expansion terms.

Figure 5 shows a comparative analysis in terms of P@5, P@30, Rprec and GMAP for the four test collections. Notice that while P@K is defined as the proportion of relevant documents at rank $K$ , Rprec measures the precision over the top $R$ documents retrieved, where $R$ is the number of relevant documents in the entire collection. GMAP allows to assess performance against difficult queries. It is shown to be a stable metric to evaluate robustness [19] as it emphasises the poor performing topics. More detailed information about evaluation metrics in IR can be found in Manning et al. [23]. As we can see from Figure 5, the proposed QE method clearly outperforms the other methods. Based on GMAP results presented in Figure 5(d), we can have an insight into the robustness of our QE method.

For a more thorough evaluation of the robustness of QE methods, we report in Table 6 the RI, also called Reliability of Improvement [62]; for each method, RI is a simple measure, which provides a general indication of robustness. Given a set of queries $Q$ , RI is measured as follows [62,67]

RI (Q) = \frac{n_{+} - n_{-}}{| Q |} \in [- 1, + 1]

(10)

Table 6.

Comparison of robustness index (RI) with respect to the non-expanded baseline.

Method	Robust04		TREC2018		CLEF2000		CLEF2003
	n ₊	RI	n ₊	RI	n ₊	RI	n ₊	RI
Bo1	139	+0.12	31	+0.24	19	+0.18	24	+0.04
KLD	137	+0.10	33	+0.32	19	+0.18	24	+0.04
BM $25_{cog}$ QE (fixed weight)	153	+0.23	34	+0.36	24	+0.50	28	+0.23
BM $25_{cog}$ QE	156	+0.26	35	+0.40	26	+0.62	27	+0.15

KLD: Kullback–Leibler divergence.

$n_{+}$ = the actual number of improved queries by each method. The highest value in each column is marked in bold.

where $n_{+}$ is the number of improved queries, $n_{-}$ is the number of hurt queries and $| Q |$ is the total number of queries. Robust methods have a higher value of RI. A negative RI indicates that the number of hurt queries is higher than the number of improved queries compared with the non-expanded baseline. In other words, an RI value of −1.0 means that all queries were hurt by the QE method, while an RI value of +1.0 means that all queries were improved (the most robust results).

From Table 6, it can be observed that the RI values are always positive for all methods, which means that, on average, more queries were improved than degraded. According to the results, our QE method achieves the highest RI values compared with the baseline methods. We can see that our method obtains largely higher robustness scores across the four test collections. Considering the method, we propose to use two strategies: one with applying the reweighting step and the other without the reweighting step. We see that the former is better in all collections except CLEF2003, where we notice a slightly lower performance.

According to the results obtained so far in context of several standard evaluation metrics and across different TREC/CLEF datasets, we can claim that our proposal is shown to be both an effective and robust method for QE, which leads to improved IR results.

To further analyse the effectiveness of the new expanded queries, we plot in Figure 6 the Precision-Recall (P-R) curves in comparison to the baselines for different test collections. These graphs allow to evaluate ranked retrieval results by presenting a trade-off between precision and recall for different thresholds [23]. Traditionally, the interpolated precision is plotted at 11 recall points {0.0, 0.1, …, 1.0}. By examining the P-R curves in Figure 6, we can see that our method yields better results compared with the non-expanded baselines at different recall levels. For all test collections, the P-R curves with QE are better than the curves with the initial non-expanded queries in most cases. Besides, it can be seen that the proposed method outperforms the Bo1 and KLD baselines on three out of four collections, except for the Washington Post collection, where we notice a slightly lower performance in some recall points. This analysis demonstrates that our QE method generated good expansion terms, which had a positive impact and brought a significant gain in retrieval effectiveness of the baseline IR model across different test collections.

6.1. Effect of varying the number of expansion terms

After weighing and ranking of expansion features, the top terms are selected to form the new query. Typically, a large number of expansion terms are generated and only a limited number of these terms are added to the initial query. This is done to have a compromise between retrieval effectiveness and response time, and because adding many terms usually introduces noise in the new query, which may cause query drift [4]. Therefore, finding the optimal number of expansion terms has always been a challenge in many experimental studies. According to Carpineto and Romano [4], the best choice is to use 10–30 terms for QE.

In our experimental setup, we empirically set the number of expansion terms to 10 as suggested in previous experiments [4,38,68]. To investigate the impact of term selection on our proposed method, we varied the number of expansion terms in ${| Q |, 10, 20, 30, 40, 50, 60}$ , where $| Q |$ refers to the number of the original query terms (i.e. it uses a dynamic number of expansion terms and varies according to the length of each query). Table 7 displays retrieval performance in terms of MAP for each collection with different numbers of expansion terms.

Table 7.

Retrieval performance (MAP) of the proposed QE method for the four test collections with different numbers of expansion terms.

Collections	$\| Q \|$	10	20	30	40	50	60
Robust04	0.2498	0.2584	0.2573	0.2564	0.2564	0.2556	0.2550
TREC2018	0.2625	0.2653	0.2666	0.2687	0.2663	0.2635	0.2613
CLEF2000	0.3051	0.3266	0.3383	0.3408	0.3411	0.3441	0.3454
CLEF2003	0.4180	0.4228	0.4240	0.4141	0.4098	0.4075	0.4098

The highest value in each row is marked in bold.

When we compare the results of Table 7, we note that the maximum MAP values are reached for different choices of the number of expansion terms. According to Table 7, the optimal number of expansion terms among the values tested for each collection is as follows: 10 terms for the Robust04 collection, 30 terms for the TREC2018 collection, 60 terms for the CLEF2000 collection and 20 terms for the CLEF2003 collection. Nevertheless, we can observe that, overall, the variations in performance are negligible; the relative improvement between the lowest and highest MAP values does not exceed 4% for three out of four collections, except for the CLEF2000 collection, where we notice that the MAP value increases by increasing the number of expansion terms. Therefore, we can infer that retrieval effectiveness appears to be less susceptible to the number of expansion terms.

The obtained results corroborate previous experimental studies [2,27], stating that the choice of the number of expansion terms is of little relevance and has a minimal impact on retrieval effectiveness. However, emphasis should be placed on selection strategies to generate the most relevant expansion candidates [4].

In this set of experiments, we adjusted the free parameters of BM $25_{cog}$ to their optimal values to make a fair comparison while varying the number of expansion terms. Next, we study the sensitivity of the proposed method to these parameters.

6.2. Sensitivity analysis

The method we proposed introduces two free parameters, which can be adjusted to enhance results. To this end, we used five-fold cross-validation to tune the parameters $k_{1}$ and $b$ , where MAP served as the evaluation metric to be optimised. The optimal parameter settings of $k_{1}$ and $b$ on the four test collections are listed in Table 8. The constant $k_{1}$ determines how relevance changes when the number of co-occurrences increases. A large value of $k_{1}$ means that the score would increase nearly linearly with the co-occurrence value. A low value of this parameter means that after a certain number of co-occurrences, additional co-occurrences will have a little impact. The constant $b$ determines the scaling by the total number of co-occurrences of the target term (document length normalisation in query-document matching). A value of $b = 1.0$ means fully scaling, while $b = 0.0$ disables normalisation completely. According to Table 8, we observe that the optimal parameter settings vary from one collection to another and therefore are collection-dependent, which is consistent with the behaviour of the Okapi BM25 model [69].

Table 8.

Optimal parameter settings of $k_{1}$ and $b$ on the four test collections.

Parameter	Robust04	TREC2018	CLEF2000	CLEF2003
$k_{1}$	0.90	0.70	2.58	2.22
$b$	0.89	0.40	0.39	0.48

To further investigate the sensitivity of our proposed method to parameters $k_{1}$ and $b$ , we evaluated retrieval effectiveness in terms of MAP with varying parameters. We plot the sensitivity curves for each test collection against different values of $k_{1}$ and $b$ in Figures 7 and 8. We fixed the parameter $b$ at different thresholds {0.1, 0.3, 0.5, 0.7, 0.9} and varied the parameter $k_{1}$ in the interval [0.1, 3.0]. Similarly, we fixed the parameter $k_{1}$ at different thresholds {0.1, 0.6, 1.2, 1.8, 2.4, 3.0} and varied the parameter $b$ in the interval [0.1, 0.9].

Overall, we can observe that retrieval performance is sensitive to both $k_{1}$ and $b$ , that is, results vary depending on the setting of $k_{1}$ and $b$ . This means that better results could be achieved if both parameters are correctly adjusted. Figure 7 shows the sensitivity of MAP to the parameter $k_{1}$ for different thresholds of $b$ . For instance, we notice a relative MAP improvement ranging from 3.7% ( $b = 0.9$ ) to 5.5% ( $b = 0.1$ ) for the Robust04 collection by varying the parameter $k_{1}$ . Figure 8 also shows a similar behaviour by varying the parameter $b$ . Further experiments and analysis are needed to estimate and suggest optimal ranges for these two parameters, although a value of $b$ in a range of 0.4–0.9 seems to give best results. For the parameter $k_{1}$ , higher values (from 2.0 to 3.0) seem to give the best results for the French collections. For English collections, results seem to show the optimal $k_{1}$ to be in a range of 0.3–0.9.

7. Conclusion

In this article, we presented a new method for AQE based on global statistics of term co-occurrence. After performing different text pre-processing tasks, we built a term co-occurrence graph over the entire corpus using a context window approach, where nodes denote terms and edges represent co-occurrence relations between terms. We employed a semantic similarity measure inspired by the Okapi BM25 model, which leverages the performance of this robust model and proved to be able to capture the semantic relatedness between candidate expansion terms and the whole query. It also allows to evaluate the discriminative power of each query term to give higher importance to terms that will be more useful in identifying relevant expansion candidates. The same measure has also been used for reweighting the expansion terms according to their relevance to the query, so that the most relevant ones are assigned higher weights, yielding better results.

Experiments on four standard test collections of English (TREC Robust04 and TREC Washington Post) and French (CLEF2000 and CLEF2003) demonstrate the effectiveness and robustness of our proposed QE method compared with competitive state-of-the-art baselines in context of several standard evaluation metrics, leading to significantly improved results. We also evaluated the retrieval effectiveness of the proposed method with varying numbers of expansion terms. Further investigation into the free tuning parameters involved in our method shows that better results could be achieved if these parameters are correctly adjusted.

The proposed method considered only endogenous resources for expanding the queries. An interesting direction for future research is to investigate the use of exogenous resources, such as Wikipedia, for the selection of expansion terms. We believe that the results can be further improved, as similar studies [8,37] have shown significant results using external resources. Besides, the idea of taking advantage of the context provided by global analysis and the semantic richness provided by an ontologys [48,50] is another interesting direction for future research.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

ORCID iDs

Billel Aklouche

Ibrahim Bounhas

Notes

References

Jansen

Liu

Weaver

, et al. Real time search on the web: queries, topics, and economic value. Inform Process Manag 2011; 47(4): 491–506.

Azad

Deepak

Query expansion techniques for information retrieval: a survey. Inform Process Manag 2019; 56(5): 1698–1735.

Lau

Horvitz

. Patterns of search: analyzing and modeling web query refinement. In: Proceedings of the seventh international conference on user modeling, Banff, AB, Canada, 20–24 June 1999, pp. 119–128. New York: Springer.

Carpineto

Romano

A survey of automatic query expansion in information retrieval. ACM Comput Surv 2012; 44(1): 1–50.

Croft

WB.

Query expansion using local and global document analysis. In: Proceedings of the 19th annual international ACM SIGIR conference on research and development in information retrieval, Zurich, 18–22 August 1996, pp. 4–11. New York: ACM.

Fernández-Reyes

Valadez

Montes-y-Gómez

A prospect-guided global query expansion strategy using word embeddings. Inform Process Manag 2018; 54(1): 1–13.

Bai

Song

Bruza

, et al. Query expansion using term relationships in language models for information retrieval. In: Proceedings of the 14th ACM international conference on information and knowledge management, Bremen, 31 October–5 November 2005, pp. 688–695. New York: ACM.

Azad

Deepak

A new approach for query expansion using Wikipedia and Wordnet. Inform Sci 2019; 492: 147–163.

Croft

WB.

Improving the effectiveness of information retrieval with local context analysis. ACM Trans Inform Syst 2000; 18(1): 79–112.

10.

Van Rijsbergen

. A theoretical basis for the use of co-occurrence data in information retrieval. J Document 1977; 33(2): 106–119.

11.

Mitra

Singhal

Buckley

Improving automatic query expansion. In: Proceedings of the 21st annual international ACM SIGIR conference on research and development in information retrieval, Melbourne, VIC, Australia, 24–28 August 1998, pp. 206–214. New York: ACM.

12.

Collins-Thompson

Callan

Query expansion using random walk models. In: Proceedings of the 14th ACM international conference on information and knowledge management, Bremen, 31 October–5 November 2005, pp. 704–711. New York: ACM.

13.

Peat

Willett

The limitations of term co-occurrence data for query expansion in document retrieval systems. J Am Soc Inform Sci 1991; 42(5): 378–383.

14.

Blanco

Lioma

Graph-based term weighting for information retrieval. Inform Retrieval 2012; 15(1): 54–92.

15.

Mihalcea

Tarau

TextRank: bringing order into text. In: Proceedings of the 2004 conference on empirical methods in natural language processing, Barcelona, 25–26 July 2004, pp. 404–411. Stroudsburg, PA: ACL.

16.

Robertson

Walker

. Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval. In: Proceedings of the 17th annual international ACM SIGIR conference on research and development in information retrieval, Dublin, 3–6 July 1994, pp. 232–241. New York: ACM.

17.

Savoy

Cross-language information retrieval: experiments based on CLEF 2000 corpora. Inform Process Manag 2003; 39(1): 75–115.

18.

Braschler

Peters

Cross-language evaluation forum: objectives, results, achievements. Inform Retrieval 2004; 7(1–2): 7–31.

19.

Voorhees

EM.

Overview of the TREC 2004 robust retrieval track. In: Proceedings of the Thirteen Text REtrieval Conference (TREC 2004), Gaithersburg, MD, 14–19 November 2004, pp. 70–79. New York: ACM.

20.

Bhogal

MacFarlane

Smith

A review of ontology based query expansion. Inform Process Manag 2007; 43(4): 866–886.

21.

Rocchio

JJ.

Relevance feedback in information retrieval. In: Salton

(ed.) The SMART retrieval system: experiments in automatic document processing. Upper Saddle River, NJ: Prentice-Hall, 1971, pp. 313–323.

22.

Croft

Harper

DJ.

Using probabilistic models of document retrieval without relevance information. J Document 1979; 35(4): 285–295.

23.

Manning

Raghavan

Schütze

Introduction to information retrieval. Cambridge: Cambridge University Press, 2008.

24.

Fonseca

Golgher

Pôssas

, et al. Concept-based interactive query expansion. In: Proceedings of the 14th ACM international conference on information and knowledge management, Bremen, 31 October–5 November 2005, pp. 696–703. New York: ACM.

25.

Colace

Santo

Greco

, et al. Weighted word pairs for query expansion. Inform Process Manag 2015; 51(1): 179–193.

26.

Griffiths

Steyvers

Tenenbaum

JB.

Topics in semantic representation. Psychol Rev 2007; 114(2): 211–244.

27.

Carpineto

de Mori

Romano

, et al. An information-theoretic approach to automatic query expansion. ACM Trans Inform Syst 2001; 19(1): 1–27.

28.

Wang

Luo

, et al. An end-to-end pseudo relevance feedback framework for neural document retrieval. Inform Process Manag 2020; 57(2): 102182.

29.

Bhatnagar

Pareek

Improving pseudo relevance feedback based query expansion using genetic fuzzy approach and semantic similarity notion. J Inform Sci 2014; 40(4): 523–537.

30.

Wang

Pan

, et al. A pseudo-relevance feedback framework combining relevance matching and semantic matching for information retrieval. Inform Process Manag 2020; 57(6): 102342.

31.

Zamani

Dadashkarimi

Shakery

, et al. Pseudo-relevance feedback based on matrix factorization. In: Proceedings of the 25th ACM international on conference on information and knowledge management, Indianapolis, IN, 24–28 October 2016, pp. 1483–1492. New York: ACM.

32.

Singh

Sharan

A new fuzzy logic-based query expansion model for efficient information retrieval using relevance feedback approach. Neural Comput Appl 2017; 28(9): 2557–2580.

33.

Valcarce

Parapar

Barreiro

. Lime: linear methods for pseudo-relevance feedback. In: Proceedings of the 33rd annual ACM symposium on applied computing, Pau, 9–13 April 2018, pp. 678–687. New York: ACM.

34.

Diaz

Mitra

Craswell

Query expansion with locally-trained word embeddings. In: Proceedings of the 54th annual meeting of the association for computational linguistics, Berlin, 7–12 August 2016. pp. 367–377. Stroudsburg, PA: ACL.

35.

Zamani

Croft

WB.

Relevance-based word embedding. In: Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval, Tokyo, Japan, 7–11 August 2017, pp. 505–514. New York: ACM.

36.

Mahdaouy

Ouatik

SEA

Gaussier

É.

Word-embedding-based pseudo-relevance feedback for Arabic information retrieval. J Inform Sci 2019; 45(4): 429–442.

37.

Nasir

Varlamis

Ishfaq

A knowledge-based semantic framework for query expansion. Inform Process Manag 2019; 56(5): 1605–1617.

38.

Cao

Nie

Gao

, et al. Selecting good expansion terms for pseudo-relevance feedback. In: Proceedings of the 31st Annual International ACM SIGIR conference on research and development in information retrieval, Singapore, 20–24 July 2008, pp. 243–250. New York: ACM.

39.

ALMasri

Berrut

Chevallet

. A comparison of deep learning based query expansion with pseudo-relevance feedback and mutual information. In: 38th European conference on information retrieval, Padua, 20–23 March 2016, pp. 709–715. New York: Springer.

40.

Aklouche

Bounhas

Slimani

. Query expansion based on NLP and word embeddings. In: Proceedings of the Twenty-Seventh Text REtrieval conference (TREC 2018), Gaithersburg, MD, 14–16 November 2018.

41.

Esposito

Damiano

Minutolo

, et al. Hybrid query expansion using lexical resources and word embeddings for sentence retrieval in question answering. Inform Sci 2020; 514: 88–105.

42.

Mikolov

Sutskever

Chen

, et al. Distributed representations of words and phrases and their compositionality. In: Proceedings of the 26th international conference on neural information processing systems, Lake Tahoe, NV, 5–8 December 2013, pp. 3111–3119. New York: ACM.

43.

Miller

GA.

Wordnet: a lexical database for English. Commun ACM 1995; 38(11): 39–41.

44.

Bouziri

Latiri

Gaussier

LTR-expand: query expansion model based on learning to rank association rules. J Intel Inform Syst 2020; 55(2): 261–286.

45.

Padaki

Dai

Callan

. Rethinking query expansion for BERT reranking. In: 42nd European conference on information retrieval, Lisbon, 14–17 April 2020, pp. 297–304. New York: Springer.

46.

Zheng

Hui

, et al. BERT-QE: contextualized query expansion for document re-ranking. In: Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP): findings, online event, 16–20 November 2020, pp. 4718–4728. Stroudsburg, PA: ACL.

47.

Wongthongtham

Salih

BA.

Ontology-based approach for identifying the credibility domain in social big data. J Organiz Comput Electr Commerce 2018; 28(4): 354–377.

48.

Abu-Salih

Wongthongtham

Chan

, et al. CredSat: credibility ranking of users in big social data incorporating semantic analysis and temporal factor. J Inform Sci 2019; 45(2): 259–280.

49.

Abu-Salih

Bremie

Wongthongtham

, et al. Social credibility incorporating semantic analysis and machine learning: a survey of the state-of-the-art and future research directions. In: Workshops of the 33rd international conference on advanced information networking and applications, Matsue, Japan, 27–29 March 2019, pp. 887–896. New York: Springer.

50.

Abu-Salih

Chan

Al-Kadi

, et al. Time-aware domain-based social influence prediction. J Big Data 2020; 7(1): 10.

51.

Raza

Mokhtar

Ahmad

, et al. A taxonomy and survey of semantic approaches for query expansion. IEEE Access 2019; 7: 17823–17833.

52.

Robertson

Jones

KS.

Relevance weighting of search terms. J Am Soc Inform Sci 1976; 27(3): 129–146.

53.

Salton

Buckley

Term-weighting approaches in automatic text retrieval. Inform Process Manag 1988; 24(5): 513–523.

54.

Kim

Query term expansion and reweighting using term co-occurrence similarity and fuzzy inference. In: Proceedings Joint 9th IFSA world congress and 20th North American fuzzy information processing society (NAFIPS) international conference, Vancouver, BC, Canada, 25–28 July 2001, pp. 715–720. New York: IEEE.

55.

Johannesson

Modelling asymmetric similarity with prominence. Brit J Math Stat Psychol 2000; 53(1): 121–139.

56.

Gawron

. Improving sparse word similarity models with asymmetric measures. In: Proceedings of the 52nd annual meeting of the association for computational linguistics (ACL), Baltimore, MD, 22–27 June 2014, pp. 296–301. Stroudsburg, PA: ACL.

57.

Porter

MF.

An algorithm for suffix stripping. Program 1980; 14(3): 130–137.

58.

Singh

Gupta

A systematic review of text stemming techniques. Artif Intel Review 2017; 48(2): 157–217.

59.

Aklouche

Bounhas

Slimani

BM25 beyond query-document similarity. In: Proceedings of the 26th International symposium on string processing and information retrieval (SPIRE 2019), Segovia, 7–9 October 2019, pp. 65–79. New York: Springer.

60.

Shannon

CE.

A mathematical theory of communication. Bell System Technical Journal 1948; 27(3): 379–423.

61.

Amati

Probability models for information retrieval based on divergence from randomness, PhD thesis, Department of Computing Science, University of .Glasgow, Glasgow, 2003.

62.

Sakai

Manabe

Koyama

Flexible pseudo-relevance feedback via selective sampling. ACM Trans Asian Language Inform Proces 2005; 4(2): 111–135.

63.

Huston

Croft

. A comparison of retrieval models using term dependencies. In: Proceedings of the 23rd ACM international conference on information and knowledge management, Shanghai, China, 3–7 November 2014, p. 111–120. New York: ACM.

64.

Trotman

Puurula

Burgess

. Improvements to BM25 and language models examined. In: Proceedings of the 2014 Australasian document computing symposium, Melbourne, VIC, Australia, 27–28 November 2014, pp. 58–65. New York: ACM.

65.

Plachouras

Ounis

University of Glasgow at TREC 2004: experiments in web, robust and terabyte tracks with terrier. In: Proceedings of the Thirteenth Text REtrieval Conference (TREC 2004), Gaithersburg, MD, 16–19 November 2004.

66.

Järvelin

Kekäläinen

Cumulated gain-based evaluation of IR techniques. ACM Trans Inform Syst 2002; 20(4): 422–446.

67.

Collins-Thompson

. Reducing the risk of query expansion via robust constrained optimization. In: Proceedings of the 18th ACM conference on information and knowledge management, Hong Kong, China, 2–9 November 2009, pp. 837–846. New York: ACM.

68.

Chang

Ounis

Kim

Query reformulation using automatically generated query concepts from a document space. Inform Process Manag 2006; 42(2): 453–468.

69.

Zhai

Lower-bounding term frequency normalization. In: Proceedings of the 20th ACM international conference on information and knowledge management, Glasgow, 24–28 October 2011, pp. 7–16. New York: ACM.