Semantic Hashing with Locality Sensitive Embeddings
Authors: Levi Boyles
Aniket Anand Deshmukh
Urun Dogan
Rajesh Koduru
Charles Denis
Eren Manavoglu
Venue:  (2021)
Keywords: Semantic Hashing
Approximate Nearest Neighbor

Abstract: Semantic hashing methods have been explored for learning transformations into binary vector spaces. These learned binary representations may then be used in hashing based retrieval methods, typically by retrieving all neighboring elements in the Hamming ball with radius 1 or 2.  Prior studies focus on tasks with a few dozen to a few hundred semantic categories at most, and it is not currently well known how these methods scale to domains with richer semantic structure.  In this study, we focus on learning embeddings for the use in exact hashing retrieval, where Approximate Nearest Neighbor search comprises of a simple table lookup. We propose similarity learning methods in which the optimized similarity is the angular similarity (the probability of collision under SimHash.)  We demonstrate the benefits of these embeddings on a variety of domains, including a coocurrence modelling task on a large scale text corpus; a rich structure of which cannot be handled by a few hundred semantic groups.

Under review as a conference paper at ICLR 2021
SEMANTIC HASHING WITH LOCALITY SENSITIVE EM- BEDDINGS
Anonymous authors Paper under double-blind review
ABSTRACT
Semantic hashing methods have been explored for learning transformations into binary vector spaces. These learned binary representations may then be used hashing based retrieval methods. typically by retrieving all neighboring elements in the Hamming ball with radius or 2. Prior studies focus on tasks with a few dozen to a few hundred semantic categories at most, and it is not currently well known how these methods scale to domains with richer semantic structure. this study, we focus on learning embeddings for the use in exact hashing re- trieval, where Approximate Nearest Neighbor search comprises of simple table lookup. We propose similarity learning methods in which the optimized base sim- ilarity is the angular similarity (the probability of collision under SimHash.) We demonstrate the benefits of these embeddings on a variety of domains, including coocurrence modelling task a large scale text corpus; the rich structure of which cannot be handled by a few hundred semantic groups
INTRODUCTION
One of most challenging aspects in many Information Retrieval (IR) systems is the discovery and identification of the nearest neighbors of query element in an vector space. This is typically solved using Approximate Nearest Neighbors (ANN) methods as exact solutions typically do not scale well with the dimension of the vector space. ANN methods typically fall into one of three categories: space partitioning trees, such the kd-tree (Bentley (1975); Friedman et al. (1977); AAyy et al. (1998), neighborhood graph search (Chen al. (201 8); wasaki & Miyazaki (018)) or Locality
Sensitive Hashing (LSH) methods (Charikar (2002); Gionis et al. (1999): Lv et al. (2007)).
Despite their theoretical, intuitive, and computational appeal, LSH methods are not as prevalent in modern IR systems as space-partitioning trees neighborhood graph methods (Bernhardsson (013 ; ies demonstrate that LSH techniques frequently do not attain the same level of quality space- partitioning trees (Muja & Lowe 2009)).
Chen et al.; (2018); Johnson et al.] (2017); Iwasaki & Miyazaki (2018)). Empirical stud-
Nonetheless, space-partitioning and neighborhood graph search methods expensive, both in data structure construction and in query time, and remain a bottleneck in many modern IR pipelines. As many modern retrieval tasks revolve around solving ANN for vector representations learned from raw, structured data, one might attempt to learn representations which are more suited towards efficient retrieval. Metric learning methods (Xing al. (2003); Weinberger et al. (2006); Chechik et al. 2010);Hoffee & Ailon (2015): Kulis et al. (2013) have been proposed for learning linear and non-linear transformations of given representations for improved clustering and retrieval quality. A class of related methods, semantic hashing or hash learning methods (Salakhutdinov & Hinton (2009), have also been explored for learning transformations into binary vector spaces. These learned binary representations may then be used in hashing based retrieval methods, typically by retrieving all neighboring elements the Hamming ball with radius or 2.
Exact hashing retrieval algorithms, that is, Hamming ball "search" with radius O, have particular computational appeal in that search data structures are not needed nor is enumeration of all codes within Hamming ball. In addition, binary representations that are suitable for exact hashing trieval can also be used to identify groups of related items that can be interpreted as clusters in the traditional sense. As the number of clusters discovered by the algorithm isn't explicitly controlled

---

Under review as a conference paper at ICLR 2021
(only bounded by 2*.) algorithms generating binary embeddings suitable for exact hashing retrieval can be viewed as nonparametrie clustering methods.
To this end, we propose method for learning continuous representations in which the optimized similarity is the angular similarity. The angular similarity corresponds to the collision proba- bility of SimHash, a hyperplane based LSH function (Charikar (2002)). Angular distance gives a sharp topology on the embedding space which encourages similar objects have nearly identical embeddings suitable for exact hashing retrieval.
Related work on similarity learning, LSH, and hash learning can be found in Section 2 The proposed models are found in Section 3] The experimental results, and other technical details, can be found in Sections 4 Finally, we conclude in Section 5
2 PRELIMINARIES
2.1 SIMILARITY MODELLING
Similarity learning methods class of techniques for learning similarity function between objects. One successful approach for similarity learning are "twin network" or "two tower architec- ture" models, which two neural network architectures are joined to produce a similarity prediction (Bromley et al. (1994); Chopra et al.] (2005): Huang et al. (2013)). The weights of these networks may be shared or not, depending on whether the two input domains are equivalent or not.
Let i E U and across which similarity function is tations for the objects (these functions & may be identity functions if the input domains are dis- crete.) These representations are then transformed through parameterized vector-valued functions f.(00 and (-00)) whose output are typically the learned representations u, fu (1) and 0/ = fo.
V be the identities of two objects, where 2 and V are the two domains
learned. Let (i) and (),()) be the input represen-
A loss is then defined using pairwise labels Myy and an interaction function s(u,, 12) which denotes the similarity or relevancy of the pair. Taking fa to be a mapping for each index to an independent parameter vector u, (similarly for fo and v.), and taking s(u,, 02) =u," with appropriate loss results in a variety of matrix factorization approaches (Koren et al. (2099) Lee & Seung (200T);
Mnih & Salakhutdinov (2088:
Blei al. 22033; Rendle et al. 2212 Pennington al. (2014)).
Taking fu to be a neural network mapping a context (1) to a representation u, allows for similarity models that readily make use of complex contextual information. Common choices for the similarity function include transformations of Euclidean distance (Chopra et al. (2005)), and cosine similarity:
s(u;, U2)
|| (Huang et al. (2013)) addition, the loss can be defined for pairs (Chopra
let al.] (2005) ), triplets (one positive pair, one negative pair) (Rendle et al. (2012): Chechik et al.
(2010) ) or on larger sets (Huang et al. (2013)).
2.2 LOCALITY SENSITIVE HASHING AND ANGULAR SIMILARITY
A Locality Sensitive Hash (LSH) family F is distribution of hashes ht on collection of objects Q such that for gi, qj E Q (Indyk & Motwani 1998); Gionis et al. (1999; Charikar (2002)
Pr[h(g)) = M(g;)] = s(g.,)) 4)
(I)
for some similarity function s the objects. SimHash (Charikar 2002 is LSH technique de- veloped for document deduplication but may be used in other contexts. For a vector representations q Rd, SimHash draws random matrix Z E Rdx with standard Normal entries. The hash h((:)) E 1) 1 is then constructed as h(q:m 1 19 Z.m 0].
(2)
Intuitively, SimHash draws random hyperplanes intersecting the origin to separate points. A useful property of this hash function, as stated in Charikar (2002), that
1
q. gj
(g g;)= = Pr(h(g.m h(g,)m) = 1 cos -1
π
||::
|gp
2

---

Under review as a conference paper at ICLR 2021
Casine Distance SimHash Calisiinn Probability
Cosine Distanci Varfous SiillrRiies
0.0
0.99
Caltoon PoNAMRPCC
0.0
0.940
07
0.003
0.973
0,970
Logatic
0.4
0.963
DCC
16
1.0d
10
10"3
1.0
10.
10
1.0
1.07
3010
3000
1.2
Cocne Dictance
Contre Oitance
Figure 1: (left) Response of 8-bit SimHash collision probability vs. cosine distance. The plot indicates that vectors that are extremely close cosine distance may not collide under SimHash. For example, cosine distance of 0.001 corresponds to a collision probability of only 0.9. (right) Response of various similarities vs cosine distance. Angular distance (1-bit Simhash collision prob- ability) induces the sharpest topology. The DCH distance uses y and d = 32.
where the above probability is measured with respect to Z. (/g, q3), the collision probability for two vectors, is also known as the angular similarity, and & v is the angular distance, which is proper metric (unlike the cosine distance 1 1 of
|19.11l1,11 ). As the columns of Z are independent, the collision probability for a K bit hash v.K.
2.3 LEARNING TO HASH
related approach to similarity learning is hash learning methods, introduced in Salakhutdinov Hinton (2009). These methods train binary embeddings directly and then hash collisions or Hamming Ball search to retrieve approximate nearest neighbors. Binary representations lead to some technical challenges: Salakhutdinov & Hinton (2009) uses contrastive divergence for train- ing, whereas Hubara et al. (2016) implement binary threshold activation functions with stochastic neurons.
Another approach (and the one followed in this work) is to avoid explicit binary representations in training and introduce an quantization loss penalize embeddings that are not close to binary, and to subsequently threshold these bear-binary embeddings to binary ones. This type of quantization loss is distinct from those used vector quantization methods (Ahalt al. (1990); Kohonen [990);; Sato & Yamada (1996)) in which the data representations are fixed and the codes are learned; here the codes are fixed and the representations are learned.
The quantization loss introduced in Deep Hashing Networks (DHN) Zhu et al. (2016) is of the form
6(u,10)
log cosh (Juaal 1) ~= ||| 1||
(3)
Other quantization losses based on distances to binary codes have been used in Li et al. (2016);
Liu et al. (2016). Cao et al. (2017) utilizes a quantization loss whose strength increases over time. Finally, Deep Cauchy Hashing (DCH) (Cao et al. (2018)) has shown improvements by utilizing htavy-tailed similarity function with a similarly inspired quantization loss.
3 LOCALITY SENSITIVE EMBEDDINGS
Many similarity learning methods utilize dot products or cosine similarity to relate the embeddings of a pair to each other. For example GloVe (Pennington et al. (2014)) minimizes the weighted error between the dot product of the embeddings and log-coocurrence matrix, and the DSSM model (Huang et al. (203)) utilizes cosine similarity as the "crossing" layer between the two halves of a twin network. In general, embeddings trained in this way are not suitable for SimHash retrieval, as can be seen Figure]] [
If models are trained so as to minimize the error of a prediction made by cosine similarity, extremely low tolerances required in order achieve embeddings with
3

---

Under review as a conference paper at ICLR 2021
significant collision probability. Similar observations the misspecifiation of cosine distance for Semantic Hashing were made in [Cao et al. (2018). In this section, we define models in which collision probabilities of learned representations are directly optimized.
3.1 Loss DEFINITION
In the following, we define population loss through a data distribution D of relevant and irrelevant pairs, Each sample from D a tuple (y, i.j) {0, 1} V. where and V are the sets across which a similarity is to be learned - for example, "users" and "items" in recommender system. the relevancy of the pair (i.j)-
The population losses we consider are expectations over DD of a per-tuple loss with regularization terms r per item:
((O) = E W.jDD
Mly, i,,1, + Ar(1 + Ar(j10)-
(4)
In practice, minimize the empirical loss Ż constructed from finite sample from D, and r(1)0) = b(u,)0) defined in equation
! represents all parameters of the model, including any learned representations for the elements of the sets and V. An embedding п, for element i may either be a vector of free parameters, as would be in fixed vocabulary embedding model, may be the output of model u, = ((.()))) as would be in twin network model. In addition, each half of the pair (u, vy) may represent a different input space, as in the DSSM model.
input:
3.2 BINARY CROSS ENTROPY Loss
We may simply model the relevancy Vi for the pair (u,, vy) with binary cross entropy loss:
Uyng (,) = Yij log (f(vn)li, 0)) 3(1 - yis) ) log (1 p(yis (. 0)).
(5)
where á is the learned estimate for Fi 0). and relative importance of positive and negative samples. One standard choice for in representation learning is to take
scalar hyperparameter for tuning the
u Uy ||lll|
((ur)i,,,0) = 8. so,, (;);;;))000 =
(6)
where the logistic function and a scalar. As the logistic function saturates quickly, the embeddings and by do not need to be extremely close (when Dij is positive) in order to achieve hashing retrieval, we might
low error. Thus, encourage representations that are amenable consider other transformations of the embeddings that do not saturate quickly. For example, one may take polynomial transformation of cosine similarity:
p(ytyli, sc(u,, 12)
(1 (1
(1+
uf Uj ||e||||a,|]
2
or polynomial transformation of the angular similarity:
cos uf 0y |
PV.r)li.500 +uu, ,(),,,,)*
π
The P(ycyli.j.) v((,, choice has a natural interpretation of using the SimHash collision probability under K bit hash as the estimation function. Intuitively, we are training representa- tions whose collision probability distribution under SimHash has minimum cross entropy with the pairwise label distribution y. Embeddings trained with equation g are termed Locality Sensitive Embeddings (LSE) and are the proposed method of this paper. Deterministic thresholding still used to derive binary embeddings from dense versions.
DCH Cao et al. 2018) introduced the following similarity measure for defining the loss:
7
p(yiy j. 8) sn. (u4 01)= :
(9)
7 + d
2
T
4

---

Under review as a conference paper at ICLR 2021
Table 1: Results of Tuned Models on SBM Experiment
Model
K
5
Hard Negatives?
Prec
Rec
F1
COS
4
False
0.3
0.724 = 0.030
0.679 = 0.028
0.701 = 0.027
DCH
False
3.0
0.924 0.021
0.916 = 0.008
0.920 0.012
DHN
2
False
0.3
0.415 0.017
0.124 + 0.010
0.191 + 0.013
LSE
2
True
0.1
0.992 + 0.005
0.986 + 0.005
0.989 0.005
3.3
TOPOLOGICAL ANALYSIS
The SimHash method and the angular similarity can be used for studying the topologies induced by the different similarity measures in the previous section.
Theorem 1.
Let B(g) = (66, qs: 1 8) denote a ball around with radius under the - distance. For an arbitrary point 9 E B(q.). we can consider the probability qj and qu will collide under SimHash - denote this with (0). Then,
(LSE) (6)
2. (COS) Ps, (5) 21 2vσ - 0(02)
(12
4y6 (22(118)) )² 0
3. (DCH) Ps.. (8) 21
know the asymptotic enror for each (for LSE there no error term). Theorem 1 reveals that, for similarity model trained to tolerance level for positive pairs, under SimHash algorithm LSE would have linear scaling of single bit collision probability, while COS and DCH would have sublinear scaling.
Proof in Appendix. These bounds tight
Note that for the logistic based similarity, Ps,, (6) is only well defined for |log(d)- (old)>-logh log(1 8)1 (otherwise So cannot be below 5.) Any analysis here requires choosing a rate for a.
There is also relationship between Angular and Hamming distances. Angular distance be viewed as a dimension scaled version of Hamming distance applied to randomly rotated inputs.
Lemma 1. Let bgg) be the vector indicating signs of qs. that b(q: )m := 1 [gin > 0), Denote the Hamming distance of the sign vectors as pH (g: 9;) = [lb(g)) b(g;)lli which defines semimetric on Rd. Take R as uniformly random orthogonal matrix. Then
1 (1s,, 9i) Balpn (Ry,, Rgy)]-
(10)
Proof in Appendix. Lemma [ demonstrates that angular distance may viewed as an expectation of dimension- scaled Hamming distance, where the expectation is taken with respect to the choice of basis. In other words, minimizing angular distance is cquivalent to minimizing the Hamming semimetric Pи averaged over all possible bases.
4 EXPERIMENTS
In this section, compare representations trained using equation (LSE), using equation (COS), using DHN's logistic based similarity, and using DCH. All methods use the quantization loss in equation from Zhu et al. (2016), except DCH which uses the quantization loss from Cao et al. 2018).
4.1 SYNTHETIC DATA
We generate data from Stochastic Block Model (SBM) (Holland et al. (1983) with 500 factions, 10 individuals per faction, and the probability of an edge appearing between two individuals belonging factions and governed by the matrix of probabilities W e 50500x500 500 with W., 0.8I(
0)+0.1T(0 ji-5l +ell((-i) >= 3). The resulting cooccurrence matrix D E {0, 1) 30000x0000
5

---

Under review as a conference paper at ICLR 2021
16
0.8
Roc
2.
0.6
2.6
0.4
3A
02
22
0.0
300
3.0
F1
Prct
6.3
Adc
64-
64
62
60
120
Unditar Soatttr
Figure 2: Results of the SBM experiment hyperparameter search, sliced by different variables. Each set of bars represents the scores of the highest F1 model with the listed constraint.
Table 2: Mean Average Precision Image Models
Dutasets
Cifar-10
NUS Wide
ImageNet
Methods Metrics
48
32
48
32
16
DHN
0.779
0.776
0.773
0.777
0.821
0.818
0.809
0.790
0.518
0.473
0.423
0.400
DCH
0.774
0.777
0.780
0.772
0.763
0.761
0.759
0.742
0.564
0.583
0.607
0.558
COS
0.802
0.802
0.797
0.778
0.792
0.788
0.775
0.757
0.638
0.634
0.616
0.558
LSE
0.789
0.786
0.788
0.772
0.758
0.753
0.742
0.732
0.594
0.586
0.567
0.505
roughly block diagonal, with additional edges appearing from "nearby" factions at lower rate. The task is to hash the individuals from each faction together, while separating them from all other factions. In order to enable higher precision of the resulting models, set of hard negatives is generated by taking pairs (i,j) such that D)é > 0 and Dij 0. Easy negatives are also generated by taking pairs random and assuming cooccurrence of 0, common in Noise Contrastive Estimation (Gutmann & Hyvärinen (2010) inspired methods.
Each individual is given free parameter u; which is the output of embedding layer followed by tanh activation. This output is dropped-out (shared randomization for each half of the training pair) before the cosine similarity computation. Batches constructed from 1024 positive pairs, and 3072 negative pairs (1024 of which may either be hard or easy negatives, determined as hyperparameter.)
We trained all models with 32 dimensional representations, for 50 epochs, where epoch is the number of batches required to iterate through all positive pairs. We explore 4 hyperparameters, 8, X, and the use of hard negative samples. During evaluation, we retrieve all individuals which have the same binarized embedding as the query individual. We measure precision, recall and Fl-score with the data generating factions as the target. 10 trials are repeated for each hyperparameter setting, and the mean over trials is reported. Figure 2 shows a detailed view of the hyperparameter tuning, and Table T shows the chosen hyperparameters for each model when ranking by Fl Fl-score. DCH and LSE are competitive, however the LSE model is able to achieve surprisingly accurate recovery of the data generating structure with an F1 of nearly 0.99.

---

Under review as a conference paper at ICLR 2021
Table 3: Tuned Parameters and Performance of 100-Epoch Models on OSCAR dataset
Model
K
B
Tr. Prec.
Tr. Rec
Tr. F1
WP
Ts. IIR@50
Ts. HRR@500
Clusters
DHN
12
1
0.3
0.031
0.005
0.008
0.042
0.004
0,009
14K
COS
16
2
0.3
0.301
0.186
0.230
0.279
0.040
0.100
298K
DCH
4
4
3.0
0.345
0.185
0.241
0.264
0,045
0.115
253K
LSE
8
4
0.3
0.412
0.260
0.319
0.291
0.048
0.150
313K
Table 4: Example Clusters Discovered
Cluster Words
Cluster Size
Author Annotations
basil, honey, vinegary, ribeye, grilling,.. ...
1134
Generic Food Vegan Terms Coral Species
vegan, veganism, cleaneating, vegano, plantpower, ...
28
scleractinia, pertusa, pistillata, acropora, hystrix, ... bristle, tinged, mohair, metallic, inseam,
14
1208
Generic Style/Fashion
4.2 HAMMING BALL IMAGE RETRIEVAL ON IMAGE DATASETS
The experiment on image datasets is motivated from state of the art methods which build binary embeddings directly and use hashing retrieval for image similarity search. In this section we demon-
strate that LSE is appropriate for these tasks as well. We follow the experimental setup as in Zhu
al. (2016) on three datasets: Cifar- 10 Krizhevsky et al. 2209), NUS-WIDE Chua al. (2009)
and Meageeet(Ruusskknn
et al. (0155). C0 is a dataset consisting of 10 categories and 60000
color images size 32 x 32. We use the same data splits (available online) as Zhu et al. (2016):
500 images per category in training set, 100 images per category it test query set and the remaining
54000 images are used as database. We again follow Zhu et al. 2016) for experiments with NUS- WIDE dataset: 149736 images that associated with 21 most frequent categories database and 2100 images as queries, and 10500 images from the database as training set. For ImageNet, we use the same 100 categories Cao et al. (2017) the indexing database and the 13000/5000 image train/test split. We follow [Co et al. (0188) and use pretrained AlexNet as described. We take the open-source code for deep hashing methods Zhu et al. (2016)) and add the LSE model. Results are shown in Table 2 We show results for binary embedding size of 64 bits, 48 bits, 32 bits, and 16 bits. We do not alter any other setting and use K 1, 0.1 for all models. In pilot experiments we did not find any significant improvement for higher K for any of the methods. All baseline papers use mean average precision for the evaluation (Cao et al. 2018)); Zhu et al. (2016)) which is the evaluation method we adopt for this experiment. The LSE model is comparable to the baseline methods. Cifar10 results are statistically significant with the p-vuuue of 7.5 x 10 NUS Wide with the p-value of 2.81 10-14t and Imagenet with the p-value of 7.99 10 according to widely used Iman Daveport test (Garcia & Herrera 2008). We want to point out that all the experimental results (originally in the respective baseline papers and in this paper) on DCH and DHN have used pretrained AlexNet. The usage of pretrained network and well separated categories reduces the need for a model with a strong inductive bias like LSE, Nonetheless LSE remains good choice for these type of tasks as well.
4.3 OSCAR COOCCURRENCE MODEL
Finally, we compare all methods on a cooccurrence matrix generated from the OSCAR English dataset (Ortiz Suarez al. 2019); Ortiz Suarez et al. (2020).. We take the deduplicated version of the corpus (1.2TB compressed) and generate an initial symmetric cooccurrence matrix by counting word pairs with window of size 10, inversely weighting the counts by the distance of the words within the sentence, as in Pennington et al. (2014). This initial matrix is then filtered to remove extremely common terms, extremely rare terms. Additional filtering based on row and column nor- malized cooceurrences is used to retain pairs that are atypical compared to the marginal frequencies of the two terms. For each row, the top 100 pairs ranked by the original cooccurrence are kept, and the resulting binary matrix is symmetrized. The resulting cooccurrence matrix D has 660K unique
https::/gitthee http://hhttb..cmommoo////////aa/

---

Under review as a conference paper at ICLR 2021
0.30
0.25
0.00
WP
0.6
0.08
Figure 3: Results of the OSCAR experiment hyperparameter search, sliced by different variables. Each set of bars represents the scores of the highest combined WP+FI measures (where WP is Wu- Palmer similarity described main text) with the listed hyperparameter value fixed. Fl score are computed on query set randomly sampled from the 660K vocabulary, and is computed by performing retrieval on the full 660K vocabulary. Wu-Palmer similarity computed on the 46K WordNet evaluation vocabulary, with query set sampled from the WN vocabulary. (bottom right) T-SNE plot the dense embeddings assigned single hash cluster ("Generic Food"), revealing additional structure
words, with 16M nonzero entries. set of hard negatives is generated by taking pairs (i,j) such that (D D)as and Dij 0. 4600 pairs from 1) are held out for the final evaluation.
Popular models for text data frequently allow for each word's representation to have multiple con- texts, in topic modelling (Hofmann (1999); Blei et al. (2003) or multi-sense embedding models (Nguyen et al. (2017)). To incorporate multiple context representations into semantic hashing meth- ods, represent each word with L embeddings uą (these are free parameters per word and no subword information is used.) The maximum among all pairwise cosine similarities is then taken as the base similarity function:
Uim
s(u,, ug)
max 1.m
(11)
|
This base similarity is then used in place of cosine similarity in defining the loss for all model At retrieval time, a query word is mapped to its L hashes, corresponding to L "clusters." " The union of the clusters is the retrieved set for the query - no search is performed and the only data structures used are hash tables. As each word is associated with I. hashes, this model may be understood "word2hashes" method.
The base architecture used for all models is 32 dimension tanh activated embedding layer fol- lowed by dropout (with shared randomization across all 2L embeddings.) with L = 3. Following the dropout layer is equation [T] Batches are constructed from 8192 positíves, 8192 hard negatives, and 16384 easy negatives. Models are trained for 20 epochs through the positive set using 2 GPUs.
We utilize a semantic quality measure based on Wu-Palmer similarity (WP) (Wu & Palmer (1994) on WordNet (WN) (Miller (1995); Fellbaum et al. (1998)). We take all nouns, verbs and adjectives from the WordNet corpus and remove all words with no hypernyms (these are typically isolated nodes in the WordNet graph for which WP values are not available.) The intersection with the 660K
As DHN uses the unnormalized inner product, for which the max operation has undesirable properties, modify the DHN implementation 5s(u, uy) the input the logistic function.
8

---

Under review as a conference paper at ICLR 2021
vocabulary leaves 46K words, which we index based the semantic hashing models. For each query word w and its retrieved set Vww), the average WP similarity is computed across all pairs w, u with e (w). Self-pairs are removed, and empty V(w) are given O values. This WP measure is bounded between and 1, with higher values indicating more semantically meaningful clusters.
IK word query set (taken randomly from the 46K WN vocabulary) which we use as a tuning data set. We also report F1 score on a IK query set sampled from the 660K vocabulary to evaluate how well each model reconstructs the training data. All models used the same tuning grid, except COS for which K = 16 was added, as the initial sweep showed potentially large improvement by expanding the grid for the COS model.
Figure 3 shows WP of the models
Table shows the final model comparison. The hyperparameters with highest WP per model are taken and models for each are trained with 100 epochs. We compare the scores of these models on non-tuning set of IK queries from WN for WP, and 1K queries from the full vocab for Precision, Recall, and F1. addition, we evaluate HitRatio (HR) score on the heldout 4600 pairs, where all colliding words for query are retrieved, and if the target word appears in the top items ranked by cosine similarity (of the dense embeddings.) the query achieves HR I. This the only measure to use the dense embeddings. We also report the number of non-singleton clusters. As can be seen, LSE outperforms the baselines on training, test, and semantic quality measures
We display some example queries and their retrieved hash siblings from the 100 epoch LSE model in Table T-SNE Maaten Hinton (2008) plots of the dense embeddings on WordNet vocabulary shown in Figures 5 6 and 7 Within the discrete hash based clusters used in retrieval, there is still additional structure in the dense embeddings that may be leveraged. This can be seen from T-SNE plots (Figures and [ of the dense embeddings that collide together in the "Generic Food"
cluster seen in Table
CONCLUSION
We extend semantic hashing methods problems with substantial label noise and the exact hash- ing retrieval case via the introduction of Locality Sensitive Embeddings, which leverage angular similarity as the main component of an output prediction. The learned representations show su- perior performance in the exact hashing retrieval setting. We applied LSE to multiple-cone representation learning model to cooccurrence matrix generated from the OSCAR English corpus, producing a "word2hashes" model which is novel to the best of the authors' knowledge.
REFERENCES
Stanley C Ahalt, Ashok Krishnamurthy, Prakoon Chen, and Douglas E Melton. Competitive learning algorithms for vector quantization. Neural networks, 3(3):277-290, 1990.
Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM) 45(6):99199) 1998.
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communi- cations of the ACM, 1809):5095517, 1975.
Erik Bernhardsson. Annoy approximate nearest neighbors in c++//pthhon optimized for memory usage and loading/saving to disk. hhttps:// http:/tthh......oooo/oe.tooooo/t http://poofffy//aaa 2013.
David M Blei, Andrew Y Ng, and Michael I Jordan. Latent dirichlet allocation. Journal of machine Learning research, 399 2003.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verifi- cation using a "siamese" time delay neural network. In Advances in neural information processing systems, pp. 737-744, 1994.
*DH performs poorly here as it is unable to proper handle the inclusion of hard negative samples. See A.I for ablation study and discussion of the impact of hard negatives.
9

---

Under review as a conference paper at ICLR 2021
Yue Cao, Mingsheng Long, Bin Liu, and Jianmin Wang. Deep cauchy hashing for hamming space retrieval. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1229-1237, 2018.
Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Philip S Yu. Hashnet: Deep learning hash by continuation. In Proceedings of the IEEE international conference on computer vision, pp- 5608 5617,56172220 2017.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 380-388. ACM, 2002.
Gal Chechik, Varun Sharma, Uri Shalit, and Samy Bengio. Large scale online learning of image similarity through ranking. Journal Machine Learning Research, 11 (Mar):: 109-1133 135, 2010.
Qi Chen, Haidong Wang, Minggin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. SPTAG: A library for fast approximate nearest neighbor search, 2018. URLptttpe thub. com
wwm/Micciiccccoocoocoooooooe htt:/Micooos crosoft//PSA
Sumit Chopra, Raia Hadsell, Yann LeCun, al. Learning similarity metric discriminatively, with application to face verification. In CVPR (1), pp. 539-546, 2005.
Tat-Seng Chua, Jinhui Tang, Richang Hong, Haojie Li, Zhiping Luo, and Yantao Zheng. Nus-wide: real-world web image database from national university of singapore. In Proceedings of the ACM international conference on image and video retrieval, pp. 1-9, 2009.
Christiane Fellbaum et al. Wordnet: An electronic database, 1998.
Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), (3):209-226, 1977.
Salvador Garcia and Francisco Herrera. An extension on" statisscll comparisons of classifiers over multiple data for all pairwise comparisons. Journal of machine learning research, 9(Dec): 2677-2694, 2008
Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search in high dimensions via hashing. In Vldb, volume 99, pp. 518-529, 1999.
Michael Gutmann and Aapo Hyvärinen. Doise-contrastive estimation: A new estimation principle for unnormalized statistical models. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International Workshop on Similarity- Based Pattern Recognition, pp. 84-92. Springer, 2015.
Thomas Hofmann. Probabilistic latent semantic indexing. In Proceedings of the 22nd annual in- ternational ACM SIGIR conference Research and development in information retrieval, pp- 50-57, 1999.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-1:)) 1983.
Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. Learning deep structured semantic models for web search using clickthrough data. Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pp. 2333-2338, 2013.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in neural information processing systems, pp. 4107-4115, 2016.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium Theory of computing, pp. 604-613. ACM, 1998.
Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv: /810007355 2018.
10

---

Under review as a conference paper at ICLR 2021
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion- scale similarity search with gpus. arXiv preprint arXiv:1702.087. 2017.
Teuvo Kohonen. Improved versions of learning vector quantization. In 1990 ijenn international joint conference on Neural networks, pp. 545-550. IEEE, 1990.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Brian Kulis et al. Metric learning: A survey. Foundations and Trends in Machine Learning, 5(4): 287-364, 2013.
Daniel D Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems, pp. 556-562, 2001.
Wu-Jun Li, Sheng Wang, and Wang-Cheng Kang. Feature learning based deep supervised hash- ing with pairwise labels. In Proceedings of the Twenty-Fithe International Joint Conference Artificial Intelligence, pp. 1711-1717, 2016.
Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen. Deep supervised hashing for fast im- age retrieval. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2064-2072, 2016.
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe Ish: efficient indexing for high-ding nigh-dimensional similarity search. In Proceedings of the 33rd international confer- ence on Very large data bases, pp. 950-961. VLDB Endowment, 2007.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (Nov):2579-2605, 2008
George A Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(11): 39-41, 1995.
Andriy Mnih and Russ R Salakhutdinov. Probabilistic matrix factorization. In Advances in neural information processing systems, pp. 1257-1264, 2008.
Marius Muja and David G Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP (1), 2(331-340):2, 2009.
Dai Quoc Nguyen, Dat Quoe Nguyen, Ashutosh Modi, Stefan Thater, and Manfred Pinkal. A mixture model for learning multi-sense word embeddings. arXiv preprint 1.Xiv:1706.055
2017.
Pedro Javier Ortiz Suarez, Benoit Sagot, and Laurent Romary. Asynchronous pipelines for process- ing huge corpora on medium to low resource infrastructures. Proceedings of the Workshop on Challenges in the Management of Large Corpora (CMLC-7) 2019. Cardiff, 22nd July 2019, pp. 9 - 16, Mannheim, 2019. Leibniz-Institut für Deutsche Sprache. doi: 10.14618/ica pubd---ub--
URL httphhtpp:///bt reso ving. de/urn mbo : :e bsz mh39 90215.
Pedro Javier Ortiz Suarez, Laurent Romary, and Benoit Sagot. A monolingual approach to con- textualized word embeddings for mid-resource languages. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguisties, pp. 1703 1703-1714, Online, July 2020. As- sociation for Computational Linguistics. URL htl.http::/ /wwww a c web. www./aattttteooo ogy/
2200. acl-main 156.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-15453 2014. URL TtRLhttp://///
awwweb. ort/ htwp://.......aatooooooo//------
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv: /20..2/00.2222 28,, 2012.
11

---

Under review as a conference paper at ICLR 2021
40
60-
60
20 40 80
20 60
80
Figure 4: (left) Subset of SBM dataset, indicating near block block-diagonal structure. (right) Hard neg- atives sampled for SBM dataset
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-252 2015.
Ruslan Salakhutdinov and Geoffrey Hinton. Semantic hashing. International Journal of Approxi-
mate Reasoning, 50(7):969-97) 9778,,, 2009.
Atsushi Sato and Keiji Yamada. Generalized learning vector quantization. In Advances in neural information processing systems, pp. 423-429, 1996.
Kilian Q Weinberger, John Blitzer, and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. In Advances in neural information processing systems, pp. 1473- 1480, 2006.
Zhibiao Wu and Martha Palmer. Verb semantics and lexical selection. arXiv preprint cmp- 1g/9406033, 1994.
Eric Xing, Michael Jordan, Stuart Russell, and Andrew Ng. Distance metrie learning with application to clustering with side-information. In Advances in neural information processing systems, pp. 521-528, 2003.
Han Zhu, Mingsheng Long, Jianmin Wang, and Yue Cao. Deep hashing network for efficient simi- larity retrieval. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
A APPENDIX
A.1 EFFECT OF HARD NEGATIVES AND ABLATION STUDY
In this section we study the impact of hard negatives. Recall from the main text that we define hard negatives from a dataset D by taking pairs where (DD D)s; > O and Dij = 0. See Figure for diagram showing these hard negative pairs on the SBM synthetic data.
We performed an experiment on the OSCAR dataset in which modified loss function is used where hard negatives samples are weighted (that is, easy negatives are always given weight of 1.) These tuned models are compared to the tuned models of the main text in Table 5 This tuning gives modest improvement to COS and DCH models in terms of WP (and degradation for LSF..) while keeping Fl much the same. However, DCH is not able to obtain the same Fl measure LSE (in either tuning.) In addition, the LSE model from the original tuning outperforms the other models in WP+F1. Also note that the DHN model improves substantially on the removal of Hard Negatives, however it still remains the worst performing algorithm of the four.
We also use this experiment to perform ablation study, Table 6 DHN is most competitive when hard negatives are removed, achieving the highest WP (but still lowest F1.) It is also this case where see LSE achieve a Recall of 0.54 this metric is essentially traded-off for Precision
12

---

Under review as a conference paper at ICLR 2021
Table 20-Epoch Models on OSCAR Dataset with Various Tuning Criteria
Tuning Criteria
Model
K
B
A
Tr. Prec.
Tr. Rec
Tr. Fl
WP
DHN
12
1
0.0
0.018
0.003
0.004
0.047
COS
2
0.3
0.269
0.154
0.196
0.291
Max WP
DCH
8
8
1.0
0.141
0.174
0.156
0.304
LSE
4
0.3
0.409
0.196
0.265
0.310
DHN
1
0.3
0.027
0.004
0.008
0.046
COS
16
1
0.3
0.218
0.195
0.206
0.260
Max
DCH
4
2
3.0
0.259
0.198
0.225
0.250
LSE
8
2
0.3
0.295
0,250
0.271
0,230
DHN
12
1
0.3
0.027
0.004
0.008
0.046
COS
16
2
0.3
0.269
0.154
0.196
0.291
Max WP+F1
DCH
4
3.0
0.335
0.153
0.210
0.290
LSE
8
4
0.3
0.409
O. 196
0.265
0.310
DHN
12
0
0.03
0.109
0.088
0.098
0.241
COS
1
0.3
0.279
0.153
0.197
0.306
(Hard Negative 3) Max WP+F1
DCH
4
2
1.0
0.238
0.197
0.215
0.305
LSE
2
0.3
0.272
0.260
0.266
0.285
Table 6: Ablation Study of 20-Epoch Models on OSCAR Dataset (Hard Negative 3 formulation)
Ablated Paramater
Model
3
Tr. Prec.
Tr. Rec
Tr.
WP
DHN
12
0
0.03
0.109
0.089
0.098
0.241
COS
0
0.10
0.137
0.263
0.178
0.162
Hard Negative Weight
DCH
2
0
3.00
0.156
0.366
0.219
0,076
LSE
0
0.30
0.139
0.541
0.221
0.078
DHN
12
0.00
0
0.098
0.062
0.076
0.218
COS
0.25
0.156
0.086
0.111
0.264
Quantization Weight
DCH
4
4.00
0
0.224
0.075
0.112
0.267
LSE
12
8.00
0.163
0.091
0.117
0.275
DHN
0.0
0.03
0.004
0.001
0.001
0.107
COS
0.0
0.00
0.006
0.005
0.005
0.141
Concentration K
DCH
0.5
1.00
0.121
0.061
0.082
0.218
LSE
0.0
0.03
0.005
0.021
0.008
0.097
13

---

Under review as a conference paper at ICLR 2021
and WP when increasing the negative weight. All methods have comparable performance when the quantization loss is removed. And finally, DCH performs the best when K
A.2 PROOFS
Theorem 1. Let B(q)) N(8, qs 1 s) denote ball around q: with radius under the distance. For an arbitrary point 93 E B.).). we can consider the probability 93 and qi will collide under SimHash denote this with P())). Then,
1. (LSE) Pe (6) 8
2. (COS) Ps, (6) 2 2v8 (
3. (DCH) Ps. (0) 2 1
475
-
Proof. (I): (1, 9,) v by definition, so (v.(8) 2 1 6.
For each of the following, will use the expansion via the Frobenius method: cos-1(1 5) V28 + (6²).
(2): 1 se( qj) S 8. Substituting
5. [l ||
cos(m(1
(b( (;))) in se and rearranging gives
(note cos is monotonically decreasing on 1))
9 4j
1 - selgi. 93)
S
|
cos(TT1 [1(9, 2 1 - 28
2v8
- (ai 91) 5 π
cos (11 28)
+ 0(8+)
(3): 1 - 8h (gig 13) S Proceeding as above
1 - sg 93) =
S 6
d
of 4j
7 2
270
cos(T(1 +11 2 1
d(1 8)
- ((a 9j) 5 cos (1
278
478
2d1 - 5) +0
d(1 8)
Note that for the logistic based similarity, Ps. (6) is only well defined for a: > log(()) log(1 - 5) (otherwise So cannot be below 6.) Any analysis here requires choosing rate for a.
Lemma 1. Let b(g.) be the vector indicating signs of qu that is b(g:)m := [[ 0j. Denote the Hamming distance of the sign vectors as Pи (g:, 92) := [lb(q)) - -b(g))lla which defines a semimetric on Rdd. Take R as a uniformly random orthogonal matrix. Then
1 1 (/r 9,) BRIPH (Rq,, Rq;)].
(12)
Proof. Consider modified SimHash algorithm where z' is taken uniformly at random from the standard basis vectors {em { Ime and let h(gs) == [9 z' > 0) denote this hash. The collision probability is simply the chance that two given embeddings share the same sign for a randomly chosen dimension, so
Pr[h(g)) = h(q,)) = Em-(1 [1 = 4mmll = PH P06(9600 9j)
(13)
d
14

---

Under review as a conference paper at ICLR 2021
Let 20 Rd be vector with independent standard Normal entries, and take = which is equal in distribution to the uniform distribution on the unit sphere. Thus Rz' = 2. The original
SimHash function h(a:)) 1 luf 20 > 0] 1 > 0j. and so h(gs)) Rg.), and thus
(19. 9,) = Pr(h(q.) = h(g,)) ) = ER PH [Rq. Rg,))
(14)
d
A.3 EVALUATION METRICS
Precision Retrieve all items with the same hash, and compute precision
Recall Retrieve all items with the same hash, and compute recall
Compute Fl-measure using the above Precision and Recall
WP- Wu-Palmer similarity measure for evaluation of semantic quality of hash groups. Wu- Palmer similarity (Wu & Palmer (1994)) is computed on WordNet (WN) (Miller (1995); Fellbaum et al. (1998). We take all nouns, verbs and adjectives from the WordNet corpus and remove all words with no hypernyms (these typically isolated nodes in the WordNet graph for which WP values are not available.) The intersection with the 660K OSCAR vocabulary leaves 46K words, which we index based the semantic hashing models. For each query word w and its retrieved set V(w), the average WP similarity is computed across all pairs w, with v V(w). Self-pairs removed, and empty V(w) are given O values. This WP measure is bounded between 0 and 1, with higher values indicating more semantically meaningful clusters.
HR @n HitRatio score the heldout (test) 4600 pairs, where all colliding words for query are retrieved, and if the target word appears in the top items ranked by cosine sim- ilarity (of the dense embeddings.) the query achieves HR of 1. This is the only measure in the OSCAR experiment to use the dense embeddings.
Mean Average Precision (MAP) Consider rank position of each relevant retrieved item (in top R) based Hamming distance K₁, K2,... KR. First calculate precision @ by setting a rank threshold S R and then ratio of relevant in top divided by k (ignoring the ranked lower than k). Next step is calculate average of precision mean average precision is calculated by taking mean of average precision over all queries.
R. Finally
Recall@2 Retrieve everything within hamming distance and calculate recall
A.4 QUALITATIVE PLOTS AND TABLES
Table 7 shows example hash factors retrieved in the OSCAR model for set of queries. These constructed from exact hash collisions only - no search or ANN is performed in either the binary representation space or the dense embeddings space. Figures 5 and 7 show TSNE plots for the dense embeddings on the WordNet set. Figures Band9Sshow TSNE plots for the dense embeddings associated with the single hash that resembles "Generic Food" cluster. These figures demonstrate there is significant structure remaining in the dense version of the embeddings that is semantically meaningful.
15

---

Under review as a conference paper at ICLR 2021
Figure 5: TSNE on the LSE 100 Epoch model on WordNet
16

---

Under review as a conference paper at ICLR 2021
Iefrahymeen
attensated
cyloloain
Infect
malaria
pandemic
forsythia
vitrio
encephalltss
measles
rables
nubella
syphillo
toxin
voocine
dysentery
mumps
tetrahymena
decryoooedits a
candida
inoculum
mizobium
streptomyces
brome
out
bell
gingee
pon
pomtage
brome
Tendar
top
bost Pca
Trentraeos
copomicia
invigorading
spearmint
decostion
curd
pioce
1a5de
Figure 6: TSNE clusters from the WordNet set
17

---

Under review as a conference paper at ICLR 2021
Filtate
saturated
formaldehydo
peroxde
rauthallad
paratte
nuorin
magnesium
imiiazole
thiocyanate
molerity
Highn
oxide
botassium
ammonium
compound
hydride
polyelectroytee
suffile
diuue
permanganate
adentt
chelicess
exudation
sclertts
mageosion
spondyllts
syphillic
thombose
arthropathy
glosslts
astonish
chorloretintts
indoccyclii
papilloma
tubercular
pleurey
metrila
quiney
eclemppia
slightnes
adenitis
Figure 7: TSNE clusters from the WordNet set
18

---

Under review as a conference paper at ICLR 2021
ajwain
arare
dhania
gourd
Jeera
kadai
kofle
methi
momos
pancer
poshwari
pulav
ratta
$440
aaare
ajwaiin
semosas
seeth
tawa
Nbachi
nigiri
otoro
shabu
shiso
talyaki
tobiko
togarashi
wagyu
wasabl
yuzu
allspice
hibachi
bento
faiyaki
dumpling
glutioous
gyoza
masago
Figure 8: TSNE subclusters from the "Generic Food" Cluster
19

---

Under review as a conference paper at ICLR 2021
cereal
daiy
legumes
papitas
sprouted
sugars
wholegrain
cakes
chia
dipped
dried
cereal
fats
flours
gluten
milk
nuts
oats
wholewheat
apple
spricot
cranberry
flavors
juicy
pudding
respberry
rich
soft
vanilla
banana
blueberry
chocolate
compote
apple
flavoured
fruit
jam
orange
passionfrutt
Figure 9: TSNE subclusters from the "Generic Food" Cluster
20

---

Under review as a conference paper at ICLR 2021
Query
Cluster Siblings
Cluster Size
Author Annotations
succulent
stonecrop, sedums, crassula, sempervivum.
10
Succulent Plants
succulent
succulent
battered, tossing, tenderized, spareribs, sax2, lalr, fixpoint, xerces, gson, ...
Enticing Food Terms
parser
22
Parser Instances
parser
fasthoot, lwo, eml, compute, osgi,.. ...
732
Generic Technology
parser
tokenizer, javace, tokenizes, jtb, lexer amidship, starboard, portside cockpit, coaming coatroom, garran, carrels, stowage, locker, basil, honey, vinegary, ribeye, grilling,
Java Tree Builder
lazarette
Ship Locations
lazarette
Ship Components
lazarette
12
Storage
vegan
1134
Generic Food
vegan
vegatarian
2
Portmanteau
vegan
veganism, eleaneating, vegano, plantpower, seleractinia, pertusa, pistillata, acropora, hystrix, ycllow, root, crocheted, soles, linen,
28
Vegan Terms
coral
14
Coral Species
coral
1208
Generic Fashion
coral
bronchitis
eyedrops, fever, myalgia, sinusitis, fasciculations...
187
Generic Health
bronchitis
bronchitis
pneumonia
Respiratory Infections
split
split
subsections, empirical, broader, alexa, cafes, ubli, imotski, zlatni, milna, dalmatia,
5455
Generic English
split
55
Croatian Locations
Table 7: Example Retrieved Hash Clusters
21


Reviews:
[{"review_id": "vMvqFO74ypT", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 consider the problem of learning a hash function such that semantically similar elements have high collision probability.  They modify the approach Deep Hashing Networks (Zhu et al., 2016) with a new loss function. Rather than use a sigmoid based loss function, the authors argue that a loss function based on angular similarity and SimHash would be better. Specifically, they use the probability of SimHash collisions as a loss function. They then experimentally verify their method on synthetic data from a Stochastic Block Model distribution, image data (CIFAR-10 and ImageNet), and text data (OSCAR). They show improvements over related methods.\n\nOverall, I found this paper to be incremental compared to previous work, such as (Zhu et al., 2016). The theoretical contributions are fairly weak. Why is the relation to SimHash useful? The authors need to better justify their choice of loss function. Additionally, how does the method compare to using a sigmoid loss but changing the temperature parameter so that the loss function doesn't saturate as quickly?\n\nThe authors do improve over related methods in the experiments. However it is not clear if this is due to the choice of loss function or the use of negative mining. The authors should also improve the clarity of how their metrics are defined. Is precision, recall simply based on the elements that collide together?\n\nTo summarize, I think this paper needs to better justify their use of loss function in theory and also perform ablation tests in the experiments before it can be accepted.", "extra_scores": {}, "extra_text": {}}, {"review_id": "tvQA_5UB8v6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "+++Pros.  \n-----The idea learning embeddings via angular similarity is interesting and important for exact hashing retrievals; and the design of experiments on different domains to validate the proposed method is worth encouraging.\n\n+++Cons.  \n-----This paper just devised the angular similarity, whose contribution is limited for ICLR.  \n-----There are some technical minors or typos, such as the binary cross entropy loss in Eq.~(5) (should be “+\\beta(1-y_{ij})log(……)”).  \n-----There are several grammar minors, such as “…utilizes cosine similarity to as the crossing layer between the two halves…” in the beginning of Section 3, “We measure precision, recall and F1-score on with the data generating factions as the target.” in Section 4.1 above Table 2; and some confusing expressions, such as “in Table 4.1.” (there is no Table 4.1.).  \n-----Better replace beta with \\beta, lambda with \\lambda, and keep them identical in texts and figures. And better organize figures with subtitles.  \n-----At the end of each equation marked (1), …, (10), there should be appropriate punctuations, such as commas.  \n-----The authors concluded that “The learned representations show superior performance in the exact hashing retrieval setting”. But the results in Table 2 does not support it.  \n-----Besides, the authors mentioned that … a “word2hashes” model which is novel to the best of the authors’ knowledge …, and I do not agree with such statements.  \n-----Actually, I think Figures 4-8 and Table 5 should be regarded as the main texts; and if so, this paper exceeds the page limit.  \n\n+++Conclusions.  \n-----Based on the above pros and cons, I think this paper is interesting, but the contribution is limited; thus, I would make a REJECT recommendation.  \n\n+++Suggestions.  \n-----Need careful writing and presentation.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "f-OHYZXPKO4", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "########\nPros\n########\n\n- The paper is well written and easy to read\n\n- The authors have explained the background, motivation and prior work quite comprehensively\n\n- The idea of learning embeddings such that nearest neighbors have the same hash is interesting. \nBecause of this property, nearest neighbor search becomes a simple hash lookup. \n\n\n\n########\nCons\n########\n\n- The authors claim, \"We extend semantic hashing methods to problems with **substantial label noise**\", but there doesn't appear to be any specific modeling to handle label noise in Section 3.\n\n- In practice, for IR, can this method support a ranking of the items based on query similarity? For example, if for query q, documents A, B, C are relevant in that order (most relevant to least). It appears that this method would all assign the same hash to A, B, C and therefore, retrieve them, but not in any particular order?\n\n- Experiments don't appear to be necessarily a fair comparison that can show the merits of this approach conclusively.\n\n\n########################\nComments / queries\n########################\n\nQ1 Section 4.1,  Table 1 shows very low numbers for DHN. Is that a typo, given that DHN performs quite well in all the other experiments. \n\nQ2. Section 4.1, Table 1: Can you also provide the numbers for LSE without false negatives for fair comparison with the baselines?\n\nQ3. Section 4.2, Table 2: It appears that LSE is able to perform well and beats the baselines in many cases. Can you provide the statistical significance p values?\n\nQ4. Section 4.3, Table 3: LSE has a substantially lesser number of clusters, making it difficult to isolate the merits of the method vs. outcome that is a result of just lesser clusters. E.g. Recall can be better just by returning a larger cluster, which is probably the case if the number of clusters are lesser. Can you provide a fairer comparison, for example, by lowering the number of clusters of the other methods or some other way?\n\n\n########\nTypos\n########\n\nSection 4.2: \"100 images per category it test query set\"\n\nSection 4.2: \"Results are shown in Table 4.1.\" --> Table 2?\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your submission to ICLR.

This paper presents an extension to Deep Hashing Networks that utilizes angular similarity, and show improved results using the proposed method.  The reviewers were somewhat mixed on this paper, with two of three reviewers on the negative side.  Some reviewers appreciated that the paper was easy to follow and well written, though one reviewer felt that the paper's writing and presentation could improve.  A big concern about the paper expressed by multiple reviewers was that the paper was incremental, in that the main architectural difference seemed to be a change in loss function over existing work.  Unfortunately, the reviewers were fairly unresponsive to attempts to get them to respond to the rebuttals offered by the authors.  

Ultimately, I took a look at the paper and found it to be borderline.  I do think the contribution is a bit limited, particularly as it is in an area which has seen many papers over the years (and thus has a high bar for new work).  However, with some additional work this paper could definitely be acceptable.  I think it could use an additional round of editing and review, and I'd encourage the authors to submit this paper to another venue.
Decision: Reject