S. D. V. Stephens

notes / Basic Neuroscience and Geometry of Neuroscience / chapter 7: Neurons and Neural Codes

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 . A neural code is a subset , where . Its elements, the codewords (or “codes”) , describe activation states of the neurons. The support of a codeword is and the code has the collection of supports where is the set of all subsets of .

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 is a simplicial complex if whenever and , also . A neural code is simplicial if is a simplicial complex. If it is not, the simplicial complex of the neural code is the smallest simplicial complex containing .

Left: a simplicial complex made of a solid tetrahedron, filled triangles, edges and a hollow triangle glued along common faces. Right: two triangles that cross each other in a region that is not a face of either, so they do not form a simplicial complex.

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 be the space of stimuli, and for each neuron let be the average firing rate of the -th neuron in response to the stimulus . The open sets are the receptive fields; they are usually assumed convex. The place field of a neuron is its preferred convex region of the stimulus space, where it has a high firing rate. (For orientation-selective neurons the firing rates are tuning curves, with a preference for a particular angle, and the receptive fields are intervals on a circle.) Codewords arise from the way the receptive fields overlap.

Panel A: five bump-shaped tuning curves on a line; a stimulus in the shaded interval activates neurons 1, 2 and 3, giving codeword 11100. Panel B: five overlapping discs in the plane; a stimulus in the shaded region lies only in discs 3 and 5, giving codeword 00101.

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 . In panel B the receptive fields are five discs in the plane; a stimulus in the shaded region lies in and only, giving the codeword .

The receptive field code

Definition G4.2 (Receptive field code). Let be a stimulus space and a set of neurons with receptive fields and convex sets , and let be the collection of (convex) open sets. The receptive field code is the set of all binary codewords corresponding to stimuli in , with the convention that the intersection over is and the union over is .

If , there are points of the stimulus space not covered by any receptive field, and the word is in . If , the word records the points where all the neurons are activated.

Reconstructing the stimulus space

The main question: if we know the code without knowing and , what can we learn about the geometry of ? To what extent is reconstructible from ?

Step one: every code is a receptive field code

Proposition G4.3. Let be a code with codewords. There exist an and a collection of (not necessarily convex) open sets such that .

Proof. List the codewords , . For each codeword choose a point and an open neighborhood such that for . Take and with If the zero codeword is in , its neighborhood is the set of outside points not captured by the code. By construction . ∎

Caveat: convexity is a real restriction

We can always find with , but not always with the convex.

Example G4.4. The code cannot be realized by a collection with the convex.

Suppose it could: convex with . Then we know that

  • , because ;
  • , because ;
  • , because .

Take points and . Both are in , which is convex, so the segment lies in .

  • 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.
Two cases of the convexity argument. Left: two overlapping ovals U1 and U2 with p1 in U1 only and p2 in U2 only; the segment from p1 to p2 crosses their intersection. Right: two elongated ovals crossing near the top; the segment from p1 to p2 runs below the crossing and leaves both ovals.

Topological constraints on the stimulus space

Codes that can be realized as with the convex put strong constraints on the geometry of the stimulus space . There are two types of constraints:

  1. constraints from the simplicial complex ;
  2. other constraints from that are not captured by .

The nerve of an open covering

Definition G4.5 (Simplicial nerve). Let be convex open sets in with . The nerve is the simplicial complex in which is a simplex if and only if .

The nerve is the simplicial complex of the receptive field code:

Seven dashed open discs with their nerve drawn on the disc centres: four discs with a common point give a solid tetrahedron, three give a triangle attached to it, and two more overlapping pairs give a path of two edges.

In this example of convex open sets and their nerve , the four discs on the left have a common point and give a solid tetrahedron; two of them meet a fifth disc in a common region, giving a triangle; and two more overlapping pairs give two edges. A second example on the slides shows about fifteen dashed circles, with a nerve made of a ring of edges and triangles on the left, a path, and a group of four mutually overlapping circles on the right.

The complex is also known as the Čech complex of the collection of convex open sets.

Helly’s theorem

Theorem G4.6 (Helly’s theorem). Let be convex, with . If the intersection of every of the is nonempty, then also .

The -skeleton of a simplicial complex is the subcomplex of its simplices of dimension at most (subsets with at most elements).

Corollary G4.7. For convex open sets , the nerve is completely determined by its -skeleton: it is the largest simplicial complex on with that given -skeleton.

Left: a simplicial complex on vertices 1 to 9 with a solid tetrahedron on 1, 2, 3, 4, a filled triangle on 5, 6, 7, and edges 3-5, 5-8, 7-8 and 7-9. Right: its 1-skeleton, the graph of all its vertices and edges.

The nerve theorem

Theorem G4.8 (Nerve theorem). (Hatcher, Algebraic Topology, Corollary 4G.3.) For a collection of convex open sets, the homotopy type of is the same as the homotopy type of the nerve .

As a consequence, and have the same homology and homotopy groups (but not necessarily the same dimension).

Note. The space may not capture all of the stimulus space if the are not an open covering of , that is, if .

Homology groups

Homology groups are very useful topological invariants, and they are computationally tractable.

Definition G4.9 (Homology groups). Let be a simplicial complex. The group of -chains is the abelian group spanned by the -dimensional simplices of . The boundary maps satisfy usually stated as . The cycles are and the boundaries are ; because there is an inclusion . The homology groups are the quotient groups

On an oriented edge, triangle and tetrahedron the boundary maps are

Boundary maps on oriented simplices: an edge from v0 to v1 maps to [v1] - [v0]; a triangle maps to its three edges oriented around the boundary, [v1,v2] - [v0,v2] + [v0,v1]; a tetrahedron maps to its four faces, [v1,v2,v3] - [v0,v2,v3] + [v0,v1,v3] - [v0,v1,v2].

The chain complex and its homology can be pictured as below. Inside each sit the cycles , and inside those the boundaries; maps all of onto the boundaries in and maps the cycles to . (In the picture the image of in is labeled , the more common indexing; above it was called .)

Three nested ovals for C_{p+1}, C_p and C_{p-1}, each containing cycles Z and inside them boundaries B, all touching at the zero element; the boundary map sends all of C_{p+1} onto B_p and the cycles Z_{p+1} to zero, and likewise from C_p to C_{p-1}.

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 , each having . Square boxes denote the stimulus space in the cases where .

Four arrangements of three convex receptive fields: A, three discs in general position inside a square stimulus space; B, two overlapping discs 1 and 2 inside an oval 3 that is the whole stimulus space; C, three nested discs 1 inside 2 inside 3 within a square; D, two overlapping discs 1 and 2 with a thin oval 3 lying across their overlap.
  • (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 , while for panels B and C it is . All four have the same , because is a codeword in every case.

Embedding dimension

Definition G4.10 (Embedding dimension). The minimal embedding dimension of a code is the minimal dimension for which can be realized as with convex open sets .

The topological dimension of a space is the minimum such that any open covering has a refinement (an open covering each of whose sets lies in some set of the original covering) in which no point is in more than open sets of the covering.

A square covered by six discs; an arrow marks a point lying in three of the discs and another arrow a point lying in two. No point lies in more than three discs.

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 is the same, but the embedding dimension differs.

Nontrivial inclusions

The main information carried by the code lies in nontrivial inclusions.

  • 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 including all the empty intersection relations

Algebraic geometry of neural codes

Problem: how can we extract this information from algorithmically, without having to construct ? The key method is algebraic geometry: ideals and varieties.

Rings and ideals

Definition G4.11 (Ideals). Let be a commutative ring with unit. An ideal is an additive subgroup such that for and for all the product . A set generates if

  • 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 (in the polynomial rings used here) has a prime decomposition with the prime ideals.

Affine algebraic varieties

Definition G4.12 (Varieties and spectrum). Let be the polynomial ring over a field . An ideal determines the variety The spectrum of a ring is its set of prime ideals,

Ideals give varieties .

To model neurons with binary on/off states we take ; then is a possible state of the set of neurons.

The neural ring

Definition G4.13 (Neural ring). Given a binary code (a neural code), let be the ideal of polynomials vanishing on the codewords, The quotient ring is the neural ring of .

Note. We are working over , so , and contains the relations . So in all elements are idempotent, (the cross terms vanish): is a Boolean ring, isomorphic to . It is still useful to keep the explicit coordinate functions , which measure the activity of the -th neuron.

The spectrum of the neural ring

The points give maximal ideals of the polynomial ring , and these are exactly the maximal ideals that contain the relations . In a Boolean ring the prime ideal spectrum and the maximal ideal spectrum coincide.

Proposition G4.14. For the neural ring , the spectrum is where is the image in the quotient ring of the maximal ideal of .

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 , which is a problem for practical computational purposes. A closely related and more tractable ideal is the neural ideal .

Definition G4.15 (Neural ideal). Given (a possible state of a system of neurons), take the function (as a function on it equals at and elsewhere). A binary code determines the neural ideal When we have , the trivial ideal.

The ideal of Boolean relations is

Proposition G4.16. The ideals and are related by

Neural ring relations

Notation: given open sets and , set Interpret the coordinates as functions on :

Inclusions give relations. If , then implies either or , so we get the relation (this polynomial vanishes at every point of ). In the same way, every inclusion corresponds to a relation , and the ideal is generated by them (these are the relations defining ):

Pseudomonomials and canonical form

Consider such a relation , with subsets and . If then ; if then .

Definition G4.17 (Pseudomonomials and canonical form). A function of the form with is a pseudomonomial, and an ideal generated by pseudomonomials is a pseudomonomial ideal. A pseudomonomial is minimal if there is no other pseudomonomial with and for some . The canonical form of a pseudomonomial ideal is , with the all the minimal pseudomonomials in .

The neural ideal is a pseudomonomial ideal. The ideal is not, because of the Boolean relations.

The canonical form of the neural ideal

A subset is minimal for a property if is satisfied by and not satisfied by any .

Theorem G4.18 (Canonical form of the neural ideal). Let be a binary code, realized as with in (not necessarily convex). The canonical form of consists of three types of relations:

  1. , with minimal for ;
  2. , with , , , and minimal for ;
  3. , with minimal for .

The Type 1 relations bound the minimal embedding dimension: (By Helly’s theorem, a minimal empty intersection of convex sets in involves at most of them.)

There are efficient algorithms to compute from , without passing through .

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):

Four arrangements of three convex receptive fields: A, three discs in general position inside a square stimulus space; B, two overlapping discs 1 and 2 inside an oval 3 that is the whole stimulus space; C, three nested discs 1 inside 2 inside 3 within a square; D, two overlapping discs 1 and 2 with a thin oval 3 lying across their overlap.

A. . There are no relations here because .

B. . This Type 3 relation reflects the fact that .

C. . These Type 2 relations correspond to , and . The first two of these receptive field relationships imply the third; correspondingly, the third canonical form relation satisfies

D. . This Type 3 relation reflects , and implies .

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 (for binary codes) and a code (code words of length ), with code words . Codes are unstructured: we don’t necessarily require that the code be linear ( is not necessarily an -vector space).

Definition G4.20 (Code parameters). Let , and let be the integer part of , so that The Hamming distance between and in is and the minimal distance of the code is The code parameters are

  • , the transmission rate of the code;
  • , the relative minimum distance of the code.

Small : fewer code words, easier decoding, but a longer encoding signal. Small : too many code words close to the received one, more difficult decoding. The optimization problem is to increase both and … how good can codes be?

Bounds in the space of code parameters

Each code gives a code point in the square . There is a tension between optimizing and optimizing , which can be seen in several bounds.

  • 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 , where is the -ary entropy

The curve comes from the asymptotic behavior of volumes of balls in the Hamming distance as the code length , which is governed by the function . Writing for the number of words within Hamming distance of a given word of length over an alphabet of letters, the volume estimate is This shows that the parameter of a code from the SRCE meets the GV bound with probability exponentially (in ) near . The expected number of pairs of distinct code words within Hamming distance of each other, for a random code with words, is which is exponentially small when .

The asymptotic bound

There is another curve in the space of code parameters: the asymptotic bound . Its existence was proved by Manin using spoiling operations on codes (operations, such as adding or deleting a coordinate, that turn a code into codes with worse parameters), in “What is the maximum number of points on a curve over ?” (1981).

There is no explicit expression for the asymptotic bound . In fact the computability of this function is in question, because of its relation to Kolmogorov complexity (the length of the shortest program that produces a given object): see Manin, “A computability challenge: asymptotic bounds and isolated error-correcting codes”, and Manin–Marcolli, “Kolmogorov complexity and the asymptotic bound for error-correcting codes”.

Proposition G4.21 (Known estimates on the asymptotic bound). Plotkin bound: Singleton bound: lies below .

Hamming bound: Gilbert–Varshamov bound:

Unlike the Gilbert–Varshamov bound and random codes, the asymptotic bound has no statistical description.

Characterization of the asymptotic bound. The curve separates the region below it, where code points are dense and have infinite multiplicity, from the region above it, where code points are isolated and have finite multiplicity (Manin–Marcolli, “Error-correcting codes and phase transitions”).

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 of a flipping to and false-negative probability of the opposite flip, with . (Here is a probability, not the size of an alphabet.) One also assumes that the error probability is smaller than the sparsity of the neural code, where is the weight of .

The overall probability of an error in transmission is (for words transmitted with equal probabilities). The maximum likelihood decoder uses , the probability that is received if was transmitted: For symmetric errors , this decoding is equivalent to the usual minimization of Hamming distance:

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 , from to . For the 2D receptive field codes it falls from about to about ; for shuffled codes and random codes of the same size it stays high, between about and .

  • 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 “spins”). A population of neurons each has two possible states , firing or not firing (in a fixed time interval ). The discrete dynamics, with weight matrix assumed symmetric (), is with the update rule implemented on a single at a time: either maintaining its value or flipping.

The energy functional of the network is

Proposition G4.24. is a Lyapunov function of the dynamics (a quantity that never increases along the dynamics): it decreases under the flipping of a single under the update rule.

Proof. Suppose and for . Then using the update rule and the symmetry of . ∎

So binary Hopfield dynamics flows toward energy minima.

Memory storage and retrieval

The idea is that the weight matrix is determined by a given set of patterns one wants to store in the network: a set of patterns, binary strings satisfying .

Definition G4.25 (Hebbian learning rule). Take weights of the form

Compare a state with one of the patterns by measuring the overlap It has maximum value when and match completely, minimum value for the opposite pattern, and values for low correlation.

The update rule of the binary Hopfield network becomes and the energy has minima at the patterns (where the overlap is maximal) and at their opposites. Initializing the dynamics close to one of the stored patterns causes the dynamics to reconstruct the pattern, by flowing to the corresponding energy minimum.

In the case of a single pattern , the pattern is a fixed point of the dynamics: This is not always so for multiple patterns: since and .

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”).

Left: an expander-like graph on ten vertices arranged in a circle, each vertex with three edges, many crossing through the centre. Right: a poorly connected graph made of two dense clusters of five vertices joined by a single edge.

Definition G4.26 (Expansion constant). For two sets of vertices of a graph , let be the set of edges of with one end-vertex in and the other in , and let be the “boundary” of the region with vertex set . The expansion constant of , with vertex set of size , is

This is the graph-theoretic analog of the Cheeger constant of an -dimensional Riemannian manifold , the infimum over all -dimensional submanifolds that decompose . The constant measures whether the manifold has bottlenecks, and so does . It is related to the spectrum of the graph Laplacian.

Definition G4.27 (Expander property). Let , and . The graph is a -expander if for

This is often taken with , as in above. A good expander graph has a large expansion constant and low vertex degrees.

Definition G4.28 (Bipartite expander graphs). Let be a bipartite graph whose input vertices all have the same valence . Then is a -expander if all subsets of input vertices with have where is the set of neighbors of . A particular case is that of the -biregular graphs, where is the valence of the input set and the valence of the output set.

A bipartite graph with eight square output vertices on top and nine round input vertices below; the three middle inputs, boxed and labelled S, each send three edges upward, reaching seven distinct outputs, the neighbourhood N(S).

Bipartite graphs and linear codes

Definition G4.29 (Linear codes and parity checks). A binary -code (length , minimum distance ) is linear if is a linear subspace of the -vector space ; then . A parity-check matrix of is an matrix of rank over with

The matrix describes the linear code in terms of a bipartite graph, with one vertex for each digit , one vertex for each row of , and an edge when .

Example G4.30. The parity-check matrix imposes the code constraints and gives the bipartite graph

Bipartite graph of a linear code: seven variable nodes x1 to x7 on the left joined to three check nodes on the right, one for each constraint x1+x3+x4+x7=0, x1+x2+x4+x6=0 and x1+x2+x3+x5=0.

Tanner codes

Definition G4.31 (Tanner code). Start with a linear binary code with code parameters (not necessarily a good code). Let be a bipartite graph with inputs and outputs that is right--regular (all output vertices have the same valence ). The Tanner code is where is the restriction of to the neighbors of .

Proposition G4.32. The code parameters of the Tanner code satisfy where the -estimate holds if is -biregular with and a -expander, and for .

(But regularity assumptions on expander graphs are not so realistic for applications to neural codes.)

Usual Hopfield networks

Definition G4.33 (Hopfield network). Take neurons with binary values, detecting whether the neurons are active or inactive in the -th time interval. The network has discrete dynamics with activation thresholds and weight matrix , and energy functional The discrete update rule of the dynamics changes the state of a neuron and accepts the change if it decreases the energy.

Higher Hopfield networks from linear codes

Let be a linear code with constraints specified by the parity check matrix , represented as a bipartite graph : the set of (input) nodes is the digits of the code words (code length ), and the set of (output) nodes is the linear constraints imposed by the parity check matrix (codimension ), Write the parity check constraints multiplicatively, with spins : Then the energy functional is minimized at the satisfying the -constraints.

The interactions of this higher Hopfield network couple a whole simplex of neurons (all the with ) instead of a pair of graph vertices. The construction below reduces them to usual Hopfield networks.

  • 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” with at most nodes (a set of words of length , any two of which differ in at least two digits, has at most elements), all with shared inputs from the vertices of : a glomerulus (node Hopfield network).

Two grey boxes, each a constraint node network of eight units arranged around a hatched central node (2^{z_C-1} units), above a row of input neurons; each box is wired to z_C = 4 of the input neurons.

Definition G4.34 (Energy functional). The network has energy functional where and , and , with and , is The vector is given by with , and is the -matrix with zeros on the diagonal and all other entries equal to : inhibitory connections between constraint neurons.

The energy minima are given by and .

  • 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.