MLS3RDUH: Deep Unsupervised Hashing via Manifold based Local Semantic Similarity Structure Reconstructing

1 Introduction

With the unprecedented growth of image data, hashing based approximate nearest neighbour (ANN) searching have attracted more and more attention due to their high retrieval efficiency and low storage cost. The main idea of hashing methods is to project high dimensional data points into compact binary codes, meanwhile, preserve the semantic similarity of original datapoints.

Generally, hashing methods can be grouped into supervised and unsupervised categories. The supervised hashing [Li et al., 2016; Wang et al., 2018; Huang et al., 2019] methods mainly utilize semantic labels as supervised information to train models to get remarkable performance. However, they extremely rely on vast labeled datapoints to train their models. Thus, it means supervised hashing methods are not suitable to the cases where there are no labeled training datapoints.

∗The author is corresponding author

Unsupervised hashing [Gong et al., 2012; Huang et al., 2017; Tu et al., 2019; Yang et al., 2019] methods, which can be used in the cases, learn hashing functions with unlabeled datapoints. Most of the unsupervised hashing methods usually project datapoints into semantic similarity-preserving hash codes by constructing local semantic similarity structure as the guiding information, i.e., treating a datapoint similar to its k nearest neighbours. The k nearest neighbours are the top k datapoints ranked by the natural distance, such as the Euclidean distance and the cosine similarity of their features. However, among the k nearest neighbours of an image, some of them are dissimilar to the image, i.e., they are noisy datapoints which will damage the retrieval performance. For example, as shown in Figure 1, the two images are mostly the same except their core objects that the core object of Figure 1 (a) is a bird and the one of Figure 1 (b) is an airplane. It means the two images are semantic dissimilar, but their natural distance is small. Then, Figure 1 (a) is probably one of the k nearest neighbours of Figure 1 (b), and Figure 1 (a) will be misjudge as similar to Figure 1 (b) which will misguide the hashing model and damage the retrieval performance.

Intuitively, we can use the intrinsic manifold structure in the feature space of datapoints to reduce the noisy datapoints. For example, as shown in Figure 2, among the k nearest neighbours of the query red "circle" point which defined by the natural distance, the brown "triangle" points which are the noisy datapoints are on different manifolds with the red "circle" point. Thus the manifold similarities, defined on the manifold structure, between the red "circle" point and the brown "triangle" points are large. It means the noisy datapoints can be distinguished from the k nearest datapoints by incorporating the manifold structure. Specifically, given an image x, its k nearest neighbours, denoted as nnck (x), are the top k points ranked by their cosine similarity with the image x; and its o nearest points on manifold structure, denoted as nnmo (x), are the top o points ranked by the manifold similarity which are measured by a random walk [Zhou et al., 2004b] . Then, if a point in nnck (x) but not in nnmo (x), it can be defined as noisy points, i.e., it is dissimilar to x.

Thus, in this paper, we proposed a novel deep unsupervised hashing method, called MLS3RDUH, which reduces the noisy points by incorporating manifold structure to reconstruct the local semantic similarity structure. Specifically, MLS3RDUH deems an image x similar to the points in the set nnck (x) ∩ nnmo (x), and dissimilar to the other points in the set nnck (x). Furthermore, inspired by the recently work [Girshick et al., 2014] that rich semantic informations are contained in the features extracted by a pre-trained CNN, MLS3RDUH defines the semantic similarity between the image x and the datapoints that do not belong to nnck (x) by the corresponding cosine similarity of their features extracted by a pre-trained CNN. Finally, a novel log-cosh hashing loss function is used to optimize the hashing network to generate compact hash codes by using the defined similarity as guiding information.

To sum up, our contributions can be outlined as follows:

• MLS3RDUH utilises the intrinsic manifold structure in the feature space and cosine similarity to reconstruct the local semantic similarity structure to define a novel similarity matrix.
• A novel log-cosh hashing loss is proposed to optimize the hashing network to improve the performance.
• Experiments on three public datasets show that the proposed method outperforms the state-of-the-art baselines.

2 RelatedWork

A variety of hashing methods have been proposed in recent years, and based on whether supervised information is needed in the training phase, they can be broadly categorized into supervised and unsupervised hashing methods.

Supervised hashing methods learn hashing functions by using not only the data representation but also the label information in the training phase. A mass of methods in this category have been proposed, such as Deep Supervised Hashing with Pairwise (DPSH) [Li et al., 2016], HashNet [Cao et al., 2017] and Deep Hashing With Gradient Attention (GAH) [Huang et al., 2019]. HashNet alleviates data imbalance by adjusting the weights of semantic similarity matrix to learn discriminative hash codes. GAH utilizes a novel gradient attention mechanism to train deep hashing model.

The unsupervised hashing methods can be divided into traditional unsupervised hashing methods and deep unsupervised hashing methods. The traditional unsupervised hashing methods use hand-crafted features and shallow hash functions to obtain binary hash codes. Numerous algorithms in this category have been proposed, such as Spectral Hashing (SH) [Weiss et al., 2009], and Circulant Binary Embedding (CBE) [Yu et al., 2014]. However, limited by the hand-crafted features and shallow hash functions, it is hard for them to generate high-quality hash codes for complex and high dimensional real-world data. The deep unsupervised hashing methods utilize deep architecture to extract image features to learn hash code. For example, Deepbit [Lin et al., 2016] get rotation invariant and balanced binary hash codes by defined a quantization loss. Semantic structure-based unsupervised deep hashing (SSDH) [Yang et al., 2018] constructs semantic structures based on a Gaussian estimation to guide hashing network learning. DistillHash [Yang et al., 2019] learns hashing models by distilling data pairs with confident semantic similarity relationships as training set.

Compared with these methods, MLS3RDUH utilizes manifold structure to reduce the noisy datapoints when defining the similarity matrix, and a novel loss function is used to incorporate the defined similarity matrix into the training process to get a better performance.

3 Our Method

In this section, we first give a problem definition in section 3.1. The whole architecture of MLS3RDUH will be introduced in section 3.2. Then we discuss the detail of similarity matrix definition and the object function in section 3.3 and section 3.4, respectively. Finally, we will introduce the learning of parameters in section 3.5.

3.1 ProblemDefinition

Suppose a dataset has n images X = {xi}ni=1 , and the ith image is xi. The goal of unsupervised hashing is to learn a hashing model which maps an image xi into a similaritypreserving hash code bi ∈ {-1, 1}l where l is the length of hash codes, such that an input image xi will be encoded into a l bit binary code bi.

3.2 Design Overview

As shown in Figure 3, MLS3RDUH consists of a similarity generating part and a hashing network part. In the similarity generating part a pre-trained AlexNet [Krizhevsky et al., 2012] is used to extract features for training images to generate a similarity matrix. Then by using the generated similarity matrix as guiding information, the hashing network can be trained well to generate hash codes for images. Moreover, the hashing network contains five convolutional layers and three fully connected layers. The first seven layers are the same with the first seven layers of AlexNet, and the third fully-connected layer has l units.

3.3 SimilarityMatrix Generating

For each image xi, we first select its k nearest neighbours nnck (xi) based on their cosine similarity. The cosine similarity is formulated as follows:

where fi is the feature of image x which is extracted by a pre-trained CNN such as Alexnet [Krizhevsky et al., 2012] and VGG [Simonyan and Zisserman, 2014]. |·| denotes the length of a vector.

Then, inspired by [Zhou et al., 2004b], we measure the manifold similarity between datapoints by utilizing a random walk on the nearest neighbour graph. The nearest neighbour graph is undirected weighted which is constructed by using the n image X as nodes and can be represented by sparse symmetric adjacency matrix G ∈ Rn×n which is formulated as follows:

Moreover, the diagonal elements of G are zero. With the nearest neighbour graph, for each node xi, the random walk follows the iteration:

where α ∈ [0, 1) is a hyper-parameter; ˆG = D-1/2GD-1/2 and D = diag(G1) where 1 is a vector whose elements are 1; r(0) i ∈ Rn is an arbitrary vector; hi is a one-hot vector that only the ith element of hi equals to 1, and the others equal to 0. According to [Zhou et al., 2004a], the sequence {rti }∗t=0 can converges to the solution r∗i , then we have:

where I is an identity matrix. Then, we use r∗ij , the j th element of r∗i , denotes the manifold similarity between image xi and image xj. Finally, for each image xi, we rank the other points by the manifold similarity from large to small and nnmo (xi) are the set of the top o datapoints.

Then, with the constructed nnmo (xi), we can reconstruct nnck (xi) that divide the k nearest neighbours into two groups: the datapoints in one group are similar to image xi, and the datapoints in the other group are dissimilar to image xi. Specifically, for each datapoint in the nnck (xi), if it also belong to the nnmo (xi), then it is similar to xi, otherwise, it is dissimilar to xi; for the other datapoints that are not in the nnck (xi), their similarity with the image xi are fuzzy. Thus, we can define a similarity matrix ˆS as follows:

where ˆSij is the ith row j th column of ˆS. When ˆSij = 1, it means image xi is similar to image xj; when ˆSij = -1, it means image xi is dissimilar to image xj; when ˆSij = 0, it means the similarity between image xi and image xj is fuzzy. The defined ˆS may be an asymmetric matrix, then to ensure the symmetry, we further update it as ̂S following the rules: if ˆSij = 1 or ˆSji = 1, then ̂Sij = ̂Sji = 1; if ˆSij = 0 and ˆSji = 0, then ̂Sij = ̂Sji = 0; otherwise ˆSij = ˆSji = -1.

Furthermore, recently work [Girshick et al., 2014] shows that rich semantic information is contained in the feature extracted by a pre-trained CNN. It means that some semantic similarity information can be mined from the feature of images. Thus, for the similarity fuzzy image pairs, i.e., ̂Sij = 0, we further define their similarity by the cosine similarity of their features. Then, we can get the final similarity matrix S which can be formulated as follows:

Thus, the similarity between two images can be divided into three types: completely similar Sij = 1, completely dissimilar Sij = -1, and partly similar Sij ∈ (-1, 1).

3.4 Objective Function

The goal of hashing model is to map the images into hash codes which can preserving the constructed similarity S, i.e., if image xi and image xj are similar, the Hamming distance d(bi, bj) = 12 (l -bTi bj) should be small otherwise should be large. To achieve this goal, we used a novel log-cosh hashing loss which can be formulated as follows:

where F(xi;W) denotes the output of the hash network with image xi as input, andW represents the set of parameters of hashing network; cosh(a) = ea+e-a 2 ; sign(·) is an elementwise sign function which returns 1 if the element is positive and returns -1 otherwise.

By minimizing Formula (8), its goal is to make 1l bTi bj = Sij , i.e., it can make the hamming distance between two completely similar points as small as possible, and simultaneously make the hamming distance between two completely dissimilar points as large as possible. Meanwhile, it can make the partly similar images xi and xj have the suitable hamming distance complying with the similarity Sij .

However, the sign(·) function is in-differentiable at zero and the derivation of it will be zeros for a non-zero input. It means that the parameters of hashing model will not be updated with the back-propagation algorithm when minimizing the loss function L1. Thus, we directly discard the sign(·) function to ensure the parameters of our hashing model can be updated, and use tanh(·) to approximate the sign(·) function to make each element of output of hashing network can be close to "+1" or "-1". Then the final objective function can be formulated as follows:

3.5 Optimization

To optimize the proposed hashing model, we first construct the similarity matrix by using Formula (7), then minimize Formula (9) by using the mini-batch stochastic gradient descent (SGD) and update the parameter of hashing model with the back propagation (BP) algorithm. The details of the learning procedure are shown in Algorithm 1.

After the similarity matrix S is constructed, we use the mini-batch SGD method to learn the parameters W of hashing network. Specifically, we can calculate the gradient of the loss function L with regard to ˆbi as follows:

where tanh(a) = ea-e-a ea+e-a .

Then by using the chain rule, the gradients of the loss function L with regard to the parameters W can be calculated as Algorithm 1 Learning algorithm for MLS3RDUH

Input: Images X, the length of hash codes k. Output: Parameters of hashing network W, hash codes B.

• 1: Initialize parameters: W, α, k, o. learning rate: lr, iteration number: T, mini-batch size z (see Section 4.1).
• 2: Extract 4,096-dimensional deep features for images by Alexnet model which is pre-trained on ImageNet dataset.
• 3: Construct the semantic structure S by using Formula (7).
• 4: for i = 1 : T do
• 5: for j = 1 : nz do
• 6: Randomly sample z image from database as a minibatch.
• 7: Generateˆbi with image xi as input by hash network.
• 8: Update parameters of hash networkW by Formula (11) with back propagation algorithm.
• 9: end for
• 10: end for
• 11: Generate image hash codes B.

follows:

4 Experiments

In this section, we conduct extensive experiments on three commonly used image retrieval datasets to evaluate the proposed method against the state-of-the-art baselines.

4.1 Datasets and Settings

Three benchmark image retrieval datasets are used for evaluation, i.e., NUS-WIDE [Chua et al., 2009], MS COCO [Lin et al., 2014] and CIFAR10 [Krizhevsky et al., 2009], which are described below.

NUS-WIDE dataset contains 269,648 images crawled from Flickr. Each image is annotated with one or multiple labels from 81 concept labels. To ensure sufficient samples in each category, only 195,834 images that belong to the 21 most frequent concepts are selected for our experiment. We randomly sample 5,000 images as the test set and use the remaining images as the database, 10,500 images from the database as the training set.

MS COCO contains about 82,783 training images and 40,504 validation images, where each image is labeled by some of the 80 categories. After pruning images with no category information, we obtain 12,2218 images by combining the training and validation images. We randomly sample 5,000 images as the test set and use the other images as the database, 10,000 images from the database as the training set.

CIFAR10 is a popular image dataset which contains 60,000 images in 10 classes. We randomly sample 1,000 images as the test set and use the remaining images as the database, 5,000 images from the database as the training set.

Our proposed method is an unsupervised method, thus we compare our method with eight classical and state-of-the-art

unsupervised hashingmethods: four traditional shallowunsupervised methods LSH [Gionis et al., 1999], SH [Weiss et al., 2009], PCAH [Wang et al., 2010] and CBE [Yu et al., 2014]; four deep unsupervised hashing methods: Deepbit [Lin et al., 2016], UTH [Huang et al., 2017], SSDH [Yang et al., 2018] and DistillHash [Yang et al., 2019]. The four traditional shallow unsupervised hashing methods use 512-dimensional GIST features of images as inputs for all the datasets, and the four deep hashing methods use the raw images as their inputs. For fair comparison, we adopt the AlexNet architecture [Krizhevsky et al., 2012] for all the deep hashing methods. Moreover, we extract 4,096-dimensional deep features by Alexnet model which is pre-trained on ImageNet [Russakovsky et al., 2015] dataset as the inputs of the four shallow hashing methods and denote them as LSH+CNN, SH+CNN, PCAH+CNN and CBE+CNN, respectively.

In our implementation of MLS3RDUH, we utilize the AlexNet architecture [Krizhevsky et al., 2012] and implement it based on Pytorch framework. The parameters in the first seven layers of hashing model are initialized with the parameters of the first seven layers of Alexnet which is pretrained on ImageNet, and the parameters in the eight layer of hashing model are initialized by Xavier initialization [Glorot and Bengio, 2010]. We use mini-batch stochastic gradient descent (SGD) with 0.9 momentum and the learning rate is fixed to 0.04. The iteration number is 150. We fix the minibatch size of images as 128 and the weight decay parameter as 10-5 . We set k=0.06N, o=0.06N where N is the number of training datapoints, and following [Zhou et al., 2004b], the hyper-parameters α is set as 0.99.

4.2 Evaluation Criterions

We evaluate the retrieval quality based on three evaluation metrics: Mean Average Precision (MAP), Precision curves with respect to the number of top returned results (P@N) and Precision-Recall curves (PR). The first two criterions are based on Hamming ranking which sorts the datapoints based the Hamming distance to the query datapoint. Specifically, MAP is one of the most widely-used criteria for evaluating retrieval accuracy. Given a query and a list of R ranked retrieval results, the average precision (AP) for this query can be calculated. MAP is the average APs of all queries. P@N

is defined as the precision of the top N retrieved instances. In our experiments, following the settings in [Yang et al., 2018], R is set to 5,000. and N is set to 1,000. PR curve is based on hash lookup which aims to return retrieval data in radius of a certain Hamming distance to the query datapoint.

Moreover, in our experiments, two images are considered as similar if they share share at least one common label, otherwise they are dissimilar.

4.3 Experimental Results

For Hamming ranking, the results of MAP for MLS3RDUH and all the baselines on all the three datasets are shown in Table 1 with hash code numbers varying from 16 to 64, and P@N curves of the proposed method and all baselines over the three dataset on 64 bits are shown in Figure 4 (a), (c) and (e), respectively. In general, from Table 1 and Figure 4 (a), (c) and (e), three observations can be got: (1) Our proposed method outperforms all the baselines for different length of hash codes. For example, on NUS-WIDE dataset, comparing with the best traditional competitor PCAH+CNN on 64-bits, the MAP of MLS3RDUH have a increases of 13.4%, and comparing with the best deep competitor DistillHash, MLS3RDUH achieves a increase of 7.9%. Moreover, as shown in Figure 4, the P@N curves of the proposed method are better than all baselines on all the three datasets. (2) The performance of most shallow architecture methods with deep feature as input are better than the ones with handcrafted features as input. For example, on MS COCO dataset, CNNH+SH which used deep features as input outperforms SH which whose inputs are hand-crafted features by 11% on 16 bits. (3) When there are not enough supervisory signals, deep hashing methods may not outperform the shallow architecture hashing methods with deep feature as input. For example, on CIFAR10 dataset, the MAP results of CNN+SH and CNN+PCAH which are shallow architecture hashing methods with deep feature as input are higher than the results of deep hashing methodes DeepBit and UTH.

For hash lookup, the PR curves of the proposed method and all baselines over the three dataset on 64 bits are shown in Figure 4 (b), (d) and (f). It can be found that the curves of MLS3RDUH are higher than all the baselines' on the whole which demonstrates MLS3RDUH outperforms all the baselines in hash lookup.

4.4 Ablation Study

We investigate two variants of MLS3RDUH: (1) MLS3RDUH-1 is a variant of MLS3RDUH that only used manifold based reconstructed local semantic similarity, i.e., ̂Sij, as guiding information. (2) MLS3RDUH-2 is a variant of MLS3RDUH that only use the cosine similarity between datapoints, i.e., without the manifold based reconstructed local semantic similarity part as guiding information. The MAP results on 64 bits over three datasets are shown in Table 2. From the results, there are two points can be observed: (1) the manifold based reconstructed local semantic similarity can improve the retrieval performance. For example, MLS3RDUH outperforms MLS3RDUH-2 by 6.3%, 6.8% and 8.4% on NUS-WIDE dataset, MS

COCO dataset and CIFAR10 dataset, respectively. (2) Deep features of images extracted by a pre-trained CNN contains semantic information which can be used to improve retrieval performance. For example, compared with MLS3RDUH-1, MLS3RDUH which use the cosine similarity of deep features as additional guiding information has a increases of 5.3%, 4.5% and 6.2% on NUS-WIDE dataset, MS COCO dataset and CIFAR10 dataset, respectively.

4.5 Sensitivity to Hyper-parameters

We investigate the influence of the hyper-parameters k and o. Figure 5 shows the effect of these two hyper-parameters over NUS-WIDE dataset on 64 bits. To investigate the influence of k, we fix o = k and evaluate the MAP values of the proposed method by varying k from 0.01N to 0.5N where N is the number of training datapoints. The results are shown in Figure 5 (a). It can be found the performance first increases and then decreases as k varies, and can get a good performance in the range of [0.05N, 0.07N]. Then in order to investigate the influence of o, we set k = 0.06N and vary the ratio between o and k from 0.25 to 16. The results are shown in 5 (b). It can be find when the ratio equals to 1, i.e., k = o, MLS3RDUH can get the best performance. Then, for the proposed method, the parameters k and o are both set as 0.06N.

5 Conclusion

In this paper, we have proposed a novel Deep Unsupervised Hashing via Manifold based Local Semantic Similarity Structure Reconstructing, called MLS3RDUH. MLS3RDUH first construct a novel similarity matrix by utilizing manifold and cosine similarity between datapoints to reconstruct semantic similarity structure, then a log-cosh loss is used to optimize the hashing model by incorporating the defined similarity matrix into the training process. Extensive experiments on three real-world public datasets have shown that the proposed MLS3RDUH outperforms the state-of-the-art unsupervised baselines.

Acknowledgments

The work is supported by National Key R&D Plan (No. 2018YFB1005100), NSFC (No. 61772076, 61751201 and 61602197), NSFB (No. Z181100008918002), Major Project of Zhijiang Lab (No. 2019DH0ZX01), Open fund of BDAlGGCNEL, and CETC Big Data Research Institute Co., Ltd (No. w-2018018), and the funds of Beijing Advanced Innovation Center for Language Resources (No. TYZ19005).