Capacity Analysis of Vector Symbolic Architectures
summary
Paper gives concrete dimension bounds and algorithms: MAP-I reduces to sketching and uses JL-type sign matrices to prove how large m must be for membership and |X∩Y| estimates; bundles-of-bindings require expanding columns and use McDiarmid-style concentration; Bloom filters get a new set-intersection estimator with a collision-compensation h function; a novel variant Hopfield± matches VSA efficiency by using a Gramian-based one-step recovery; empirical/analytic weakness: MAP-B loses signal 2^{-r} under repeated online bundling.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:07Vector symbolic architectures
- 2:33MAP-I atomic vectors
- 8:47Advantages and applications of VSAs
- 10:58VSA sketching for sets
- 13:50VSA capacity analysis
- 14:56Johnson-Lindenstrauss lemma
- 18:54Bindings and norm preservation
- 21:23Rotations and sequence encoding
- 23:16Hopfield networks vs VSAs
- 27:50Hopfield ± algorithm
- 30:25Non-linear operations in MAP-B
- 35:10Clipping in MAP-B
- 35:53Bloom filters as VSAs
- 37:02Set intersection in Bloom filters
- 40:26Limitations and future work
- 40:50Q&A
related talks
27m"Vector Symbolic Architectures In Clojure"
39mUniversal Sketches
35mImpact of Vector Search
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
01h 40mBoot camp on generalization theory for graph learning
34mThe Challenges of Making Vector Search Billion-scale
31mStatistical Estimation on Graphs
01h 06mData Streams I