Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> This paper considers various flavors of the following online problem: preprocess a text or collection of strings, so that given a query string p, all matches of p with the text can be reported quickly. In this paper we consider matches in which a bounded number of mismatches are allowed, or in which a bounded number of "don't care" characters are allowed. The specific problems we look at are: indexing, in which there is a single text t, and we seek locations where p matches a substring of t; dictionary queries, in which a collection of strings is given upfront, and we seek those strings which match p in their entirety; and dictionary matching, in which a collection of strings is given upfront, and we seek those substrings of a (long) p which match an original string in its entirety. These are all instances of an all-to-all matching problem, for which we provide a single solution.The performance bounds all have a similar character. For example, for the indexing problem with n=|t| and m=|p|, the query time for k substitutions is O(m + (c 1 log n)k⁄k! + # matches), with a data structure of size O(n (c 2 log n)k⁄k!) and a preprocessing time of O(n (c 2 log n)k⁄k!), where c 1 ,c 2 > 1 are constants. The deterministic preprocessing assumes a weakly nonuniform RAM model; this assumption is not needed if randomization is used in the preprocessing. <s> BIB001 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> A common problem encountered in disciplines such as statistics, data analysis, signal processing, textual data representation, and neural network research, is finding a suitable representation of the data in the lower dimension space. One of the principles used for this reason is a factor analysis. In this paper, we show that Hebbian learning and a Hopfield-like neural network could be used for a natural procedure for Boolean factor analysis. To ensure efficient Boolean factor analysis, we propose our original modification not only of Hopfield network architecture but also its dynamics as well. In this paper, we describe neural network implementation of the Boolean factor analysis method. We show the advantages of our Hopfield-like network modification step by step on artificially generated data. At the end, we show the efficiency of the method on artificial data containing a known list of factors. Our approach has the advantage of being able to analyze very large data sets while preserving the nature of the data <s> BIB002 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> The objective of this paper is to introduce a neural-network-based algorithm for word clustering as an extension of the neural-network-based Boolean factor analysis algorithm (Frolov , 2007). It is shown that this extended algorithm supports even the more complex model of signals that are supposed to be related to textual documents. It is hypothesized that every topic in textual data is characterized by a set of words which coherently appear in documents dedicated to a given topic. The appearance of each word in a document is coded by the activity of a particular neuron. In accordance with the Hebbian learning rule implemented in the network, sets of coherently appearing words (treated as factors) create tightly connected groups of neurons, hence, revealing them as attractors of the network dynamics. The found factors are eliminated from the network memory by the Hebbian unlearning rule facilitating the search of other factors. Topics related to the found sets of words can be identified based on the words' semantics. To make the method complete, a special technique based on a Bayesian procedure has been developed for the following purposes: first, to provide a complete description of factors in terms of component probability, and second, to enhance the accuracy of classification of signals to determine whether it contains the factor. Since it is assumed that every word may possibly contribute to several topics, the proposed method might be related to the method of fuzzy clustering. In this paper, we show that the results of Boolean factor analysis and fuzzy clustering are not contradictory, but complementary. To demonstrate the capabilities of this attempt, the method is applied to two types of textual data on neural networks in two different languages. The obtained topics and corresponding words are at a good level of agreement despite the fact that identical topics in Russian and English conferences contain different sets of keywords. <s> BIB003 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> There is growing interest in representing image data and feature descriptors using compact binary codes for fast near neighbor search. Although binary codes are motivated by their use as direct indices (addresses) into a hash table, codes longer than 32 bits are not being used as such, as it was thought to be ineffective. We introduce a rigorous way to build multiple hash tables on binary code substrings that enables exact k-nearest neighbor search in Hamming space. The approach is storage efficient and straight-forward to implement. Theoretical analysis shows that the algorithm exhibits sub-linear run-time behavior for uniformly distributed codes. Empirical results show dramatic speedups over a linear scan baseline for datasets of up to one billion codes of 64, 128, or 256 bits. <s> BIB004 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> MinHash and SimHash are the two widely adopted Locality Sensitive Hashing (LSH) algorithms for large-scale data processing applications. Deciding which LSH to use for a particular problem at hand is an important question, which has no clear answer in the existing literature. In this study, we provide a theoretical answer (validated by experiments) that MinHash virtually always outperforms SimHash when the data are binary, as common in practice such as search. The collision probability of MinHash is a function of resemblance similarity (R), while the collision probability of SimHash is a function of cosine similarity (S). To provide a common basis for comparison, we evaluate retrieval results in terms of S for both MinHash and SimHash. This evaluation is valid as we can prove that MinHash is a valid LSH with respect to S, by using a general inequality S 2 <s> BIB005 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> To solve the approximate nearest neighbor search problem (NNS) on the sphere, we propose a method using locality-sensitive filters (LSF), with the property that nearby vectors have a higher probability of surviving the same filter than vectors which are far apart. We instantiate the filters using spherical caps of height 1 -- α, where a vector survives a filter if it is contained in the corresponding spherical cap, and where ideally each filter has an independent, uniformly random direction. For small α, these filters are very similar to the spherical locality-sensitive hash (LSH) family previously studied by Andoni et al. For larger α bounded away from 0, these filters potentially achieve a superior performance, provided we have access to an efficient oracle for finding relevant filters. Whereas existing LSH schemes are limited by a performance parameter of ρ ≥ 1/(2c2 -- 1) to solve approximate NNS with approximation factor c, with spherical LSF we potentially achieve smaller asymptotic values of ρ, depending on the density of the data set. For sparse data sets where the dimension is super-logarithmic in the size of the data set, we asymptotically obtain ρ = 1/(2c2 -- 1), while for a logarithmic dimensionality with density constant κ we obtain asymptotics of ρ ~ 1/(4κc2). To instantiate the filters and prove the existence of an efficient decoding oracle, we replace the independent filters by filters taken from certain structured random product codes. We show that the additional structure in these concatenation codes allows us to decode efficiently using techniques similar to lattice enumeration, and we can find the relevant filters with low overhead, while at the same time not significantly changing the collision probabilities of the filters. We finally apply spherical LSF to sieving algorithms for solving the shortest vector problem (SVP) on lattices, and show that this leads to a heuristic time complexity for solving SVP in dimension n of (3/2)n/2+o(n) a 20.292n+o(n). This asymptotically improves upon the previous best algorithms for solving SVP which use spherical LSH and cross-polytope LSH and run in time 20.298n+o(n). Experiments with the GaussSieve validate the claimed speedup and show that this method may be practical as well, as the polynomial overhead is small. <s> BIB006 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> A model of associative memory is studied, which stores and reliably retrieves many more patterns than the number of neurons in the network. We propose a simple duality between this dense associative memory and neural networks commonly used in deep learning. On the associative memory side of this duality, a family of models that smoothly interpolates between two limiting cases can be constructed. One limit is referred to as the feature-matching mode of pattern recognition, and the other one as the prototype regime. On the deep learning side of the duality, this family corresponds to feedforward neural networks with one hidden layer and various activation functions, which transmit the activities of the visible neurons to the hidden layer. This family of activation functions includes logistics, rectified linear units, and rectified polynomials of higher degrees. The proposed duality makes it possible to apply energy-based intuition from associative memory to analyze computational properties of neural networks with unusual activation functions - the higher rectified polynomials which until now have not been used in deep learning. The utility of the dense memories is illustrated for two test cases: the logical gate XOR and the recognition of handwritten digits from the MNIST data set. <s> BIB007 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> [See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the $c$-Approximate Near Neighbor Search problem. For the $d$-dimensional Euclidean space and $n$-point datasets, we develop a data structure with space $n^{1 + \rho_u + o(1)} + O(dn)$ and query time $n^{\rho_q + o(1)} + d n^{o(1)}$ for every $\rho_u, \rho_q \geq 0$ such that: \begin{equation} c^2 \sqrt{\rho_q} + (c^2 - 1) \sqrt{\rho_u} = \sqrt{2c^2 - 1}. \end{equation} This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor $c>1$, improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for $\rho_q = 0$, improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes. <s> BIB008 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> Deep neural networks (DNNs) trained in a supervised way suffer from two known problems. First, the minima of the objective function used in learning correspond to data points (also known as rubbish... <s> BIB009 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> We show that approximate similarity (near neighbour) search can be solved in high dimensions with performance matching state of the art (data independent) Locality Sensitive Hashing, but with a guarantee of no false negatives. Specifically we give two data structures for common problems. For $c$-approximate near neighbour in Hamming space we get query time $dn^{1/c+o(1)}$ and space $dn^{1+1/c+o(1)}$ matching that of [Indyk and Motwani, 1998] and answering a long standing open question from [Indyk, 2000a] and [Pagh, 2016] in the affirmative. For $(s_1,s_2)$-approximate Jaccard similarity we get query time $d^2n^{\rho+o(1)}$ and space $d^2n^{1+\rho+o(1)}$, $\rho=\log\frac{1+s_1}{2s_1}\big/\log\frac{1+s_2}{2s_2}$, when sets have equal size, matching the performance of [Pagh and Christiani, 2017]. The algorithms are based on space partitions, as with classic LSH, but we construct these using a combination of brute force, tensoring and splitter functions \`a la [Naor et al., 1995]. We also show two dimensionality reduction lemmas with 1-sided error. <s> BIB010 </s> Neural Distributed Autoassociative Memories: A Survey <s> DISCUSSION <s> We present an improved data structure for approximate similarity (or"nearest neighbor") search under Braun-Blanquet similarity. For $\mathbf{x}, \mathbf{y} \subseteq \{1, \dots, d\}$, Braun-Blanquet similarity is defined as $B(\mathbf{x}, \mathbf{y}) = |\mathbf{x} \cap \mathbf{y}| / \max(|\mathbf{x}|, |\mathbf{y}|)$. Given a collection $P$ of sets, $(b_1,b_2)$-approximate Braun-Blanquet similarity search asks to preprocess $P$ such that given a query set $\mathbf{q}$ for which there exists $\mathbf{x} \in P$ with $B(\mathbf{q},\mathbf{x}) \geq b_1$, we can efficiently return $\mathbf{x}' \in P$ with $B(\mathbf{q},\mathbf{x}')>b_2$. Historically a different measure, the Jaccard similarity $J(\mathbf{x},\mathbf{y}) = |\mathbf{x} \cap \mathbf{y}|/|\mathbf{x} \cup \mathbf{y}|$, has been more widely studied. We argue that it suffices to study regular data structures in which the size of the query set $\mathbf{q}$ and the sizes of sets in $P$ are fixed. In this setting there is a 1-1 mapping between Jaccard similarity and Braun-Blanquet similarity, so the problems are equivalent. It follows from the seminal paper of Indyk and Motwani (STOC 1998) that the so-called MinHash locality-sensitive hash function can be used to construct a data structure for $(j_1,j_2)$-approximate Jaccard similarity with space $O(n^{1+\rho} + dn)$ and query time $O(dn^\rho)$, where $n = |P|$ and $\rho = \log(1/j_1)/ \log(1/j_2)<1$. In the regular setting our data structure improves $\rho$ in the exponent to $\rho' = \log\left(\tfrac{1 + j_1}{2j_1}\right)/\log\left(\tfrac{1+j_2}{2j_2}\right)$ which is always strictly smaller than $\rho$. The exponent in terms of Braun-Blanquet similarity is $\rho'=\log(1/b_1)/ \log(1/b_2)$. Our main technical idea (continued...) <s> BIB011
In addition to being an interesting model of biological memory, neural network autoassociative distributed memories (NAMs) have also been considered as index structures that give promise to speed up nearest neighbor search relative to linear search (and, hopefully, to some other index structures). This mainly concerns sparse binary vectors of high dimension, because the number of such vectors that it is possible to memorize and retrieve from a significantly distorted version may far exceed the dimensionality of the vectors in some matrix-type NAMs, and the ratio / ND may be similar to the speed-up relative to linear search (see the first four Sections). Distributed NAMs have some drawbacks relative to traditional computer science methods for nearest neighbor search. The vector retrieved by a NAM may not be the nearest neighbor of the query vector. This could be tolerable if the output vector is an approximate nearest neighbor from the set of stored vectors. However, in NAMs the output vector may not even be a vector of the base set ("spurious memories"). (Up to a certain number of stored vectors and query vector distortion these problems remain insignificant.) For dense binary vectors, the number of vectors able to be reliably stored and retrieved is (much) smaller than the vector dimension. Also, NAMs are usually analyzed for the average case of random vectors and distortions, whereas real data are not like that, which results in poorer performance. However, available comparisons with the inverted index for sparse binary vectors in the average case do not clearly show the advantage of one or other algorithm in query time (Subsections "Hopfield networks with sparse vectors", "Willshaw networks with sparse vectors") An obvious approach to improve the memory and time complexity of the matrix-type NAMs from quadratic to linear in vector dimension is the use of incompletely connected networks with constant (but rather large) number of connections per neuron. An interesting direction is index structures for similarity search in which NAM modules are used at some stages. The index structure of Subsection "Willshaw networks in the index structures for nearest neighbor search" uses several NAMs to memorize parts of the base, and the similarity of the result of single-step retrieval with the query vector is used to select the "best" NAM on which to perform an exact linear search against its stored vectors. Some studies are aimed at more efficient use of NAMs when working with real data. For example, the GB network with binary connections uses different neurons to represent the same component of the source vector, which allows for more balanced use of connections. In Section "Generalization in NAMs" we discussed the use of NAMs for generalization rather than exact retrieval from associative memory. In the NAMs that use versions of the Hebb learning rule, storage of vectors (even random ones) is accompanied by emergence of additional stable states. For correlated vectors, their common 1-components become "tightly" connected and stable states corresponding to them arise. Revealing these stable states can be used for data mining, e.g. for binary factor analysis BIB002 BIB003 . Research of complex (possibly hierarchical) structure of stable states (discussed in terms of cores and fringes of neural assemblies) may appear useful both for modeling brain function and for applications. Real data in many cases are not binary sparse vectors of high dimension with which the NAMs considered in the first four Sections work best. So, similarity preserving transformations to that format are required (Subsection "Similarity preserving binary vectors"). However, the obtained vectors (as well as the initial real data) are not random and independent, so the analytical and experimental results available for random, independent vectors usually can not predict NAM characteristics for real data. Using data vectors (often non-binary) that satisfy some linear constraints (instead of random independent vectors) allows bipartite graph based NAM construction with capacity near exponential in the vector dimension (Section "NAMs with a Bipartite Graph Structure for Nonbinary Data with Constraints"). However, again, this requires data from specific vector models (to which real data often do not fit). In NAMs with higher-order connections, connections are not between a pair, but between a larger number of neurons (this number being the order). So, the NAM becomes of tensor-type instead of matrix-type. These NAMs (Section "NAMs with Higher-Order Connections and without Connections") allow storing the number of dense vectors exponential in the order. However, this is achieved by the corresponding increase in the number of connections, and therefore in memory and in query time. The higher-order NAMs are generalized in BIB007 BIB009 , where, roughly, the sum of polynomial functions of the dot products between all memory vectors and the network state is used as the input sum of a neuron. Such a treatment makes it possible to draw interesting analogies with perceptrons and kernel methods in the classification problem. However, for nearest neighbor search, this seems impose a query time exceeding that of linear search. Overcoming these and other drawbacks and knowledge gaps, and improving NAMs are promising topics for further research. Let's note other directions of research in fast similarity search of binary (non-sparse) vectors. Examples of index structures for exact search are BIB001 (with a fixed query radius and analysis for worst-case data; however impractical due to the small query radius required for sub-linear query time and moderate memory costs) and BIB004 (practical, with variable radius of the query and analysis for random data). Theoretical algorithms for approximate search (providing: sublinear search time, a specified maximum difference of the result from the result of the exact search, and no false negatives) in BIB010 are modifications of more practical algorithm classes related to Locality Sensitive Hashing and Locality Sensitive Filtering (see BIB006 BIB008 BIB005 ). However, the latter allow false negatives (with low probability). Unlike NAMs, these algorithms provide guarantees for the worstcase data, but require a separate index structure for each degree of distortion of the query vector. The bounds on the ratio of binomial coefficients BIB010 is useful for NAMs. We note that the index structures for the Hamming distance BIB001 BIB004 work with vectors of moderate dimension (up to hundreds), and for binary sparse high dimensional vectors Jaccard similarity index structures are used BIB005 BIB010 BIB011  . A survey of these and other similar index structures is presented in the forthcoming  , see also  for another type of index structures. модифікації значень ваг міжнейронних зв'язків, які існують між всіма нейронами (пов-нозв'язні мережі). У розподіленій пам'яті різні вектори запам'ятовуються в одних і тих самих елементах пам'яті, яким в цьому випадку нейронної мережі відповідають одні і ті ж зв'язки. Зазвичай досліджують запам'ятовування векторів, випадково вибраних з деякого розподілу. Якщо на вхід автоасоціативної пам'яті подаються спотворені варіанти за-пам'ятованих в ній векторів, здійснюється витяг (відновлення) найближчого раніше запам'ятованого вектора. Це реалізується за рахунок ітераційної динаміки нейронної мережі на основі локально доступної в нейронах інформації, отриманої від інших нейронів мережі. До певної кількості запам'ятованих в мережі векторів і ступеня їх спотворення на вході, в результаті динаміки мережа із симетричними зв'язками прихо-дить в стійкий стан, відповідний запам'ятованому в мережі вектору, який має найбільшу схожість з вхідним вектором (схожість зазвичай вимірюють як скалярний добуток). Такі нейромережні варіанти автоасоціативної пам'яті дозволяють запам'ятати з можливістю відновлення таку кількість векторів, яка може перевищувати розмірність векторів ( що збігається з кількістю нейронів в мережі). Для векторів великої розмірності це відкриває можливість пошуку наближеного найближчого сусіда з складністю, сублінейною від кількості запам'ятованих в нейронній мережі векторів. До недоліків такої пам'яті відноситься те, що відновлений динамікою мережі вектор може не бути найближчим до вхідного або навіть може взагалі не належати до множини запам'ятованих векторів і значно відрізнятися від будь-якого з них. Дослідження різних типів нейромережної автоасоціативної пам'яті спрямовано на виявлення діапазонів параметрів, при яких зазначені недоліки проявляються з малою імовірністю, а достоїнства виражені в максимальному ступені. Основну увагу приділено мережам з парними зв'язками типу Hopfield, Willshaw, Potts і роботі з бінарними розрідженими векторами (векторами з кількістю одиничних компонентів, яке є малим у порівнянні з кількістю їх нульових компонентів), так як тільки для таких векторів вдається запам'ятати з можливістю відновлення велику кількість векторів. Крім функції автоасоціативної пам'яті, для цих мереж також обговорюється функція узагальнення. Обговорюються також неповнозв'язкові мережі. Крім того, розглянуто автоасоціативну пам'ять в нейронних мережах зі зв'язками ви-щого порядку -тобто зі зв'язками не між парами, а між великою кількістю нейронів. Розглянуто також автоасоціативна пам'ять в нейронних мережах зі структурою двудольного графа, де одна множина нейронів надає вектори, які запам'ятовуються, а інша -лінійні обмеження, яким вони підкорюються. Ці мережі виконують функцію автоасоціативної пам'яті також для небінарних даних, які відповідають заданій моделі обмежень. Обговорюються можливості використання розглянутих в огляді моделей нейромережної автоасоціативної розподіленої пам'яті у проблематиці пошуку за схожістю, достоїнства і недоліки розглянутих методів, напрямки подальших досліджень. Один із цікавих і все ще не повністю вирішених питань полягає в тому, чи може нейронна автоасоціативна пам'ять шукати наближених найближчих сусідів швидше інших індексних структур для пошуку за схожістю, зокрема, у випадку векторів дуже великих розмірностей. 