Users often issue web queries related to current news events. For such queries, it is useful to predict the news intent automatically and highlight the news documents on the search result page. An example query would be \election results" issued during the time of elections. These highlighted displays are called news verticals. Prior work has proposed several features for predicting whether a query has news intent. However, most approaches treat each query individually. So on a given day, very similar queries can be assigned opposite predictions. In our work, we explore how a system can utilize query similarity information to improve the quality of news verticals along two dimensions|prediction and presentation. We show via a study of actual search tra c that the accuracy of predicting queries into newsworthy and not newsworthy categories can be improved using query similarity. Further, we present a method to identify a canonical variant for a newsworthy query such that using the canonical query would retrieve better results from the news backend to show in the display. Use of the canonical query also has the advantage of creating a consistent presentation of results for query variants related to the same news event.
Consider the query \Michelle Obama visits Spain" issued to web search engines during the time of the First Lady's visit to Spain. If this query is issued on a news website, the results would contain all news articles about the event. On the other hand, a user may also issue such a query to a generic web search engine. If the search engine can predict the query as related to currently newsworthy events, latest news can be retrieved for the query and explicitly
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. This article was presented at the workshop Very Large Data Search (VLDS) 2011.
Copyright 2011.
highlighted on the result page. Such news displays, also
called news verticals now appear on the result pages of
major search engines such as Google, Yahoo! and Bing. An
example news vertical on the search result page of a generic
search engine is shown in Figure 1. Prior work has
introduced several features for news intent prediction. These
features characterize the bursty nature of a query during a
particular time period [
We consider two properties related to news displays which can further bene t from information about similar queries.
Triggering accuracy: When two queries q and q0 are related to the same news event, they would have the same news intent. For example, the queries \Michelle Obama Spain visit" and \Spain vacation Michelle Obama" refer to the same event and both are newsworthy during that time. If a system can identify q and q0 as similar, it can make more accurate predictions. Besides accuracy, it is desirable that a consistent system would trigger a news display for both queries regardless of the actual lexical realization.
Retrieval of results for the display: Another use of query similarity is in the case when q and q0 are predicted to be newsworthy. The lexical form of q could retrieve very relevant content from the news backend while q0 might be a speci c query with few matches. Knowledge that they are similar can help us choose from q, q0 and other similar queries, a variant which would retrieve the most relevant results for the event that they represent. This setup could also lead to uniformity in the results shown for di erent variants belonging to the same event. So query similarity can help in presentation quality and consistency.
The work on news intent prediction that is closest to ours
is by Diaz and Arguello [
In this paper we augment a news intent predictor with query similarity information. (a) We show that a simple lexical match method to get similar queries is highly accurate and useful for improving news intent predictions. We show that the improvement is pronounced even in a model which uses a rich set of features for the baseline predictions. (b) We validate through a user study on actual search trafc, that the predictions get improved when we add query similarity information. (c) We propose a method to identify a canonical variant for similar queries. We show that we can outperform the baseline approaches signi cantly for this task and achieve a better display of news results for di erent query variants.
Our study is insightful for both the quality of news
display and the search user experience. Inconsistent triggering
lowers accuracy. Recent work [
Prior work on news intent prediction have introduced a
number of features [
In most prior approaches, the vector of features for a query
is not dependent on other queries issued the same day. Even
when two queries are closely related, they could have
varying frequencies in query logs and news documents. So their
predictions could be quite di erent. We want to
incorporate query similarity to create more accurate predictions.
In Diaz and Arguello's work, they share user feedback from
one query to those which are similar, so that similar queries
can also take advantage of the feedback information. In this
work, we seek to produce more accurate baseline predictions
using query similarity. Our approach to do similarity-aware
predictions is similar to techniques introduced to handle tail
queries for advertisement display [
Our approach to canonical query selection is reminscent of
query modi cation methods to obtain better matches with
documents or advertisements. Here, when queries do not
match the bid phrases or documents, some substitution [
We consider a simple news predictor and then show how we add query similarity information to it. We predict newsworthy queries in an o ine process. To identify newsworthy queries for day d, we use the query logs from day d 1. The queries from immediately previous day are likely to be issued again. (In fact, one-third are repeated on average.) Each query from day d 1 is associated with a binary prediction (newsworthy or not) and the newsworthy queries are are entered into a whitelist. On day d, if a query issued is in the whitelist, we trigger a news display. The list is refreshed daily. So the goal of the predictor is to identify queries that will continue to have news intent on the next day.
This situation is obviously incapable of handling new queries that were not seen the previous day. However, for our goal of evaluating the use of query similarity, this setup is simple and appropriate, also enabling us to deploy it for a user study. Although the system is simple, this o ine setup enables us to use a rich set of features which would be prohibitively costly to compute at query issue time. So we are evaluating the power of query similarity over an already strong feature set. So we focus on this baseline model for our experiments, further approaches such as adding user feedback and handling new queries will improve the capabilities of the model we use. 3.1
The gold standard news intent judgements for a query was obtained empirically as was done in prior work. We logged query statistics in early 2008 from a commerical web search engine. A small portion of search users were shown news displays for every query they issued provided there was any matching content in the news backend. On average, 800,000 2008 long beach grand prix long beach grand prix (0.57), f1 grand prix (0.03), long beach (0.02) 2008 n draft order 2008 n draft (0.30), 2008 draft (0.19), n draft (0.12), n draft 2008 (0.06) bad beef recall beef recall (0.15), recalled beef (0.02), massive beef recall (0.01), california beef recall (0.01) carly smithson controversy carly smithson (0.10), carly smithson american idol (0.01), carly hennessy smithson (0.01) unique queries were issued per day by these users and 30,000 of them had matches in the news index. For these 30,000 queries, displays were shown without any attempt to verify their news intent. The display consisted of the titles of the three most relevant news documents. The click through rate (CTR) on the display for each query was logged and we consider these values as gold standard. A click on any of the three titles within the display is considered as a click on the display. The 30,000 queries per day collected for a two week period form our data set. We train a model to predict the CTR of a query and then apply a threshold to obtain a binary (newsworthy or not) prediction. 3.2
As already outlined, our method predicts newsworthy queries for day d from the query tra c logged for day d 1. So the target for training is the next day CTR of a query. Only those queries observed on two consecutive days can be used for training. We divide the data described above into training (around 100,000 unique queries) and test (60,000) sets.
Overall, we use around 70 features in our model. Most
of them are inspired by prior work by Konig et al. [
A Gradient Boosted Decision Trees (GBDT) [
Next we explain how we add query similarity information to the predictions.
We use a simple metric that measures the match between
bigrams in the two queries. Such a lexical measure is
inadequate when we consider query variants such as
\Jennifer Lopez babies" and \Marc Antony twins". So we also
tried other methods which o er more exibility for
matching queries. These methods included the similarity in the
URLs, titles and abstracts of the top results [
The words in the query are stemmed and each bigram of stems is a feature. We also include skip bigrams with gap 1, i.e. we form bigrams by ignoring atmost one intervening word. The feature value is the frequency of the bigram in the query multiplied by the inverse-document frequency (idf) computed on all the queries seen that day (recall that our processing is o ine and all queries on day d 1 are available). The vectors from two queries are compared using cosine similarity. A cuto is applied on the similarity value and we consider those query pairs above the threshold as similar. A threshold value of 0.01 was picked by manually examining the query pairs from di erent threshold ranges. We also limit the number of similar queries to atmost 10. Some example matches are shown in Table 1. 5.
Now, we add query similarity to the news intent predictions using a post-processing approach. 5.1
Let us call the predicted CTR for a query q as score(q). Next, we gather the most similar queries to q, kNN(q), using lexical similarity and applying the threshold we described earlier. Now, we want to modify score(q) such that if the majority of neighbours in kNN(q) are newsworthy, it is likely that q is also such or vice versa.
Some ways to modify score(q) are: assign the weighted average of score for queries in kN N (q), or assign the score of the most similar query from kNN(q), etc. During development testing, we found that the predicted scores from the baseline model were more accurate for high frequency queries. So setting score(q) to be the same as that of its variant in kNN(q) with maximum frequency (was issued most times) provided the best CTR adjustments which moved queries reliably across the boundary for newsworthy/ not newsworthy decision. (We evaluate this aspect using the true category of queries where the system proposed to make a change in category.) We also found that the queries predicted with high con dence in the newsworthy category were quite accurate and demoting scores led to a number of false negatives. So we only focus on adding queries to the whitelist.
Our rescoring method can be summarized as follows. Let T be the threshold on score(q) to mark newsworthy queries. modScore(q) = score(q), if jkNN(q)j = 0 or score(q) > T = score( arg max frequency(q0)), otherwise
q02kNN(q) 5.2
We employed both human judgements and system deployment for evaluating our approach. The human evaluation was done on a sample of our data. The deployment was done for a fraction of users of a commerical search engine and serves as a large scale study in the target setting. Both cases con rm the usefulness of our approach. 5.2.1
We ran our rescoring method on one day of full web trafc in 2010 containing over 20 million unique queries. The default whitelist had 33,000 queries. When the scores were modi ed, the size increased to 57,000. We selected a random sample of 250 queries from those added to the whitelist and obtained annotations for their newsworthiness. To also con rm our choice to not remove queries from the whitelist, we also created a list of queries that would be demoted had we kept that option. A random sample of 250 queries from this list was also included for annotation.
The queries were presented on the next day to annotators. We did not use the same click data as for development because it is di cult for people to judge the newsworthiness of events from the past. We asked them to rate the news intent of queries on a 4-level scale a) very newsworthy, b) newsworthy, c) somewhat newsworthy d) not newsworthy. The division that the judges provided are shown in Table 2.
From the results, we see that 60% of queries added to the whitelist are clearly newsworthy. An additional 10% of the added queries are on the borderline. So a number of queries missed by the default predictor are added to the whitelist. We also see from the annotations for the removed queries, that removing queries from the whitelist seems not to be a good option. 30% of those removed are actually rated `very newsworthy'. However, it should be remembered that these judgements are only on a small sample. We also had 50 queries simultaneously annotated by 3 judges. The pairwise annotator agreement (Kappa) is only 0.29 to 0.36. Collapsing the levels into two categories|`very newsworthy' and `newsworthy' into one and the other two into a second category|increases the agreement to only 0.44 to 0.60 range. So it is rather di cult for human annotators to agree on the news level of events even for the most recent time frame. So we use this evaluation to validate our design and focus on system deployment to test if there are any signi cant improvements in the user experience. 5.2.2
rescored 10.67 2.39
We studied two small fractions of search users. There were 37 million unique queries issued by each set of users on a given day. During a two week period, news verticals were shown for one set of users as per baseline predictions. For the other, the rescored predictions were used. It is important to note that both systems were employed simultaneously during the two weeks, so users would be querying for the same events in both tracks. The CTR and coverage (proportion of queries that were shown displays) for the two branches are shown in Table 3.
After rescoring, there was a 2.36% improvement in CTR compared to the baseline approach. At the same time, the system was also able to show displays for 3.13% more queries than the baseline. Approximately same number of users interacted with the baseline and new system during the two week period. The click rate of each user was used as a data point and a Wilcoxon test was used to compare these values between the two systems. Both CTR and coverage are signi cantly di erent with p-values lower than 0.0001.
These results show that after rescoring, we were able to show news displays for more queries at the same time improving the average user engagement on the displays. 6.
Making accurate predictions is only a rst step towards display quality. The results retrieved for newsworthy queries should also be informative. Here again we can make use of information from similar queries. So we propose an approach to query canonicalization. For each newsworthy query, we identify a canonical variant which retrieves the most relevant results from the backend. This canonical query might be the original query itself or a semantically equivalent variant. In this way, quality results can be shown regardless of the query variant actually issued. Further this approach would ensure that similar queries have some uniformity and consistency in what results get highlighted for that news event. 6.1
This experiment is based on the data described in Section 3.1. We try to nd a canonical variant for each query in the whitelist. Those queries not predicted as newsworthy will not trigger news displays and need not be considered. For each query in the whitelist, we obtain a set of candidates for canonicalization. We limit these candidates to other queries in the whitelist which are highly similar (using the same threshold on lexical similarity as we have done so far). The original query is always added as a candidate.
The task is to pick out the candidate that will have highest success as a canonical variant. The whitelist queries are compiled to be used on the next day. So we de ne the most successful query as the one with highest next day CTR.1 However, we should avoid choosing very speci c and rare queries as canonical. For example, a query such as \Obama Texas debate opposition response" is rather speci c and could have a CTR value of 1, but might have been 91Only queries overlapping between consecutive days were used. Original query
Lexical variants marc anthony, jennifer lopez, jennifer lopez baby, jennifer lopez babies, jennifer lopez twins republican presidential candidates, 2008 presidential candidates satellite shoot down, US shoots down satellite, spy satellite shot down n draft combine, n combine, n draft, 2008 n draft,n draft 2008, n scouting combine, n mock draft issued only once. We do not wish to canonicalize queries such as \Obama debate" and \Obama Clinton texas debate" to such a speci c query. So we lter out candidates that were issued fewer than two times that day. (The original query is always retained as a candidate regardless of its frequency.) Then we also include the number of clicks with the CTR value while ranking the candidates: fnext day CTR * log(next day clicks+1)g. The top variant in this ranking is considered canonical.
Some examples from our data are shown in Table 4. We can see that the canonical variant chosen in this way is a crisp characterization of the event. Since we use lexical similarity, we can expect the candidate set to be of high precision. The candidates have at least one bigram match with the original query and so these matching keywords will still appear in the search results. We divide the data into a training set of 2876 examples and a test set of 1659. The breakdown of the number of candidates for di erent queries in our test set is below. (a) 2 candidates: 800 (b) 3 to 5 candidates: 636 (c) 6 and above: 223
Our de nition of canonical queries holds for a period of one day only. For the whitelist queries, we identify and store the mappings of original-canonical queries. On the next day, when a query from this list is issued, the canonical variant can be used for retrieving news results in place of the original one. The list is refreshed at the end of the day. It is also worth noting that we wish to present canonical results for the news display only so that the relevant news updates are provided for all query variants. The regular search results would still provide more ne-grained distinctions (if any) as per the original query. 6.2
We test several baselines for this task: a) a random query from the candidate set, b) the original query itself (no canonicalization), c) the query with maximum frequency that day, d) the query with maximum score from the GBDT model (the model predicts the next day CTR and high CTR queries could be considered as more representative ones), e) maximum and f) minimum length queries.
We also propose a ranking approach to canonicalization.
The target value fnext day CTR * log(next day clicks + 1)g
is used to train a ranker to predict the ordering of queries
within a candidate set. For this purpose, we employ
SVMRank [
Self Max. frequency Max. o ine score Max. length Min. length Ranking approach one. Our ranking approach combines a number of features with the baseline metrics.
Simple metrics. Frequency of the query, o ine model score, length of the candidate
Relationship to original query. Is the original query?, is substring/superstring of original query?, is subsequence/ supersequence of original query?
Content-based. These features are based on the relevance of the news documents that are present for a candidate query in the index. In addition, the readability of the titles from these news documents is also an important factor for quality of the news display. We retrieve the top 3 titles for the query from the news index and compute the following features: length of the titles, query is subsequence/substring of one of the titles (similarly for rst title), whether there is a title string that is spelled fully in capital letters.
Informativeness of the query. Words used in queries could make some queries more informative compared to others. So we add some features based on query word frequency and word types. We compute the frequency of each query word and bigram over all the candidates in a set. Then for each query, we indicate whether it contains the top, second or third most frequent unigrams and bigrams of that cluster. Numbers or year also get mentioned in some queries, for example, \grammy awards 2008". To check the usefulness of such information, we add the features: query contains number/year, query's pre x/su x is a number/year. We also indicate the presence of prepositions. 6.3
The accuracies for predicting the canonical query is shown in Table 5 for di erent baselines and the ranking approach. We also provide a breakdown of the results depending on the size of the candidate sets (columns 3-5): choosing the canonical variant from a larger set of options is bound to be a harder task.
Among the baselines, using the maximum frequency query produces the best results. It has an accuracy of 53% on all test examples, 10% higher than random choice. The maximum frequency heuristic is also consistently better performing than the other baselines for larger sets. When a set contains only two candidates (original query and one other variant), random choice, the original query or using the top o ine score query are equally e cient, giving 60% accuracy. The accuracy of these baselines degrades much more as the candidate set size increases.
The ranking approach outperforms the baselines for candidate sets of all sizes. There is a 3% improvement when all the test examples are considered. In closer look, one can see that the bene t of the ranking approach is more pronouned when there are more candidates. It gives a 10% improvement over the maximum frequency baseline for sets of size above 5 queries. In fact, the very popular queries are likely to have several variants and therefore a large candidate set. So the ranking approach would be the preferred setup for canonicalization in this case.
In this work, we have shown that our system which used query similarity had better user engagement and also increased the recall of newsworthy queries. There are several issues that we can address in future work. One is purging non-newsworthy queries from the whitelist. Since similarityonly rescoring was not accurate to do this, we have not addressed this aspect. Perhaps, a combination of query similarity to add queries and user feedback to quickly learn how to demote queries would be a good approach. We will explore these ideas in future.
In our approach, we have not only considered the prediction accuracy but also the presentation of the display. We have introduced the notion of a canonical query for news intent. As a simple baseline for canonical query, maximum frequency query is a good choice and the selection is further improved using query match and content features. But we have only worked with CTR data in this paper. We plan to conduct a user study to strengthen the result and help us to understand if canonical results are preferred by users.