Learning to Hash on Partial Multi-Modal Data

1 Introduction

With the explosive growth of the Internet, a huge amount of data has been generated, which indicates that efficient similarity search becomes more important. Traditional similarity search methods are difficult to be directly used for large scale applications since linear scan between query example and all candidates in the database is impractical. Moreover, the similarity between data examples is usually conducted in high dimensional space. Hashing methods [Datar et al., 2004; Bergamo et al., 2011; Weiss et al., 2008; Liu et al., 2011; Rastegari et al., 2013; Salakhutdinov and Hinton, 2009; Wang et al., 2010; Ye et al., 2013; Wang et al., 2014a; 2013a; Kong and Li, 2012; Raginsky and Lazebnik, 2009; Zhang et al., 2013; Wang et al., 2014c; 2015] have been proposed to address the similarity search problem within large scale data. Hashing techniques design compact binary code in a low-dimensional space for each data example so that similar examples are mapped to similar binary codes. The retrieval of similar data examples can then be completed in a sublinear or even constant time, using Hamming distance ranking based on fast binary operation (XOR) or hash table lookup within a certain Hamming distance. In addition, the storage cost can be significantly reduced due to the binary compression.

In many applications, data examples are usually represented by multiple modalities captured from different sources. For example, in web page search, the web page content and its linkage information can be regarded as two modalities. In web image retrieval, the image visual feature, text description and textual tags can be viewed as multiple modalities. Recently, several multi-modal hashing methods (also known as multi-view or cross-view) have been proposed to handle multi-modal data. Roughly speaking, these multimodal hashing approaches can be divided into two categories: modality-specific methods and modality-integrated ones.

The modality-specific hashing methods [Bronstein et al., 2010; Kumar and Udupa, 2011; Ou et al., 2013; Quadrianto and Lampert, 2011; Zhen and Yeung, 2012; Liu et al., 2014; Zhai et al., 2013] learn independent hashing codes for each modality of data examples, and then merge multiple binary codes from different modalities into the final hashing codes. A cross-modality similarity search hashing (CMSSH) method [Bronstein et al., 2010] is proposed to embed data from different feature space into a common metric space. The hashing codes are learned through eigen-decomposition with AdaBoost framework. In work [Kumar and Udupa, 2011], a cross-view hashing method is designed based on spectral hashing, which generates the hashing codes by minimizing the distance of hashing codes for similar data and maximizing the distance for dissimilar data. Co-Regularized Hashing [Zhen and Yeung, 2012] method intends to project data from multiple sources, and at the same time, preserve the intermodality similarity.

The modality-integrated hashing methods [Ding et al., 2014; Gong et al., 2014; 2012; Kim et al., 2012; Zhang et al., 2011; Zhang and Li, 2014] directly learn unified hashing codes for each data example. In the work of [Zhang et al., 2011], a Composite Hashing with Multiple Information Sources (CHMIS) method is proposed to incorporate information from multiple sources into final integrated hashing codes by linearly combining the hashing codes from different modalities. Multi-View Spectral Hashing (MVSH) [Kim et al., 2012] integrates multi-view information into binary codes, and uses product of codewords to avoid undesirable embedding. More recently, A Canonical Correlation Analysis with Iterative Quantization (CCA-ITQ) method has been proposed in [Gong et al., 2014; 2012] which treats the data features and tags as two different modalities. The hashing function is then learned by extracting a common space from these two modalities. The work in [Ding et al., 2014] introduces collective matrix factorization into multi-modal hashing (CMFH), which learns unified hashing codes by collective matrix factorization with latent factor model from different modalities. However, existing multi-modal hashing methods fail to handle the situation where only partial examples are available in different modalities.

Although existing multi-modal hashing methods generate promising results in dealing with multi-modal data, most of them assume that all data examples have full information in all modalities, or there exists at least one modality which contains all the examples. However, in real world tasks, it is often the case that every modality suffers from some missing information, which results in many partial examples [Li et al., 2014]. For instance, in web page search, many web pages may not contain any linkage information. For web image retrieval, not all images are associated with tags or text descriptions. Moreover, the image itself may be inaccessible due to deletion or invalid url. Therefore, it is a practical and important research problem to design effective hashing methods for partial multi-modal data.

In order to apply existing multi-modal hashing methods to partial data, we can either remove the data examples that suffer from missing information, or preprocess the partial examples by first filling in the missing data. The first strategy is clearly not suitable since the purpose is to map all examples to their corresponding binary codes, whereas our experiments show that the second strategy does not achieve good performance either. In this paper, we propose a novel Partial Multi-Modal Hashing (PM2H) approach to deal with such partial data. More specifically, a unified learning framework is developed to learn the binary codes, which simultaneously ensures the data consistency among different modalities via latent subspace learning, and preserves data similarity within the same modality through graph Laplacian. A coordinate descent algorithm is applied as the optimization procedure. We then further reduce the quantization error via orthogonal rotation based on the orthogonal invariant property of our formulation. Experiments on the datasets demonstrate the advantages of the proposed approach over several state-of-the-art multi-modal hashing methods. We summarize the contributions in this paper as follows:

1. We propose a unified hashing method to deal with partial multi-modal data scenario, which can generate effective hashing codes for all data examples. As far as we know, it is the first attempt to learn binary codes on partial multi-modal data.
2. We propose a coordinate descent method for the joint
3. optimization problem. We prove the orthogonal invariant property of the optimal solution and learn an orthogonal rotation by minimizing the quantization error to further improve the code effectiveness.
4. Our extensive experiments demonstrate PM2H is an effective hashing method when only partial multiple modality information sources are available.

2 Partial Multi-Modal Hashing

2.1 ProblemDefinition

For the convenience of discussion, assume we are dealing with two-modality data, i.e., given a data set of N data examples X={(x1i , x2i ), i = 1, . . . ,N}, where x1i ∈ Rd1 is the instance of the i-th example in the first modality and x2i ∈ Rd2 is the i-th example in the second modality (usually d1 ̸= d2). In the partial modality setting, a partial data set ˆXˆXˆX={ ˆXˆXˆX(1,2) , ˆXˆXˆX(1) , ˆXˆXˆX(2)} instead of X is given, where ˆXˆXˆX(1,2)={(x11 , x21 ), . . . , (x1c , x2c )} ∈ Rc×(d1+d2) denotes the common examples present in both modalities, ˆXˆXˆX(1)={x1c+1 , . . . , x1c+m} ∈ Rm×d1 denotes the examples only present in the first modality and ˆXˆXˆX(2)={x2c+m+1 , . . . , x2c+m+n} ∈ Rn×d2 denotes the examples only present in the second modality. Note that the number of examples present and only present in both modalities, the first modality, and the second modality are c, m and n (N=c+m+n). The purpose of PM2H is to learn unified hashing codes Y ={y1, y2, . . . , yN} ∈ {-1, 1}N×k together with the modality-specific hashing functions H 1 and H 2 to map each data example xi to the corresponding hashing codes yi:

where H t ∈ Rk×dt is the coefficient matrix representing the hashing function for the t-th modality and sgn is the sign function. k is the length of the code. vi is the signed magnitude relaxation of binary code yi, which is widely adopted in previous hashing approaches. The objective function of PM2H is composed of two components: (1) Data consistency between modalities, latent subspace learning is utilized to ensure that the hashing codes generated from different modalities are consistent. (2) Similarity preservation within modality, graph Laplacian is applied to enforce that similar data examples within each modality are mapped into similar codes.

2.2 Data Consistency betweenModalities

In the partial modality setting, ˆXˆXˆX(1,2) , ˆXˆXˆX(1) , ˆXˆXˆX(2) are represented by heterogeneous features of dimensions (d1 + d2), d1, d2, which makes it hard for their hashing codes learning. But investigating the problem from modality perspective, in each individual modality, the data instances are sharing the same feature space. The two different modalities are coupled/bridged by the shared common examples. If we can learn a common latent subspace for the two modalities, where instances belonging to the same example between different modalities are consistent, while at the same time for each modality, the representations for similar instances are close in the latent subspace. Then the hashing codes can be directly learned from this subspace, and we do not need to fill in or complete the partial modality examples. Let ˆXˆXˆX(1,2) = [ ˆXˆXˆX(1) c , ˆXˆXˆX(2) c ], where ˆXˆXˆX(1) c ∈ Rc×d1 , ˆXˆXˆX(2) c ∈ Rc×d2 are the instances of the common examples coming from the two modalities. We denote the instances of each modality as: ¯X¯X¯X(1) = [ ˆXˆXˆX(1) c , ˆXˆXˆX(1) ] ∈ R(c+m)×d1 , ¯X¯X¯X(2) = [ ˆXˆXˆX(2) c , ˆXˆXˆX(2) ] ∈ R(c+n)×d2 . Following the above idea, the latent subspace learning can be formulated as:

where B (1) ∈ Rk×d1 and B (2) ∈ Rk×d2 are the basis matrix for each modality's latent space. ¯ V¯ V¯ V (1) = [ˆ Vˆ Vˆ V (1) c , ˆ Vˆ Vˆ V (1) ] ∈ R(c+m)×k and ¯ V¯ V¯ V (2) = [ˆ Vˆ Vˆ V (2) c , ˆ Vˆ Vˆ V (2) ] ∈ R(c+n)×k are the latent representation of instances in the latent space, which can also be viewed as the relaxed representation of binary codes Y . The same latent space dimension k is shared between the two modalities. R(· ) = ‖· ‖2F (sum over all matrices) is the regularization term and λ is the tradeoff parameter. By Eqn.2 and Eqn.3, the latent space basis B and corresponding instance latent representation V are simultaneously learned to minimize the reconstruction error from each individual modality.

In the above equations, the latent space are learned independently for each modality. But in the partial modality setting, for examples present in both modalities ˆXˆXˆX(1) c , ˆXˆXˆX(2) c , their latent representation ˆ Vˆ Vˆ V (1) c , ˆ Vˆ Vˆ V (2) c should also be consistent. Incorporating the above formulations by ensuring ˆ Vˆ Vˆ V (1) c = ˆ Vˆ Vˆ V (2) c = ˆ Vˆ Vˆ V c, we seek to minimize:

By solving the above problem, we can obtain the homogeneous feature (relaxed hashing) representation for all examples as V = [ˆ Vˆ Vˆ V c, ˆ Vˆ Vˆ V (1) , ˆ Vˆ Vˆ V (2) ] ∈ R(c+m+n)×k , whether they are originally partial or not. Then the hashing codes Y can be directly achieved via binarization from this relaxed latent representation. Note that Eqn.4 is different from previous subspace based multi-modal hashing approaches, which either requires ¯ V¯ V¯ V (1) and ¯ V¯ V¯ V (2) to be the same or do not require ¯ V¯ V¯ V (1) and ¯ V¯ V¯ V (2) to share any common part. In the above formulation, ¯ V¯ V¯ V (1) and ¯ V¯ V¯ V (2) share one common representation ˆ Vˆ Vˆ V c, while at the same time have their own individual components. Moreover, the individual basis matrix B (1) and B (2) , which are learned from all available instances from both modalities, are connected by the common ˆ Vˆ Vˆ V c.

2.3 Similarity Preservation withinModality

One of the key problems in hashing algorithms is similarity preserving, which indicates that similar data examples should be mapped to similar hashing codes within a short Hamming distance. Therefore, besides the data consistency between different modalities, we also preserve the data similarity within each individual modality. In other words, we want the learned relaxed representation V to preserve the similarity structure in each modality. In this work, we use the L2 distance to measure the similarity between vi and vj as ‖vi - vj‖2 , which is consistent with the Hamming distance between the binary codes yi and yj ( 1 4 ‖yi - yj‖2 ). Then one natural way to preserve the similarity in each modality is to minimize the weighted average distance as follows:

Here, S (t) is the similarity matrix in t-th modality, which can be calculated from the instances ¯X¯X¯X(t) . In this paper, we adopt the local similarity [Wang et al., 2014b; Zhang et al., 2011], due to its nice property in many machine learning applications. To meet the similarity preservation criterion, we seek to minimize this quantity in each modality since it incurs a heavy penalty if two similar examples have very different latent representations.

By introducing a diagonal n×n matrix D(t) , whose entries are given by D(t) ii = ∑nj=1 S (t) ij . Eqn.5 can be rewritten as:

where L is called graph Laplacian [Weiss et al., 2008] and tr(· ) is the matrix trace function. By minimizing the above objective in all modalities, the similarity between different examples can be preserved in the latent representation.

2.4 Overall Objective and Optimization

The entire objective function consists of two components: the data consistency between modalities in Eqn.4 and similarity preservation within modality given in Eqn.6 as follows:

where α and λ are trade-off parameters to balance the weights among the terms. Note that ¯ V¯ V¯ V (1) and ¯ V¯ V¯ V (2) share an identical part ˆ Vˆ Vˆ V c corresponding to the common examples present in both modalities. Directly minimizing the objective function in Eqn.7 is intractable since it is a non-convex optimization problem with V and B coupled together. We propose to use coordinate descent scheme by iteratively solving the optimization problemwith respect to V andB as follows:

(1) Optimizing O with respect to ˆ Vˆ Vˆ V c, ˆ Vˆ Vˆ V (1) and ˆ Vˆ Vˆ V (2) by fixing B. Given the basis matrix B (t) for both modalities, we can decompose the objective since ˆ Vˆ Vˆ V c and ˆ Vˆ Vˆ V (t) will not depend on each other.

where ˆLˆLˆL(t) and ˆLˆLˆL(t) c can be simply derived from L(1) with some addition mathematical operation. const is the constant value independent with the parameter that to be optimized with. Although Eqn.8 and Eqn.9 are still non-convex, but they are smooth and differentiable which enables gradient descent methods for efficient optimization. We use L-BFGS quasiNewton method [Liu and Nocedal, 1989] to solve Eqn.8 and Eqn.9 with the obtained gradients. Due to space limitation, we will present the gradients in supplementary material.

(2) Optimizing O with respect to B (t) by fixing V . It is equivalent to solve the following least square problems:

By taking the derivative of Eqn.10 w.r.t. B (t) and setting it to 0, a closed form solution can be simply obtained. We then alternate the process of updating V and B for several iterations to find a locally optimal solution.

2.5 Orthogonal Rotation

After obtaining the optimal latent representation V , the hashing codes Y and modality-specific hashing functions H t can be generated using Eqn.1. It is obvious that the quantization error can be measured as ‖Y - V ‖2F . Inspired by [Gong et al., 2012], we propose to further improve the hashing codes by minimizing this quantization error using an orthogonal rotation. We first prove the following orthogonal invariant theorem.

Theorem 1. Assume Q is a k × k orthogonal matrix, i.e., QT Q = I . If V and B are an optimal solution to the problem in Eqn.7, then V Q and QT B are also an optimal solution.

‖B‖2F . Thus, the value of the objective function in Eqn.7 does not change by the orthogonal rotation.

According to the above theorem, we propose to seek for better hashing codes by minimizing the quantization error between the binary hashing codes Y and the orthogonal rotation of the latent representation V Q as follows:

Intuitively, we seek binary codes that are close to some orthogonal transformation of the latent representation. The orthogonal rotation not only preserves the optimality of the solution but also provides us more flexibility to achieve better hashing codes with low quantization error. The above optimization problem can be solved by minimizing Eqn.11 with respect to Y andQ alternatively.

Fix Q and update Y . The closed form solution can be expressed as:

which is identical with Eqn.1 except the rotation.

Fix Y and update Q. The objective function becomes:

In this case, the objective function is essentially the classic Orthogonal Procrustes problem [Schonemann, 1966], which can be solved efficiently by singular value decomposition using the following theorem (detailed proof in [Schonemann, 1966]).

Theorem 2. Let SΛU T be the singular value decomposition of Y T V . Then Q = US T minimizes the objective function in Eqn.13.

We perform the above two steps alternatively to obtain the optimal hashing codes and the orthogonal rotation matrix. The modality-specific hashing functions can be then derived by minimizing the projection error as:

where γ is the tradeoff parameter of the regularization term. The full learning algorithm is described in Algorithm 1.

Algorithm 1 Partial Multi-Modal Hashing (PM2H)

Input: Partial data { ˆXˆXˆX(1,2) , ˆXˆXˆX(1) , ˆXˆXˆX(2)}, trade-off parameters α, λ and γ

Output: Unified hashing codesY and hashing functionsH 1 , H 2

Initialize B, Calculate L.

repeat

Optimize Eqns.8 and 9 and update ˆ Vˆ Vˆ V c, ˆ Vˆ Vˆ V (1) and ˆ Vˆ Vˆ V (2) . Optimize Eqn.10 and update B (1) and B (2) .

until the solution converges

repeat

Update Y using Eqn.12 Update Q = US T according to Theorem 2. until the solution converges Obtain the hashing functions H 1 and H 2 from Eqn.14.

2.6 Analysis

This section provides some complexity analysis on the training cost of the learning algorithm. The optimization algorithm of PM2H consists of two main loops. In the first loop, we iteratively solve V and B to obtain the optimal solution, where the time complexities for solving V and B are bounded by O(Nkd1 + Nkd2 + Nk2 + N 2k) and O(Nk2 + Nkd1 + Nkd2) respectively. The second loop iteratively optimizes the binary hashing codes and the orthogonal rotation matrix, where the time complexities for updating Y and Q are bounded by O(Nk2 + k3 ). Thus, the total time complexity of the learning algorithm is bounded by O(Nkd1 +Nkd2 +N 2k +Nk2 + k3 ). For each query, the hashing time is constant O(d1k) and O(d2k).

3 Experimental Results

3.1 Datasets and Setting

We evaluate our method on two image datasets: NUS-WIDE and MIRFLICKR-25k. NUS-WIDE 1 contains 270k images associated with more than 5k unique tags. 81 ground-truth concepts are annotated on these images. We filter out those images with less than 10 tags, resulting in a subset of 110k image examples. Visual features are represented by 500dimension SIFT [Lowe, 2004] histograms, and text features are represented by index vectors of the most common 2k tags. We use 90% of the data as the training set and the rest 10% as the query set. MIRFLICKR-25k2 is collected from Flicker images for image retrieval tasks. This dataset contains 25k image examples associated with 38 unique labels. 100dimensional SIFT descriptors and 512-dimensional GIST descriptors [Oliva and Torralba, 2001] are extracted from these images as the two modalities. We randomly choose 23k image examples as the training set and 2k for testing. Two image examples are considered to be similar if they share at least one ground-truth concept/label. In our experiments, SIFT feature is viewed as modality 1, while text and GIST features are viewed as modality 2.

1 http://lms.comp.nus.edu.sg/research/NUS-WIDE.htm

2 http://press.liacs.nl/mirflickr/

To simulate the partial modality setting, we randomly select a fraction of training examples to be partial examples, i.e., they are represented by either of the modality but not both, and the remaining ones appear in both modalities. We refer the fraction number of partial examples as Partial Data Ratio (PDR), i.e., m+n N .

The proposed PM2H approach is compared with four different multi-modal hashing methods, i.e., CVH [Kumar and Udupa, 2011], CMSSH [Bronstein et al., 2010], CCAITQ [Gong et al., 2014; 2012] and CMFH [Ding et al., 2014]. 3 We implement our algorithm using Matlab on a PC with Intel Duo Core i5-2400 CPU 3.1GHz and 8GB RAM. The parameters α, λ and γ are tuned by 5-fold cross validation on the training set. We set the maximum number of iterations to 100. To remove any randomness caused by random selection of training set and random initialization, all of the results are averaged over 10 runs.

3.2 Results and Discussion

We first evaluate the performance of different methods by varying the number of hashing bits in the range of {8, 16, 32, 64, 128}, with fixed PDR 0.4. To apply the compared multi-modal hashing methods to the partial data, a simple way is to fill in the missing data with 0. However, this may result in large fitting errors between two modalities for the multi-modal methods, since the hashing code for the missing instance will be 0. Therefore, to achieve stronger baseline results, we replace the missing instance using the linear combination of its 5 nearest neighbor examples (weighed by their similarities) which appear in both modalities 4 . Then the baseline multi-modal hashing methods can be directly applied on these extended data.

The precisions for the top 100 retrieved examples are reported in Table 1. From these comparison results, we can see that PM2H provides the best results among all five hashing methods on both datasets. For example, the precision of PM2H increases over 8% and 15% on average compared with CMFH and CCA-ITQ on NUS-WIDE under modality 1. The reason is that PM2H can effectively handle the partial data by common subspace learning between modalities and similarity preservation within modality, while the compared methods fail to accurately extract a common space from the partial examples. It can be seen from Table 1 that CMSSH and CVH do not perform well especially with 64 or 128 bits. This phenomenon has also been observed in [Ding et al., 2014; Wang et al., 2013b]. Actually, in CMSSH and CVH methods, the hashing codes are learned by eigenvalue decomposition under the hard bit orthogonality constraint, which makes the first few projection directions very discriminative with high variance. However, the hashing codes will be dominated by bits with very low variance when the code length increases, resulting in many meaningless and ambiguous bits. Another interesting observation is that the retrieval result from modality 1 is better than that from modality 2 on NUSWIDE. This coincides with our expectation that the image modality is more informative than the tag modality since tags are usually noisy and incomplete.

3 We implement CVH and obtain the codes of CMSSH and CMFH from the authors. The code of CCA-ITQ is public available.

4 We empirically choose 5 in our experiments. But other numbers can also be applied.

To evaluate the effectiveness of the proposed PM2H under different partial data ratios, we progressively increase the PDR from {0, 0.2, 0.4, 0.6, 0.8} and compare our method with the other baselines by fixing the hashing bits to 32. The precision results of top 100 retrieved examples are shown in Fig.1. It can be seen from the figure that when the partial data ratio PDR is 0, the data actually becomes the traditional multi-modal setting with each example appears in both modalities. In this case, PM2H is also able to perform better than most baselines and is comparable with CMFH. As the PDR increases from 0 to 0.8, our PM2H approach always achieves the best performance among all compared methods. Although the missing instances are recovered from the common examples in both modalities, the baseline methods seem less effective in the modality missing case. Our hypothesis is that the missing data may not be accurately recovered when the data are missing blockwise for the partial data setting. In other words, the missing examples can be dissimilar to all the examples appear in both modalities.

We also evaluate the code effectiveness with and without orthogonal rotation. The comparison results (before and after rotation) in Table 2 demonstrate that the orthogonal rotation can further improve the effectiveness of the codes, which is consistent with our expectation since the quantization error is minimized through the rotation. Similar results on modality 2 are observed. Furthermore, we conduct parameter sensitivity experiment on α and λ by tuning only one parameter while fixing the other one to the optimal values obtained from the previous experiments. We identify that the performance of PM2H is relatively stable with respect to α ∈ (2, 100) and λ ∈ (0.001, 0.1).

4 Conclusions

This paper propose a novel hashing approach to deal with partial multi-modal data. We formulate a unified learning framework by simultaneously ensuring data consistency among different modalities via latent subspace learning, and preserving data similarity within the same modality through graph Laplacian. A coordinate descent algorithm is applied to solve the optimization problem. We then utilize orthogonal rotation to further reduce the quantization error. Experiments on two datasets demonstrate the advantages of the proposed approach in dealing with partial multi-modal data over several multi-modal hashing methods. There are several possibilities to explore in the future research. For example, we plan to apply some sequential learning approach to accelerate the training process. We also plan to extend this subspace based partial modality learning idea to nonlinear latent subspace cases.

5 Acknowledgments

This work is partially supported by NSF research grants IIS0746830, DRL-0822296, CNS-1012208, IIS-1017837, CNS1314688 and a research grant from Office of Naval Research (ONR-11627465). This work is also partially supported by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF0939370.