In this paper, we evaluate query suggestion for Boolean queries in a news monitoring system. Users of this system receive news articles that match their running query on a daily basis. Because the news for a topic continuously changes, the queries need regular updating. We rst investigated the users' working process through interviews and then evaluated multiple query suggestion methods based on pseudo-relevance feedback. The best performing method generates at least one relevant term among 5 suggestions for 25% of the searches. We found that expert users of news retrieval software are critical in their selection of query terms. Nevertheless, they judged the demo application as clear and potentially useful in their work.
Diversity their work. An organization typically monitors multiple topics. For monitoring the news for a user-de ned topic, LexisNexis Publisher takes a Boolean query as input, together with a selection of news sources and a date range. Two example queries can be found in Table 1.
Interviews with users of LexisNexis Publisher indicate that noise in the set of retrieved documents is not very problematic because the user has the option to disregard irrelevant documents in the selection, thereby controlling precision. Recall is more di cult to control because the user does not know the documents that were not found. For the user, it is important that no relevant news stories are missed. Therefore, the query needs to be extended when there are changes to the topic. This can happen when new terminology becomes relevant for the topic (e.g. `wolf' for the topic `biodiversity'), when there is a new stakeholder (e.g. the name of the new minister of economic a airs for the topic `industry and ICT') or when new geographical names are relevant to the topic (e.g. `Lesbos' for the topic `refugees'). The goal of the current work is to support users of news monitoring applications by providing them with suggestions for new query terms in order to retrieve more relevant news articles.
Our intuition is that documents that are relevant but not retrieved for the current query have similarities with the documents that are retrieved for the current query. Therefore, our approach to query suggestion is to generate candidate query terms from the set of retrieved documents.
In this paper, we present the results of a user study in which we evaluate our methodology for query term suggestion with 9 expert users of LexisNexis Publisher. We rst conducted interviews with the users to collect their wishes and needs. Then we developed a demo application for news retrieval with query term suggestion functionality. We used this application to evaluate our approach and compare 12 di erent methods for query term suggestion. 2
The task of spotting novel terms in a news stream
is related to research on topic detection and tracking
(TDT) which has its roots in the 1990s [
Our approach to query suggestion { generating
candidate query terms from the set of retrieved
documents { is related to pseudo-relevance feedback [
There are two key di erences between pseudorelevance feedback and our approach: First, instead of adding terms blindly, we provide the user with suggestions for query adaptation. Second, we deal with Boolean queries, which implies that we do not have a relevance ranking of documents to extract terms from. This means that the premise of `pseudo-relevance' may be weak for the set of retrieved documents. 3
We conducted interviews with three experienced users of LexisNexis Publisher to get to know their way of working, their priorities and their wishes for query assistance. The following paragraphs summarize the insights obtained during these interviews.
Way of working. Queries are not changed frequently; most attention is paid to the initial query. Formulating this query takes several hours up to a whole day. Query constructions with Boolean operators are often re-used, for example to exclude speci c sources or newspaper sections. If a query gives too much noise, exclusions are added (using the `NOT' operator). If a query gives too few results, new terms are added (with the `OR' operator). Changes that are made a later stage are often changes in person and place names. Some customers have di culties formulating good Boolean queries. These customers make use of information specialist at LexisNexis to formulate their queries.
Priorities. The experts we interviewed use LexisNexis Publisher to create newsletters for their organization. Typically, they review all the retrieved articles before deciding which are included in the newsletter. This selection is based on redundancy and relevance; in case of overlapping news articles, the longest story from the most reliable source is selected. This is done manually, as it allows users to control the precision of the news articles included in the newsletter. The users indicate that for this reason, it is especially important that no relevant documents are missed by the search. Noise in the result set is not so much an issue; if half of the retrieved articles is relevant, the users are satis ed.
Wishes for query assistance. Users indicate that assistance in query formulation could be helpful, not only when adapting existing queries, but especially when formulating new queries. The users mention assistance in the form of: (a) suggestions of new query terms; (b) suggestions for deleting query terms that give too much noise; (c) suggestions for deleting query terms that give very few results. Of these three tasks, we concentrated on the rst: suggesting potential new query terms. One requirement posed by the users is that the user still has full control over the query. Terms should not be added blindly, but be presented as suggestions.
Our approach to query suggestion is to generate candidate query terms from the set of retrieved documents.2 The central methodology needed for generating terms from a document collection is term scoring; each candidate term from the document collection is assigned a score that allows for selecting the best { most descriptive { terms. The term scoring methods that we use are de ned below.
Problem de nition. We have a text collection D (the `foreground collection') consisting of one or more documents. Our goal is to generate a list of terms T with for each t 2 T a score that indicates how descriptive t is for D. Each t is a sequence of n non-stopwords; we use n = f1; 2; 3g in our experiments.
In most term scoring methods, descriptiveness is determined by comparing the relative frequency of t in the foreground collection D to the relative frequency of t in a background collection. For a given Boolean query, we retrieve the result set Rrecent, which is the set of articles published in the last 30 days, and the result set Rolder, which is the set of articles published 60 to 30 days ago.
We compare three methods for generating the most relevant query terms (see Figure 1 for a schematic overview): A. Return the top-k terms from T1, generated using Rrecent as the foreground collection and a generic news corpus as background collection;3 B. Return the top-k terms from T2, generated using Rrecent as foreground collection and Rolder as background collection; C. First generate T3, using Rolder as foreground collection and the generic news corpus as background collection. Then return the top-k terms from the set ft : t 2 T1 ^ t 2= T3g (all terms from T1 that are not in T3).
di erent term scoring algorithms from the literature
that we compare for the task of generating potential
query terms from the set of retrieved documents:
Parsimonious Language Models (PLM) [
3We used the newspaper section from the Dutch
SoNaRcorpus [
T1 News for topic of last 30 days
T2
T3 News for topic 30-60 days ago
determined by comparing the relative frequency
of t in D to the relative frequency of t in the
background collection. Phraseness is determined
by comparing the frequency of t as a whole to the
frequencies of the unigram that the n-gram t is
composed of; Informativeness of t and Phraseness
of t are summed to obtain a relevance score for t.
Frequency pro ling (FP) [
For one query and the corresponding retrieved documents, we generate twelve lists of potential query terms: three di erent approaches (A{C) with four term scoring algorithms. 5
We collected feedback from expert users of LexisNexis Publisher to determine the best method for generating term suggestions. For this purpose, we developed an external demo application for news retrieval from the LexisNexis collection that includes query term suggestion functionality. Note that the query term suggestion functionality was not integrated in the existing LexisNexis search interface, but implemented as a standalone web application. Figure 5 shows a screenshot of the demo application.4 The user interface is in Dutch. In the top part of the screen (`Zoekopdracht bewerken' { `Edit search'), the user sees the current query and the results (`Resultaten') retrieved for that query. In total, 1110 results were retrieved for this query. In the bottom part of the screen (`Query aanpassen' { `Adapt query'), the user sees a list of term suggestions. This example illustrates the nal functionality, in which only the 5 suggestions by the best performing method are shown. In the experimental setting, the user saw a pool of 10{25 terms from different methods. 5.1
The query suggestion software was evaluated by 9 individual users of LexisNexis Publisher. A 2-hour eval4A video demonstrating the demo application can be viewed here: https://youtu.be/4yIYpvHVugQ uation session was organized for each participant. The interviews described in Section 3 revealed that queries change more frequently when they are novel. Therefore, each participant was asked to perform two di erent tasks with the assistance of our demo application during the evaluation session. In the rst task, the participant is asked to update a query that is already being used by his company. In the second task, the participant designs a new query for a topic of which they received a short topic description.
The initial (existing or new) Boolean query is issued in LexisNexis Publisher through its API, searching in Dutch newspapers of the last 60 days (the maximum posed by the API). The titles and abstracts of the matching news articles are shown in a result list (in chronological order) and a list of query term suggestions is presented. The participant reviews the set of retrieved documents and improves the query by adding and/or removing terms, optionally using a term from the suggestions. Subsequently, the updated query is issued and the query can be improved again. In both tasks, the participant was asked to review and update the query up to a maximum of ve iterations. After the complete evaluation session, the participants lled in a post-experiment questionnaire, in which they could provide additional comments. 5.2
The participants issued 83 searches in total. The Boolean queries are long: 45 terms on average. Terms can be single words or phrases (multi-word terms), and they are combined with Boolean operators. We used the LexisNexis Publisher API to retrieve documents (news articles) published in the last 60 days. On average, 1; 031 documents were retrieved per query (ranked by date), with an average length of 63 words. The short document length is caused by the API allowing us to extract only the summary of the news article, not the full text. This means that the size of the subcollection from which potential new query terms are extracted for a query is on average 1; 031 63 = 64; 953 words.
We created a pool of terms from the 12 (3 approaches * 4 term scoring algorithms) term lists per topic. We assume that in a real application, the query suggestion software would show ve candidate terms to the user, and we want to be able to evaluate these 5 suggestions for each method. Therefore, the top 5 terms from each term list were added to the pool. The maximum number of terms in a pool is 60 (12*5) but in reality there is quite some overlap: the number of terms per pool is between 10 and 25. For each query, the participants were presented with this pool of 10{25 terms. The terms were ranked by the number of top-5 lists they appear in: the terms that were extracted by most methods were ranked on top of the pool. 5.3
The selection of query terms and the relevance judgments for the suggested terms in the pool allow us to evaluate and compare the methods. For each method, we have judgments for the 5 highest scoring terms. We count how often one of these terms was selected by a participant, and how often at least one of these terms received a relevance rating of at least 4. The results are in Table 2 and Table 3. The results for the best performing methods (method A with either FP or KLIP as term scoring algorithm, or method C with KLIP) are marked with boldface in the tables. With these methods, participants selected a term from the top-5 suggestions for 13% of the searches, and judged at least one term from the top-5 suggestions as relevant (relevance score >= 4) for 25% of the searches. The average rating given to the terms in the pool was low: 1.36 on a 5-point scale.
Further analysis of the results showed that the term suggestions were noisy because the sets of retrieved documents are noisy. The Boolean queries return a large set of documents (more than a thousand on average for the last 60 days), without any relevance ranking. The interviews with the users indicated that this is not a problem for the users (because they lter the news items for the newsletter), but it turns out to be a problem for the extraction of relevant terms. In other words, the premise of `pseudo-relevance' does not hold for Boolean retrieval, and this hurts the quality of query term suggestion based on retrieved documents. 5.4
In the post-experiment questionnaire, participants indicated that the demo application was clear and intuitive (median score of 4 on a 5-point scale for the statement `the web application is clear'). Half of the participants would be interested in using the tool. However, they felt that the quality of the terms should be improved for the application to be really useful. Suggestions that were provided by the users included: Do not to suggest terms that are already covered by wildcards in the query. We improved this in the nal version of the demo application.
Terms that occur in important parts of the text should be more relevant. In fact, this was already taken into account because the API only allowed us to access the abstracts of the documents. Multi-word terms should not be suggested. This comment appeared to be in contrast with the users' term selections: of the selected terms by the users (15), the majority (12) are multi-words. Add suggestions for the use of Boolean operators. This was beyond the scope of the current project, which focused on term suggestion. 6
The results of our user experiment show that with the best performing method, participants selected a term from the top-5 suggestion list for 13% of the topics, and judged at least one term as relevant for 25% of the topics. Inspection of the results and the post-task questionnaire revealed that the term suggestions are noisy, mainly because the set of retrieved documents for the Boolean query is noisy. We expect that the use of relevance ranking instead of Boolean retrieval, and a post- ltering for noisy terms, will give better user satisfaction.
The relevance judgments for the suggested terms
are low compared to another application area for term
extraction that we addressed in previous work with
the same methodology, namely author pro ling [