Robust Iterative Quantization for Efficient ℓp-norm Similarity Search

1 Introduction

Similarity search is of great importance to applications in various areas, such as data mining [Altman, 1992], machine learning [Cheng et al., 2015], information retrieval [Furnas et al., 1988], and etc. Formally, given a database D = ¶x1↪ ▷▷▷↪ xn♦, similarity search is to find those instances that most closely resemble a query xq based on a similarity or distance measure d(xq↪ xi), e.g., Euclidean distance. The small-database case is well solved, however, the cost of computing the distance between the query and all database instances becomes prohibitively high in the case that the reference database is huge. To address this problem, hashing based methods [Gionis et al., 1999; Andoni and Indyk, 2006] are proposed, which transform the data from a real-value representation into a sequence of binary bits. The binary representation and those bit-wise operations make computing the Hamming distance between binary codes extremely efficient in a modern CPU architecture [He et al., 2013], therefore enabling a fast nearest neighbor search. Such a procedure can be considered as a means for transforming high-dimensional feature vectors to a low-dimensional Hamming space, while retaining the original similarity structure of data as much as possible. In this way, the original distance d(xq↪ xi), thanks to the similarity preservation, can be effectively approximated by the Hamming distance dh(bq↪ bi) between binary codes.

⇤Corresponding author: Guiguang Ding. This research was supported by the National Natural Science Foundation of China (Grant No.61271394 and 61571269), the National Basic Research Project of China (Grant No. 2015CB352300), and the Royal Society Newton Mobility Grant (IE150997).

Locality Sensitive Hashing (LSH) [Gionis et al., 1999], as the seminal work, adopts random split to generate binary codes. Although enjoying asymptotic theoretical benefits, LSH needs long codes for a good performance because of its data-independent [Zhang et al., 2010] property. To obtain compact binary codes, many machine learning techniques are exploited [Wang et al., 2014]. Among all, Iterative Quantization (ITQ) [Gong et al., 2013] that aims to minimize the distortion between binary codes and the original features, has shown the state-of-the-art performance for learning `2-norm similarity-preserving binary codes, and thus ITQ has been utilized in information retrieval, image classification, and etc.

1.1 Problem Statement

The extraordinary performance and a large number of the follow-up works [Ge et al., 2014; Zhang et al., 2014; Kong and Li, 2012; Xu et al., 2013] motivate us to closely investigate the ITQ algorithm. Specifically, the objective of ITQ is to learn the binary representation and an orthogonal rotation matrix R 2 Rk⇥k which minimizes the distortion as follows,

where bi 2 ¶-1↪ 1♦k is the binary representation of xi, k is the length of binary codes and I is the identity matrix. Without loss of generality, hereafter we assume the data is zerocentered, i.e., Pi xi = 0. A close look at the objective function reveals that a squared `2 loss is applied to measure the distortion. But unfortunately, this sort of distance measurement comes with certain vulnerabilities. For instance, there

are noise and outliers in real-world datasets but the squared loss is sensitive to them because their large distortion may dominate the sum of the squared loss [Huang et al., 2013; Pan et al., 2014; Jiang et al., 2015], which may markedly degrade the quality of binary codes. Solving this problem becomes important when we need to search nearest neighbors for data in the wild, such as Flickr images and Youtube videos, as the noises are commonly existed. To verify our observation, we carried out an experiment based on SIFT1M dataset, in which the noise is manually added into the data and we plot the similarity search performance of ITQ w.r.t. the noise ratio. As can be seen from Figure 1(a), the performance of ITQ degrades significantly even with only 1% of noise. Additionally, ITQ works pretty well for `2-norm similarity search, i.e., d(xq↪ xi) = kxq - xik2 but not for the other measurements like a Manhattan distance d(xq↪ xi) = kxq -xik1 [Singh and Jain, 2010]. In practice, the preferred measure means may need to be defined by users depending on the application. This indicates that a good similarity search algorithm should be generic enough to deal with different distance measurements. Again, to demonstrate this, we plot the `1-norm distortion w.r.t. the number of iterations of ITQ, as shown in Figure 1(b). It can be observed that the distortion keeps increasing with more iterations. This phenomenon reveals that the distance approximation gets worse such that more iterations might result in worse similarity search result.

1.2 Our Contributions

Aiming to address the two problems mentioned above, we intend to develop an improved ITQ algorithm, in which both robustness and generalization are enhanced by using a `pnorm distance. Recent studies have shown that the q-th order (q < 2, especially q  1) of `2 loss, i.e., kbi - xiRkq2 , is more robust to the noise and outliers in data than the squared loss [Wright et al., 2009; Wang et al., 2013]. Based on the triangle inequality, preserving `p-norm distance can be achieved by minimizing the `p-norm distortion, i.e., kbi - xiRkp. Therefore, in this paper, we propose a `p↪q-norm loss function for learning robust `p-norm similarity-preserving binary codes, termed as ITQ+. In Figure 1, we exhibit the effectiveness of ITQ+, in contrast to the original ITQ algorithm. In summary, the major contributions of this paper are two folds.

• ÷ We propose a new `p↪q-norm loss for binary-code learning. It is robust to noise by using a small q and supports `p-norm (p  2) similarity search with the `p-norm loss.
• ÷ To minimize the orthogonality constrained `p↪q-norm function, a novel and efficient iterative optimization algorithm is proposed and its convergence property is theoretically investigated. To the best of our knowledge, it is the first work that provides the theoretical solution to this challenging non-smooth and non-convex problem.

In addition, it is worthwhile to highlight two important properties of the ITQ+ algorithm from the application perspective.

• ÷ ITQ+ is resistant to the noise, enabling us to search similarity in wild data. Such an algorithm is favorably demanded by the applications like Internet image retrieval.
• ÷ Our algorithm is more generic in the sense that multiple distortion measurements are implemented in one framework, allowing us to facilitate a wide range of applications in which different measurements may be requested.

2 The ProposedMethod

2.1 Objective Function

As we mentioned before, the algorithm can be enhanced if we make the squared loss less sensitive to the noise. In this paper, we adopt a widely used method that replaces the squared loss by the the q-th order loss. It has been shown in the literatures [Wright et al., 2009; Huang et al., 2013; Wang et al., 2013] that the loss function is more robust to noise and outliers in data in case of q < 2, especially q  1. Inspired by the idea, we reformulate the objective function of ITQ in Eq. (1) from the squared loss to the q-th order loss as

Denote Q(x) as the quantization result of x. Based on the vector norm property, we obtain two inequalities as follows,

where kxkp = (Pj ♣xj♣p ) 1p denotes the `p norm of a vector. The above inequalities are based on the triangle inequality. From these inequalities, we can observe that with smaller distortion (kx-Q(x)kp), the distance between Q(x) and Q(y) can accurately approximate the distance between x and y [Ge et al., 2014; Zhang et al., 2014]. Furthermore, in the extreme situation where the distortion is 0, we have kQ(x) -Q(y)kp = kx-ykp. Fortunately, the binary codes used in the hashing algorithm are exactly the quantization result of original features. Therefore, to learn `p-norm similarity-preserving binary codes, we need to minimize the `p-norm distortion. Here, ITQ can be considered as a special case (p = 2) of our scheme . To clarify it, we can rewrite the objective function in Eq. (2) from the `2-norm loss to the `p-norm loss, which leads to the objective function of ITQ+:

2.2 Learning Algorithm

Changing to a `p↪q-norm loss is not difficult, but minimizing obtained orthogonality constrained `p↪q-norm is non-trivial since it becomes a non-smooth and non-convex optimization problem when p  1 or q  1. Solving this problem is much more difficult than minimizing the `2↪2-norm in ITQ, for which many solutions are available [Gong et al., 2013]. To solve our problem, we propose an efficient iterative optimization algorithm, which can be decomposed into two parts:

Fix R and update bi. Similar to ITQ, the problem that arises in Eq. (3) can be optimized w.r.t. every element in bi individually, which reduces the optimization problem below

The solution for the above problem can be written as follows:

Here, sign(x) = 1 if x ≥ 0 or -1 otherwise. It is an explicit hashing function for the out-of-sample data 1 . Hence, given a new data x, we can adopt Eq. (5) to generate its binary codes.

Fix bi and update R. This is the most difficult part in the entire solution, because the `p↪q norm is neither smooth nor convex, and meanwhile, the orthogonality constraint limits the feasible set. To solve it, we rewrite the complicated `p↪qnorm problem into a weighted `2↪2-norm problem as below,

where X = [x1; ▷▷▷; xn] are the original training features, B = [b1; ▷▷▷; bn] are the binary codes. W = [w1; ▷▷▷;wn] is the weighting matrix, k · kF is the Frobenius norm of matrix, and "◦" represents the element-wise multiplication operation. In our algorithm, the weighting matrix is defined as follows

Based on the above definitions, it is easy to verify that Eq. (6) is equivalent to Eq. (3). Now, if we fix W, solving the weighted `2↪2-norm problem is much easier than the original problem since it is a smooth and convex function. The only challenge left in this problem is to solve the orthogonality constraint. To address this issue, in this paper, we adopt the optimization algorithm proposed in [Wen and Yin, 2013], which starts by computing the gradient of O w.r.t. R as below

Next, we construct a skew-symmetric matrix based on G as

Having obtained G, the next step is to search the sequential point using the Crank-Nicolson-like scheme [Goldfarb et al., 2009; Vese and Osher, 2002], which is described as follows

where ⌧ is the step size. The solution to Eq. (10) is given by

1 The out-of-sample data is the one that is not in the training set.

Algorithm 1 Learning ITQ+

Input: Centered training data X;

Parameters p  2 and q  p;

Output: Orthogonal matrix R;

• 1: Initialize R= I, and B= sign(XR);
• 2: repeat
• 3: Update bij with Eq. (5);
• 4: Construct weighting matrixWby Eq. (7);
• 5: Update Rwith Eq. (8)(9)(11);
• 6: until Convergence.
• 7: Return R;

The objective function value in Eq. (6) will keep decreasing w.r.t. the updating rule in Eq. (11) until the stationary point is achieved. Note that Rt+1 satisfies the orthogonal constraint (detailed proof can be found in [Wen and Yin, 2013]). We update R by fixing W as we can see that W depends on R. Therefore, the updates of R and W can be implemented by an iterative strategy, which can be described in Algorithm 1.

2.3 Convergence Analysis

In this subsection, we will prove that the objective function value in Eq. (3) is non-increasing at each iteration of Algorithm 1, and is guaranteed to converge at the local optimum.

First, let us make it clear that OITQ+ is obviously nonincreasing w.r.t. the updating rule for bij in Eq. (5) because it is the global optimum given R. Now, we need to prove that OITQ+ is non-increasing under the updating rule in Eq. (11).

Proof 1 Denote c = b◁a and f(x) = xc -cx+c-1. Apparently, f(1) = 0. Then, we have f 0 (x) = cxc-1 - c ,leading to f 0 (1) = 0. In addition, f 00 (x) = c(c - 1)xc-2  0 when x ≥ 0 because 0 < c  1. This implies f 0 (x) ≥ 0 8x 2 [0↪ 1] and f 0 (x)  0 when x > 1. Therefore, f(x)  f(1) = 0. Finally, we can obtain af (xa ) = axb - bxa + b - a  0.⇤

Lemma 1 1 Given any a > 0 and 0 < b  a, for 8x ≥ 0, we have the inequality: axb - bxa + b - a  0.

Theorem 1 The objective function OITQ+ is non-increasing under the updating rule for R in Eq. (11).

Proof 2 Let Y = B-XRt, Z = B-XRt+1, we have

Based on the proof in [Wen and Yin, 2013], we know that Eq. (11) can decrease the value of O in Eq. (6), i.e., we have

Now if we set a = 2, b = p, x will be ♣zij♣◁♣yij♣. Based on the Lemma 1 above, we can obtain the following inequalities

Combining inequalities (13) with (14) will bring us

Denote a = p, b = q, and x = kzikp◁kyikp, then we get

Again, if we combine inequalities (15) with (16), we obtain

which ends the proof to Theorem 1. ⇤

We have the following inequalities with the above proofs: OITQ+(Bt↪ Rt) ≥ OITQ+(Bt+1↪ Rt) ≥ OITQ+(Bt+1↪ Rt+1) which states that OITQ+ is non-increasing with Algorithm 1.

3 Experiment

3.1 Datasets andMetrics

To demonstrate the effectiveness of ITQ+, we carried out comprehensive experiments for similarity search. In this paper, we adopt two widely used benchmark datasets. The first one is SIFT1M [J´egou et al., 2011] which consists of 128dimensional SIFT [Lowe, 2004] descriptors. It is made up of 1 million base vectors, 10↪ 000 query vectors and 100↪ 000 vectors for training. The second dataset is GIST1M [J´egou et al., 2011] which contains 960-dimensional GIST [Oliva and Torralba, 2001] descriptors. This dataset contains 1 million base vectors, 1↪ 000 query vectors and 500↪ 000 for learning.

Following the settings in [Gong et al., 2013; He et al., 2013], we use Recall@R as the metric to evaluate the similarity search performance, which reflects the ratio between the number of the true positives in the first R retrieved points based on Hamming ranking and the total number of true positives. More precisely, the true positives for each query are the 10 nearest neighbors of the query in the base by running a brute-force linear scan measured by the `p-norm distance.

In addition, following the setting in [Jegou et al., 2010; Gong et al., 2013], we first centralize the data and perform a PCA to reduce the feature dimensionality to the length of binary codes. Afterwards, the rotation matrix R is learned from the reduced data. The binary codes are generated by a sign function after rotation. In addition, we repeat each experiment for 50 times and the average performance is reported.

3.2 Robustness Study

We firstly investigate the robustness of ITQ+ against the noise and outliers. To better investigate this property, we have manually added some noise to the data, where each dimension of each noisy point is sampled randomly from 100 ⇥ N(0↪ 1). This also implies that the distribution of noise is not as same as that of the original data. To understand the boundary of the algorithm, we continuously change the noise ratio (NR: the ratio between noisy points and original points), and evaluate the `2-norm similarity search performance of different methods. For ITQ+, we consistently set q = 1 when comparing to ITQ. The results of ITQ+ and ITQ on two datasets with different binary code lengths are shown in Figure 2. It can be observed that our ITQ+ is overwhelmingly better than ITQ at all the situations in terms of the Recall. On average, we have improved the recall of the original ITQ by 12▷2% when NR = 5%. It is worthwhile to point out that the results actually demonstrate the following properties of our algorithm.

ITQ+ performs observably better than ITQ even when applying to the original data (no manual noise; NR = 0). The major reason is that the data are from the real-world dataset, on which the noises and outliers have existed. Therefore, it turns out that noisy data and outliers in the real-world dataset are indeed influential in the performance of ITQ because their large errors may dominate the total distortion due to the squared loss. In contrast, in ITQ+, we adopt the q-th (q < 2) order loss function that can effectively suppress the effect of noisy data and outliers as the learned parameters can better capture the intrinsic information in the dataset. In other words, our ITQ+ is better suited to deal with data in the wild.

When NR gets increased, the similarity search performance of ITQ degrades rapidly. This phenomenon once again demonstrates that ITQ is sensitive to noise and outliers in data because of the squared loss, as we have mentioned before. On the contrary, ITQ+ shows very stable performance in most cases when we increase NR. More importantly, it can be seen that the performance gap between ITQ+ and ITQ becomes even larger when increasing NR. This again demonstrates the superior robustness of the proposed ITQ+ against the noise.

3.3 Effect of Parameter q

There is one important parameter q in ITQ+. Here, we investigate how the algorithm will behave when varying q. To do so, we change the value of q and plot the corresponding performance of ITQ+ on both datasets with different binary code lengths and noise ratios. The results are illustrated in Figure 3. It is noticed that ITQ is a special case of ITQ+ when q = 2. We can get the following observations based on the results.

Firstly, in all settings, we can find a Bell-shape curve for ITQ+. Basically, the model is affected by both noise and normal data. With a large q (say, q > 1▷5), ITQ+ will increase the weight of those large-distortion entries such that the model will be biased by them. Unfortunately, due to the existence of noisy entries and their large distortions, the learned model will deviate significantly to fit the outliers from the one which best suits to the normal data. Therefore, the performance of ITQ+ degrades significantly when we increases q from 1.5 to 2, especially in more noisy settings, e.g., NR = 5%. On the other hand, if q is too small (say,q < 0▷5), we cannot obtain good results either. According to the principle, the difference between normal and noisy data becomes smaller in this case, though the effect of outliers is suppressed. In the extreme case where q = 0, every entry has the same distortion 1 such that any model is the solution for this case. Thus, it is almost impossible to find the optimal model for normal data. This interprets why ITQ+ performs worse when we decrease q from 0.5 to 0.25, especially when there is less noise, e.g., NR = 0. In Figure 3, we can see that ITQ+ performs stably good when q 2 [0▷75↪ 1▷25] where the outliers affect ITQ+ much less and that a model which can well fit to the normal data is learned.

Secondly, we can observe that the performance-vs-q curve behaves differently at different noise levels. Specifically, given a small NR, e.g., NR = 0, ITQ+ seems more sensitive to q when q < 1, because the the performance changes dramatically when varying q in this range. On the other hand, given a large NR, e.g., NR = 5%, ITQ+ becomes more sensitive when q > 1. The reason is analogous to our analysis in the last paragraph. When there is little noise, the primary target of ITQ+ is to fit the normal data. In this case, the performance may degrade rapidly if q is too small. On the other hand, as a result of the increasing noise, the primary target of ITQ+ becomes to suppress the influence of noise. Thus, increasing the value of q when q > 1 leads to much worse

1(b), the learning algorithm of ITQ may unavoidably lead to larger distortion with more iterations since it adopts `2 loss.

3.5 Convergence Study

We have theoretically proved that Algorithm 1 leads to nonincreasing objective value. Now, we empirically investigate its convergence property by conducting the experiment on SIFT1M with 64 bits. Because Algorithm 1 is designed for the general `p↪q-norm loss, we assign different values to p and q. The objective function value in Eq. (3) w.r.t. the number of iterations with different settings are plotted in Figure 5. As can be seen, the objective value decreases steadily with more iterations and can achieve a nearly stable value within less than 50 iterations, which validates the effectiveness of Algorithm 1. For a fair comparison, we terminate the algorithm after 50 iterations in all experiments as suggested by ITQ.

4 Conclusion

In this paper, we have presented an enhanced ITQ algorithm, termed ITQ+, which changes the `2↪2-norm loss to a more

performance.

3.4 `p-norm Similarity Search

In this subsection, we will demonstrate the effectiveness of ITQ+ for `p-norm similarity search. For ITQ+, we can set the parameter p depending on the specific task and we set q = 1.

We consider the `2-norm (Euclidean distance), `1▷5-norm and `1-norm (Manhattan distance) similarity search because of the space limitation. The recall curves of ITQ+ and ITQ on both datasets with different code lengths for three tasks are plotted in Figure 4, respectively. Here, we use `2-norm as the reference as ITQ is designed for this task. We can observe that ITQ+ has stable performance on different tasks whereas ITQ performs much worse on other two tasks than on `2-norm task. For example, the Recall@1000 of ITQ drops from 0▷651 for `2-norm to 0▷474 for `1-norm on SIFT1M with 64 bits. Consequently, the performance gap between ITQ+ and ITQ becomes much larger when we change p from 2 to 1▷5 and 1. This result demonstrates that ITQ+ can well support the `p-norm similarity search but ITQ cannot handle the tasks excluding `2-norm search. In fact, as we have shown in Figure general `p↪q-norm loss. The benefits are twofold. On the one hand, the algorithm becomes more robust to the noise, which potentially makes ITQ+ better suited to search similarity in the real-world data. On the other hand, promoting to `p↪qnorm loss allows ITQ+ to handle various applications, where different distance measurements are requested. The major technical challenge comes from minimizing the new `p↪q- loss function, which is a non-smooth and non-convex optimization problem. To solve this orthogonality constrained `p↪qnorm minimization problem, we propose an efficient algorithm and rigorously prove its convergence. Comprehensive experiments on two benchmarks show that ITQ+ performs significantly better than ITQ, and demonstrate that ITQ+ is robust to noise and works well for `p-norm similarity search.