Supervised Matrix Factorization for Cross-Modality Hashing

1 Introduction

Cross-modality retrieval has been a fundamental problem in several emerging applications including visual search, machine translation, and text mining [Bronstein et al., 2010; Masci et al., 2014; Rasiwasia et al., 2010; Costa Pereira et al., 2014]. In a typical scenario of cross-modality retrieval, a query comes from one modality, e.g., text, while the returned results come from another modality, e.g., image. To achieve this goal, a typical solution adopted by most existing works is to embed data samples of different modalities into a common low-dimensional space. By doing so, both the query and returns can be well aligned to capture their crossmodality similarities for retrieval [Costa Pereira et al., 2014; Wang et al., 2014].

⇤Corresponding author.

Recently, both unsupervised and supervised hashing techniques have been investigated for cross-modality retrieval due to their prominent efficiency. For instance, Bronstein et al. proposed a Cross-Modality Similarity Search Hashing (CMSSH) algorithm by using eigen-decomposition and boosting. Both Cross-View Hashing (CVH) [Kumar and Udupa, 2011] and Inter-Media Hashing (IMH) [Song et al., 2013] extended the classic Spectral Hashing approach [Weiss et al., 2009] to the scenario of cross-modality retrieval. For another instance, Co-Regularized Hashing (CRH) [Zhen and Yeung, 2012] and Heterogeneous Translated Hashing (HTH) [Wei et al., 2014] further deal with the cross-modality hashing under a co-regularized boosting framework.

In [Rastegari et al., 2013], Predictable Dual-View Hashing (PDH) was proposed to learn the discriminative hash functions via a max-margin formulation with an iterative optimization algorithm. In [Ding et al., 2014], Collective Matrix Factorization Hashing (CMFH) was proposed to formulate the joint learning of cross-modality binary codes as a collective matrix factorization problem. In [Zhang and Li, 2014], Supervised Multi-modal Hashing (SMH) was proposed to integrate semantic labels to improve the performance of hash function learning in the respective modalities.

While promising progress has been made, it remains as an open problem to capture the multi-modal similarities among data samples, as well as to preserve such similarities in a produced binary code (Hamming) space. As mentioned before, collective factorization [Ding et al., 2014] and supervised hashing [Zhang and Li, 2014] have demonstrated outperformance on respective problems, a.k.a., for cross-modality retrieval and for single-modality binary code learning [Liu et al., 2015; Mukherjee et al., 2015; Lin et al., 2015]. The intuition of our work is to combine the merits of supervised hashing [Liu et al., 2012; Zhang and Li, 2014] over the state-ofthe-art cross-modality retrieval schemes [Ding et al., 2014].

However, the integration of both approaches towards supervised cross-modality hashing is not an easy task. In one aspect, it is hard to optimize the discrete Hamming distances. In the other aspect, the complexity of the existing matrix factorization hashing and supervised cross-modality hashing are very high, which are the square of the training set size [Zhang and Li, 2014; Liu et al., 2015; Mukherjee et al., 2015] and cannot be easily scaled up to massive training data.

In this paper, we propose a novel cross-modality hashing method, dubbed the name Supervised Matrix Factorization Hashing (SMFH), which addresses the above challenges under a graph-regularized, collective non-negative matrix factorization framework. The first contribution we make is a hybrid regularization method to model the hash function learning, which integrates graph regularization into the collective non-negative matrix factorization. The second contribution we make is a supervised collective non-negative matrix factorization scheme, which leverages semantic labels to refine the graph regularizer during the step of graph construction. It ensures the learned binary codes to preserve the semantic similarities among data within multiple modalities.

Besides the two contributions mentioned above, we also propose an optimization algorithm to solve the objective function designed for SMFH, which works under an iterative updating procedure with stochastic sampling. This strategy can reach a training time reduction of supervised crossmodality hashing. Fig. 1 shows the overall framework of the proposed SMFH scheme. We conduct extensive experiments in cross-modality visual search, i.e., using text queries to retrieve relevant images and vice versa, on three widely used benchmarks including, PASCAL-Sentence, Wiki and NUSWIDE. We demonstrate the superior performance of SMFH over a group of state-of-the-art cross-modality hashing methods including CVH [Kumar and Udupa, 2011], PDH [Rastegari et al., 2013], SMH [Zhang and Li, 2014], and CMFH [Ding et al., 2014].

The rest of this paper is organized as follows: in Section 2, we present our SMFH approach in depth. Section 3 shows extensive experiments conducted on three benchmark datasets. Finally, we draw our conclusions in Section 4 and discuss the future work.

2 SupervisedMatrix Factorization Hashing

In this section, we describe the proposed supervised crossmodality hashing algorithm. Without loss of generality, we take bi-modal hashing for instance, which can be easily extended to the scenario of multi-modality hashing.

2.1 Collective Factorization for Cross-Modality Hashing

Non-negative Matrix Factorization (NMF) is a matrix decomposition algorithm that focuses on learning low-rank representation. We define a non-negative data matrix X = [x1↪ ▷▷▷↪ xN] 2 Rd⇥N , where N is the number of samples, d is the feature dimension, and xi is the i-th sample. Non-negative matrix factorization aims at finding two non-negative factors U = [u1↪ ▷▷▷↪ ur] 2 Rd⇥r and Y = [v1↪ ▷▷▷↪ vN] 2 Rr⇥N , r << d, whose product can approximate X, i.e.,

The squared Frobenius norm of the difference between two matrices is commonly used as the cost function to measure the approximation quality [Cai et al., 2011; Liu et al., 2013], which is defined as:

where k · kF is the Frobenius norm of the matrix.

However, when facing cross-modality data, it is expected that the matrix Y is a new multi-modality representation of the data matrices X1 and X2 in a common low-dimensional space. It aims to learn two base U1 2 Rd1⇥r and U2 2 Rd2⇥r to produce hash codes, which map bi-modal feature matrices into a r-dimensional binary code matrix Y 2 ¶0↪ 1♦r⇥N , where r is the number of hash bits. Ideally, Y should reveal the hidden semantics shared by different modalities.

Correspondingly, the learning of the hash code is done via:

where λt is the weight coefficient of this modality satisfying P2t=1 λt = 1. Intuitively, for the 1-st modal data X1 , the matrix U1 and the matrix Y are learned by Eq. (3), which is the same to X2 . yji = 1 means that the corresponding semantic representation ut·j is related to data Xt·i and vice versa.

2.2 Learning Supervised Hash Function

Towards learning supervised hash function, our goal is to preserve the semantic similarity among data points in the Hamming space. That says, the hash functions should enforce labeled data pair l(ei) = l(ej) to have identical or similar binary codes, where ei = (x1i ↪ x2i ) is the i-th data sample on both modalities from the training set, and function l(·) returns the supervised labels of the data across different modalities.

Our task is to find a graph matrix that preserves the intrinsic geometric structure of the similarity from bi-modal data. To this end, we first construct an affinity graph to model the aforementioned semantic information. This is done by calculating the pairwise similarity via the inner product among the semantic labels.

More specifically, the similarity between the i-th data sample and the j-th data sample is defined as follow:

Without loss of generality, we define a matrix La 2 ¶0↪ 1♦dl⇥N , where each column of La is the label representation vector of each data sample, and each row represents each sample's category 1 . Subsequently, the similarity matrix can be presented as A = La T ·La.

Then, our goal can be formulated via a spectral graph learning problem from the label similarity matrix A as:

where L is the Laplacian matrix for A.

Given data in two modalities, a.k.a, X1 = ¶x1i 2 Rd1 ♣i = 1↪ ▷▷▷↪N♦, X2 = ¶x2i 2 Rd2 ♣i = 1↪ ▷▷▷↪N♦, and their pairwise semantic similarity A, the goal of supervised hash function learning is to learn two basis matrices U1 and U2 , together with the hash codes Y by the following objective function:

where ↵ is a balance parameter, which can be seen as a regularizer for the above collective non-matrix factorization.

Intuitively, we learn coefficients of the optimal projection Wt by minimizing the error term between the linear hash function Ht (Xt ) = sgn(WtT Xt ) and the hash codes Y as ∥∥Y-Ht (Xt )∥∥2 . Inspired by [He et al., 2015], label graph can be used as Laplacian Regularized in this error. Then, the objective function of hash function learning is written as follows:

where ⌘ is the balance parameter. This term is integrated with the term of supervised semantic similarity in the proposed graphregularized collective matrix factorization. Then, the overall objective function is written as follows:

1 In this paper, we assume that La is fully observed without missing labels. We can get the labels among points in many cases for missing labeled datas, i.e. classification technology, which makes our assumption reasonable.

where θ is a tradeoff parameter to control the weights between hash function approximation and the proposed graph-regularized collective non-matrix factorization scheme.

2.3 Optimization

Directly minimizing the objective function in Eq. (8) is intractable due to the discrete constraint of Y. To tackle this issue, we relax the discrete constraint from Y 2 ¶0↪ 1♦r⇥n to 0  Y  1. After that, it is still non-convex with respect to Y↪Ut , and Wt jointly. This is further handled by using an alternating optimization, i.e., updating one variable while fixing the rest two until convergence. Due to the scale of the label similarity matrix, it is inefficient to store and compute it during optimization. To solve this problem, we propose a random sampling method, which uses a sampled sub-graph to replace the complete similarity matrix. The detailed optimization procedure is presented as follows:

(1) Fix Wt and Y, then update Ut . The corresponding subproblem is

Here we learn two basis matrices U1 and U2 , which turns this subproblem to be a traditional NMF problem for each modality.

By directly optimizing Eq. (9) within each modality respectively, we solve the new objective function through Lagrange multiplier = [ ik] with constant utij ≥ 0:

We derive the partial derivatives with respect to Ut as :

Then by Karush-Kuhn-Tucker (KKT) conditions, we update Ut via the following procedure:

Intuitively, Ut is non-negative after updating.

(2) Fix Ut andWt , then update Y. We then fix Ut andWt , the updating of Y subsequently refers to:

However, the scale of the semantic matrix is extremely large, which needs huge storage cost and makes the Eq. (12) hard to optimize during each iteration. To tackle this problem, we randomly sample parts of the original label similarity matrix A, which can approximate the graph regularization. We define a sampling matrix S 2 ¶0↪ 1♦N⇥m during each iteration, where m is the number of sampling points with m << N. Then the hash code of sampled data can be represented by ˆY = YT S 2 ¶0↪ 1♦dt⇥m, and the sampled label representation can be presented by ˆ La = La T S 2 ¶0↪ 1♦dl⇥m. By using the above sampling, this sub-problem of Eq. (12) can be rewritten as:

Algorithm 1 Supervised Matrix Factorization Hashing

• Input: Training data points in two modalities X1 and X2 , the corresponding pairwise semantic similarity matrix A, the number of support samples m, and the number of hash bits r.

Output: The hash codes Y for training data and the projection coefficient matrix Wt .

• 1: InitializeWt , Ut and Y by randommatrices, t = 1↪ 2.
• 2: repeat
• 3: FixingWt and Y, update Ut by Eq. (12);
• 4: Uniformly and randomly select m sample pairs from training data.
• 5: Fixing Ut andWt , update Y by Eq. (17);
• 6: Fixing Ut and Y, updateWt by Eq. (18);
• 7: until convergence

where ˆL is the Laplacian matrix for ˆA= ˆ La T · ˆ La.

Since solving such a constraint is not convenient, we further relax it to Y ≥ 0 and normalize Y after factorization in each iteration. Let Φ be the Lagrange Multiplier for the new constraint. The Lagrange term could be written as follows:

Using the KKT conditions, we have:

Eq. (14) can be solved by the following updating rule:

ˆD is the diagonal matrix with entries of column sums of ˆA.

(3) FixUt andY, thenupdateWt . This last sub-problemfinds the best projection coefficientWt by minimizing Eq. (7) for the t-th modality as the Laplacian Regularized Least squares algorithm [He et al., 2015], resulting in a closed-form solution:

We summarize the whole procedure of the proposed SMFH in Algorithm 1.

Times Complexity: The main time consumption of the proposed SMFH is the matrix factorization, its complexity is O⇣(ndr +(n+

d)(r2 + r) +m2 r)t⌘, where t is the number of iterations. Since r↪ m << n, the overall complexity is O(n(d+r)rt), which is linear to the size of the training data. In practice, the proposed SMFH is much faster than most cross-modality hashing, i.e. PDH and CMFH, whose training time is rounded to the competing cross-moality hashing method SMH. Although the hash codes of training data is obtained by minimizing Eq. (8), it cannot be directly applied to the case of the out-of-sample query. For such out-of-sample query, we use the hash function learned by Eq. (8) to generate the corresponding binary code. Then in online search, the time complexity for each modality is constant as O(dr).

2.4 Extension toMulti-Modality Search

It is quite intuitive to extend SMFH in Eq. (8) from bi-modal to multiple modalities, that is:

where Pnt t=1 λt = 1. It is convenient to adopt Algorithm 1 to minimize the objective function in Eq. (8). An alternating optimization strategy can also be used here. In particular, the variableUt andWt can be directly got through Eq. (12) and Eq. (17), respectively.And finally, the variable Y can be learned by the new formulation as follows:

3 Experiments

Quantitative experiments are conducted to validate the advantages of the proposed cross-modality hashing algorithm on three widely-used benchmark, i.e., PASCAL-Sentence 2 , Wiki 3 and NUS-WIDE 4 .

The PASCAL-Sentence dataset contains 1,000 images that are divided into 20 categories. Each image is represented by a 269dimensional visual feature extracted by a collections detectors. A 2,790-dimensional textual feature is extracted using the bag-ofwords representation with WordNet [Farhadi et al., 2010]. For this dataset, 800 image-sentence pairs are randomly sampled as the training set and the remaining for query testing.

The Wiki dataset contains 2,866 documents, where the imagetext pairs are fully annotated with 10 semantic categories. Each image is represented as a 128-dimensional bag-of-visual-words feature. Each document is represented as a 10-dimensional topical feature using Latent Dirichlet Allocation [Blei et al., 2003]. For the Wiki dataset, we randomly select 75% image-text pairs for training and the rest for query testing.

The NUS-WIDE dataset contains 269,648 images with 81 concepts crawled from Flickr. We select 186,577 labeled image-text pairs according to the top 10 largest concepts as adopted in [Hu et al., 2014; Zhang and Li, 2014]. In this dataset, images are represented by a 500-dimensional bag-of-visual-words feature, and its corresponding tags are represented by a 1,000-dimensional bag-ofwords feature. We choose 6,577 image-text pairs from this database as query and the remaining to form the dataset for training.

2 http://vision.cs.uiuc.edu/pascal-sentences/

3 http : //www.svcl.ucsd.edu/projects/crossmodal/

4 http : //lms.comp.nus.edu.sg/research/NUSWIDE.htm

Compared Methods: We evaluate the cross-modality retrieval task via: (1) the text-to-image side, termed Task 1, and (2) the image-to-text side, termed Task 2. In both sides, the proposed SMFH is compared against four state-of-the-art methods: CrossView Hashing (CVH) [Kumar and Udupa, 2011], Supervised MultiModal Hashing (SMH) [Zhang and Li, 2014], Predictable Dualview Hashing (PDH) [Rastegari et al., 2013] and Collective Matrix Factorization Hashing (CMFH) [Ding et al., 2014]. Except CVH, the source codes of the rest methods are available publicly, and all their parameters' setting are used as what their papers presented. All our experiments were run on a workstation with a 3.60GHz Intel Core I5-4790 CPU and 16GB RAM.

Evaluation Protocols: The quantitative performance is evaluated by using the mean Average Precision (mAP) with top 100 ranking list. We also consider other three evaluation protocols, i.e., precision at top-100 positions (Precision@100), Recall curves at top-K and Precision curves at top-K.

Parameter Settings: SMFH has five essential parameters in Eq. (13), i.e., λ1, λ2, ↵, θ, ⌘ and m. The parameter λ1 and λ2 control the weights between two modalities, which are found to have little influence. In our experiments, we empirically set λ1 = 0▷5 for the image modality and λ2 = 0▷5 for the text modality. The parameter ↵ holds the semantic similarity of the original space, which is set as a large number of 2. θ is a trade-off parameter, which is set as 25 on the two datasets. During each iteration, the number of sampling points is set as 800 for PASCAL-Sentence, 1↪ 000 for Wiki, and 2↪ 000 for the NUS-WIDE. At the last part of this section, we will analyze the relation of the parameter m, and show the convergence result. The three regularization parameters γ, β, and ⌘ are set to a small number 0▷001 in all the experiments.

Quantitative Results: Fig.2 shows the mAP results on PASCALSentence dataset with different bits on both retrieval tasks. SMFH has achieved remarkable mAP scores, especially when hash bit is larger than 32. Comparing to the second best scheme, SMFH has achieved 7▷1% mAP improvement for the Task 1 and 6▷5% improvement for the Task 2.

Then, we evaluate the proposed method on Wiki, as shown in the first row of Fig.3 and Tab.1, which demonstrate that SMFH has achieved superior performance on this benchmark for both text-toimage and image-to-text sides, both with a performance gain of more than 6%. The mAP results and Precision@100 results on Wiki are reported in Tab.1 under the setting of 32, 64, and 128 bits respectively. SMFH has achieved remarkable mAP and precision scores. Comparing with the state-of-the-art alogrithms, i.e., [Kumar and Udupa, 2011; Rastegari et al., 2013; Zhang and Li, 2014; Ding et al., 2014], for the task of text-to-image retrieval, our SMFH has significant advantage on precision and mAP values with all bits, mainly due to the fact that the matrix factorization can successfully find better latent topic concepts from text. Meanwhile SMFH fully uses supervised label to improve the cross-modality retrieval. Fig.3 shows the comparison of precision curves and recall curves on Wiki when hash bit is 64.

Similar performance gains are observed on the large-scale NUSWIDE, especially in the text-to-image retrieval. As shown in Tab.1 and the second row of Fig.3, SMFH achieves highest search accuracy. When the hash bit is 64, the precision of the top-100 Hamming ranking is over 60% by SMFH, which is much better than the state-of-the-arts [Ding et al., 2014; Kumar and Udupa, 2011; Rastegari et al., 2013; Zhang and Li, 2014]. Although, the mAP is not the highest when hash bit is 32 for text-to-image sides, SMFH maintain its the competitive advantage on higher hash bits. Nevertheless, the performance of Task 2 is at the second place, which also have competitive performance for cross-modality retrieval.

Tab.2 shows the results of training time comparing with different algorithms on different hash bits on three benchmarks, which contain the whole training set. PDH and CMFH are much higher than that of our proposed SMFH, with larger size of training data and higher feature dimensions. SMFH can get the better performance comparing with others, by fully use of the semantic information to enhance the performance with less training time.

We further study the influence of different sizes of the training set. As shown in Fig.4 (a) for Wiki, mAP results are shown when hash bit is 64, in which we vary the size of sampling from 200 to 2↪ 000. The performance of cross-modality retrieval consistently improve with the increasing of the sampling size for SMFH. Thus, we randomly choose about 100 image-tag pairs for each concept as the training set for convenience in optimization, which contain about 1↪ 000 pairs during each iteration. At last, we validate the convergence according to the sampling during each iteration. As shown in Fig.4 (b), when the size of sampling pairs is 1↪ 000, and the hash bit is 64, SMFH can quickly converge by using random sampling. The same conclusion holds on the NUS-WIDE dataset.

4 Conclusions

In this paper, we propose a novel hashing method termed Supervised Matrix Factorization Hashing (SMFH) for cross-modality visual search. We employ graph regularization to develop a collective matrix factorization based hashing framework, which can preserve the similarities among original features from different modalities into a produced Hamming space. Meanwhile, SMFH incorporates supervised label information to enhance the quantization quality of the learned binary codes. Furthermore, hashing and graph

Figure 4: Parameter Analysis.

regularization are integrated into a unified framework by means of joint hash function learning. In this framework, the given supervised labels can be leveraged to construct a label matrix, leading to more discriminative hash codes. Extensive experiments conducted on PASCAL-Sentence, Wiki, and NUS-WIDE benchmarks demonstrated the superior performance of SMFH over several state-of-the-art cross-modality hashing methods [Ding et al., 2014; Kumar and Udupa, 2011; Rastegari et al., 2013; Zhang and Li, 2014]. In the future, we would investigate large-scale discrete optimization techniques for the proposed SMFH.

5 Acknowledgement

This work is supported by the Special Fund for Earthquake Research in the Public Interest No.201508025, the Nature Science Foundation of China (No. 61402388, No. 61422210 and No. 61373076), the Fundamental Research Funds for the Central Universities (No. 20720150080 and No.2013121026), and the CCF-Tencent Open Research Fund.