Source-linked AI summary
Properties of Sparse Distributed Representations and their Application to Hierarchical Temporal Memory
Subutai Ahmad, Jeff Hawkins
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.
Method
The paper derives SDR bounds, scaling laws, and error properties, and maps these mathematical results to HTM operations.
Results
SDRs support robust classification under noise, massive temporal-sequence capacity, and dynamic-set representation through the union property.
Takeaways & Limitations
Under appropriate parameters, SDRs provide a mathematical basis for highly robust HTM systems and temporal prediction, pooling, invariance, and hierarchy operations.
Abstract
from arXiv · showhide
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.
- Overlap measures SDR similarity by counting active bits in the same locations.
- SDR matching occurs when overlap reaches or exceeds a threshold θ, typically constrained by the active-bit counts of both vectors.
- For example, vectors with n=40 and w=4 match when their overlap is 3 and θ=3.
- Typical HTM parameters span n=1024 to 65,536, w=10 to 40, and sparsity s=0.05% to 2.0%.
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.
- For n=40 and w=4, SDRs provide 91,390 encodings, while n=2048 and w=40 provide 2.37×10^? encodings.
- The SDR encoding space is smaller than the 2^n possibilities of dense representations, but remains astronomically large at typical HTM parameters.
- For n=1024 and w=2, identical random encodings occur with probability 1 in 523,776.
- Increasing w sharply reduces identity probability, reaching essentially zero for n=2048 and w=40.
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.
- With w=40 and θ=20, random noise can change 50% of ON bits while the corrupted vector still matches the original.
- For n=1024, w=4, and θ=2, the false-match probability is one in 14,587 under 50% noise.
- Increasing w and θ to 20 and 10 reduces the false-match probability to less than 1 in 10^?.
- The false-positive approximation is accurate when the first term in the numerator sum dominates by at least an order of magnitude.
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.
- Increasing subsampling raises the chance of a false positive.
- With n=1024, subsampling from w=8 to w′=4 at θ=2 yields an error probability of one in 3,142.
- With w=20, w′=10, and θ=5, the false-positive probability falls to 1 in 2.5 million.
- At n=2048, w=40, w′=20, and θ=10, the false-positive probability is better than 1 in 10^?.
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.
- When noise changes at most t ≤ w−θ bits, classification has no false negatives and errors arise only from false positives.
- With n=64, w=3, θ=2, storing 10 vectors gives a false-positive probability of about 1 in 22.
- 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.
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).
- A fixed-size union vector can store a dynamic set of elements and supports temporal prediction, temporal pooling, invariance, and hierarchy operations in HTM.
- The union has no false negatives for stored vectors, but increasing M saturates ON bits and raises false positives for random vectors.
- 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.
- 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.
- HTM vector sizes are often substantially larger than 1024, making the union property particularly useful in HTM systems.
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.
- The false-match probability is computed from the expected number of ON bits in the union and the size of the corresponding overlap set.
- The resulting error expression is an approximation based on the expected union size, with the first numerator term dominating in most practical cases.
- 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.
- 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.
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.
- HTM relies on binary SDRs as its primary data structure across specialized functions.
- The discussion assumes familiarity with HTM neuron models, spatial pooling, and prediction operations.
- Hierarchy, feedback, sensorimotor inference, and motor commands also rely on SDR properties, but are outside this paper’s scope.
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.
- 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.
- Spatial pooling: In the absence of learning, the top k columns form the output SDR, which is passed to subsequent Temporal Memory processes.
- Spatial pooling: The overlap curve estimates column overlaps and indicates that sharper separation after k improves robustness to input noise; SP learning sharpens this curve.
- Temporal memory: The first TM phase combines the spatial-pooled SDR with the previous predicted state to determine the current active state.
- Temporal memory: 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.
- Temporal memory: The TM predicted state represents a union of possible next states, whose robustness is fundamental to TM performance.
- 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.
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.
- SDRs support robust classification under noise and random deletions, while the union property represents dynamic lists within one SDR.
- Under suitable parameters, SDRs provide massive temporal-sequence capacity and form the basis of robust classification systems.
- Together, these properties provide a mathematical theory characterizing HTM-system robustness.
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.
- 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.
- 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.
- With n=64, significant pooling is difficult because the error rate is too high.
- With typical settings of 1024 or 2048 columns, very large amounts of pooling are possible with very low error rates and reasonable noise robustness.