Multi-Modal Distance Metric Learning

1 Introduction

Multi-modal data is ubiquitous in web. Especially, with the vast prosperity of social media, data with multiple modalities is enjoying explosive growth. For example, in user-centric social networks (e.g., Facebook, Google Plus), users possess blogs, photos, friends circles. In photo sharing websites (e.g., Flickr, Pinterest), photos can be described by image contents, text tags and meta information like albums and groups. In video sharing website (e.g., Youtube), videos can be characterized by image frames, audio, and user comments. In music social network (e.g., iTunes Ping), songs are accompanied by acoustic features (e.g., rhythm and timbre), semantic features (e.g., tags, lyrics) and social features (e.g., artist reviews) [McFee and Lanckriet, 2011]. Information from dif-

∗The work is done while Pengtao Xie is visiting Carnegie Mellon University.

Eric P. Xing

Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213, USA

ferent sources (text, image, video, audio, meta and social information) jointly reveal the fundamental characteristics of the study subjects from different views.

Choosing a proper distance function or similarity measure for multi-modal data is crucial for many applications, including retrieval [Zhang et al., 2011; Zhen and Yeung, 2012], clustering [Bekkerman and Jeon, 2007; Qi et al., 2012], classification [Nishida et al., 2012] and recommendation [Aizenberg et al., 2012; Baluja et al., 2008]. While various metric learning methods [Xing et al., 2002; Globerson and Roweis, 2006; Weinberger et al., 2006; Davis et al., 2007] defined on single data modality have been proposed, learning distance in the presence of multiple modalities remains largely unexploited. McFee and Lanckriet [2011] applied the multiple kernel learning technique for integrating heterogeneous feature modalities into a single unified similarity space. An ensemble of kernel transformations are learned given the labeled relative similarity comparisons. To our best knowledge, this is the only work regarding multi-modal distance metric learning. However, their method enjoys very limited scalability.

In this paper, we propose a multi-modal distance metric learning framework based on the multi-wing harmonium (MWH) model [Xing et al., 2005] for multi-model integration and the metric learning method by [Xing et al., 2002] for distance supervision. Our method provides a principled way to embed data of arbitrary modalities into a single latent space where distance supervision is leveraged. This MWH is a two-layer random field that jointly models the visible feature modalities and their latent semantic embeddings. Given labeled "similar" and "dissimilar" pairs, we aim to minimize the distance of similar pairs while separating dissimilar pairs with a certain margin in the latent space. The embedding from feature modalities to semantic space is learned by simultaneously maximizing random field induced data likelihood and minimizing distance induced loss, with the goal to reasonably explain data and provide an effective distance metric. The data likelihood provides a natural regularizer to avoid overfitting commonly suffered by most metric learning algorithms. Unlike existing distance metric learning approaches which requires costly semi-definite programming or kernel embedding, our method is highly efficient and scalable.

The rest of the paper is organized as follows. Section 2 introduces related work. In section 3, we propose the multimodal distance metric learning framework based on multiwing harmonium model and present the optimization technique. Section 4 gives experimental results. Section 5 concludes the paper.

2 RelatedWork

Metric learning on single modality has been widely studied in [Xing et al., 2002; Globerson and Roweis, 2006; Weinberger et al., 2006; Davis et al., 2007]. Xing et al [2002] used semidefinite programming to learn a Mahalanobis distance metric for clustering under similarity and dissimilarity constraints. They aim to minimize the distance of similar pairs while separating dissimilar pairs with a certain margin. Weinberger et al [2006] employed a similar semidefinite formulation for k-nearest neighbor classification. The metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. Globerson and Roweis [2006] proposed a formulation aiming to collapse all examples in the same class to a single point and push examples in other classes infinitely far away. Davis et al [2007] proposed information theoretic metric learning which minimizes the differential relative entropy between two multivariate Gaussians under the constraints on the distance function. These algorithms are primarily designed for single feature representations and are not suitable for multi-modal data. One naive way is to concatenate features from different modalities into a single representation and subsequently apply single-modal metric learning techniques to learn a distance measure. This strategy ignores the incompatibility of heterogeneous information sources and fails to consider the dependency and complementarity relationships among different modalities, thereby leading to suboptimal performance.

To our best knowledge, the only work of distance metric learning on multiple modalities is proposed by McFee and Lanckriet [2011]. They integrate heterogeneous data to learn a holistic similarity measure based on multiple kernel learning, where each kernel encodes a different modality of the data. Their method learns a Mahalanobis distance metric for each modality over the reproducing kernel Hilbert space, which can be solved by semidefinite programming. This method is computationally costly both in training and testing. The training phase involves optimizing over multiple high-dimensional positive semi-definite matrices, which is hard to scale to large data set. In the test phase, to embed query into the learned target space, it needs to evaluate the kernel functions at query against the entire training set, which can not meet real-time requirements when the training set is large.

One closely related work is proposed in [Chen et al., 2010], which integrates multi-wing harmonium model [Xing et al., 2005] and large margin learning for the purpose of predictively learning a latent subspace for multi-view data. In their work, the available supervised information is class labels and the major goal of their approach is classification. Our work focuses on distance metric learning and the available supervision is "similar" and "dissimilar" pairs. Li et al [2009] proposed a unified framework to estimate similarities by exploiting the interactions between objects of different modality. In their work, similarity measure is learned in an unsupervised manner. Our work exploits the problem of distance metric learning which leverages supervised "similar" and "dissimilar" pairs to learn a similarity measure.

3 Multi-Modal Distance Metric Learning

In this section, we first briefly describe the multi-wing harmonium model (MWH). Based on MWH model, we introduce the multi-modal distance metric learning (MMDML) framework and the optimization technique.

3.1 Multi-Wing HarmoniumModel

For simplicity, we start with dual-wing harmonium model, which is a special case of multi-wing harmonium model and can be easily extended to multi-wing case. The dual-wing harmonium model (DWH) [Xing et al., 2005] is shown in Figure 1, which consists of two modalities of input units x = {xi}, z = {zj} and a set of hidden units h = {hk}. In this undirected graphic model, there exist no connections between two input modalities. Each modality of input units and the hidden units form a complete bipartite graph where units in the same set have no connections and are fully connected to units in the other set. This topology induces three conditional independence assumptions: given latent variables h, the two modalities x and z are independent, p(x, z|h) = p(x|h)p(z|h); given x and z, each unit in h is independent from each other p(h|x, z) = ∏k p(hk|x, z); given h, units within each modality are independent p(x|h) = ∏i p(xi|h), p(z|h) = ∏j p(zj|h). Consider the case where all observed and hidden variables are from exponential family, we have

where θi, ηj, λk are natural parameters, φ(·), ϕ(·), ψ(·) are sufficient statistics and A(·), B(·), C(·) are log partition functions.

We couple the random variables in the log-domain by introducing an additional term and get the joint distribution

the log-partition function of the joint probability is not explicitly shown to emphasize the difficulty of its estimation. If we examine the joint distribution from the random field viewpoint, φ(xi), ϕ(zj), ψ(hk) define potentials over cliques formed by individual nodes, φ(xi)ψ(hk) ,ϕ(zj)ψ(hk) define potentials over cliques consisting of pairwise linked nodes and θi, ηj, λk,Wk i ,Ukj are the associated weights of potential functions. We use Θ to denote all the parameters (θ, η, λ,W, U). Θ is learned by maximum likelihood method. From the joint distribution, we derive the conditional distributions

with shifted parameters ˆ θi = θi + ∑k Wk i ψ(hk),ˆ ηj = ηj +∑k Ukj ψ(hk), ˆλk = λk+∑i Wk i φ(xi)+∑j Ukj ϕ(zj ), where the shifts are induced by the coupling between the observed and hidden units.

Reversely, we can firstly specify the local conditional distributions in Eq.(3) according to specific applications, then write the joint distribution in Eq.(2). This is called bottom-up construction of the dual-wing harmonium model.

The dual-wing harmonium model can be readily extended to multi-wing when multi-modal input feature set are observed.

3.2 Multi-Modal Distance Metric Learning

In this section, we present how to employ MWH model to learn a distance measure on multiple modalities. Given a data point y = (x, z) with two feature modalities x and z, under the dual-wing harmonium model framework, we can embed y into the shared latent space and obtain its latent representation t:

Note that t is a function of Θ. Semantically, hidden units h can be viewed as a set of latent topics. Observations of different sources reflect the central theme from different perspectives and are generated from the shared topics.

Given a set of pairs labeled as "similar" or "dissimilar", we enforce similar pairs to be close to each other and dissimilar pairs to be far from each other in the latent space. We simply use Euclidean distance as distance measure for embedded points in this latent space. Let S = {(y(i) , y(j) )} denote the set of similar pairs and D = {(y(i) , y(j) )} denote the set of dissimilar pairs, we formulate the following optimization problem:

where t(i) is the representation of y(i) in the latent space. The goal is to minimize the distance between points labeled as "similar" while keeping the "dissimilar" points separated by a margin of 1 in the latent space. The parameter to be learned is Θ which is explicitly embedded in t.

Let Y denote all data instances appearing in S or D. The unsupervised dual wing harmonium model learns parameter Θ by maximizing the likelihood of data observations Y. Θ is learned in the sense of best explaining the data. In supervised multi-modal distance learning metric framework, we combine distance metric learning and maximum likelihood learning together and learn Θ by jointly maximizing data likelihood, minimizing distances of similar pairs and maximizing distances of dissimilar pairs. The learned Θ not only explains the data reasonably, but also facilitates good similarity comparison between data points. Specifically, we define the optimization problem as

where L(Y;Θ) is the negative log-likelihood of data Y parameterized by Θ and λ is the trade-off parameter. | · | denotes the cardinality of a set.

3.3 Optimization

In this section, we present an efficient solver of the problem defined in Eq.(6). The strategy is to use hinge loss to eliminate constraints, obtaining an unconstrained problem and subsequently employ subgradient method to do optimization.

We use hinge loss to eliminate the constrains in Eq.(6) and obtain:

where λ1 and λ2 are trade-off parameters. The problem defined in Eq.(7) is a relaxed version of that in Eq.(6). When constraints in Eq.(6) are satisfied, hinge loss in Eq.(7) is zero. Otherwise, hinge loss is nonzero and is minimized to enforce the constraints to be satisfied. Since hinge loss is nondifferential, we adopt sub-gradient method to do optimization.

We use contrastive divergence [Hinton, 2002] method to approximate the gradient of Θ w.r.t the negative loglikelihood 1 |Y| L(Y;Θ). Gradients (or sub-gradients) w.r.t the distance loss induced by similar pairs and distance loss induced by dissimilar pairs can be easily derived. In summary, the sub-gradients of parameters w.r.t the objective function defined in Eq.(7) can be computed as

where Ep[·] is the expectation w.r.t the true distribution and Eˆ p[·] is the expectation w.r.t the empirical distribution. Exact computation of Ep[·] is intractable. Ep[·] is approximated by running a few step of Gibbs sampling starting from Eˆ p[·]. The sampling can be iteratively done as follows

where l is the index of iterations.

4 Experiments

We have developed the general framework of large scale multi-modal distance metric learning. To corroborate the effectiveness and efficiency of our method, we evaluate it on tagged images data. Images tagged with textual tags are quite prevalent in photo sharing websites (like Flickr, Pinterest, Instagram), where each image is associated with user tags, title, description and comments.

4.1 MMDML on Tagged Images

To specialize the general MMDML framework to tagged images data, we need to specify the local conditionals defined in Eq.(3) to concrete exponential family distributions according to data characteristics. Specially, we consider two modalities: a discrete bag-of-words representation x of text and a normalized bag-of-words representation z of image based on SIFT [Lowe, 2004] feature. We assume each xi is a Bernoulli variable denoting whether the ith term of a tag dictionary appears or not around an image. Each zj is a Gaussian variable denoting the normalized bag-of-words representation based on SIFT feature.

We assume each hidden variable hk follows a Gaussian distribution conditioned on both text modality x and image modality z. We can define a dual-wing harmonium model in a bottom-up manner by specifying the local conditionals

From the definition of the conditional distribution of h over the observations x, z, we can easily infer the latent representation t

Accordingly, the sub-gradients defined in Eq.(8-10) can be specialized to

The Gibbs sampling process defined in Eq.(11) can be specialized to

4.2 Dataset

The dataset used in our experiments is NUS-WIDE-1.5K: a subset selected from NUS-WIDE dataset [Chua et al., July 8 10 2009]. Images are downloaded from Flickr and each image is associated with more than one user tags. We choose 30 classes and select about 50 images for each class. The total number of images is 1536. The 30 classes are actor, airplane, bicycle, bridge, buddha, building, butterfly, camels, car, cathedral, cliff, clouds, coast, computers, desert, flag, flowers, food, forest, glacier, hills, lake, leaf, monks, moon, motorcycle, mushrooms, ocean, police, pyramid. We randomly choose half of the images for training and the other half for testing. For text modality, 1000 tags with top frequency are selected to form the tag dictionary. For image modality, we extract SIFT based bag-of-words representation with a codebook of size 1024.

Following [Davis et al., 2007; Xing et al., 2002], we sample "similar" pairs by picking up two instances from the same class and "dissimilar" pairs by choosing two instances from different classes. We randomly sample about 10K "similar" pairs and 10K "dissimilar" pairs from the training set.

4.3 Experiment Setup

We compare with the following baselines:

• Xing+Original. We concatenate original feature vectors of text modality and image modality into a single representation and subsequently learn a Mahalanobis distance using the metric learning method proposed in [Xing et al., 2002].
• ITML+Original. We combine features of text and image into a whole and feed it to the ITML [Davis et al., 2007] method.
• Xing+MWH. We use the unsupervised MWH model to embed data from text and image modalities to the latent space and learn distance measure on the latent representations using the method proposed in [Xing et al., 2002].
• ITML+MWH. We use ITML [Davis et al., 2007] to learn distance on the latent feature vectors obtained from MWH model.
• MKE. We compare with the multiple kernel embedding method proposed in [McFee and Lanckriet, 2011].

All parameters are tuned by 5-fold cross validation. In our method MMDML, the dimension K of latent variables is set to 100. Trade-off parameters λ1, λ2 are set to 100. Coupling matrices W and U defined in Eq.(12) are initialized using SVD. Partial SVDs are performed on the design matrices over text features and image features respectively. Singular vectors corresponding to the top K singular values are selected as initial values of W and U. We run stochastic gradient descent with a fixed step size of 0.000001 and 200 iterations. The Gibbs sampling iterations in contrastive divergence is set to 1. For unsupervised MWH used in two baseline methods Xing+MWH and ITML+MWH, the parameters are the same as those in MMDML. For ITML, the trade-off parameter is set to 10. For MKE, we use Gaussian kernel with bandwidth 1 to compute the kernel matrices. The trade-off parameter is set to 10000.

After obtaining the learned parameters, we infer the latent representation for each test image using Eq.(13). We use Euclidean distance computed on latent representations as distance measure. Next, we report experimental results on image retrieval and classification.

4.4 Retrieval and Classification

For image retrieval, each test image is treated as query and the other images in the test set are ranked according to their distances with the given query. An image is considered relevant to query if it share the same class label with query image. We use average precision (AP) [Smeaton and Over, 2003] and precision-recall curve to measure retrieval performance.

The AP result is summarized in Table 1. The precisionrecall curve is shown in Figure 2. As can be seen from Table 1 and Figure 2, our method MMDML significantly outperforms baseline methods. MMDML achieves an average precision score of 0.8409, which is greatly higher than the second best method Xing+MWH. Note that, Xing+MWH and ITML+MWH both achieve substantial improvements compared with Xing+Original and ITML+Original. The reasons are two folds. First, Xing+MWH and ITML+MWH operate in a space with much lower dimension than the original feature space. Thereby the risk of overfitting is reduced. Second, MWH model maps two different modalities into a single latent space, which captures the correlation and complementary relationships between modalities. Xing+Original and ITML+Original naively concatenate heterogeneous modalities into a whole, where the hidden structure of modalities is not explored. However, compared with our method, Xing+MWH and ITML+MWH are suboptimal. In these two methods, multi-modal embedding and distance metric learning are performed separately. MWH is employed to project different modalities into the latent space and subsequently distance measure is learned in this latent space. In our method, multi-modal embedding and distance metric learning are jointly performed to achieve the overall optimality, thus yielding much better performance.

We also apply the learned distance measure for k-nearest neighbor (k-NN) classification. Table 2 summarizes the classification accuracy for k=1, 3, 5, 10, 20. Under varying k, our method consistently outperforms other methods.

4.5 Parameter Sensitivity

We test the sensitivity of MMDML to different choices of the dimension K of latent space and the tradeoff parameter λ1, λ2. Throughout the experiments, we set λ1 and λ2 to the same value to indicate equal importance of "similar" pairs and "dissimilar" pairs. When evaluating one parameter, the other parameters are fixed to values reported in Section 4.3. Figure 3(a) shows the variation of average precision (AP) with varying K. As can be seen, the retrieval performance is robust to the choice of K. For K larger than 10, the average precision almost remains the same. This suggest that we can choose a sufficiently small K to reduce computational cost and storage cost without degrading retrieval performance. Figure 3(b) shows how AP varies with different λ1. λ1 has a strong influence on MMDML. A larger λ1 means more emphasis over distance metric learning loss. For small λ1 (0.01, 0.1, 1), the average precision is very low. As λ1 increases to 10 and 100, AP is dramatically improved. However, further increasing λ1 results in performance decreasing. When λ1 is increased from 10 to 10000, the average score drops from 0.8433 to 0.7928. The possible reason is that too large λ1 makes the model overfitted to training data.

4.6 Computational Efficiency

To evaluate the efficiency of MMDML, we compare its running time with Xing+Original, ITML+Original, MKE. The comparison is performed on a machine with 3.3GHz quadcore Intel processor and 8GB memory. Table 3 summarizes the results. ITML is substantially time-consuming. It takes about 6.5 hours to converge. Considering its computational complexity grows quadratically with feature dimension and linearly with number of constraints, we can conclude this method is not applicable for large scale problems. Xing+Original takes reasonable time to converge. This method requires eigen-decomposition over the Mahalanobis matrix, which is of size 2024 in NUS-WIDE-1.5K dataset. However, in problems of high feature dimension, eigendecomposition will be extremely computationally demanding, if possible. MKE takes the least time in this experiment. However, this does not imply that this method is scalable. In MKE, each iteration of the projected gradient solver requires eigen-decompositions, whose complexity is O(mn3 ), where m is the number of modalities and n is the number of training examples. Clearly, MKE is not scalable for large dataset whose n can be very huge. Our method takes about 6.5 minutes for learning. It requires no eigen-decompositions and facilitates efficient stochastic gradient descent optimization. In our method, we mainly need to compute Eq.(8-10) which involves simple arithmetic operations and one step Gibbs sampling which turns out to be very efficient [Hinton, 2002].

5 Conclusions

We introduce a general framework of multi-modal distance metric learning based on multi-wing harmonium model. The framework can flexibly embed arbitrary number of feature modalities into a shared latent space where distance supervision is encoded. We apply the method to tagged image retrieval and experiments demonstrate the effectiveness and scalability of our method.

Acknowledgments

We would like to thank the anonymous reviewers for their insightful comments and suggestions and thank Jun Zhu and Brian McFee for providing their code.