Semantic Topic Multimodal Hashing for Cross-Media Retrieval

1 Introduction

With the rapid development of the Internet and multimedia devices such as smart phone, tablet computer, and digital camera, tremendous amounts of multimedia data including texts, images, and videos have been easily obtained. It is common that relevant multimedia data from different media types may have semantic correlations. For example, a microblog in Facebook often consists of a short text and some correlative images; a video in YouTube is always associated with some related descriptions or tags. As semantic information inherently consists of data with different modalities, it gives rise to an emerging demand to study and explore the interactions between multimodal data for the applications like cross-media retrieval [Zhai et al., 2013], image annotation [Weston et al., 2011], and recommendation system [Bedi et al., 2007]. Multimodal hashing methods, which map heterogeneous data points into a common low-dimensional Hamming space, have recently received considerable attentions to address cross-modality similarity search problem. The core problem of multimodal hash codes learning is how to construct the underlying correlations between the multiple modalities and preserve the similarity relationships in each individual modality. Generally, multimodal hashing methods can be divided into two categories: graph based methods and matrix decomposition based ones.

Graph based multimodal hashing methods construct similarity graph for each individual modality to preserve the intra-modal similarities and simultaneous concatenate multiple modality-specific binary codes to preserve the inter-modal similarities for the final hash codes. The learning problems often can be converted into eigen-decomposition problems by means of relaxation. Cross-view hashing (CVH) [Kumar and Udupa, 2011] extends spectral hashing (SH) [Weiss et al., 2009] to the multimodal setting by maximizing the weighted average correlations between data pairs through solving a generalized eigenvalue problem. However, CVH treats the correlations between inter-classes and intra-classes in the same way and such strategy often results in poor performance as the differences between the modalities are ignored. Inter-media hashing (IMH) [Song et al., 2013] takes the differences between multiple modalities into consideration. It first explores the correlations within each single modality according to similarity graph and then keeps the binary codes of the paired data points with different modalities consistent. However, IMH needs to construct the similarity matrix for all the data points, which will lead to a large computational complexity for large-scale data set. Linear cross-modal hashing (LCMH) [Zhu et al., 2013] avoids the large-scale graph construction by representing training data with a small number of cluster centers. Nevertheless, how to choose appropriate cluster centers of massive data set is a difficult problem as the performance of LCMH is sensitive to the number of clusters. Generally, those graph based multimodal hashing methods have two drawbacks. Firstly, considerable computational complexity for computing similarity graph leads to long training time. Secondly, eigen-decomposition process decreases the mapping quality substantially when increasing the number of bits, since most of the information is contained in the top few eigenvectors.

Matrix decomposition based multimodal hashing methods seek latent low dimensional spaces to well reconstruct multimodal data and quantify the reconstruction coefficients to obtain the binary codes. Such kinds of methods can avoid the large scale graph construction and eigen-decomposition. Collective matrix factorization hashing (CMFH) [Ding et al., 2014] learns the unified hash codes by collective matrix factorization with latent factor model from different modalities of one instance. However, it assumes that each view of one instance generates identical hash codes. This identical constraint is too restrictive which only guarantees the consistence of pairwise data points but ignores the cross correlationship between different pairwise data points. Latent semantic sparse hashing (LSSH) [Zhou et al., 2014] uses sparse coding and matrix factorization to learn the latent spaces and then merges the learned latent features to generate binary codes. As sparse coding results in long training time consuming, LSSH cannot fully utilize all the training data to learn the model, thus will deteriorate the accuracy.

Although the above multimodal hashing methods have achieved promising results in multimodal applications, these methods often discard the discrete constraints of hashing to solve a relaxed problem and afterwards round the continuous solutions to get the binary codes. Whereas, such continuous relaxation scheme will cause large quantization error consequently deteriorate search performance especially for long codes length. To this end, we design a novel multimodal hashing model, namely semantic topic multimodal hashing (STMH), which focuses on the binary nature of hashing, to facilitate the large-scale cross-media retrieval for multimedia data sources with texts and images. As illustrated in Figure 1, STMH represents text in (a) as multiple semantic topics in (c) and image in (b) as multiple semantic concepts in (d). After represented both texts and images in latent semantic spaces, STMH transforms the learned multimodal semantic features to a common subspace by their semantic correlations. Finally, it generates the unified hash codes directly by figuring out whether a topic or concept is contained in a text or an image. The contributions of the proposed model are summarized as below:

• The proposed method explicitly considers the implication and preserves the discrete nature of the hash code. Each bit of hash code represents whether a text or an image contains the corresponding topic or concept. By focusing on the binary nature, STMH is more suitable for hashing learning scheme and achieves better search performance.
• We develop a fast and efficient method which learns latent topics from texts and the unified hash codes simultaneously.
• By using ℓ2,1-norm to learn the robust salient concepts of images, the proposed method can achieve better robustness against noisy and unreliable image data.

The rest of this paper is organized as follows. Section 2 introduces the proposed STMH model and its multiple modalities extension. Experimental results and comparisons on two benchmark data sets are presented in Section 3. Finally, the conclusions are given in Section 4.

(c) Latent Topics of Text

(d) Latent Concepts of Image

Figure 1: An illustration of topics and concepts for text and image about scenery of Santorini fromWikipedia.

2 Semantic Topic Multimodal Hashing

This section details the proposed STMH model. We firstly introduce STMH to bimodal instance consisting of images and texts as they are the most common-used and important modalities in multimedia. Without loss of generality, it can be easily extended to cases with more modalities.

2.1 ProblemFormulation

Suppose that O={oi}ni=1 , oi =(xi, yi) is a set of multimodal objects, where xi ∈ Rm is a m-dimensional image feature, and yi ∈Rd is a d-dimensional text feature (usually, m̸=d). Given the bits length k, the purpose of STMH is to learn an integrated binary code hi ∈ {0, 1}k for oi, i = 1, 2, · · · , n, such that hi and hj preserve the semantic similarity between oi and oj with high probability. More specifically, if oi and oj are two objects have similar semantic, hi and hj should have a small Hamming distance, and vice versa.

2.2 Semantic Modeling

Semantic information usually can be extracted from a large data set by the topic model [Blei, 2012]. The basic idea of the topic model [Blei et al., 2003; Blei, 2012] is that data are represented as random mixtures over an underlying set of topics, where each topic is characterized by a distribution over words. There are at least two advantages of modeling data as a set of topics for retrieval. Firstly, it offers a highlevel abstraction which can remove redundant information or noise and highlight the important information for complex data. Secondly, the data can be described by a small number of semantic topics which make the computation of the semantic similarity between a data-pair fast and accurately. Motivated by topic models, STMH discovers latent semantic topics in texts and explores latent semantic concepts in images.

Semantic Topic Modeling for Text

To extract the semantic topics, the paper discovers latent topic patterns via a way like cluster analysis. And texts are projected to the latent topic space formed by cluster centers.

Then a text can be described as the topic distribution which can be easily represented by hash codes. When a topic is contained in a text, the corresponding hash code is 1, and otherwise 0.

Let Y be a set of d-dimensional text features, i.e., Y = [y1, y2, · · · , yn] ∈ Rd×n , H be the corresponding unified hash codes for O, i.e., H = [h1, h2, · · · , hn] ∈ Rk×n , and F be a set of d-dimensional latent semantic topics, i.e., F= [f1, f2, · · · , fk]∈Rd×k . The semantic topic modeling for text is

where hij is the i-th element of hj and c is a positive integer less than k which denotes how many "1" lies in hj. In this paper, c is set to k/2 to balance partition binary codes in order to maximize the information of each bit. Eq. (1) is used to simultaneously learn the latent semantic topics and determine the closely related topics for a text adaptively.

Note that when each fi in Eq. (1) has equal value, which means all the topics are the same, then the corresponding hash codes will randomly distribute. Therefore, the semantic similarities between texts will cannot be reflected by hash codes. To avoid this case, we consider to add the diversity regularization term of topics. Let hi denotes the i-th row of hash codes H, then it represents the distribution of the i-th topic fi on the text set Y. If hi is in close proximity to hj , i, j∈1, 2, · · · , k, i̸=j, the value of hi (hj )T will be large, and fi and fj will be similar to each other with high probability. To avoid fi and fj equal to each other, we add the diversity regularization term of topics as follows.

where

fi T fj is the dot-product similarity metric which has been widely used in text analysis [Cai et al., 2011]. Therefore, it is quite natural to use dot-product similarity metric for topics. When wij has a relatively large value, it means that the distributions of topics fi and fj are similar to each other. To minimize Eq. (2), fi T fj should be small, then topics fi and fj should be different from each other. Therefore, the diversity of topics is increased.

Accordingly, the overall objective function for text semantic modeling can be obtained by combining Eqs. (1) and (2)

By minimizing Eq. (4), the latent semantic topics for text and the corresponding hash codes will be learned simultaneously.

Semantic Concept Modeling for Image

Compared with text, the high-level semantic concepts hidden in the image are more difficult to extract. Here, we use matrix factorization to discover semantic concepts in image. Matrix factorization which learns a latent low dimensional space to well reconstruct the original data, is one of the most useful tools for learning latent concepts from image [Lee and Seung, 1999; Zhou and Tao, 2011]. However, the standard matrix factorization often uses the least square error function which is well known to be unstable w.r.t. noise and outliers [Kong et al., 2011]. Meanwhile, large scale multimedia data sets collected from the Internet often inevitably contain noise and outliers. Therefore a robust version of matrix factorization is demanded to learn salient concepts of images. For this reason, ℓ2,1-norm loss function [Ding et al., 2006] is introduced to design a robust matrix factorization. ℓ2,1-norm is defined for a matrix A=[a1, a2, · · · , an]∈Rp×n as

Compared with ℓ2-norm, ℓ2,1-norm does not square the reconstruction error of each sample ai. Therefore, the objective function in Eq. (5) is expected to be robust to noise and outliers.

Let X be a set of m-dimensional image features, i.e., X = [x1, x2, · · · , xn] ∈ Rm×n , the proposed robust matrix factorization can be formulated as

where U=[u1, u2, · · · , uk]∈Rm×k , V=[v1, v2, · · · , vn]∈ Rk×n , and k is the length of the hash codes. By robust matrix factorization, each image feature xj is approximated by a linear combination of the columns of U, weighted by the components of vj. Then, U can be regarded as containing some semantic concepts and each image can be regarded as the linear combination of those concepts.

Note that in general, the cost function of ℓ2,1-norm form in Eq. (6) is harder to solve than the ℓ2-norm form. Then we rewrite Eq. (6) as

where DX is a diagonal matrix with the j-th diagonal element given by

Therefore, the overall objective function for image concept modeling is

By minimizing Eq. (9), the latent semantic concepts and the corresponding coefficients for images will be learned simultaneously.

2.3 Semantic CorrelationMatching

If multimodal data points have the same semantics, they are expected to have a certain common latent space. For example, there are two semantic topics of text in Figure 1 (a) which are the natural landscape and cultural landscape as shown in Figure 1 (c). The relevant image in Figure 1 (b) also has some semantic concepts such as architectures, mountains, sky and sea as shown in Figure 1 (d). The topics of text actually have correlativity with the concepts of the image. For instance, natural landscape topic of text is related to the image concepts mountains, sky and sea. Therefore a topic in a text can be described by several concepts in an image. Accordingly, the cross-correlation for image and text can be formulated as

where P ∈ Rk×k is the correlation matrix between images and texts. By Eq. (10), the coefficients of image can be transformed into hash codes. Then, a text and image pair has the identical hash code which facilities the cross-media retrieval.

2.4 Overall Objective Function

The overall objective function, combining the semantic topic modeling for text given in Eq. (4), the robust matrix factorization for image given in Eq. (9), and the cross-correlation between the latent semantic spaces of image and text given in Eq. (10), is written as below.

(11)

where λ, µ and γ are tradeoff parameters, and R(·)=‖·‖2F is the regularization term to avoid overfitting.

2.5 Optimization Algorithm

The optimization problem in Eq. (11) can be solved by updating the following steps iteratively until convergency or the preset maximum number of iterations is reached.

1. Fix H, U, V, and P, let the derivative of L with respect to F equals to zero, then we obtain

where I is the identity matrix.

2. Fix F, H, V, and P, let the derivative of L with respect to U equals to zero, then we obtain

3. Fix F, H, U, and V, let the derivative of L with respect to P equals to zero, then we obtain

4. Fix F, H, U, and P, let the derivative of L with respect to V equals to zero, then we obtain

where qj is the j-th column of (1-λ)UT XDX +µPT H. 5. Fix F, U, V, and P, we have the following equation to calculate H

Eq. (16) can be solved by calculating hj one by one independently. That is, we need to solve the following problem for hj

where (Pvj)i is the i-th element of vector Pvj and C is a constant. To minimize Eq. (17), we first rank ‖yj - fi‖22 - 2µ/λ(Pvj)i , i = 1, 2, · · · , k, with the order small to large. Then let hij =1 if ‖yj - fi‖22 - 2µ/λ(Pvj)i belongs to the top c minimum values in the ranking list and otherwise hij = 0.

2.6 Out-of-Sample Extension

Text

Let yt ∈Rd×1 be the query text feature, then its hash code ht can be obtained by

where hti is the i-th element of vector ht . It can be solved by ranking ‖yt - fi‖22 , i=1, 2, · · · , k, with the order small to large. And then let hti =1 if ‖yt - fi‖22 belongs to the top c minimum values in the ranking list and otherwise hti =0.

Image

Let xt ∈ m×1 be the image query feature, then its hash code ht can be obtained by first embedding it to the semantic concept space U by

Then transform vt to the hash space by

where sign(·) denotes the sign function and median(·) denotes the median function.

We summarize the procedures for STMH in Algorithm 1.

Algorithm 1 Semantic Topic Multimodal Hashing

Training:

Input: Images X, texts Y, parameters λ, µ, and γ, bit length k.

Output: Hash codes H, matrices F, U, and P. Procedure:

1. Initialize F, H, U, V, and P;

1. Repeat
2. Compute DX with Eq. (8);

2.2 Fix H, U, V, and P, update F with Eq. (12);

2.3 Fix F, H, V, and P, update U with Eq. (13);

2.4 Fix F, H, U, and V, update P with Eq. (14);

2.5 Fix F, H, U, and P, update V with Eq. (15);

1. Fix F, U, V, and P, update H by solving Eq. (17). until convergency.
2. Return H, F, U, and P.

Testing:

Input: Image xt or text yt , matrices F, U, and P.

Output: Hash code ht .

Procedure:

Text: Get the hash code ht by solving Eq. (18). Image: Get the hash code ht with Eqs. (19) and (20).

2.7 Computational Complexity Analysis

The computational complexity for training STMH is O ((k3 + dk +mk) nt), where t is the number of iterations. As k, d, m and t≪n, the training complexity is linear to the training data size. In the search phase, the complexity is constant with O(dk) for a text query and O(mk) for an image query. In a word, the time complexity for training STMH is linear to n and is constant for testing, which is really scalable for large-scale data sets.

2.8 Multiple Modalities Extension

The extension for STMH in Eq. (11) from bimodal to multiple modalities is quite easy and direct by using semantic topic modeling for one chosen modality and robust matrix factorization for others.

It is straightforward to adapt Algorithm 1 presented above to solve Eq. (21).

3 Experiments

To evaluate the performance of the proposed STMH, we conduct comparison experiments with several state-of-art methods including CMSSH [Bronstein et al., 2010], CVH [Kumar and Udupa, 2011], LCMH [Zhu et al., 2013], IMH [Song et al., 2013], CMFH [Ding et al., 2014], and LSSH

[Zhou et al., 2014], on two real-world datasets, i.e., Wiki1 and NUS-WIDE2 for cross-media similarity search. The retrieval performance is evaluated by mean of average precision (mAP), recall-precision, and topN-precision. Details about data sets processing and evaluation metrics can be referred to [Zhou et al., 2014].

3.1 Experimental Settings

CMSSH, IMH and LSSH require too much computational costs that are quite difficult to learn hash functions on NUSWIDE with all data. Thus, we randomly select 5000 instances from data set for these methods to train hash functions and then apply the trained hash functions to the other instances in data set to generate hash codes for them as [Song et al., 2013] did.

For all the comparison algorithms except LCMH, the codes are kindly provided by the authors. We implemented LCMH as the code is not publicly available. The parameters for all the comparison methods are tuned according to the corresponding literatures. When comparing with the baseline methods, we use the parameter settings, λ=0.5, µ=0.001, and γ=10-4 for STMH.

3.2 Results and Discussions

The mAP values for STMH and six baseline methods are reported in Figure 2. The recall-precision and topN-precision curves are plotted in Figure 3 and Figure 4 respectively.

Results on Wiki

The Wiki data set is separated into two parts, with 2173 pairs for training and 693 pairs for testing. It can be observed that STMH achieves the best performance than baseline methods on text-query-image similarity search task. And the performance for STMH on image-query-text task although does not always achieve the best performance, it achieves comparable performance to the best. As shown in Figure 4, we can find that STMH achieves better performance on the top 400 retrieved instances. In retrieval system, the top retrieved instances often need high accuracy as users care more about the front instance in the retrieved list. From this point of view, STMH can achieve relatively good performance on imagequery-text task.

Results on NUS-WIDE

We randomly choose 1K images with their tags to serve as the test set and the rest images and tags are serving as the training set in NUS-WIDE data set. As the results show, STMH outperforms baseline methods significantly which verifies that it can better model the complex structure of large-scale data set by their latent semantic topics and reduce the semantic gap between heterogeneous data compared with state-of-the-art methods. Furthermore, STMH achieves higher mAP values with longer codes. This is reasonable as longer hash codes can encode more semantic information and therefore can improve the retrieval accuracy. As NUS-WIDE data set is quite similar to real-world scenario, experimental results show that STMH can handle large-scale multimodal similarity search problem.

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

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

3.3 Parameter Sensitivity Analysis

The empirical analysis on parameter sensitivity is given in this section. The analysis is conducted for one parameter by varying its value while fixing the other parameters.

The parameter µ controls the connection of latent semantic spaces between image and text. If it is too large, the strong connection will affect the learning of latent semantic topics of texts and images. However, if it is too small, the connection between different modalities is weak which will result in poor performance for cross-modality similarity search. It is reasonable to choose proper value of µ from the range of [0.0001, 0.01].

The parameter γ controls the complexity of the model. The model is over-fitted with too small value while under-fitted with too large value. It can be observed from Figure 5 that STMH can achieve stable performance under a wide range of γ. Usually, it can be chosen from the range of [0.0001, 0.1].

From the above analysis, we can reach the conclusion that STMH can achieve stable performance under a wide range of parameter values.

4 Conclusions

In this paper, we presented a novel multimodal hashing method, referred to as semantic topic multimodal hashing (STMH), for large-scale cross-media similarity search. Specifically, STMH models text as multiple semantic topics and image as latent semantic concepts and learns the relationship of text and image in their latent semantic spaces. Then, each bit of unified hash code can be generated directly by figuring out whether a topic or concept is contained in a text or an image. By maintaining the discrete nature of hashing, STMH is more suitable for hashing learning scheme and can obtain better retrieval performance. Comparative studies on two bench-mark datasets show that STMH outperforms the state-of-the-art multimodal hashing methods. In future work, we will explore more efficient semantic information to further improve the performance of STMH.

Acknowledgments

This paper was supported partially by the National Natural Science Foundation of China (Grant Nos. 61125204, 61432014, 61472304, and 61172146), the Fundamental Research Funds for the Central Universities (Grant Nos. BDZ021403 and JB149901), the Program for Changjiang Scholars and Innovative Research Team in University of China (No. IRT13088), the Shaanxi Innovative Research Team for Key Science and Technology (No. 2012KCT-02) and the Project Funded by China Postdoctoral Science Foundation (No. 2014M562378).