Learning A Deep ℓ∞ Encoder for Hashing

1 Introduction

1.1 ProblemDefinition and Background

While `0 and `1 regularizations have been well-known and successfully applied in sparse signal approximations, it has been less explored to utilize the `1 norm to regularize signal representations. In this paper, we are particularly interested in the following `1-constrained least squares problem:

where y 2 Rn⇥1 denotes the input signal, D 2 Rn⇥N the (overcomplete) the basis (often called frame or dictionary) with N < n, and x 2 RN⇥1 the learned representation. Further, the maximum absolute magnitude of x is bounded by a positive constant λ, so that each entry of x has the smallest dynamic range [Lyubarskii and Vershynin, 2010]. As a result, The model (1) tends to spread the information of y approximately evenly among the coefficients of x. Thus, x is called "democratic" [Studer et al., 2014] or "anti-sparse" [Fuchs, 2011], as all of its entries are of approximately the same importance.

In practice, x usually has most entries reaching the same absolute maximummagnitude [Studer et al., 2014], therefore resembling to an antipodal signal in an N-dimensional Hamming space. Furthermore, the solution x to (1) withstands errors in a very powerful way: the representation error gets bounded by the average, rather than the sum, of the errors in the coefficients. These errors may be of arbitrary nature, including distortion (e.g., quantization) and losses (e.g., transmission failure). This property was quantitatively established in Section II.C of [Lyubarskii and Vershynin, 2010]:

Theorem 1.1. Assume ♣♣x♣♣2 < 1 without loss of generality, and each coefficient of x is quantized separately by performing a uniform scalar quantization of the dynamic range [-λ↪ λ] with L levels. The overall quantization error of x from (1) is bounded by λpN L . In comparision, a least squares solution xLS, by minimizing ♣♣DxLS - y♣♣22 without any constraint, would only give the bound pn L .

In the case of N << n, the above will yield great robustness for the solution to (1) with respect to noise, in particular quantization errors. Also note that its error bound will not grow with the input dimensionality n, a highly desirable stability property for high-dimensional data. Therefore, (1) appears to be favorable for the applications such as vector quantization, hashing and approximate nearest neighbor search.

In this paper, we investigate (1) in the context of deep learning. Based on the Alternating Direction Methods of Multipliers (ADMM) algorithm, we formulate (1) as a feedforward neural network [Gregor and LeCun, 2010], called Deep `1 Encoder, by introducing the novel Bounded Linear Unit (BLU) neuron and modeling the Lagrange multipliers as network biases. The major technical merit to be presented, is how a specific optimization model (1) could be translated to designing a task-specific deep model, which displays the desired quantization-robust property. We then study its application in hashing, by developing a Deep Siamese `1 Network that couples the proposed encoders under a supervised pairwise loss, which could be optimized from end to end. Impressive performances are observed in our experiments.

1.2 RelatedWork

Similar to the case of `0/`1 sparse approximation problems, solving (1) and its variants (e.g., [Studer et al., 2014]) relies on iterative solutions. [Stark and Parker, 1995] proposed an active set strategy similar to that of [Lawson and Hanson, 1974]. In [Adlers, 1998], the authors investigated a primaldual path-following interior-point method. Albeit effective, the iterative approximation algorithms suffer from their inherently sequential structures, as well as the data-dependent complexity and latency, which often constitute a major bottleneck in the computational efficiency. In addition, the joint optimization of the (unsupervised) feature learning and the supervised steps has to rely on solving complex bi-level optimization problems [Wang et al., 2015]. Further, to effectively represent datasets of growing sizes, a larger dictionaries D is usually in need. Since the inference complexity of those iterative algorithms increases more than linearly with respect to the dictionary size [Bertsekas, 1999], their scalability turns out to be limited. Last but not least, while the hyperparameter λ sometimes has physical interpretations, e.g., for signal quantization and compression, it remains unclear how to be set or adjusted for many application cases.

Deep learning has recently attracted great attentions [Krizhevsky et al., 2012]. The advantages of deep learning lie in its composition of multiple non-linear transformations to yield more abstract and descriptive embedding representations. The feed-forward networks could be naturally tuned jointly with task-driven loss functions [Wang et al., 2016c]. With the aid of gradient descent, it also scales linearly in time and space with the number of train samples.

There has been a blooming interest in bridging "shallow" optimization and deep learning models. In [Gregor and LeCun, 2010], a feed-forward neural network, named LISTA, was proposed to efficiently approximate the sparse codes, whose hyperparameters were learned from general regression. In [Sprechmann et al., 2013], the authors leveraged a similar idea on fast trainable regressors and constructed feedforward network approximations of the learned sparse models. It was later extended in [Sprechmann et al., 2015] to develop a principled process of learned deterministic fixedcomplexity pursuits, for sparse and low rank models. Lately, [Wang et al., 2016c] proposed Deep `0 Encoders, to model `0 sparse approximation as feed-forward neural networks. The authors extended the strategy to the graph-regularized `1 approximation in [Wang et al., 2016b], and the dual sparsity model in [Wang et al., 2016a]. Despite the above progress, up to our best knowledge, few efforts have been made beyond sparse approximation (e.g., `0/`1) models.

2 An ADMMAlgorithm

ADMM has been popular for its remarkable effectiveness in minimizing objectives with linearly separable structures [Bertsekas, 1999]. We first introduce an auxiliary variable z 2 RN⇥1 , and rewrite (1) as:

The augmented Lagrangian function of (2) is:

Here p 2 RN⇥1 is the Lagrange multiplier attached to the equality constraint, β is a positive constant (with a default value 0.6), and Φλ(z) is the indicator function which goes to infinity when ♣♣z♣♣1 > λ and 0 otherwise. ADMM minimizes (3) with respect to x and z in an alternating direction manner, and updates p accordingly. It guarantees global convergence to the optimal solution to (1). Starting from any initialization points of x, z, and p, ADMM iteratively solves (t = 0, 1, 2... denotes the iteration number):

Furthermore, both (4) and (5) enjoy closed-form solutions:

The above algorithm could be categorized to the primaldual scheme. However, discussing the ADMM algorithm in more details is beyond the focus of this paper. Instead, the purpose of deriving (2)-(8) is to preparing us for the design of the task-specific deep architecture, as presented below.

3 Deep `1 Encoder

We first substitute (7) into (8), in order to derive an update form explicitly dependent on only z and p:

where Bλ is defined as a box-constrained element-wise operator (u denotes a vector and ui is its i-th element):

.

Eqn. (9) could be alternatively rewritten as:

and expressed as the block diagram in Fig. 1, which outlines a recurrent structure of solving (1). Note that in (11), while W and S are pre-computed hyperparamters shared across iterations, bt remains to be a variable dependent on pt, and has to be updated throughout iterations too (bt's update block is omitted in Fig. 1).

By time-unfolding and truncating Fig. 1 to a fixed number of K iterations (K = 2 by default) 1 , we obtain a feed-forward network structure in Fig. 2, named Deep `1 Encoder. Since the threshold λ is less straightforward to update, we repeat the same trick in [Wang et al., 2016c] to rewrite (10) as: [Bλ(u)]i = λiB1(ui◁λi). The original operator is thus decomposed into two linear diagonal scaling layers, plus a unitthreshold neuron, the latter of which is called a Bounded Linear Unit (BLU) by us. All the hyperparameters W, Sk and bk (k = 1, 2), as well as λ, are all to be learnt from data by back-propogation. Although the equations in (11) do not directly apply to solving the deep `1 encoder, they can serve as high-quality initializations.

1 We test larger K values (3 or 4). In several cases they do bring performance improvements, but add complexity too.

It is crucial to notice the modeling of the Lagrange multipliers pt as the biases, and to incorporate its updates into network learning. That provides important clues on how to relate deep networks to a larger class of optimization models, whose solutions rely on dual domain methods.

Comparing BLU with existing neurons As shown in Fig. 3 (e), BLU tends to suppress large entries while not penalizing small ones, resulting in dense, nearly antipodal representations. A first look at the plot of BLU easily reminds the tanh neuron (Fig. 3 (a)). In fact, with the its output range [-1↪ 1] and a slope of 1 at the origin, tanh could be viewed as a smoothened differentiable approximation of BLU.

We further compare BLU with other popular and recently proposed neurons: Rectifier Linear Unit (ReLU) [Krizhevsky et al., 2012], Soft-tHresholding Linear Unit (SHeLU) [Wang et al., 2016b], and Hard thrEsholding Linear Unit (HELU) [Wang et al., 2016c], as depicted in Fig. 3 (b)-(d), respectively. Contrary to BLU and tanh, they all introduce sparsity in the outputs, and thus prove successful and outperform tanh in classification and recognition tasks. Interestingly, HELU seems exactly the rival against BLU, as it does not penalize large entries but suppresses small ones down to zero.

4 Deep `1 Siamese Network for Hashing

Rather than solving (1) first and then training the encoder as general regression, as [Gregor and LeCun, 2010] did, we instead concatenate encoder(s) with a task-driven loss, and optimize the pipeline from end to end. In this paper, we focus on discussing its application in hashing, although the proposed model is not limited to one specific application.

Background With the ever-growing large-scale image data on the Web, much attention has been devoted to nearest neighbor search via hashing methods [Gionis et al., 1999]. For big data applications, compact bitwise representations improve the efficiency in both storage and search speed. The state-of-the-art approach, learning-based hashing, learns similarity-preserving hash functions to encode input data into binary codes. Furthermore, while earlier methods, such as linear search hashing (LSH) [Gionis et al., 1999], iterative quantization (ITQ) [Gong and Lazebnik, 2011] and spectral hashing (SH) [Weiss et al., 2009], do not refer to any supervised information, it has been lately discovered that involving the data similarities/dissimilarities in training benefits the performance [Kulis and Darrell, 2009; Liu et al., 2012].

Prior Work Traditional hashing pipelines first represent each input image as a (hand-crafted) visual descriptor, followed by separate projection and quantization steps to encode it into a binary code. [Masci et al., 2014] first applied the siamese network [Hadsell et al., 2006] architecture to hashing, which fed two input patterns into two parameter-sharing "encoder" columns and minimized a pairwise-similarity/dissimilarity loss function between their outputs, using pairwise labels. The authors further enforced the sparsity prior on the hash codes in [Masci et al., 2013], by substituting a pair of LISTAtype encoders [Gregor and LeCun, 2010] for the pair of generic feed-forward encoders in [Masci et al., 2014] [Xia et al., 2014; Li et al., 2015] utilized tailored convolution networks with the aid of pairwise labels. [Lai et al., 2015] further introduced a triplet loss with a divide-and-encode strategy applied to reduce the hash code redundancy. Note that for the final training step of quantization, [Masci et al., 2013] relied on an extra hidden layer of tanh neurons to approximate binary codes, while [Lai et al., 2015] exploited a piece-wise linear and discontinuous threshold function.

Our Approach In view of its robustness to quantization noise, as well as BLU's property as a natural binarization approximation, we construct a siamese network as in [Masci et al., 2014], and adopt a pair of parameter-sharing deep `1 encoders as the two columns. The resulting architecture, named the Deep `1 Siamese Network, is illustrated in Fig. 4. Assume y and y+ make a similar pair while y and y- make a dissimilar pair, and further denote x(y) the output representation by inputting y. The two coupled encoders are then optimized under the following pairwise loss (the constant m represents the margin between dissimilar pairs):

The representation is learned to make similar pairs as close as possible and dissimilar pairs at least at distance m. In this paper, we follow [Masci et al., 2014] to use a default m = 5 for all experiments.

Once a deep `1 siamese network is learned, we apply its encoder part (i.e., a deep `1 encoder) to a new input. The computation is extremely efficient, involving only a few matrix multiplications and element-wise thresholding operations, with a total complexity of O(nN + 2N 2 ). One can obtain a N-bit binary code by simply quantizing the output.

5 Experiments in Image Hashing

Implementation The proposed networks are implemented with the CUDA ConvNet package [Krizhevsky et al., 2012]. We use a constant learning rate of 0.01 with no momentum, and a batch size of 128. Different from prior findings such as in [Wang et al., 2016c; 2016b], we discover that untying the values of S1, b1 and S2, b2 boosts the performance more than sharing them. It is not only because that more free parameters enable a larger learning capacity, but also due to the important fact that pt (and thus bk) is in essence not shared across iterations, as in (11) and Fig. 2.

While many neural networks are trained well with random initializations, it has been discovered that sometimes poor initializations can still hamper the effectiveness of first-order methods [Sutskever et al., 2013]. On the other hand, It is much easier to initialize our proposed models in the right regime. We first estimate the dictionary D using the standard K-SVD algorithm [Elad and Aharon, 2006], and then inexactly solve (1) for up to K (K = 2) iterations, via the ADMM algorithm in Section 2, with the values of Lagrange multiplier pt recorded for each iteration. Benefiting from the analytical correspondence relationships in (11), it is then straightforward to obtain high-quality initializations for W, Sk and bk (k = 1, 2). As a result, we could achieve a steadily decreasing curve of training errors, without performing common tricks such as annealing the learning rate, which are found to be indispensable if random initialization is applied.

(e) Deep `1 representation (f) Deep `1 binary hashing code

Figure 5: The learned representations and binary hashing codes of one test image from CIFAR10, through: (a) (b) NNH; (c) (d) SNNH; (e) (f) proposed.

Datasets The CIFAR10 dataset [Krizhevsky and Hinton, 2009] contains 60K labeled images of 10 different classes. The images are represented using 384-dimensional GIST descriptors [Oliva and Torralba, 2001]. Following the classical setting in [Masci et al., 2013], we used a training set of 200 images for each class, and a disjoint query set of 100 images per class. The remaining 59K images are treated as database.

NUS-WIDE [Chua et al., 2009] is a dataset containing 270K annotated images from Flickr. Every images is associated with one or more of the different 81 concepts, and is described using a 500-dimensional bag-of-features. In training and evaluation, we followed the protocol of [Liu et al., 2011]: two images were considered as neighbors if they share at least one common concept (only 21 most frequent concepts are considered). We use 100K pairs of images for training, and a query set of 100 images per concept in testing.

Comparison Methods We compare the proposed deep `1

siamese network to six state-of-the-art hashing methods:

• ÷ four representative "shallow" hashing methods: kernelized supervised hashing (KSH) [Liu et al., 2012], anchor graph hashing (AGH) [Liu et al., 2011] (we compare with its two alternative forms: AGH1 and AGH2; see the original paper), parameter-sensitive hashing (PSH) [Shakhnarovich et al., 2003], and LDA Hash (LH) [Strecha et al., 2012] 2 .
• ÷ two latest "deep" hashing methods: neural-network hashing (NNH) [Masci et al., 2014], and sparse neuralnetwork hashing (SNNH) [Masci et al., 2013].

Comparing the two "deep" competitors to the deep `1 siamese network, the only difference among the three is the type of encoder adopted in each's twin columns, as listed in Table 1. We re-implement the encoder parts of NNH and SNNH, with three hidden layers (i.e, two unfolded stages for LISTA), so that all three deep hashing models have the same depth 3 . Recall that the input y 2 Rn and the hash code x 2 RN , we immediately see from (11) that W 2 Rn⇥N , Sk 2 RN⇥N , and bk 2 RN . We carefully ensure that both NNHash and SparseHash have all their weight layers of the same dimensionality with ours 4 , for a fair comparison.

We adopt the following classical criteria for evaluation: 1)

2 Most of the results are collected from the comparison experiments in [Masci et al., 2013], under the same settings.

3 The performance is thus improved than reported in their original papers using two hidden layers, although with extra complexity.

4 Both the deep `1 encoder and the LISTA network will introduce the diagonal layers, while the generic feed-forward networks not. Besides, neither LISTA nor generic feed-forward networks contain layer-wise biases. Yet since either a diagonal layer or a bias contains only N free parameters, the total amount is ignorable.

precision and recall (PR) for different Hamming radii, and the F1 score as their harmonic average; 2) mean average precision (MAP) [M¨uller et al., 2001]. Besides, for NUS-WIDE, as computing mAP is slow over this large dataset, we follow the convention of [Masci et al., 2013] to compute the mean precision (MP) of top-5K returned neighbors (MP@5K), as well as report mAP of top-10 results (mAP@10).

We have not compared with convolutional network-based hashing methods [Xia et al., 2014; Li et al., 2015; Lai et al., 2015], since it is difficult to ensure their models to have the same parameter capacity as our fully-connected model in controlled experiments. We also do not include triplet lossbased methods, e.g., [Lai et al., 2015], into comparison because they will require three parallel encoder columns .

Results and Analysis The performance of different methods on two datasets are compared in Tables 2 and 3. Our proposed method ranks top in almost all cases, in terms of mAP/MP and precision. Even under the Hamming radius of 0, our precision result is as high as 33.30% (N = 64) for CIFAR10, and 89.49% (N = 256) for NUS-WIDE. The proposed method also maintains the second best in most cases,

65.62 84.63 7.2⇥10-2

in terms of recall, inferior only to SNNH. In particular, when the hashing code dimensionality is low, e.g., when N = 48 for CIFAR10, the proposed method outperforms all else with a significant margin. It demonstrates the competitiveness of the proposed method in generating both compact and accurate hashing codes, that achieves more precise retrieval results at lower computation and storage costs.

The next observation is that, compared to the strongest competitor SNNH, the recall rates of our method seem less compelling. We plot the precision and recall curves of the three best performers (NNH, SNNH, deep l1), with regard to the bit length of hashing codes N, within the Hamming radius of 2. Fig. 6 demonstrates that our method consistently outperforms both SNNH and NNH in precision. On the other hand, SNNH gains advantages in recall over the proposed method, although the margin appears vanishing as N grows.

Although it seems to be a reasonable performance tradeoff, we are curious about the behavior difference between SNNH and the proposed method. We are again reminded that they only differ in the encoder architecture, i.e., one with LISTA while the other using the deep l1 encoder. We thus plot the learned representations and binary hashing codes of one CIFAR image, using NNH, SNNH, and the proposed method, in Fig. 5. By comparing the three pairs, one could see that the quantization from (a) to (b) (also (c) to (d)) suffer visible distortion and information loss. Contrary to them, the output of the deep l1 encoder has a much smaller quantization error, as it naturally resembles an antipodal signal. Therefore, it suffers minimal information loss during the quantization step.

In view of those, we conclude the following points towards the different behaviors, between SNNH and deep l1 encoder:

• ÷ Both deep l1 encoder and SNNH outperform NNH, by introducing structure into the binary hashing codes.
• ÷ The deep l1 encoder generates nearly antipodal outputs that are robust to quantization errors. Therefore, it excels in preserving information against hierarchical informa-
• tion extraction as well as quantization. That explains why our method reaches the highest precisions, and performs especially well when N is small.
• ÷ SNNH exploits sparsity as a prior on hashing codes. It confines and shrinks the solution space, as many small entries in the SNNH outputs will be suppressed down to zero. That is also evidenced by Table 2 in [Masci et al., 2013], i.e., the number of unique hashing codes in SNNH results is one order smaller than that of NNH.
• ÷ The sparsity prior improves the recall rate, since its obtained hashing codes can be clustered more compactly in high-dimensional space, with lower intra-clutser variations. But it also runs the risk of losing too much information, during the hierarchical sparsifying process. In that case, the inter-cluster variations might also be compromised, which causes the decrease in precision.

Further, it seems that the sparsity and l1 structure priors could be complementary. We will explore it as future work.

6 Conclusion

This paper investigates how to import the quantization-robust property of an `1-constrained minimization model, to a specially-designed deep model. It is done by first deriving an ADMM algorithm, which is then re-formulated as a feedforward neural network. We introduce the siamese architecture concatenated with a pairwise loss, for the application purpose of hashing. We analyze in depth the performance and behaviors of the proposed model against its competitors, and hope it will evoke more interests from the community.