Quantized Correlation Hashing for Fast Cross-Modal Search

1 Introduction

Multi-modal data becomes more and more popular in our daily life. For instance, on webpages, objects are often described with images or videos surrounded by text. With the interests on searching multi-modal data (e.g. using images to query texts), cross-modal retrieval becomes an emergent issue. A lot of works have been done in this field [Li et al., 2003a; Rasiwasia et al., 2010; Gong et al., 2014; Hwang and Grauman, 2012; Sharma et al., 2012]. Recent efforts focus on studying efficient search methodologies over large databases. Inspired by the fast search based on hashing algorithms [Datar et al., 2004; Weiss et al., 2009; Wang et al., 2010; Liu et al., 2012; Norouzi and Blei, 2011], which have witnessed great success in single-modal search, cross-modal hashing[Masci et al., 2013; Bronstein et al.,

∗Corresponding Author

2010; Zhang and Li, 2014; Zhou et al., 2014; Zhen and Yeung, 2012a] or cross-view hashing[Kim and Choi, 2013; Quadrianto and Lampert, 2011; Song et al., 2013; Zhai et al., 2013; Zhang et al., 2011; Zhou et al., 2014] have been attracting a lot.

Most cross-modal hashing methods are similarity based (for example, Cross Modality Similarity Sensitive Hashing(CMSSH) [Bronstein et al., 2010] and Semantic Correlation Maximization(SCM) [Zhang and Li, 2014]) or distancebased (e.g. Cross View Hashing(CVH) [Kumar and Udupa, 2011] and Co-Regularized Hashing(CRH) [Zhen and Yeung, 2012a]). The objective of these methods is to purse "meaningful" hash codes of data points across domains, i.e., the distance between two codes - in the mapped hashing spaces - should be close if the respective data points are from the same class, and it should be far otherwise. Parametric Local Multimodal Hashing(PLMH) [Zhai et al., 2013] further constrains the learned hashing functions so that they can locally adapt to the data structure of each modality, and Sparse Multi Modal Hashing(SM2H) [Wu et al., 2014] preserves both data similarity based on joint multi-modal dictionary learning constrained by Hypergraph Laplacian sparse coding. Multimodal Latent Binary Embedding(MLBE) [Zhen and Yeung, 2012b] derives a probabilistic model to learn cross-modal binary hash codes.

In this work, we propose a new cross-modal hashing method. We take both hashing function learning and quantization of hash codes into consideration. This is inspired by the significance of quantization in single-modal hashing algorithms (e.g. ITQ [Gong and Lazebnik, 2011]). However, the effect of hash code quantization is less studied in crossmodal hashing literature. In conventional cross-modal hashing methods, the quantization of hash codes is realized independent of learning the correlation across domains. The separation of the two processes usually results in a sub-optimal solution. In this work, we propose a joint learning schema that consolidates the minimization of quantization loss and maximization of domain correlation into a single objective function so that optimal cross-modal hash codes are derived. In this way, we can simultaneously optimize the quantizer along with binary code learning, so that the quantizer is more fit to the cross-modality data search. To the best of our knowledge, it is the first attempt to integrate hash function learning with quantization together for cross-modal hashing. We call the proposed cross-modal hashing algorithm as Quantized Correlation Hashing (QCH). Compared to existing works, the novelty of our work includes:

• A new cross-modal hashing model is optimized simultaneously on both hashing code learning and binary quantization;
• The proposed multi-modality objective function is transformed to a single-modality formalization, leading to an easier optimization procedure.

In the rest part of the paper, we present the details of the proposed method in Sec. 2 and extensive evaluation on three public datasets in Sec. 3. Finally, we conclude the paper in Sec. 4.

2 Quantized Correlation Hashing

In this section, we will present our QCH in details and use two-modalities for example introduction. Our method would be easily extended to the case for more than two modalities. In addition, our hashing model can be applied to deal with multi-view data as well, which will be tested in Section 3.

Assume that there are n objects represented by two modalities (xi, yi), where xTi is the ith row of data matrix X ∈ Rn×dx of the first modality and yT i is the ith row of data matrix Y ∈ Rn×dy of the second modality. dx and dy are the dimensions of the two modalities. We assume all data are zero-centered which is usually adopted in existing hashing algorithms [Wang et al., 2010; Zhang and Li, 2014], i.e., ∑ni=1 xi = 0 and ∑nj=1 yj = 0. In addition, the similarity information between data points across domains is given: Sij = 1 if xi and yj are similar and Sij = 0 otherwise.We focus on a weakly supervised case which we are offered only positive pairs data.

The goal of cross-modal hashing is to learn two types of binary codes (Bx ∈ {-1, 1}n×c and By ∈ {-1, 1}n×c ) with the same code length c for each object by the hash functions f(xi) = sign(Wx T xi) and g(yj) = sign(Wy T yj), where Wx ∈ Rdx×c and Wy ∈ Rdy×c denote two projection matrices for the two modalities, respectively. The cross-modality fast searching task includes 1) using texts to search for the related images, and 2) using images to query the related texts. In cross-modal hashing framework, these two tasks are translated below: 1) using the hash codes of texts to find the related images in the hash code set of images according to the hamming distance, and 2) using the hash codes of images to query texts within the hash code set of texts. The framework of our approach is shown in Figure 1.

The principle of cross-modal hashing is that the codes Bx and By of data points from the same class but from different modalities should be as similar as possible, while they should be as distinct as possible if they are from different classes.

2.1 Formulation

We use the cosine similarity between hash codes of two across-modality data points,

to measure the similarity in the hash space. The cosine similarity between two data points should be as small as possible if they are from the same class and as large as possible if not. We use the projection vector to replace the hash codes and obtain the approximate cosine similarity:

We further borrow the maximum margin criterion idea from [Sharma et al., 2012; Li et al., 2003b] and replace the ratio operation with the subtraction operation:

The quantization loss, inspired by ITQ [Gong and Lazebnik, 2011], is defined as ‖B-XW‖2F . Combining the similarity constraint across domains and the quantization losses over each domain, we have the optimization problem:

Here α′ is the control parameter to balance the quantization loss and the cosine similarity constraint. The constraints, Wx T Wx = Ic×c and Wy T Wy = Ic×c, are used to make Wx andWy be orthogonal projections.

2.2 Relaxation

We first derive an upper bound of the objective function O(Bx, By,Wx,Wy) in Eq.(4) use it as a substitute for the objective function, leading to a relatively easily-optimized problem. Then we transform the multi-modality formulation into a unimodal formulation.

Exploring the well-known inequality,

we simplify the third term on the right hand side of Eq.(4), resulting in

(6)

write it in a matrix form,

where Lx and Ly are diagonal matrix and the diagonal elements are the row sum and column sum of S.

Then, the objective function in Eq.(4) becomes

where α = 12 α′ is the control parameter to keep a balance between the hash function learning stage.

It can be distinctly verified that the relationship between the objective function values in Eq.(4) and Eq.(8) is: O(Bx,By,Wx,Wy) ≤ O′ (Bx,By,Wx,Wy). This indicates that minO′ (Bx,By,Wx,Wy) ≥ O(Bx,By,Wx,Wy). In other words, our approach adopts a widely-used optimization principle: minimize an upper bound of the objective function. To balance the cross-domain correlation tr(Wx T XT SYWy) and its normalization term tr(Wx T XT LxXWx) + tr(Wy T YT LyYWy), we introduce an extra parameter β′ to weigh the normalization term: tr(Wx T XT SYWy) - 12 β′ (tr(Wx T XT LxXWx) + tr(Wy T YT LyYWy). For simplicity, the third term and the fourth term in Eq.(8) are written as 2αtr(Wx T XT SYWy) - β(tr(Wx T XT LxXWx) + tr(Wy T YT LyYWy), where β = αβ′ .

Rather than optimizing the problem through an alternating procedure: optimizing the parameters for one domain and then optimizing the parameters for the other domain in one iteration, we transform the objective function by combining the parameters across domains together into a unimodal objec-

tion Eq.(8) can be simplified below:

To facilitate the optimization, we impose the orthogonality constraint over the whole weight matrix W: WT W = Ic×c.

Algorithm 1 Quantized Correlation Hashing

Require:

Two-modality data matrices X and Y, similarity matrix S between two modalities, code length c, random initialized matrix W0 , α, β, iteration number N.

Optimize B when fixing W using Eq.(12); Iteratively optimize W when fixing B using Eq.(18);

end for

Ensure:

Projection matrix W and hash codes B

2.3 Optimization

We adopt an alternating optimization procedure to iteratively optimize W and B.

Fix W and optimize B

When W is fixed, the second term of Eq.(9) is a constant. Then, we have

Minimizing Eq.(10) is equal to maximizing the following:

where V = ZW. Since V is fixed, it is clear that the hash codes Bij should have the same sign as Vij. Consequently, we have

Fix B and optimize W

When B is fixed, Eq.(9) becomes an optimization problem with orthogonal constraint. Through introducing Lagrangian multipliers, we can rewrite the objective function for optimizingWas follows:

where Λ consists of Lagrangian multipliers, and O(W) is

Setting the gradient of Eq.(13) with respect to W to be zero, we can get

For the convenience of description, let G = ∂O(W) ∂W . Then we have

From Eq.(15), it is clear that we can get Λ = WT G. Since WT W is symmetric, Λ is symmetric as well. So Λ = WT G = GT W and ∂L(W) ∂W = G -WGT W. Based on the orthogonal constraint optimization procedure in [Wen and Yin, 2013], we can define a skew-symmetric matrix A = GWT -GT W. Then, we will update W by Crank-Nicolsonlike scheme [Smith, 1965]

where τ is the step size. By solving (17), we can obtain

Hereafter, we iteratively update W several times based on Eq.(18) with Barzilai-Borwein (BB) method [Wen and Yin, 2013]. In addition, please note that when iteratively optimizingW, the initial W is set to be the one optimized in the last round between B and W. For the first round, W is randomly initialized.

Convergence Analysis

B and W are alternately optimized for several iterations to seek an optimal solution. Since we minimize the objective function in each step, the convergence analysis of our optimization is

where B(t) and W(t) are the optimal hash codes and projection matrix in the tth iteration, respectively. In the experiments, the proposed hashing model almost converges at 50 iterations were conducted on optimizing W, as shown in Figure 2(a) and 2(b). In summary, the whole procedure of our method is illustrated in Algorithm 1.

3 Experiments

3.1 Datasets

To verify the efficiency and effectiveness of QCH, a series of experiments are carried out on two benchmark multimodal datasets, Wiki[Rasiwasia et al., 2010] and NUS-WIDE [Chua et al., 2009], and a large-scale dataset 58W-CIFAR [Krizhevsky and Hinton, 2009] for which we extracted two types of features to build multi-view data, so that cross-view retrieval can be performed.

The Wiki dataset [Rasiwasia et al., 2010] consists of 2,866 documents containing image-text pairs annotated with 10 semantic labels and each image was represented by 128dimensional SIFT feature and each text was denoted with a 10-dimensional feature vector generated by Latent Dirichlet Allocation (LDA) model.

The NUS-WIDE dataset [Chua et al., 2009] consists of 269,648 images from 81 ground-truth concepts with a total number of 5,018 unique tags. In our experiments, 186643 samples from 10 classes that involve largest amount of data were selected. Besides, each image was presented by a 500dimensional bag-of-words (BOW) feature vector and each text was denoted by a 1000-dimension tag vector.

To evaluate the performance in cross-view retrieval and the scalability of QCH, the 58W-CIFAR dataset consisting of 580,409 images from 10 categories selected from the 80 million tiny image dataset [Krizhevsky and Hinton, 2009] was used. To establish the multi-view data, a 384-dimensional GIST descriptor and a 496-dimensional HOG descriptor were extracted from each image. In the rest of paper, for the convenience of description, we consider GIST as "image" and HOG as "text" so that identical denotations can be acquired for all datasets.

On training and testing protocol, for Wiki dataset, 80% of the data were randomly selected as the training set and the remaining formed the testing set. For the other two datasets, NUS-WIDE and 58W-CIFAR, we randomly selected 1% of the data as the testing samples; while for training, we selected different numbers of instances to evaluate the influence of training size on our proposed model. In Experiment, we set the size of training set to 5000.

3.2 ComparedMethods and Evaluation

In this experiment, we concentrate on two-modality data, and the following two tasks for fast search are conducted. 1) Task 1: using images to query texts; and 2) Task 2: using texts to query images. To make comparisons with QCH, three stateof-the-art cross-modal hashing algorithms were selected in this paper: (1) CMSSH [Bronstein et al., 2010], (2) CVH[Kumar and Udupa, 2011] and (3) SCM [Zhang and Li, 2014]. CMSSH is a method to learn a group of hash functions for two modalities through eigen-decomposition and boosting. CVH extends spectral hashing [Weiss et al., 2009] to multimodal data, and SCM is derived from Kernel-based supervised hashing [Liu et al., 2012].

In addition, two baseline methods are selected, including (1) CCA [Hardoon et al., 2004] which is an unsupervised and also based on the cosine similarity function that can be applied to match data points of two domains, and (2) supervised CCA(SCCA) which is our QCH method without incorporating the quantization loss for optimization.

To assess the performance of different algorithms, the widely used criterion Mean Average Precision(MAP)[Kumar and Udupa, 2011; Zhang and Li, 2014; Zhai et al., 2013; Zhen and Yeung, 2012a] is selected, defined as:

where Q is the number of queries, and AP is computed as

where L is the number of true neighbors for the query q among the retrieval items, Pq(r) denotes the precision for query point q when top r data points are returned, and δ(i) is an indicator function which is 1 when the ith result is a true neighbor of the query and otherwise 0. Ground-truth neighbors are defined as those pairs which share at least one label. In our experiments, we set R = 500. All results were averaged over 10 independent runs with random selection of training and testing data in each run. All the experiments were conducted on a workstation with 24 Intel(R) Xeon(R) E5-2620@2.0GHz CPUs, 96 GB RAM and 64-bit Ubuntu system.

3.3 Evaluation of QCH

Firstly, we investigate the influence of two parameters introduced in QCH: α and β. α controls the tradeoff between hash function learning stage and quantization stage and β is a regularizer coefficient. During this experiment, c = 16 is used. Fig.3 displays the MAP results of QCH on three datasets with α varying from 0.001 to 5 and β ranging from 0.001 to 5.

We can find that QCH is a little more sensitive to α and β on Wiki and NUS-WIDE as compared to the case on dataset 58W-CIFAR. By further investigating the results in this figure closely, an interesting and promising phenomenon can be found that when α > 0.02 and 0.005 < β < 0.05 on Wiki and NUS-WIDE datasets, QCH seems not so sensitive to α and β, which provides us the evidence that setting α = 0.05 and β = 0.02 is a reasonable to QCH for Wiki and NUS-WIDE datasets. QCH performs better on 58W-CIFAR dataset when α and β are larger. Since multi-view data have stronger correlation than cross-modal data, so we set larger values, i.e. α = 1 and β = 0.1 on multi-view datasets for example 58W- CIFAR.

3.4 Comparison with State-of-the-art Methods and Baselines

The comparison experiments were carried out between the compared methods and QCH on the three datasets. For fair comparison, the parameter settings of three state-of-the-art algorithms are adopted as recommended in their corresponding papers. Table 1 shows the experimental results of different algorithms on two tasks with different code lengths on the three datasets. In addition, for different tasks, Fig. 4 further presents the precision changes of different algorithms along with the number of retrieval results R with c = 8 and c = 16, respectively. Based on the table and figure, we have the following analysis.

Task 1: using images to query texts

From Table 1, we can find that QCH outperforms all the compared algorithms on all datasets over all code lengths. From Fig.4, we can find that QCH is notably superior to the five compared methods on Wiki and NUS-WIDE datasets; On 58W-CIFAR, QCH is particularly better than SCM, CMSSH and CCA, and obtains a bit better performance than CVH and SCCA. The above performance of QCH demonstrates the efficiency and effectiveness of QCH on the first task. The superiority of QCH over SCCA on all datasets over all code lengths substantiates the importance of simultaneously optimizing quantization loss in our cross-modal hashing model.

Task 2: using texts to query images

From Table 1, the same conclusion as that of the first task can be drawn. Compared to the first task, we find that QCH obtains better performance on the second task, especially on Wiki and NUS-WIDE datasets. From Fig.4, we can observe that QCH shows its great advantage over all the compared algorithms on Wiki and NUS-WIDE. While on the 58W-CIFAR dataset, QCH achieves a notable improvement over SCM, CMSSH and CCA, and performs comparably to CVH and SCCA. Again, the comparison results on the second task consistently verify the superiority of the proposed cross-modal hashing model.

3.5 Effect of the Size of the Training Set and the Code Length

To further demonstrate the effectiveness of QCH, we additionally evaluate the effect of the code length and the effect of the numbers of training data against the compared methods in Figure 6 and Figure 3, respectively.

From Figure 6, we can conclude that QCH consistently performs significantly better than all compared algorithms on all datasets as the code length c increases no matter for Task1 or Task2. More specifically, QCH outperforms CMSSH, CVH, CCA and SCCA clearly; Compared to SCM, though QCH is a little better on Wiki and NUS-WIDE datasets, it particularly gains great advantage on 58W-CIFAR.

To see the effect of the training data size on QCH, we conducted experiments on the NUS-WIDE dataset by increasing the train size from 2,000 to 20,000 as shown in Figure 3. Evidently, QCH is not sensitive to the size, while the others are particularly sensitive. It indicates QCHcan performverywell even only a small number of data points are used for training. This is beneficial from the incorporating of simultaneously optimizing quantization loss and optimizing similarity loss in the proposed model. Note that due to space limitation, we only report the results over the NUS-WIDE dataset, and the conclusions for other datasets hold.

4 Conclusions

In this paper, we introduce the Quantized Correlation Hashing (QCH) method for cross-modal similarity search that simultaneously optimizes the quantization loss and binary code learning. The problem is effectively optimized using the relaxation scheme and the alternative procedure. Extensive experiments on three datasets show that QCH outperforms the state-of-the-art cross-/multi-modal hashing methods, especially when the code length is small.

5 Acknowledgement

This research work was partially supported by Grants 9732015CB351800, Natural Science Foundation Of China (No. 61472456,61421062), Guangzhou Pearl River Science and Technology Rising Star Project under Grant 2013J2200068, and the Guangdong Natural Science Funds for Distinguished Young Scholar under Grant S2013050014265. This research was partially supported by the Guangdong Provincial Government of China through the "Computational Science Innovative Research Team" program.