Dense associative memories learn complex patterns from few examples
Sample-efficient learning with Dense Associative Memories
Machine Learning
Summary
Learning to recognize complex patterns often requires a lot of examples, but this paper shows a method where a special kind of memory model can learn the hidden rules behind many patterns by seeing only a few. The model works by discovering the simple rules that generate all examples after training on a relatively small number of samples. The authors also introduce a new learning rule that makes this learning much more efficient, allowing the system to uncover even hidden parts of the data it never directly saw. This helps explain how complex 'understanding' might arise in artificial memory systems.
What this means in practice
- •For machine learning engineers: Train associative memory models efficiently with minimal data by exploiting sparse structure in complex pattern sets.
- •For coding theory developers: Recover underlying code rules and latent variables of error-correcting codes using a novel energy-based learning approach.
Authors
Andrew Lucas, Dmitry Krotov
Abstract
We analytically study the evolution of the energy function of Dense Associative Memories (DenseAMs) as they train on randomly sampled codewords of random expander low-density parity-check codes (a.k.a. solutions of random XORSAT problems). We identify two distinct regimes and a transition between them, reminiscent of grokking in neural networks. A regime of small training set size is where the model memorizes a few training examples but cannot discover the underlying rules of the entire codeword dictionary generative process. The opposite regime, corresponding to a larger training set size, is where the model has uncovered the sparse constraints that generated the entire data set after seeing only polynomially many patterns. We also design a novel class of DenseAMs with a thresholding learning rule, and show that any amount of thresholding enables the model to perform simplified sparse Hamiltonian learning, which exponentially reduces the number of training examples needed to learn the true underlying data set. In this regime, the model learns how to discover $\exp[\mathrm{O}(n)]$ solutions from only $\mathrm{O}(\log n)$ training samples, which is asymptotically optimal for any learning algorithm. When training on codewords of certain random codes, the model can even learn the underlying code when a small O(1) fraction of bits are latent variables. These latent variables are not shown to the model during learning, but will be discovered by sparsifying observed higher-order correlations. For certain random codes, we show that a simple and conservative algorithm learns a minimal latent representation for the data set. This provides a transparent, physics-motivated, and analytically tractable toy model for how deep latent representations emerge in an associative memory training.