Polysemous codes

Introduction

Nearest neighbor search, or more generally similarity search, has received a sustained attention from different research communities in the last decades. The computer vision community has been especially active on this subject, which is of utmost importance when dealing with very large visual collections.

While early approximate nearest neighbor (ANN) methods were mainly optimising the trade-off between speed and accuracy, many recent works put memory requirements as a central criterion for several reasons. For instance, due to the memory hierarchy, using less memory means using faster memory: disks are slower than the main memory, the main memory is slower than CPU caches, etc. Accessing the memory may be the bottleneck of the search. Therefore algorithms using compact codes are likely to offer a better efficiency than those relying on full vectors. For these reasons, we focus on ANN search with compact codes, which are able to make search in vector sets comprising as much as one billion vectors on a single machine.

We distinguish two separate lines of research in ANN with compact codes. The first class of methods proposes to map the original vectors to the Hamming hypercube . The resulting bit-vectors are efficiently compared with the Hamming distance thanks to optimized low-level processor instructions such as xor and popcnt, available both on CPUs and GPUs. Another increasingly popular approach is to adopt a quantization point of view to achieve a better distance estimation for a given code size. While these two classes of approaches are often seen as contenders, they both have their advantages and drawbacks. Binary codes offer a faster elementary distance computation and do not need external meta-data once the codes are produced. In contrast, quantization-based approaches achieve better memory/accuracy operating points.

The polysemous codes introduced in this paper offer the best of both worlds. They can be compared either with binary codes, which is especially useful in a filtering step, or with the asymmetric distance estimator of product quantization approaches. The key aspect to attain this dual interpretation is the learning procedure. Our approach is inspired by works on channel-optimized vector quantization . We start by training a product quantizer . We then optimize the so-called index assignment of the centroids to binary codes. In other terms, we re-order the numeration of the centroids such that distances between similar centroids are small in the Hamming space, as illustrated in Figure 1.

As a result, our method is almost on par both with quantization-based methods in terms of accuracy and binary methods with respect to search efficiency. When combining this approach with a complementary approach such as the inverted multi-index , we outperform the state of the art by a large margin, as shown by our experiments carried out on several large public benchmarks. Interestingly, the high efficiency of our approach offers a scalable solution to the all-neighbor problem, i.e., to compute the k-NN graph, for the large image collection Flickr100M described by 4,096 dimensional vectors.

This paper is organized as follows. After briefly reviewing related works on ANN search with compact codes in Section 2, Section 3 describes the design of polysemous codes. The experiments analyzing our approach and comparing to the state-of-the-art are detailed in Section 4. Finally Section 5 illustrates our method on the task of constructing an image graph on a large scale.

Related work: ANN with compact codes

The literature on efficient search with compact codes is vast and we refer the reader to two recent surveys for extensive references on this subject. In this section, we present only a few popular approaches.

Locality-Sensitive hashing is a pioneering binary encoding technique. Charikar shows under some assumptions that the Hamming distance is statistically related to the cosine similarity (equivalently the Euclidean distance for normalized vectors). Brute-force comparison of binary hashes has been seen as a viable option for efficient image search with memory constraints , which was popularized by subsequent works evidencing the scalability of this approach to million-sized image collections . Additionally, Norouzi and Fleet have proposed an algorithm to speed-up the search in this Hamming space . Many variants have been subsequently proposed, such as spectral hashing or ITQ – see also for representative works. Related to our work, the k-means hashing method first produces a vector quantizer where the produced codes are compared with the Hamming distance.

Several works have primarily focused on optimizing the trade-off between memory and distance estimation. In particular, it is shown that vector quantizers satisfying the Lloyd conditions offer statistical guarantees on the square Euclidean distance estimator, which is bounded in expectation by the quantizer squared loss. These quantization-based methods include product quantization (PQ) and its optimized versions “optimized product quantization” and “Cartesian $k$-means” .

These approaches are effective for approximate search within large collections of visual descriptors. Subsequent works have pushed possible memory/efficiency trade-off by adopting a more general point of view, such as “Additive quantization” , which provides an excellent approximation and search performance, yet obtained with a much higher computational encoding cost . In between PQ and this general formulation, good trade-offs are achieved by residual quantizers , which are routinely used in the non-exhaustive PQ variant to reduce the quantization loss by encoding the residual error vector instead of the original vector, but also as a coding strategy on its own .

The aforementioned methods for ANN search limit the memory usage per indexed vector and provide a distance estimator that is faster to compute than the exact distance. However, the search is still exhaustive in the sense that the query is compared to all database elements. For billion-sized collections, reading the codes in memory is a severe constraint leading to search times in the order of a second, typically. The limitation imposed by this memory bottleneck has led to two-stage approaches , in which the feature space is first partitioned through hashing or clustering. Practically, an inverted list storing identifiers and corresponding compact codes is stored for each region. At query time, the distance is estimated only for the codes associated with a subset of regions . It is also possible to use multiple partitions as in early LSH papers, as done in joint inverted indexing . These solutions however require several indexing structures and are therefore not competitive in terms of memory usage. Various partitioning methods have been proposed for the coarse level . In particular, the inverted multi-index uses product quantization both to define the coarse level and for coding residual vectors. This strategy offers state-of-the-art performance when further combined with a re-ranking strategy based on codes .

The Hamming distance is significantly faster to evaluate than the distance estimator based on table look-ups involved in quantization methodsA recent method reduces the scanning by employing a lower-bounding look-up table stored in SIMD registers, however this method is efficient only on long inverted lists, which makes it sub-optimal in the usual setting.. From our measurements, the acceleration factor is typically between $4\times$ and $7\times$, depending on the code length. However, binary methods suffer limitations imposed by the Hamming space. First, the number of possible distances is at most $d$+1, where $d$ is the binary vector length. This problem is partially solved by asymmetric variants of LSH , whose estimations use compact codes for database vectors but not on the query side. Yet such asymmetric measures require look-ups, like the methods derived from product quantization, and are therefore more expensive to evaluate than the Hamming distance. On the other hand, quantization-based methods offer a better memory/accuracy compromise, which is expected since binarization is a particular case of quantization.

Binary and quantization-based codes have their own advantages and drawbacks. While the literature usually presents binary and quantized-based codes as concurrent methods, the next section introduces a method that benefits from the advantages of both classes of methods.

Polysemous codes

We, now, introduce our strategy to take advantage of the fast computation of Hamming distances while offering the estimation accuracy of quantization-based methods. The main idea is to learn a regular product quantizer , and then to optimize the assignment of centroid indexes to binary codes such that the Hamming distance approximates the inter-centroid distance. In this section, we first describe the objective functions optimized to achieve this property, and then describe the optimization algorithm.

Note that for a product quantizer, one typically optimizes separately each of the constituent sub-quantizers. Therefore, in what follows, we have one objective function (and optimization process) per sub-quantizer.

We consider two objective functions: one that minimizes a loss based on the distance estimator and one that minimizes a ranking loss.

One possible objective if to find the bijective map $\pi$ such that the distance $d(c_{i},c_{j})$ between two centroids is approximated by the Hamming distance $h(\pi(i),\pi(j))$ between the two corresponding binary codes:

where $\mu$ and $\sigma$ are measured empirically.

As, in the context of k-NN, it is more important to approximate small distances than large ones, we found out in practice that it is beneficial to weight the distances in the objective function (1). This leads to a weighted objective:

In the context of k-NN search, we are interested in finding a bijective map $\pi$ that preserves the ranking of codewords. For this purpose, we adopt an Information Retrieval perspective. Let $(i,j)$ be a pair of codewords such that $i$ is assumed to be a “query” and $j$ is assumed to be “relevant” to $i$. We will later discuss the choice of $(\mbox{query},\mbox{relevant})$ pairs. We take as negatives for query $i$ the codewords $k$ such that $d(c_{i},c_{j})<d(c_{i},c_{k})$. The loss for pair $(i,j)$ may be defined as:

A subsequent question is how to choose pairs $(i,j)$. One possibility would be to choose $j$ among the $k$-NNs of $i$, in which case we would optimize

An issue with this approach is that it requires choosing an arbitrary length $k$ for the NN list. An alternative is to consider all $j\neq i$ as being potentially “relevant” to $i$ but to downweight the contribution of those $j$’s which are further away from $i$. In such a case, we optimize

where we recall that $\alpha_{i}$ is a decreasing sequence and $r(i,j)$ is the rank of $j$ in the ordered list of neighbors to $i$:

In all our ranking experiments, we use Equation (6) and choose $\alpha_{i}=1/i$ (following ).

2 Optimization

The aforementioned objective functions aim at finding a bijective map $\pi$, or equivalently another numeration of the set of PQ centroids, that would assign similar binary codes to neighbouring centroids.

This problem is similar to that of channel optimized vector quantization , for which researchers have designed quantizers such that the corruption of a bit by the channel impacts the reconstruction as little as possible. This is a discrete optimisation problem that can not be relaxed, and for which we can only target a local minimum, as the set of possible bijective maps is huge. In the coding literature, such index assignment problems were first optimised in a greedy manner, for instance by using the binary switching algorithm . Starting from an initial index assignment, at each iteration, this algorithm tests all possible bit swaps (i.e., $d$), and keeps the one providing the best update of the objective function. As shown by Farvardin , this strategy rapidly gets trapped in a poor local minimum. To our knowledge, the best approach to index assignment problems is to employ simulated annealing to carry out the optimization. This choice was shown to be significantly better than previous greedy approaches. The algorithm aims at optimizing a loss $L(\pi)$ that depends on the bijective mapping $\pi$ defined as a table of size $2^{d}$. It proceeds as follows

$\pi^{\prime}:=\pi$, with entries $i$ and $j$ swapped

compute the cost update $\Delta C:=L(\pi^{\prime})-L(\pi)$

if $\Delta C<0$ or at random with probability $t$:

accept the new solution: $\pi:=\pi^{\prime}$

Figure 2 shows on a set of SIFT descriptors that our optimization is effective: the comparison of the codes used as binary vectors is much more correlated with the true distance after than before the optimization.

3 Discussion

Although the optimization algorithm is similar to those previously employed in channel-optimized vector quantization, our objective functions are significantly different to reflect our application scenario. In communications, it is unlikely that many bit errors occur simultaneously, in particular not on a memoryless channel. Therefore the objective functions employed in communication focus on small Hamming distances. In contrast, for ANN the typical Hamming distances of the neighbors are relatively large.

We point out that, while the proposed binarized PQ codes offer a competitive performance, their accuracy is significantly lower than that of PQ. This suggests a two-step strategy for large-scale search. Given a query, we first filter out the majority of the database items using the fast Hamming distance on the binarized PQ codes. We then evaluate the more costly asymmetric distances for the items whose Hamming distance was below a given threshold $\tau$.

Other strategies could be contemplated for the filtering stage. One such strategy is to measure how many quantization indexes differ for the product quantizerFormally, this quantity is also called Hamming distance, but measured between vector of indexes and not binary vectors.. In other terms, one can filter out vectors if more than a given number of sub-quantizers produce indexes not identical to those of the queries. As shown in the experimental section 4, this method is not as efficient nor precise as the strategy proposed in this section.

Another such strategy would be to use for the filtering stage a binary encoding technique unrelated to PQ, e.g., ITQ. The issue is that it would increase the memory requirements of the method as it would involve storing ITQ codes and PQ codes. In constrat, we only store one polysemous code per database item in the proposed approach – a must if the emphasis is on storage requirements.

Experiments

This section gives an analysis and evaluates our polysemous codes. After introducing the evaluation protocol, we analyze our core approach in different aspects. Then we show that our approach is compatible with the inverted multi-index (IMI) and give a comparison against the state of the art.

We analyze and evaluate our approach with standard benchmarks for ANN as well as a new benchmark that we introduce to evaluate the search quality.

is a benchmark of 128-dimensional SIFT descriptors . There are one million vectors in the database, plus 100,000 vectors for training and 10,000 query vectors. This is a relatively small set that we mainly use for parameter analysis.

is a large-scale benchmark widely used for ANN search, also made of SIFT descriptors. It comprises one billion database vectors, 100 million training vectors and 10,000 queries.

are introduced to evaluate the quality of the search with more challenging features. We leverage the Yahoo Flickr Creative Commons 100MOut of which only 95M are available for download today. image collection as follows. In FYCNN90M, we split the dataset into three sets: 90M vectors are to be indexed, 10k vectors serve as queries, 5M vectors are used for training. FYCNN1M uses the same training set and queries, but the indexed set is restricted to the first million images for the purpose of analyzing our method. We extract convolutional neural networks features following the guidelines of : we compute the activations of the 7th layer of AlexNet . This yields 4096-dimensional image descriptors. Prior to indexing we reduce these descriptors to 256D with PCA and subsequently apply a random rotation .

For all datasets, the accuracy is evaluated by recall@$R$. This metric measures the fraction of the queries for which the true nearest neighbor is returned within the top $R$ results. All reported times are on a single core of a 2.8GHz machine.

2 Analysis of Polysemous codes performance

We first analyze the performance of polysemous codes. Let us introduce notations. We first consider three ways of constructing a product quantizer:

is the baseline: we directly use the code produced by the product quantizer, without any optimization of the index assignment;

refers to a product quantizer whose index assignment is optimized by minimizing the distance estimator loss introduced in Section 3.1;

similarly refers to a PQ optimized with the proposed ranking loss.

Once the codebook and index assignment are learned, we consider the following methods to estimate distances based on polysemous codes:

is the regular comparison based on an asymmetric distance estimator ;

refers to the bitwise comparison with the Hamming distance when the codes are regarded as bitvectors, like for binary codes (e.g., ITQ);

counts how many sub-quantizers give different codes (see Section 3.3);

refers to the strategy employing both interpretations of polysemous codes: the Hamming codes are used to filter-out the database vectors whose distance to the query is above a threshold $\tau$. The indexed vectors satisfying this test are compared with the asymmetric distance estimator.

Note: Polysemous codes are primarily PQ codes. Therefore the performance of polysemous codes and regular PQ is identical when the comparison is independent from the index assignment, which is the case for ADC and disidx. For instance the combinations PolyD/ADC, PolyR/ADC and PQ/ADC are equivalent both in efficiency and accuracy.

Table 1 details the performance of the aforementioned PQ constructions. First, note that the accuracy of disidx is low, and that it is also relatively slow due to the lack of a dedicated machine instruction. Second, these results show that our index assignment optimization is very effective for improving the quality of the binary comparison. Without this optimization, the binary comparison is ineffective both to rank results (PQ/binary), and to filter (PQ/dual). The ranking loss PolyR is slightly inferior to PolyD, so we adopt the latter in the following.

Figure 3 confirms the relevance of PolyD/dual. It gives the performance achieved by this method for varying Hamming thresholds $\tau$, which parametrizes the trade-off between speed and accuracy. Polysemous codes allow us to make almost no compromise: attaining the quality of PQ/ADC only requires a minor sacrifice in search time compared to binary codes. With threshold $\tau=54$, 90–95% of the points are filtered out; for $\tau=42$ this raises to more than 99.5%.

Convergence: Figure 4 shows the performance of the binary filtering as a function of the number of iterations. The algorithm typically converges in a few hundred thousand iterations (1 iteration $=$ 1 test of possible index swaps). For a set of PQ subquantizer with 256 centroids each, this means a few seconds for the distance reconstruction loss PolyR and up to one hour for the ranking loss PolyR.

3 Comparison with the state of the art

As mentioned in the related work Section 2, for large datasets the best trade-offs between accuracy, search time and memory are obtained by hybrid methods that combine a preliminary space partitioning, typically implemented through clustering, with compact codes learned on residual vectors. That is why we combine our polysemous codes with IMI . This method partitions the space with a product quantizer (the “coarse” partitioning level) and uses PQ to encode residual error vectors. The search proceeds by selecting a few inverted lists at the coarse level, and then use the residual PQ codes to estimate distances for the vectors associated with the selected lists. We further optimize the computation of the lookup tables involved in PQ when multiple lists are probed , and use an optimized rotation before encoding with PQ .

Building upon this method, we learn polysemous codes for the residual PQ, which allows us to introduce an intermediate stage to filter out most of the list items, hence avoiding most of the distance estimation with PQ. Table 2 gives a comparison against state-of-the-art algorithms on the BIGANN dataset. We report both the timings reported for concurrent methods and our improved re-implementation of IMI. Note already that our system obtains very competitive results compared to the original IMI. Note, in the case where a single query vector is searched at a time, as opposed to batch mode, the coarse quantization becomes 50 to 60% more expensive. Therefore, in the following we use $K=4096^{2}$ to target more aggressive operating points by reducing the fixed cost of the coarse quantizer. In this case, the results of PolyD/dual gives a clear improvement compared to IMI$\star$ and the state of the art. In particular, with 16 bytes we are able to achieve a recall@1=0.217 in less than 1 ms on one core (0.38 ms in single query mode, 0.64 ms in batch mode). The binary filter divides by about 2$\times$ the search time, inducing only a small reduction of the Recall@1 score.

We now compare our method on the more challenging FYCNN90M benchmark, for which a single query amounts to searching an image in a collection containing 90 million images. Figure 5 reports the performance achieved by different methods. First observe that the non-exhaustive methods (bottom) are at least 2 orders of magnitude faster than the methods that compare the codes exhaustively (top), like ITQ. The former are able to find similar images in a few seconds. Again, our polysemous strategy IMI+PolyD/dual offers a competitive advantage over its competitor IMI. Our method is approximately $1.5\times$ faster for a negligible loss in accuracy.

Application: large-scale k-NN image graph

As an application to our fast indexing scheme, we now consider the problem of building the approximate k-NN graph of a very large image collection. For this experiment, we make use of the 95,063,295 images available in the Flickr 100M dataset. As was the case in Section 4, we use 4,096D AlexNet features reduced to 256D with PCA. For the graph construction, we simply compute the k-NN with $k$=100 for each image in turn. This takes 7h44 using 20 threads of a CPU server. Note that the collection that we consider is significantly larger than the ones considered in previous works on kNN graph. Moreover, our approach may be complementary with the method proposed by Dong et al. .

For visualization purposes, we seek the modes following a random walk technique : we first iteratively compute the stationary distribution of the walk, (i.e. the probability of each node to be visited during the random walk) and then consider as modes each local maximum of the stationary probability in the graph. We find on the order of 3,000 such maxima. Figure 6 depicts a sample of these maxima as well as their closest neighbors. We believe that these results are representative of the typical quality of the found neighbors, except that, for privacy reasons, we do not show the numerous modes corresponding to faces, of which we found many including specialized modes of “pairs of persons”, “clusters of more than two persons” or “baby faces”.

Conclusion

In this work, we introduced polysemous codes, i.e., codes that can be interpreted both as binary codes and as product quantization codes. These complementary views are exploited for very large-scale indexing in a simple two-stage process that first involves filtering-out the majority of irrelevant indexes using the fast Hamming distance on binary codes, and then re-ordering the short list of candidates using the more precise but also slower asymmetric distance on PQ codes. This yields a competitive indexing scheme that combines the best of both worlds: its speed is comparable to that of pure binary techniques and its accuracy matches that of PQ.

We are very grateful to Armand Joulin and Laurens van de Maaten for providing the Flicrk100M images and their CNN descriptors. Alexandre Sablayrolles had the idea of extending the OPQ method to reduce the number of dimensions.

Additional results

We present results obtained after the ECCV final version submission. We compare operating points with recent papers . The only addition to our method is to reduce the dimension of the descriptors before encoding it, within the OPQ transformation. The runtime parameters (multi-probe, Hamming threshold) are tuned automatically to optimize the tradeoff between speed and accuracty.

Table 3 compares with a recent hybrid CPU/GPU method , for a given accuracy. It shows that our implementation is slower with a single thread, but is much faster when all cores are used.

Deep1B is a 1-billion CNN vector dataset, introduced by Babenko et al . The vectors are reduced to 96 dimensions, otherwise the dataset statistics are the same as for SIFT1B. We compare against the method that was introduced along with the dataset, allowing 20-byte codes to have a similar memory usage. Table 3 shows that our method is about 5 times faster for a comparable accuracy.

References