Li 2021 - TaoBao Embedding-Based Retrieval

Li 2021 - Embedding Based Product Retrieval in TaoBao Search

This paper explains TaoBao's embedding-based search retrieval system. Some interesting aspects of this paper:

• Tackles the inherent trade-off between recall and relevance for embedding based retrieval
• Shows a way to incorporate personalization into search retrieval
• Ideas on enhancing representation of the search query

Context

TaoBao's product search has many stages. This paper focuses on the initial retrieval stage, when around 10k products are retrieved per query. The retrievers used are:

• Traditional lexical based term match retriever
• Item-based collaborative filtering retriever (presumably based on recent items)
• Embedding based retriever

The retrieval results from each retriever are merged and de-duplicated, and then sent to participate in the next phase (pre-ranking). This paper is only focused on the embedding-based retriever.

Problem

Taobao tackles several problems in this paper:

• Poor control of relevance for embedding based retrieval (EBR). Taobao reported that over time, the EBR contributed to an increase in complaints as non-relevant items started to get surfaced. For example, if a query is made for Nike Shoes, shoes from similar brands like Adidas may get surfaced.
• Balancing relevance and personalization. Taobao notes that personalization is an important aspect of product search, and they propose a way of merging search relevance and personalization in this paper.

Setup

Let $U=\{u_1,...,u_N\}$ denote a set of users, $Q=\{q_1,...,q_N\}$ denote their corresponding queries, and $I=\{i_1,...,i_M\}$ denote the collection of items. Let us divide the user $u$'s historical sequence of items into 3 buckets:

• Real time, i.e. most recent $T$ item interactions, denote as $R^u=\{i_1^u,...,i_T^u\}$
• Short term, i.e. within last 10 days but older than real time, denote as $S^u=\{i_1^u,...,i_T^u\}$
• Long term, i.e. within last 1 month but older than short term, denote as $L^u=\{i_1^u,...,i_T^u\}$

The search task is as follows. We are given the historical behaviours $(R^u,S^u,L^u)$ of a given user and the submitted query $q_u$ at time $t$. We also get access to a sequence of historical queries for the user $q_{his}=\{q_1^u,...,q_k^u\}$. Our task is to return a set of items $i\in I$ that satisfy the search request. Typically, we score each query, item pair according to score $z$ and return the top-K items: $$z=\mathcal{F}(\varphi (q_u,R^u,S^u,L^u),\psi (i))$$

Where:

• $\mathcal{F}$ denotes the scoring function, typically the inner product function
• $\varphi$ denotes the query + behaviour encoder
• $\psi$ denotes the item encoder

Model Architecture

The model architecture in the paper is quite complicated, although understandable after some time. I don't think it is profitable to describe the architecture in full specificity, but there are useful ideas within.

At a high level, the model architecture is a standard two-tower setup, where the user query and behaviours are encoded into a user embedding, and the item is encoded into an item embedding. The dot product is used to score user-item pairs and ANN search is used for retrieval. The interesting details lie mostly within the user tower, in particular the way the query and behaviours are integrated.

Query Representation

We first tackle the Query Representation. Given a query string, the query encoder encodes it into $Q_{mgs}\in {\mathbb{R}}^{6\times d}$, where $d$ is an arbitrary embedding dimension. The first dimension is 6 because the paper uses 6 different ways to encode the query (they call this multi-grained representation). The 6 representations are briefly explained as follows:

• 1-gram and 2-gram embeddings. The query string is tokenized into 1-gram or 2-gram and embeddings are looked up for each token. Mean pooling over tokens is done to get a single embedding.
• Phrase embeddings. Similarly, the query string is tokenized into phrases using their query segmentation engine. For example, 红色 is a phrase and 连衣裙 is a phrase. The same embedding lookup and mean-pooling is done. Call this $q_{seg}$ embedding.
• Phrase transformer embeddings. The phrase embeddings are also passed through a transformer before mean-pooling. I suppose the sequence of phrases matters enough to do this.
• Historical query embeddings. This is the interesting part where the query interacts with historical queries.
  • Specifically, the phrase embedding $q_{seg}\in {\mathbb{R}}^d$ and the historical query matrix $q_{his}\in {\mathbb{R}}^{k\times d}$ is used to form an attention matrix in the form of $\text{attn}=\text{softmax}(q_{seg}\cdot q_{his}^T)\in {\mathbb{R}}^{1\times k}$, which provides the relevance of each historical query to the current submitted query.
  • The attention weights are then used to do a weighted average over the historical query embeddings $q_{his\_seq}=\text{attn}\cdot q_{his}\in {\mathbb{R}}^d$.
  • Hence we get a weighted representation of historical queries where more relevant queries to the current query are emphasized.
• Mix embeddings. This is simply a sum over the above 5 embeddings

Note that in the query representation, both token-based embeddings and phrase-based embeddings are used to provide a fine grained representation of the query.

User Behaviour Representation

Now we tackle the representation of user behaviours. There are some minor deviations on how they treat $R^u,S^u,L^u$ respectively, but broadly they follow the same structure. We refer to $R^u$ below but similar treatment applies to $S^u$ or $L^u$.

• Each item in the sequence $R^u$ is represented by an embedding
• The item embedding comprises a concatenation of several embeddings, such as item ID embedding, item category embedding, brand embedding etc.
• $R^u\in {\mathbb{R}}^{T\times d}$ is passed into a transformer with self attention to get a hidden representation $R_{self\_attn}^u\in {\mathbb{R}}^{T\times d}$
• Similar to the treatment of historical query above, cross attention is performed with the query representation $q_{mgs}$ to get a query-weighted representation of $R^u$, as follows:
  • The attention matrix is formed by taking $\text{attn}=\text{softmax}(q_{mgs}\cdot (R_{self\_attn}^u{)}^T)\in {\mathbb{R}}^{6\times T}$, which provides the relevance of each historical interacted item to the current submitted query.
  • The attention weights are then used to do a weighted average over the historical item embeddings $H_R=\text{attn}\cdot R_{self\_attn}^u\in {\mathbb{R}}^{6\times d}$.
  • Hence we get a weighted representation of historical item interactions where more relevant items to the current query are emphasized.
• The same operations are applied to $S^u$ and $L^u$ to get $H_S$ and $H_L$ respectively.

Finally, the query $q_{mgs}$ and the representations of historical item interactions $H_R,H_S,H_L$ are passed into a self attention layer to get the final user representation, which captures both query semantics and historical information about the user: $$H_{qu}=\text{Transformer}([\text{[CLS]},q_{mgs},H_R,H_S,H_L])\in {\mathbb{R}}^{25\times d}$$

The embedding at the $\text{[CLS]}$ token is taken to represent the user. This has dimension $d$.

Item Representation

The item embedding is represented similarly to how each item was represented above. Mean pooling is done over the phrase segmentation of the item title, and added to the ID embedding of the item.

Loss Function

Now that we have described the model architecture, we proceed to training details. The authors used sampled softmax loss to train the model. The sampled softmax loss was compared against pairwise hinge loss and found to be superior. The hinge loss also has a downside of needing to tune the margin parameter, which can significantly affect results.

Specifically, for a given user representation $H_{qu}$ and item representation $H_i$ of item $i$. Let the predicted score for the match between user and item $i$ be denoted: $$\hat{y}(i|q,u)=\frac{\exp (\mathcal{F}(H_{qu},H_i)/\tau )}{{\sum }_{i^{\prime }\in I}\exp (\mathcal{F}(H_{qu},H_{i^{\prime }})/\tau )}$$

Where $\tau$ is the temperature parameter.

We can then denote the loss as the negative log likelihood of the positive interactions: $$\mathcal{L}=-\sum _{(q,u,i^{+})\in \mathcal{D}}\log \hat{y}(i^{+}|q,u)$$

Adjustments

The authors propose two adjustments to the training procedure to improve performance.

Firstly, they propose to use temperature $\tau$ to handle noisy relevance labels. They argue that the positive signals in e-commerce data from clicks and purchases are noisy, and will benefit from tuning the temperature. The argument is:

• As $\tau \to 0$, the softmax function approaches a one-hot function of the item with the highest score. Thus the model will be encouraged to fit the training signals exactly, which runs the risk of overfitting to noisy labels.
• Conversely, as $\tau \to \infty$, the softmax function approaches a uniform distribution over all items regardless of relevance. This encourages the model to underfit the training signals, since scoring positive items higher does not affect the loss by much.

Therefore, supposing the positive signals to be noisy, we should increase $\tau$ to accommodate the noise. The authors found that $\tau =3$ performed the best for their data.

Note: This approach advocates for more smoothing of the softmax distribution, which is opposite to the findings from papers like SimCSE, which advocate for less smoothing (or a very low $\tau =0.05$). I suppose the optimal temperature depends on how noisy the positive signals are relative to how noisy the negative signals are.

Secondly, they propose a unique way of mining hard negative samples. Firstly, they mine hard negatives from the random negatives as per normal by choosing the top $N$ negative items with the highest inner product with the user representation. Let this matrix be called $H_{hard}\in {\mathbb{R}}^{N\times d}$. Now, they linearly interpolate $H_{hard}$ with the positive item embedding $H_{i^{+}}$ as follows: $$H_{mix}=\alpha \cdot H_{i^{+}}+(1-\alpha )\cdot H_{hard}$$

This $H_{mix}$ is then used in the loss function as the negative item embeddings. In their experiment, they found that $\alpha$ between $0.4-0.6$ worked well.

Note: This approach seems to exacerbate the problem of false negatives, since we are using the positive item as part of the negative signal.

Finally, the authors propose a simple solution to the problem they raised of poor relevance matches surfaced by the EBR approach. The propose relevance control measure is to simply add a boolean term-based filter to the EBR results. For example, if the query is Red Nike Shoes, the boolean query will be something like Color:Red AND Brand:Nike AND Product:Shoes. The boolean filter will thus filter out any irrelevant results.

The paper does not elaborate much on how the query filter is implemented. Taobao decides on the key query terms to filter based on their understanding of what constitutes essential components of the query (i.e. brand name, color, style etc.).

Note: One may wonder what is the point of Embedding Based Retrieval (EBR) if we are going to slap a lexical boolean filter on it at the end. The answer is that Taobao is not using EBR as a way to achieve fuzzy semantic matching, as one might do when the lexical retrieval is too strict. Rather, it seems that due to the large number of items in Taobao's catalogue, the number of items passing the boolean filter already far exceeds the 10k limit. Thus they are using EBR as a way of surfacing the most relevant items within the subset of items that pass the boolean filter.

Results

Interestingly, Taobao evaluates the quality of the retrieval based on two metrics:

• Recall@1k: This is a typical measure of how many positive items were retrieved by the algorithm
• Relevant %: Taobao has an in-house relevance model that scores 0.915 AUC on human-annotated data on whether a query and product has good relevance match. Hence they use this model to determine if each query and retrieved product has good relevance, and reports the % of good relevance.

The findings of the paper are:

• The multi-grained representation of the query adds a small amount of recall
• Tuning temperature $\tau$ / using hard negatives adds significant amount of relevance
• Adding all the improvements raises relevance but decreases recall slightly, showing that there is some inherent trade-off between relevance and recall (i.e. some users do indeed engage with non-relevant items to their query)

It seems that Taobao prioritizes relevance over recall, which makes sense as surfacing irrelevant results undermines the integrity of the search system. Furthermore, since they use a boolean filter for relevance control, irrelevant results surfaced by the EBR system would get filtered out anyway.

Takeaways

This paper tackles an important problem for EBR systems where irrelevant results get surfaced sometimes. While a boolean filter might make sense for Taobao's use case, other systems might need a different approach to avoid being overly strict in relevance control. It is also insightful to understand the inherent trade-off between recall and relevance when training the model.

Finally, the paper also demonstrates a way to incorporate personalization into search via cross attention mechanisms between the query representation and the historical item interactions of the user.