Leveraging semantic resources in diversified query expansion

Search Result Diversification is the task of producing a ranked result set of documents in a retrieval task such that most aspects of the query are covered. The pioneering SRD work [5] proposed the usage of the MMR principle in a technique that targets to reduce the redundancy among the top-results as a method to implicitly improve aspect representation:

In MMR, the next document d to be added to the result set (S), is determined as that maximizing a score modeled as the relevance to the query (S ₁) penalized by the similarity (S ₂) to already chosen results in S. A more recent SRD method uses Markov Chains to reduce redundancy [37]. Since then, there have been methods to explicitly model query aspects and diversify search results using query reformulations [26], query logs [12] and click logs [16], many of which use MMR-style diversification.

Diversified Query Expansion, a more recent task as well as the problem addressed in this paper, starts from a query and identifies a set of terms that could be used to extend the query that would then yield a more aspect-diverse result set; thus, DQE is the diversity-conscious variant of the well-studied Query Expansion problem [8]. In a way, DQE differs from SRD in being an active (or user-reliant) aspect diversification task targeted at providing some suggestions to the user so she can explicitly reformulate the query as needed; thus, this relaxes the SRD expectation that the system is capable of doing the diversification itself using just the initial query. Table 1 summarizes the various DQE methods in literature. Drawing inspiration from recent interest in linking text with knowledge-base entities (notably, since explicit semantic analysis [14]), BHN [2] proposes to choose expansion terms from the names of entities in the ConceptNet ontology, thus generating expansion terms that are focused on entities. BLN [3] extends BHN to use Wikipedia and query logs in addition to ConceptNet; the Wikipedia part relies on being able to associate the query with one or more Wikipedia pages, and uses entity names and representative terms as candidate expansion terms from Wikipedia. While such choices of expansion terms make BHN and BLN methods suitable for entity recommendations (i.e., DER), the limited vocabulary of expansion terms makes it a rather weak query expansion method. For example, though courses might be a reasonable expansion term for python under the computing aspect, BHN/BLN will be unable to choose such words since python courses is not an encyclopaedic concept to be an entity in the ConceptNet or Wikipedia. The authors in [3] note that the BLN-Wiki is competitive with BHN in cases where the query corresponds to a known Wikipedia concept, and that BHN performs better in general cases. We will use BHN as an entity ranking (DER) baseline in our experiments.

LBSN [21] gets candidate expansion terms from query logs. Such direct reuse of search history is not feasible in cold start scenarios and cases where the search engine is specialized enough to not have a large enough user base (e.g., single-user desktop search) to accumulate enough redundancy in query logs; our framework targets more general scenarios where query logs may not be available. t s _{x Q u A D} [34], another DQE method, is designed to use terms from corpus documents to expand the query, making it immune to the small vocabulary problem and useful in a wide range of scenarios, much like the focus of SLR. However, t s _{x Q u A D} works only for queries where the set of relevant documents are available at the aspect level. Given that, if each result document retrieved for the initial query may be deemed relevant to at least one aspect, a topic learner such as LDA [1] may be used to partition the results into topical groups by assigning each document to the topic with which it has the highest affinity. Since such topical groups are likely to be aspect-pure, such result partitions can be fed to t s _{x Q u A D} to generate expansion terms without usage of relevance judgments. We will use the LDA-based t s _{x Q u A D} as the baseline DQE technique for our experiments. Another related work is that of enhancing queries using entity features and links to entities [9], which may then be processed using search engines that have capabilities to leverage such information; we, however, target the DQE/DER problem where the result is a simple ordered list of expansion terms or entities.

We now consider research on using external semantic resources for query expansion. Due to the usage of Wikipedia and word embeddings in our method, we give a short summary of such resources and work on using such resources for query expansion.

The suggested uptake model for DQE as used in most methods (e.g., [2]) is that the original search query (e.g., python) be appended with all the (optionally weighted) terms in the result (e.g., language, monty) to form a single large query that is expected to produce a result set encompassing multiple aspects. While this is likely be a good model for search engines that work on a small corpus and other specialized scenarios, we observe that such extended queries are not likely to be of high utility for large-scale search engines. This is so since there is a likelihood of a very rare aspect in the intersection of multiple terms in the extended query that would most likely end up being the focus of the search since search engines do not consider terms as being independent. Figure 1 illustrates a couple of such examples, where very rare and non-noteworthy aspects form part of the top results. Thus, we focus on the model where terms in the DQE result set be separately appended to the initial query to create multiple aspect-pure queries. Thus, in our example, we expect that ‘python language’ or ‘python monty’ be candidates for the user to choose from, in order to expand and re-formulate the initial query, i.e., python.

Given a document corpus \(\mathbb {D}\) and a query phrase \(\mathcal {Q}\), the diversified query expansion (DQE) problem requires that we generate an ordered (i.e., ranked) list of expansion terms \(\mathbb {E}\). Each of the terms in \(\mathbb {E}\) may be appended to \(\mathcal {Q}\) to create an extended query phrase that could be processed by a search engine operating over \(\mathbb {D}\) using a relevance function such as BM25 [35] or PageRank [23]. The relevance function itself is external to the DQE task. The ideal \(\mathbb {E}\) is that ordering of terms such that the separate extended queries formed using the top few terms in \(\mathbb {E}\) are capable of eliciting documents relevant to most aspects of \(\mathcal {Q}\) from the search engine. Typically, users are interested in perusing only a few expansion possibilities, with research indicating that as many as 91% of users are unlikely to go beyond the first page of search results in Web search engines [33]; thus, a quality measure for DQE is the aspect coverage achieved over the top-k terms for an appropriate value of k such as 5. Diversified entity recommendation (DER) is the analogous problem of generating an ordered list of entities, \(\mathcal {E}\), from an ontology (Wikipedia, ConceptNet etc.) such that most diverse aspects of the query are covered among the top few entities. It may be noted that we do not presume availability of usage data (e.g., query logs) or supervision (e.g., documents labelled with aspect relevance information) in addressing the DQE/DER tasks.

We now outline our three-phase skeletal framework for diversified query expansion that we base our methods on. The three phases are as follows:

As outlined earlier, we develop two methods based on this framework, SLR and SER, targeted at using Wikipedia and pre-learned word embeddings respectively. Both the methods are identical in the selection phase, but differ in the subsequent phases. We describe each method in separate sections.

We first start by retrieving the top-K relevant documents to the initial query \(\mathcal {Q}\), denoted by \(Res_{K}(Q,\mathbb {D})\) from a search engine operating on \(\mathbb {D}\). From those documents, we then choose T terms whose distribution among the top-K documents contrasts well from their distribution across documents in the corpus. This divergence is estimated using the Bo1 model [15], a popular informativeness measure that uses Bose-Einstein statistics to quantify divergence from randomness as below: where f(a, B) denotes the frequency of the term a in the document collection represented by B. Thus, \(f(t,\mathbb {D})/|\mathbb {D}|\) denotes the normalized frequency of t in \(\mathbb {D}\). It is notable that Bo1 scoring does not involve any parameter that requires tuning. To ensure all aspects of \(\mathcal {Q}\) have a representation in \(Res_{K}(Q,\mathbb {D})\), K needs to be set to a large value; we set both K and T to 1000 in our method. The selected candidate terms are denoted as \(Cand(Q,\mathbb {D})\). The top Bo1 words for our example query jaguar included words such as panthera (relating to animal), cars, racing, atari (video game) and jacksonville (American football).

In this phase, we use the terms in \(Cand(Q,\mathbb {D})\) to link to Wikipedia entities leading up to the creation of an entity graph with nodes weighted as a function of their relatedness to the terms. We now outline the steps leading to the creation of the graph in three subsections herein.

This phase uses the graph \(G(\mathcal {Q})\) and associated node-importance weights to arrive at a the final DQE result set, i.e., an ordered list of terms, \(\mathbb {E}\). We model this phase as two sub-phases, the first that scores entities in \(G(\mathcal {Q})\) in diversity-conscious fashion and the second that translates such scoring to the space of terms.

We briefly analyze the computational efficiency of SLR, in the interest of understanding its scalability.

The various steps in SLR and their sequence of operation are outlined in the pseudocode in Algorithm 2. Since the separate phases have been covered in detail in the previous section, we do not explain them further. It may be noted that we do not make use of wikipedia disambiguation pages in SLR. While wikipedia disambiguation pages are useful, they are generally available only for topics of broad-based interest, and a technique relying on them would not be applicable for queries focused on niche entities. Further, this ensures fairness in comparison with the baselines that do not use curated disambiguations.

The select phase in SER is identical to the select phase in SLR as outlined in Section 4.1. It involves selecting the top-T terms from across the top-K documents retrieved in response to the search query, Q. The Bo1 measure is used to score terms, resulting in a candidate set \(Cand(Q,\mathbb {D})\). Due to the usage of the initial result set from a relevance-only search, SER is also amenable to be used within an IR re-ranking framework.

The embed phase brings in word embeddings into the picture. SER was designed in order to be able to leverage pre-learned word embeddings such as the Google News word2vec¹² or the Wikipedia/Twitter/Gigaword GloVe vectors¹³ in diversified query expansion. While we will consistently make use of such pre-trained vectors in our empirical evaluation, the framework itself only expects to be able to map each term from \(Cand(Q,\mathbb {D})\) to a vector; thus, for very specialized-domain search systems, it would be appropriate to use word vectors learnt from the corpus \(\mathbb {D}\) itself. This phase involves the construction of an initial term graph using word embedding similarities, followed by refining it by heuristically filtering out edges and vertices.

This phase, much like the analogous phase in SLR, employs a VRRW to score terms in the graph in a diversity-conscious fashion. Unlike the SLR version, we do not use node importance weights in the SER graph, and thus, the transition probability is uniform across all the edges. An important distinction between SLR and SER being that the former employs VRRW on the entity graph whereas we use VRRW on the term graph directly. Once the VRRW stabilizes, we are left with a score for each term in the term graph, which we denote as S(t). The DQE output, \(\mathbb {E}\) is then the set of terms in \(V(\mathcal {Q})\) ordered in the decreasing (or non-increasing, to be precise) order of the scores according to S(.).

Due to the non-usage of an entity knowledge base such as Wikipedia or ConceptNet within the SER pipeline, the DQE output \(\mathbb {E}\) needs to be adapted in conjunction with an entity knowledge base to form a diversified entity ranking output, \(\mathcal {E}\), for usage as a DER method. We accomplish this using a suitable entity linking method, such as those was discussed in Section 4.2.1. Specifically, for each term in the \(\mathbb {E}\) output, we append the query with that term forming a text segment, which would then be used in an entity linking system to choose the most related entity as the following: where t.E is the set of entities linked to the text segment formed by collating the query with the term t and r(t, e) is a relationship strength output by the linking method (all notations same as in Section 4.2.1).

Similar to Section 4.4, we analyse the computational costs of the various phases in SER.

In summary, SER is seen to be quadratic in the Rank phase. However, since the Rank phase graph has fewer nodes than the initial Embed phase graph, the Embed phase could be prioritized for optimization by way of usage of a pre-computed similarity index over the distributional word embeddings.

Algorithm 2 illustrates the various steps in the SER method in a pseudocode. As indicated in previous sections, the major difference between the SLR and SER is in the Correlation phase in the three-phase framework (Section 3.2), where different strategies are adopted to make use of respective semantic resources, motivated by the nature of their different characteristics.

We use the ClueWeb09 [7] Category B dataset comprising 50 million Web pages in our experiments. In SLR and SER, we use the publicly accessible Indri interactive search interface for procuring initial results. This was followed by usage of a simple custom entity linker based on Apache Lucene [17]; specifically, all entities were indexed using their article body text, and the top-result entities in response to each term were used as linked entities along with their corresponding relevance scores. We now detail the default parameter settings for our methods. For the Select phase parameters, we set K = K ^′ = 1000 across both the methods. The SLR link phase parameter α is set to 0.65 and we set λ = 0.2. Meanwhile, the SER embed phase parameters are set as τ = 0.4, μ = 4 and ρ = 5. The VRRW restart probability in the Rank phase of both the methods was set to 0.25. We consistently use a query set of 15 queries gathered across motivating examples in papers on SRD and DQE.

We compare our DQE results against LDA-based t s _{x Q u A D} [34] where we set the #topics to 5. SLR’s DER results are compared against that of BHN [2]. For both t s _{x Q u A D} and BHN, all parameters are set to values recommended in the respective papers.

We use both user studies and automatic evaluations in order to assess the empirical performance of our methods, SLR and SER. With the limited amount of resources available for the user study, we choose to do two sets of user evaluations; (i) benchmarking SLR on both DQE and DER against respective baselines, and (ii) evaluating SER against SLR on the DQE task. The user study was rolled out to an audience of up to 100 technical people (grad students and researchers) of whom around 50% responded. The users were free to choose one or more of the four surveys to respond to, thus leading to different numbers of votes for each of the four surveys. All questions were optional; thus, some users only entered responses to a few of the queries even within a survey. Since the user study was intended to collect responses at the result-set level to reduce the number of entries in the feedback form, we are unable to use evaluation measures such as α-NDCG that require relevance judgements at the level of each result-aspect combination. Apart from the user study, we also perform an automated diversity evaluation focused on the DQE task.

For each user study, two methods are pitched against each other. For each of the 15 queries in our query set, we generate the top-5 results (terms for the DQE task and entities for the DER task) by both the methods and request users to choose the better result set. The survey itself was randomized; thus, for one query, results from the first method could appear on the left, while it might be on the right for another query.

We further evaluate the performance of our methods with respect to the diversity of the aspects represented by the expansion terms and their relevance. Since all previous efforts on DQE use evaluation measures that are based on expensive human-inputs in the form of releveance judgements (e.g., [4, 27]), we now devise an intuitive and automated metric to evaluate the diversity of DQE results by mapping them to the entity space where external entity relatedness measures can be exploited. In other words, this evaluation measure quantifies the diversity of the entities that the DQE output maps to. This allows us to compare all our three methods, SLR, SER-Wiki and SER-News against the baseline methods t s _{x Q u A D} , RM-CombSum-Wiki and RM-CombSum-News. The last two methods are the MMR-based extensions of the method from citekuzi over the Wiki and Google News word embeddings respectively. Consider the top-k query expansions as \(\mathbb {E}\); we start by finding the set of entity nodes associated with those expansions, \(\mathbb {N}\). We then define an entity-node relevance score \(r_{\mathbb {E}}(n)\) as the sum of its relevance scores across its associated expansion terms; i.e., \(r_{\mathbb {E}}(n) = {\sum }_{t \in \mathbb {E}} r(t,n)\). Let S(n _i ,n _j ) denote an entity-pair semantic relatedness estimate from an external oracle; our quality measure is: where e x p(−S(n _i ,n _j )), as the formula suggests, is a positive value inversely related to similarity between the corresponding entities. Intuitively, it is good to have highly relevant entities to be less related to ensure that entity-nodes in \(\mathbb {N}\) are diverse. Thus, higher values of the Q(.,.) metric are desirable. We use two versions of Q by separately plugging in two different estimates of semantic similarity to stand for the oracle: where n.n e i g h b o r s indicate the neighbors of the node n according to the Wikipedia graph, and D e x t e r(.,.) denotes the semantic similarity from Dexter [6].

Figures 5 and 6 show the expansion qualities based on Jaccard and Dexter respectively for the SLR, SER-Wiki, SER-News, t s _{x Q u A D} , RM-CombSum-Wiki and RM-CombSum-News methods. It may be noted that the values are plotted in log-scale to allow for better visualization since the techniques vary much in terms of the evaluation measure; the quality measure being in [0,1], the log-scale yields all negative values with all the bars in the figure seen to be ’hanging’ from the x-axis rather than being held upright. Since higher values (i.e., smaller negative values) are desirable, shorter (hanging) bars correspond to better performance. On an average, across all queries, SLR was seen to outperform all the other methods on both the evaluation measures. SER-Wiki comes next convincingly beating the other methods. Though SER-News was seen to be slightly better than t s _{x Q u A D} and RM-CombSUM-News, the difference in the quality measure was less than an order of magnitude on an average; note that, due to the log-scale plot, each unit of ”length” corresponds to significant deterioration in the quality metric. The main high-level observation from the automated diversity evaluation is that our methods SLR and SER-Wiki significantly outperform the baseline methods. It is also interesting to note that SER-News despite using word embeddings from a specialized domain (i.e., Google News) is still able to outperform t s _{x Q u A D} , albeit not by much.

We now analyze the amount of fluctuation in the results of the DQE methods when the parameter settings are varied. It is of interest to see some stability in the results when parameters are varied slightly; this would indicate that the method would be robust to changes in the character of the dataset or the external knowledge base employed. We now outline our stability analysis blueprint. First, we fetch the top-10 results of DQE from each method (SLR and SER) with the parameters set to values outlined in Section 6.1, and get their associated entities. Second, we change a particular parameter and get the entity results of the same method, and measure the overlap between the top-entities retrieved from the changed parameter settings and those from the initial parameter settings; we call this overlap as the stability factor. This is repeated for each parameter, to measure the stability of the method across each parameter in round-robin fashion. It may be noted that the measure of overlap should not be interpreted as an accuracy measure; it simply indicates the amount of deviation. In particular, a parameter variation that brings in a correct entity that was not covered by the initial parameter setting would be penalized due to divergence from the latter, thus indicating that this quality measure is not directly to accuracy measured against labelled data. We define the stability factor for a range of parameter values as the minimum among the stability values across values in the range. Table 5 lists the stability factors measured over different ranges of parameter values. As may be seen, SLR is seen to be much more stable than SER-Wiki, with the latter replacing upto two-fifths of the results with variations along τ. Overall, our methods are seen to be fairly stable against small variations in parameters.

Our user study as well as the two automated evaluations indicate that SLR outperforms the SER variants and the baselines, with the SER variants emerging as the best alternative to SLR when a well-curated knowledge-base such as Wikipedia is not available for usage. These results indicate that our skeletal three-phase framework is effective in developing practical DQE methods. Our empirical evaluation further establishes two key properties of the proposed techniques. First, external semantic resources such as Wikipedia and word embeddings provide useful information for DQE. Second, VRRW is effective in mining accurate representatives of the various aspects related to the query. Overall, the empirical analysis establishes that our methods are effective in providing good term-level abstractions of diverse user intents.