{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:44:07Z","timestamp":1764175447085},"reference-count":60,"publisher":"MIT Press","issue":"7","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We investigate the task of retrieving information from compositional distributed representations formed by hyperdimensional computing\/vector symbolic architectures and present novel techniques that achieve new information rate bounds. First, we provide an overview of the decoding techniques that can be used to approach the retrieval task. The techniques are categorized into four groups. We then evaluate the considered techniques in several settings that involve, for example, inclusion of external noise and storage elements with reduced precision. In particular, we find that the decoding techniques from the sparse coding and compressed sensing literature (rarely used for hyperdimensional computing\/vector symbolic architectures) are also well suited for decoding information from the compositional distributed representations. Combining these decoding techniques with interference cancellation ideas from communications improves previously reported bounds (Hersche et al., 2021) of the information rate of the distributed representations from 1.20 to 1.40 bits per dimension for smaller codebooks and from 0.60 to 1.26 bits per dimension for larger codebooks.<\/jats:p>","DOI":"10.1162\/neco_a_01590","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T22:20:42Z","timestamp":1684189242000},"page":"1159-1186","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":10,"title":["Efficient Decoding of Compositional Structure in Holistic Representations"],"prefix":"10.1162","volume":"35","author":[{"given":"Denis","family":"Kleyko","sequence":"first","affiliation":[{"name":"Redwood Center for Theoretical Neuroscience, University of California at Berkeley, Berkeley, CA 94720, U.S.A."},{"name":"Intelligent Systems Laboratory, Research Institutes of Sweden, 16440 Kista, Sweden denis.kleyko@ri.se"}]},{"given":"Connor","family":"Bybee","sequence":"additional","affiliation":[{"name":"Redwood Center for Theoretical Neuroscience, University of California at Berkeley, Berkeley, CA 94720, U.S.A. bybee@berkeley.edu"}]},{"given":"Ping-Chen","family":"Huang","sequence":"additional","affiliation":[{"name":"Redwood Center for Theoretical Neuroscience, University of California at Berkeley, Berkeley, CA 94720, U.S.A. pingchen.huang@berkeley.edu"}]},{"given":"Christopher J.","family":"Kymn","sequence":"additional","affiliation":[{"name":"Redwood Center for Theoretical Neuroscience, University of California at Berkeley, Berkeley, CA 94720, U.S.A. cjkymn@berkeley.edu"}]},{"given":"Bruno A.","family":"Olshausen","sequence":"additional","affiliation":[{"name":"Redwood Center for Theoretical Neuroscience, University of California at Berkeley, Berkeley, CA 94720, U.S.A. baolshausen@berkeley.edu"}]},{"given":"E. Paxon","family":"Frady","sequence":"additional","affiliation":[{"name":"Neuromorphic Computing Laboratory, Intel Labs, Santa Clara, CA 95054, U.S.A. e.paxon.frady@intel.com"}]},{"given":"Friedrich T.","family":"Sommer","sequence":"additional","affiliation":[{"name":"Redwood Center for Theoretical Neuroscience, University of California at Berkeley, Berkeley, CA 94720, U.S.A."},{"name":"Neuromorphic Computing Laboratory, Intel Labs, Santa Clara, CA 95054, U.S.A. fsommer@berkeley.edu"}]}],"member":"281","published-online":{"date-parts":[[2023,6,12]]},"reference":[{"key":"2023061316474803200_B1","first-page":"315","article-title":"Toward fast reliable communication at rates near capacity with gaussian noise","volume-title":"Proceedings of the IEEE International Symposium on Information Theory","author":"Barron","year":"2010"},{"issue":"1","key":"2023061316474803200_B2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","article-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","volume":"2","author":"Beck","year":"2009","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"2023061316474803200_B3","author":"Clarkson","year":"2023","journal-title":"Capacity analysis of vector symbolic architectures"},{"key":"2023061316474803200_B4","volume-title":"Elements of information theory","author":"Cover","year":"1999"},{"key":"2023061316474803200_B5","first-page":"1986","article-title":"Associative long short-term memory","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Danihelka","year":"2016"},{"issue":"1","key":"2023061316474803200_B6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.3103\/S1060992X21010033","article-title":"Encoding and decoding of recursive structures in neural-symbolic systems","volume":"30","author":"Demidovskij","year":"2021","journal-title":"Optical Memory and Neural Networks"},{"issue":"4","key":"2023061316474803200_B7","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","article-title":"Compressed sensing","volume":"52","author":"Donoho","year":"2006","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023061316474803200_B8","author":"Frady","year":"2021","journal-title":"Computing on functions using randomized vector representations"},{"key":"2023061316474803200_B9","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1145\/3517343.3522597","article-title":"Computing on functions using randomized vector representations (in brief)","volume-title":"Proceedings of the Neuro-Inspired Computational Elements Conference","author":"Frady","year":"2022"},{"key":"2023061316474803200_B10","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1162\/neco_a_01084","article-title":"A theory of sequence indexing and working memory in recurrent neural networks","volume":"30","author":"Frady","year":"2018","journal-title":"Neural Computation"},{"issue":"5","key":"2023061316474803200_B11","doi-asserted-by":"crossref","first-page":"2191","DOI":"10.1109\/TNNLS.2021.3105949","article-title":"Variable binding for sparse distributed representations: Theory and applications","volume":"34","author":"Frady","year":"2023","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"2023061316474803200_B12","author":"Gallant","year":"2022","journal-title":"Orthogonal matrices for MBAT vector symbolic archi-tectures, and a \u201csoft\u201d VSA representation for JSON"},{"issue":"8","key":"2023061316474803200_B13","doi-asserted-by":"publisher","first-page":"2038","DOI":"10.1162\/NECO_a_00467","article-title":"Representing objects, relations, and sequences","volume":"25","author":"Gallant","year":"2013","journal-title":"Neural Computation"},{"key":"2023061316474803200_B14","first-page":"133","article-title":"Vector symbolic architectures answer Jackendoff's challenges for cognitive neuroscience","volume-title":"Proceedings of the Joint International Conference on Cognitive Science","author":"Gayler","year":"2003"},{"key":"2023061316474803200_B15","first-page":"1","article-title":"Wireless on-chip communications for scalable in-memory hyperdimensional computing","volume-title":"Proceedings of the International Joint Conference on Neural Networks","author":"Guirado","year":"2022"},{"issue":"1","key":"2023061316474803200_B16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1111\/j.1551-6709.2010.01149.x","article-title":"Holographic string encoding","volume":"35","author":"Hannagan","year":"2011","journal-title":"Cognitive Science"},{"key":"2023061316474803200_B17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40708-021-00138-0","article-title":"Near-channel classifier: Symbiotic communication and classification in high-dimensional space","volume":"8","author":"Hersche","year":"2021","journal-title":"Brain Informatics"},{"key":"2023061316474803200_B18","first-page":"1","article-title":"Non-orthogonal modulation for short packets in massive machine type communications","volume-title":"Proceedings of the IEEE Global Communications Conference","author":"Hsu","year":"2020"},{"issue":"2","key":"2023061316474803200_B19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.3233\/AIS-2012-0139","article-title":"Collective communication for dense sensing environments","volume":"4","author":"Jakimovski","year":"2012","journal-title":"Journal of Ambient Intelligence and Smart Environments"},{"key":"2023061316474803200_B20","first-page":"358","article-title":"Fully distributed representation","author":"Kanerva","year":"1997","journal-title":"Proceedings of the Real World Computing Symposium"},{"issue":"2","key":"2023061316474803200_B21","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s12559-009-9009-8","article-title":"Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors","volume":"1","author":"Kanerva","year":"2009","journal-title":"Cognitive Computation"},{"issue":"3","key":"2023061316474803200_B22","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1109\/MDAT.2018.2890221","article-title":"Computing with high-dimensional vectors","volume":"36","author":"Kanerva","year":"2019","journal-title":"IEEE Design and Test"},{"key":"2023061316474803200_B23","first-page":"1","article-title":"HDM: Hyper-dimensional modulation for robust low-power communications","volume-title":"Proceedings of the IEEE International Conference on Communications","author":"Kim","year":"2018"},{"issue":"10","key":"2023061316474803200_B24","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1109\/JPROC.2022.3209104","article-title":"Vector symbolic architectures as a computing framework for emerging hardware","volume":"110","author":"Kleyko","year":"2022","journal-title":"Proceedings of the IEEE"},{"key":"2023061316474803200_B25","article-title":"Commentaries on \u201cLearning sensorimotor control with neuromorphic sensors: Toward hyperdimensional active perception\u201d [Science Robotics (2019), 4(30) 1\u201310]","author":"Kleyko","year":"2020"},{"issue":"8","key":"2023061316474803200_B26","doi-asserted-by":"publisher","first-page":"3777","DOI":"10.1109\/TNNLS.2020.3015971","article-title":"Density encoding enables resource-efficient randomly connected neural networks","volume":"32","author":"Kleyko","year":"2021","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"2023061316474803200_B27","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-642-34976-8_15","article-title":"Dependable MAC layer architecture based on holographic data representation using hypedimensional binary spatter codes","volume-title":"Multiple access communications","author":"Kleyko","year":"2012"},{"key":"2023061316474803200_B28","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.procs.2016.07.421","article-title":"Recognizing permuted words with vector symbolic architectures: A Cambridge test for machines","volume":"88","author":"Kleyko","year":"2016","journal-title":"Procedia Computer Science"},{"issue":"6","key":"2023061316474803200_B29","doi-asserted-by":"publisher","first-page":"1250","DOI":"10.1109\/TNNLS.2016.2535338","article-title":"Holographic graph neuron: A bioinspired architecture for pattern processing","volume":"28","author":"Kleyko","year":"2017","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"2023061316474803200_B30","first-page":"1","article-title":"Integer self-organizing maps for digital hardware","volume-title":"Proceedings of the International Joint Conference on Neural Networks","author":"Kleyko","year":"2019"},{"issue":"6","key":"2023061316474803200_B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3538531","article-title":"A survey on hyperdimensional computing aka vector symbolic architectures, Part I: Models and data transformations","volume":"55","author":"Kleyko","year":"2022","journal-title":"ACM Computing Surveys"},{"issue":"9","key":"2023061316474803200_B32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3558000","article-title":"A survey on hyperdimensional computing aka vector symbolic architectures, Part II: Applications, cognitive models, and challenges","volume":"55","author":"Kleyko","year":"2023","journal-title":"ACM Computing Surveys"},{"key":"2023061316474803200_B33","doi-asserted-by":"publisher","first-page":"3675","DOI":"10.1007\/s00521-019-04397-1","article-title":"Autoscaling Bloom filter: Controlling trade-off between true and false positives","volume":"32","author":"Kleyko","year":"2020","journal-title":"Neural Computing and Applications"},{"issue":"12","key":"2023061316474803200_B34","doi-asserted-by":"publisher","first-page":"5880","DOI":"10.1109\/TNNLS.2018.2814400","article-title":"Classification and recall with binary hyperdimensional computing: Tradeoffs in choice of density and mapping characteristic","volume":"29","author":"Kleyko","year":"2018","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"issue":"PP","key":"2023061316474803200_B35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TNNLS.2023.3237381","article-title":"Perceptron theory can predict the accuracy of neural networks","volume":"99","author":"Kleyko","year":"2023","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"2023061316474803200_B36","first-page":"1","article-title":"High-dimensional computing with sparse vectors","author":"Laiho","year":"2015","journal-title":"Proceedings of the IEEE Biomedical Circuits and Systems Conference"},{"issue":"3","key":"2023061316474803200_B37","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.cosrev.2009.03.005","article-title":"Reservoir computing approaches to recurrent neural network training","volume":"3","author":"Lukosevicius","year":"2009","journal-title":"Computer Science Review"},{"issue":"6","key":"2023061316474803200_B38","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1049\/ip-com:20050237","article-title":"Fountain codes","volume":"152","author":"MacKay","year":"2005","journal-title":"IEE Proceedings-Communications"},{"issue":"12","key":"2023061316474803200_B39","doi-asserted-by":"publisher","first-page":"3397","DOI":"10.1109\/78.258082","article-title":"Matching pursuits with time-frequency dictionaries","volume":"41","author":"Mallat","year":"1993","journal-title":"IEEE Transactions on Signal Processing"},{"key":"2023061316474803200_B40","first-page":"1","article-title":"Analyzing the capacity distributed vector representations to encode spatial information","volume-title":"Proceedings of the International Joint Conference on Neural Networks","author":"Mirus","year":"2020"},{"issue":"30","key":"2023061316474803200_B41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1126\/scirobotics.aaw6736","article-title":"Learning sensorimotor control with neuromorphic sensors: Toward hyperdimensional active perception","volume":"4","author":"Mitrokhin","year":"2019","journal-title":"Science Robotics"},{"issue":"6583","key":"2023061316474803200_B42","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1038\/381607a0","article-title":"Emergence of simple-cell receptive field properties by learning a sparse code for natural images","volume":"381","author":"Olshausen","year":"1996","journal-title":"Nature"},{"key":"2023061316474803200_B43","first-page":"3276","article-title":"Associative synthesis of finite state automata model of a controlled object with hyperdimensional computing","volume-title":"Proceedings of the Annual Conference of the IEEE Industrial Electronics Society","author":"Osipov","year":"2017"},{"key":"2023061316474803200_B44","first-page":"2825","article-title":"Scikit-learn: Machine learning in Python","author":"Pedregosa","year":"2011","journal-title":"Journal of Machine Learning Research"},{"key":"2023061316474803200_B45","first-page":"34","article-title":"Holographic recurrent networks","volume-title":"Advances in neural information processing systems","author":"Plate","year":"1992"},{"issue":"3","key":"2023061316474803200_B46","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1109\/72.377968","article-title":"Holographic reduced representations","volume":"6","author":"Plate","year":"1995","journal-title":"IEEE Transactions on Neural Networks"},{"key":"2023061316474803200_B47","author":"Plate","year":"1995","journal-title":"Networks which learn to store variable-length sequences in a fixed set of unit activations"},{"key":"2023061316474803200_B48","volume-title":"Holographic reduced representations: Distributed representation for cognitive structures","author":"Plate","year":"2003"},{"key":"2023061316474803200_B49","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1109\/69.917565","article-title":"Representation and processing of structures with binary sparse distributed codes","volume":"2","author":"Rachkovskij","year":"2001","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"9","key":"2023061316474803200_B50","doi-asserted-by":"publisher","first-page":"2508","DOI":"10.1109\/TCSI.2017.2705051","article-title":"High-dimensional computing as a nanoscalable paradigm","volume":"64","author":"Rahimi","year":"2017","journal-title":"IEEE Transactions on Circuits and Systems I: Regular Papers"},{"key":"2023061316474803200_B51","first-page":"1300","article-title":"Permutations as a means to encode order in word space","volume-title":"Proceedings of the Annual Meeting of the Cognitive Science Society","author":"Sahlgren","year":"2008"},{"key":"2023061316474803200_B52","first-page":"1","article-title":"Randomness in neural networks: An overview","volume":"7","author":"Scardapane","year":"2017","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2023061316474803200_B53","doi-asserted-by":"publisher","first-page":"4523","DOI":"10.1007\/s10462-021-10110-3","article-title":"A comparison of vector symbolic architectures","volume":"55","author":"Schlegel","year":"2022","journal-title":"Artificial Intelligence Review"},{"key":"2023061316474803200_B54","author":"Shwartz-Ziv","year":"2017","journal-title":"Opening the black box of deep neural networks via information"},{"key":"2023061316474803200_B55","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.future.2019.04.010","article-title":"Constructing distributed time-critical applications using cognitive enabled services","volume":"100","author":"Simpkin","year":"2019","journal-title":"Future Generation Computer Systems"},{"key":"2023061316474803200_B56","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.bica.2018.07.002","article-title":"Representing sets as summed semantic vectors","volume":"25","author":"Summers-Stay","year":"2018","journal-title":"Biologically Inspired Cognitive Architectures"},{"key":"2023061316474803200_B57","first-page":"157","article-title":"Collecting performance data with PAPI-C","volume-title":"Tools for high performance computing","author":"Terpstra","year":"2010"},{"key":"2023061316474803200_B58","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1613\/jair.1.12664","article-title":"A theoretical perspective on hyperdimensional computing","volume":"72","author":"Thomas","year":"2021","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"2023061316474803200_B59","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","article-title":"Regression shrinkage and selection via the Lasso","volume":"58","author":"Tibshirani","year":"1996","journal-title":"Journal of the Royal Statistical Society: Series B (Methodological)"},{"key":"2023061316474803200_B60","first-page":"1","article-title":"The hyperdimensional stack machine","volume-title":"Proceedings of Cognitive Computing","author":"Yerxa","year":"2018"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/7\/1159\/2127124\/neco_a_01590.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/7\/1159\/2127124\/neco_a_01590.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T16:48:17Z","timestamp":1686674897000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/35\/7\/1159\/115997\/Efficient-Decoding-of-Compositional-Structure-in"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,12]]},"references-count":60,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,6,12]]},"published-print":{"date-parts":[[2023,6,12]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01590","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2023,6,12]]}}}