# Seasonality Based Reranking of E-commerce Autocomplete Using Natural
Language Queries

Prateek Verma
Walmart Global Tech
Bellevue, WA
<EMAIL_ADDRESS>Shan Zhong
Walmart Global Tech
Bellevue, WA
<EMAIL_ADDRESS>
Xiaoyu Liu
Walmart Global Tech
Hoboken, NJ
<EMAIL_ADDRESS>Adithya Rajan
Walmart Global Tech
Hoboken, NJ
<EMAIL_ADDRESS>

###### Abstract

Query autocomplete (QAC) also known as typeahead, suggests list of complete
queries as user types prefix in the search box. It is one of the key features
of modern search engines specially in e-commerce. One of the goals of
typeahead is to suggest relevant queries to users which are seasonally
important. In this paper we propose a neural network based natural language
processing (NLP) algorithm to incorporate seasonality as a signal and present
end to end evaluation of the QAC ranking model. Incorporating seasonality into
autocomplete ranking model can improve autocomplete relevance and business
metric.

Seasonality Based Reranking of E-commerce Autocomplete Using Natural Language
Queries

Prateek Verma Walmart Global Tech Bellevue, WA<EMAIL_ADDRESS>Shan
Zhong Walmart Global Tech Bellevue, WA<EMAIL_ADDRESS>

Xiaoyu Liu Walmart Global Tech Hoboken, NJ<EMAIL_ADDRESS>Adithya
Rajan Walmart Global Tech Hoboken, NJ<EMAIL_ADDRESS>

##  1 Introduction

Query autocomplete (QAC) is a common feature in most modern search engines. It
refers to the task of suggesting complete queries given the prefix consisting
of limited number of characters Cai et al. (2016). Goal of QAC is to help
users formulate their query or predict user’s intent. Studies have shown that
it can significantly reduce the number of characters typed, thus reducing
physical and cognitive overload (Shokouhi and Radinsky, 2012; Zhang et al.,
2015). An autocomplete system typically consists of two steps: _Matching_ and
_Ranking_ : Matching refers to the task of generating candidates using some
form of string matching or retrieval techniques using data structures such as
prefix trees. In the second step (Ranking) the matched suggestions are ordered
according to their expected likelihood Shokouhi (2013).

The focus of this paper is _Ranking_ step, specifically, generation of the
seasonality scores for each query such that it can be generated offline and
incorporated in the autocomplete ranking model. Seasonality plays an important
role in e-commerce search. Likelihood of users searching for seasonal queries
in that particular season is higher than the non-seasonal queries. For
example, in winter, users are more likely to search for winter related queries
like _winter gloves_ or _winter hats_ than generic version of _gloves_ or
_hats_. Therefore it makes sense to rank them higher during winter season.
Since seasonal queries is mostly searched during specific part of the year
they do not have very high aggregate popularity score. So, the common practice
of ranking queries by their aggregate popularity score can overshadow this
temporal factor.

In this paper, we define the query’s seasonality score based on query volume
similar to the idea mentioned in Yang et al. (2021) and propose a simple feed
forward neural network architecture to predict score given the query and
month. The model learns relationship between query tokens and the time period
specified in the training data and can predict seasonality scores for new
queries. This score can be generated for all the queries regardless of whether
it is head, torso or tail and can be computed offline. It can then be
integrated in the QAC ranking model to reflect seasonality in the suggested
queries and their ranking. We also show the improvement in relevance and
business metrics using offline evaluation and online experiments.

††Accepted at The Sixth Workshop on e-Commerce and NLP (ECNLP 6), KDD’23, Long
Beach, CA

##  2 Related Works

Cai et al. (2016) reviewed and summarized recent advancements over the auto-
complete works in their survey paper. One of the most common approach for
ranking QAC suggestions is to $aggregate$ the query frequency over query log
and use these for ranking. Bar-Yossef and Kraus (2011) referred to this as
_MostPopularCompletion_ (MPC).

$MPC(p)=\arg\max_{q\in C(p)}w(q),w(q)=\frac{f(q)}{\sum_{i\in Q}f(i)},$ (1)

where $f(q)$ denotes the number of times the query $q$ appears in the search
log $Q$ and $C(p)$ is a set of query completions that start with the prefix
$p$. Under the MPC model, the candidates are ranked by their past popularity
and the scores do not change as long as the same query log $Q$ is used. It is
assumed here that the current query popularity distribution will remain the
same as that previously observed.

Time sensitive QAC approaches have been studied in (Shokouhi and Radinsky,
2012; Whiting and Jose, 2014; Strizhevskaya et al., 2012). Shokouhi and
Radinsky (2012) analyzed why it is hard for MostPopularCompletion (MPC) based
approach to handle queries whose popularity may change over a period of time.
To account for such temporal behavior, they propose a time sensitive QAC
ranking model. Here the default aggregate candidate scores are replaced with
forecasted values computed by time-series models based on query history. In
Whiting and Jose (2014), the author uses predicted popularity based on short-
range time period regression models to rank the suggestions. In addition,
Jiang et al. (2017) proposed a hybrid QAC model combining periodicity with
burst trend to predict future popularity of queries. They use Discrete Fourier
Transform to find the periodic behavior of each query’s popularity. Cai et al.
(2014) proposed a hybrid QAC model which considers predicted query popularity
and user-specific context. The predicted query popularity is defined based on
long-term time series analysis plus recent trend based on regression model.

Seasonality in queries has been studied before. Shokouhi (2011) used time
series decomposition techniques to identify seasonal queries in the context of
web search. Vlachos et al. (2004) built time series for each query and phrase
in the query logs and detected significant periodicities and burst in
sequences. A recent work on seasonal relevance in ecommerce by Yang et al.
(2021) leverages deep learning based language modeling task to learn and
assign seasonal relevance scores to items. These scores are used as signals in
search ranking.

In this paper, our work focuses on time-sensitive auto-completion in QAC
ranking. The primary difference between prior work and our work is that we use
a neural network model to assign seasonality score to queries. Benefit of the
deep learning based NLP approach is that it can learn from large amount of
queries present in the search logs and learn to model the relationship between
query tokens and time of the year (month in our case). This enables the
feasibility to predict the seasonality for unseen or rare queries with limited
historical data. E-commerce search logs typically follow long tail
distribution, and such characteristics make language model based deep learning
techniques more desirable since the queries in QAC will have comprehensive
coverage for the seasonality score.

Application of deep learning in the context of QAC has been studied before
such as (Park and Chiba, 2017; Yuan and Kuang, 2021). However, the direction
of work is orthogonal to ours. Park and Chiba (2017) proposed a neural
language model to generate a queries for unseen or rare prefixes, and Yuan and
Kuang (2021) proposed deep pairwise learning to rank model that employs
contextual and behavioral features to rank the queries by minimizing pairwise
loss.

##  3 Seasonality

We conduct our study for the queries in our search logs. Queries tend to show
seasonality patterns, which is demonstrated by the peak and off-peak traffic
during different periods of the year. For example, in November and December
queries related to Thanksgiving and Christmas have higher traffic. In auto-
complete, our goal is to assign a higher weight to these queries according to
their seasonalities.

###  3.1 Definition of seasonality

Similar to Yang et al. (2021) we define seasonality of a query in a given
month as probability of seeing the query in that month conditioned on its
occurrence. This can be estimated by the query traffic or query volume V as:

$V_{qm}=\frac{\frac{t_{qm}}{t_{m}}}{\sum_{m^{{}^{\prime}}=1}^{12}\frac{t_{qm^{{}^{\prime}}}}{t_{m^{{}^{\prime}}}}},$
(2)

where $t_{qm}$ denotes the traffic of query $q$ in month $m$, and $t_{m}$ is
the overall traffic of the month.

An advantage of the above equation is that, it enforces the value to be
between 0 and 1 for each query - month pair. This allows us to compare
seasonality component of each query independently, regardless of the aggregate
popularity of the query. Also, normalizing query volume in the given month
$t_{qm}$ by total query volume in that month $t_{m}$ takes care to a certain
extent of changing consumer shopping pattern overall or external circumstances
across different time period in the year.

Figure 1 indicates the trend that is captured by the above Eq. (2) in the year
for sample queries _winter hats_ and _fathers day gift_.

Figure 1: Sample query volume $V_{qm}$ across the twelve months

##  4 Modeling seasonality

Seasonality for a given query $q$ in the month $m$ can be estimated from data
through $V_{qm}$ . However, it has couple of limitations. First, it can only
be computed for queries which have traffic information available. Second, it
can be noisy due to factors like the query being tail/torso, sparse data, and
other external scenarios.

To take care of cold start and reduce noise due to the above mentioned issues,
we build a neural network to model the seasonality values based on the query
text $q$, month $m$ and $V_{qm}$ which is defined in the previous section. $q$
and $m$ is the input to the neural network and $V_{qm}$ is the target value.
The model can be represented by a function $f(\theta):$ ($q$, $m$)
$\rightarrow$ $S_{qm}$, and $f(\theta)$ is learnt by minimizing the mean
square error

$L=\sum_{q\in D}(S_{qm}-V_{qm})^{2}$ (3)

Here $D$ is the dataset of training documents. $S_{qm}$ is the value predicted
by the model, month $m$ is a value between 1 and 12 representing January to
December. It is represented as a one hot encoding. Query $q$ is the embedding
of query text. We model the function $f$ using a feed forward neural network.

To mitigate the issue of disambiguating new product launches with seasonality,
mutiple years can be considered for the training data.

###  4.1 Training Dataset Generation

We use search query logs to create the training dataset. It is a log of every
single query the search platform has seen in the past. Firstly, we compute
monthly query volume for each query $t_{qm}$ and filter out queries that have
query volume below certain threshold say $K$. Then we aggregate monthly query
volume of all search queries $t_{m}$. Finally, using the Eq. (2) we compute
$V_{qm}$. This is normalized and scaled to a value between 0 to 1 using
monthly and yearly search traffic. After the thresholding and some random
sampling, our training dataset consist of about 337,000 distinct queries.

Figure 2: Feed-forward neural network for predicting seasonality value for a
given query and month

###  4.2 Model Architecture

Figure 2 shows the model architecture. It accepts query $q$ and month $m$ as
inputs. We encode query using dense vector representation Mikolov et al.
(2013) and month by a one-hot vector representation. We initialize the
embedding layer with a 300 dimensional pre-trained Glove embedding Pennington
et al. (2014). This layer is set as trainable.

We use dropout ratio of 0.2 in between the layers to reduce overfitting, it
was obtained via hyper parameter tuning. The layers in between use $relu$ as
non-linear activation function. Finally, the output layer is a single neuron
with $linear$ activation function. The intuition behind the architecture is to
capture relevancy of the given query and month for building a regression model
which can predict $V_{qm}$. To select number of layers, dropout and the
dimensions of Glove embedding, we performed hyper parameter tuning and used
_mean square error_ as the evaluation metric. We were able to obtain optimal
_mean square error_ using the configuration of the architecture as described
above.

$Adam$ $optimizer$ and $mean$ $square$ $error$ loss function are used for
training the model.

In table 1, we show the loss metric for 100 and 300 dimensional Glove
embedding pretrained with 6B and 42B tokens Pennington et al. (2014). We
report the numbers for configuration of the dropout parameters for which we
obtained the best _mse_ loss.

The neural network model can be further improved by potentially introducing
attention layer. Another way to model seasonality is to build a sequence to
sequence deep learning model and have it predict twelve numbers for a given
query which correspond to seasonality values for the twelve months in a year.
We leave the evaluation of these methods as future work. Note that the
objective of this paper is to define seasonality and evaluate if integrating
it with the auto-complete ranking model improves the overall ranking
performance.

Table 1: Test error to evaluate Glove embeddings Glove Embedding | Test Error (MSE)
---|---
6B 100D | 0.00218
6B 300D | 0.00241
42B 300D | 0.00215
Table 2: Autocomplete suggestion for the prefix "memo" a week before memorial day Control | Test Group
---|---
memory foam mattress topper | memorial day flowers
memory foam mattress | memory foam mattress topper
memory foam pillow | memory foam mattress
memorial day flowers | memorial day decorations
memory card | memory foam pillow
memorial day decorations | memorial day
memory foam futon | memorial flowers
Table 3: Offline evaluation: mean reciprocal rank on four different platforms Device | Desktop | Mobile web | IOS | Android
---|---|---|---|---
MRR lift | +0.37% | +0.96% | +0.24% | +0.13%

##  5 Experiment

In this section, we discuss the impact of integrating seasonality into the
auto-complete ranking model. Our analysis is based on seasonality values
modeled using the predictive approach described in the previous section. We
study the impact through offline evaluation and online experiment.

###  5.1 System Implementation for QAC ranking model

Our auto complete system consists of two components: _L1_ and _L2_ ranker (a
re-ranking model). _L1_ ranker is linear time series model trained on a
historical search log. It is trained to predict a linear combination of number
of add-to-carts, clicks and impressions a given query would receive in
upcoming weeks. This runs offline in a batch manner and helps us select
initial corpus of queries which we index into our auto-complete platform. _L2_
ranker is a runtime re-rank model: a function of the offline score generated
by _L1_ ranker and the user session level feature. It performs re-ranking and
shows top ten suggestion to users. This function could be a simple linear
model or a more sophisticated function estimated through deep learning models.
In _L2_ ranker we incorporate the seasonality value predicted by the deep
learning model as a signal.

The _L1_ ranker already captures seasonality and time sensitivity to a certain
extent. By integrating the seasonality signal into the re-rank model _L2_ , we
are interested to observe the additional improvements to the ranking. We
obtained the weight for the seasonality signal in the L2 ranker by fine-tuning
it on evaluation datasets. For offline and online evaluation, the control
group is the QAC model where _L2_ ranker does not have seasonality signal and
the test group is the QAC model where _L2_ ranker includes the seasonality
signal.

Table 2 shows ranking of QAC suggestions for the prefix "memo" a week before
the memorial day in the US. We can see suggestions related to the memorial day
event is ranked higher in test compared to the control goup. It is to be noted
that extra suggestions relevant to the event show up because we re-rank top
_N_ suggestions obtained from L1 ranker to display top _K_ to the user, where
_N_ > _K_.

###  5.2 Offline evaluation

The offline evaluation system uses queries from historical search logs to
query the auto-complete system and records the suggestions for each character
of a given query. From the search logs we know the ground truth query i.e.
final query user had submitted. Thus we can compute reciprocal rank for each
search request. We use this technique to compute _mean reciprocal rank_ (MRR)
from about 400,000 prefixes generated from randomly sampled 50,000 search
queries for four platforms: desktop, mobile web, IOS and Android. Table 3
shows the impact of incorporating seasonality feature into the autocomplete
ranking model on MRR for the four platforms. We observe statistically
significant lift in MRR.

###  5.3 Online experimentation

We conduct an online A/B test and study the effect of incorporating
seasonality feature into our autocomplete ranking. Experiment shows the
ranking model with seasonality signal in iOS and android yields a lift of
0.25% (p-value < 0.1) and 0.34% (p-value < 0.1) in GMV (Gross Merchandise
Value) respectively.

##  6 Conclusion and Future Work

In this work, we introduced a method to make auto-complete suggestions
seasonally relevant using deep learning based NLP algorithm to predict
seasonality for a given query and month. The predicted score is integrated as
a feature in the auto-complete learning-to-rank model. We also present end-to-
end evaluation of auto-complete ranking model and measure the gains in _mean
reciprocal rank_ (MRR).

As future work, we intend to explore following areas: First, generation of
seasonality score at a more granular level such as biweekly, weekly intervals
or include day of the week as signal in the ranking model. Second, making use
of transformer based architecture to model the seasonality of queries. Third,
study the interaction of seasonality and query category, and include
seasonality at the category level in the learning-to-rank model.

## Acknowledgements

We would like to thank Ari Kast, Aishwarya, Sanjay Shah and Kevin Li from the
Walmart Search Team for helping with the platform engineering support. We are
also very thankful to John Yan for providing leadership support.

## References

  * Bar-Yossef and Kraus (2011) Ziv Bar-Yossef and Naama Kraus. 2011.  Context-sensitive query auto-completion.  In _Proceedings of the 20th international conference on World wide web_ , pages 107–116.
  * Cai et al. (2016) Fei Cai, Maarten De Rijke, et al. 2016.  A survey of query auto completion in information retrieval.  _Foundations and Trends® in Information Retrieval_ , 10(4):273–363.
  * Cai et al. (2014) Fei Cai, Shangsong Liang, and Maarten De Rijke. 2014.  Time-sensitive personalized query auto-completion.  In _Proceedings of the 23rd ACM international conference on conference on information and knowledge management_ , pages 1599–1608.
  * Jiang et al. (2017) Danyang Jiang, Honghui Chen, and Fei Cai. 2017.  Exploiting query’s temporal patterns for query autocompletion.  _Mathematical problems in engineering_ , 2017.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  _Advances in neural information processing systems_ , 26.
  * Park and Chiba (2017) Dae Hoon Park and Rikio Chiba. 2017.  A neural language model for query auto-completion.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 1189–1192.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Shokouhi (2011) Milad Shokouhi. 2011.  Detecting seasonal queries by time-series analysis.  In _Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval_ , pages 1171–1172.
  * Shokouhi (2013) Milad Shokouhi. 2013.  Learning to personalize query auto-completion.  In _Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval_ , pages 103–112.
  * Shokouhi and Radinsky (2012) Milad Shokouhi and Kira Radinsky. 2012.  Time-sensitive query auto-completion.  In _Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval_ , pages 601–610.
  * Strizhevskaya et al. (2012) Alisa Strizhevskaya, Alexey Baytin, Irina Galinskaya, and Pavel Serdyukov. 2012\.  Actualization of query suggestions using query logs.  In _Proceedings of the 21st International Conference on World Wide Web_ , pages 611–612.
  * Vlachos et al. (2004) Michail Vlachos, Christopher Meek, Zografoula Vagena, and Dimitrios Gunopulos. 2004\.  Identifying similarities, periodicities and bursts for online search queries.  In _Proceedings of the 2004 ACM SIGMOD international conference on Management of data_ , pages 131–142.
  * Whiting and Jose (2014) Stewart Whiting and Joemon M Jose. 2014.  Recent and robust query auto-completion.  In _Proceedings of the 23rd international conference on World wide web_ , pages 971–982.
  * Yang et al. (2021) Haode Yang, Parth Gupta, Roberto Fernandez Galan, Dan Bu, and Dongmei Jia. 2021\.  Seasonal relevance in e-commerce search.  In _CIKM 2021_.
  * Yuan and Kuang (2021) Kai Yuan and Da Kuang. 2021.  Deep pairwise learning to rank for search autocomplete.  _arXiv preprint arXiv:2108.04976_.
  * Zhang et al. (2015) Aston Zhang, Amit Goyal, Weize Kong, Hongbo Deng, Anlei Dong, Yi Chang, Carl A Gunter, and Jiawei Han. 2015.  adaqac: Adaptive query auto-completion via implicit negative feedback.  In _Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval_ , pages 143–152.


Beyond special cases such as SIC measurements, we present a numerical approach to evaluate intrinsic randomness under a general POVM. For the convex-roof-type randomness measure defined by the optimization in Eq.~\eqref{appeq:Rexdecomp}, the objective function is biconvex in its arguments, the probability distribution $\{r_j\}$ and decomposed extremal POVMs $\{\mathbf{N}^j\}$. Also, the constraints form a convex set. For such optimization problems, a global optimal value can be obtained in principle~\cite{gorski2007biconvex}. Nevertheless, there are two difficulties: (1) the characterization of the set of extremal POVMs is relatively complex~\cite{d2005classical}, (2) the dimension of the probability distribution $\{r_j\}$ is not fixed.

To tackle the first problem, we can remove the constraint that $\{\mathbf{N}^j\}$ are all extremal. To see why this is the case, suppose the optimal value to Eq.~\eqref{appeq:Rexdecomp} is given by the tuple $\{r_j^{*},\mathbf{N}^{*j}\}$. In Theorem~\ref{appthm:POVMrandom}, we show that for any probability distribution $\{\tilde{r}_k\}$ and POVMs $\{\tilde{\mathbf{N}}^k\}$ such that $\mathbf{M}=\sum_k\tilde{r}_k\tilde{\mathbf{N}}^k$, the following inequality holds,
\begin{equation}
\sum_k\tilde{r}_k R\left(\rho\otimes\ketbra{0},\tilde{\mathbf{P}^k}\right)\geq\sum_jr_j^{*}R\left(\rho\otimes\ketbra{0},\mathbf{P}^{*j}\right) =\sum_jr_j^{*}R\left(\rho,\mathbf{N}^{*j}\right),
\end{equation}
where $\tilde{\mathbf{P}^k},\mathbf{P}^{*j}$ represent the canonical Naimark extension of $\tilde{\mathbf{N}}^k,\mathbf{N}^j$, respectively. With a slight abuse of notation, we also write $R\left(\rho\otimes\ketbra{0},\tilde{\mathbf{P}^k}\right)$ as $R\left(\rho,\tilde{\mathbf{N}^k}\right)$ for a general POVM $\tilde{\mathbf{N}^k}$. Therefore, the optimization in Eq.~\eqref{appeq:Rexdecomp} is equivalent to the following problem,
\begin{equation}\label{appEq:EquivOpt}
\begin{split}
R^{cf}(\rho,\mathbf{M}) &= \min_{\{\mathbf{N}^j,r_j\}} \sum_j r_j R(\rho, \mathbf{N}^{j}), \\
\textrm{s.t.} \quad   \mathbf{M}&=\sum_{j} r_j \mathbf{N}^j, \\
\mathbf{N}^j&\in \mathcal{P} ,\forall j, \\
r_j&\geq0,\forall j, \\
\sum_jr_j&=1,
\end{split}
\end{equation}
where $ \mathcal{P}$ is the set of POVMs.

To tackle the second problem that the dimension of $\{r_j\}$ is not fixed, we can apply Carath\'eodory's theorem for convex hulls. Suppose $\mathbf{M}$ is a POVM acting on a $d$-dimensional Hilbert space with $m$ elements. After considering the positive-semidefinite property and completeness, it can be parameterized by $(md^2-1)$ real parameters. Then, according to Carath\'eodory's theorem, the optimal value to Eq.~\eqref{appEq:EquivOpt} can be attained by a probability distribution $\{r_j\}$ with at most $md^2$ terms. Consequently, we can restrict the dimension of $\{r_j\}$ to be $md^2$ in Eq.~\eqref{appEq:EquivOpt} without loss of generality.

With the above results, the global optimum to Eq.~\eqref{appEq:EquivOpt} can now be efficiently solved numerically. In particular, for a fixed probability distribution $\{r_j\}$, the problem becomes a semi-definite programming optimization in the arguments $\{\textbf{N}^j\}$.
%For readers who are interested in performing the optimization in practice, we refer them to the approaches surveyed in Ref.~\cite{gorski2007biconvex}.
\end{appendix}

\end{document}