Transfer Hashing with Privileged Information

1 Introduction

Hashing methods have been applied for efficient similarity search in many application areas, especially for information retrieval [Wang et al., 2016]. The goal of hashing is to design or learn a compact binary code, with each bit taking values of either -1/1 or 0/1, in a low-dimensional space for each data instance such that similar instances in the original space are mapped to similar binary codes. As a result, data instances can be stored in a low cost, and the similarity between instances can be efficiently computed with the Hamming distance using binary operation (XOR).

Most existing learning to hash methods require a large amount of data instances to learn a set of hash functions to construct binary codes [Wang et al., 2016]. However in some real-world applications, for a domain of interest, i.e., the target domain, the data instances may not be sufficient enough to learn a precise hashing model. For example, Taobao.com provides a platform for small businesses and individual entrepreneurs to open online stores. Suppose an individual entrepreneur wants to build a hashing system for all the images of the products sold in his/her online store. Unfortunately, the number of images are not sufficient enough to build a precise hashing system. A straightforward solution is to download images of the same or related products from other ecommerce websites, such as Amazon.com or eBay.com, to help learning a hashing system. However, in many individual online stores in Taobao.com, the images used to demonstrate the products are usually amateur, which are taken by the individual entrepreneur himself/herself, while the images of products demonstrated in Amazon.com are professional. A simple aggregation of these two different kinds of images may not help to learn a precise hashing system for the target images. Motivated by transfer learning [Pan and Yang, 2010], instead of using the images downloaded from Amazon.com or other e-commerce websites directly, one can extract knowledge from the auxiliary images, and then transfer the knowledge to help learning a more precise hashing system for the target images.

Specifically, we propose a novel framework named "Transfer Hashing with Privileged Information" (THPI), which is a marriage of transfer learning and a new learning paradigm, namely Learning Using Privileged Information (LUPI), proposed by [Vapnik and Vashist, 2009], where privileged information is assumed to be available for each training instance in the training phrase, and missing in the testing phrase. Our aim is to construct precise hash codes for a target domain instances, e.g., the images of product in an individual online store, by encoding the privileged information from a source domain, e.g., images on products downloaded from Amazon.com, into a learning to hash model. In this example, the target images can be considered as training instances, while auxiliary images of the same or similar products as the target images can be considered as their privileged information in the training phrase. As shown in [Vapnik and Izmailov, 2015], the amount of training data required for training can be dramatically reduced with the help of privileged information. Therefore, we expect that with privileged information, we are able to learn precise hashing functions for the target domain where data instances are not sufficient.

Note that the proposed THPI framework is different from cross-modal hashing which assumes that training instances of different modalities are rich, and are sufficient to learn reliable hash codes, respectively [Kumar and Udupa, 2011].

In most cross-modal hashing methods, full correspondences across different modalities are required as input [Kumar and Udupa, 2011; Wu et al., 2015]. Moreover, the goal of crossmodal hashing is to retrieve relevant data across modalities. In THPI, the goal is to learn a set of good hash functions with insufficient training instances in a target domain, and retrieve relevant information in the target domain.

The novelties of our work are summarized as follows,

• ÷ We propose a novel framework named "Transfer Hashing with Privileged Information" (THPI) to alleviate data sparsity in a target domain by transferring knowledge from a source domain.
• ÷ A new algorithm named ITQ+ is proposed, where a novel slack function for incorporating privileged information is introduced to regularize the learning of hash codes for the target domain.
• ÷ We further extend ITQ+ to LapITQ+, where underlying graph structure extracted from the source domain is encoded as a prior for learning more precise hash codes for the target domain.

2 RelatedWork

2.1 Learning to Hash

Most hashing methods focus on how to quantize data with minimal information loss. For example, Locality-sensitive Hashing (LSH) [Raginsky and Lazebnik, 2009] uses a set of random projections followed by thresholding. Spectral Hashing (SH) formulates the quantization as spectral graph partitioning [Weiss et al., 2008], where the graph geometry on original feature space is preserved. Iterative Quantization (ITQ) [Gong and Lazebnik, 2011] is proposed to refine the initial projections, e.g., Principal Component Analysis (PCA) [Tipping and Bishop, 1999], Canonical Correlation Analysis (CCA) [Hardoon et al., 2004], such that quantization error can be reduced. All these methods require sufficient data for learning hash functions for a domain of interest. Different from these methods, THPI aims at alleviating data sparsity and further improving hashing performance on the target domain by exploiting knowledge from other domains, which may be of heterogeneous features. Recently, cross-modal hashing [Kumar and Udupa, 2011; Zhang et al., 2011] that aims to learn hash codes with data from different modalities draws much attention. However, cross-modal hashing assumes training instances of different modalities be sufficient to learn reliable hashing functions respectively, which is different from THPI.

2.2 Transfer Learning

Transfer learning (TL) [Pan and Yang, 2010] aims to transfer knowledge across different domains so that rich source domain knowlege can be used to build better classifiers on a target domain where the transferred knowledge can be labels [Zhou et al., 2014b], features [Pan et al., 2011], crossdomain correspondences [Zhou et al., 2014a; 2016]. TL has shown promising results in many machine learning tasks, such as classification and regression. To the best of our knowledge, there is only one work on studying transfer learning for hashing [Ou et al., 2014]. Different from their work, we focus on how to transfer knowledge across heterogeneous feature spaces in an unsupervised manner.

2.3 Learning using Privileged Information

Recently, Vapnik and Vashist [2009] introduced a new learning paradigm namely learning using privileged information (LUPI). In LUPI, auxiliary privileged features are assumed to be available in the training phrase but not available in the testing phrase. A new model SVM+ is proposed by exploiting the privileged features to construct a correcting function in traditional Support Vector Machines (SVMs) to control the loss such that the learned classifiers can embrace stronger generalization ability. Specifically, given a set of training data ¶xi↪ ˜xi♦li=1 , where ˜x is the corresponding privileged features for the original features x, SVM+ aims to learn a target classifier f (x) = w>x from the original feature vectors and a slack approximation function ✏(˜x) = ˜w> ˜x from the privileged feature vectors, simultaneously. The goal of the slack approximation function is to control the loss of the target classifier by incorporating privileged features. The objective function of SVM+ is written as follows:

Inspired by the formulation of SVM+ and recent advances on LUPI [Niu et al., 2016; Xu et al., 2015; Sharmanska et al., 2013], in this work, we aim to construct a slack function for hashing by incorporating privileged information to learn a more precise hash model in the target domain where data is sparse.

3 Iterative Quantization with Privileged Information (ITQ+)

Suppose that we are given n data points ¶xT1 ↪ xT2 ↪ ▷ ▷ ▷ ↪ xTn ♦ with xTi 2RdT . Denote by XT = [xT1 ↪ ▷ ▷ ▷ ↪ xTn ]> 2Rn⇥dT the data matrix. Without loss in generality, we assume that all the n points have been zero-centered, i.e., Pni=1 xTi = 0. The goal of learning to hash is to learn a binary code matrix BT 2 Rn⇥c with its elements in ¶-1↪ 1♦, where c is the length of each hash code. For each bit k 2 ¶1↪ ▷▷▷↪ c♦, a binary function hk(xT ) = sgn(r>k xT ) is learned, where rk 2 RdT is the hyperplane for the k-th bit. Denote by R 2 RdT⇥c the projection matrix for all the c bits, the binary code matrix BT can be obtained by setting BT = sgn(XTR).

When n is small, i.e., the available target training data is limited, the hash codes learned by existing methods may not perform well. How to learn a precise hash model from sparse data is a crucial issue for most existing learning-to-hash algorithms. Inspired by the exciting results of LUPI, which prove that the amount of training data can be significantly reduced with privileged information for training a precise predictive model [Lapin et al., 2014; Vapnik and Vashist, 2009; Vapnik and Izmailov, 2015], we propose a new framework for learning to hash, namely Transfer Hashing with Privileged Information (THPI). In THPI, the data sparsity issue on the target domain is alleviated by using privileged information from an auxiliary domain which is referred to as the source domain. Apart from a target feature vector xT , in THPI, we assume that corresponding privileged information xS 2RdS from the source domain is available for training as well, which means that there are n corresponding data pairs ¶(xS1 ↪ xT1 )↪ (xS2 ↪ xT2 )↪ ▷ ▷ ▷ ↪ (xSn ↪ xTn )♦ for training. Furthermore, we denote by XSC = [xS1 ↪ ▷ ▷ ▷ ↪ xSn ]> 2 Rn⇥dS the matrix of the n corresponding instances on the source domain, and XSU = [xSn+1 ↪ xSn+2 ↪ ▷ ▷ ▷ ↪ xSn+nS ]> 2 RnS⇥dS the matrix of the additional nS source domain instances. Note that the privileged information is only available for training but not for testing.

3.1 Iterative Quantization

The ITQ algorithm [Gong and Lazebnik, 2011] aims to construct hashing functions using an iterative quantization method to learn a rotation matrix by minimizing the quantization error. Specifically, an orthogonal projection matrix RT 2 RdT⇥c is learned with the code matrix BT 2 ¶-1↪ 1♦n⇥c by optimizing the following quantization loss:

3.2 The objective function for ITQ+

Here, we assume that for BT , each bit is balanced, i.e., BT 2 B = ¶B 2 ¶-1↪ 1♦n⇥c and Pni=1 bi = 0♦, where bi is the i-th column of B. Define E = BT -XTRT , where E is the error matrix induced by the quantization process. With the privileged data XSC 2 Rn⇥c , we aim to approximate the quantization error matrix E by using a slack function g(XSC) = XSCP, where P 2 RdS⇥c is another orthogonal projection matrix to be learned. Therefore, we formulate Iterative Quantization with privileged information (ITQ+) as

where λ1 > 0 is a tradeoff parameter. Note that in SVM+, the privileged information is used to approximate the slack variables, which can be considered as tolerance functions that allow the margin constraints to be violated. Here, in ITQ+, we borrow the high-level idea of SVM+ to use source-domain information to approximate the target-domain quantization error E. On one hand, the constructed slack function models the difficulty in quantizing the target domain data with privileged information from the source domain. On the other hand, the constructed slack function can provide a way to regularize the quantization error to avoid overfitting when the size of target domain training data is small.

3.3 Optimization

The solution for the optimization problem (2) can be obtained by alternatingly updating the binary code matrix BT and the rotation matrices RT and P. The procedure is summarized in Algorithm 1, and the details are described in this section.

Update BT by fixing RT and P

By fixing RT and P, the binary code matrix BT can be obtained by solving the following optimization problem,

As RT and P are constant when optimizing BT , (3) can be reformulated as

where tr(·) denotes the trace of a matrix. The solution for (3) can be obtained by sorting the matrix M, column-wisely, and then projecting the sorted matrix onto the constraint B, where

Update RT by fixing P and BT

By fixing BT and P, the optimization problem with respect to RT can be written as follows,

As P is fixed, and only RT is to be optimized, we further rewrite the above optimization problem as

which is an orthogonal procrustes problem [Sch¨onemann, 1966], and can be solved analytically. To be specific, by performing the Singular Value Decomposition (SVD) on

we obtain

Update P by fixing RT and BT

With RT and BT fixed, we obtain an optimization problem with respect to P as

which again is a standard orthogonal procrustes problem, and can be solved analytically as follows,

where (BT -XTRT )> XSC = ˆQ⇤Q> is obtained by performing the SVD on (BT - XTRT )> XSC.

Algorithm 1 : Alternating optimization procedure for ITQ+ (or LapITQ+)

• 1: Initialize R0T ↪P0 to be the random orthogonal matrices, and set ⌧ = 0.
• 2: while not converge do
• 3: Update B⌧+1 T by solving (4) (or (11) for LapITQ+).
• 4: Update R⌧+1 T according to (7).
• 5: Update P⌧+1 according to (9).
• 6: ⌧ = ⌧ +1.
• 7: end while

4 Extension for ITQ+ (LapITQ+)

In ITQ+, only XSC is used for learning a hashing model for the target domain. In practice, besides XSC, we may have a large amount of training instances XSU on the source domain, whose corresponding feature vectors in the target domain are unknown. To fully exploit all the source domain data to learn a more precise hashing model for the target domain, we proposed an extension of ITQ+ in this section, namely LapITQ+.

Our motivation is from multi-view learning, where the underlying graph structures in different views are assumed to be similar [He and Lawrence, 2011]. Intuitively, as we have a large amount of training instances on the source domain, we can learn a precise graph structure for the source domain, and encode the structure as a regularization term for learning the hash codes for the target domain. Specifically, we can first apply ITQ to learn the hash codes BS using all the available source domain data XS = [X>SC ↪X>SU ]> by optimizing the following quantization loss,

where XS 2 R(nS+n)⇥dS , BS 2 ¶-1↪ 1♦(nS+n)⇥c and RS 2 RdS⇥c . This can be done offline in advance.

Next, we construct an adjacency graph G from the hash codes BS as follow: for each code BSi (each row of BS), connect BSi to its k nearest neighbors with a weight of value 1, where Hamming distance is applied. After constructing the adjacency graph, we use it to define the graph Laplacian LC 2 Rn⇥n for the target domain data. Finally, the proposed LapITQ+ method is formulated as

where λ1↪ λ2 ≥ 0 are parameters. Compared to (2), the third term in the above objective is to transfer the graph structure from the source domain to the target domain. Note that instead of constructing the graph Laplacian matrix on the original space [Weiss et al., 2008], we construct the graph Laplacian on the binary code space. In this way, we quantify the local properties of the manifold on the source domain and thus naturally transfer the graph structure across domains for learning hash codes. Though learning the hash codes on the source domain and the constructing adjacency graph can be very expensive, they can be done offline. The procedure to solve the above optimization is the same as that used for ITQ+ except for the update on BT .

4.1 Updating BT by fixing P and RT

We first relax the constraint BT 2 ¶-1↪ 1♦n⇥c to BT 2 [-1↪ 1]n⇥c on the feasible domain B, and obtain the following constrained quadratic programming optimization,

where K = ((1+λ1)R>X>T )+λ1P>X>SC , and LC = L>L. Finally, we binarize the codes by BT = sgn(BT ).

5 Complexity Analysis

The computational cost for proposed algorithms mainly depends on two parts: 1) to optimize the binary codes BT and 2) to optimize the orthogonal rotation matrices RT and P. For updating BT , the time complexity for ITQ+ which involves sorting is O(nT log(nT )c), and for LapITQ+, which involves QP programming, the time complexity is O(n3T ). For updating the orthogonal rotation matrices RT and P, the time complexities are bounded by O(c2dT + d3T ) and O(c2dS + d3S ) respectively. In transfer learning, nT is supposed to be not large. Moreover, in learning to hash, the code length c is supposed to be small. The dimensions dS and dT can be preprocessed to be small through dimensionality reduction techniques, such as CCA or PCA. Therefore, the overall complexities for ITQ+ and LapITQ+ are reasonably small.

6 Experiments

6.1 Datasets and Experimental Setup

To verify the effectiveness of our proposed approaches, ITQ+ and LapITQ+, we conduct a series of experiments on three benchmark datasets: BBC Collection [Greene and Cunningham, 2006], multilingual Reuters [Amini et al., 2009], and NUS-WIDE [Chua et al., 2009].

BBC Collection was collected for multi-view learning, where each instance is represented by three views. Specifically, this dataset was constructed from a single-view BBC corpora by splitting news article into related "views" of text. On this dataset, we consider View 1 as the source domain, and View 2 as the target domain.

Multilingual Reuters Collection is a text dataset with over 11,000 news articles from 6 categories in 5 languages, e.g., English, French, etc., which are represented by a bag-ofwords weighted by TF-IDF. Each document was also translated into the other four languages to construct correspondences. In the experiments, we use the English as the source domain and French as the target domain. Note that the original data is of very high dimensionality, we first perform PCA with 60% energy preserved on the TF-IDF features. After that, we obtain 1131- and 1230-dimensional features for the the English and French documents respectively.

NUS-WIDE dataset consists of 269,648 images from 81 concepts with a total number of 5,018 unique tags downloaded from Flickr. Following [Song et al., 2013], we use

150-D color moment for each image. For the corresponding text documents, we use bag-of-word features based on the 5,018 tags provided by NUS-WIDE, and further reduce its dimensionality by LDA to obtain a 60-D textual feature vector for each document. On this dataset, we treat image features as the target data and the text features as the source data.

While different features may lead to different retrieval performances, the evaluation of different features is not the focus of this paper. To simulate the partial cross-domain correspondence setting, we randomly select a fraction of training examples that are of both modalities as correspondences and denote the correspondences ratio by ↵, i.e., ↵ = n◁(n+nS), and from the remaining data, we randomly selected 10% as the test samples. The parameters λ1 and λ2 for the proposed methods are tuned by cross validation in the range of [0↪ 0▷001↪ 0▷005↪ · · · ↪ 1↪ 2]. We set the maximum number of iterations to be 150. To remove any randomness caused by random selection of training set, the results are averaged over 10 training-testing splits. To assess the performance of different algorithms, following the evaluation protocols in [Gong and Lazebnik, 2011; Raginsky and Lazebnik, 2009], a nominal threshold of the average distance to the 50th nearest neighbor is used to determine whether a database point returned for a given query is considered a true positive. Finally, we adopt the widely used criterion Mean Average Precision (MAP) [Gong and Lazebnik, 2011; Kumar and Udupa, 2011] for evaluation.

6.2 ComparedMethods and Evaluation

We first evaluate the performance of different methods by varying the number of hashing bits in the range of ¶8↪ 16↪ 32↪ 64♦, with fixed ↵ = 0▷5. The proposed transfer hashing approach is compared with four state-of-the-art hashing methods, i.e., LSH [Andoni and Indyk, 2006], DSH [Jin et al., 2014], CCA-ITQ [Gong and Lazebnik, 2011] and one cross-modal hashing method CVH [Kumar and Udupa, 2011].

• ÷ LSH: Local Sensitive Hashing (LSH) [Andoni and Indyk, 2006] is based on the a series of random projection to preserve pairwise distances for data points.
• ÷ DSH: Density Sensitive Hashing (DSH) [Jin et al., 2014] is to exploit the clustering results to generate a set of candidate hash functions and to select the hash functions which can split the data most equally.
• ÷ CCA-ITQ: For a fair comparison, we utilize the data from two domains by using CCA instead of PCA to generate initializations for ITQ [Gong and Lazebnik, 2011].
• ÷ CVH: Cross-View Hashing (CVH) [Kumar and Udupa, 2011] extends Spectral Hashing [Weiss et al., 2008] in a cross-modal manner, which maps similar data to similar codes across views based on a similarity graph.

We report MAP over all the test data for different methods in the Table 1. From the results, we can see that the proposed methods ITQ+ and LapITQ+ perform much better than the baselines. The reason is that ITQ+ and LapITQ+ introduce the new slack function to regularize the quantization loss by using privileged information, which is very important for loss generalization, and insensitive to noise or outliers, especially when the target data is sparse. Compared to LSH and DSH, both ITQ and CVH show better performance as they can make use of knowledge of both the source domain and the target domain by projecting them onto a common space. In this way, the source domain data can be utilized to slightly alleviate the data sparsity issue on the target domain. However these two methods still show inferior performance compared to ITQ+ and LapITQ+. As CCA-ITQ simply performs CCA as a preprocessing step, CCA does not explicitly affect the quantization loss during learning of hashing codes. The CVH method extends spectral hashing in a cross-modal manner and learns hashing codes by performing an eigenvalue decomposition, which usually requires a large number of training data.

From the experimental results, we conclude that the proposed slack function is a better way to transfer source domain knowledge for hashing. Most cross-modal hashing methods require a lot of cross-domain data correspondences, and learn hashing functions only on the correspondences. In contrast, LapITQ+ utilizes all source domain data including unparalleled data to learn source-domain hash codes offline, and use the structure underlying these hash codes to regularize the learning of hash codes on the target domain. Finally, we also observe that LapITQ+ outperforms ITQ+ by incorporating data geometry structure, and thus consistently obtain improvement by 1-2% in MAP.

6.3 Training Data Size and Retrieved Sample Size

We randomly select [10%↪ 30%↪ 50%↪ 70%] of the data from the target domain as the training set to evaluate the influence of training size on all the methods. Furthermore, for these data, we are also given the corresponding privileged data during training. Correspondences ratio is set to be ↵ = [0▷1↪ 0▷3↪ 0▷5↪ 0▷7] accordingly. Results are reported in the Figure 1. From the figure, we observe that ITQ+ and LapITQ+ outperform other baselines by large margins, especially when the target training data size is small. Although CCA-ITA shows promising results compared with other baselines, it still performs worse than our proposed methods.

In the application of information retrieval, users are usually more interested in precision at the first K returned results. We also report the Top-K precision [Liu et al., 2011] with varying numbers of K retrieved samples on the three datasets with 32 bits in Figure 2. As can be seen from the figure, our proposed methods achieve the best precisions for different values of K. For different numbers of bits, we have similar observations. Thus, we do not report the results here due to space limitation.

6.4 Parameter Analysis

In ITQ+, there is one parameter λ1, and in LapITQ+, there are two parameters λ1 and λ2. As LapITQ+ is an extension of ITQ+, we only analyze the parameter sensitivity of LapITQ+ in the range of [0↪ 0▷001↪ 0▷005↪ 0▷01↪ 0▷05↪ 0▷1↪ 0▷5↪ 1↪ 2]. We first fix λ2 = 0▷01 and vary λ1. The results of LapITQ+ with 32 bits on the three datasets are shown in the Figure 3(a) with x-log scale. In the second experiment, we fix λ1 = 0▷01 and vary λ2. The results are reported in the Figure 3(b). 1 We observe that LapITQ+ is not sensitive to λ1 and λ2.

7 Conclusion

In this paper, we propose a new learning framework for hashing named Transfer Hashing with Privileged Information (THPI), where privileged information is used to approximate a slack function to regularize the learning of hashing functions with insufficient data instances in the target domain. Based on the framework, we develop two particular transfer learning methods named ITQ+ and LapITQ+. We conduct extensive experiments on three benchmark datasets. Experimental results verify the superiority of the proposed methods ITQ+ and LapITQ+.

8 Acknowledgement

Sinno Jialin Pan is supported by the NTU Singapore Nanyang Assistant Professorship (NAP) grant M4081532.020. Ivor W. Tsang is grateful for the support from the ARC Future Fellowship FT130100746 and ARC grant LP150100671.

1 The results on the three datasets are 28.49, 11.52, 41.78 with λ1 = 0, and 27.56, 13.37, 42.41 with λ2 = 0, respectively.