Modeling Winner-Take-All Competition in Sparse Binary Projections
Authors: Wenye Li
Venue:  (2020)
Keywords: Sparse Representation
Sparse Binary Projection
Winner-Take-All

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.


Under review as a conference paper at ICLR 2020
MODELING WINNER-TAKE-ALL COMPETITION IN SPARSE BINARY PROJECTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Inspired by the advances in biological science, the study of sparse binary pro- jection models has attracted considerable recent research attention. The models project dense input samples into a higher-dimmensional space and output sparse binary data representations after Winner-Take--ll competition, subject to the con- straint 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 simple, efficient yet effective algorithm. We further extended the model and the algorithm to an unsupervised setting where only the imput 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-ane methods in both search accuracy and running time. The successful results give us strong confidence that the work pro- vides highly practical tool to real world applications.
INTRODUCTION
Random projection has emerged powerful tool in data analysis applications (Bingham & Man- nila 2001). It is often used to reduce the dimension of a set of data samples in the Euclidean space. It provides 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, 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 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 mod- els seeks the optimal projection matrix under a supervised setting, while the other model operates purely in an unsupervised manner. For each model, we derived algorithm that is surprisingly simple, yet with highly promising empirical results in both similarity search accuracy and running speed over the state-of-the- tfr approaches.
A note on notation. Unless specified otherwise, capital letter, such as W, denotes a matrix. A lower-cased letter, with without subscript, denotes vector scalar. For example w, denotes the i-th row, w denotes the j-th column, and Wiy denotes the (i, entry of the matrix W.
The paper is organized as follows. Section 2 introduces the necessary background. Section presents our models and the algorithms. Section 4 reports the experiments and results, followed by the discussion and conclusion in Section

---

Under review as a conference paper at ICLR 2020
2 BACKGROUND
2.1 SPARSE BINARY PROJECTION ALGORITHMS
Different from classical projection methods that commonly map data from a higher-dimensional space to 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 a 50-dimensional feature vector of firing rates. To associate each odor with a tag involves three steps. Firstly, divisive normalization step (Olsen al. 2010) centers the mean of the feature vector. Secondly, the dimension of the feature vector is expanded from 50 to 2, 000 with 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 result of strong inhibitory feedback coming from an inhibitory neuron. After the competition, all but the highest-firine 5% out 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 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 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 discov- eries (Zheng al. 2018). In the work. the projection matrix obtained through supervised learning. Suppose training samples with both dense input representation X E Rdx and sparse output rep- resentation Y E f0, 11d xm are available. The LIFTING algorithm seeks the projection matrix W that minimizes ||WX X I| + B |WI]l in the feasible region of sparse binary matrices. To solve the optimization problem, the Frank-Wolft 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 al.| 2008). Based the lateral information, some neurons raise to the excitatory state; while the rest get inhibited and remain silent. The excitation and inhibition re- sult 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 com- puter algorithms for 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 a and a given
hash length & (k & d), the WTA competition computes a function WT 4 Rd (0,1 with the output y WT Ag (xr) satisfying, for each 1 < i d.
y = {
1, if x; is among the la-legest entries of (#1,"", ,.d). 0, otherwise.
Thus the output entries with value 1 just mark the positions of the k-largest values of z. For sim- plicity and without causing ambiguity. we will not differentiate whether the input/output vector of the WTA A function is vector or column vector.
2

---

Under review as a conference paper at ICLR 2020
3 MODEL
3.1 SUPERVISED TRAINING
Let set of samples be in the form of X Rd and Y (0, (0,1) with each x.m (1 v S being an input sample and V.m being its output representation satisfying llu Il = k for given k. We assume that there exists a projection matrix W {0, 1) dddx with each ||w, = c i for given cا such that each y.m = WTA (Wz.m) holds.
From the definition of the WTA function Eq. D. a necessary and sufficient condition for a sparse binary matrix W being the projection matrix for the given samples is:
Wr m
m. if yim 1 and Vjm
for all 1 v S and 1 iij
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 linear integer program, would involve d' x d variables and O (nk (d' k) + d') constraints, which is infeasible solve even for moderately small and d'.
To handle the difficulty, the problem can be relaxed. For each i, and m, define measure Vim (1 yjm) (W. W F.m) ) to quantify the compliance with the condition Eq. (2). For Vim and fjm = 0, the measure has non-negative value if the condition is met; otherwise, it is negative. Naturally, we sum up the values of the measure over possible m, i, and define
L. (W) ΣΣΣ Utm (1 yjm) (W,.F.m W....m..
(3)
The value of Lg (W) measures how well matrix W meets the conditions in Eq. Maximizing Lg with respect to W in the feasible region of sparse binary matrices provides principled solution seeking the projection matrix. And call this the supervisedWTTA model.
Considering that
d' W 2.m
max Lg (W)
max
Vim Wi
mm
i=
j=l
d'
d'
k
max
Vim Wt,
Wi, X.
d'
m=
1=1
max
Vim
d'
W. F.
m=
k
Σ
max
W/s
F.m
Yim
d'
Therefore, maximizing La (W) is equivalent to d' maximization sub-problems. Each sub-problem seeks row vector wi. (1 S < d') by
d' )
max W/,
Σ x Lmml
yim
(4)
subject to:
Wy. E 1) xd
and
||w;. ||
(5)
FFllooiig the work of (Dasgupta et al. 2017 c to [0.1 d] in this paper.
3

---

Under review as a conference paper at ICLR 2020
Let
1:
f, =
Vim
(6)
d'
m=1
and the optimal solution of wo, to Eq.
(4) is just given by
w WTA (C.)..
3.2 UNSUPERVISED TRAINING
The supervised WTT model utilizes both input and output representations to learn a projection ma- trix. When only the input representation is available, we can extend the work to an unsupervised- WTA model, by maximizing the objective:
Lu (W, Y)
Vom (1 Gjm) (W. I. W.
(8)
j=1
satisfying
W/.- E {0, 1] xd || 11l = y.m E (0,1) and 1l..mll
for all 1 ssisa d' and 1 S <
Different from the supervised model, this unsupervised model treats the unknown output represen- tation Y as a variable, and jointly optimizes on both W and Y. To maximize Ly. an alternating algorithm can be used. Start with a random initialization of W as W and solve the model itera- tively. In t-th Yr. Then maximize L. (W, Y") with respect to W and get the optimal W
2, ...) iteration, maximize L, (W', Y) with respect to Y and get the optimal
The optimal Y given by:
y.m = WT A (W'x.,)
(10)
for all 1 < < Similarly to the supervised setting, the optimal W=++1 is given by:
wf WTA (E.)
(11)
for all 1 S i S d', where E, = Em== I.m (vfm +
monotonically increases for == .... Therefore the alternating optimization process is guaranteed converge when the objective value L can't 't be increased any more.
Denote by L Lu (W', Y*). Obviously, the sequence {LS}
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. special case of i: corresponds
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 subset of features, instead of all 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-WTTA model is computationally straightforward and can be implemented with high efficiency. For each projection vector w.., naive implementation needs (dn + d lo c) operations, among which O (dn) are for the summation operation in Eq. (6) and O (d e) are for the sorting operations in Eq. (7). Therefore, computing the whole projection matrix needs O (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' log c). As seen Section 4.3 this is highly efficient result.
4

---

Under review as a conference paper at ICLR 2020
To solve the unsupervised WTA model, each iteration we need compute both Y and W. Solving one Y needs O (cdn + 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. (1O). Comput- ing one W has the same complexity as in the supervised- -TTA model, O (kdn + d' d log c). There- fore, the total complexity per iteration is O ((k: c) dn + d' d' log (kc)), which also efficient solution as seen in Section 4.3
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) 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.
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 similarity measure (Baeza-Yan 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 too large or the dimension of the data is too high.
Application:
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 representation.
Our major objective is to evaluate and compare the similarity search accuracies for different algorithms. Each sample in 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, higher similarity search accuracy indicates better preserving of locality structures from the input space to the output space by the algorithm.
Objective:
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:
GLOVE: 100- to 1000-dimensional GloVe word vectors (Pennington et al. 2014) trained on sub- set of 330 million tokens from wikimedia database dumps 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 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 of 2, 000-dimensional sparse binary vectors were randomly generated with the hash length. Then the vectors were projected 1, d00-dimmesionall dense vectors through principal component analysis. In this way, the sam- plcs' pairwise distances are roughly preserved between the input space and the output space; i.c., ||..m F. mm I|u.. y.m for all pairs of samples in the same set.
hhups//damppssiiiimediaaog
5

---

Under review as a conference paper at ICLR 2020
Algorithms to compare: We compared the proposed supervised-WTH 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 al. (017) 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 random sparse binary matrix to map d-dimensional inputs to d' d'-dimensional vectors. The LIFTING algorithm trains a sparse binary projection matrix in supervised manner for the d-dimensional to d' o'-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
Besides. we included the comparison with number of more recent hashing algorithms. including iterative quantization (ITQ) (Gong et al. 2012), spherical hashing (SPH) (Heo al.) 2015) and isotrophic hashing (ISOH) (Kong & Li, 2012). These algorithms were popularly used in literature to produce sparse binary data emheddings.
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.
4.2 SIMILARITY SEARCH ACCURACY
Table 1: Comparison of similarity search accuracies various datasets with fixed output dimension
(d' = 2, 000).
Dacasets
SUP
UNSUP
LSW
FLF
LIFTING
TTQ
SPW
ISOH
0.1758
0.1143
0.0174
0.0474
0.1748
0.0103
0.0097
0.0101
ARTIFICIAL
0.3531
0.0215
0.0813
0.8133
0.0175
0.0138
0.0227
d' 1,000
0.3647
0.3044
0.0259
0.0370
0:2812
0.0360
0.0173
0.0331
16
0.8884
0.3266
0.0278
0.0402
0.1009
0.0387
0.0202
0.0349
0.3141
0.1319
0.0324
0.0443
0,0832
0,0382
0.0235
0,0375
0.1317
0.1590
0.0217
6.0511
0,0831
0.0221
0.0195
0.0198
GLOVE
0,2310
0.8251
0.0356
0.00164
0.1458
0.0617
0.0311
0.00534
d 300
D.3061
0.3959
0.0655
0.1073
0.1914
0.1209
0.0591
0.1112
0.4030
0.4495
0.1148
0.1809
0.2851
0.1939
0.1004
0.1882
0.4374
0.4323
0.2039
0,26008
0.3017
0.3208
0.1717
0.2727
O. 2828
0.2476
0.0364
0.1119
0.1159
0.0288
0.0237
0.0194
MNSST
0.3338
0.3820
0.0844
0.1221
0.2003
0.0852
0.0840
0.0173
0.3865
0.438
0.1622
0.2717
0.3044
2008
1443
0.4698
0.4957
0.3226
0.3953
0.4150
0.3207
0.2550
0.310
32
0.3108
0.5207
0.4773
0.5162
0.5130
0.4415
0.3816
0.4067
0.1706
0.1502
0.0855
0.1066
0.1139
0.0274
0.0272
0.0230
SIFT
D.2249
0.2278
0.0760
0.1592
0.2120
0.0550
0.0596
d 128
D.3763
0.3912
0.1656
0.2352
0.3059
0.0351
0.1153
0.1240
D.4353
0.4461
0.2751
0.3409
0.3029
0.1712
0.1993
0.1900
0.4839
0.4751
0.4122
0.3217
0.2582
Table 2: Comparison of similarity search accuracies on GLOVE dataset with various input dimen- sions and fixed output dimension (d' 2, 000).
Dimension
SUP
UNSUP
7S8
FLY
LIFTING
7TQ
SPH
ISOR
U. 0.1007
0.1210
0.0208
0.0503
0.0962
0.0245
0.0229
0.0250
0.1720
0. 2274
0.0335
0.0787
0.1449
0.0883
0.0452
0,0033
0.2365
0.2816
0.0591
0.1059
0.1509
0.0705
0.1297
0.3113
0.3572
0.1096
0.1698
0.2279
0.2201
0.1252
0.1995
32
D.3779
0.3881
0.1962
0.2681
0.2964
0.3311
0.2398
U.
0.0808
1078
0.0183
0.0733
0.0231
0.0228
D.1432
0.2030
0.0274
0.0024
0.1037
0.0802
0.0396
0,0212
d = 200
0.2008
o 0821
0.0455
0.0750
0. 0.13
0.17
0.0624
0. 2256
D.2775
0.3189
0.0818
0.14
0.1712
0. 1014
0.1
0. 1900
0.3254
0.3331
0.1412
0.19
0,2391
0,3025
0,2051
0.2182
0.0689
0.0866
0.01.88
0.0226
0.0490
0.0197
0.0178
U.D182
0.1328
0.1702
0.0195
0.0394
0.0711
0.0522
0.0301
0.0397
d
0.1878
0.2262
0.0278
0.0421
0.0899
0.0973
0.0621
0,0886
0.2768
0.2896
0.0437
0.0710
0.1188
0.1497
0.0995
0.1305
32
0.3172
0.2727
0.0723
0.15
0.1806
0.2119
0.1202
0.2117
0.0464
0.0508
0.0132
0.0172
0:0293
0.0177
0.0166
0.0179
0.00085
0.1131
0.0162
0.0238
0.0356
0.0289
d 1, 0000
0.144
0.1618
0.0214
0.0303
0.0490
0.044
0.0312
0.0355
16
0.2115
0.2071
0.0300
0.0174
0.0662
0.0012
0.0787
0.0853
0.2199
0.2049
0.0464
0.06531
0.0874
0.1507
0.1330
0.1303
6

---

Under review as a conference paper at ICLR 2020
We carried out the experiments the artificial datasets and the real datasets. From each ARTIFI- CIAL dataset, we randomly chose 10, 000 training samples with both the imput (X) and the output (Y) representations, and chose another 10, 000 testing samples with the input representation only. For the supervised-WTI WTT model, we trained a sparse binary projection matrix W, and generated the 2, 000-dimennioonll 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 ap- plied. For all other algorithms, we applied each on the testing samples get either dense or sparse binary output vectors. Then the output representation is adopted in similarity search and compared against the imput representation, as illustrated in Section 4.1
We repeated the experiments for fifty runs and recorded the average accuracies. In Table each row shows the similarity search accuracies with the output representations generated by the algorithms with the same hash lengtt Consistent with the results reported in (Dasgupta et al. 2017). the sparse binary projection algorithms reported improved results over the classical LSH method. 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 model's
length &s = 4, the FLY algorithm has accuracy of 6. 6.73%, while the supervised-W accuracy reaches %6, almost ten times higher. When comparing the two supervised algorithms, the supervised 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 the representations generated by the LSH, FLY, ITQ, SPH and ISOH algorithms. Its performance is even better than the supervised-We -TT model when the hash length 8.
On GLOVE/MNIST/SIFT datasets, only the input X is available. As suggested in (Li et al. 2018
computed Y argy min 2 X -y y ||Y||| in the feasible region of sparse bi- nary 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 on the ARTIFICIAL datasets. Again the two WTA models reported evidently improved results.
When comparing the two WTA models, the unsupervised-WTT model seems to perform even better than the supervised- -WT-isdddd--------- model on these real datasets. In the case with known X only, an approx- imation 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-WTT 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 we can see that the WTA models reported consistently improved results under all settings.
4.3 RUNNING SPEED
As practical concern, measured the training time of our proposed WTA models, and compared with the LIFTING algorithm. In the experiment, we used the ARTIFICIAL datasets with 1, 000- dimensional 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 compute the sparse binary projection matrix W. On all training sets, our proposed models reported significantly faster speed over the LIFTING algorithm. With n 0.2 seconds to get the optimal solution, hundreds of times faster than the LIFTING algorithm which used around 50 seconds.
0000 samples (ref. Fig. a)), the supervised-W -TA model took less than
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 F.Y LIFTING and WTA algorithms. For other algorithms, it is defined as the output dimensionality.
7

---

Under review as a conference paper at ICLR 2020
01
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 2//48/116/ 16 6/3)). The vertical axis is the running time (seconds) in log-scale. When n = 50, 000, the LIFTING algorithm didn't 'tt't finish within 12 hours and its result not reported.
Figure I:
The unsupervised-V WTAA model needs to solve multiple W and Y iteratively. spent to 20 sec- onds, which was slower than the supervised-W7T WTA model but several times faster than the LIFTING algorithm. With n = 50, 000 training samples (ref. Fig. d)), the supervised-WTr model took less than 10 seconds, and the unsupervised- WTA model took around 400 seconds to get the solutions.
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 dibber-dimensoona sparse binary vectors, the models have achieved excellent empirical results and provided 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 -TA model utilizes both input and output representations of the samples, and trains the projection matrix as a supervised learning problem. The unsupervised-WTI -TA 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-fe the-art art methods, in both search accuracy and running time.
Our work potentially triggers number of topics. Firstly, the algorithms for both models are simple, only involving vector addition and scalar comparison operations. The algorithms are highly par- allelizable. Such characteristics make the computing procedures suitable to be implemented with customized hardware such as in the FPGA platform (Omondi & Rajapakse 2006), which will pro- vide high-throughput and economical solution for large scale data analysis applications.
Secondly, the unsupervised-We WTA model has a natural relationship with the clustering and the fea- ture selection models. It provides 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 potential bridge that helps to make clear why modeling the WTT competition could lead to algorithms that preserve the locality structures of the data well, reported in this paper.
The third potential is in designing new artificial neural network architectures. The approach adopted in this paper can be used 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).
ACKNOWLEDGMENTS
Suppressed for blind review.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
M. Arbib. The Handbook of Brain Theory and Neural Networks, MIT Press, 2003.
R. Baeza- Yates and B. Ribeiro-Neto. Modern Information Retrieval, volume 463. ACM Press, 1999.
E. Bingham and H. Mannila. Random projection in dimensionality reduction: applications image and text data. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 245-250. ACM, 2001.
Caron, V. Ruta, L. Abbott, and Axel. Random convergence of olfactory inputs in the drosophila mushroom body, Nature, 497(7447):113, 2013.
M. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 380-388. ACM, 2002.
Dasgupta, C. Stevens, and S. Navlakha. A neural algorithm for fundamental computing problem. Science, 35666)6))773 2017.
M. Frank and Wolfe. An algorithm for quadratic programming. Naval Research Logistics, 3(1-2): 95-110, 10, 1956.
A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In Pro- ceedings of 25th International Conference on Very Large Data Bases, volume 99, pp. 518-529, 1999.
Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence,
2012.
I. Guyon and A. Elisseeff. An introduction variable and feature selection. Journal of Machine Learning Research, 115- 2003.
J. Heo, Y. Lee, J. He, S. Chang, and S. Yoon. Spherical hashing: Binary code embedding with hyperspheres. IEEE transactions on pattern analysis and machine intelligence, 37(11)2 2316, 2015.
M. Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, pp. 427-435, 2013.
A. Jain, N. Murty, and P. Flynn. Data clustering: areview ACM Computing Surveys, 31(3):264-323, 1999.
H. Jegou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. JEEE Transactions Pattern Analysis and Machine Intelligence, 33(1):117-128, 2011.
W. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into Hilbert space. Contem- porary Mathematics, 26(189-206):,, 1984.
T. Kohonen. The self-organizing map. Proceedings of the IEEE, 78(9):1464-1480, 1990.
W. Kong and W. Li. Isotropic hashing. In Advances in neural information processing systems, pp- 1646-1654, 2012.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based based learning applied to document recognition. Proceedings of the IEEE, 36(11):2278-2324 1998.
W. Li, Mao, Y. Zhang, and S. Cui. Fast similarity search via optimal sparse lifting, In Advances in Neural Information Processing Systems, pp. 176-184, 2018.
N. Lynch, C. Musco, and M. Parter. Winner-take-all computation in spiking neural networks. arXiv preprint
2019.
W. Maass. On the computational power of winner-take-all. Neural computation, 12(11))2519-255 2535,, 2000.

---

Under review as a conference paper at ICLR 2020
S. Olsen, V. Bhandawat, and R. Wilson. Divisive normalization in olfactory population codes. Neuron, 66(2):287-299. 2010.
A. Omondi and J. Rajapakse. FPGA Implementations of Neural Networks, volume 365. Springer, 2006.
K. Panousis, Chatzis, and S. Theodoridis. Nonparametric bayesian deep networks with local competition. In Proceedings of the 36th International Conference on Machine Learning. 2019.
C. Pehlevan, A. Sengupta, and D. Chklovskii. Why do similarity matching objectives lead to aaahaa//antihebbbia networks? Neural Computation, 30(1):84-124, 2018.
J. Pennington, R. Socher, and C. Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pp- 1532-1543, 2014.
C. Stevens. What the flys nose tells the flys brain. Proceedings the National Academy of Sciences, 112(30):960-9445; 2015.
G. Turner, M. Bazhenov, and Laurent. Olfactory representations by drosophila mushroom body neurons. Journal of Neurophysiology, 99(2):734-746, 2008.
Z. Zheng, S. Lauritzen, E. Perlman, C. Robinson, al. A complete electron microscopy volume of the brain of adult drosophila melanogaster. Cell, 174(3):73--743 2018.
10


Reviews:
[{"review_id": "r1lgqMYTKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a Winner-Take-All model that learns a sparse binary representation for dense vectors. The method learns a binary lifting matrix to project low-dimension vectors into higher dimension, and apply WTA to get a final binary embedding with fixed number of 1s. I find this paper interesting and good extension of exiting lifting method. Please see my detailed comments:\n\n1. The assumption of the existence of W seems strong. I understand in reality it may not hold but shouldn't affect the representation learning and downstream applications of the binary vector, but is there any work done to estimate whether it holds in general or only for d' in some range?\n\n2. In experiments, both the supervised and unsupervised methods are compared. For the supervised version and for search accuracy evaluation, what is the ground truth? E.g. what's the label for Glove data?\n\n3. Is the term in equation (3) first proposed in this paper or already used before? \n\n4. How to choose the value of d' in practice? How to balance the speed and representation quality?\n\n5. Is there an information theoretical way to evaluate whether y has encoded near complete information from the previous vector? Or the high-dimension binary vector only works in practice without deeper theories?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkxKdAolqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nThe 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.\n\nMy 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.\n\nWith a valid response to the issue of PCA, I would probably \"strongly accept\" this paper.\n\n(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).\n\nMinor notes:\n- 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).\n\n- 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BklLKjNaYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors 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. The authors further extended the model and the algorithm to an unsupervised setting where only the input representation of the samples is available.\n\nOverall I think this paper is clearly presented with some good experiment results. \n\nI have the following concerns:\n\n1)As for the supervised setting, may I know in what kind of real-world applications we can find the OPTIMAL binary and sparse output representation?  Why can we assume they are optimal?\n\n2)Is this algorithm can really work on a large scale problem? The mnist level dataset is far from giving strong evidence in claiming this point. A larger dataset like ImageNet is preferred. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a WTA models for binary projection.  While there are notable partial contributions, there is disagreement among the reviewers.   I am most persuaded by the concern expressed that the experiments are not done on datasets that are large enough to be state-of-the-art compared to other random projection investigations.
Decision: Reject