Parametric Local Multimodal Hashing for Cross-View Similarity Search

1 Introduction

The problem of similarity search is encouraged in many engineering and science applications, ranging from information retrieval, data mining, and computer vision. Many tasks such as content-based retrieval, object recognition and nearduplicate detection, depend critically on the choice of an effective and efficient similarity search strategy. To confront with the scalability issue in massive data, hashing-based

The appealing property of hashing methods is they index data with binary hash codes which enjoy not only the compactness of the representation but also the low complexity in distance computation. By utilizing hash codes, we can achieve fast search with constant or sub-linear time complexity [Norouzi et al., 2012] and greatly decreased storage cost.

Early exploration of hashing is data-independent [Andoni and Indyk, 2006; Lv et al., 2007]. However, these methods require long codes to achieve good precision, which will result in low recall as the collision probability decreases exponentially with the code length. Recent endeavors aim at data-dependent hashing by employing machine learning techniques to learn the hash functions for specific datasets. This new direction is also referred to as hash function learning (HFL). Some representative HFL works include semantic hashing [Salakhutdinov and Hinton, 2007], spectral hashing [Weiss et al., 2008], and kernel-based supervised hashing [Liu et al., 2012], etc.

Existing HFL methods have been applied to a wide range of real-world applications with great success. Nevertheless, most algorithms deal with data lying in a single-view observation space, i.e., unimodal hashing. Nowadays, it is common to conduct similarity search across different modalities. For instance, a multimedia search engine may perform queries in a corpus consisting of texts and images [Rasiwasia et al., 2010; Chua et al., 2009]. One may query image datasets by text keywords to quickly draw a vivid imagination, or query text datasets by images to accurately describe the details. Consequently, multimodal HFL, which learns different hash functions for different modalities to enable cross-modal comparison, is a very worthwhile direction to explore. This motivates the study reported in this paper.

Multimodal HFL is a challenging task, since different observations generally have different representations with incommensurable structure and dimensionality. Up to now, only a few attempts have been made for multimodal hashing [Zhen and Yeung, 2012a; Kumar and Udupa, 2011; Bronstein et al., 2010; Zhen and Yeung, 2012b]. Bronstein et al. first put forward multimodal HFL method, called crossmodal similar sensitive hashing (CMSSH) [Bronstein et al., 2010], which constructs two groups of linear hash functions (for bimodal case) sequentially based on a standard boosting framework. Later, Kumar et al. present another method called cross-view hashing (CVH) [Kumar and Udupa, 2011] which essentially extends spectral hashing to the multi-view setting. The main idea of CVH is to find view-specific linear projections as hash functions so that similar objects are mapped to similar binary codes across all of views. More recently, Zhen et al. present co-regularized hashing (CRH) [Zhen and Yeung, 2012a] for multimodal data based on a boosted co-regularization framework. The hash functions for each bit of hash codes are learned by solving DC (difference of convex functions) programs, while the learning for multiple bits is carried out via a boosting procedure.

The above multimodal HFL methods have achieved promising results in several applications, but they still have some limitations. First, these methods are all limited to a relatively narrow class of globally linear multimodal HFL that often cannot capture well the structure of the data for each modality. Although it is claimed that nonlinear hash functions could be achieved via the kernel trick [Sch¨olkopf and Smola, 2001], the choice of both the problem-dependent kernel function and its parameters is still a sticky problem. Moreover, the nonlinearity is performed in a global way since the induced kernel function with the same parameters is generally applied to all data pairs in each view. Second, both CMSSH and CVH treat each bit independently, which results in finding unnecessary long hash codes. Besides, CMSSH ignores the intra-modality similarities which are very useful in some cases [Weiss et al., 2008], while CRH does not consider the correlation within each modality in defining the intra-modality loss. A recent work, called multimodal latent binary embedding (MLBE) [Zhen and Yeung, 2012b], takes a probabilistic generative approach to solve the multimodal hashing problem. MLBE regards the binary latent factors as hash codes, and the learning of binary latent factors corresponds to hash function learning. MLBE alleviates the weaknesses of global linearity in each modality and bit independence in hash codes, and actually shows superior performance against most previous methods when the bit number is small. However, MLBE still has limitations on the restrictive global intra-modality weighting matrices involved in the probabilistic model. Moreover, since there are no explicit projections learned frommultimodal inputs to presigned hash codes, MLBE suffers from the high computation complexity for the out-of-sample extension.

Actually, as pointed out by Bottou and Vapnik [Bottou and Vapnik, 1992], it is usually not easy to find a unique function which holds good predictability in the entire data space. Especially, very often a global hash function cannot accurately model the complex structure of large-scale datasets in which discriminative features vary from one neighborhood to the other. Vapnik [Vapnik, 1995] further demonstrate that local learning based algorithms usually achieve lower empirical errors than global ones. This is because nearby instances are more likely generated by the same data generation model, while far away instances tend to differ in it. Accordingly, neighboring instances may have the same or similar hash functions, while for instances lying away in different neighboring spaces their hash functions change heavily. Consequently, it is more ideal to learn a set of local multimodal hash functions which sufficiently boost the modeling ability.

In this paper, we propose a novel multimodal HFL method, called Parametric Local Multimodal Hashing (PLMH), which learns a set of local hash functions for each modality space. Different local hash functions are learned at different locations of the input spaces, therefore, the overall transformations of all points in each modality are locally linear but globally nonlinear. To reduce the computational complexity, the projection matrix of each instance is approximated as a linear combination of basis projections of a small set of anchor points, with guaranteed approximation error bound. For each bit of hash codes, we use the local optimal conjugate gradient method to optimize the relaxed objective function which preserves both intra-modality and inter-modality similarities. PLMH learns bits of hash codes in a sequential manner so that the bias introduced by antecedent hash functions can be sequentially minimized, and the dependence between bits is explored at the same time.

The rest of this paper is organized as follows. In Section 2, we present the PLMH method in detail, followed by a short discussion. Experiments analysis are presented in Section 3. Finally, Section 4 gives some conclusion remarks.

2 Parametric Local Multimodal Hash Function Learning

In this section, for simplicity of our presentation, we give a description on the bimodal case as an example, but it is very easy to extend the proposed method to more general cases including more than two modalities.

2.1 Local Hash Functions

Suppose that there are two sets of data points from different modalities: X = {xi ∈ Rdx }Ii=1 for a set of I images and Y = {yj ∈ Rdy }Jj=1 for a set of J textual documents. Each data point xi(yj) is located in the dx(dy) dimensional input feature space. We also have an inter-modality similarity matrix Sxy ∈ {±1, 0}I×J , where +1 and -1 denote similar and dissimilar relationships respectively, and 0 indicates the corresponding entries are not observed. In addition, two symmetric intra-modality similarity matrices Sx ∈ RI×I and Sy ∈ RJ×J are constructed to reflect the local geometric structures of data in each input feature space.

We solve the problem of generating K-bit hash codes through parametric local multimodal hash functions learning. Specifically, two sets of local hash functions are defined as:

where sgn(·) denotes the element-wise sign function, Wi ∈ Rdx×K andWj ∈ Rdy×K are the instance-specific projection matrices. Note that the projection matrix is defined for each individual data point but not shared by all data points globally in each view. The overall transformations of all points are locally linear but globally nonlinear. As a result, different local hash functions are learned at different locations of the input space for each modality.

To balance locality and computational efficiency, we propose to approximate the projection matrix for each point instead of directly learning it. Specially, inspired by local coordinate coding (LCC) [Yu et al., 2009], we parameterize the local projection matrixWi as a linear weighted combination of a small set of projection basis associated with a set of anchor points:

Here, Cx = {xa1 , . . . , xam } represents the set of anchor points, where {ak}mk=1 are the indices of the anchor points in X, and m = |Cx|. The vector of combination weights is denoted as γ(xi) = [γa1 (xi), . . . , γam (xi)]T . That is, the weights are decided locally by the anchor points. Both Cx and γ(·) are unknown parameters to be learned by our algorithm. Similarly, we can represent the set of anchor points and the combination weights for the projection matrix of each data point in Y as Cy = {yb1 , . . . , ybm } and θ(yj) = [θb1 (yj), . . . , θbm (yj)]T .

The feasibility and error bound of the above parameterizations can be verified. To this end, we rewriteWi as a vectorvalued function: h(xi) = vec(Wi), where vec(·) denotes the operator to convert a matrix into a vector in a columnwise manner. It can be proved that h(·) is a Lipschitz smooth function according to the following definition.

Definition 2.1 Lipschitz Smooth Vector-Valued Function [Wang et al., 2012a]: A vector-valued function h(x) on Rdx is a (α, β, p)-Lipschitz smooth function with respect to a vector norm || · ||, if ||h(x) - h(x′ )|| ≤ α||x - x′ || and ||h(x) - h(x′ ) - ∇h(x′ )T (x - x′ )|| ≤ β||x - x′ ||1+p , where ∇h(x′ ) is the derivative of the function h at x′ , α, β > 0 and p ∈ (0, 1].

It has been shown in [Yu et al., 2009] and [Wang et al., 2012a] that any Lipshitz smooth real-valued and vectorvalued functions can be approximated as a linear combination of the function values on the anchor points. Based on these results, we have the following lemma that gives the error bound for Eqn. (2).

Lemma 2.1 Error Bound for Approximated Local Hashing Projection: Suppose the projection matrix Wi is approximated by a set of local projection basis as in (2), parameterized by Cx and γ(xi). We have the following relationship for all xi ∈ X:

Due to the space limitation, the proof of the above Lemma is omitted here.

Based on the verified local parameterization defined above, the local hash functions could be further formulated with respect to the projection basis as follows:

where Wx=[Wa1 ; · · · ;Wam ] and Wy=[Wb1 ; · · · ; Wbm ] are the concatenated basis projection matrices, I is the identity matrix, and ⊗ represents the kronecker product. This transformation can be regarded as an explicit kernel projection of data in a dx(dy)-dimensional space to a higher mdx(mdy)-dimensional space expanded by anchor points.

To obtain the anchor points and the weights for all instances, a straightforward manner is to formulate it as an optimization problem by minimizing the reconstruction error bound in Eqn. (3) as that in LCC method [Yu et al., 2009]. However, solving such an optimization problem is computationally expensive. Alternatively, we adopt a much more efficient and practical method in our experiments. We simply set the anchor points as the outputs of k-median (setting k = m) algorithm and compute the corresponding weights using inverse Euclidian distance [Gemert et al., 2008] based weighting for nearest neighbors. Empirical results show that this does not lead to a decrease of the performance compared with minimizing codings [Yu et al., 2009].

2.2 Objective Function

In devising the multimodal HFL algorithm, two important issues should be taken into consideration: (1) The intermodality pairs with the same (or similar) semantic concept should be mapped to the same hash bin, and vice versa. (2) The intra-modality local topological structures should be preserved, which forces points with high similarity to have similar binary codes in the hamming space for each modality.

We propose to achieve the overall objective by minimizing the following energy function w.r.t. {Wak }mk=1 and {Wbk }mk=1 :

where ℓxy ij is the pairwise inter-modality loss term, ℓxii′ and ℓyjj ′ are the pairwise intra-modality loss terms for modalities X and Y, respectively. μ is the regularization parameter to balance these two kinds of loss terms. In this work, we define inter-modality loss term as:

where Sxy represents the inter-modality similarity matrix. Inspired by Laplacian eigenmap [Belkin and Niyogi, 2003], the pairwise intra-modality loss terms ℓxii′ and ℓyjj ′ are defined as:

where Sx and Sy are the intra-modality similarity matrices.

Note that the inner product of the hashing code of each instance always equals to the constant hash number, meaning:

By neglecting the constant term, the minimization problem in (5) equals to maximizing the following objective function:

where X = [(γ(x1) ⊗ I)x1, · · · , (γ(xI) ⊗ I)xI], and Y = [(θ(y1) ⊗ I)y1, · · · , (θ(yJ ) ⊗ I)yJ ].

2.3 Optimization Solutions

Maximizing Eqn. (6) is a non-trivial problem since the objective function is neither convex nor smooth. It is observed that the same sign is more favored for similar pairs and different signs are more favored for dissimilar pairs, regardless of their magnitudes. As a result, J can be approximated by replacing the sign of projections with the signed magnitude:

Finally, we impose an additional constraint to achieve the scaling invariance and bits decorrelation, and solve the optimization problem of local hash functions by maximizing:

Although the optimal solutions can be derived directly by solving an eigen-decomposition problem ZSZT W= λZZT W in theory, it is rather time consuming and storage prohibitive to optimize all parameters simultaneously in practice. To be more efficient, we propose to learn the hash functions for each bit of hash codes via the local optimal conjugate gradient method. Rewrite Wx and Wy as Wx = [w1x , · · · ,wK x ] and Wy = [w1 y , · · · ,wK y ]. Let Zk-1 be the updated data matrix after removing the spanned subspace generated from previous k-1 projection directions. The details of solving one-bit multimodal hash functions are described in Algorithm 1.

Algorithm 1 One-bit multimodal HFL via conjugate gradient

Output: wkx and wk

Procedure:

1. For i = 0, · · · , until convergence

1. Search the step size ζ i via Rayleigh-Ritz method;

End for

To learn the hash functions for multiple bits, we propose to generalize the sequential learning process (SLP) [Wang et al., 2012b] for local multimodal HFL to progressively minimize the bias introduced by antecedent hash functions. The overall procedure of PLMH method is represented in Algorithm 2. At each iteration, both the intra and inter similarities are updated (Step 3.2-3.3) by imposing higher weights on point pairs violated by previous hash functions (i.e., the condition in Step 3.3), and the data matrices in constraint term are also updated (Step 3.4-3.5) to decorrelate the hash bits for compact codes. Since the original data matrices are still exploited in the objective function term (to compute matrix E in Algorithm 1), SLP tends to progressively pick the hash projections with high empirical accuracy as well as low correlation

y

Algorithm 2 Parametric Local Multimodal Hashing (PLMH)

Input:

X, Y: multimodal data

Sxy , Sx(y) : inter-modality and intra-modality similarity μ: regularization parameter

K: code length

Output:

Procedure:

1. Compute X and Y in Eqn. (6); set Z0 = Z;
2. For k = 1 to K do
3. Optimize wkx and wk y via Algorithm 1;
4. Compute the similarity of current hash projections: ˜Sx = XT wkx (wkx )T X, ˜Sy = YT wk y (wk y )T Y, and ˜Sxy = XT wkx (wk y )T Y;
5. Update the similarity matrices:

1. Compute the residual of data matrix:

End for

on data sets. If the empirical accuracy and bits decorrelation contradict each other, the algorithm trades decorrelation for accuracy by picking correlated projections. Consequently, the sequential process also implicitly creates the dependency between bits.

2.4 Complexity Analysis and Discussions

The computational cost of the proposed algorithm is mainly on three modules: local coding (Step 1-2), one-bit multimodal HFL (Step 3.1), and sequential learning update (Step 3.2-3.5). For the stage of local coding, the time complexity is linear with the number of data points. For the stage of one-bit multimodal HFL, the computationally expensive part is on evaluating the conjugate gradient, with the time complexity O(D2xNSx + D2 yNSy + DxDyNSxy + D2x I + D2 y J ), where Dx(y)=mdx(y), NSx(y) and NSxy are the number of observations in the intra-modality and inter-modality similarities, respectively. Since in general the similarity matrices are sparse, the complexity for conjugate gradient can be greatly reduced. For the stage of sequential learning update, the complexity is O(DxI +DyJ +NSx +NSy+NSxy). To summarize, the time complexity of our algorithm scales linearly with the number of data points and is quadratic with the data dimension. Thus the proposed algorithm is computationally efficient as long as the dimensions of input features are not exceptionally large.

It is worth mentioning that our work is also closely related to two recent works, locally linear support vector machines (LLSVM) [Ladicky and Torr, 2011] and parametric local metric learning (PLML) [Wang et al., 2012a], which share the same idea of local learning. However, there are several significant differences between the proposed method and them. First, our method aims to do multimodal hashing, while LLSVM is developed for classification and PLML is for continuous Mahalanobis metric learning. Second, LLSVM and PLML are designed for dealing with data in a single view observation space, which is quite different from the multi-view scenarios of interest here. Third and more importantly, the strategy of local learning proposed in our method is totally different from that of LLSVM and PLML.

3 Experiments

Empirical studies are conducted on cross-media retrieval application for two typical tasks: (1) querying image database by text keywords; (2) query text database by image examples.

We evaluate the performance of the proposed PLMH method, and compare it with four state-of-the-art multimodal HFL methods: (1) CMSSH [Bronstein et al., 2010]; (2) CVH [Kumar and Udupa, 2011]; (3) CRH [Zhen and Yeung, 2012a]; (4) MLBE [Zhen and Yeung, 2012b]. 1

The retrieval performance is evaluated by mean Average Precision (mAP). For each query and a set of R retrieved documents, we first compute the Average Precision (AP). We then average the AP values over all the queries in the query set to obtain the mAP measure. The larger the mAP, the better the retrieval performance. In the experiments, we set R = 50. Moreover, we also report the precision-recall curve and recall curve by varying the Hamming radius of the retrieved points.

For PLMH, the intra-modality similarity matrices are computed as s = e-d2 /2σ2 within 8 nearest neighbors (8NN), where d is the Euclidean distance between two normalized feature vectors, and σ2 is fixed to 1 for both data sets. The inter-modality similarity matrices are simply determined by the class labels with 0.1% randomly selected entries observed. Besides, 20 and 50 anchors points of each modality are generated with k-median clustering for flickr and wiki datasets, respectively 2 . The weights of local coding are simply obtained using inverse Euclidian distance [Gemert et al., 2008] based weighting solved for 8NN. The regularization parameter μ is set to 1.

In experiments, 3000 instances are randomly selected as the training set from the database for each modality. All comparison methods adopt the same training data for fairness.

3.1 Results onWiki

The Wikipedia dataset [Rasiwasia et al., 2010] from the Wikipedia's "featured articles", consists of 2866 documents which are image-text pairs and annotated with labels of 10 semantic categories. Each image is represented w.r.t. a 128dimensional SIFT [Lowe, 2004] codebook and each text is represented with a 10-dimensional latent dirichlet allocation model [Blei et al., 2003]. We use 80% of the data as the database and the remaining 20% to form the query set.

1 The codes of these methods are provided by the authors.

2 More complex problems will often require a larger number of anchor points to better model the complex structure of the data.

The mAP results are summarized in Table 1 with various code lengths. The precision-recall curves and recall curves are illustrated in Figrue 1 3 . From the results, we can see that PLMH outperforms all comparative studies under all settings. Benefiting from the local hash functions, PLMH method achieves higher empirical accuracy than the global based ones.

Table 1: mAP comparison on Wiki

Task	Method	Code Length
		K = 8	K = 16	K = 24
Image Query v.s. Text Database	CMSSH	0.1988	0.1973	0.1785
	CVH	0.2758	0.2134	0.1843
	CRH	0.2956	0.2714	0.2607
	MLBE	0.3175	0.2507	0.2736
	PLMH	0.4435	0.4916	0.5516
Text Query v.s. Image Database	CMSSH	0.1912	0.2128	0.1977
	CVH	0.3342	0.2893	0.2839
	CRH	0.3260	0.3222	0.3407
	MLBE	0.4414	0.2977	0.2869
	PLMH	0.5976	0.6073	0.6011

3.2 Results on Flickr

The Flickr dataset contains 186,577 image-tag pairs from the 10 largest classes of NUS dataset [Chua et al., 2009]. Each image is represented with a 500-dimensional SIFT codebook and each tag is represented with a 1000-dimensional feature vector which is reduced by PCA on original tag occurrence features. We use 99% of the data as the database and the remaining 1% to form the query set.

Table 2: mAP comparison on Flickr

Task	Method	Code Length
		K = 8	K = 16	K = 24
Image Query v.s. Text Database	CMSSH	0.4612	0.4724	0.5103
	CVH	0.5287	0.5000	0.4461
	CRH	0.5385	0.5290	0.5393
	MLBE	0.5394	0.5235	0.4805
	PLMH	0.5987	0.5976	0.5975
Text Query v.s. Image Database	CMSSH	0.5277	0.5133	0.4588
	CVH	0.5259	0.4949	0.4491
	CRH	0.5225	0.5217	0.5244
	MLBE	0.5542	0.5293	0.4852
	PLMH	0.5701	0.5947	0.5985

Similar to previous subsection, we show the mAP results in Table 2, the precision-recall curves and recall curves in Figure 2. We can find that PLMH achieves the best overall performance. It further verifies that the proposed local hash functions learning is more robust and can better model the complex structure of large-scale datasets compared with state-of-the-art methods.

3 Due to space limitation, only K = 8, 16 are shown in Figrue 1.

Text Query vs. Image Database

CMSSH

CVH

CRH

MLBE

PLMH

0

0.5

1

0.7

0.6

0.5

0.4

0.3

0.2

1

0.8

0.6

0.4

0.2

Recall

(b) K = 8

Text Query vs. Image Database

CMSSH

CVH

CRH

MLBE

PLMH

0

0.5

1

Recall

(f) K = 16

Image Query vs. Text Database

CMSSH

CVH

CRH

MLBE

PLMH

0

1

2

3

4

1

0.8

0.6

0.4

0.2

0

1

0.8

0.6

0.4

0.2

0

0

No. of Retrieved Points

(c) K = 8

x 10 8

Image Query vs. Text Database

1

2

CMSSH

CVH

CRH

MLBE

PLMH

3

4

No. of Retrieved Points

(g) K = 16

x 10 8

Figure 2: Precision-recall curves and recall curves on Flickr

outperforms the state-of-the-art multimodal hashing methods. In future work, we will explore more efficient optimization algorithms to further improve the scalability of PLMH.

Acknowledgement: This work was supported by the Major State Basic Research Development Program of China (973 Program) under Grant 2009CB320900, the National Science Foundations of China under Grant 61272319, and the new Ph.D researcher award of Chinese Ministry of Education.

Precision

Precision

0.7

0.6

0.5

0.4

0.3

0.2

Image Query vs. Text Database

CMSSH

CVH

CRH

MLBE

PLMH

0

0.5

1

1

0.8

0.6

0.4

0.2

Recall

(a) K = 8

Image Query vs. Text Database

CMSSH

CVH

CRH

MLBE

PLMH

0

0.5

1

Recall

(e) K = 16

4 Conclusions

In this paper, we presented a new parametric local multimodal hashing (PLMH) method for cross-view similarity search. Different local hash functions are learned at different locations of the input spaces to better model the complex structure of large-scale datasets. As a result, PLMH achieves higher empirical query accuracy than global-based ones. Comparatives studies on two benchmark datasets show that PLMH

Precision

Precision Recall Recall Recall Recall

1

0.8

0.6

0.4

0.2

0

Text Query vs. Image Database

0

1

2

CMSSH

CVH

CRH

MLBE

PLMH

3

4

1

0.8

0.6

0.4

0.2

0

0

No. of Retrieved Points

(d) K = 8

x 10 8

Text Query vs. Image Database

1

2

CMSSH

CVH

CRH

MLBE

PLMH

3

4

No. of Retrieved Points

(h) K = 16

x 10 8