Learning search popularity for personalized query completion in information retrieval

The basic query ranking approach works well based on the overall search popularity. However, the temporal information, e.g., recency, has not been taken into account in the original ranking model while the query popularity is changing over time. Rather than ranking query candidates by their previously overall popularity, researchers proposed a time series analysis based modeling approach to forecast the query frequency by applying a fixed moving time window [5]. Queries recurring during specific temporal intervals, such as day/night, workday/weekend, summer/winter, etc. are modeled differently to predict the future popularity for query ranking at different time. The forecasts obtained by such models are substantially more reliable, by which good query ranking can be generated. However, a detailed analysis of the performance impact of the time window period selection is lacking.

Moreover, the time information, such as recency, has been studied [12–14] and the seasonality has also been considered [5, 15] for ranking query candidates. These approaches employ time-series analysis techniques to forecast query’s future popularity [5, 15]. In addition, a popularity-based query ranking approach can be combined with other criteria. The hybrid model assigns a final score to each candidate by linearly combining the popularity score and another metric score, e.g., context similarity score. All these discussed models use the search popularity in a straightforward way, ignoring the latent contributions from recent search popularity or the trend. Our proposal will conduct a deep investigation on the impact of search popularity to query ranking performance.

2.2 Search context based query completion

In most work mentioned so far, query candidates are computed globally, and for a given prefix, all users are presented with the same list of candidates. However, different users have various search intents. Hence, exploiting user’s personal search context has led to increase the query ranking effectiveness [4, 16–18].

Typically, the user’s recent queries are used as context to find users with shared search activity [4, 19], considering the similarity of query candidates to this context for ranking. Their hybrid model computes a final score of each candidate by linearly combining the MPC score and a context-similarity score. Similarly, the click graph is used [11, 20] to measure the similarity between search context and query candidates, by which the query ranking list can be generated. Moreover, user interactions can play a prominent role in models for ranking queries [3, 21]. In addition, exploiting the context to learn user reformulation behavior is well proposed [21], where a supervised approach for ranking query completions based on term-, query- and session-level features of user reformulation behavior was proposed. These features can capture how users change their queries during search sessions and these interesting findings provide valuable insights for understanding user’s engagement in search systems.

In this paper, we argue that injecting recent search popularity features, from observations and predictions, into a learning to rank framework to query completion tasks will boost the ranking performance. In addition, our personalized query ranking based on semantic query similarity will help generate better ranking of queries.

3.1 Search popularity based features

We propose a learning-based query ranking method, i.e., LQR, that ranks query candidates by both observed and predicted query popularity (i.e., frequency) based on its recent trend. LQR not only inherits the merits of time-series analysis on short-term observations of query popularity, but also considers the overall query counts. Generally, we collect the observed query popularity in the whole query log as well as in recent m day(s), and denote the corresponding features as: f_o+w and f_o+m, where the former relates to the popularity in the whole query logs and the latter is collected only in the recent m days.

In addition, we predict a query q’s future popularity based on its recent preceding observations. The search popularity prediction y ˆ ( t 0 , q , i ) trend for query q at future day t₀ generated from the observation of preceding day i (i = 1, 2, ⋯ , n) is derived from the first order derivative of q’s daily count C (q, i) as Equation (2): y ˆ ( t 0 , q , i ) trend = C ( q , i ) + ∫ i t 0 ∂ C ( q , t ) ∂ t d t(2)

We indicate the features based on the predicted search popularity with f_p+n, where n denotes the day from which the prediction is generated.

The problem of learning-based query completion ranking can be formalized as follows. For a prefix p typed by a user and a query candidate set Q consisting of N queries to be ranked, i.e., q₁, q₂, ⋯ , q _N , the optimal ranking approach should return a ranked query list L _r that orders the queries in Q according to a score (or relevance), where the queries can be represented as vectors, e.g., q _i  ← {f_i1, f_i2, ⋯ , f _iu }, where u is the number of features. Hence, the query ranking approach tries to assign a score s (p, q) to each query candidate q in the set Q using a ranking function as Equation (3): s ( p , q ) ← ω → Φ ( p , q )(3) where ω → is a weight vector that is adjusted by learning. Φ (p, q) is a vector of mapping features that describe the match between query q and prefix p.

Typically, the ranking systems can not achieve an optimal ranked list L r * including all query candidates matching the typed prefix. Instead, we can only focus on the top positions in the list, e.g., the top N candidates. Formally, if a query q₁ is ranked higher than another query q₂ in a list L _r , we denote q₁ ≻  _{L r} q₂, and finally, if the query q₁ is issued by the user and the other queries in the candidate list are not, we can assign a binary score 1 to q₁ and 0 to others. By dong so, we can get a query-pair comparison score: com (q₁, q₂) =1 for the pair of q₁ and q₂, which can be used for learning.

We are now in a position to define the problem of learning a query ranking function. For a fixed but unknown distribution P ( p , L r * ) of prefix p and an optimal query ranking L r * in a query candidate set Q with N queries, the goal is to learn a ranking function f by which the expected score as Equation (4): ExpectedS ( f ) = ∫ s ( p , qr * d P ( p , qr * ) )(4) is maximal. Instead of maximizing (4) directly, it is equivalent to find a weight vector so that the maximum number of the following inequalities as Equation (5) is fulfilled. { ∀ ( q 1 i , q 1 j ) ∈ L * r 1 : ω → Φ ( p 1 , q 1 i ) > ω → Φ ( p 1 , q 1 j ) ∀ ( q 2 i , q 2 j ) ∈ L * r 2 : ω → Φ ( p 2 , q 2 i ) > ω → Φ ( p 2 , q 2 i ) ⋯ ∀ ( q ni , q nj ) ∈ L * rn : ω → Φ ( p n , q ni ) > ω → Φ ( p n , q ni )(5)

However, it has been shown that this problem is NP-hard [22]. Instead, it is possible to approximate the solution by introducing a non-negative variable ξ_i,j,k and minimizing the upper bound ∑ξ_i,j,k. Hence, it leads to the following optimization objective in Equation (6): min ∑ i , j , k ξ i , j , k(6) subject to the conditions in Equation (7): { ∀ ( q 1 i , q 1 j ) ∈ L * r 1 : ω → Φ ( p 1 , q 1 i ) - ω → Φ ( p 1 , q 1 j ) > 1 - ξ i , j , 1 ∀ ( q 2 i , q 2 j ) ∈ L * r 2 : ω → Φ ( p 2 , q 2 i ) - ω → Φ ( p 2 , q 2 j ) > 1 - ξ i , j , 2 ⋯ ∀ ( q ni , q nj ) ∈ L * rn : ω → Φ ( p n , q ni ) - ω → Φ ( p n , q nj ) > 1 - ξ i , j , n(7) where these constrains mentioned in Equation (5) can be directly derived from the query-pair comparisons in the training phase of query pairs for a specific prefix. Through this formulation of training samples, the query ranking function can be produced by applying a learning algorithm, e.g., SVM _light [23] or LambdaMART [24], which results in a ranking model M .

As queries in the same session always express similar search intents [25], we personalize query completion according to the query similarity to the current search context in session, i.e., the previous queries in session.

We introduce a hybrid model to incorporate the scores of the similarity and the ranking generated by the learning process in §3.2. First, the learning process produces a ranking of query candidates S (p) of prefix p, where each candidate q _c  ∈ S (p) is associated with a ranking score LeaScore (q _c ). Then we calculate the similarity score SimScore (q _c ) for q _c to the previous queries Q _S in session by the scheme in Equation (8)SimScore ( q c ) = 1 | Q S | ∑ q i ∈ Q S cos ( q c , q i ) ,(8) where |Q _S | indicates the number of queries in session and we use the cosine function to measure the similarity between queries. To represent queries, a word-embedding approach is introduced [26], which is based on the word representation. For instance, we use Equation (9) to calculate the cosine similarity between queries q₁ and q₂, cos ( q 1 , q 2 ) = 1 | q 1 | | q 2 | ∑ w i ∈ q 1 ∑ w j ∈ q 2 cos ( w i , w j ) ,(9) where |q| means the length of query q in words and each word w can be directly represented a vector returned by word2vec [26].

Like this work [4], we then define our hybrid model as a combination of two scores in Equation (10):

HybScore ( q c ) = γ · LeaScore ( q c ) + ( 1 - γ ) · SimScore ( q c ) .(10)

As LeaScore (q _c ) and SimScore (q _c ) use different units and scales, they need to be standardized before being combined. We standardize LeaScore (q _c ) as follows in Equation (11): LeaScore ( q c ) ← LeaScore ( q c ) - μ T σ T ,(11) where μ _T and σ _T are the mean and standard deviation of scores of queries in S (p). Similarly, we standardize SimScore (q _c ) in Equation (12): SimScore ( q c ) ← SimScore ( q c ) - μ P σ P ,(12) where μ _P and σ _P are the mean and standard deviation of similarity scores of queries in S (p). Algorithm 1 details the major steps of our LQR model.

Algorithm 1 Learning-based Personalized Query Ranking (LQR).

Require: A prefix p; A ranking model M learnt by popularity features; A list L of top N query candidates returned by MPC; Previous queries in session Q _S .

Ensure: A reranked list L′ of N query candidates;

1: for each query q ∈ Ldo

2:  Extract the popularity features q _i  ← {f_i1, f_i2, ⋯ , f _iu };

3:  Compute LeaScore (q _c ) using M ;

4:  Compute SimScore (q _c ) according to Eq. (8);

5:  Compute HybScore (q _c ) according to Eq. (10);

6: end for

7: Rerank query q ∈ L based on the hybrid scores to generate L′;

8: returnL′;

4.1 Dataset

We use the query log dataset collected from a commercial search engine. It’s sampled between March 1, 2006 and May 31, 2006. In total there are 16,946,938 queries submitted by 657,426 unique users and we partitioned the data into two parts: a training set consisting of 75% of the query log in terms of time period, and a test set consisting of the remaining 25%. Traditional k-fold cross-validation is not applicable to streaming sequence since it would disorder the temporal data [27]. Moreover, we filtered out a large volume of navigational queries containing URL substrings (.com,.net,.org, http,.edu, www.) from the dataset and removed queries starting with special characters such as &, $ and # from both datasets.

Additionally, only queries appearing in both partitions were kept in order to extract the popularity features. A cross-validation based approach cannot be applied in our setting because it will disorder the sequence of queries, resulting in incorrect time-aware query popularity. Table 1 details the statistics of the dataset. One of the most interesting findings from the data is that the phenomenon typified by a number of repeated queries from each user can be seen in both the training and testing phase.

One baseline used for comparisons with our method was proposed in 2011 [4], namely, the most popular completion method, which sorts the queries by their popularity based on the whole log, referred as MPC in this paper. In addition, we use another baseline for comparison, i.e., MPC-R [12], which ranks query candidates by the popularity collected in recent R days of query logs, where we set R = 7 in our experiments [12].

To evaluate the quality of query rankings, Mean Reciprocal Rank (MRR) is selected as a standard measure. Given a query q with prefix p in the query set Q associated with a list of query candidates S (p) for this prefix p, and the user’s finally completed query q, Reciprocal Rank (RR) is computed as Equation (13): RR = { 1 rank of q ′ in S ( p ) , if q ′ ∈ S ( p ) 0 , else .(13)

Then MRR is computed as the mean of RR for all prefixes.

In our learning-based query ranking approach experiments, we are first given a list of top N QAC candidates returned by MPC; we set N = 10 as this is commonly used [4, 11–13] and used by many web search systems. In addition, the cases where the final submitted query is not included in the original list of N candidates by MPC are removed from the dataset, to guarantee the ground truth is returned.

We use the LambdaMART [24] learning algorithm for ranking QAC candidates across all experiments. For the observed query popularity, we set m ∈ {1, 2, 4, 7, 14, 28}, which was often used [12] for the same task and reported a good result. These options are also used for predicting the future popularity. Therefore, we can generate totally 15 popularity features for each query, i.e., 7 features from observations in recent m day(s), 7 features from predictions based on recent m day(s), and 1 feature from observation in the whole query logs. We set the tradeoff γ = 0.5 in (10) to balance the contribution of learning-based ranking and of query similarity. In addition, we compare the models at various lengths of prefix in character, ranging from 1 to 5 characters.

5.1 Query completion ranking performance

In this section, we compare the query ranking results generated by our model against those of baselines, i.e., MPC and MPC-R. We report the performance of these two models in terms of MRR in Table 2. Clearly, our LQR model can beat the baseline MPC at all prefix lengths, which presents an MRR improvement around 8.10% and 5.31% generated at prefix length 1 and 5, respectively. Additionally, all the MRR scores are larger than 0.5, indicating that for most cases, the final submitted query can be returned early in the top two positions in the query list. One particularly interesting finding from Table 2 is that, the MRR scores are increased and the MRR improvement margins of LQR against MPC are decreased as the prefix length increases. It could be explained by the fact that long prefix can sharply narrow the space of query candidates, resulting in relatively high MRR scores and small MRR gaps when it’s increased.

Regarding MPC-R, it performs better than MPC at long prefix, e.g., 4 or 5, however, it loses the comparison with MPC at short prefix, e.g., 1. In contrast, our LQR models again beats MPC-R for at all prefix lengths. From the results shown in Table 2, we can conclude that, our LQR model can benefit not only from the overall popularity of candidates but also from the recent popularity. In addition, the personalization mechanism in our model helps further boost the ranking performance.

Next, we compare the performance of LQR and baselines at the prefix level in terms of reciprocal rank. We report the ratios of prefixes at various lengths for which LQR wins, ties and loses the comparisons against baselines in Table 3.

As shown in Table 3, compared to MPC, LQR shows a majority of draws (more than 50%). These draws actually often happen in these cases where both LQR and MPC return the ground truth (finally submitted query by user) early in the query list, e.g. at position 1 or 2. This could also be used to explain why these two models can receive very high MRR scores reported in Table 2. Another finding from Table 3, the opportunity for MPC of winning the comparisons against LQR is increased when more keystrokes are typed, i.e., when the prefix length becomes long. It means our model can work better for short prefixes than long prefixes.

In particular, LQR wins or ties MPC for most cases at various prefix length. In other words, LQR outperforms MPC frequently. It means these developed features for learning to rank queries used in LQR model do help improve the performance. We can also argue the search popularity in recent period does affect the ranking of query candidates. In order to have a deep look at these developed features, we will conduct an investigation on feature importance analysis in our learning algorithm in Section 5.3.

Regarding the comparison between LQR and MPC-R, similar findings can be observed. For prefix length at 1, MPC-R wins only 5.10% against LQR, less than the ratios of MPC, i.e., 5.38%. However, for longer prefixes, MPC-R wins LQR a bit more than MPC against LQR, indicated by the corresponding ratios at various prefix lengths. These results are consistent with the findings in Table 2, where MPC-R can work better than MPC at longer prefixes, e.g., 4 or 5.

Following previous work [28], we implement a feature ranking investigation to derive the relative importance of features used in our learning approach, according to a χ² test. We report the top ten important features used in our learning approach in Table 4. We score the most important feature with 1.0000 and assign the relative importance scores of other features against the most important one. By doing so, the scores are all in (0, 1).

As shown in Table 4, the feature of predicted search popularity based on the observation in 2 days before is the most important feature in our LQR model. Besides that, the observed search popularity in recent 4 days or 2 days are also important, which are ranked in position 3 and 4, respectively. Apparently, the search popularity in recent period either from observations or from predictions plays absolutely important role in query candidate ranking. In contrast, compared to the features in Table 4, the feature of popularity in recent 28 days is less important. However, the overall search popularity in the whole query logs, i.e. feature f_o+w, line 5 in Table 4, is relatively important. That’s probably because for some queries, their popularity are not time-sensitive but they are frequently issued by searchers.

Finally, we zoom in on the performance of our LQR model only using these top ten important features reported in Table 4. We denote this model as LQR _top and plot the comparisons in Fig. 3. Clearly, both LQR model and LQR _top model can beat the baseline MPC as all the MRR margins, i.e., the MRR scores of LQR-MPC and LQR _top -MPC are positive. In addition, if we compare the MRR gap between LQR and LQR _top , the biggest gap can be found at prefix length 1 and the gap is further shorten as the length of prefix increases. It could be explained by the fact that long prefixes make it difficult to distinguish the results generated by these two models, because both models report good performance in terms of MRR. Moreover, we can see from Fig. 3 that LQR always outperforms LQR _top , indicating than our learning-based query ranking approach not only learns from the important features, but also from the less important ones.

OPEN IN VIEWER

Fig.3

Overall performance of two models, i.e., LQR and LQR _top , tested on all prefixes at various lengths in terms of MRR margin, i.e., LQR-MPC and LQR _top -MPC.

To examine the relative contribution of learning output and of personalization, we manually vary the value of γ in (10) in LQR and LQR _top models form 0.1 to 0.9 with interval 0.1. We plot the results in Fig. 4.

OPEN IN VIEWER

Fig.4

Performance of LQR in terms of MRR at various γ.

As shown in Fig. 4, apparently, our LQR and LQR _top models with a relatively small γ < 0.5 can produce better results than those with a large γ > 0.5. It means that in our task, the personalized information of search context similarity contributes much more than the learning output. It’s further confirmed by the finding that both models achieve the best performance when γ = 0.3. In addition, we find LRQ is more sensitive to γ than LQR _top as it shows obvious fluctuation when γ varies.