Source-linked AI summary
A Hierarchical Recurrent Encoder-Decoder For Generative Context-Aware Query Suggestion
Alessandro Sordoni, Yoshua Bengio, Hossein Vahabi, Christina Lioma, Jakob G. Simonsen, Jian-Yun Nie
TL;DR
Query suggestion must preserve intent across ordered query histories despite data sparsity, especially for rare and complex queries. The paper introduces a hierarchical recurrent encoder-decoder that generates synthetic suggestions from variable-length contexts. It reports improved next-query ranking and better synthetic queries than compared methods in a user study, while noting limited diversity in generated reformulations.
Problem
Context-aware suggestion must use ordered previous queries, but diverse contexts create sparsity and co-occurrence methods provide weak coverage for rare or long-tail queries.
Method
A hierarchical recurrent encoder-decoder uses query-level and session-level RNNs to generate synthetic next-query word sequences from variable-length query histories.
Results
The model improves MRR in next-query ranking and user-study participants judged its synthetic queries better than those from compared methods.
Takeaways & Limitations
The architecture handles context-aware and rare-query suggestion while supporting end-to-end training and generative query production.
Takeaways & Limitations
Generated suggestions tend to be horizontal, adding or removing terms from context queries, and rarely propose orthogonal but related reformulations.
Abstract
from arXiv · showhide
Users may strive to formulate an adequate textual query for their information need. Search engines assist the users by presenting query suggestions. To preserve the original search intent, suggestions should be context-aware and account for the previous queries issued by the user. Achieving context awareness is challenging due to data sparsity. We present a probabilistic suggestion model that is able to account for sequences of previous queries of arbitrary lengths. Our novel hierarchical recurrent encoder-decoder architecture allows the model to be sensitive to the order of queries in the context while avoiding data sparsity. Additionally, our model can suggest for rare, or long-tail, queries. The produced suggestions are synthetic and are sampled one word at a time, using computationally cheap decoding techniques. This is in contrast to current synthetic suggestion models relying upon machine learning pipelines and hand-engineered feature sets. Results show that it outperforms existing context-aware approaches in a next query prediction setting. In addition to query suggestion, our model is general enough to be used in a variety of other applications.
1. INTRODUCTION
Query suggestion must preserve search intent across sequential reformulations while handling sparse, rare, and unseen contexts. The paper presents a generative model that produces synthetic, context-aware suggestions for variable-length query histories.
- Query reformulation suggestions are produced after users submit one or more queries, unlike auto-completions generated during query entry.
- Query co-occurrence in sessions signals relatedness, but count-based methods suffer data sparsity and weak coverage for rare or long-tail queries.Long-tail queries are unseen in the training data and may require more common, effective formulations based on similar observed queries.
- Context-aware suggestions should use previous queries and their order because they narrow ambiguity and encode generalization or specification reformulation patterns.Diverse contexts create sparsity, making classical count-based models unreliable.
- Synthetic suggestions address cases where the best formulation for a rare query or complex information need has not appeared in training data.They can increase coverage and serve as candidates for learning-to-rank models.
- The proposed probabilistic model predicts likely word sequences after a query prefix, supports variable context lengths, and generates suggestions for popular and long-tail queries.Sampling likely continuations uses standard word-level decoding techniques, while representing the prefix as words helps robustness to long-tail effects.
- In an example session, the model generates “cleveland indian art” by using the earlier query’s concept and does not require the suggestion to occur in training data.The suggestion is sampled sequentially until a special end-of-query symbol is reached.
- The architecture embeds words, queries, and query sequences as dense vectors, avoiding data sparsity while enabling end-to-end training on query sessions.The authors also identify potential applications in search-log mining, auto-completion, and next-word prediction.
2. KEY IDEA
The model combines word- and query-level recurrent encoding with session-level context modeling and recurrent decoding. This hierarchy preserves query order, generalizes across similar queries, and conditions next-query generation on arbitrary session histories.
- Word and query embeddings place topically similar terms and queries near one another in the learned vector space.
- An RNN builds an order-sensitive query representation by updating a recurrent state for each word in sequence.The state summarizes information seen up to the current word, unlike simple averaging of word vectors.
- A decoder RNN converts a query encoding into a conditional distribution over possible next queries and samples words until the end-of-query symbol.Each generated word updates the recurrent state before the next word is sampled.
- A recurrent encoder-decoder maps one query to the next, but this pairwise design loses most of the broader session context.The query encoder’s representation initializes the decoder for the following query.
- The hierarchical architecture adds a session-level RNN above the query encoder, summarizing past queries before the decoder predicts the next query.The session state retains information relevant to next-query prediction and makes generation contextual.
- Similar contexts map near one another, allowing the model to generalize to unseen queries whose words are in vocabulary and to handle arbitrary-length contexts.This representation supports useful formulations beyond previously co-occurred queries and avoids the sparsity of count-based models.
3. MATHEMATICAL FRAMEWORK
The mathematical framework represents a query session as chronologically ordered queries, with each query represented as an ordered sequence of words from a vocabulary.
- A session is a sequence of M user queries submitted in chronological order, typically within a 30-minute time frame.
- Each query Q_m is an ordered sequence of N_m words, and V denotes the vocabulary size.
3.1 Recurrent Neural Network
The model uses recurrent states to encode query words in order and predict subsequent words. GRU gating helps retain relevant information across longer sequences while filtering less informative input.
- Recurrent representation: An RNN updates a recurrent state for each query word, creating an order-sensitive summary of the words seen so far.The first state is initialized with the zero vector.
- Gated recurrent units: The gating behavior is intended to ease learning long-term dependencies at affordable computational cost and improve robustness to noisy input sequences.The paper hypothesizes that this can exclude non-discriminative query terms from the summary.
- Recurrent representation: The encoder uses the final recurrent state as a fixed-length representation of the input query, while the decoder uses recurrent states to predict the next word.Word probabilities are computed from the preceding recurrent state and normalized over possible vocabulary items.
- Gated recurrent units: GRUs add reset and update gates that control whether past information is forgotten and whether current information is stored.The final update combines the previous state with a candidate update according to the update gate.
- Query suggestion: In the HRED example, the model encodes previous queries, updates session-level recurrent states, and samples a contextual suggestion from the final state.For the illustrated context, the generated suggestion is cleveland indian art.
3.2 Architecture
HRED hierarchically combines query-level and session-level recurrent networks to preserve word order within queries and query order across sessions. A decoder then uses the session summary to generate the next query contextually.
- Query-level encoding: The query-level encoder reads each query sequentially and maps it to a fixed-length, order-sensitive vector shared across session queries.The final hidden state stores information about all words in the query.
- Session-level encoding: The session-level GRU processes query representations sequentially, producing states that summarize prior queries and retain their order.These states can encode order-dependent generalization or specification reformulation patterns.
- Contextual decoding: The decoder is initialized with a nonlinear transformation of the preceding session state, transferring previous-query information into next-query generation.The projection maps the session summary into the decoder space before recurrent decoding begins.
- Contextual decoding: The decoder GRU updates its state word by word and estimates each next-word probability from the preceding decoder state and generated word.An output transformation combines decoder-state and previous-word information before comparing words in the output space.
3.3 Learning
The model learns its recurrent and output parameters by maximizing the log-likelihood of training sessions. Gradients are computed with back-propagation through time.
- Objective: The parameters of the encoder, decoder, session GRUs, and output components are learned by maximizing the log-likelihood of a session.The objective uses probabilities estimated by the model's specified equations.
- Optimization: Gradients for the learning objective are computed using back-propagation through time.BPTT is the stated optimization-gradient procedure.
3.4 Generation and Rescoring
Generation treats next-query suggestion as inference conditioned on the submitted query sequence, using word-level beam search to construct well-formed queries. The model can also rescore candidate suggestions through their conditional likelihood.
- Generation: Given a sequence of submitted queries, generation seeks a likely next query from the space of sentences ending with the end-of-query symbol.The target query is defined as the highest-probability candidate under the model's conditional distribution.
- Generation: Beam search keeps the k best prefixes, extends them with probable next words, and repeatedly retains the k best candidates.Generation ends when k well-formed queries contain the special end-of-query token.
- Generation: In the worked example, query vectors and session states are computed before decoding begins from the last session-level state.With beam size 1, the example selects cleveland and then indian as successive words.
- Rescoring: Table 1 presents HRED suggestions given the context.The supplied table caption identifies the table's purpose but does not state a specific comparison or outcome.
- Rescoring: The model can score a suggestion conditioned on previous-query history, allowing its likelihood to serve as an additional feature in a learning-to-rank system.This rescoring capability supports integration into more complex suggestion systems.
4. EXPERIMENTS
Experiments evaluate HRED for next-query prediction on AOL search logs using candidate reranking, session-length and context-length analyses, robustness tests, long-tail queries, and a user study. HRED improves over baselines across these settings, including noisy contexts and long-tail queries.
- Evaluation setup: The evaluation uses AOL search logs and ranks 20 candidates per session with LambdaMART, labeling the true next query as relevant.The study includes general next-query prediction, perturbed contexts, and cases where the anchor query is absent from the background data.
- Next-query prediction: The Baseline Ranker improves 4.3% over ADJ, while adding HRED features yields a 7.8% relative improvement over ADJ, with both differences significant at p < 0.01.These results are reported for the general next-query prediction setting.
- Session length: HRED improves significantly across short, medium, and long sessions, achieving its highest relative gains in long sessions: +15% over ADJ and +7% over the Baseline Ranker.ADJ loses performance as session length increases, whereas HRED remains robust across session lengths.
- Context length: HRED performs best when the entire context is used, and considering more than 3 queries provides additional gains on long sessions.With one query, HRED performs similarly to the whole-context Baseline Ranker at 0.529.
- Robust prediction: In corrupted-context tests, HRED improves 17.8% over ADJ and 9.9% over the Baseline Ranker, with both improvements statistically significant.The reported improvements over the two baselines are 2.5 and 3 times higher, respectively, than in the standard next-query task.
- Long-tail prediction: For long-tail queries, HRED improves 5.6% over the Baseline Ranker and remains useful despite anchor-prefix matching reducing ADJ performance.Only 8% of long-tail session contexts contain a noisy query, compared with 37% in the general next-query setting.
- User study: In a user study, 64% of HRED recommendations were judged useful or somewhat useful, exceeding the baselines in both categories.Assessors evaluated recommendations for 50 test-bed queries using useful, somewhat useful, and not useful ratings.
5. RELATED WORKS
Prior query-suggestion work models context, similarity, synthetic generation, and neural representations, but existing approaches face long-tail coverage or computational limitations.
- Context-aware query suggestion: Variable Memory Markov models and clustered-query suffix trees represent higher-order query sequences for context-aware suggestion.The former was used as a baseline feature, while the latter did not improve the authors’ supervised ranker.
- Graph and clustering approaches: Query Flow Graph methods capture high-order co-occurrence, while Term-QFG adds individual query terms to address query-level long-tail limitations.Term-QFG requires repeated complex random walks with restart, whereas the proposed model handles rare queries when their words are in vocabulary.
- Synthetic suggestion models: Synthetic suggestion methods use WordNet templates or multiple resources with machine-learning pruning, whereas likelihood maximization learns related-term modifications.These modifications include automatic addition, removal, and substitution of related terms.
- Neural networks for NLP: Neural NLP systems commonly use recurrent architectures, while this work contributes a hierarchical structure for query suggestion.Related neural approaches include machine translation, embeddings for information retrieval, and pairwise query-similarity ranking.
6. CONCLUSION
The paper presents a hierarchical neural query-suggestion model that is context-aware, handles rare queries, and supports end-to-end training. Experiments report improved next-query ranking and better synthetic queries than compared methods, while future work targets diversification and broader applications.
- Conclusion: The model is context-aware, handles rare queries, and can be trained end-to-end on query sessions using simple optimization procedures.Its architecture is also generative by definition.
- Conclusion: The model’s scores improve mean reciprocal rank for next-query ranking, and a user study finds its synthetic queries better than compared methods.The conclusion reports both ranking gains and a user-study comparison.
- Future work: Future work includes click-based usefulness modeling, large-scale automatic evaluation, suggestion diversification, and leveraging interactions with previous suggestions.The authors also identify auto-completion, next-word prediction, and other NLP tasks as possible applications.
- Limitations: Synthetic suggestions tend to be horizontal, adding or removing terms from context queries while rarely proposing orthogonal but related reformulations.The authors plan to diversify generation to address this effect.