超维计算(又称向量符号体系结构)综述，第一部分:模型和数据转换丹尼斯·克莱科、德米特里·拉奇科夫斯基、叶夫根尼·奥西波夫和阿巴斯·拉希米这两个部分的综合调查致力于一个计算框架，最常见的名称是超维计算和向量符号架构(HDC/VSA)。这两个名称都指的是一系列计算模型，这些模型使用高维分布式表示，并依靠其关键操作的代数属性来结合结构化符号表示和矢量分布式表示的优点。HDC/VSA家族中值得注意的模型是张量积表示、全息简化表示、乘加置换、二进制喷溅码和稀疏二进制分布表示，但还有其他模型。HDC/VSA是一个高度跨学科的领域，涉及计算机科学、电子工程、人工智能、数学和认知科学。这一事实使得对该地区进行全面的概述具有挑战性。然而，由于近年来加入该领域的新研究人员激增，对该领域进行全面调查的必要性变得极其重要。因此，在该领域的其他方面中，第一部分调查了重要的方面，例如:HDC/VSA的已知计算模型和各种输入数据类型到高维分布式表示的转换。本调查的第二部分[Kleyko et al., 2021c]致力于应用、认知计算和架构，以及未来工作的方向。这份调查对新人和从业者都有用。CCS Concepts: • Theory of computation → Random projections and metric embeddings; Data structures design and analysis; Bloom filters and hashing; • Computing methodologies → Artificial intelligence; Knowledge representation and reasoning;人工智能、机器学习、超维计算、向量符号架构、分布式表示、数据结构、全息简化表示、张量积表示、加法项的矩阵绑定、二进制空间码、乘-加-置换、稀疏二进制分布式表示、稀疏块码、模块复合表示、全息简化表示的几何模拟HDC/VSA可以克服SRs和LRs关于缺乏语义基础的问题(即，缺乏对象的直接相似性；参见第节2.1.1).HDC/VSA通过其表示中的显式相似性克服了这些问题，因为HV不必以全有或全无的方式来表示相似性。然而，这些承诺带来了设计具体转换的问题，这些转换形成各种组成结构的HV，使得它们的HV之间的相似性将反映底层对象的相似性![]()
![]()
表1:现有HDC/VSA文献的定性评估和调查要素。人工智能(AI)的两种主要方法是符号方法和连接方法。符号方法通过符号及其关系来表示信息。符号AI(替代术语是Good Old-fashion AI，GOFAI)通过对这些符号的处理来解决问题或推断新知识。在另一种连接主义方法中，信息是在一个通常称为神经元的简单计算单元网络中处理的，因此连接主义方法的另一个名称是人工神经网络。本文介绍了一个起源于GOFAI和连接主义交叉点的研究领域的概况，它被称为超维度计算，HDC(这个术语是在[Kanerva, 2009])和向量符号体系结构，VSA(术语引入于[Gayler, 2003]).为了保持一致，避免该地区以外的研究人员产生混淆，我们在提到该领域时将使用HDC/VSA的联合名称。还值得指出的是，可能最有影响力和最著名的(至少在机器学习领域)HDC/VSA模型是全息简化表示Holographic Reduced Representations (HRR)[Plate,2003]因此，这个术语也用于指该地区。然而，出于一致性的原因，我们使用HDC/VSA作为一个通用术语，而在讨论这个特定的模型时，使用全息简化表示。HDC/VSA是一系列计算模型的总称，这些模型依赖于高维随机空间的数学特性，并使用被称为超向量(HVs)的高维分布式表示1)用于数据的结构化(“符号”)表示，同时保持连接主义矢量分布式表示的优点。这为构建人工智能系统开辟了一条充满希望的道路[Levy and Gayler, 2008].很长一段时间，HDC/VSA并没有获得人工智能社区的太多关注。然而，最近情况开始改变，VSA人权发展委员会的势头正在增强。我们将此归因于几个因素的结合，如研究团体成员的传播努力23，机器学习领域的几个成功的工程应用(例如[Sahlgren, 2005], [Rahimi et al., 2019])和认知架构[Eliasmith et al., 2012], [Rachkovskij et al., 2013].当前兴趣背后的主要驱动力是寻找传统(冯·诺依曼)计算范式替代方案的全球趋势，如神经形态和纳米尺度计算，HDC/VSA有望在其中发挥重要作用(参见[Kleyko et al., 2021a]以及其中用于透视的参考文献)。对于新进入该领域的研究人员来说，主要的问题是以前在HDC/VSA方面的工作分散在许多地点和学科中，不容易跟踪。因此，了解该领域的最新发展水平并不容易。因此，在本文中，我们调查HDC/VSA，目的是提供该地区的广泛覆盖，这是目前所缺乏的。虽然调查旨在让更多的受众了解，但不应将其视为“最容易的切入点”。对于尚未接触HDC/VSA的任何人，在阅读本调查之前，我们强烈建议从三篇类似教程的介绍性文章开始[Kanerva, 2009], [Kanerva, 2019]，以及[Neubert et al., 2019].前两者提供了该领域背后的坚实的介绍和动机，而后者侧重于在机器人的特定应用领域的背景下介绍HDC/VSA。如果有人正在寻找该领域的非常简明的高级介绍，而没有太多的技术细节，可以参考[Kanerva, 2014].最后还有一本书[Plate, 2003]全面介绍了两种特定HDC/VSA模型的基本原理(参见2.3.3 和2.3.5).而[Plate, 2003]以这两个具体模式为重点，其中提出的许多方面一般适用于人类发展中心/VSA。据我们所知，以前没有人试图对HDC/VSA进行全面的调查，但有文章概述了HDC/VSA的特定主题。table1 将这次调查的覆盖范围与以前的进行对比1.认知科学文献中常用的另一个指代HVs的术语是“语义指针”Blouw et al., 2016].2.HDC/VSA门户网站。【在线。]可用:https://www.hd-computing.com3.VSAONLINE。网络研讨会系列。【在线。]可用:https://sites.google.com/ltu.se/vsaonline文章(按时间顺序排列)。我们用来表示一篇文章部分地讨论了一个特定的主题，但是要么是从那时起报道了新的结果，要么是没有覆盖所有相关的工作。
本调查的第一部分结构如下。在截面中2，我们介绍了HDC/VSA背后的动机，它们的基本概念，并总结了目前已知的HDC/VSA模型。部分3 介绍各种数据类型到HVs的转换。讨论和结论如下4 和5，分别为。本调查的第二部分[Kleyko et al., 2021c])将涵盖现有应用以及HDC/VSA在认知架构中的使用。最后，由于篇幅限制，有些主题不在本次调查的范围之内。这些主题包括HDC/VSA和其他研究领域之间的联系，以及HDC/VSA的硬件实现。我们计划在另一部作品中讨论这些问题。在本节中，我们描述了导致开发早期HDC/VSA模型的动机(第2.1)，列出它们的组件(第2.2)，现有HDC/VSA模型概述(第节2.3)并讨论了HVs的信息容量(第2.4).2.1动机和基本概念
与人类发展委员会/VSA有关的想法在1980年代末和1990年代初就已经出现[Kanerva, 1988], [Mizraji, 1989], [Smolensky, 1990], [Rachkovskij and Fedoseyeva, 1990], [Plate, 1991], [Kussul et al., 1991a].在这一节中，我们首先回顾表示的类型以及它们的优缺点。然后，我们介绍了分布式表示面临的一些挑战，这些挑战被证明是激励HDC/VSA发展的激励因素。Symbolic representations 符号表示(SRs)是人类的天性，广泛应用于计算机。在SRs中，每个项目或对象都由一个符号表示。这里，我们所说的对象指的是各种性质和复杂性的项目，例如特征、关系、物理对象、场景、它们的类别等。更复杂的符号表示可以由简单的符号表示组成。SRs自然地拥有一个组合结构，允许无限地产生许多命题/符号表达式(参见2.1.2.2 下面)。这是通过使用例如图灵机所展示的规则或程序进行合成来实现的。当然，这一过程受到内存大小的限制，但内存大小可以在不改变系统计算结构的情况下进行扩展。符号表示/系统的一个生动的例子是自然语言，其中大量的单词是由一个小字母表组成的。反过来，有限数量的单词被用来组成无限数量的句子等等。SRs具有全有或全无的显式相似性:相同的符号具有最大的相似性，而不同的符号具有零相似性，因此被称为不相似。为了处理符号结构，需要跟踪边缘和/或匹配基础图的顶点，以例如揭示整个结构或计算相似性。因此，符号模型通常存在缩放问题，因为这种模型中的相似性搜索和推理需要复杂的顺序操作，这很快变得难以处理。在类脑计算的背景下，符号计算的传统实现的缺点是它们需要可靠的硬件[Wang et al., 2004]，因为计算中的任何错误都可能导致致命的错误。总的来说，也不清楚SRs和用它们进行的计算如何在生物组织中实现，特别是考虑到它的不可靠性。2.1.1.2连接主义表示:本地化和分布式:: localist and distributed:在本文中，连接主义被用作与神经网络和类脑计算相关的方法的总称。有两种主要的连接主义表示:本地的和分布式的[van Gelder,1999], [Thorpe, 2003].本地化表示(LRs)类似于SRs，因为每个对象在表示中都存在一个元素。有证据表明LRs可能被用于大脑(所谓的“祖母细胞”)[Quiroga et al., 2005].为了链接lr，可以创建组件之间的连接，对应于SRs中的指针。然而，构建包括已经呈现的对象的组合的组成结构需要分配(潜在地无限数量的)新的附加元素和连接，这在神经生物学上是有问题的。比如代表“abc”、“abd”、“acd”等。需要为它们引入新元素，以及“a”、“b”、“c”、“d”等之间的联系。此外，LRs与SRs一样缺乏足够的语义基础，这可以被认为是表示之间缺乏直接的显式相似性。换句话说，代表不同对象的不同神经元是不相似的，并且估计对象相似性需要额外的过程。分布式表示(DRs)的灵感来自于“全息”表示作为本地表示的替代方案的想法[Hinton et al., 1986], [Thorpe, 2003], [van Gelder, 1999], [Plate, 2006].它们被归因于一种基于将大脑中的信息表示建模为“分布”在许多神经元上的连接主义方法。在DRs中,(有限大小的)一组神经元的状态被建模为向量，其中每个向量分量代表特定神经元的状态。DRs被定义为一种向量表示形式，其中每个对象由向量分量的子集表示，并且每个向量分量可以属于许多对象的表示。这涉及各种复杂对象的(完全分布式)表示，从基本特征或原子对象到由(分层)组合结构表示的复杂场景/对象。在DRs中，如果不知道其他组件的状态，就无法解释表示的单个组件的状态。换句话说，在DRs中，表示的单个组件的语义通常是未定义的，这与LRs不同。为了有用，相似对象的DRs应该是相似的(根据相应向量表示的某种相似性度量；参见第节2.2.2)，从而解决SRs和LRs的语义基础问题。高代表能力。例如，如果一个对象由D维向量的M个二进制分量表示，那么可表示对象的数量等于组合的数量，这与LRs的D/M相反； •直接访问对象的表示。可以直接处理组合结构的组合DR，而不像在SRs中那样跟踪指针，也不像在LRs中那样跟踪组件之间的连接；•相似性的显式表示。相似的对象具有相似的表示，可以通过有效计算的向量相似性度量(例如，点积、闵可夫斯基距离等)立即进行比较。);•丰富的语义基础，这是由于基于特征的表示的直接使用，以及在其矢量表示中表示特征本身的相似性的可能性；•对于许多类型的DRs——恢复对象的原始表示的能力；•除了神经生物学的合理性之外，在噪音、故障和不确定性存在的情况下工作的能力。![]()
让我们考虑早期DRs面临的几个挑战，称为“叠加灾难”，例如[von der Malsburg,1986], [Rachkovskij and Kussul, 2001].在更高的层次上，由“系统性”的需求[Fodor and Pylyshyn, 1988]，以及更晚，为了快速合成[Jackendoff, 2002].这些挑战导致了通过引入“绑定”操作使DRs“结构敏感”的必要性(第2.2.3.2).人们认为，由于叠加突变，连接主义表示不能表示层次组合结构，叠加突变表现为丢失关于结构中对象排列的信息，见von der Malsburg, 1986], [Rachkovskij and Kussul, 2001], [Rachkovskij, 2001]供讨论和参考。在最简单的情况下，让我们激活对应于“a”和“b”的二元LR（左右？）元素，然后激活对应于“b”和“c”的二元LR元素。如果我们想同时表示“a”和“b”，以及“b”和“c”，我们激活所有三个表示:“a”、“b”、“c”。然而，现在“a”与“b”在一起，“b”与“c”在一起的信息丢失了。例如，相同的“a”、“b”、“c”激活可以通过“a”和“c”以及单个“b”来获得。如果“a”、“b”、“c”用分布式模式表示，也会出现同样的情况。在[Fodor and Pylyshyn, 1988]，对连接主义的批评与[Hinton et al., 1986].作者声称，联结主义缺乏生产力、系统性、组合性和推理的连贯性，而这些都是用SRs操作的系统所固有的。他们对这些直觉上吸引人的问题的定义是相当模糊和相互关联的，他们的批评局限于作者为他们的批评选择的早期特定的联结主义模型。因此，我们重申这些挑战，如[Plate, 2003]:•组成、分解和操作:元素是如何组成结构的，元素是如何从结构中提取出来的？可以使用DRs操作这些结构吗？•生产率:组成元素的一些简单规则可以产生大量不同的可能结构。如果一个系统是由相同的元素和关系组成的，那么它应该能够表示不同于它以前遇到过的任何结构吗？•系统性:DR允许过程对对象的结构敏感吗？这些过程在多大程度上独立于组成结构中元素的同一性？2.1.2.3Jackendoff对连接主义的挑战；Jackendoff对连接主义提出了四个挑战Jackendoff, 2002]，另见[Gayler, 2003]进行HDC/VSA治疗。原则上，它们与认知有关，但尤其与语言有关。总的来说，问题是如何神经例示组成结构的快速构建和转换。•挑战1。绑定问题:观察到语言表示必须使用组合表示，考虑到顺序和出现的组合。例如，相同的单词以不同的顺序和组合将产生不同的句子。•挑战2。问题之二:同一个对象的多个实例是如何实例化的？例如，如何将“小星星”和“大星星”实例化，使它们都是星星，但又可以区分？•挑战3。变量问题:关注类型化变量。人们应该能够用变量(例如，关系的名称)和值(例如，关系的自变量)来表示模板或关系。•挑战4。工作记忆和长期记忆中的结合:同一结合的表征在不同类型的记忆中应该是相同的。换句话说，挑战在于工作记忆和长期记忆之间界限的透明度。有人认为，语言任务需要在工作记忆和长时记忆中实例化相同的结构，这两种实例化在功能上应该是等价的。上面提出的挑战清楚地表明，组成结构的适当表示需要保存关于它们的分组和顺序的信息。例如，在SRs中，可以使用括号和符号顺序来实现这一点。出于同样的目的，DRs中需要某种绑定机制(a` la "分组括号)。DRs中绑定的方法之一是基于组成激活的时间同步[Milner,1974], [von der Malsburg, 1986], [Shastri and Ajjanagadde, 1993], [Hummel and Holyoak, 1997].尽管这种机制在单个组合级别上可能是有用的，但是它用多层次来表示组合结构的能力是有问题的，因为它需要许多时间步骤和复杂的“编排”来表示组合结构。另一个主要问题是，这种时间表征不能立即储存在长期记忆中。消除这些问题的另一种绑定方法是在HDC/VSA中使用的所谓的联合编码方法。它的前身是[Hinton, 1981]来表示分布模式的活动单元以及张量积的各种组合[Mizraji, 1989], [Smolensky, 1990]，但是，这增加了表示的维数(请参见一节中的详细信息)2.3.2).在HDC/VSA中，绑定操作不改变DRs的维度，并且通过类似分量乘法的操作保留分组信息。此外，它不需要任何培训。这是HDC/VSA业务性质的必然结果。重要的是，用于形成利用绑定的组合结构的dr的方案产生对于相似对象而言相似的dr(即，它们考虑了对象元素的相似性、它们的分组以及在不同层级的顺序)。总之，开发HDC/VSA的主要动机是结合早期DRs和SRs的优点，同时避免它们的缺点，以追求更有效的信息处理，并最终获得更好的人工智能系统。目标之一是解决传统连接主义表示所面临的上述挑战。下面介绍的HDC/VSA模型的特性允许在不同程度上解决这些挑战。2.2结构敏感的分布式表示
当设计基于HDC/VSA的系统时，通常为给定的问题定义一组最基本的对象/项目/实体/概念/符号/标量，并给它们分配HV，这被称为原子HV。分配原子HV的过程通常被称为映射、投影、嵌入、形成或转换。为了保持一致，我们将使用转换transformation这个术语。对于给定的问题，我们需要选择对象的原子表示，使得对象表示之间的相似性对应于我们关心的属性。其他(组合)对象的HV由原子HV形成(参见2.2.4).顾名思义，原子HV是高维向量。HV分量的值可以是二进制数、实数或复数。在HDC/VSA的早期，大部分作品都集中在象征问题上。在使用符号的情况下，人们可以很容易地想象出许多问题，其中一个合理的假设是符号根本不相关。因此，它们的原子HV是随机生成的，并且被认为是不相似的，即，它们的预期相似性值被认为是“零”。另一方面，在许多问题中，完全随机地分配原子HV不会导致所设计系统的任何有用行为，参见第节3.2。![]()
如上所述，在HDC/VSA中，从某种分布产生的随机独立HV用于表示被认为是独立和不相似的对象。例如，具有来自集合0，1的分量的随机生成的二进制HVs，对于密集二进制表示，1分量的概率为P1 = 1/2[Kanerva, 2009]或稀疏二进制表示[Rachkovskij, 2001或者具有固定数量的M << D个随机激活的组件。这种随机HV类似于SRs中的“符号”。然而，在Sr中引入新的符号或在LRs中引入新的节点需要改变表示的维度，而在HDC/VSA中，它们只是作为固定维度的新HV而被引入。因此HDC/VSA可以容纳具有D维HV的N个符号，使得N >> D。这是因为在高维空间中，随机选择的HV彼此伪正交。这种数学现象被称为测度的集中Ledoux, 2001].这种现象的特殊性质是随着HVs维数的增加，伪正交收敛到精确正交。这有时被称为“维度的祝福”Gorban and Tyukin, 2018].图。1 提供了双极HVs情况的直观说明。
![]()
图1:双极随机HV之间测量现象的集中。这些线对应于HVs的不同维度的余弦相似性的概率密度函数。将正态分布与2000个随机选择的HV的成对相似性进行拟合。如果对象之间的相似性很重要，那么HV是以这样一种方式生成的，即它们的相似性表征了对象之间的相似性。HV之间的相似性通过标准向量相似性(或距离)度量来测量。![]()
不改变HV维度的叠加和绑定操作是特别令人感兴趣的，因为它们允许将相同的操作应用于它们的结果HV。但是请注意，一些应用程序可能需要改变表示的维度。2.2.3.1 Superposition 叠加:叠加是用于形成表示几个HV的HV的最基本操作。类似于HVs所代表的神经模式的同时激活，这可以被建模为二进制HVs的析取或实值HVs的相加。请参见第节中特定实现的更多示例2.3。在HDC/VSA中，这种操作有几种名称:捆绑、叠加和相加。由于其直观的含义，下面，我们将使用术语叠加。最简单的无约束叠加(表示为s)就是:![]()
其中f()是限制s的值的范围的函数。下面，当暗示某种标准化时，我们也将使用括号。例如，在密集二进制/双极性HV的情况下，使用通过多数规则/符号函数对分量进行二进制化。
在稀疏二元HV的情况下，它们的叠加增加了合成HV的密度。因此，存在“稀释”合成HV并保持稀疏性的操作。叠加后，合成HV与其输入HV相似。此外，HV的叠加仍然与每个HV相似，但是相似性随着更多HV叠加在一起而降低。这可以被看作是一种非结构化的和附加的相似性保持。 如上所述，单独的叠加操作导致叠加突变(由于其关联特性)，即，在叠加的递归应用期间，关于初始对象的组合的信息丢失。为了表示组成结构，需要解决这个问题。在HDC/VSA中使用绑定操作(当没有指定特定实现时表示为)作为解决方案。有两种类型的绑定:通过类似乘法的运算和通过置换运算。 乘法绑定
当两个或多个HV应该绑定在一起时，在不同的HDC/VSA模型中使用类似乘法的操作来实现绑定操作。类似乘法的绑定操作的例子是二进制HV的合取或实值HV的分量式乘法。请参考第节2.3 特定HDC/VSA模型的具体实现。[中的图1Schlegel et al., 2020]还介绍了最常用的乘法绑定的分类。将几个输入HV绑定在一起后获得的HV取决于所有输入HV。相似的输入HV产生相似的约束HV。然而，保持相似性的方式(通常)不同于叠加操作的方式[Plate, 2000], [Rachkovskij, 2001].我们将在第2节详细讨论这一方面2.2.3.3。在许多情况下，需要一个操作来反转绑定操作的结果。此操作称为解除绑定或释放(表示为)。它允许恢复结合的HV [Widdows and Cohen, 2015], [Gosmannand Eliasmith, 2019]，例如:
![]()
这里，只有两个HV的绑定用于演示目的。一般来说，许多HV可以相互绑定。请注意，当取消绑定操作应用于HV的叠加时，结果将不会完全等于原始绑定HV。它还将包含串扰噪声；因此，在解除绑定操作之后通常会有一个清理过程(参见第节)2.2.5)以获得原始绑定HV。在某些模型中，绑定操作是自逆的，这意味着解除绑定操作与绑定操作相同。我们将在第节中详细说明如何在不同的模型中实现解绑定操作2.3。排列装订
另一种类型的HV绑定是通过置换，这可能对应于例如对象的某个位置。我们把置换在HV上的应用记为ρ(a)；如果将相同的排列应用I次作为ρi(a ),则相应的倒数为ρI(a)。请注意，置换后的HV与原始HV不同。然而，部分置换的使用[Kussul and Baidyk, 2003], [Cohen and Widdows, 2018]允许保留一些相似性(参见3.4.1).置换运算可以通过与相应的置换矩阵相乘来实现。置换运算的这种实现与[Gallant and Okaywe, 2013]，其中矩阵乘法也用于通过给每个位置分配一个随机矩阵来进行位置绑定(第2.3.4).对于排列绑定，通过逆排列来实现解绑定。在实践中，通常使用置换的一个特例——循环移位，因为它非常容易实现。在HDC/VSA中使用循环移位进行位置绑定最初是在[Kussul and Baidyk, 1993]用于表示2D结构(图像)和1D结构(序列)。接下来，使用排列来表示[Rachkovskij, 2001].本着类似的精神，排列被用于[Plate, 1995a], [Jones and Mewhort, 2007]以避免循环卷积的交换性(类似乘法的绑定操作的实现)。后来[Kanerva, 2009]引入了一个原语，用于在复合HV中表示一个序列，使用相同固定排列的多个应用来表示序列中的一个位置。这个原语通过在文本中的应用而得到推广[Sahlgren et al., 2008], [Joshi et al., 2016].对于叠加运算，任何输入HV对合成HV的影响是相同的，与其他输入HV无关。在绑定中，任何输入HV对结果的影响取决于所有其他输入HV。此外，叠加和绑定操作以不同的方式保持相似性。有一种非结构化相似性，它是合成HV与用作操作输入的HV的相似性。叠加操作保留了合成HV与每个叠加HV的相似性，也就是说，它保留了非结构化相似性。例如，d = a + b类似于a和b。事实上，给定一些叠加HVs性质的假设，就有可能分析HVs的信息容量(参见第2.4 详情)。绑定操作的大多数实现不保持非结构化的相似性。然而，它们保留了结构上的相似性，也就是说，相互结合的HV的相似性。让我们考虑两个i.i.d .随机HVs和b；d = a b与d′= a′b′相似如果a与a′相似，b与b′相似。因此，绑定操作的大多数实现以乘法方式保持结构化的相似性。当a和b独立，以及a′和b′独立时，那么d到d′的相似度等于a到a′和b到b′的相似度的乘积。例如，如果a = a’，则d到d’的相似性将等于b到b’的相似性。如果a与a’不相似，由于相似性保持的乘法方式，d将与d’不相似，而不管b和b’之间的相似性。这种类型的相似性不同于叠加HVs的非结构化相似性:即使b与c不相似，d = a + b仍将与e = a + c相似。
如第节所述2.1.1.2组成结构由对象形成，其中对象可以是原子的或组成的。原子对象是组成结构中最基本的(不可约的)元素。更复杂的组合对象由原子对象和更简单的组合对象组成。这种结构可以被认为是部分-整体的层次结构，其中较低级别的部分被递归地组合以形成较高级别的整体(参见，例如，部分中的图形的例子3.5.2).在HDC/VSA中，使用元素的HV以及上面介绍的叠加和绑定操作，将组成结构转换成它们的HV。如中所述2.1.3通常要求相似的组成结构由相似的HV表示。从其组成HV中恢复原始表示的可能性(我们将在下一节中描述)可能是一个额外的要求。在截面中3 下面，我们将回顾形成原子HV和组成HV的许多方法。给定一个组成HV，通常希望找到构建它的特定输入HV。我们将实现这一点的过程称为恢复。这个过程也被称为解码、重建、恢复、分解、解析和检索。为了恢复，有必要知道形成HV的(一些)输入HV的集合。该集合通常被称为字典、码本、清除存储器或项目存储器4。在其最简单的形式中，项目存储器只是一个显式存储HVs的矩阵，但是它可以被实现为例如内容可寻址关联存储器[Stewart et al.,2011].此外，最近的工作表明[Schmuck et al., 2019], [Kleyko et al., 2021b], [Eggimann et al., 2021没有必要总是明确地存储项目记忆，因为它可以很容易地重新物质化。此外，采收需要关于组成HV的结构的知识，即关于用于形成给定HV的操作的信息(参见下面的例子)。4.在人类发展中心/VSA的范围内,[Plate, 1991项目记忆一词是在[Kanerva, 1998].大多数HDC/VSA模型产生的合成HV与输入HV不相似，这是由于它们的绑定操作的特性。因此，为了恢复组成HV中涉及的HV，使用解绑定操作(第2.2.3.2 以上)通常是必需的。如果在形成合成HV时使用叠加操作，则在解绑定之后，所获得的HV将是要恢复的输入HV的有噪声版本(在仅使用绑定操作来形成合成HV的情况下，可以获得无噪声版本)。因此，在恢复的最后阶段使用“清除”过程，即，在项目存储器中搜索与噪声查询HV最相似的HV。对于代表有限大小的组成结构的HVs，理论上可以保证精确回收[Thomas et al., 2021].![]()
在更复杂的设置中，不知道输入HV是a、b、c、d，但是项目存储器中的HV是![]()
已知。因此，我们一个接一个地取出这些HV，重复上面的操作。恢复过程中可能的最后一步是从重建的HVs重新计算组成HV。重新计算的组成HV应与原始组成HV相匹配。注意，在m个HV被绑定而不是仅仅成对绑定的情况下，恢复过程变得更加复杂。如果已知其他m1 HVs，则很容易恢复绑定中使用的HV之一。它们可以简单地不受组成HV的约束。
当绑定中使用的其他HV未知时，找到用于绑定的HV的最简单方法是计算与来自项目存储器的HV的所有可能绑定的相似性。这种搜索的复杂性随着m成指数增长。然而，最近有一项工作[Kent et al., 2020], [Frady et al., 2020]提出了一种称为谐振器网络的机制来解决这个问题。2.3HDC/VSA模型
表2:HDC/VSA模型汇总。每个模型都有自己的原子HV和操作，用于绑定和叠加，以及相似性度量。
![]()
本节概述了各种HDC/VSA模型。对于每一个模型，我们都提供了所采用的HVs的格式以及第节中介绍的基本操作的实现2.2.3 以上。桌子2 提供了模型的摘要(另请参见[Schlegel et al., 2020])5。在向读者展示每种HDC/VSA模型的细节之前，有必要对其多样性的本质进行评论，并使读者能够凭直觉选择最适合实际用途的模型。当前HDC/VSA模型的多样性是独立研究小组和个体研究人员对主要矢量符号范式进行进化发展的结果。最初，多样性来自于不同的初始假设、神经生物学灵感的变化以及发起人的特定数学背景。因此，从历史的角度来看，选择最佳模型的候选人的问题是不适定的。最近的工作[Schlegel et al., 2020]开始在模型之间进行系统的实验比较。我们强调在这个方向上进一步研究的重要性，以促进对给定问题有意识地选择一个或另一个模型，并将HDC/VSA提高到成熟工程学科的水平。5.注意，表中没有指定通过置换运算的绑定。这是因为它可以在任何模型中使用，即使它最初并没有被提议成为模型的一部分。在这里，我们仅限于指定不同模型的细节，但参见，例如[Schlegelet al., 2020]查看表中七种不同型号的对比2 (该工作不包括GAHRR、MCR和TPR模型)及其一些变体(HRR 2个，MAP 3个，SBDR 2个)。然而，使用目标计算硬件视角，此时已经可以对不同模型的使用进行优先级排序。非常规计算硬件的最新发展旨在提高人工智能应用中传统冯诺依曼架构的能效。各种非常规硬件平台(参见第4.3)在超越当前标准的能效和运行速度方面做出了巨大承诺。独立于计算硬件的类型，任何HDC/VSA模型都可以被视为算法层的抽象，因此可以用于设计计算原语，然后可以使用不同的模型将其映射到各种硬件平台[Kleyko et al., 2021a].在接下来的小节中，我们将详细介绍目前已知的HDC/VSA模型。2.3.2张量积表示Tensor Product Representations张量积表示模型(简而言之，TPR模型或简称TPR)是HDC/VSA中最早的模型之一。TPR模型最初是由Smolensky在[Smolensky, 1990].然而，值得注意的是,[Mizraji, 1989], [Mizraji, 1992]但却很少受到研究界的关注。原子HV是从欧几里得单位球S(D1)中均匀随机选择的向量。绑定操作是HVs的张量积(广义外积)。因此，约束HV的维度随着它们的数量呈指数增长(例如，2个约束HV具有维度D2，3个约束向量具有维度D3，等等)。向量不需要具有相同的维数。这指出了另一个重要的注意事项，即TPR模型可能或可能不被归类为HDC/VSA模型，这取决于表示的固定维度是否被认为是HDC/VSA模型的强制属性。叠加是通过(张量)加法实现的。由于维数增加，绑定操作的递归应用具有挑战性。合成张量也依赖于HV出现的顺序。结合相似的HV将导致相似的张量。通过采用组成结构的张量积表示并从中提取感兴趣的HV来实现解绑。对于线性无关HV，精确的解绑是通过张量乘以解绑HV(s)来完成的。未绑定HV被获得为矩阵的逆矩阵的行，其中原子HV在列中。使用原子HV而不是未绑定HV来完成近似未绑定。如果原子HVs是正交的，这将导致精确的解束缚。虽然没有指定相似性度量，但我们假设它是simcos/distEuc。2.3.3全息简化表示Holographic Reduced Representations全息简化表示模型(HRR)是由Plate在20世纪90年代早期开发的Plate, 1991], [Plate,1994], [Plate, 1995a].HRR模式的灵感来自斯摩棱斯基的TPR模式[Smolensky, 1990]和辛顿的“简化表述”[Hinton, 1990].注意，由于语义指针架构统一网络中HRR的使用[Elia-smith, 2013]，有时HRR模型也被称为语义指针架构(SPA)。关于HRR最详细的信息来源是普拉特的书Plate, 2003].在HRR，用于表示不同对象的原子HV是实值的，并且它们的分量是从均值为0且方差为1/D的正态分布中独立生成的。对于大的D，欧几里德范数接近1。绑定操作在两个HV(a和b)上定义，并通过循环卷积实现:![]()
循环卷积乘以范数，并保留输入HVs的单位范数。界限HV与输入HVs不相似。然而，相似输入HV的界限HV是相似的。解除绑定是通过绑定HV与输入HV之一的循环相关来完成的。结果会产生噪音，因此需要一个清理程序(参见第2.2.5)是必需的。在[Gosmann and Eliasmith, 2019]以获得绑定操作的另一种实现，称为向量导出转换绑定(VTB)。据称其更适合在尖峰神经元中实施，并被证明可恢复序列的HVs(用来自[Recchia et al., 2015])优于循环卷积。叠加操作是分量相加。通常，在加法之后使用归一化来保持合成HVs的单位欧几里德范数。在HRR，叠加和束缚运算都是可交换的。相似性度量是simdot或simcos。2.3.4加法项的矩阵绑定Matrix Binding of Additive Terms在矩阵约束的附加条款模型(MBAT) [Gallant and Okaywe, 2013Gallant和Okaywe提出了通过矩阵-向量乘法来实现绑定操作。[Plate, 2003].通常，如果需要，它可以改变结果HV的维数。![]()
此绑定的属性类似于大多数其他模型(HRR、MAP和BSC)的属性。特别是，相似的输入HV将导致相似的约束HV。约束HV与输入HV不相似(这一点在这里尤其明显，因为甚至HV的维度也会改变)。相似性度量是distEuc或simdot。叠加是一种分量相加，可以归一化。解除绑定可以使用角色矩阵的(伪)逆矩阵(或正方形矩阵的逆矩阵，保证用于正交矩阵，如[Tissera and McDonnell, 2014]).为了检查特定HV是否存在于由矩阵乘法绑定的HV的总和中，该HV应该乘以矩阵，并且应该计算所得HV的相似性，并将其与相似性阈值进行比较。2.3.5傅立叶全息简化表示 Fourier Holographic Reduced Representations傅里叶全息简化表示模型(FHRR) [Plate, 1994], [Plate, 2003]是由Plate作为受HRR启发的模型引入的，其中HVs的分量是复数。原子HV是复值随机向量，其中每个向量分量可以被视为独立于(0，2π)上的均匀分布随机选择的角度(相量)。通常，使用每个分量的单位量级(单位HVs)。相似性度量是角度差的余弦和的平均值。绑定操作是分量式复数乘法，通常称为哈达玛乘积。解绑定通过与HV共轭绑定来实现(分量角度减法模2π)。净化程序的使用与HRR相似。叠加是一种分量式的复数加法，其后可以是幅度归一化，使得所有分量都具有单位幅度。2.3.6二元喷溅代码Binary Spatter Codes二元飞溅代码模型(BSC)6 是由卡内瓦在20世纪90年代中期在一系列论文中提出的[Kanerva, 1994], [Kanerva, 1995], [Kanerva, 1996], [Kanerva, 1997].如[Plate, 1997]，BSC模型可以被视为FHRR模型的特例，其中角度被限制为0°和π。在BSC中，原子HV是由0，1组成的稠密二元HV。叠加是分量相加，被阈值化(二进制化)以在合成HV中获得大约相等密度的1和0。这种运算通常被称为多数法则或多数和。它根据被加数中的0或1的数量是否更高以及例如随机地中断联系，为每个分量选择0或1。为了实现确定性的多数法则，通常会指定一个固定的随机HV，当被加数为偶数时，它会包含在叠加中。另一种方法是对第一个和最后一个被加数的邻近部分使用异或运算来打破平局Hannagan et al.,2011].
绑定是一个组件式的异或(XOR)。约束HV与输入HV不相似，但两个相似输入HV的约束HV相似。解除绑定操作也是XOR。清理程序的使用类似于上述模型。相似性度量是distHam。2.3.7乘加置换Multiply-Add-PermuteGayler提出的乘加置换模型Gayler, 1998]类似于BSC。在MAP模型中，原子HV是具有来自1，1的分量的密集双极HV。这比最初提出的[ 1，1]中的实值部分更常用。
绑定是组件式乘法。界限HV与输入HVs不相似。然而，两个相似输入HV的结合HV是相似的。解绑定也是组件式乘法，对于两个绑定输入HV的情况，需要知道绑定HV和其中一个输入HV。叠加是分量相加。叠加的结果可以保持原样，使用欧几里德范数归一化，或者用符号函数二进制化为1，1，其中0分量的关系应该随机断开(但是对于特定的输入HV集是确定的)。规范化的选择取决于用例。相似性度量是simdot或simcos。
2.3.8稀疏二进制分布式表示Sparse Binary Distributed Representations稀疏二进制分布式表示模型(SBDR) [Rachkovskij et al., 2013]，也称为二进制稀疏分布码[Rachkovskij, 2001], [Rachkovskij and Kussul, 2001]是作为联想-投射神经网络的一部分出现的Kussul et al., 1991a](参见第节3.2.2 在本调查的第二部分[Kleykoet al., 2021c]).下面，我们提供一些关于SBDR的两个版本的基本块的细节:合取-析取和上下文相关的细化。2.3.8.1合取-析取:Conjunction-Disjunction合取-析取是最早的HDC/VSA模型之一。它使用原子HVs的二进制向量[Rachkovskijand Fedoseyeva, 1990].HVs的组件式连接被用作绑定操作。HVs的分量析取被用作叠加运算。这两种基本操作都是为两个或多个HV定义的。两种操作6.这个缩写在最初的出版物中没有使用，但我们在这里使用它是为了与后来的文献保持一致。产生与其来源的HVs相似的HVs。也就是说，绑定HV类似于输入HVs，不同于大多数其他已知的绑定操作，除了上下文相关的细化(见下文)。如果两个基本操作的输入HV相似，则它们产生的HV相似。然而，相似性保持的种类是不同的，参见[Rachkovskij and Kussul, 2001].这些运算是可交换的，因此结果HV不依赖于输入HV出现的顺序。这可以通过使用例如置换HVs来容易地改变，其中一些随机置换用于表示顺序。合成HV中1分量的概率可以由输入HV中1分量的概率来控制。稀疏HVs允许使用高效的算法，如倒排索引或自动联想记忆来进行相似性搜索。因为与输入HV的密度相比，合取降低了结果HV的密度，所以它实际上是[Hinton, 1990].同时，这种绑定的递归应用导致HVs的所有组件都被设置为零。然而，析取叠加增加了1分量的数量。因此，这些操作可以用来相互补偿(在一定程度上；见下一节)。合取-析取的修改版本保留了合成HV中1分量的密度，如以下子部分所示。2.3.8.2上下文相关细化:Context-Dependent ThinningRachkovskij和Kussul提出的上下文相关细化(CDT)过程[Rachkovskij and Kussul,2001]既可以被认为是绑定操作，也可以被认为是叠加和绑定的组合。它在20世纪90年代就已经使用了[Rachkovskij and Fedoseyeva, 1990], [Kussul and Rachkovskij, 1991], [Kussul et al., 1991b], [Kussulet al., 1991a]称为“标准化”,因为它近似地保持了合成HV中1-分量的期望密度。然而，这种密度也决定了结合的“程度”或“深度”,如[Rachkovskijand Kussul, 2001].CDT程序实现如下。首先，m个输入二进制HV通过分量析取叠加为:![]()
其中ρk表示第k个随机排列。得到的HV的密度取决于置换-析取T的数量。如果使用许多置换-析取，我们最终从第一级得到HV，即，没有输入HV的绑定。CDT程序的描述版本被称为“加法”。在[Rachkovskij and Kussul, 2001].CDT过程保留了关于被绑定在一起的HV的信息。所以合成HV可以和其他HV“作为一个整体”绑定。CDT过程是可交换的。它是为多个输入HV定义的。和合取-析取一样，CDT过程保留了非结构化和结构化的相似性。注意，对于SBDR，不需要解除绑定，因为绑定HV类似于输入HVs。然而，通过重复结合HV与一些输入HV的结合，在SBDR中存在类似的解结合。2.3.9稀疏分组码Sparse Block CodesLaiho等人提出的稀疏分组码模型(SBC)背后的主要动机[Laiho et al., 2015], [Fradyet al., 2021b]，是使用稀疏二进制HVs，如在SBDR，但是具有绑定操作，其中绑定HV与输入HVs不相似(与SBDR相反)。类似于SBDR，SBC模型中的原子HV是稀疏的，并且是二进制的，分量从0，1开始。然而，HV具有附加结构。HV被划分成大小相等的块(HV的维数是块大小的倍数)。在每个块中，只有一个非零分量，即每个块中的活动最大程度地稀疏，如在Potts关联存储器中，参见，例如[Gritsenko et al., 2017].
在SBC中，绑定操作是为两个HV定义的，并通过循环卷积实现，循环卷积按块应用。解除绑定是通过绑定HV与输入HV之一的逐块循环相关来完成的。叠加运算是一种分量相加。如果组合HV将被用于绑定，则可以通过仅保留每个块中具有最大幅度的分量之一有效来将其二进制化。如果有几个分量具有相同的最大幅度，则可以做出确定性的选择(例如，可以选择具有最大位置号的分量)。相似性度量是simdot或simcos。2.3.10模块化复合表示Modular Composite Representations模块化复合表示模型(MCR) [Snaider and Franklin, 2014]与FHRR、BSC和SBS有一些相似之处。原子HVs的分量是从某个有限范围(表示为r)均匀抽取的整数，这是MCR模型的参数。绑定操作被定义为基于组件的模加法(模值取决于范围限制)，它推广了BSC中用于绑定的XOR。绑定属性与大多数其他模型相似。解绑定操作是组件式模减法。相似性度量是曼哈顿距离的变体[Snaider and Franklin, 2014]:![]()
叠加操作类似于FHRR。整数被解释为单位圆上的离散角度。首先，对于每个分量叠加相量(即，执行向量相加)。第二，通过将幅度设置为1并将相位设置为对应于来自定义范围的整数的最接近的相位，来归一化叠加的结果。2.3.11全息简化表示的几何模拟 Geometric Analogue of Holographic Reduced Representations顾名思义，全息简化表示模型(GAHRR)的几何模拟[Aerts et al.,2009](由Aerts、Czachor和De Moor提出)是作为HRR的替代模型开发的。一个早期的提议是BSC的几何模拟[Aerts et al., 2006].主要的想法是根据几何代数来重新表述HRR。绑定操作是通过几何积(外积的推广)实现的。叠加操作是分量相加。到目前为止，GAHRR主要是一个有趣的理论成果，因为它相对于概念上更简单的模型的优势不是特别清楚，但它可能在未来变得更相关。对GAHRR感兴趣的读者可以参考原始出版物。该模型的介绍见[Aerts and Czachor, 2008], [Aerts et al., 2009], [Patyk-Lonska, 2010], [Patyk-Lonska et al., 2011b]，用GAHRR表示数据结构的例子在[Patyk-Lonska, 2011b]和一些将GAHRR与其他HDC/VSA模型进行比较的实验在[Patyk-Lonska, 2011a], [Patyk-Lonska et al.,2011a].2.4HVs的信息容量
一个有趣的问题是，可以在HVs的叠加中储存多少信息，这个问题经常被这个领域的新来者提起。这个值称为HVs的信息容量。通常假设叠加态的原子HV是随机的，并且彼此不同。换句话说，人们可以将这种叠加视为表示例如一组符号的HV。一般而言，容量取决于参数，例如项目存储器中的符号数量(表示为N)、HV的维数(D)、叠加操作的类型以及被叠加的HV的数量(m)。容量的早期结果见[Plate, 1994], [Plate, 2003].关于BSC、MAP和MBAT中二元/双极HVs的一些想法也在[Kleyko et al., 2017], [Gallant and Okaywe, 2013].对SBDR的容量进行了分析Kleyko et al., 2018].对不同HDC/VSA模型(以及某些类型的递归神经网络)能力的最一般和最全面的分析最近在[Frady et al., 2018b].能力理论的核心思想[Frady et al., 2018b]可以由下面的场景来说明，当要恢复的HV包含来自项目存储器的有效HV和来自合成HV的一些其他元素的串扰噪声(例如，来自角色填充绑定，参见第3.1.3).从统计学上讲，我们可以把从项目记忆中恢复正确的原子HV的问题看作是一个具有两个正态分布的检测问题:击中和拒绝；其中hit对应于正确原子HV的相似性值(例如，simdot)的分布，而reject是所有其他原子HV的分布(假设所有HV都是随机的)。每个分布的特征在于其相应的均值和标准差:分别为h & σhand r& σr。给定h、σh、r和σr的值，我们可以根据下式计算检索正确原子HV的预期精度(pcorr ):![]()
其中φ(x)是累积高斯函数，N表示项目存储器的大小。图。2描述了从其组成HV中检索序列元素的准确性(参见第3.3)适用于三种HDC/VSA型号:BSC、MAP和FHRR。精度是凭经验或用(14).正如我们所看到的，容量理论(14)完美预测预期精度。能力理论[Frady et al., 2018b]最近已经被扩展到预测HDC/VSA模型在分类任务中的准确性[Kleyko et al., 2020c].[Thomas et al., 2021]提出了从人类视觉系统中完美检索集合和序列的界限。近期作品[Mirus et al., 2020], [Schlegel et al., 2020]报告了对HVs容量的实证研究。这些结果中的一部分可以使用容量理论通过分析获得。此外，[Summers-Stayet al., 2018], [Frady et al., 2018b], [Kim, 2018], [Hersche et al., 2021]阐述了恢复信息的方法图2:对于三个HDC/VSA模型，D = 256，N = 64，从HVs恢复序列的分析和经验精度相对于序列长度。报道的经验准确度是用随机初始化的项目记忆进行5次模拟的平均值。从超出项目存储器中的标准最近邻搜索的合成HVs，达到高达1.2比特/分量的容量Hersche et al., 2021].上面的工作集中在单个HV用于存储信息的情况，但是正如在[Danihelka et al., 2016]如果使用冗余存储，可以改进HVs的解码。如上所述，SRs和LRs的相似性是全有或全无:相同的符号被认为是最大相似的，而不同的符号被认为是不相似的。另一方面，由符号组成的结构(如序列、图形等)的相似性。)通常使用计算量大的过程来计算，例如编辑距离。HV是矢量表示，因此依赖于简单的矢量相似性度量，可以按分量计算并立即提供结果相似性值。这也涉及组成结构的相似性。因此，例如，关系结构的相似性，考虑到它们的元素、它们的分组和顺序的相似性，可以通过测量它们的HV的相似性来估计，而不需要诸如跟随边或匹配底层图的顶点的显式分解。此外，HDC/VSA可以克服SRs和LRs关于缺乏语义基础的问题(即，缺乏对象的直接相似性；参见第节2.1.1).HDC/VSA通过其表示中的显式相似性克服了这些问题，因为HV不必以全有或全无的方式来表示相似性。然而，这些承诺带来了设计具体转换的问题，这些转换形成各种组成结构的HV，使得它们的HV之间的相似性将反映底层对象的相似性。在这一节中，我们考虑如何将各种类型的数据转换成HVs来创建这样的表示。数据类型包括符号(部分3.1.1)、集合(部分3.1.2)、角色填充绑定(部分3.1.3)、数字标量和向量(第3.2)、序列(部分3.3)，2D图像(部分3.4)，以及图表(第3.5).3.1符号和集合
如第节所述2.2.1，最简单的数据类型是符号。通常，不同的符号被认为是不相似的，因此，对不同的符号使用i.i.d .随机HV是将符号转换为HV的标准方法。这种HV对应于SRs(章节2.1.1)因为在HV和它的拷贝之间的相似性最大(即，相同的符号)而两个相同的随机HV之间的相似性最小(即，不同的符号)的意义上，它们表现得像符号。在LRs中，集合通常被表示为二进制“特征向量”，其中每个向量分量对应于所有可能符号的宇宙中的特定符号。特定集合中存在的符号由相应矢量分量中的1来表示。在多重集的情况下，特征向量的分量值是相应符号的计数器。在HDC/VSA中，一组符号通常由符号HV的叠加形成的HV来表示。合成HV保持了与符号HV的相似性。请注意，布隆过滤器[Bloom, 1970]–一种众所周知的近似隶属度数据结构–是一种HV，其中叠加操作是通过符号的二进制HV的分量析取获得的(如在SBDR ),因此，可以被视为HDC/VSA的特殊情况[Kleyko et al.,2020b].还要注意，原则上，乘法绑定可以用来表示集合[Mitrokhin et al., 2019], [Kleyko et al.,2020a]，然而，相似性属性将完全不同于通过叠加的表示。3.1.3角色填充绑定Role-filler bindings角色填充绑定，也称为槽填充或键值对，是表示结构化数据记录的一种非常通用的方式。例如，在LRs中，角色(键)是组件的ID，而填充符(值)是组件的值。在HDC/VSA中，这由绑定的结果来表示。乘法绑定和置换绑定都可以使用。使用乘法绑定，角色和填充符都被转换为HV，它们被绑定在一起。当使用排列时，通常填充符由它的HV表示，而角色与一个唯一的排列或者某个固定排列应该应用于填充符的HV的次数相关联。在乘法绑定的情况下，关联不必限于两个HV，因此，可以表示涉及更多关联的数据结构。例如,“模式”的表示[Neubert and Protzel, 2018]可能涉及绑定对应于上下文、动作、结果的三个HV7。
一组角色填充绑定由它们的HV的叠加来表示。请注意，叠加的(角色填充)HV的数量是有限的，以保留其中包含的信息，例如，如果想要恢复被叠加的HV(参见第2.2.5 和2.4).3.2数字标量和向量
Numeric scalars and vectors
实际上，数字标量是许多任务中存在的数据类型，尤其是作为向量的组成部分。用i.i.d .随机HVs表示相近的数值不会保留原始数据的相似性。因此，当将数值数据转换为HV时，通常的要求是附近数据点的HV相似，而远处数据点的HV不相似。我们区分了三种将数值向量转换成HVs [Rachkovskij et al., 2013]:可选(部分3.2.1)、显性感受野(节3.2.2)，以及随机投影(第3.2.3).为了用相似HV表示标量的接近值，应该生成相关HV，使得相似性随着标量值的差异增大而减小。通常，标量首先被规范化到某个预先指定的范围内(例如，[0，1])。接下来，它被量化成有限的等级(级别)。由于HV具有有限的维度并且是随机的，它们只能可靠地(在相似性上有不可忽略的差异)代表有限数量的标量等级。因此，只有有限数量的等级由相关的HV表示，通常多达几十个。用HVs表示标量的早期方案是在[Rachkovskij and Fedoseyeva, 1990]和[Smith and Stanford, 1990].这些和其他计划[Rachkovskij et al., 2005c], [Purdy, 2016]可以被认为是实现了从HV的一个组件集到另一个组件集的某种“流动”,有或没有替换。例如，“通过连接进行编码”[Rachkovskij et al., 2005c]使用两个随机的HV:一个分配给范围内的最低等级，而第二个用于表示最高等级。使用某种形式的插值来形成中间等级的HV，例如与从当前等级到最小和最大等级的距离成比例的HV部分的串联。在[]中提出了类似类型的插值Cohen et al., 2013], [Widdows and Cohen, 2015], [Kleyko et al., 2018].[中的方案Smith and Stanford, 1990]和“减法-加法”的一个[Rachkovskij et al., 2005c]从一个随机HV开始，递归翻转一些分量的值，得到以下等级的HV。这种方案在例如[Rahimi et al., 2016], [Kleyko et al., 2018]，用于在分类任务中应用HDC/VSA时表示特征值。为复数和实值HVs提出的另一种早期方案称为分数功率编码(参见[Plate, 1994]).它基于复值HVs(单位圆上的随机角度)可以(按分量)指数化为任意值的事实:其中z(x)是表示标量x的HV，z是称为基HV的随机HV [Frady et al., 2021a]，而β是控制所得相似性核的宽度的带宽参数。这种方法既不需要在预先指定的范围内归一化标量，也不需要量化它们。分数功率编码可以立即应用于FHRR。它也用于HRR，通过使用快速傅立叶变换进行复值HV、指数运算，然后进行快速傅立叶逆变换以返回实值HV(参见[Frady et al., 2021a]了解详情)。7.请注意[Neubert and Protzel, 2018]是基于三个角色填充绑定的叠加。在由HVs ( [Rachkovskij and Fedoseyeva, 1990], [Stanfordand Smith, 1994], [Rachkovskij et al., 2005d]，我们首先为标量(即一个数值向量的分量)形成HV。然后，对应于不同分量的值的HV被组合(通常使用叠加，但是也使用乘法绑定)以形成表示数字向量的合成HV。如果不同组件中的标量由不同的项目存储器表示，HV可以按原样叠加。有时，保存单个标量项内存更实用8，由所有组件共享。在这种情况下，在应用叠加运算之前，必须将标量的HV与其在数值向量中的分量标识相关联。这可以通过表示角色填充绑定来实现(参见3.1.3)与某种形式的绑定。请注意，不同的方案和模型提供不同类型的相似性，例如[Rachkovskij et al., 2005d], [Thomas et al., 2021].还要注意，与分量正交的普通向量不同，可以使附近分量的角色HV相关(例如，附近的过滤组比位于远处的过滤组更相关)。3.2.2显性感受野Explicit Receptive Fields感受野方法通常被称为粗编码，因为一个数字向量是由该向量激活的感受野粗略表示的。有几个利用显式感受野的众所周知的方案，如Cere- bellar模型发音控制器(CMAC) [Albus, 1975]，普雷格代码[Prager, 1993]，以及随机子空间码(RSC) [Kussul et al., 1999], [Kussul et al., 1994]，其中感受野是各种随机放置和大小的超矩形，通常仅在一些输入空间维度中。值得注意的是，这些方案形成了(稀疏的)二进制HVs。然而，类似的方法可以产生实值HV，例如，通过使用径向基函数作为感受域[Aiserman et al., 1964], [Moody and Darken, 1989].详情和比较可在[Rachkovskij et al., 2005b], [Rachkovskij et al., 2005a].特别地，获得了由RSCs表示的输入数值向量之间的相似性函数。3.2.3基于随机投影的方法Random projections based approach随机投影(RP)是另一种方法，其允许通过将数值向量x乘以RP矩阵R来形成数值向量x的HV:并且可能执行一些归一化、二值化和/或稀疏化。这是一种众所周知的方法，在数学和计算机科学中得到了广泛的研究Johnson and Lindenstrauss, 1984], [Indyk and Motwani,1998], [Papadimitriou et al., 2000], [Vempala, 2005], [Rachkovskij and Gritsenko, 2018].最初，RP方法用于产生较小维度的合成向量Rx的方案中(即，用于维度缩减)。这对于例如原始高维数值向量(以及simdot和distangle)的快速估计是有用的。知名应用在相似性搜索[Kaski, 1998], [Indyk and Motwani, 1998]和压缩感知[Donoho, 2006].首先，研究了具有来自正态分布的分量的随机R[Johnson andLindenstrauss, 1984], [Indyk and Motwani, 1998], [Vempala, 2005]，但是对于具有来自1，+1(双极矩阵)和1，0，+1(三元和稀疏三元矩阵)的分量的RP矩阵，证明了相同的性质[Achlioptas,2003], [Li et al., 2006], [Kane and Nelson, 2014].
在HDC/VSA的背景下，使用稀疏三元矩阵的RP方法首次应用于[Kanerva et al.,2000](另请参见第节)2.2.1.1 调查第二部分[Kleyko et al., 2021c]了解详情)。在[Misuno et al., 2005b], [Misunoet al., 2005a](参见第节2.2.1 调查第二部分[Kleyko et al., 2021c])，建议将Rx的结果二进制化或三进制化(通过阈值化),这产生稀疏HVs。稀疏HVs对simcos估计值的分析于2006/2007年首次报道，随后发表在[Rachkovskij et al., 2012], [Rachkovskij, 2014], [Rachkovskij, 2015]，从而使用具有稀疏三元和二元矩阵的RP。在[Dasgupta et al., 2017]，稀疏二进制矩阵的RP用于扩展原始向量的维数。注意，增加原始向量的维度先前已经在机器学习分类任务中广泛使用，因为它允许线性化非线性类别边界。在[Becker et al., 2016]，研究了由Rx产生的HV的阈值，并将其应用于快速(即，相对于基础中的对象数量的次线性)相似性搜索的环境中。![]()
通常使用单个RP矩阵来形成HV，但也有一些方法依赖于使用多个RP矩阵[Ra¨sa¨nen, 2015]:z =σn λiRix，其中λi决定I RP Rix对合成HV的贡献。 RP方法的一个吸引人的特点是，它可以应用于任意维数和任意数量的分量渐变的输入向量，这与合成或感受野方法不同。[1]对使用快速成型技术形成HVs进行了一些理论分析Thomas et al., 2021].3.3顺序
下面我们介绍几种用HVs表示序列的标准方法。这些方法包括将元素的HV与其位置HV绑定，使用置换的绑定，与上下文HV绑定，以及将HV用于n元语法。有关这些方法的概述，请参见，例如[Sokolov and Rachkovskij, 2006].8.这种项目记忆通常被称为连续项目记忆，因为它存储相关的HV。3.3.1元素的HV与其位置或上下文HV的绑定Binding of elements’ HVs with their position or context HVs表示序列的标准方式之一是使用角色-填充绑定HV的叠加，其中填充是符号的HV，而角色是其位置的HV [Kussul and Rachkovskij, 1991], [Plate, 1995b], [Hannagan et al., 2011].在[Kussul and Rachkovskij, 1991]，顺序由从序列符号的初始HV中选择的分量子集的权重来表示(例如，每个在前的符号由比在后的符号更多的二进制HV的1分量来表示)。在[Rachkovskij, 1990]，建议从先前序列符号(上下文)的HVs中使用细化。然而，最常见的是使用i.i.d .随机HV来表示位置。避免存储不同位置的HV的方法是使用HDC/VSA模型，其中绑定操作不是自逆的。在这种情况下，序列中的绝对位置k通过将位置HV与其自身绑定k次来表示[Plate, 1992], [Plate,1995b].这样的机制被称为“轨迹关联”。当顺序形成序列表示时，轨迹关联可能是方便的，允许以递增的方式形成序列HV。然而，序列HV不保持与邻近位置的符号HV的相似性，因为位置HV不相似，因此角色填充结合HV也不相似。MBAT模式(第2.3.4)具有类似的性质，其中通过乘以随机位置矩阵来执行位置绑定。为了使附近位置的符号彼此相似，可以使用相关位置HVs [Sokolov andRachkovskij, 2006使得例如移位的序列仍将导致它们的HV之间的高度相似性。这种方法也是在[Cohen et al., 2013], [Widdows and Cohen, 2015](参见第节3.2).2D图像的类似想法将在第节中讨论3.4.2。此外，下一个符号的HV可以绑定到前一个符号的HV，或者绑定到前一个符号的几个(加权)HV，即实现“与上下文绑定”的方法[Rachkovskij, 1990].3.3.2通过排列表示位置Representing positions via permutations表示序列中位置的另一种方法是使用排列[Kussul and Baidyk, 1993], [Sahlgrenet al., 2008], [Kanerva, 2009].在组合序列符号的HV之前，通过对每个符号的HV i次(例如，ρ2(c))应用某种特定的置换来表示每个符号的阶I。然而，这种基于置换的表示不能保持邻近位置的相同符号的相似性，因为置换不能保持置换HV和原始HV之间的相似性。为了在使用置换时保持HV的相似性，在[Kussul and Baidyk, 2003], [Cohen and Widdows, 2018]，建议使用部分(相关)置换。3.3.3序列的合成HVs Compositional HVs of sequences一旦序列的符号与它们的位置相关联，最后一步是将序列符号的HV组合成表示整个序列的单个合成HV。有两种常见的方法来组合这些HV。![]()
第一种方法是使用叠加运算，类似于截面集中的情况3.1.2。例如，对于序列(a，b，c，d，e ),合成HV(表示为s)为:s = ρ0(a) + ρ1(b) + ρ2(c) + ρ3(d) + ρ4(e)。(17)在这里，我们举例说明了通过排列来表示位置，但是其他方法的组成也是一样的。叠加操作方法的优点是可以通过测量两个序列HV的相似性来估计它们的相似性。形成序列的组成HV的第二种方式涉及置换HV的结合，例如，上述序列表示为(表示为p):p =ρ0(a)♀ρ1(b)♀ρ2(c)♀ρ3(d)♀ρ4(e)。(18)这种序列表示法的优点是，它允许形成伪正交HVs，即使序列仅在一个位置不同。类似于轨迹关联，可以通过置换当前序列的HV并将其与序列中的下一个HV相加或相乘来扩展序列，因此，导致每个符号的固定计算成本。
注意，序列的组成HVs也可以是杂交性质的。例如，当通过排列来表示位置时，相邻位置中相同符号的相似性不会被保留。一种当序列中的一些符号被置换时保持相似性的方法在[Kleyko et al., 2016a]，其中序列的合成HVs包括两部分:构成序列的多重符号集的表示(符号包)和符号的有序表示。第一部分被转换成HV作为多组符号(部分3.1.2)通过叠加序列中存在的所有符号的原子HV。第二部分被转换成HV作为序列，使用符号HV的排列来编码它们的顺序(部分3.3.2) .两种表示叠加在一起以获得组成HV。n元文法是一个序列的n个连续符号。在序列的n-gram表示中，提取序列的所有n-gram，有时针对不同的n。通常，形成包含n-gram统计的向量，使得其分量对应于不同的n-gram。该分量的值是相应n元语法出现的频率(计数器)。n-grams到HV有各种各样的转换。用HVs表示多重集的可能性(第3.1.2)允许将表示n元语法统计的HV形成为各个n元语法的HV的叠加。因此，n-grams在HVs中的表示通常在以下方面有所不同:•它们区分不同的n-gram，其中“不同”意味着甚至单个唯一的符号(例如，(abc)对(abd))或者不同位置的相同符号(例如，(abc)对(ACB))；为了形成不同n元文法的不同HV，可以为每个n元文法分配一个i.i.d .随机HV。然而，n元语法HV通常是从其符号的HV生成的。因此，为了节省n元文法的HV表示空间，可以使用复合HV[Rachkovskij, 1996], [Joshi et al., 2016]而不是为每个n元语法生成原子HV。因此，可以使用上述表示序列的方法。在[Rachkovskij, 1996], [Joshi et al.,2016], [Kim et al., 2020]，n元符号的置换HV通过乘法绑定来绑定。或者，在[Jones and Mewhort, 2007], [Kachergis et al., 2011]，HV对的乘法绑定被递归地执行，由此左边的HV对应于n元文法的已经表示的部分，而右边的HV对应于n元文法的下一个元素。左HV和右HV通过不同的固定随机排列来排列。与上述方法相反，在[Recchia et al., 2010], [Imani et al., 2018n-gram符号的置换HV不是乘法绑定的，而是叠加的，这给出了相似n-gram的相似HV。在[Hannagan et al.,2011]，还使用了对应于符号位置的HV的叠加。然而，二元模型中符号的位置(可能来自不相邻的符号)不是通过排列来指定的，而是通过与左右位置的HV的乘法绑定来指定的。栈可以被看作是一个序列的特例，其中元素以后进先出的方式被插入或移除。在任何给定的时刻，只有堆栈的最顶层元素可以被访问，而之前写入堆栈的元素是不可访问的，直到所有后面的元素都被移除。基于HDC/VSA的堆栈表示在[Plate, 1994], [Stewart et al., 2014], [Yerxa et al., 2018].堆栈的HV本质上是一个序列的表示，叠加操作总是将最顶端的元素移动到序列的开头。3.42D图像
对于在HDC/VSA模型中用二维结构表示对象，例如2D图像，有许多建议。在这一节中，我们将现有的表示建议分为三组:基于排列、基于角色填充绑定和基于神经网络。3.4.1基于排列的表示Permutation-based representations如第节所述2.2.3.2置换通常被用作实现绑定操作的一种方式。在2D图像的上下文中，可以通过为x轴分配一个排列和为y轴分配另一个排列来使用排列[Kussul and Baidyk, 1993], [Kussul et al., 2010].实现这些置换的最简单方法是使用循环移位。然后，为了将像素值(或图像特征)的HV与其位置绑定，应用x轴置换x次，应用y轴置换y次[Mitrokhin et al., 2019], [Kleyko et al., 2020a].然后，整个图像被表示为包含像素值的所有置换HV的叠加的合成HV。表示像素(特征)值的HVs可以使用任何表示标量的方法来形成(参见3.2).因为置换的HV在上面的任何作品中都不相似，所以即使在附近位置的相同像素的值也将由不同的HV表示。基于排列的表示缺乏相似性的问题在[Kussul and Baidyk,2003], [Kussul et al., 2006]通过使用部分置换。一些像素值HV(或者，更一般地，一些特征的HV)的置换分量的数量随着坐标变化(在一些半径内)而增加，直到完全置换。因此，在半径内，相似性降低。在半径之外，同样的过程再次重复。结果，在(x，y)处的像素值HV类似于相似性半径内附近位置的HVs。其位置被表示的特征是随机局部描述符(RLD)。例如，对于二进制图像，如果局部感受野内的一些(因不同特征而异)像素取0和1值，则检测到RLD特征。注意，RLD可以被认为是感受野方法的一个版本(节)3.2.2)并能形成代表图像的HVs，如线性感受区(LIRA)特征的情况[Kussul and Baidyk, 2004].3.4.2基于角色填充绑定的表示Role-filler binding-based representations在2D图像中，很自然地将像素的位置及其值表示为角色-填充符绑定，其中像素的位置HV是角色，对应于像素值的HV是填充符。类似于置换的情况，图像HV形成为包含所有角色填充结合HV的叠加的合成HV。当涉及到像素位置HVs时，最简单的方法是将每个位置视为一个唯一的符号，以便可以为其分配一个唯一的随机HV。这种方法允许通过角色填充绑定来形成图像HV。它是在[Kelly et al., 2013], [Kleyko et al., 2017], [Manabat et al., 2019]对于实值和稠密二进制HVs和in [Kleyko et al., 2016b]对于稀疏二进制HV。然而，具有用于角色的唯一HV的方法既不强加像素位置HV之间的任何关系，也不允许在局部邻域中保持像素位置HV的相似性，这例如对于抵抗2D图像中的小变化的鲁棒性是有用的。为了解决后一个问题，在[Kussul et al., 1992描述了一种方法，其中附近的x和y坐标的HVs也表示为相关的HV，使用表示标量的方法(第3.2).然后，通过绑定三个HV来表示位置(x，y)中的像素值:一个表示像素在(x，y)处的值，两个表示x和y坐标本身(在[Kussul et al., 1992]).因此，相近的相似值由相似的HV表示。移动MBAT(蒙巴特)[Gallant and Culliton, 2016]被提出来显式地保持邻近像素的HVs的相似性。如在MBAT模式中(第2.3.4)，矩阵被用作角色。特别地，每个坐标(x，y)的矩阵由两个随机矩阵的加权叠加形成。因此，对于x和y，附近的坐标由相似的(相关的)矩阵表示。然后，每个(x，y)对由通过绑定(相乘)那些对应的矩阵而获得的矩阵来表示。(x，y)处的像素值通过将其HV与(x，y)的矩阵绑定来表示。最后，叠加获得的HVs。所有参与MOMBAT的HV都有实值部分。在[1]中考虑了用于BSC和稠密二元HVs的具有局部相似性保持的类似方法Burco, 2018].分数功率编码方法(章节3.2.1)对2D形象的再现是在[Weisset al., 2016], [Frady et al., 2018a], [Komer et al., 2019].它在像素位置之间强加了一种结构，并且可以在局部邻域中保持相似性。特别地，图像HV如下形成。分别为x轴和y轴分配两个随机基本HV。为了表示x和y坐标，相应的基HV被指数化为坐标值；和z(x，y)(x，y)坐标的HV)形成为它们的结合(假设β = 1 cf .(15)):最后，与像素值的HV绑定完成。在六边形坐标中基于分数功率编码的表示的变体在[Komer and Eliasmith, 2020].由于神经网络目前是处理2D图像的主要工具之一，所以使用它们来产生2D图像的HVs变得越来越普遍。这一点尤其重要，因为直接将像素值转换为HVs通常不会为解决具有竞争性能的机器学习任务提供良好的表示。例如，有一些研究[Manabat et al., 2019], [Hassan et al., 2021]直接将MNIST的2D图像转换为HVs。事实上，所报告的精度低于用例如直接应用于像素值的kNN分类器获得的精度。因此，重要的是应用一些特征提取技术(例如[Kussul and Baidyk, 2004], [Kussulet al., 2006])或者使用神经网络作为前端。证明这一点的最早尝试之一出现在[Yilmaz, 2015b], [Yilmaz, 2015a].所提出的方法采用由输入图像引起的卷积神经网络的隐藏层之一的激活。这些激活然后被二进制化，并且二进制化的结果被用作基本细胞自动机的初始网格状态。自动机进化了几个步骤，并且先前步骤的结果被连接在一起，其结果被视为对应于图像的HV。自动机进化执行非线性特征提取，本着里拉和RLD的精神。后来的工作使用了卷积神经网络的激活，而没有额外的细胞自动机计算。例如，在[Neubert et al., 2019], [Mitrokhin et al., 2020]使用预先训练的现成卷积神经网络Karunaratne et al., 2021网络的注意机制和损失函数是专门设计来产生具有理想特性的HVs的。例如，它指示神经网络的输出将伪正交HVs分配给来自不同类别的图像[Karunaratne et al., 2021].值得注意的是，从神经网络中获得HVs是一个相当新的方向，没有任何研究能够仔细比较从不同神经网络结构中获得的HVs。3.5图表
一个图，记为G，由节点和边组成。边可以是无向的，也可以是有向的。图。3 提供有向和无向图的例子。首先，我们考虑将图简单地转换成HVs [Gayler and Levy, 2009].随机HV被分配给图中的每个节点，如下图所示。3 节点HV由字母表示(即，a表示节点“a ”,依此类推)。一；一个![]()
注意，最后六个等式指的是CDT程序。HVs的这些类型的图形表示将在第节中进一步讨论3.1.2.2调查第二部分[Kleyko et al., 2021c]在描述HDC/VSA对类比推理的应用时。
图4:表示发作原因(咬伤(斑，简)，逃跑(简，斑))的标记图的示例。知识图的表示在[Ma et al., 2018].这项工作提出使用柯西分布来生成原子HVs，并展示了使用知识图的HVs作为神经网络的输入来推断缺失链接的任务的最新结果。知识图的HVs也可以使用从数据中学习的节点和关系的HVs来构建，如[Nickel et al., 2016]，由于HRR的可微性，这里使用了它。树是图形的一个实例，其中较低级别的节点(子节点)属于单个较高级别的节点(父节点)。因此，树可以用与上图相同的方式来表示。请参考给定的HVs转换示例，例如，在[Rachkovskij and Kussul, 2001]对于无序二叉树和in [Frady et al., 2020], [Kleyko et al.,2021a]对于有序二叉树。在本节中，我们仅讨论调查第一部分中涉及的HDC/VSA的一些方面。请参阅第二部分[Kleyko et al., 2021c]获得与应用领域、与神经网络的相互作用和开放问题相关的方面的广泛讨论。4.1HDC/VSA型号之间的连接
如第节所述2.3，有几个HDC/VSA模型。目前，关于模型之间的联系还有许多未解的问题。例如，一些模型在执行乘法绑定操作(例如，循环卷积或依赖于上下文的细化过程)时使用HVs的多个分量之间的交互。其他模型(例如，傅立叶全息简化表示和二进制飞溅码)使用针对组件的乘法绑定操作。在什么情况下一个比另一个更好并不总是很清楚。因此，对乘法绑定操作之间的关系以及它们的适用范围有更原则性的理解是很重要的。例如，这方面的一个最新理论结果[Frady et al., 2021b在某些条件下，乘法-加法-置换中的乘法结合在数学上等价于张量积表示中的乘法结合。此外，一般来说，不清楚是否存在一个最佳模型，它将支配所有其他模型，或者每个模型是否有自己的适用范围。最近的一部作品[Schlegel et al., 2020]开始在模型之间进行系统的实验比较。我们认为这方面的工作应该继续下去。最后，还有一个问题是，是否有必要寻找新的人类发展中心/VSA模式。4.2HDC/VSA的理论基础
应当指出，人类发展中心/VSA在很大程度上是作为一个经验领域开始的。与此同时，HDC/VSA隐含地使用了众所周知的数学现象，如集中测量[Frady et al., 2021b]和随机投影[Thomas et al., 2021].目前，需要为人类发展中心/VSA制定坚实的理论原则。我们开始在这方面看到有希望的结果。例如，最近有一种“能力理论”[Frady et al., 2018b](部分2.4)，它提供了一种使用最近邻搜索来估计可以从HVs重构的信息量的方法在项目存储器中。另一个例子是从HVs [Thomas et al., 2021].在[Frady et al., 2021bHDC/VSA中的HVs操作显示与压缩感知有关。我们预见到，随着HDC/VSA将更多地接触理论计算机科学家，我们将看到更多的工作建立该领域的理论基础。4.3HDC/VSA模型的硬件实现
HDC/VSA的承诺很大一部分是基于这样一个事实，即它们适合在各种非常规硬件上实现，如神经形态硬件[Frady and Sommer, 2019]，内存计算[Karunaratneet al., 2020]，单片3D集成硬件[Li et al., 2016], [Wu et al., 2018】等。有趣的是，在专用硬件上使用HDC/VSA的动机从一开始就存在。一个早期的例子是专门的神经计算机Kussul et al., 1991b]构建为使用稀疏二进制分布式表示进行操作。此外，硬件实现的话题最近受到了很多关注。这主要是因为深度神经网络等现代机器学习算法需要大量资源来训练和运行它们[Strubellet al., 2019].在我们看来，另一个动机来自于HDC/VSA可以被视为一个抽象算法层，因此可以用于设计计算原语，然后可以映射到各种硬件平台[Kleyko et al., 2021a].然而，HDC/VSA的硬件是一个活跃的研究领域，也是一个独立的主题，因此我们决定将其排除在本次调查的范围之外。然而，我们期望在未来的几年里，这一主题将在社区的发展中发挥重要作用。在调查的第一部分中，我们提供了一个关于计算框架的全面报道，该框架被命名为超维度计算和向量符号架构。我们特别关注现有的超维度计算/向量符号体系结构模型以及各种类型的输入数据到超向量表示的转换。调查的第二部分[Kleyko et al., 2021c]回顾已知的应用，触及认知建模和认知架构，并讨论开放的问题以及未来工作最有希望的方向。A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
Denis Kleyko, Dmitri A. Rachkovskij, Evgeny Osipov, and Abbas Rahimi !
Abstract
This two-part comprehensive survey is devoted to a computing framework most commonly known under the names Hyperdimensional Computing and Vector Symbolic Architectures (HDC/VSA). Both names refer to a family of computational models that use highdimensional distributed representations and rely on the algebraic properties of their key operations to incorporate the advantages of structured symbolic representations and vector distributed representations. Notable models in the HDC/VSA family are Tensor Product Representations, Holographic Reduced Representations, Multiply-Add-Permute, Binary Spatter Codes, and Sparse Binary Distributed Representations but there are other models too. HDC/VSA is a highly interdisciplinary area with connections to computer science, electrical engineering, artificial intelligence, mathematics, and cognitive science. This fact makes it challenging to create a thorough overview of the area. However, due to a surge of new researchers joining the area in recent years, the necessity for a comprehensive survey of the area has become extremely important. Therefore, amongst other aspects of the area, this Part I surveys important aspects such as: known computational models of HDC/VSA and transformations of various input data types to high-dimensional distributed representations. Part II of this survey [Kleyko et al., 2021c] is devoted to applications, cognitive computing and architectures, as well as directions for future work. The survey is written to be useful for both newcomers and practitioners.
Index Terms
Artificial Intelligence, Machine Learning, Hyperdimensional Computing, Vector Symbolic Architectures, Distributed representations, Data structures, Holographic Reduced Representations, Tensor Product Representations, Matrix Binding of Additive Terms, Binary Spatter Codes, Multiply-Add-Permute, Sparse Binary Distributed Representations, Sparse Block Codes, Modular Composite Representations, Geometric Analogue of Holographic Reduced Representations
