G4 Neural Codes and Neural Rings: Topology and Algebraic Geometry
This lecture asks what the firing patterns of a population of neurons can tell us about the space of stimuli they respond to. The first half uses topology (simplicial complexes, nerves, homology) and algebraic geometry (the neural ring and the neural ideal of a code), following Curto–Itskov–Veliz-Cuba–Youngs, Youngs, Curto–Youngs, Gross–Obatake–Youngs and Manin. The second half asks how good neural codes are as error-correcting codes, and describes the Chaudhuri–Fiete mechanism that uses Hopfield networks on expander graphs to pass from poor codes to good ones. The works cited are collected in the References at the end.
Neural codes
Codes and supports
Fix a set of neurons
This neglects information about the timing and rate of neural activity: we focus on the combinatorial neural code, which records only which neurons are active together.
The simplicial complex of a code
Definition G4.1 (Simplicial complex of a code). A subset
In a picture, the simplices of a complex are glued to one another along common faces, as on the left. On the right, two triangles cross in a region that is not a face of either, so the picture is not a simplicial complex.
Receptive fields
Codewords come from patterns of neuron activity. Let
In panel A the stimulus space is a line and five neurons have bump-shaped tuning curves; a stimulus in the shaded interval lies in the receptive fields of neurons 1, 2 and 3 and no others, so its activity pattern is the codeword
The receptive field code
Definition G4.2 (Receptive field code). Let
If
Reconstructing the stimulus space
The main question: if we know the code
Step one: every code is a receptive field code
Proposition G4.3. Let
Proof. List the codewords
Caveat: convexity is a real restriction
We can always find
Example G4.4. The code
Suppose it could:
, because ; , because ; , because .
Take points
- If
passes through , then ; but , a contradiction. - Otherwise
does not meet , and then meets the complement of (the segment is connected, runs from to , and , are open). A point of there lies in alone, which would imply , again a contradiction.
Topological constraints on the stimulus space
Codes
- constraints from the simplicial complex
; - other constraints from
that are not captured by .
The nerve of an open covering
Definition G4.5 (Simplicial nerve). Let
The nerve is the simplicial complex of the receptive field code:
In this example of convex open sets
The complex
Helly’s theorem
Theorem G4.6 (Helly’s theorem). Let
The
Corollary G4.7. For convex open sets
The nerve theorem
Theorem G4.8 (Nerve theorem). (Hatcher, Algebraic Topology, Corollary 4G.3.) For a collection
As a consequence,
Note. The space
Homology groups
Homology groups are very useful topological invariants, and they are computationally tractable.
Definition G4.9 (Homology groups). Let
On an oriented edge, triangle and tetrahedron the boundary maps are
The chain complex and its homology can be pictured as below. Inside each
What else does the code tell us about the stimulus space?
The simplicial complex does not see everything. The following figure, from Curto–Itskov–Veliz-Cuba–Youngs (their Figure 3), shows four arrangements of three convex receptive fields
- (A)
, including the all-zeros codeword . - (B)
, with . - (C)
. - (D)
, and .
The minimal embedding dimension (defined below) for the codes in panels A and D is
Embedding dimension
Definition G4.10 (Embedding dimension). The minimal embedding dimension of a code
The topological dimension of a space is the minimum
In this covering of a square by discs, some points lie in three of the discs (and none in more), others in two.
In the previous examples
Nontrivial inclusions
The main information carried by the code
- Some inclusion relations between intersections and unions are always trivially satisfied: for example
, because . - Other inclusion relations are specific to the structure of the collection
of open sets, and are not automatically satisfied: this is the information encoded in .
It consists of all relations of the form
Algebraic geometry of neural codes
Problem: how can we extract this information from
Rings and ideals
Definition G4.11 (Ideals). Let
- A prime ideal is an ideal
such that if then or . - A maximal ideal is an ideal
such that if is an ideal with , then either or . (Geometrically, maximal ideals correspond to points.) - A radical ideal is an ideal
such that implies , for all .
A radical ideal
Affine algebraic varieties
Definition G4.12 (Varieties and spectrum). Let
Ideals
To model
The neural ring
Definition G4.13 (Neural ring). Given a binary code
Note. We are working over
The spectrum of the neural ring
The points
Proposition G4.14. For the neural ring
So the spectrum of the neural ring recovers the codewords of
The neural ideal
In general it is difficult to give explicit generators for the ideal
Definition G4.15 (Neural ideal). Given
The ideal of Boolean relations is
Proposition G4.16. The ideals
Neural ring relations
Notation: given open sets
Inclusions give relations. If
Pseudomonomials and canonical form
Consider such a relation
Definition G4.17 (Pseudomonomials and canonical form). A function of the form
The neural ideal
The canonical form of the neural ideal
A subset
Theorem G4.18 (Canonical form of the neural ideal). Let
, with minimal for ; , with , , , and minimal for ; , with minimal for .
The Type 1 relations bound the minimal embedding dimension:
There are efficient algorithms to compute
Example G4.19 (Canonical forms for the four arrangements). For the four arrangements of three receptive fields shown earlier (Curto–Itskov–Veliz-Cuba–Youngs, Figure 3):
A.
B.
C.
D.
How good are neural codes as codes?
The rest of the lecture looks at neural codes from the point of view of coding theory:
- how one evaluates the properties of codes in coding theory;
- codes and code parameters, bounds;
- neural codes as error-correcting codes;
- neural mechanisms passing from bad to good codes (Chaudhuri–Fiete);
- expander graphs and codes;
- Hopfield equations and hyperplane arrangements;
- Hopfield networks;
- expander codes and Hopfield networks.
When is a code a good code?
Error-correcting codes can be viewed as an optimization problem:
- optimize encoding: more choice of code words makes for better encoding;
- optimize decoding: sparse code words make for better decoding (better error correction: only one true code word near a corrupted one).
Take the alphabet
Definition G4.20 (Code parameters). Let
, the transmission rate of the code; , the relative minimum distance of the code.
Small
Bounds in the space of code parameters
Each code gives a code point
- Singleton bound:
. (For a code of length the exact inequality is , that is , which becomes as .) - Typical random codes (the Shannon Random Code Ensemble, SRCE: code words and letters generated uniformly and randomly as i.i.d. random variables) tend to accumulate in the region below the Gilbert–Varshamov curve.
The Gilbert–Varshamov curve is
The curve comes from the asymptotic behavior of volumes of balls in the Hamming distance as the code length
The asymptotic bound
There is another curve in the space of code parameters: the asymptotic bound
There is no explicit expression for the asymptotic bound
Proposition G4.21 (Known estimates on the asymptotic bound). Plotkin bound:
Hamming bound:
Unlike the Gilbert–Varshamov bound and random codes, the asymptotic bound has no statistical description.
Characterization of the asymptotic bound. The curve
Definition G4.22 (Good codes). Good codes are codes near or above the asymptotic bound.
The main source of good codes is algebro-geometric codes, built from algebraic curves over finite fields (Tsfasman–Vladut–Zink, “Modular curves, Shimura curves, and Goppa codes, better than Varshamov–Gilbert bound”). Another, unexpected, source of codes above the asymptotic bound is linguistics (Shu–Marcolli, “Syntactic structures and code parameters”; Marcolli, “Syntactic parameters and a coding theory perspective on entropy and complexity of language families”).
Neural codes as error-correcting codes
Curto, Itskov, Morrison, Roth and Walker (“Combinatorial neural codes from a mathematical coding theory perspective”) compare the error-correcting properties of neural codes with those of random codes of the same length and size.
The probability of a neuron failing to fire in response to a stimulus is greater than the probability of a neuron firing in the absence of a stimulus. So the channel is modeled as a binary asymmetric channel (BAC), with false-positive probability
The overall probability of an error in transmission is
The observed performance of two-dimensional receptive field neural codes compared with random codes is shown on the slides in a plot from Curto et al., “ML decoding for 2D RF codes”. It plots the probability of correct decoding against the false-positive probability
- Neural codes have high redundancy: low values of the transmission rate parameter
. - They also have low values of the relative minimum distance
. Consider a pair of overlapping receptive field open sets: there are code words with and , and a code word with both ; such code words, which differ in few places, achieve the minimum of the Hamming distance. - So neural codes lie below the Gilbert–Varshamov line (where the typical behavior of random codes is located).
- If an error-tolerance threshold is introduced between the original code word and the decoded one, then error correction becomes more similar to the case of random codes.
Most neural codes are not good codes, but “rely on” good codes
In “Error-correcting codes and neural networks”, Manin considers models of the encoding of the stimulus space via error-correcting codes.
- Computing the code parameters of typical neural codes corresponding to visual stimuli gives codes with a very low position in the space of code parameters (not good codes): the combinatorics of the covering can make the minimal Hamming distance between code words small.
- Auxiliary codes are involved in the formation of “place maps” in the brain, and experiments show that these codes have signatures of “criticality” (Nonnenmacher–Behrens–Berens–Bethge–Macke, “Signatures of criticality arise in simple neural models with correlations”; Tkačik–Mora–Marre–Amodei–Palmer–Berry–Bialek, “Thermodynamics and signatures of criticality in a network of neurons”).
In this paper Manin proposes that the “criticality” behavior of the neural codes involved in place field maps is related to their position as “good codes” near the asymptotic bound. The idea is based on a characterization of the asymptotic bound for error-correcting codes via Kolmogorov complexity, and on another characterization as a phase transition, obtained in Manin–Marcolli, “Kolmogorov complexity and the asymptotic bound for error-correcting codes”, and Manin–Marcolli, “Error-correcting codes and phase transitions”. In turn, criticality can be characterized as the behavior of a system near a phase transition, and codes weighted by a probability distribution based on Kolmogorov complexity have a phase transition at the asymptotic bound.
From bad to good neural codes via expander graphs
Rishidev Chaudhuri and Ila Fiete (“Bipartite expander Hopfield networks as self-decoding high-capacity error correcting codes”, NeurIPS 2019) describe a neural mechanism that passes from the “bad codes” of open coverings of place fields to “good codes”, via expander graphs.
- Hopfield networks are used as models for neural memory (error correction through dynamics).
- Hopfield networks with exponentially many robust stable states are constructed via expander codes.
Their schematic shows a large population of neurons with “sparse transient activation” (a few active cells scattered among many), connected by sparse bipartite wiring to a smaller row of neurons labeled “dense stable coding core”, about half of which are active.
First step: binary Hopfield networks
Definition G4.23 (Binary Hopfield network). A binary Hopfield network is a model of memory storage and retrieval in neuronal networks, by analogy with spin glass models in statistical physics (systems of many interacting
The energy functional of the network is
Proposition G4.24.
Proof. Suppose
So binary Hopfield dynamics flows toward energy minima.
Memory storage and retrieval
The idea is that the weight matrix
Definition G4.25 (Hebbian learning rule). Take weights of the form
Compare a state
The update rule of the binary Hopfield network becomes
In the case of a single pattern
Hopfield networks with continuous parameters will be discussed later.
Second step: expander graphs
Expander graphs are sparse graphs (few edges) with strong connectivity properties (many paths between nodes, and short ones). Being both highly connected and sparse, they exhibit pseudo-random behavior: a random walk through the graph gets lost quickly, which is good for stochastic and diffusion processes. Their geometric property is that every subset of vertices that is not “too large” has a “large” boundary (hence “expander”).
Definition G4.26 (Expansion constant). For two sets of vertices
This is the graph-theoretic analog of the Cheeger constant of an
Definition G4.27 (Expander property). Let
This is often taken with
Definition G4.28 (Bipartite expander graphs). Let
Bipartite graphs and linear codes
Definition G4.29 (Linear codes and parity checks). A binary
The matrix
Example G4.30. The parity-check matrix
Tanner codes
Definition G4.31 (Tanner code). Start with a linear binary code
Proposition G4.32. The code parameters of the Tanner code satisfy
(But regularity assumptions on expander graphs are not so realistic for applications to neural codes.)
Usual Hopfield networks
Definition G4.33 (Hopfield network). Take
Higher Hopfield networks from linear codes
Let
The interactions
is the number of parity-check constraints.- Assume the
have valence . - The graph
has the -expander property if for with the boundary has , with the valence of the input vertices. - Since
is the set of linear constraints of and the set of variables, the expander property means that a sufficiently small subset of variables participates in a significant part of the linear constraints. - The
input neurons in connected to can take possible states . - Fix a set
of such states , with the property that any two , , in differ in at least two digits.
The “glomerulus” structure
This gives a “constraint node network”
Definition G4.34 (Energy functional). The network has energy functional
The energy minima are given by
- If a neuron within the node Hopfield network
receives input matching the configuration (its “preferred state”), it becomes active: this is the energetically preferred configuration, because of the -term in the energy. - It suppresses the other neurons in
, because of the inhibition -term. - If the input does not match any
, the configuration has higher energy. - Minimum energy states occur when the input neuron configuration satisfies all the linear constraints (and the corresponding constraint node Hopfield networks are active).
- The total number of minimum energy states grows exponentially with the size of the network.
- For sufficiently large
the network (with all the nodes of the constraint node Hopfield networks and all the input nodes of ) is sparse and has good expander properties. - Energy-based decoding: flips violate parity check constraints and increase the energy, so the number of errors can be read off from the energy value.
As a brain model
Chaudhuri–Fiete propose this as a model of the brain.
- The bipartite graph has neurons as the input nodes, and output nodes representing small networks of neurons interacting competitively with each other through inhibition.
- The size of these small networks at the output nodes is bounded (
), independently of the sizes of the vertex sets of the bipartite graph. - Input patterns in a very high-dimensional space (possibly the neocortex) are mapped to the exponentially many stable states of a bipartite expander Hopfield network (possibly the hippocampus).
- These stable states provide memory labels for patterns that the network can retrieve.
- The expander codes associated to these networks have good code properties: a possible mechanism for passing from the bad error-correcting properties of neural codes to good codes.
References
References for the lecture
- C. Curto, V. Itskov, A. Veliz-Cuba, N. Youngs, The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes, Bull. Math. Biol. 75 (2013), no. 9, 1571–1611.
- N. Youngs, The Neural Ring: using Algebraic Geometry to analyze Neural Codes, arXiv:1409.2544.
- Yu. I. Manin, Neural codes and homotopy types: mathematical models of place field recognition, Mosc. Math. J. 15 (2015), no. 4, 741–748.
- C. Curto, N. Youngs, Neural ring homomorphisms and maps between neural codes, arXiv:1511.00255.
- E. Gross, N. K. Obatake, N. Youngs, Neural ideals and stimulus space visualization, arXiv:1607.00697.
- Yu. I. Manin, Error-correcting codes and neural networks, Selecta Math. (N.S.) 24 (2018), no. 1, 521–530.
Also cited
- A. Hatcher, Algebraic Topology, Cambridge University Press, 2002 (Corollary 4G.3).
- Yu. I. Manin, What is the maximum number of points on a curve over
?, J. Fac. Sci. Tokyo, IA, Vol. 28 (1981), 715–720. - Yu. I. Manin, A computability challenge: asymptotic bounds and isolated error-correcting codes, arXiv:1107.4246.
- Yu. I. Manin, M. Marcolli, Kolmogorov complexity and the asymptotic bound for error-correcting codes, J. Differential Geom. 97 (2014), no. 1, 91–108.
- Yu. I. Manin, M. Marcolli, Error-correcting codes and phase transitions, Mathematics in Computer Science 5 (2011), 133–170.
- M. A. Tsfasman, S. G. Vladut, Th. Zink, Modular curves, Shimura curves, and Goppa codes, better than Varshamov–Gilbert bound, Math. Nachr. 109 (1982), 21–28.
- K. Shu, M. Marcolli, Syntactic structures and code parameters, Math. Comput. Sci. 11 (2017), no. 1, 79–90.
- M. Marcolli, Syntactic parameters and a coding theory perspective on entropy and complexity of language families, Entropy 18 (2016), no. 4, paper 110.
- C. Curto, V. Itskov, K. Morrison, Z. Roth, J. L. Walker, Combinatorial neural codes from a mathematical coding theory perspective, Neural Comput. 25 (2013), no. 7, 1891–1925.
- M. Nonnenmacher, Ch. Behrens, Ph. Berens, M. Bethge, J. Macke, Signatures of criticality arise in simple neural models with correlations, arXiv:1603.00097.
- G. Tkačik, T. Mora, O. Marre, D. Amodei, S. Palmer, M. Berry, W. Bialek, Thermodynamics and signatures of criticality in a network of neurons, Proc. Natl. Acad. Sci. USA 112 (2015), no. 37, 11508–11513.
- R. Chaudhuri, I. Fiete, Bipartite expander Hopfield networks as self-decoding high-capacity error correcting codes, 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada.