End-to-End Retrieval in Continuous Space

Introduction

Nearly 30 years ago, Deerwester et al. Deerwester et al. (1990) described the shortcomings of the standard retrieval systems that are still widely used today: ”The problem is that users want to retrieve on the basis of conceptual content, and individual words provide unreliable evidence about the conceptual topic or meaning of a document.” As a solution, they introduced Latent Semantic Indexing, using Singular Value Decomposition over word co-occurrences to encode (or embed) a piece of text as a dense low-dimensional vector rather than a sparse high-dimensional vector of word indicators. This work opened the field of representation learning Bengio et al. (2013), but did not address the issue of efficient retrieval from the learned space. We’ll call the overall task – constructing dense representations and retrieving neighbors – continuous retrieval by way of contrast with discrete retrieval that uses an inverted index to leverage sparse representations. In principle, continuous retrieval has clear benefits: improved recall (unconstrained by specific word choice), more granular similarity scoring, learned relationships between query and candidates, and the possibility of retrieval across modalities.

However, models for learning text representations have found application in IR by re-ranking the top candidates proposed by a discrete retrieval system Huang et al. (2013); Shen et al. (2014); Palangi et al. (2016); Dos Santos et al. (2015); Lei et al. (2016). To the best of our knowledge, there have been no previous comparisons of end-to-end retrieval systems Onal et al. (2017). A model intended for re-ranking differs from a model intended for retrieval in two important ways. First, a re-ranking model has access to the raw representations of both query and candidate and can thus learn complex interactions Parikh et al. (2016); Gong et al. (2017), whereas a retrieval model must encode queries and candidates independently to allow for fast neighbor look-up. Second, re-rankers can focus modeling power on the boundary encoderscases proposed by the discrete retrieval systems, while retrieval models must also perform well with random pairs.

The primary goal of this paper is to show that using standard ANN search, simple models trained for the purpose of continuous retrieval can substantially outperform discrete retrieval systems. We show evidence for choosing a negative sampling method which we call in-batch sampled softmax, and evaluate a variety of baselines and trained models on two pairwise datasets that we modify for the purpose of retrieval evaluation.

Dual Encoders

Neural network models for learning distance functions date back to early work on signature verification Bromley et al. (1994), later extended to face verification Chopra et al. (2005). This work and its descendants (Yih et al., 2011; Hu et al., 2014, etc.) refer to the models as siamese networks because two similar objects are encoded by two copies of the same network (all parameters are shared). The Wsabie model Weston et al. (2010), intended for classification with large label sets, learns embeddings for the inputs and outputs separately. The StarSpace model Wu et al. (2017) extends the idea of learned embeddings to more data types. More generally, we refer to the class of models in which pairs of items are encoded in a shared space, as Dual Encoders. This is a modular architecture with the following components:

Encoder: An encoder is any learnable function $f(X)$ that takes an item $X$ as input and returns a $d$-dimensional real-valued encoding vector. Here, we focus on neural network functions $f$.

Similarity Function: A similarity function $sim(E_{1},E_{2})$ takes two encodings of the same dimension, and outputs a score in $$. Similarity functions can be arbitrarily complex, including neural networks that learn interactions between encodings, but to enable nearest neighbor search, we use cosine similarity, the standard for retrieval Manning et al. (2008).

Dual Encoder: A dual encoder has the form $g(X_{1},X_{2})=sim(f_{1}(X_{1}),f_{2}(X_{2}))$ where $f_{1},f_{2}$ are two possibly identical encoders. We additionally apply a learned affine transform, $\alpha g(\cdot,\cdot)+\beta$, which scales the similarity so it can be treated as a logit during training.

Note that while we train dual encoders for each pairwise dataset, including scaling parameters $\alpha,\beta$, retrieval requires only the individual trained encoders: the candidate items are encoded by the candidate encoder and indexed off-line; at inference time, the query is encoded by the query encoder and neighbors are retrieved from the candidate space according to cosine distance.

In our experiments, we train a very simple form of dual encoder for similar question retrieval. Much like the Paragram-Phrase setup Wieting et al. (2015), we use a single question encoder that represents the input with an average over word embeddings. Thus, the question encoder parameters are just the set of learned embeddings.

Some of our experiments use a multi-task setup, with up to 3 tasks. While there is a separate dual encoder for each task, they all share the same question encoder, so only the scaling parameters are task-specific. In multi-task training, we compute a task-specific loss, then take a weighted average to produce the overall loss; the weights are uniform in all experiments.

Much of the relevant prior work on representation learning has focused on pairwise similarity Hu et al. (2014); Wieting et al. (2015); Arora et al. (2017); Conneau et al. (2017), sometimes with the goal of re-ranking retrieval candidates.

If the training data consists of positive and negative example pairs, it is standard to minimize the logistic (cross-entropy) loss between true labels and model predictions.

But often, training data consists just of positive pairs. In the Word2Vec setting Mikolov et al. (2013) or in Language Model training Jozefowicz et al. (2016), the negative examples are implied: while there are a number of words that could reasonably fit with some context, a random word, on average, will be a poor substitute for the observed word. These models are trained with a softmax loss, where the negatives are all non-observed words in the vocabulary. For efficiency, the denominator can be approximated with a sample from the vocabulary. In the more general dual encoder case, though, the set of negative examples may not be enumerable. Indeed, if both inputs are sentences (or questions), negative sampling is a necessary approximation.

We consider a few different loss functions (in addition to the standard cross-entropy loss for binary-valued labels), each of which implies a different negative sampling strategy. All the strategies make use of items in the batch as a source of random negatives. A batch includes $B$ positive pairs of items which have been encoded by their respective encoders. We apply the similarity function to all pairs $(E_{1}^{i},E_{2}^{j})$ to form a similarity matrix $M$ where the diagonal contains positive examples and the off-diagonal contains random negative examples.

In-batch Cross-Entropy We form a cross-entropy loss term for each element in $M$, with positives on the diagonal and negatives on the off-diagonal, and return the average.

In-batch Sampled Softmax We form a softmax loss term for each row in $M$, where row $i$ has a positive label on column $i$ (corresponding to the diagonal), and return the average. This was suggested by Henderson et al. Henderson et al. (2017).

In-batch Triplet We form a triplet loss term for each row in $M$ that maximizes the margin between the positive element and the highest scoring negative element in the row: $\max(0,\delta-s^{+}+s^{-})$, where $\delta=0.5$. This is most similar to the loss used by Wieting et al. Wieting et al. (2015).

2 Training

We train all our models using mini-batch Gradient Descent with the Momentum optimizer and a fixed learning rate of $0.01$. Unless otherwise noted, the batch size is $1000$ and the loss is in-batch sampled softmax. We use a lowercased unigram vocabulary and 300-dimensional embeddings, initialized randomly. We use no explicit regularization (like dropout), but rely on early stopping (based on tuning set evaluation) to avoid over-fitting. In-batch precision@1 (accuracy computed over each row of the similarity matrix $M$), averaged over the rows in $M$, is our tuning metric, since this is a reasonable proxy for precision@1 computed over the full set of candidates, which in turn represents retrieval performance.

Experimental Setup

Neither pairwise similarity tasks nor re-ranking tasks are useful for evaluating end-to-end retrieval: the pairs of items are usually sourced using some heuristic or existing retrieval system. The resulting test data distribution is biased towards pairs selected by that system. Such test sets may fail to discriminate among models that have drastically different performance on random pairs, and it is particularly important that retrieval models be robust to all sorts of noisy candidates.

An offline retrieval task consists of (1) a set of test queries, (2) a set of candidate items (sufficiently large so as to be realistic), and (3) a set of (query, candidate) pairs labeled with relevance judgments. However, for any reasonable size candidate set, it’s infeasible to have all pairs annotated by a human. As a result, all retrieval tasks are necessarily incomplete: only a small subset of relevant candidates are labeled, so we assume that all unlabeled candidates are not relevant. This issue is discussed at length by Buckley and Voorhees Buckley and Voorhees (2004), who show that the Mean Average Precision (MAP) metric computed on an incomplete evaluation set correlates reasonably well with the MAP metric computed on a (significantly more) complete version of that evaluation set.

Computing full MAP on such a dataset can be computationally expensive (for each query, all candidates need to be scored). Instead, we only consider the top K results and compute MAP@K based on the following definition:

where $Q_{i}$ is the set of test queries, $R_{i}$ is the number of known relevant candidates for $Q_{i}$, $p_{i}^{j}$ is precision@j for $q_{i}$, and $r_{i}^{j}$ is 1 if the jth result is relevant to $q_{i}$, 0 otherwise.

2 Approximate nearest neighbor search

While the problem of nearest neighbor search Indyk and Motwani (1998); Gionis et al. (1999) is central to continuous retrieval, we’re glossing over it here for two reasons. First, a simple quantization method Guo et al. (2016) works quite well for the tasks we consider; second, since we are more interested in analyzing modeling issues, we use exhaustive search to avoid any confounding effects linked to the choice of approximate search algorithm. Moreover, we found that approximate search is nearly as accurate as exhaustive search in our retrieval tasks: MAP@100 for approximate search declined no more than 0.4% even as we increased the candidate set size from 20k up to 1M.

3 Constructing retrieval tasks

We use a simple approach to turn a conventional similarity scoring or ranking task into an incomplete retrieval task. Given a test set with labeled pairs, we first build the graph induced by positive pairs. Next, we compute the transitive closure of the graph, which may yield additional positive pairs. Now, each element of a positive pair is considered a test query, and its neighbors in the transitive closure graph are the known positive results for that query. Finally, the set of candidates consists of all items found in the test set (either in a positive or a negative pair).

We apply this method to the Quora question pairs datasethttps://data.quora.com/First-Quora-Dataset-Release-Question-Pairs and the AskUbuntu datasethttps://github.com/taolei87/askubuntu Dos Santos et al. (2015); Lei et al. (2016) to produce new retrieval evaluation sets. We use only the question titles in the AskUbuntu data, and leave the more complex problem of modeling (often much longer) question bodies to future work. In our experiments, we apply our trained encoder models to all pairs of (query, candidate) and evaluate MAP@100 on the resulting scores. While this means that our results are not comparable to previous reported work using these pairwise datasets, we provide results from a variety of baseline systems.

The AskUbuntu training set includes just positive pairs, so negative sampling is required. However, the Quora training set includes positive and negative examples (in roughly a 2:1 ratio). This allows us to compare standard cross-entropy loss with our negative sampling strategies.

Since we are interested in a training setting where a single model works well for both tasks, we also experiment with the Paralex datasethttp://knowitall.cs.washington.edu/paralex, 18 million question-paraphrase pairs scraped from WikiAnswers.

4 Baselines

To facilitate meaningful comparison, we start with a few common baselines. First, because each candidate set includes all the test queries, an ”identity” baseline simply retrieves the exact test query as the only matched candidate. Second, we use TFIDF and the BM25 algorithm Robertson et al. (2009) for discrete retrieval, standard baselines for retrieval comparisons Hoogeveen et al. (2015).

We also compare a variety of averaged word embeddings baselines, starting with uniform averaging of 300-dimensional pretrained word2vec embeddings. Next, following Arora et al. Arora et al. (2017), we take a weighted average of pretrained embeddings using Inverse Document Frequency (IDF)We found no advantage by using the SIF weighting or PCA subtraction proposed by Arora et al., and try 3 different settings for pre-training: standard word2vec, word2vec trained with the Paralex dataset (closer to the question domain), and Glove Pennington et al. (2014) trained from Web (Common Crawl) data. We also try embedding each question using a 300-dimensional Skip-Thought model Kiros et al. (2015).

Note that in all cases, the score for a query-candidate pair is computed using cosine distance between the respective encodings.

Analysis of Results

Table 2 shows MAP@100 results on the Quora and AskUbuntu retrieval tasks. First, we observe that while IDF-weighting the pretrained embeddings is useful, this is still not clearly better than the BM25 baseline. We show this is not a domain issue by training word2vec directly with Paralex data. However, the dual encoder trained with Paralex data is significantly better, and now improves on BM25 on both evaluations. Next, we are able to improve results quite a bit more by using in-domain training data. And finally, we get the best overall results by training a single multi-task dual encoder that combines data from all three tasks (note that we train the Paralex-only dual encoder to convergence before adding the multi-task loss).

In Section 2.1, we enumerated a number of loss functions using different negative sampling strategies. Most importantly, we found that training a Quora-only model with standard cross-entropy (using the provided positive and negative training examples) was substantially worse than training with any of the negative sampling strategies: 88.3 vs. 90.4 MAP@100. Among sampling strategies, in-batch sampled softmax loss gave the best retrieval results and converged much faster than in-batch cross-entropy, though in-batch triplet loss was fairly similar.

Given that we are using the batch as a source for random negatives, the batch size becomes important. In fact, we found that the larger the batch, the better the retrieval results. Batches of size 2, 10, 100, and 1000 resulted in 82.8, 87.9, 89.2, and 90.4 MAP@100 on Quora.

Conclusion

In this work, we distinguished between pairwise scoring tasks (including re-ranking) and retrieval tasks. We described a general dual encoder abstraction for training arbitrary complex distance functions, and a specific simple setting with negative sampling that improves substantially over standard retrieval baselines.

Our results begin to show that end-to-end retrieval is a viable alternative to discrete retrieval. Future work will include:

Extending these experiments to larger tasks, with many more retrieval candidates.

Adding a scoring or re-ranking model after retrieval to show overall improvements to existing systems.

Exploiting the Dual Encoder framework presented here to handle multiple data modalities.

References