Properties of Sparse Distributed Representations and their Application to Hierarchical Temporal Memory

Subutai Ahmad; Jeff Hawkins

Source-linked AI summary

Properties of Sparse Distributed Representations and their Application to Hierarchical Temporal Memory

Subutai Ahmad, Jeff Hawkins

arXiv:1503.07469v1Mar 25, 2015q-bio.NCcs.AI

TL;DR

The paper addresses the missing theoretical understanding of the capacity and robustness of cortical sparse representations. It derives mathematical properties and scaling laws for SDRs, then applies them to HTM operations. The results show robust classification under noise, large temporal-sequence capacity, and useful fixed-size union representations, with trade-offs involving false positives.

Problem
The paper addresses the missing detailed theoretical understanding of the capacity and robustness of cortical sparse representations.
Source: §II · p. 2
Method
The paper derives SDR bounds, scaling laws, and error properties, and maps these mathematical results to HTM operations.
Source: §II · p. 2, §IV · p. 14
Results
SDRs support robust classification under noise, massive temporal-sequence capacity, and dynamic-set representation through the union property.
Source: G. The Surprising Union Property · p. 7, B. Spatial Pooling · p. 13, §IV · p. 14
Takeaways & Limitations
Under appropriate parameters, SDRs provide a mathematical basis for highly robust HTM systems and temporal prediction, pooling, invariance, and hierarchy operations.
Source: G. The Surprising Union Property · p. 7, §IV · p. 14

Abstract

from arXiv · show

Empirical evidence demonstrates that every region of the neocortex represents information using sparse activity patterns. This paper examines Sparse Distributed Representations (SDRs), the primary information representation strategy in Hierarchical Temporal Memory (HTM) systems and the neocortex. We derive a number of properties that are core to scaling, robustness, and generalization. We use the theory to provide practical guidelines and illustrate the power of SDRs as the basis of HTM. Our goal is to help create a unified mathematical and practical framework for SDRs as it relates to cortical function.

II. Mathematical Foundations of SDRs

SDRs represent activity as sparse binary vectors and use overlap-based matching to quantify similarity. Their mathematical analysis establishes parameters and scaling properties relevant to HTM memory operations.

An SDR is an n-dimensional binary vector with a small number w of active components.Source: A. Definitions and Notation · p. 2
Overlap measures SDR similarity by counting active bits in the same locations.Source: A. Definitions and Notation · p. 2
SDR matching occurs when overlap reaches or exceeds a threshold θ, typically constrained by the active-bit counts of both vectors.Source: A. Definitions and Notation · p. 2
For example, vectors with n=40 and w=4 match when their overlap is 3 and θ=3.Source: A. Definitions and Notation · p. 3
Typical HTM parameters span n=1024 to 65,536, w=10 to 40, and sparsity s=0.05% to 2.0%.Source: A. Definitions and Notation · p. 3

B. Uniqueness and Exact Matches

Sparse encodings provide a large space of unique representations, making accidental identity between random SDRs extremely unlikely at typical HTM parameters.

With fixed n and w, the number of unique SDR encodings is the combination n choose w.Source: B. Uniqueness and Exact Matches · p. 3
For n=40 and w=4, SDRs provide 91,390 encodings, while n=2048 and w=40 provide 2.37×10^? encodings.Source: B. Uniqueness and Exact Matches · p. 3
The SDR encoding space is smaller than the 2^n possibilities of dense representations, but remains astronomically large at typical HTM parameters.Source: B. Uniqueness and Exact Matches · p. 3
For n=1024 and w=2, identical random encodings occur with probability 1 in 523,776.Source: B. Uniqueness and Exact Matches · p. 3
Increasing w sharply reduces identity probability, reaching essentially zero for n=2048 and w=40.Source: B. Uniqueness and Exact Matches · p. 3

D. Inexact Matching

Inexact SDR matching trades stricter discrimination for noise tolerance. Appropriate parameters can preserve matching under substantial corruption while keeping false matches very unlikely.

Lowering the match threshold θ increases noise robustness but also increases false-positive probability.Source: D. Inexact Matching · p. 4
With w=40 and θ=20, random noise can change 50% of ON bits while the corrupted vector still matches the original.Source: D. Inexact Matching · p. 4
For n=1024, w=4, and θ=2, the false-match probability is one in 14,587 under 50% noise.Source: D. Inexact Matching · p. 4
Increasing w and θ to 20 and 10 reduces the false-match probability to less than 1 in 10^?.Source: D. Inexact Matching · p. 4
The false-positive approximation is accurate when the first term in the numerator sum dominates by at least an order of magnitude.Source: D. Inexact Matching · p. 4

E. Subsampling

SDRs can recognize a larger pattern from a subsampled set of active bits, although more aggressive subsampling increases false positives. Larger vectors and active-bit counts substantially improve reliability.

A subsampled SDR always matches its original when θ does not exceed the subsample’s active-bit count.Source: E. Subsampling · p. 5
Increasing subsampling raises the chance of a false positive.Source: E. Subsampling · p. 5
With n=1024, subsampling from w=8 to w′=4 at θ=2 yields an error probability of one in 3,142.Source: E. Subsampling · p. 5
With w=20, w′=10, and θ=5, the false-positive probability falls to 1 in 2.5 million.Source: E. Subsampling · p. 5
At n=2048, w=40, w′=20, and θ=10, the false-positive probability is better than 1 in 10^?.Source: E. Subsampling · p. 5

F. Classifying a Set of Vectors

The paper analyzes classifying noisy SDRs against a stored set, showing that sufficiently large SDR parameters support extremely low false-positive rates while tolerating substantial corruption.

The classifier tests whether an input matches any member of a set of unique SDR vectors.The false-positive analysis assumes stored vectors are unique with respect to the matching threshold.Source: F. Classifying a Set of Vectors · pp. 5–6
When noise changes at most t ≤ w−θ bits, classification has no false negatives and errors arise only from false positives.Source: F. Classifying a Set of Vectors · p. 6
With n=64, w=3, θ=2, storing 10 vectors gives a false-positive probability of about 1 in 22.Source: F. Classifying a Set of Vectors · p. 6
The analysis concludes that massive pattern sets can be retrieved almost perfectly under substantial noise when n, w, and t are sufficiently high.Low values such as n=64 and w=3 are insufficient to capture these properties.Source: F. Classifying a Set of Vectors · p. 6

G. The Surprising Union Property

The union property stores many SDR patterns in one fixed-size vector formed by OR operations and tests membership through overlap matching. Its reliability improves with suitable dimensions and sparsity but is limited by false positives as unions saturate.

The union property forms one fixed representation by taking the Boolean OR of M SDR vectors.Membership is tested by computing match(X, y).Source: G. The Surprising Union Property · pp. 6–7
A fixed-size union vector can store a dynamic set of elements and supports temporal prediction, temporal pooling, invariance, and hierarchy operations in HTM.Source: G. The Surprising Union Property · p. 7
The union has no false negatives for stored vectors, but increasing M saturates ON bits and raises false positives for random vectors.Source: G. The Surprising Union Property · p. 7
For n=1024 and w=2, storing M=20 vectors gives a false-positive probability of about 1 in 680, whereas w=20 lowers it to about 1 in 5.5 billion.Source: G. The Surprising Union Property · p. 8
The expected number of ON bits grows sublinearly with M, and increasing n and w substantially increases the number of patterns that can be unioned reliably.For M=80, 20% of union bits remain OFF, so a new 40-bit vector has opportunities to avoid a false positive.Source: G. The Surprising Union Property · p. 8, Figure 2 · p. 8
HTM vector sizes are often substantially larger than 1024, making the union property particularly useful in HTM systems.Source: G. The Surprising Union Property · p. 9

H. Inexact Matches with Unions

The paper extends union matching to inexact thresholds so unions can tolerate noise, while quantifying the resulting false-positive tradeoff. Increasing the vector dimension can sharply reduce the error introduced by lower thresholds.

Inexact union matching lowers the threshold θ below w to study matching against noisy inputs.Source: H. Inexact Matches with Unions · p. 9
The false-match probability is computed from the expected number of ON bits in the union and the size of the corresponding overlap set.Source: H. Inexact Matches with Unions · p. 9
The resulting error expression is an approximation based on the expected union size, with the first numerator term dominating in most practical cases.Source: H. Inexact Matches with Unions · p. 9
For n=1024, w=20, and M=20, lowering θ from 20 to 19 raises the false-positive rate from about 1 in 5 billion to about 1 in 123 million, and θ=18 raises it to 1 in 4 million.Source: H. Inexact Matches with Unions · p. 9
With n increased to 2048 while θ=18, the false-positive rate improves to 1 in 223 billion.The example illustrates how larger SDR dimensions can offset the error increase caused by lower thresholds.Source: H. Inexact Matches with Unions · p. 9

I. Computational Efficiency

SDR operations run in time proportional to the number of active bits rather than the full vector size. This is important for HTM because SDRs are typically much sparser than they are long.

SDR operations run in O(w) time, independent of vector size n.Source: §I · p. 10
HTM relies on binary SDRs as its primary data structure across specialized functions.Source: §III · p. 10
The discussion assumes familiarity with HTM neuron models, spatial pooling, and prediction operations.Source: §III · p. 10
Hierarchy, feedback, sensorimotor inference, and motor commands also rely on SDR properties, but are outside this paper’s scope.Source: §III · p. 10

A. Notation

The paper defines SDR operations and applies them to HTM’s spatial pooling and temporal memory processes. These operations select sparse winners, determine active states, form predictions, and support sequence learning through cell-specific contexts.

HTM algorithms

Spatial Pooling and Temporal Memory are the main HTM algorithms discussed.Source: A. Notation · p. 10

Spatial pooling

The SP process multiplies an input vector by connected-synapse columns, then selects the top k overlap counts as ON bits in a 1×C output SDR.Source: B. Spatial Pooling · pp. 10–11
In the absence of learning, the top k columns form the output SDR, which is passed to subsequent Temporal Memory processes.Source: B. Spatial Pooling · p. 11
The overlap curve estimates column overlaps and indicates that sharper separation after k improves robustness to input noise; SP learning sharpens this curve.Source: B. Spatial Pooling · p. 11

Temporal memory

The first TM phase combines the spatial-pooled SDR with the previous predicted state to determine the current active state.Source: B. Spatial Pooling · p. 12, Figure 5 · p. 12
The second TM phase matches cell segments against the active state, turning a cell ON when a segment exceeds threshold to produce the next predicted state.Source: B. Spatial Pooling · p. 13, Figure 6 · p. 13
The TM predicted state represents a union of possible next states, whose robustness is fundamental to TM performance.Source: B. Spatial Pooling · pp. 13–14

Sequence learning

With w columns containing x cells each, HTM can represent x! temporal contexts for the same input; w=40 and x=8 yield 1.33×10^7 contexts.Source: B. Spatial Pooling · p. 13

IV. Conclusion

The conclusion presents SDRs as a mathematical basis for understanding HTM capacity, robustness, and scaling. Under suitable parameters, SDRs support robust classification and large temporal-sequence capacity.

SDR mathematics yields bounds, scaling laws, performance characteristics, and ideal parameter choices for HTM systems.Source: §IV · p. 14
SDRs support robust classification under noise and random deletions, while the union property represents dynamic lists within one SDR.Source: §IV · p. 14
Under suitable parameters, SDRs provide massive temporal-sequence capacity and form the basis of robust classification systems.Source: §IV · p. 14
Together, these properties provide a mathematical theory characterizing HTM-system robustness.Source: §IV · p. 14

Appendix A – Practical Considerations

Practical HTM performance depends strongly on parameter scale: the derived equations and tables guide network settings, while larger SDR dimensions support more reliable pooling and classification.

The derived equations guide HTM parameters including column count, sparsity, potential pooling, thresholds, and temporal-memory limits.They also indicate how many patterns can be reliably pooled together.Source: The Numbers Game · pp. 15–16
Small toy values can obscure SDR behavior because practical properties involve exponential and super-exponential scaling.Initial toy problems help debugging, but practical parameter values are needed for meaningful behavior.Source: The Numbers Game · p. 16
Tables report pattern counts and false-match probabilities for exact matches, inexact matches, vector classification, and unions.These tables are intended to help understand SDR behavior and set parameters appropriately.Source: The Numbers Game · p. 16, Table 1 · p. 16, Table 2 · p. 16
With n=64, significant pooling is difficult because the error rate is too high.Source: SDR Actuarial Tables · p. 18
With typical settings of 1024 or 2048 columns, very large amounts of pooling are possible with very low error rates and reasonable noise robustness.Source: SDR Actuarial Tables · p. 18