Deep Cross-Modal Hashing

Introduction

Approximate nearest neighbor (ANN) search (Andoni & Indyk, 2008; Andoni & Razenshteyn, 2015) plays a fundamental role in machine learning and related applications like information retrieval. Due to its low storage cost and fast retrieval speed, hashing has recently attracted much attention from the ANN research community (Weiss et al., 2008; Raginsky & Lazebnik, 2009; Wang et al., 2010; Liu et al., 2011; Norouzi & Fleet, 2011; Norouzi et al., 2012; Rastegari et al., 2013; Yu et al., 2014; Liu et al., 2014; Shrivastava & Li, 2014; Andoni et al., 2015; Neyshabur & Srebro, 2015; Leng et al., 2015). The goal of hashing is to map the data points from the original space into a Hamming space of binary codes where the similarity in the original space is preserved in the Hamming space. By using binary hash codes to represent the original data, the storage cost can be dramatically reduced. Furthermore, we can achieve a constant or sub-linear time complexity for search by using hash codes to construct an index. Hence, hashing has become more and more popular for ANN search in large-scale datasets.

In many applications, the data can have multi-modalities. For example, besides the image content, there also exists text information like tags for the images in Flickr and many other social websites. This kind of data is always called multi-modal data. With the rapid growth of multi-modal data in real applications especially multimedia applications, multi-modal hashing (MMH) has recently been widely used for ANN search (retrieval) on multi-modal datasets.

Existing MMH methods can be roughly divided into two main categories: mutli-source hashing (MSH) (Song et al., 2011; Zhang et al., 2011) and cross-modal hashing (CMH) (Kumar & Udupa, 2011; Ding et al., 2014; Zhang & Li, 2014; Lin et al., 2015). The goal of MSH is to learn hash codes by utilizing all the information from multiple modalities. Hence, MSH requires that all the modalities should be observed for all data points including the query points and those in database. In practice, the application of MSH is limited because in many cases it is difficult to acquire all the modalities of all data points. On the contrary, the application scenarios of CMH are more flexible than those of MSH. In CMH, the modality of a query point is different from the modality of the points in the database. Furthermore, typically the query point has only one modality and the points in the database can have one or more modalities. For example, we can use text queries to retrieve images in the database, and we can also use image queries to retrieve texts in the database. Due to its wide application, CMH has gained more attention than MSH.

Many CMH methods have recently been proposed. Representative methods include cross modality similarity sensitive hashing (CMSSH) (Bronstein et al., 2010), cross view hashing (CVH) (Kumar & Udupa, 2011), multi-modal latent binary embedding (MLBE) (Zhen & Yeung, 2012a), co-regularized hashing (CRH) (Zhen & Yeung, 2012b), semantic correlation maximization (SCM) (Zhang & Li, 2014), collective matrix factorization hashing (CMFH) (Ding et al., 2014), semantic topic multi-modal hashing (STMH) (Wang et al., 2015) and semantics preserving hashing (SePH) (Lin et al., 2015). Almost all these existing CMH methods are based on hand-crafted features. One shortcoming of these hand-crafted feature based methods is that the feature extraction procedure is independent of the hash-code learning procedure, which means that the hand-crafted features might not be optimally compatible with the hash-code learning procedure. Hence, these existing CMH methods with hand-crafted features may not achieve satisfactory performance in real applications.

Recently, deep learning with neural networks (LeCun et al., 1989; Krizhevsky et al., 2012) has been widely used to perform feature learning from scratch with promising performance. There also exist some methods which adopt deep learning for uni-modal hashing (Zhao et al., 2015; Liong et al., 2015). However, to the best of our knowledge, there has not appeared any deep CMH methods which can perform simultaneous feature learning and hash-code learning in the same framework.

In this paper, we propose a novel CMH method, called deep cross-modal hashing (DCMH), for cross-modal retrieval applications. The main contributions of DCMH are outlined as follows:

DCMH is an end-to-end learning framework with deep neural networks, one for each modality, to perform feature learning from scratch.

To the best of our knowledge, DCMH is the first CMH method which integrates both feature learning and hash-code learning into the same deep learning framework.

The hash-code learning problem is essentially a discrete optimization problem, which is difficult to learn. Hence, most existing CMH methods typically solve this problem by relaxing the original discrete learning problem into a continuous learning problem. This relaxation procedure may deteriorate the accuracy of the learned hash codes (Liu et al., 2014). Unlike these relaxation-based methods, DCMH directly learns the discrete hash codes without relaxation.

Experiments on real datasets with text-image modalities show that DCMH can outperform other baselines to achieve the state-of-the-art performance in cross-modal retrieval applications.

The rest of this paper is organized as follows. Section 2 introduces the problem definition of this paper. We present our DCMH method in Section 3, including the model formulation and learning algorithm. Experiments are shown in Section 4. At last, we conclude our work in Section 5.

Problem Definition

In this section, we introduce the notation and problem definition of this paper.

2 Cross-Modal Hashing

Although the method proposed in this paper can be easily adapted to cases with more than two modalities, we only focus on the case with two modalities here.

Assume that we have $n$ training entities (data points), each of which has two modalities of features. Without loss of generality, we use text-image datasets for illustration in this paper, which means that each training point has both text modality and image modality. We use ${\bf X}=\{{\bf x}_{i}\}_{i=1}^{n}$ to denote the image modality, where ${\bf x}_{i}$ can be the hand-crafted features or the raw pixels of image $i$. Moreover, we use ${\bf Y}=\{{\bf y}_{i}\}_{i=1}^{n}$ to denote the text modality, where ${\bf y}_{i}$ is typically the tag information related to image $i$. In addition, we are also given a cross-modal similarity matrix ${\bf S}$. $S_{ij}=1$ if image ${\bf x}_{i}$ and text ${\bf y}_{j}$ are similar, and $S_{ij}=0$ otherwise. Here, the similarity is typically defined by some semantic information such as class labels. For example, we can say that image ${\bf x}_{i}$ and text ${\bf y}_{j}$ are similar if they share the same class label. Otherwise, image ${\bf x}_{i}$ and text ${\bf y}_{j}$ are dissimilar if they are from different classes.

Given the above training information ${\bf X}$, ${\bf Y}$ and ${\bf S}$, the goal of cross-modal hashing is to learn two hash functions for the two modalities: $h^{(x)}({\bf x})\in\{-1,+1\}^{c}$ for the image modality and $h^{(y)}({\bf y})\in\{-1,+1\}^{c}$ for the text modality, where $c$ is the length of binary code. These two hash functions should preserve the cross-modal similarity in ${\bf S}$. More specifically, if $S_{ij}=1$, the Hamming distance between the binary codes ${\bf b}^{(x)}_{i}=h^{(x)}({\bf x}_{i})$ and ${\bf b}^{(y)}_{j}=h^{(y)}({\bf y}_{j})$ should be small. Otherwise if $S_{ij}=0$, the corresponding Hamming distance should be large.

Here, we assume that both modalities of features for each point in the training set are observed although our method can also be easily adapted to other settings where some training points have only one modality of features being observed. Please note that we only make this assumption for training points. After we have trained the model, we can use the learned model to generate hash codes for query and database points of either one modality or two modalities, which exactly matches the setting of cross-modal retrieval applications.

Deep Cross-Modal Hashing

In this section, we present the details about our deep CMH (DCMH) method, including model formulation and learning algorithm.

The whole DCMH model is shown in Figure 1, which is an end-to-end learning framework by seamlessly integrating two parts: the feature learning part and the hash-code learning part. During learning, each part can give feedback to the other part.

The feature learning part contains two deep neural networks, one for image modality and the other for text modality.

The deep neural network for image modality is a CNN model adapted from (Chatfield et al., 2014). There are eight layers in this CNN model. The first seven layers are the same as those in CNN-F of (Chatfield et al., 2014). The eightth layer is a fully-connected layer with the output being the learned image features.

Table 1 shows the detailed configuration of the CNN for image modality. More specifically, eight layers are divided into five convolutional layers and three fully-connected layers, which are denoted as “conv1 - conv5” and “full6 - full8” in Table 1, respectively. Each convolutional layer is described by several aspects:

“f. $num\times size\times size$” denotes the number of convolution filters and their receptive field size.

“pad” denotes the number of pixels to add to each size of the input;

“LRN” denotes whether Local Response Normalization (LRN) (Krizhevsky et al., 2012) is applied or not.

The number in the fully connected layers, such as “4096”, denotes the number of nodes in that layer. It is also the dimensionality of the output at that layer.

All the first seven layers use the Rectified Linear Unit (ReLU) (Krizhevsky et al., 2012) as activation function. For the eighth layer, we choose identity function as the activation function.

To perform feature learning from text, we first represent each text ${\bf y}_{j}$ as a vector with bag-of-words (BOW) representation. And then the bag-of-words vectors are used as the input to a deep neural network with three fully-connected layers, denoted as “full1 - full3”. The detailed configuration of the deep neural network for text is shown in Table 2, where the configuration shows the number of nodes in each layer. The activation function for the first two layers is ReLU, and that for the third layer is the identity function.

Please note that the main goal of this paper is to show that it is possible to design an end-to-end learning framework for cross-modal hashing by using deep neural networks for feature learning from scratch. But how to design different neural networks is not the focus of this paper. Other deep neural networks might also be used to perform feature learning for our DCMH model, which will be leaved for future study.

1.2 Hash-Code Learning Part

The objective function of DCMH is defined as follows:

The first term $-\sum_{i,j=1}^{n}(S_{ij}\Theta_{ij}-\log(1+e^{\Theta_{ij}}))$ in (3.1.2) is the negative log likelihood of the cross-modal similarities with the likelihood function defined as follows:

where $\Theta_{ij}=\frac{1}{2}{\bf F}_{*i}^{T}{\bf G}_{*j}$ and $\sigma(\Theta_{ij})=\frac{1}{1+e^{-\Theta_{ij}}}$.

It is easy to find that minimizing this negative log likelihood, which is equivalent to maximizing the likelihood, can make the similarity (inner product) between ${\bf F}_{*i}$ and ${\bf G}_{*j}$ be large when $S_{ij}=1$ and be small when $S_{ij}=0$. Hence, optimizing the first term in (3.1.2) can preserve the cross-modal similarity in ${\bf S}$ with the image feature representation ${\bf F}$ and text feature representation ${\bf G}$.

The third term $\eta(||{\bf F}{\bf 1}||^{2}_{F}+||{\bf G}{\bf 1}||^{2}_{F})$ in (3.1.2) is used to make each bit of the hash code be balanced on all the training points. More specifically, the number of $+1$ and that of $-1$ for each bit on all the training points should be almost the same. This constraint can be used to maximize the information provided by each bit.

In our experiment, we find that better performance can be achieved if the binary codes from the two modalities are set to be the same for the training points. Hence, we add another constraint ${\bf B}={\bf B}^{(x)}={\bf B}^{(y)}$ in (3.1.2). With this constraint, the problem in (3.1.2) can be equivalently transformed to the following reduced formulation:

where ${\bf F}=f({\bf X};\theta_{x})$ means ${\bf F}_{*i}=f({\bf x}_{i};\theta_{x})$, ${\bf G}=g({\bf Y};\theta_{y})$ means ${\bf G}_{*j}=g({\bf y}_{j};\theta_{y})$. This is the final objective function of our DCMH for learning.

From (3.1.2), we can find that the parameters of the deep neural networks ($\theta_{x}$ and $\theta_{y}$) and the binary hash code (${\bf B}$) are learned from the same objective function. That is to say, DCMH integrates both feature learning and hash-code learning into the same deep learning framework.

Please note that we only make ${\bf B}^{(x)}={\bf B}^{(y)}$ for the training points. After we have learned the problem in (3.1.2), we still need to generate different binary codes ${\bf b}^{(x)}_{i}=h^{(x)}({\bf x}_{i})$ and ${\bf b}^{(y)}_{i}=h^{(y)}({\bf y}_{i})$ for the two different modalities of the same point $i$ if point $i$ is a query point or a point from the database rather than a training point. This will be further illustrated in Section 3.3.

2 Learning

We adopt an alternating learning strategy to learn $\theta_{x}$, $\theta_{y}$ and ${\bf B}$. Each time we optimize one parameter with the other parameters fixed. The whole alternating learning algorithm for DCMH is briefly outlined in Algorithm 1, and the detailed derivation will be introduced in the following content of this subsection.

When $\theta_{y}$ and ${\bf B}$ are fixed, we learn the CNN parameter $\theta_{x}$ of the image modality by using a back-propagation (BP) algorithm. As most existing deep learning methods (Krizhevsky et al., 2012), we utilize stochastic gradient descent (SGD) to learn $\theta_{x}$ with the BP algorithm. More specifically, in each iteration we sample a mini-batch of points from the training set and then carry out our learning algorithm based on the sampled data.

In particular, for each sampled point ${\bf x}_{i}$, we first compute the following gradient:

Then we can compute $\frac{\partial{\mathcal{J}}}{\partial\theta_{x}}$ with $\frac{\partial{\mathcal{J}}}{\partial{\bf F}_{*i}}$ by using the chain rule, based on which BP can be used to update the parameter $\theta_{x}$.

When ${\bf B}$ and $\theta_{x}$ are fixed, we also learn the neural network parameter $\theta_{y}$ of the text modality by using SGD with a BP algorithm. More specifically, for each sampled point ${\bf y}_{j}$, we first compute the following gradient:

Then we can compute $\frac{\partial{\mathcal{J}}}{\partial\theta_{y}}$ with $\frac{\partial{\mathcal{J}}}{\partial{\bf G}_{*j}}$ by using the chain rule, based on which BP can be used to update the parameter $\theta_{y}$.

When $\theta_{x}$ and $\theta_{y}$ are fixed, the problem in (3.1.2) can be reformulated as follows:

It is easy to find that the binary code $B_{ij}$ should keep the same sign as $V_{ij}$. Therefore, we have:

3 Out-of-Sample Extension

For any point which is not in the training set, we can obtain its hash code as long as one of its modalities (image or text) is observed. In particular, given the image modality ${\bf x}_{q}$ of point $q$, we can adopt forward propagation to generate the hash code as follows:

Similarly, if point $q$ only has the text modality ${\bf y}_{q}$, we can also generate the hash code ${\bf b}_{q}^{(y)}$ as follows:

Hence, our DCMH model can be used for cross-modal search where the query points have one modality and the points in database have the other modality.

Experiment

We carry out experiments on text-image datasets to verify the effectiveness of DCMH. DCMH is implemented with the open source deep learning toolbox MatConvNet (Vedaldi & Lenc, 2015) on a NVIDIA K40 GPU server.

Two datasets, MIRFLICKR-25K (Huiskes & Lew, 2008) and NUS-WIDE (Chua et al., 2009), are used for evaluation.

The original MIRFLICKR-25K dataset (Huiskes & Lew, 2008) consists of 25,000 images collected from Flickr website. Each image is associated with several textual tags. Hence, each point is a text-image pair. We select those points which have at least 20 textual tags for our experiment, and subsequently we get 20,015 points for our experiment. The text for each point is represented as a 1386-dimensional bag-of-words vector. For the hand-crafted feature based method, each image is represented by a 512-dimensional SIFT feature vector. Furthermore, each point is manually annotated with one of the 24 unique labels. The image $i$ and text $j$ are considered to be similar if point $i$ and point $j$ share the same label. Otherwise, they are considered to be dissimilar.

The NUS-WIDE dataset (Chua et al., 2009) contains 260,648 web images, and some images are associated with textual tags. It is a multi-label dataset where each point is annotated with one or multiple labels from 81 concept labels. We select 186,577 text-image pairs that belong to the 10 most frequent concepts. The text for each point is represented as a 1000-dimensional bag-of-words vector. The hand-crafted feature for each image is a 500-dimensional bag-of-visual words (BOVW) vector. The image $i$ and text $j$ are considered to be similar if point $i$ and point $j$ share at least one concept label. Otherwise, they are considered to be dissimilar.

2 Evaluation Protocol and Baseline

For MIRFLICKR-25K dataset, we take 2000 data points as the test (query) set and the remaining points as the retrieval set (database). For NUS-WIDE dataset, we take 1% of the dataset as the test (query) set and the rest as the retrieval set. Moreover, we take 5000 data points from the retrieval set to construct the training set for both MIRFLICKR-25K and NUS-WIDE. The ground-truth neighbors are defined as those text-image pairs which share at least one semantic label.

For hashing-based retrieval, Hamming ranking and hash lookup are two widely used retrieval procedures (Liu et al., 2014). We also adopt these two procedures to evaluate our method and other baselines. The Hamming ranking procedure ranks the points in the database (retrieval set) according to their Hamming distances to the given query point, in an increasing order. Mean average precision (MAP) (Liu et al., 2014) is the widely used metric to measure the accuracy of the Hamming ranking procedure. The hash lookup procedure returns all the points within a certain Hamming radius away from the query point. The precision-recall curve and F-measure (Liu et al., 2014) are widely used metrics to measure the accuracy of the hash lookup procedure.

2.2 Baseline

Five state-of-the-art cross-modal hashing methods are adopted as baselines for comparison, including SePH (Lin et al., 2015), STMH (Wang et al., 2015), SCM (Zhang & Li, 2014), CMFH (Ding et al., 2014) and CCA (Hotelling, 1936). Source codes of SePH, STMH and SCM are kindly provided by the corresponding authors. While for CMFH and CCA whose codes are not available, we implement them carefully by ourselves. SePH is a kernel-based method, for which we use RBF kernel and take 500 randomly selected points as kernel bases by following its authors’ suggestion. In SePH, the authors propose two strategies to construct the hash codes for retrieval (database) points according to whether both modalities of a point are observed or not. However, in this paper we can only use one modality for the database (retrieval) points, because the focus of this paper is on cross-modal retrieval. All the other parameters for all baselines are set according to the suggestion of the original papers of these baselines.

For our DCMH, we use a validation set to choose the hyper-parameter $\gamma$ and $\eta$, and find that good performance can be achieved with $\gamma=\eta=1$. Hence, we set $\gamma=\eta=1$ for all our experiments. We exploit the CNN-F network (Chatfield et al., 2014) pre-trained on ImageNet dataset (Russakovsky et al., 2014) to initialize the first seven layers of the CNN for image modality, and all the other parameters of the deep neural networks in DCMH are randomly initialized. The input for the image modality is the raw pixels, and that for the text modality is the BOW vectors. We fix the mini-batch size to be 128 and set the iteration number of the outer-loop in Algorithm 1 to be 500.

3 Accuracy

We report the accuracy for both Hamming ranking procedure and hash lookup procedure.

The MAP results for DCMH and other baselines with hand-crafted features on MIRFLICKR-25K and NUS-WIDE are reported in Table 3 and Table 4, respectively. We can find that DCMH can outperform all the other baselines with hand-crafted features.

To further verify the effectiveness of DCMH, we exploit the CNN-F deep network (Chatfield et al., 2014) pre-trained on ImageNet dataset, which is the same as the initial CNN of the image modality in DCMH, to extract CNN features. All the baselines are trained based on these CNN features. The MAP results for DCMH and other baselines with CNN features on MIRFLICKR-25K and NUS-WIDE are reported in Table 5 and Table 6, respectively. We can find that DCMH can outperform all the other baselines except SePH. For SePH, DCMH can outperform it in most cases except the image to text retrieval on NUS-WIDE. Please note that SePH is a kernel-based method, which constructs kernels based on the CNN-F image features and text features. However, our DCMH can be seen as a linear method with deep features because the final layers of both modalities are fully-collected ones with identity activation functions. We find that the better performance of SePH mainly comes from the kernel features of SePH, which is verified by the worse results of a linear variant of SePH without kernels called “SePH-linear” in Table 6. DCMH can outperform SePH with linear features in all cases. And even for SePH with kernel features, DCMH can outperform it for most cases. Hence, compared with these baselines with CNN-F features, the better accuracy of DCMH verifies that integrating both feature learning and hash-code learning into the same framework may improve the performance.

3.2 Hash Lookup

In the hash lookup procedure, we can compute the precision, recall and F-measure for the returned points given any Hamming radius. The Hamming radius can take the values in $\{0,1,\dots,c\}$. By varying the Hamming radius from 0 to $c$ with a stepsize 1, we can get the precision-recall curve.

Figure 2 shows the precision-recall curve with code length 16 on two datasets, where the baselines use hand-drafted features. Here, “Image $\to$ Text” denotes the case where the query is image and the database is text, and similar notations are used for other cases. We can find that DCMH can dramatically outperform the baselines.

Figure 3 shows the precision-recall curve with code length 16 on two datasets, where the baselines use CNN-F features. We can also find that DCMH can outperform all the other baselines with CNN-F features.

We select the best three methods and report their precision, recall and F-measure with Hamming radius $r=0,1,2$ in Table 7 on MIRFLICKR-25K when the code length is 16, where “I” denotes image and “T” denotes text. We can find that in all cases our DCMH can achieve the best recall and F-measure within Hamming radius $r=0,1,2$. For precision, DCMH outperforms SePH in all cases, but is outperformed by STMH in most cases. However, this does not mean that STMH is better than DCMH, because the recall of STMH is very poor. For example, assume there are 10,000 ground-truth similar points for a query on MIRFLICKR-25K. If we use an image query to retrieve text database with a Hamming radius 0, STMH only returns 3 points. However, our DCMH method can return nearly 580 points and 487 of them are ground-truth similar points. Hence, DCMH is more practical than STMH in real applications. From this perspective, F-measure is a more meaningful metric than precision and recall in the hash lookup procedure, and our DCMH achieves the best F-measure on all cases.

Please note that we only report the results when the code length is 16 due to space limitation. Our DCMH can also achieve the best performance on other cases with different number of code length. Furthermore, our DCMH is not sensitive to hyper-parameters $\gamma$ and $\eta$ when they are from the range $[0.5,2]$. All these experiments can be found in the supplementary materials.

Conclusion

In this paper, we have proposed a novel hashing method, called DCMH, for cross-modal retrieval applications. DCMH is an end-to-end learning framework which can perform feature learning from scratch. To the best of our knowledge, DCMH is the first cross-modal hashing method which can perform simultaneous feature learning and hash-code learning in the same framework. Experiments on two datasets show that DCMH can outperform other baselines to achieve the state-of-the-art performance in real applications.

References