Title: MODELING WINNER-TAKE-ALL COMPETITION IN SPARSE BINARY PROJECTIONS

Abstract: Inspired by the advances in biological science, the study of sparse binary projection models has attracted considerable recent research attention. The models project dense input samples into a higher-dimensional space and output sparse binary data representations after Winner-Take-All competition, subject to the constraint that the projection matrix is also sparse and binary. Following the work along this line, we developed a supervised-WTA model when training samples with both input and output representations are available, from which the optimal projection matrix can be obtained with a simple, efficient yet effective algorithm. We further extended the model and the algorithm to an unsupervised setting where only the input representation of the samples is available. In a series of empirical evaluation on similarity search tasks, the proposed models reported significantly improved results over the state-of-the-art methods in both search accuracy and running time. The successful results give us strong confidence that the work provides a highly practical tool to real world applications.

1. INTRODUCTION:

Random projection has emerged as a powerful tool in data analysis applications (Bingham & Mannila, 2001) . It is often used to reduce the dimension of a set of data samples in the Euclidean space. It provides a simple and computationally efficient way to reduce the storage complexity of the data by trading a controlled amount of representation error for faster processing speed and smaller model sizes (Johnson & Lindenstrauss, 1984) .

Very recently, with strong biological evidence, a sparse binary projection model called the FLY algorithm was designed and attracted people's much attention. Instead of performing dimension reduction, the algorithm increases the dimension of the input samples with a random sparse binary projection matrix. After winner-take-all (WTA) competition in the output space, the samples are converted into a set of sparse binary vectors. In similarity search tasks, it was reported that such sparse binary vectors outperformed the hashed vectors produced by the classical locality sensitive hashing (LSH) method that is based on the random dense projection (Dasgupta et al., 2017) .

Following the work along this line, we proposed two models with the explicit treatment of the WTA competition. Instead of residing on the random generation of the projection matrix, one of our models seeks the optimal projection matrix under a supervised setting, while the other model operates purely in an unsupervised manner. For each model, we derived an algorithm that is surprisingly simple, yet with highly promising empirical results in both similarity search accuracy and running speed over the state-of-the-art approaches.

A note on notation. Unless specified otherwise, a capital letter, such as W , denotes a matrix. A lower-cased letter, with or without a subscript, denotes a vector or a scalar. For example w i. denotes the i-th row, w .j denotes the j-th column, and w ij denotes the (i, j)-th entry of the matrix W .

The paper is organized as follows. Section 2 introduces the necessary background. Section 3 presents our models and the algorithms. Section 4 reports the experiments and results, followed by the discussion and conclusion in Section 5.

2. BACKGROUND 2.1 SPARSE BINARY PROJECTION ALGORITHMS:

Different from classical projection methods that commonly map data from a higher-dimensional space to a lower-dimensional space, the FLY algorithm increases the dimension of the data. It was designed by simulating the fruit fly's olfactory circuit, whose function is to associate similar odors with similar tags. Each odor is initially represented as a 50-dimensional feature vector of firing rates. To associate each odor with a tag involves three steps. Firstly, a divisive normalization step (Olsen et al., 2010) centers the mean of the feature vector. Secondly, the dimension of the feature vector is expanded from 50 to 2, 000 with a sparse binary connection matrix (Caron et al., 2013; Zheng et al., 2018) , which has the same number of ones in each row. Thirdly, WTA competition is involved as a result of strong inhibitory feedback coming from an inhibitory neuron. After the competition, all but the highest-firing 5% out of the 2, 000 features are silenced (Stevens, 2015) . These remaining 5% features just correspond to the tag assigned to the input odor.

The FLY algorithm can be studied as a special form of the locality sensitive hashing (LSH) method which produces similar hashes for similar input samples. But different from the classical LSH method which reduces the data dimension, the FLY algorithm increases the dimension with a random sparse binary matrix, while ensuring the sparsity and binarization of the data in the output space. Empirically, the FLY algorithm reported improved results over the LSH method (Dasgupta et al., 2017) in similarity search applications.

The success of the FLY algorithm inspired considerable research attention, among which one of particular interest to us is the LIFTING algorithm (Li et al., 2018) that removes the randomness assumption of the projection matrix, which is partially supported by most recent biological discoveries (Zheng et al., 2018) . In the work, the projection matrix is obtained through supervised learning. Suppose training samples with both dense input representation X ∈ R d×m and sparse output representation Y ∈ {0, 1}

d ×m are available. The LIFTING algorithm seeks the projection matrix W

that minimizes W X -Y 2 F + β W 1 2

in the feasible region of sparse binary matrices. To solve the optimization problem, the Frank-Wolfe algorithm was suggested with quite good performance (Frank & Wolfe, 1956; Jaggi, 2013) .

2.2. WINNER-TAKE-ALL COMPETITION:

Evidences in neuroscience showed that excitation and inhibition are common activities in neurons (Stevens, 2015; Turner et al., 2008) . Based on the lateral information, some neurons raise to the excitatory state; while the rest get inhibited and remain silent. The excitation and inhibition result in the competition among neurons. Modeling such neuron competitions is of key importance. Computational models that involve the competition stage are found in wide applications, such as in computational brain models, artificial neural networks and analog circuits design (Arbib, 2003; Maass, 2000) . In machine learning, the competition mechanism has motivated the design of computer algorithms for a long time, from the early self-organizing map (Kohonen, 1990) to more recent work in developing novel neural network architectures (Panousis et al., 2019; Lynch et al., 2019) .

To model the competition stage, the WTA model is routinely adopted. We are interested with a variant of the WTA model with the following form. For a d-dimensional input vector x and a given hash length k (k d), the WTA competition computes a function

EQUATION

Thus the output entries with value 1 just mark the positions of the k-largest values of x. For simplicity and without causing ambiguity, we will not differentiate whether the input/output vector of the W T A function is a row vector or a column vector.

3. MODEL:



3.1. SUPERVISED TRAINING:

Let a set of samples be in the form of X ∈ R d×n and Y ∈ {0, 1} d ×n with each x .m (1 ≤ m ≤ n) being an input sample and y .m being its output representation satisfying y .m 1 = k for a given k. We assume that there exists a projection matrix W ∈ {0, 1} d ×d with each w i.

1 = c (1 ≤ i ≤ d )

for a given c1 , such that each y .m = W T A d k (W x .m ) holds. From the definition of the WTA function in Eq. ( 1), a necessary and sufficient condition for a sparse binary matrix W being the projection matrix for the given samples is:

w i. x .m ≥ w j. x .m , if y im = 1 and y jm = 0 (2)

for all 1 ≤ m ≤ n and 1 ≤ i, j ≤ d .

In a supervised setting, we are interested in seeking such a projection matrix W . But unfortunately, solving the problem directly from Eq. ( 2) is generally hard. A matrix that satisfies all the constraints may not exist for the data due to the noise in observation. Even if it exists, the computational requirement can be non-trivial. A straightforward approach, modeling the problem as a linear integer program, would involve d × d variables and O (nk (d -k) + d ) constraints, which is infeasible to solve even for moderately small n and d .

To handle the difficulty, the problem can be relaxed. For each i, j and m, define a measure

y im (1 -y jm ) (w i. x .m -w j.

x .m ) to quantify the compliance with the condition in Eq. ( 2). For y im = 1 and y jm = 0, the measure has a non-negative value if the condition is met; otherwise, it is negative. Naturally, we sum up the values of the measure over all possible m, i, j, and define

EQUATION

The value of L s (W ) measures how well a matrix W meets the conditions in Eq. ( 2). Maximizing L s with respect to W in the feasible region of sparse binary matrices provides a principled solution to seeking the projection matrix. And we call this the supervised-WTA model.

Considering that

EQUATION

subject to:

EQUATION

, and

EQUATION

Let

EQUATION

and the optimal solution of w i. to Eq. ( 4) is just given by

EQUATION

3.2. UNSUPERVISED TRAINING:

The supervised-WTA model utilizes both input and output representations to learn a projection matrix. When only the input representation is available, we can extend the work to an unsupervised-WTA model, by maximizing the objective:

L u (W, Y ) = n m=1 d i=1 d j=1 y im (1 -y jm ) (w i. x .m -w j. x .m ) (8) satisfying w i. ∈ {0, 1} 1×d , w i. 1 = c, y .m ∈ {0, 1} d ×1 , and y .m 1 = k (9) for all 1 ≤ i ≤ d and 1 ≤ m ≤ n.

Different from the supervised model, this unsupervised model treats the unknown output representation Y as a variable, and jointly optimizes on both W and Y . To maximize L u , an alternating algorithm can be used. Start with a random initialization of W as W 1 , and solve the model iteratively. In t-th

(t = 1, 2, • • • ) iteration, maximize L u (W t , Y

) with respect to Y and get the optimal Y t . Then maximize L u (W, Y t ) with respect to W and get the optimal W t+1 .

The optimal Y t is given by:

EQUATION

for all 1 ≤ m ≤ n. Similarly to the supervised setting, the optimal W t+1 is given by:

EQUATION

for all 1 ≤ i ≤ d , where

t .i = n m=1 x .m y t im -k d . Denote by L t u = L u (W t , Y t ).

Obviously, the sequence {L t u } monotonically increases for t = 1, 2, • • • . Therefore the alternating optimization process is guaranteed to converge when the objective value L t u can't be increased any more. It is worth mentioning that the unsupervised-WTA model can be studied as a clustering method (Jain et al., 1999) . The model puts m data samples into d clusters and each sample belongs to k clusters. A special case of k = 1 corresponds to a hard clustering method. Two samples with the element of one in the same output dimension indicates that they have the same cluster membership.

The unsupervised-WTA model can also be treated as a feature selection method (Guyon & Elisseeff, 2003) . This can be seen from the fact that each output dimension is associated with a subset of c features, instead of all d features in the input space. The model is able to choose these c features automatically and encode the information in the projection matrix W . A detailed discussion of the clustering and the feature selection viewpoints goes beyond the scope of this paper and is hence omitted.

3.3. COMPLEXITY ISSUES:

Solving the supervised-WTA model is computationally straightforward and can be implemented with high efficiency. For each projection vector w i. , a naïve implementation needs O (dn + d log c) operations, among which O (dn) are for the summation operation in Eq. ( 6) and O (d log c) are for the sorting operations in Eq. ( 7). Therefore, computing the whole projection matrix needs O (d dn + d d log c) operations. In fact, by utilizing the sparse structure of the output matrix Y , the computational complexity for W can be further reduced to O (kdn + d d log c). As seen in Section 4.3, this is a highly efficient result. For both WTA models, the memory requirement comes mainly from the matrices X, Y and W , and the storage complexity is O (dn + d n + d d), which can be further reduced to O (dn + kn + d c) if sparse matrix representation is adopted.

The training algorithms are parallelizable. Each vector of W and Y can be solved independently with high parallel efficiency. It is also notable that, after simple pre-processing of the training data, all computations only involve simple vector addition and scalar comparison operations.

4. EVALUATION:



4.1. GENERAL SETTINGS:

To evaluate the performance of the proposed models, we carried out a series of experiments under the following settings.

Application: Similarly to the work of (Dasgupta et al., 2017) , we applied the proposed models in similarity search tasks. Similarity search aims to find similar samples to a given query object among potential candidates, according to a certain distance or similarity measure (Baeza-Yates & Ribeiro-Neto, 1999). The complexity of accurately determining similar samples relies heavily on both the number of candidates and their dimension. Computing the distances seems straightforward, but unfortunately could often become prohibitive if the number of candidates is too large or the dimension of the data is too high.

To handle the difficulty brought by the high dimension of the input data, we can either reduce the data dimension while approximately preserving their pairwise distances, or increase the dimension but confining the data in the output space to be sparse and binary, in the hope of significantly improved search speed with the new representation.

Objective: Our major objective is to evaluate and compare the similarity search accuracies for different algorithms. Each sample in a given dataset was used, in turn, as the query object, and the rest samples in the same dataset were used as the search candidates. For each query object, we compared its 100 nearest neighbors in the output space with its 100 nearest neighbors in the input space, and recorded the ratio of common neighbors in both spaces. The ratio is averaged over all query objects as the search accuracy of each algorithm. Obviously, a higher similarity search accuracy indicates a better preserving of locality structures from the input space to the output space by the algorithm.

Datasets: In the evaluation, three real datasets and five artificially generated datasets were used. The real datasets have the input representation X only; while the artificial datasets have both the input representation X and the ground-truth of the output representation Y . The datasets are:

1. GLOVE: 100to 1000-dimensional GloVe word vectors (Pennington et al., 2014) trained on a subset of 330 million tokens from wikimedia database dumps2 with the 50, 000 most frequent words. 2. MNIST: 784-dimensional images of handwritten digits in gray-scale (LeCun et al., 1998) . 3. SIFT: 128-dimensional SIFT descriptors of images used for similarity search (Jegou et al., 2011) . 4. ARTIFICIAL: five sets of 1, 000-dimensional dense vectors (X) and 2, 000-dimensional sparse binary vectors (Y ). For each hash length of k = 2/4/8/16/32, a set of 2, 000-dimensional sparse binary vectors were randomly generated with the hash length. Then the vectors were projected to 1, 000-dimensional dense vectors through principal component analysis. In this way, the samples' pairwise distances are roughly preserved between the input space and the output space; i.e., x .m -x .m 2 ≈ y .m -y .m 2 for all pairs of samples in the same set.

Algorithms to compare: We compared the proposed supervised-WTA (denoted by SUP) model and the unsupervised-WTA (UNSUP) model with the LSH algorithm (Gionis et al., 1999; Charikar, 2002) , the FLY algorithm (Dasgupta et al., 2017) and the LIFTING algorithm (Li et al., 2018) . The LSH algorithm maps d-dimensional inputs to k-dimensional dense vectors with a random dense projection matrix. The FLY algorithm uses a random sparse binary matrix to map d-dimensional inputs to d -dimensional vectors. The LIFTING algorithm trains a sparse binary projection matrix in a supervised manner for the d-dimensional to d -dimensional projection. Both the FLY and the LIFTING algorithms involve a WTA competition stage in the output space to generate sparse binary vectors for each hash length k.

Besides, we included the comparison with a number of more recent hashing algorithms, including iterative quantization (ITQ) (Gong et al., 2012) , spherical hashing (SPH) (Heo et al., 2015) and isotrophic hashing (ISOH) (Kong & Li, 2012) . These algorithms were popularly used in literature to produce sparse binary data embeddings.

Computing environment: All the algorithms were implemented in MATLAB platform running on an 8-way server, with which 128 threads were enabled for each algorithm. For the LIFTING algorithm, IBM CPLEX was used as the linear program solver that is needed by the Frank-Wolfe algorithm. We carried out the experiments on the artificial datasets and the real datasets. From each ARTIFI-CIAL dataset, we randomly chose 10, 000 training samples with both the input (X) and the output (Y ) representations, and chose another 10, 000 testing samples with the input representation only.

4.2. SIMILARITY SEARCH ACCURACY:

For the supervised-WTA model, we trained a sparse binary projection matrix W , and generated the 2, 000-dimensional sparse binary output vectors for the testing samples with the matrix and after WTA competition. For the LIFTING algorithm, the same training and testing procedures were applied. For all other algorithms, we applied each on the testing samples to get either dense or sparse binary output vectors. Then the output representation is adopted in similarity search and compared against the input representation, as illustrated in Section 4.1.

We repeated the experiments for fifty runs and recorded the average accuracies. In Table 1 , each row shows the similarity search accuracies with the output representations generated by the algorithms with the same hash length3 . Consistent with the results reported in (Dasgupta et al., 2017) , the sparse binary projection algorithms reported improved results over the classical LSH method. It is evidently shown that, with the support of the supervised information, both the LIFTING algorithm and the supervised-WTA model reported further improved results. Most prominently, when the hash length k = 4, the FLY algorithm has an accuracy of 6.73%, while the supervised-WTA model's accuracy reaches 66.7%, almost ten times higher. When comparing the two supervised algorithms, the supervised-WTA model outperformed the LIFTING algorithm with all hash lengths.

When comparing the unsupervised algorithms, the unsupervised-WTA model reported improved results, significantly better than the results on the representations generated by the LSH, FLY, ITQ, SPH and ISOH algorithms. Its performance is even better than the supervised-WTA model when the hash length k = 8.

On GLOVE/MNIST/SIFT datasets, only the input X is available. As suggested in (Li et al., 2018) , we computed

Y * = arg Y min 1 2 X T X -Y T Y 2 F + γ Y 1 2

in the feasible region of sparse binary matrices with the Frank-Wolfe algorithm, and used Y * as the output representation for the supervised models. We carried out the experiments under the same setting as on the ARTIFICIAL datasets. Again the two WTA models reported evidently improved results.

When comparing the two WTA models, the unsupervised-WTA model seems to perform even better than the supervised-WTA model on these real datasets. In the case with known X only, an approximation of Y has to be obtained through matrix factorization. The quality of this approximated Y becomes critical and sometimes the vulnerability for the supervised algorithms. We believe this is one major reason why supervised-WTA no longer excels.

In addition to the experiment on similarity search accuracies, we further investigated the influence of different input/output dimensions on the performance of the proposed models. In this experiment, we fixed the output dimension to d = 2, 000 while varying the input dimension from 100 to 1, 000 on GloVe word vectors. We recorded the similarity search accuracies by all the algorithms. From the results in Table 2 , we can see that the WTA models reported consistently improved results under all settings.

4.3. RUNNING SPEED:

As a practical concern, we measured the training time of our proposed WTA models, and compared it with the LIFTING algorithm. In the experiment, we used the ARTIFICIAL datasets with 1, 000dimensional inputs and 2, 000-dimensional outputs, and the number of training samples varied from 1, 000 to 50, 000.

We recorded the training time by each algorithm to compute the sparse binary projection matrix W . On all training sets, our proposed models reported significantly faster speed over the LIFTING algorithm. With n = 1, 000 samples (ref. Fig. 1(a) ), the supervised-WTA model took less than 0.2 seconds to get the optimal solution, hundreds of times faster than the LIFTING algorithm which used around 50 seconds. While for the LIFTING algorithm, we didn't finish the execution in our platform within 12 hours. All these real results were consistent with the complexity analysis given in Section 3.3, and justified the running efficiency of our proposed WTA models.

5. CONCLUSION:

With strong support from biological science, the study of sparse binary projection models has attracted much research attention recently. Through converting lower-dimensional dense data to higher-dimensional sparse binary vectors, the models have achieved excellent empirical results and provided a useful tool in practical applications.

Biologically, the winner-take-all competition is an important stage for pattern recognition activities that happen in the brain. Our work started from the treatment of the WTA competition, and proposed two models to seek the desired projection matrix for sparse binary projections. The supervised-WTA model utilizes both input and output representations of the samples, and trains the projection matrix as a supervised learning problem. The unsupervised-WTA model requires the input representation only, which equips the model with wider application scenarios. For the models, we have developed simple, efficient and effective algorithms. In the evaluation, our models significantly outperformed the state-of-the-art methods, in both search accuracy and running time.

Our work potentially triggers a number of topics. Firstly, the algorithms for both models are simple, only involving vector addition and scalar comparison operations. The algorithms are highly parallelizable. Such characteristics make the computing procedures suitable to be implemented with customized hardware such as in the FPGA platform (Omondi & Rajapakse, 2006) , which will provide a high-throughput and economical solution for large scale data analysis applications.

Secondly, the unsupervised-WTA model has a natural relationship with the clustering and the feature selection models. It provides a unified framework that combines these two techniques. We believe that investigating new clustering and feature selection applications following this viewpoint is possible. More importantly, we believe that clustering and feature selection may be a potential bridge that helps to make clear why modeling the WTA competition could lead to algorithms that preserve the locality structures of the data well, as reported in this paper.

The third potential is in designing new artificial neural network architectures. The approach adopted in this paper can be used as an activation function of the neurons in an artificial neural network. We highly anticipate future research work along this line (Pehlevan et al., 2018; Lynch et al., 2019) .

:

Following the work of(Dasgupta et al.,

2017), c is set to 0.1 × d in this paper.

https://dumps.wikimedia.org/

Following the work of(Dasgupta et al., 2017;Li et al., 2018), the hash length is defined as the number of ones in each output vector for the FLY, LIFTING and WTA algorithms. For other algorithms, it is defined as the output dimensionality.

Figures and Tables:

To solve the unsupervised-WTA model, each iteration we need to compute both Y and W . Solving one Y needs O (cdn + d d log k) operations by utilizing the sparse structure of W , where O (cdn) are for multiplying W with X and O (d d log k) are for the sorting operations in Eq. (10). Computing one W has the same complexity as in the supervised-WTA model, O (kdn + d d log c). Therefore, the total complexity per iteration is O ((k + c) dn + d d log (kc)), which is also an efficient solution as seen in Section 4.3.

Figure 1: Comparison of running time on ARTIFICIAL dataset with different number of training samples (n= 1, 000/5, 000/10, 000/50, 000). The horizontal axis is the hash length (k = 2/4/8/16/32). The vertical axis is the running time (seconds) in log-scale. When n = 50, 000, the LIFTING algorithm didn't finish within 12 hours and its result is not reported.

Comparison of similarity search accuracies on various datasets with fixed output dimension (d = 2, 000).

Table content: <table><tr><td>Datasets</td><td>k</td><td>SUP</td><td>UNSUP</td><td>LSH</td><td>FLY</td><td>LIFTING</td><td>ITQ</td><td>SPH</td><td>ISOH</td></tr><tr><td/><td>2</td><td>0.1758</td><td>0.1143</td><td>0.0174</td><td>0.0474</td><td>0.1748</td><td>0.0103</td><td>0.0097</td><td>0.0101</td></tr><tr><td>ARTIFICIAL</td><td>4</td><td>0.6665</td><td>0.3531</td><td>0.0243</td><td>0.0673</td><td>0.6134</td><td>0.0175</td><td>0.0138</td><td>0.0227</td></tr><tr><td>d = 1, 000</td><td>8</td><td>0.3647</td><td>0.3944</td><td>0.0259</td><td>0.0376</td><td>0.2612</td><td>0.0360</td><td>0.0173</td><td>0.0331</td></tr><tr><td/><td>16</td><td>0.5884</td><td>0.3267</td><td>0.0278</td><td>0.0402</td><td>0.1694</td><td>0.0367</td><td>0.0202</td><td>0.0349</td></tr><tr><td/><td>32</td><td>0.3141</td><td>0.1319</td><td>0.0324</td><td>0.0443</td><td>0.0832</td><td>0.0382</td><td>0.0235</td><td>0.0375</td></tr><tr><td/><td>2</td><td>0.1317</td><td>0.1596</td><td>0.0217</td><td>0.0511</td><td>0.0831</td><td>0.0221</td><td>0.0195</td><td>0.0198</td></tr><tr><td>GLOVE</td><td>4</td><td>0.2310</td><td>0.3251</td><td>0.0356</td><td>0.0964</td><td>0.1458</td><td>0.0617</td><td>0.0311</td><td>0.0594</td></tr><tr><td>d = 300</td><td>8</td><td>0.3061</td><td>0.3959</td><td>0.0655</td><td>0.1073</td><td>0.1914</td><td>0.1209</td><td>0.0591</td><td>0.1112</td></tr><tr><td/><td>16</td><td>0.4030</td><td>0.4495</td><td>0.1138</td><td>0.1809</td><td>0.2851</td><td>0.1939</td><td>0.1004</td><td>0.1882</td></tr><tr><td/><td>32</td><td>0.4374</td><td>0.4323</td><td>0.2039</td><td>0.2808</td><td>0.3917</td><td>0.3208</td><td>0.1717</td><td>0.2727</td></tr><tr><td/><td>2</td><td>0.2860</td><td>0.2476</td><td>0.0369</td><td>0.1119</td><td>0.1159</td><td>0.0288</td><td>0.0237</td><td>0.0194</td></tr><tr><td>MNIST</td><td>4</td><td>0.3338</td><td>0.3829</td><td>0.0844</td><td>0.1721</td><td>0.2003</td><td>0.0852</td><td>0.0649</td><td>0.0773</td></tr><tr><td>d = 784</td><td>8</td><td>0.3885</td><td>0.4387</td><td>0.1823</td><td>0.2717</td><td>0.3044</td><td>0.2008</td><td>0.1443</td><td>0.1601</td></tr><tr><td/><td>16</td><td>0.4698</td><td>0.4957</td><td>0.3226</td><td>0.3953</td><td>0.4150</td><td>0.3207</td><td>0.2559</td><td>0.3101</td></tr><tr><td/><td>32</td><td>0.5108</td><td>0.5207</td><td>0.4773</td><td>0.5162</td><td>0.5130</td><td>0.4415</td><td>0.3616</td><td>0.4067</td></tr><tr><td/><td>2</td><td>0.1706</td><td>0.1502</td><td>0.0355</td><td>0.1066</td><td>0.1139</td><td>0.0274</td><td>0.0272</td><td>0.0230</td></tr><tr><td>SIFT</td><td>4</td><td>0.2240</td><td>0.2278</td><td>0.0760</td><td>0.1592</td><td>0.2120</td><td>0.0550</td><td>0.0596</td><td>0.0623</td></tr><tr><td>d = 128</td><td>8</td><td>0.3768</td><td>0.3912</td><td>0.1556</td><td>0.2382</td><td>0.3059</td><td>0.0951</td><td>0.1153</td><td>0.1240</td></tr><tr><td/><td>16</td><td>0.4353</td><td>0.4461</td><td>0.2751</td><td>0.3409</td><td>0.3529</td><td>0.1712</td><td>0.1993</td><td>0.1905</td></tr><tr><td/><td>32</td><td>0.4839</td><td>0.4751</td><td>0.4122</td><td>0.4504</td><td>0.4295</td><td>0.3217</td><td>0.2582</td><td>0.2832</td></tr></table>

Comparison of similarity search accuracies on GLOVE dataset with various input dimensions and fixed output dimension (d = 2, 000).

Table content: <table><tr><td>Dimension</td><td>k</td><td>SUP</td><td>UNSUP</td><td>LSH</td><td>FLY</td><td>LIFTING</td><td>ITQ</td><td>SPH</td><td>ISOH</td></tr><tr><td/><td>2</td><td>0.1007</td><td>0.1210</td><td>0.0208</td><td>0.0503</td><td>0.0982</td><td>0.0245</td><td>0.0229</td><td>0.0230</td></tr><tr><td/><td>4</td><td>0.1720</td><td>0.2274</td><td>0.0335</td><td>0.0787</td><td>0.1449</td><td>0.0683</td><td>0.0452</td><td>0.0633</td></tr><tr><td>d = 100</td><td>8</td><td>0.2365</td><td>0.2816</td><td>0.0591</td><td>0.1059</td><td>0.1898</td><td>0.1509</td><td>0.0705</td><td>0.1297</td></tr><tr><td/><td>16</td><td>0.3113</td><td>0.3572</td><td>0.1096</td><td>0.1698</td><td>0.2279</td><td>0.2201</td><td>0.1232</td><td>0.1995</td></tr><tr><td/><td>32</td><td>0.3779</td><td>0.3831</td><td>0.1962</td><td>0.2581</td><td>0.2954</td><td>0.3311</td><td>0.2398</td><td>0.2952</td></tr><tr><td/><td>2</td><td>0.0808</td><td>0.1073</td><td>0.0183</td><td>0.0387</td><td>0.0733</td><td>0.0231</td><td>0.0223</td><td>0.1234</td></tr><tr><td/><td>4</td><td>0.1432</td><td>0.2030</td><td>0.0275</td><td>0.0624</td><td>0.1037</td><td>0.0692</td><td>0.0395</td><td>0.0212</td></tr><tr><td>d = 200</td><td>8</td><td>0.2008</td><td>0.2551</td><td>0.0459</td><td>0.0786</td><td>0.1363</td><td>0.1197</td><td>0.0624</td><td>0.1256</td></tr><tr><td/><td>16</td><td>0.2759</td><td>0.3189</td><td>0.0816</td><td>0.1284</td><td>0.1712</td><td>0.1804</td><td>0.1105</td><td>0.1905</td></tr><tr><td/><td>32</td><td>0.3254</td><td>0.3331</td><td>0.1442</td><td>0.1991</td><td>0.2391</td><td>0.3025</td><td>0.2051</td><td>0.2782</td></tr><tr><td/><td>2</td><td>0.0689</td><td>0.0866</td><td>0.0148</td><td>0.0226</td><td>0.0490</td><td>0.0197</td><td>0.0173</td><td>0.0182</td></tr><tr><td/><td>4</td><td>0.1328</td><td>0.1702</td><td>0.0195</td><td>0.0394</td><td>0.0711</td><td>0.0522</td><td>0.0301</td><td>0.0397</td></tr><tr><td>d = 500</td><td>8</td><td>0.1878</td><td>0.2252</td><td>0.0278</td><td>0.0421</td><td>0.0892</td><td>0.0973</td><td>0.0521</td><td>0.0885</td></tr><tr><td/><td>16</td><td>0.2768</td><td>0.2696</td><td>0.0437</td><td>0.0710</td><td>0.1188</td><td>0.1497</td><td>0.0995</td><td>0.1305</td></tr><tr><td/><td>32</td><td>0.3172</td><td>0.2727</td><td>0.0728</td><td>0.1115</td><td>0.1806</td><td>0.2119</td><td>0.1502</td><td>0.2117</td></tr><tr><td/><td>2</td><td>0.0464</td><td>0.0508</td><td>0.0132</td><td>0.0172</td><td>0.0293</td><td>0.0177</td><td>0.0166</td><td>0.0179</td></tr><tr><td/><td>4</td><td>0.0985</td><td>0.1131</td><td>0.0162</td><td>0.0288</td><td>0.0396</td><td>0.0356</td><td>0.0289</td><td>0.0322</td></tr><tr><td>d = 1, 000</td><td>8</td><td>0.1447</td><td>0.1615</td><td>0.0214</td><td>0.0303</td><td>0.0490</td><td>0.0434</td><td>0.0312</td><td>0.0365</td></tr><tr><td/><td>16</td><td>0.2115</td><td>0.2071</td><td>0.0305</td><td>0.0474</td><td>0.0662</td><td>0.0912</td><td>0.0787</td><td>0.0883</td></tr><tr><td/><td>32</td><td>0.2194</td><td>0.2049</td><td>0.0464</td><td>0.0699</td><td>0.0874</td><td>0.1507</td><td>0.1339</td><td>0.1303</td></tr></table>

/10, 000/50, 000). The horizontal axis is the hash length (k = 2/4/8/16/32). The vertical axis is the running time (seconds) in log-scale. When n = 50, 000, the LIFTING algorithm didn't finish within 12 hours and its result is not reported.The unsupervised-WTA model needs to solve multiple W t and Y t iteratively. It spent 10 to 20 seconds, which was slower than the supervised-WTA model but several times faster than the LIFTING algorithm. With n = 50, 000 training samples (ref.Fig. 1(d)), the supervised-WTA model took less than 10 seconds, and the unsupervised-WTA model took around 400 seconds to get the solutions.

Table content: <table/>

Peer review (iclr2020):
The paper takes the binary projection framework used for LSH-type applications (based on Dasgupta et al. 2017) and given training data from that framework, shows an efficient closed-form solution update for the *projection* matrix, and also derives an alternating minimization algorithm for when training data are not available (note that these are not training data in a typical supervised learning sense, i.e., they are not data features, but rather the output of a projection of the very specific type discussed in the paper). The idea is interesting, and the recent literature suggest that the overall idea works well. This new paper seems to work much better than recent literature (and a lot faster than some), which is very encouraging. The derivation of the closed-form updates is clever and seems to be correct. Overall, I am quite favorable for this paper. My chief critical comment is that given the complexity of the model, is is feasible to compare to PCA-based projections as well. That is, usually PCA is not compared with these methods since a random projection method is faster. But this paper proposes data-dependent projection matrices, which is exactly what PCA does. This paper has been implicitly assuming d << n and trying to avoid the O(n^2) cost of nearest neighbor search. Given that d << n, the complexity of the algorithm in the paper is, roughly (avoiding some logs), O((#iter) d^2 n ), since the constant *c* depends on d, and presumably d* also scales linearly with d. The (#iter) refers to the number of iterations of the alternating minimization. The actual constants are small, but it is still quadratic in d. PCA takes O(d^2n + d^3) operations when d<n, so therefore PCA is of roughly the same complexity, and thus I*d expect you to compare to it in the numerical comparisons. With a valid response to the issue of PCA, I would probably *strongly accept* this paper. (Another note on comparisons: it seems Johnson-Lindenstrauss projections would be applicable, so I*d suggest running a Fast Johnson-Lindenstrauss (Ailon and Chazelle) to compare with also). Minor notes: - In section 3.3, how do you get complexities like d log(c) for finding the top c entries? Please cite an algorithm textbook. I might be rusty on this, but the algorithms I can think of to do this are O( min( d log(d), d c )) operations. Same for the d* log(k). - A good number of sentences were grammatically incorrect or sounded awkward, e.g., paragraph 2, *people*s much attention*; second sentence in section 2.2, the phrase *; while the rest get inhibited and remain silent* is not a complete phrase by itself (maybe change the semicolon to a comma). Overall, another round of proof reading would help.