Unsupervised Deep Hashing via Binary Latent Factor Models for Large-scale Cross-modal Retrieval

1 Introduction

Recently, cross-modal similarity search has been a popular research topic with the roaming multimedia data from various sources on the Internet. Compared to unimodal hashing that only deals with data in a single view, the heterogeneity of different feature distributions from various modalities makes the cross-modal hashing an extremely challenging task [Wang et al., 2017; Liu et al., 2017c; 2015; 2017b]. Following the unimodal hashing, conventional multimodal hashing methods can be categorized into supervised and unsupervised methods [Liu et al., 2017c]. For the supervised methods, manually-annotated labels and pairwise similarities are utilized in the code learning [Long et al., 2017; Lin et al., 2015; Jiang and Li, 2016; Liu et al., 2017a]. However, constructing such pairwise similarity matrix is computationally expensive and not feasible for the large-scale datasets. Therefore, recently unsupervised multimodal hashing methodology has been broadly discussed and explored, which is also the focus of this paper. Particularly, CVH [Kumar and Udupa, 2011], IMH [Song et al., 2013] and LCMH [Zhu et al., 2013] are three of the earliest works in the area of unsupervised crossmodal hashing. The first two methods extend conventional spectral hashing from unimodal to multimodal data and learn the hash function by solving eigenvalue decomposition with constructed similarity graph. In LCMH, some typical cluster centroids are picked up to represent the original data, thus reducing the computational cost substantially. However, such a process of eigenvalue decomposition in LCMH still compromises the hash code quality because of arbitrary mapping [Wang et al., 2016].

∗Corresponding author.

To tackle the above issues, CMFH [Ding et al., 2014] is proposed as the pioneering work, where matrix factorization is adopted to model the multiple relations among different modalities and the unified binary codes are being learned via projecting the multimodal data into a common latent space and then quantizing the unified representation afterwards. Accordingly, LSSH [Zhou et al., 2014] updates CMFH by using sparse coding in matrix factorization to learn binary codes for different modalities. However, in both CMFH and LSSH, various relaxation and rounding schemes are utilized in generating hash codes, which usually lead to large quantization errors in the binarization. Subsequently, RFDH is proposed in [Wang et al., 2017] to directly optimize and generate the unified binary codes for various views in the unsupervised manner via matrix factorization such that large quantization errors caused by relaxation can be relieved to some extent. However, despite the claimed contributions in RFDH, the neighborhood structures of inter-modal and intramodal existed in the original data are not explored. The same problem also occurs in DBRC [Li et al., 2017a], which reconstructs the original features from the joint binary representation. Some supervised methods like SMFH [Liu et al., 2016] and MDBE [Wang et al., 2016] are proposed to ameliorate such problems by utilizing semantic labels. However, those supervised methods are not concerned in this paper.

This paper presents a novel Unsupervised Deep CrossModal Hashing (UDCMH) to deal with the above limitations, where deep learning and collaborative binary latent representation model are integrated jointly, while the unified hash codes are optimized in an alternating way and then deep hash functions are built with a self-taught fashion. The framework of UDCMH is illustrated in Figure 1 and the corresponding contributions are summarized as follows.

1. This is the first work that implements the matrix factorization based cross-modal hashing in an unsupervised deep learning framework, where the deep hash functions for two modalities are being built in a self-taught manner. The proposed framework minimizes the quantization errors when projecting the original features from various modalities into a common Hamming space, which bridges the deep feature learning and hash function learning.
2. A novel binary latent representation model is employed, which allows us to directly learn the discrete hash codes without relaxation. We generate the unified hash codes with the weights of different modalities assigned dynamically so as to avoid large quantization errors. To restrict the unified hash codes, we incorporate the Laplacian constraints into the objective function with the intention to preserve both the nearest and the farthest neighbors of data.
3. An alternating optimization strategy is proposed to solve the non-convex objective function of UDCMH directly, where the deep parameters for two modalities and unified binary codes are optimized efficiently.

The rest of the paper is organized as follows. In methodology, the proposed UDCMH framework is presented in details with theoretical analysis. Then the achieved superior results on three datasets are reported in the experiment part. Finally, the proposed method is concluded.

2 Methodology

2.1 ProblemDefinition

Suppose that the multi-modality training set contains n image-text pairs, represented by O = {Xi}2i=1 , i = {1, 2}. We use X1 = {xj1 }nj=1 to represent the image modality, where xj1 ∈ Rd1 denotes the feature vector or the raw pixels of the j-th image. The text modality is denoted as X2 = {xj2 }nj=1 , where xj2 ∈ Rd2 is the feature vector of the j-th text, d1 and d2 (usually d1 ̸= d2) represent the dimensionalities of two feature spaces, respectively. The objective of UDCMH is to learn the deep hash functions Fi(Xi; θi) that hash the training data into a set of unified binary codes B ∈ {-1,+1}m×n , where m is the code length, θi represent the parameters of deep networks within two modalities respectively.

2.2 Model Formulation

The idea behind UDCMH is that we adopt a self-taught strategy engaging deep learning with binary latent representation model to optimize and generate the hash codes directly for multimodal similarity search. The overall objective function of UDCMH is formulated as below:

where λ, β and γ are balance parameters. Zi ∈ R4096×n are the deep feature matrices extracted from fc7 (fc7 I and fc7 T) layers, Ui ∈ R4096×m are the corresponding latent factor matrices, Li ∈ Rn×n are the Laplacian constraints and αi are the weight factors for image and text modalities respectively. The first term is referred as the optimization formulation of binary latent representation model and the later one is the objective function of hash function learning part. In the following paragraphs, we will elaborate the above equation part by part.

Deep Feature Learning

Following [Cao et al., 2017; Jiang and Li, 2016], AlexNet [Krizhevsky et al., 2012] and MultiLayer Perceptrons (MLP) [Rumelhart et al., 1986] are utilized in the feature learning of the image and text modalities separately, as shown in Figure 1. Particularly, AlexNet consists of 5 convolution layers and three fully-connected (fc) layers (fc6 Ifch I), while another three fc layers (fc6 T-fch T) are constructed in the text network. We slightly modify the last layers and replace them with new bottleneck layers comprising m hidden units to facilitate the network training afterwards. The numbers of hidden units are 4096, 4096 and m respectively for those fc layers in the two networks. Moreover, hyperbolic tangent (tanh) activation functions are added at the end of the last layers to make the representations quantizable. In this paper, the deep hash functions are denoted as Fi(Xi; θi), while the fc7 layer (fc7 I and fc7 T) representations Zi ∈ R4096×n are extracted and utilized in the binary latent representation learning.

Binary Latent Representation

In the hash code learning, a novel collaborative binary latent representation model is proposed such that the unified binary representation B can be directly optimized and solved for two modalities. Such unified binary representation in most previous methods is generated via reconstructing the original features from the latent common space first and binarizing the real-valued unified representation afterwards. This two-step approach usually yields the large quantization errors because of arbitrary relaxation schemes applied [Ding et al., 2014; Wang et al., 2017]. Moreover, Laplacian constraints that contain the neighborhood information from the original data are constructed in the objective function to restrict the to-belearnt hash code matrix B in the aspects of inter-view and intra-view. Furthermore, the weights for two modalities are assigned dynamically such that the important modality holds the dominant position during the collaborative binary latent representation model. We formulate the objective function of code learning part as following:

The first term approximates the extracted feature matrices Zi from two modalities with the latent factors matrices Ui and the unified hash codes B, while the Laplacian constraints in the second term act as a regularization term to restrict B. The associated Laplacian matrix Li ∈ Rn×n is defined as below:

where Ai ∈ Rn×n represent the affinity matrices for two modalities, diag(Ai1) are the diagonal matrices with each diagonal element being calculated as the sum of values in the corresponding row of Ai and 1 = [1, ..., 1]T ∈ Rn . The Laplacian constraints in Eq. (2) can be unfolded as:

where B∗,j and B∗,j represent the j-th and k-th columns of B. Unlike the Laplacian constraints constructed via anchor graph [Liu et al., 2011; Li et al., 2017b] and Laplacian Eigenmaps [Song et al., 2013] that only consider the nearest neighbors of data, both the nearest and farthest neighbors are exploited by kNN for each data point from the feature matrix (e.g, Z1 and Z2). Then, the corresponding values are set to 1 and -1 respectively for those neighbors with balanced weights assigned in building the affinity graph. In such a way, the neighborhood structure can be considered comprehensively and well preserved in Laplacian constraints when optimizing the binary codes. Moreover, by utilizing the affinity matrices with negative weights against traditional non-negative ones, the trivial solutions, which usually yield identical columns in optimizing B when (Ai)j,k > 0, can be avoided and thus more compact objective function can be formulated without the orthogonal constraints.

Hash Function Learning

Then we use the pre-learnt binary matrix B as the guidance in building the hash functions Fi(Xi; θi) such that the original features are projected into a common binary space and the knowledge can be shared seamlessly across different modalities. The objective function of such process is shown as following:

Particularly, Euclidean distances are minimized between the outputs of the deep networks and the unified binary code B in fine-tuning image and text networks respectively, thus updating the network parameters θi in the meanwhile.

2.3 Optimization Strategy

An alternating strategy is proposed to solve the objective function in Eq. (1), where the optimization problem can be solved with the following steps iteratively.

1) Update Ui. By fixing B, θi and αi, Eq. (1) is reduced as:

Then by setting the derivation of Eq. (6) with respect to Ui as 0, we can get the closed-form solution:

2) Update B. With all parameters fixed, we can rewrite Eq. (1) with B as the only argument:

However, solving B directly from the above equation is a NP-hard problem. Alternatively, we follow discrete cyclic coordinate descent (DCC) method [Shen et al., 2015] to learn one bit per time, where the closed-form solution to each row of B can be obtained while keeping other rows fixed. Then Eq. (8) is further derived as:

where Q = ∑2i=1 (αγ i UTi Zi + λFi(Xi; θi)),L = ∑2i=1 (αγ i βLi + λIn),W = [√αγ 1 U1; √αγ 2 U2]T . Moreover, we denote bT as the j-th row of B, and B′ the matrix of B excluding b. Similarly, let wT be the j-th row of W, W′ be the matrix of W excluding w and qT be the j-th row of Q, then we have

Similar to coordinate descent methods, the above equation can be optimized by solving each entry sequentially. However, in order to accelerate the convergence, we flip all the entries and select the one that is most probable to make the objective function descend in a monotonic discrete manner, thus obtaining the optimal solution efficiently.

3) Update αi. With other parameters fixed but αi as the argument, we formulate Eq. (1) as below:

Taking ∑2i=1 αi = 1 into consideration, the Lagrange function of Eq. (11) can be obtained as:

where η is the Lagrange multiplier. Then we have the optimal solution as:

Algorithm 1 Unsupervised Deep Cross-Modal Hashing

Input: Feature matrices Xi, i = {1, 2}, code length m, parameters β and γ, initialize the binary matrix B ∈ {-1,+1}m×n and deep parameters θi randomly, αi = [0.5, 0.5].

Output: Hash functions Fi(Xi; θi);

• 1: repeat
• 2: Extract the feature matrices Zi from fc7 I and fc7 T layers;
• 3: Construct the Laplacian Matrices Li by Eq. (3);
• 4: repeat
• 5: Update the latent factor matrices Ui by Eq. (7);
• 6: Update the unified hash code B for each bit by Eq. (8)∼(10);
• 7: Update the weight factors αi by Eq. (13);
• 8: until Convergence
• 9: Update the network parameters θi by Eq. (14);
• 10: until Convergence
• 11: return Fi(Xi; θi);
• Update θi. When fixing all other parameters but θi, the objective function (1) can be reduced to

The above equation can be solved by fine-tuning deep networks respectively with Stochastic Gradient Descent (SGD) [Bottou, 2010] under the guidance of the unified binary code B via mini-batch back-propagation, thus updating the network parameters θi simultaneously [Wu et al., 2017]. By repeating the above processes until convergence, the hash functions can be built eventually. When giving new query instances Xqi , the new hash codes can be obtained by calculating sign(Fi(Xqi ; θi)). The descriptions of the proposed method is summarized in Algorithm 1.

2.4 Complexity Analysis

In this section, the time complexity of the proposed binary latent representation model is discussed. Considering the constructed affinity matrix is usually highly sparse, the time complexity of each iteration during the hash code learning is reduced to O(d2n + dn), where d = max{d1, d2, m}. In total, the training time complexity of proposed binary latent representation learning is O((d2n+dn)T ), where T is the iteration number in the code learning process.

3 Experiment

In this section, we evaluate the performance of UDCMH via extensive experiments on three datasets and report the results to validate its superiority.

3.1 Data Sets

Wiki [Rasiwasia et al., 2010] consists of 2,866 image-text pairs collected from Wikipedia, where each image and text are represented by 128-dimensional SIFT feature vectors and

10-dimensional topic vectors separately. There are 10 semantic categories in labeling all documents and each pair is annotated with one of them. The dataset is randomly split into train and test set with 2,173 and 693 image-text pairs. NUS-WIDE [Chua et al., 2009] collects 269,648 images from Flickr labeled with 81 concepts. Following [Ding et al., 2014; Lin et al., 2015], 10 largest concepts are selected such that 186,577 image-tag pairs are preserved, while each image is represented by 500-dimensional BoW SIFT features and an index vector of the most frequent 1,000 tags is selected for each text. 2,000 image-tag pairs are randomly sampled as query and the rest pairs are used as train set. Each pair is labeled with at least one of those concepts and two data pairs are considered to be similar if at least one of labels matched. MIRFlickr [Huiskes and Lew, 2008] contains 25,000 images annotated by 24 provided labels. The images are represented with 100-dimensional SIFT descriptors and the texts are expressed as 500-dimensional tagging vectors. Following the settings on NUS-WIDE, 2,000 data pairs are randomly picked up as query and the rest pairs are used as train set.

3.2 Baselines and Evaluation Criteria

For fair comparison, seven unsupervised multimodal hashing methods, CVH [Kumar and Udupa, 2011], IMH [Song et al., 2013], LCMH [Zhu et al., 2013], CMFH [Ding et al., 2014], LSSH [Zhou et al., 2014], RFDH [Wang et al., 2017] and DBRC [Li et al., 2017a] are selected as baselines against UDCMH in the experiments. We use the identical train and test sets in evaluating the performance of the above baselines and the best results are reported by tuning their parameters in the papers. Following the previous works, two popular metrics: mean Average Precision (mAP) and topN-precision curve, are adopted in the performance evaluation accordingly in the following experiments.

3.3 Implementation Details

Without loss of generality, we use the whole training set on Wiki and select 5,000 instances on the other datasets randomly in the training processes [Ding et al., 2014; Lin et al., 2015]. For the parameters in UDCMH, the number of near and far neighbors are set to 50 and 200 in building the affinity graph. During the process of binary latent representation learning, γ is set as 5, β is set to 0.01 and the maximum iteration is set to 10. In the network learning, the original images and the tagging vectors are used as the inputs to the deep networks for two modalities, respectively. The learning rates are 0.0001 and 0.01 for those networks, while the batch size is all fixed as 512. The number of retrieved points is set to 50 when evaluating mAP. All the baselines are implemented by MATLAB 2014a, while the deep networks are constructed under the open-source Caffe [Jia et al., 2014] project. The server configurations are: Intel Core i7-6700k CPU, 64GB RAM and a NVIDIA 1080i GPU.

3.4 Results and Discussions

To validate the feasibility of the proposed framework, the convergence rates need to be analyzed and the loss curves of binary latent representation model and hash function learning at 128 bits are plotted in Figure 2 respectively. As can be seen, the objective function values of proposed binary code learning decrease very fast within 10 iterations. While the hash functions for two modalities can be built efficiently after 3 ∼ 5 iterations of network training.

Then we compare the proposed UDCMH with the baselines and report the mAP results at various code lengths on three datasets in Table 1. As can be seen, the proposed UDCMH outperforms significantly the state-of-the-arts baselines in terms of mAP at all bit sizes. Generally, the mAP values on Wiki are slightly lower than those on NUS-WIDE and MIRFlickr accordingly. The main reason is that the former dataset contains much fewer instances compared to the others, which limits the learning capability of deep neural networks. Specifically, for the tasks of 'image query text', the mAP values are 34.6%, 55.8% and 71.7% on Wiki, NUS-WIDE and MIRFlickr separately at 128 bits, which are at least 5% higher than those of the baselines. While for another tasks of 'text query image', the advantages of the proposed UDCMH decline slightly to about 3%, which are still superior and highly competitive. Compared to those baselines using matrix factorization such as CMFH and RFDH, the proposed framework integrates deep learning with collaborative binary latent representation model, where unified binary codes can be optimized directly without relaxation, thus improving the hash code quality significantly. For the purpose of comprehensive investigation, we also plot the topN-precision curves of various tasks on all datasets in Figure 3. As observed from those figures, the best performance is still achieved by the proposed UDCMH and the claimed superiority can be further validated. Moreover, we evaluate the system performance with the parameter variations in learning the binary latent representation, where γ is a positive number that controls the weight of each modality and β measures the impact of the Laplacian constraints. Only mAP@64 bits is reported for the limited space. Firstly, the mAP values remain stable when γ is varied from 0.1 to 5 for the image query text task, as shown in left two sub figures of Figure 4. As for another task, the mAP slightly increases when γ is larger than 3 and reaches the maximum at 5. Then we evaluate the retrieval performance when varying β in a wide range of [0.00001, 10]. As can be seen from Figure 4, the mAP values decrease when β is larger than 0.01 to some extent for different tasks.

We further analyze the effects on mAP results when varying the training size, as shown in Table 2. For the limited space, only the results on NUS-WIDE at 64 bits are reported. The mAP values keep increasing when utilizing more training data. It is worth noting that competitive results still can be achieved when using only 5,000 data points by UDCMH, which indicates its powerful ability in producing effective hash codes with the limited data size.

4 Conclusion

In this paper, we presented a novel unsupervised deep multimodal hashing framework, UDCMH, which integrates the deep networks with the proposed binary latent representation learning. Particularly, the unified binary codes can be optimized in an alternating manner for different modalities by solving the discrete constrained objective function directly, thus avoiding the large quantization errors. Moreover, the Laplacian constraint is constructed for each modality and utilized in the binary code learning with the neighborhood structure of original data preserved. Besides, UDCMH adopts a dynamic strategy in assigning weights for different modalities during optimization. Extensive experiments on three datasets show the superiority over several state-of-the-art baselines.