Latent Structure Preserving Hashing

Similarity search (Wang et al. 2015; Gionis et al. 1999; Qin et al. 2015; Yu et al. 2015; Liu et al. 2015; Gao et al. 2015; Liu et al. 2015; Zhang et al. 2010; Wang et al. 2014; Bian and Tao 2010) is one of the most critical problems in information retrieval as well as in pattern recognition, data mining and machine learning. Generally speaking, effective similarity search approaches try to construct the index structure in the metric space. However, with the increase of the dimensionality of the data, how to implement the similarity search efficiently and effectively has become an significant topic. To improve retrieval efficiency, hashing algorithms are deployed to find a hash function from Euclidean space to Hamming space. The hashing algorithms with binary coding techniques mainly have two advantages: (1) binary hash codes save storage space; (2) it is efficient to compute the Hamming distance (XOR operation) between the training data and the new coming data in the retrieval procedure of similarity search. The time complexity of searching the hashing table is near O(1).

Current hashing algorithms can be roughly divided into two groups: random projection based hashing and learning based hashing. For the random projection based hashing techniques, the most well-known hashing technique that preserves similarity information is probably Locality-Sensitive Hashing (LSH) (Gionis et al. 1999). LSH simply employs random linear projections (followed by random thresholding) to map data points close in a Euclidean space to similar codes. It is theoretically guaranteed that as the code length increases, the Hamming distance between two codes will asymptotically approach the Euclidean distance between their corresponding data points. Furthermore, kernelized locality-sensitive hashing (KLSH) (Kulis and Grauman 2009) has also been successfully proposed and utilized for large-scale image retrieval and classification. However, in realistic applications, LSH-related methods usually require long codes to achieve good precision, which result in low recall since the collision probability that two codes fall into the same hash bucket decreases exponentially as the code length increases.

However, the random projection based hash functions are effective only when the binary hash code is long enough. To generate more effective but compact hash codes, a number of methods such as projection learning for hashing have been introduced. Through mining the structure of the data, then being represented on the objective function, a projection learning based hashing algorithm can obtain the hash function by solving an optimization problem associated with the objective function. Spectral Hashing (SpH) (Weiss et al. 2009) is a representative unsupervised hashing method, which can learn compact binary codes that preserve the similarity between documents by forcing the balanced and uncorrelated constraints into the learned codes. Furthermore, principled linear projections like PCA Hashing (PCAH) (Wang et al. 2012) has been suggested for better quantization rather than random projection hashing. Moreover, Semantic Hashing (SH), which is based a stack of Restricted Boltzmann Machines (RBM) (Salakhutdinov and Hinton 2007), was proposed in Salakhutdinov and Hinton (2009). In particular, SH involves two steps: pre-training and fine-tuning. During these two steps, a deep generative model is greedily learned, in which the lowest layer represents the high-dimensional data vector and the highest layer represents the learned binary code for that data. Liu et al. (2011) proposed an Anchor Graph-based Hashing method (AGH), which automatically discovers the neighborhood structure inherent in the data to learn appropriate compact codes. To further make such an approach computationally feasible, the Anchor Graphs used in Liu et al. (2011) were defined with tractable low-rank adjacency matrices. In this way, AGH can allow constant time hashing of a new data point by extrapolating graph Laplacian eigenvectors to eigenfunctions. More recently, Spherical Hashing (SpherH) (Heo et al. 2012) was proposed to map more spatially coherent data points into a binary code compared to hyperplane-based hashing functions. Meanwhile, the authors also developed a new distance function for binary codes, spherical Hamming distance, to achieve final retrieval tasks. Iterative Quantization (ITQ) (Gong et al. 2013) was developed for more compact and effective binary coding. Particularly, a simple and efficient alternating minimization scheme for finding a orthogonal rotation of zero-centered data so as to minimize the quantization error of mapping this data and the vertices of a zero-centered binary hypercube. Additionally, Boosted Similarity Sensitive Coding (BSSC) (Shakhnarovich 2005) was designed to learn a compact and weighted Hamming embedding for task specific similarity search. Boosted binary regression stumps were used as hashing functions to map the input vectors into binary codes. A similar idea as BSSC is also applied to Evolutionary Compact Embedding (ECE) (Liu and Shao 2015), which combines Genetic Programming with the boosting scheme to generate high-quality binary codes for large-scale data classification tasks. Besides, Self-taught Hashing (STH) (Zhang et al. 2010), in which a two-step scheme is effectively applied to learn hash functions, was also successfully utilized for visual retrieval. More hashing techniques can also be seen in Wang et al. (2015), Cao et al. (2012), Song et al. (2014), Song et al. (2013), Liu et al. (2012), Wang et al. (2015), Lin et al. (2013).

Nevertheless, the above mentioned hashing methods have their limitations. Although the random projection based hashing methods, such as LSH, KLSH and SKLSH (Raginsky and Lazebnik 2009), can produce relatively effective codes, such simple linear hash functions cannot reflect the underlying relationship between the data points. Meanwhile, since the long codes are required for acceptable retrieval results via random projection based hashing, the storage space and the cost of computing the Hamming distance will be expensive. On the other hand, in terms of learning based hashing algorithms, most of them, e.g., Shakhnarovich (2005), Weiss et al. (2009), Liu et al. (2011), only focus on the relationship between data or sets rather than considering the combination of the intra-latent structure¹ of data and the inter-probability distribution between the high-dimensional Euclidean space and the low-dimensional Hamming space.

To overcome these limitations above, in this paper, we propose a novel NMF-based approach called Latent Structure Preserving Hashing (LSPH) which can effectively preserve data probabilistic distribution and capture much of the locality structure from the high-dimensional data. In particular, the nonnegative matrix factorization can automatically learn the intra-latent information and the part-based representations of data, while the data probabilistic distribution preserving aims to maintain the similarity between high-dimensional data and low-dimensional codes. Moreover, incorporated with the representation of binary codes, the part-based latent information obtained by NMF based hashing, i.e., LSPH, could be regarded as independent latent attributes of samples. In other words, the binary codes determine whether the high-dimensional data hits the corresponding latent attributes or not. Given an image, this kind of data-driven attributes can allow us to well describe an image and also may benefit zero-shot learning (Jayaraman and Grauman 2014; Lampert et al. 2014; Tao 2015; Yu et al. 2013) for unseen image classification/retrieval in future work.

Specifically, because of the limitation of NMF, which cannot completely discover the latent structure of the original high-dimensional data, we provide a new objective function to preserve as much of the probabilistic distribution structure of the high-dimensional data as possible to the low-dimensional map. Meanwhile, we propose an optimization framework for the objective function and show the updating rules. Besides, to implement the optimization process, the training data are relaxed into a real-valued range. Then, we convert the real-valued representations into binary codes. Finally, we analyze the experimental results and compare them with several existing hashing algorithms. The outline of the proposed LSPH approach is depicted in Fig. 1.

LSPH is a linear hashing technique with a single-layer generative network and data distribution preserving constraints. Although it is an efficient binary coding method for large-scale retrieval tasks, such a single-layer generative network may lead to several limitations in the following cases as mentioned in [1]: (1) when it learns data which lie on or near a nonlinear manifold; (2) when it learns syntactic relationships of given data; and (3) when it learns hierarchically generated data. The single-layer LSPH is apparently not fit for such cases. For instance, LSPH with a single-layer network can well tackle data with small intra-variations such as face images. However, for more complex data with extremely different viewpoints, additional degrees of freedom of the data will be required. In terms of large-scale image retrieval tasks, the sources of data can be very variant and even samples belonging to the same category can differ significantly. Naturally, the single-layer LSPH is not competent for similarity search on such heterogeneous databases.

Therefore, in this paper, we also propose an extension of LSPH called multi-layer LSPH (ML-LSPH) with the multi-layer generative network [1] and distribution preserving constraints. ML-LSPH can deeply learn part-based latent information of data and preserve the joint probabilistic distribution for deep data representations. Applying the sigmoid function to each layer, ML-LSPH is a nonlinear architecture. Similar to recent deep neural networks (Hinton et al. 2006; Masci et al. 2011; Krizhevsky et al. 2012), ML-LSPH generates deep data representations which can theoretically lead to better performance than single layer LSPH for retrieval tasks with more complex data² in realistic scenarios. However, ML-LSPH is computationally more expensive during training and test phases compared to single layer LSPH. Thus, there exists a trade-off between ML-LSPH and LSPH in terms of performance and computational complexity, and the choice between these two versions depends on the requirement of the application. Besides, as ML-LSPH is a generalized framework of LSPH, it can easily shrink to LSPH if the number of the layers is set to \(\mathbf {1}\). We evaluate our LSPH and ML-LSPH on three large-scale datasets: SIFT 1M, GIST 1M and TinyImage, and the results show that our methods significantly outperform the state-of-the-art hashing techniques. It is worthwhile to highlight several contributions of the proposed methods:The rest of this paper is organized as follows. In Sect. 2, we give a brief review of NMF. The details of LSPH and ML-LSPH are described in Sects. 3 and 4, respectively. Section 5 reports the experimental results. Finally, we conclude this paper and discuss the future work in Sect. 6.

In this section, we mainly review some related algorithms, focusing on Nonnegative Matrix Factorization (NMF) and its variants. NMF is proposed to learn the nonnegative parts of objects. Given a nonnegative data matrix \(X = [\mathbf {x}_1,\cdots , \mathbf {x}_{N}]\in {\mathbb {R}}_{\ge 0}^{M \times N}\), each column of X is a sample data. NMF aims to find two nonnegative matrices \(U\in {\mathbb {R}}_{\ge 0}^{M \times D}\) and \(V\in {\mathbb {R}}_{\ge 0}^{D\times N}\) with full rank whose product can approximately represent the original matrix X, i.e., \(X\approx UV\). In practice, we always set \(D < \min (M,N)\). The target of NMF is to minimize the following objective functionwhere \(\Vert \cdot \Vert \) is the Frobenius norm. To optimize the above objective function, an iterative updating procedure was developed in Lee and Seung (1999) as follows:and normalizationIt has been proved that the above updating procedure can find the local minimum of \({\mathcal {L}}_{NMF}\). The matrix V obtained in NMF is always regarded as the low-dimensional representation while the matrix U denotes the basis matrix.

Furthermore, there also exists some variants of NMF. Local NMF (LNMF) (Li et al. 2001) imposes a spatial localized constraint on the bases. In Hoyer (2004), sparse NMF was proposed and later, NMF constrained with neighborhood preserving regularization (NPNMF) (Gu and Zhou 2009) was developed. Besides, researchers also proposed graph regularized NMF (GNMF) (Cai et al. 2011), which effectively preserves the locality structure of data. Beyond these methods, Zhang et al. (2006) extends the original NMF with the kernel trick as kernelized NMF (KNMF), which could extract more useful features hidden in the original data through some kernel-induced nonlinear mappings. Additionally, a hashing method based on multiple kernels NMF was proposed in Liu et al. (2015), where an alternate optimization scheme is applied to determine the combination of different kernels.

In this paper, we present a Latent Structure Preserving NMF framework for hashing (i.e., LSPH), which can effectively preserve the data intrinsic probability distribution and simultaneously reduce the redundancy of low-dimensional representations. Specifically, since the solution of standard NMF only focuses on optimizing matrix factorization to minimize Eq. (1), the obtained low-dimensional representation V lacks the data relationship information. In fact, most of previous NMF extensions are based on keeping the locality regularization to guarantee that, if the high-dimensional data points are close, the low-dimensional representations from NMF can still be close. However, this kind of regularization may lead to a low-quality factorization, since it ignores preserving the whole data distribution but only focuses on locality information. For a realistic scenario with noisy data, locality preserving regularization would even produce worse performance. Rather than locality-based graph regularization, we measure the joint probability of data by Kullback-Leibler divergence, which is defined over all of the potential neighbors and has been proved to effectively resist data noise (Maaten and Hinton 2008). This kind of measurement reveals the global structure such as the presence of clusters at several scales. To make LSPH more capable on data with more complex distributions, the multi-layer LSPH (ML-LSPH) is also proposed, in which more discriminative, high-level representations can be learned from a multi-layer network with the distribution preserving regularization term. To the best of our knowledge, this is the first time that multi-layer NMF based hashing is successfully applied to feature embedding for large-scale similarity search. A preliminary version of our LSPH has been presented in Cai et al. (2015). In this paper, we include more details and experimental results and extend LSPH to ML-LSPH for more complex data in realistic retrieval applications.

In this section, we mainly elaborate the proposed Latent Structure Preserving Hashing algorithm.

To better tackle the retrieval tasks with more complex data distributions, in this section, we introduce the multi-layer LSPH (ML-LSPH). ML-LSPH aims to generate more informative high-level representations compared with single-layer LSPH for data with complex distributions. Once the representation by ML-LSPH is computed, the final hashing functions are also obtained through multivariable logistic regression, same as LSPH mentioned above.

Given data matrix \(X \in {\mathbb {R}}^{M \times N}\), inspired by recent deep learning algorithms and multi-layer NMF [1], Trigeorgis et al. (2014), we can extract latent data attributes by incorporating our LSPH algorithm with a multi-layer structure as illustrated in Fig. 2. Similar to the learning of the above representation matrix V, a matrix sequence \(V_1, \cdots , V_n\) can be obtained by solving the following optimization problems:where \(U_i \in {\mathbb {R}}^{D_{i-1}\times D_i}, V_i \in {\mathbb {R}}^{D_i \times N}\), \(i=1,\cdots ,n\), \(D_0 = M\), P is the distribution of X and \(Q^{(i)}\) is the distribution of \(V_i\). In this way, \(V_i, i=1, \cdots , n\), are the hidden factors of each layer. By introducing the nonlinear function \(g(\cdot )\) into the network, these hidden factors are generated by the following rules:Then our task is to minimize the following objective function:Let us denote \(G_i = KL(P||Q^{(i)})\) and \(\odot \) is the Hadamard product (element-wise product). By taking the derivatives of F with respect to \(U_i\) and \(V_i\), we have: where matrices \(N_i, R_i \in {\mathbb {R}}^{D_{i-1} \times N}\) are calculated by the following rules:for \(i=1, \cdots , n-1\), with the initialization:Besides, the derivatives of G with respect to \(U_i\) and \(V_i\) are calculated by Eqs. (27) and (28). With the derivation in Sect. 3, we have the derivativewhere \(\mathbf {v}^j_k\) is the k-th column of \(V_j, k=1,\cdots ,N\) and \(j=1,\cdots ,n\). To ensure that every element in \(U_i\) and \(V_i\) is nonnegative, we use the following symbols to split the above derivatives as:where Then we can define two matrix sequences \(S_l\) and \(M_l\) as follows: where \(l=j, \cdots , i-2\), \(S_j^{(j)} = A_j\) and \(M_j^{(j)} = B_j\). In this way, the derivatives of \(G_j\) with respect to \(U_i\) and \(V_i\), i.e., Eqs. (27) and (28), will be: Substitute the above equations into Eqs. (33) and (34), we obtain:Finally, similar to the procedure in Sect. 3, the update rules for multi-layer LSPH (ML-LSPH) are shown in Eqs. (29) and (30), where \(0<\gamma <1\) is the learning rate and \(i=1,\cdots , n\). The convergence property of the above iteration is similar to the one in [1]. Besides, for better understanding our ML-LSPH, we aim to unify the LSPH and ML-LSPH under a same framework. Thus, in our implementation, the function \(g(\cdot )\) applied on \(U_1\) and \(V_1\) is regarded as identity function \(f(x)=x\). The function \(g(\cdot )\) for \(U_i\) and \(V_i, i=2, \cdots , n\) is played by nonlinear sigmoid function \(f(x)=\frac{1}{1+e^{x}}\). In this way, when the number of layers \(n=1\), the ML-LSPH will shrink to the ordinary single-layer LSPH. It is noteworthy that we could theoretically formulate our ML-LSPH to an arbitrary number of layers according the above algorithms. However, for realistic applications with complex data distributions, the number of layers is always less than 3, since when the number of layers increases, the accumulative reconstruction error will cause the non-convergence of the proposed model (Trigeorgis et al. 2014).

For the hash code generating phase, it is similar to LSPH. In particular, acquired the low-dimensional representation \(V_n\) in the n-th layer, we first solve the Orthogonal Procrustes problem \(\min _{\mathcal {P}^T \mathcal {P} = I}\Vert \mathcal {P} X - V_n\Vert \) to achieve the orthogonal projection \({\mathcal {P}}\). The optimal solution can be obtained by the following procedure: 1. use the singular value decomposition algorithm to decompose the matrix \(X^T V_n = A {\varSigma }B^T\); 2. calculate \({\mathcal {P}} = B{\varOmega }A^T\), where, \({\varOmega }\) is a connection matrix as \({\varOmega }=[I,\mathbf{0 }]\in {\mathbb {R}}^{D\times M}\) and \({\mathbf{0 }}\) indicates all zeros matrix. For a new coming test data \(\mathbf {x}_{new} \in {\mathbb {R}}^{M \times 1}\), the low-dimensional representation in the n-th layer is \(\mathbf {v}_n^{new} = {\mathcal {P}} \mathbf {x}_{new}\) and the binary codes are calculated by \(\hat{\mathbf {v}}_n^{new} = \lfloor h_{\varTheta }({\mathcal {P}} \mathbf {x}_{new})\rceil \) where \({\varTheta }\) is obtained by the similar multi-variable regression scheme. The procedure of ML-LSPH is summarized in Algorithm 2.

Batch-Based Learning Scheme With the number of the layers increasing, the computational costs will inevitably increase as well in the current multi-layer network architecture of ML-LSPH. In order to effectively reduce the computational complexity on large-scale data, we adopt a random batch-based learning strategy (RBLS) in the iteration optimization of ML-LSPH. The complexity of each layer’s NMF is \(O (NMD)\) as mentioned above, which is still regarded as linear complexity in terms of N and not very demanding for large-scale data processing. However, the real bottleneck of the optimization procedure is the calculation of the KL divergence for each layer, specifically, the similarity matrices P and \(Q^{(m)}\), due to the complexity of \(O (N^2D)\). Therefore, in our implementation, we adopt RBLS to effectively reduce the complexity for computing P and \(Q^{(m)}\) in ML-LSPH. In detail, for each step of updating P and \(Q^{(m)}\), we randomly select a small subset of the whole training set. Then we only need to compute the pairwise similarity of this subset and the rest of the elements of P and \(Q^{(m)}\) are replaced by zeros:where m indicates the layer index. The illustration of proposed RBLS are also shown in Fig. 3. If we assume the size of the small subset is \(\ell \), the complexity of our RBLS will be reduced from \(O (N^2D)\) to \(O (\ell ^2D)\). Usually, the \(\ell \) can be set as \(\ell =1/100N\). It is noteworthy that only the computation of P and \(Q^{(m)}\) are replaced by the above RBLS trick and other parts of the algorithm in ML-LSPH are still the same as mentioned before. In this way, our multi-layer LSPH becomes scalable for large-scale data.

In this section, we will discuss the computational complexity of LSPH and ML-LSPH. The computational complexity of LSPH consists of three parts. The first part is for computing NMF, the complexity of which is \(O (NMD)\) (Li et al. 2014), where N is the size of the dataset, M and D are the dimensionalities of the high-dimensional data and the low-dimensional data respectively. The second part is to compute the cost function Eq. (7) in the objective function which has the complexity \(O (N^2D)\). The last part is the logistic regression procedure whose complexity is \(O (ND^2)\). Therefore, the total computational complexity of LSPH is: \(O (tNMD+N^2D+tND^2)\), where t is the number of iterations.

It is obvious that single-layer ML-LSPH is actually LSPH. The computational complexity of ML-LSPH with multiple layers consists of several NMF optimizations, the computation of matrices P and \(Q^{(j)}\), and the logistic regression procedure. With the above discussion, the computational complexity of ML-LSPH is \(O(tN M \sum _{i=1}^n D_i + \ell ^2 \sum _{i=1}^n D_i + t N D^2)\), where \(\ell \) is the batch size.

In this section, we systematically evaluate the proposed LSPH and multi-layer LSPH (ML-LSPH) on three large-scale datasets. The relevant experimental results and data visualization will be included in the rest of this section. All the experiments are completed using MatLab2014a on a workstation with a 12-core 3.2GHz CPU and \(120 \hbox {GB}\) of RAM running the Linux OS.

In this paper, we have proposed the Latent Structure Preserving Hashing (LSPH) algorithm, which can find a well-structured low-dimensional data representation through the Nonnegative Matrix Factorization (NMF) with the probabilistic structure preserving regularization part, and then the multi-variable logistic regression is effectively applied to generate the final hash codes. To better tackle the data with complex and noisy data distributions, a multi-layer LSPH (ML-LSPH) extension has also been developed in this paper. Extensive experiments on three large-scale datasets have demonstrated that our algorithms can lead to competitive hashing performance for large-scale retrieval tasks.

As we mentioned in the introduction of the paper, the hash codes learned from both LSPH and ML-LSPH can be regarded as independent latent attributes due to the property of NMF. In future work, this kind of learned data-driven attributes will be further explored with zero-shot learning for unseen image classification, retrieval and annotation tasks.