ResHDC：为大脑中网格细胞的计算操作提供了可能解释的框架：残差超维计算

Computing with Residue Numbers in High-Dimensional Representation

高维表示中的残差计算 https://arxiv.org/abs/2311.04872

应用：

基础：

计算神经科学中的先前工作[11]，[30]强调残数数系统赋予网格细胞有用的计算属性，包括高空间分辨率、模块化更新和错误校正。我们展示了残数超维计算如何在工作神经实现中成功实现这些编码属性（第2.2节和2.3节）。反过来，我们的代数框架对计算神经科学有两个贡献。首先，我们展示了如何将残数数系统扩展到一个自洽的非负六边形坐标系统。其次，我们提供了一种新的算法，通过谐振器网络集体耦合空间位置到网格细胞模块。我们框架对系统神经科学的核心预测是，每个网格细胞模块对应于谐振器网络中的一个因子估计。更具体地说，每个模块实现了一个环面吸引子网络，与海马体和其他网格细胞模块的乘法耦合使错误校正成为可能。这一预测既与支持单个网格细胞模块中连续吸引子网络存在的最新实验分析一致[41]，也与海马体和内侧内嗅皮层联合吸引子动力学的最新理论一致[42]。

摘要‍‍

我们介绍了一种名为残数超维计算（Residue Hyperdimensional Computing，简称RHC）的计算框架，它将残数数系统与在随机高维向量上定义的代数统一起来。我们展示了如何将残数表示为高维向量，使得可以通过向量元素上的组件级、可并行化的操作执行代数运算。结合一种高效的高维向量分解方法，该框架能够在大幅减少资源使用的情况下表示和操作具有大动态范围的数值，并且展现出对噪声的显著鲁棒性。我们展示了这一框架在视觉感知和组合优化等计算难题上的潜力，显示了其相较于基线方法的改进。更广泛地说，该框架为大脑中网格细胞的计算操作提供了可能的解释，并为表示和操作数值数据提出了新的机器学习架构。

1 引言

表示和计算数值的高维表示形式——例如位置、速度和颜色——是机器学习和计算神经科学中的一个核心问题。在机器学习中，数值的向量表示对于在神经网络中定义位置或功能编码非常有用[1]–[3]，提高对对抗性示例的鲁棒性[4]，以及生成高效的分类器[5]。在神经科学中，实验者寻求理解大脑中神经元群体如何表示和转换感知或认知变量，因此许多理论家构建了模型，来展示这些变量如何被编码在高维向量编码中，以及如何从这些编码中解码（例如，[6]–[8]）。

神经科学中高维表示的一个特别突出的例子是海马体背侧内嗅皮层中‘网格细胞’的空间位置编码[9]。网格细胞在其放电率中具有多个峰值，这些峰值与六边形格子排列的空间位置相关联。虽然这种编码方案乍一看有些令人困惑，但其有用性从其作为群体编码的功能中变得明显。与具有传统单峰编码功能的神经元群体相比，其编码分辨率随着神经元数量的增加而线性增长，网格细胞群体拥有随着神经元数量增加而呈指数增长的编码分辨率[10]。特别是，Fiete及其同事强调了网格细胞编码利用了残数数的特性（见下文2.2节）[11]。

受这一观察结果的启发，我们提出了一个基于残数数系统的分布式神经计算的全面代数框架。我们的新框架建立在现有的用于计算高维随机向量的代数框架之上。这个想法最初被称为全息减少表示计算[12]，现在也被称为向量符号架构（Vector Symbolic Architectures，简称VSA）[13]和超维计算[14]。我们称我们的新框架为残数超维计算（RHC），并证明它继承了标准残数数系统和超维计算的计算优势。这使得即使在内存需求大大减少的情况下，也能高效地表示数字并搜索大动态范围内的数值。此外，正如我们将看到的，新框架为理解网格细胞中的计算提供了有用的形式主义。

总结来说，我们列出了通过残数超维计算实现的四个关键编码属性：(1) 代数结构：向量上的简单操作执行编码值的加法和乘法；(2) 表达性：可行的编码范围与维度的增长速度比线性更好；(3) 高效解码：解码所需的资源与编码范围的增长速度相比，增长得更慢；(4) 对噪声的鲁棒性。尽管以前提出的一些模型实现了这些属性中的一些（见表S.1，补充材料A），但据我们所知，残数超维计算是第一个实现所有这四个理想的框架，正如我们现在将要展示的。

2 结果

我们首先定义了残数超维计算框架所基于的关键概念（第2.1节），然后在第2.2节中完整描述了该框架。然后，我们展示了它在编码、解码以及鲁棒性方面的有利特性（第2.3节），以及如何将其扩展到多维（第2.4节）和小数编码（第2.5节）。特别值得注意的是，我们构建了一个类似于网格细胞坐标的六边形残数编码系统，它比正方形格子提供了更高的空间分辨率。最后，我们描述了如何将该框架应用于视觉场景分析和组合优化问题（第2.6节）。

2.1 预备定义

2.2 残数超维计算

现在，我们介绍分数幂编码（Fractional Power Encoding，简称FPE）如何实现残数数系统。作为第一步，我们解释FPE如何实现同余（表示一个余数，模m）现在，我们介绍分数幂编码（Fractional Power Encoding，简称FPE）如何实现残数数系统。作为第一步，我们解释FPE如何实现同余（表示一个余数，模m）。

除法在残数数系统中没有明确定义，因为整数在除法下不是封闭的。尽管如此，当模数 m k

m

k

m

k

为加法和乘法存在两个不同的绑定操作符是超维计算中的一个新贡献。以前的公式只支持加法，或者在进行对数变换后通过加法实现乘法[22]。因此，我们现在可以制定一个完全分布式的残数数系统，它继承了使用高维向量计算的好处。

2.3 谐振器网络实现残数的高效解码

给定残数的向量表示，我们如何解码它以恢复其值 x？在超维计算中常用的一种解码方法是码本解码[23]，它涉及将与一组已知值 x 的 M 个码本向量进行内积。然而，这个过程需要 的存储空间和 M 次内积评估。

幸运的是，我们可以利用余数将一个数字的动态范围分解为一组较小的数字，每个数字的整体动态范围较小，从而改善这种情况。例如，一个动态范围为105的数字，当表示为模数 [3, 5, 7] 的形式时，总动态范围变为3+5+7 = 15。这反过来又使解码所需的内存和计算资源减少了105/15 = 7倍。然而，要使这一方法有效，我们需要反转方程4——也就是说，我们必须将 z(x) 因式分解为一组由 x 模 mk 表示的组成向量 {zm1(x), zm2(x), ... , zmK(x)}，从中可以轻松恢复 x。为此，我们可以使用谐振器网络[24],[25]，这是一种最近发现的高效因式分解超维计算向量的方法。图2a显示，对于不同的M值范围，谐振器网络可以比标准码书解码快一个数量级地恢复向量。两个对这一点有贡献的参数是向量维度 (D) 和模数数量 (K)。

为了评估谐振器解码对向量维度的依赖性，我们固定模数数量 (K = 2) 并计算谐振器在有效范围 M 上的经验准确性（图2b）。我们发现，对于固定的 D，准确性在某个M范围内几乎保持完美，之后准确性迅速下降。为了评估 D 的扩展性，我们定义维度容量 C 为经验准确性至少为95%的最大M值。我们发现 C(D) 的扩展性可以用二次多项式很好地拟合（图2c），这与之前研究的具有两态组件的谐振器网络的扩展规律一致[25]。进一步测试更高维度将有助于确认二次扩展性，但即使是线性扩展，其斜率也很大（注意 C(4096) >。

为了评估对模数数量的依赖性，我们固定 D = 1024 并变化 K。我们发现随着 K 的增加，谐振器容量减少（图2d），这也与之前的工作一致[25]。尽管如此，我们强调具有较高 K 的谐振器有两个优势：每次解码的计算量减少（图2a），以及内存需求减少。谐振器只需要 Pk mk = b 个码书向量，而不是 Qk mk = M。这意味着，在给定的码书预算下，增加 K 可以增加几个数量级的有效范围（图2e）。值得注意的是，对于给定的 b，最大M由兰道函数 g(b) 给出，g(b) 随 b 的增加按规模增长[26]。这意味着在提供足够的 K 的情况下，存储需求和有效范围之间存在指数级的扩展关系。

最后，我们评估了谐振器网络解码对噪声的鲁棒性。我们从 von Mises 分布中抽取均值为0、集中度为 κ 的相位噪声；较高的 κ 表示噪声较小。在图2f中，我们观察到性能随噪声的增加逐渐下降，但即使在高噪声水平下，容量仍然保持相当高。

2.4 多维度的推广

2.4.1 Zn 的笛卡尔表示

2.4.2 六边形坐标系统

在多维空间中工作时，笛卡尔坐标系统有多种替代方案。例如，内侧内嗅皮层的网格细胞使用六边形坐标系统对空间位置进行编码；理论神经科学的研究表明，这是因为这种空间铺砌在二维空间中具有最高分辨率（费舍尔信息）[27]。作为一个说明性的例子，我们展示了残数超维计算也可以实现六边形坐标系统，并且这种六边形晶格比正方形晶格保留了编码优势。特别值得注意的是，我们制定了一种自洽的编码，将残数数系统扩展到非负六边形坐标。

因此，我们可以用 Voronoi 镶嵌（图 3e）来表示六边形坐标系统，其中空间的不同区域被映射到它们最近的整数值三维坐标。模数为 m 的六边形系统有 个不同的状态，需要 3m 个码本向量，而正方形晶格有个不同的状态，需要 2m 个码本向量（图 3g）。因此，对于相同的资源数量，六边形系统比正方形晶格实现了更好的空间分辨率（它是一个关于空间的更高熵编码）（图 3h）。

2.5 扩展到小数解码分辨率

在前面的部分中，我们专门使用整数状态和实现它们的残数数系统。然而，有趣的是，我们可以将 FPE（分数幂编码）的定义扩展到有理数（方法 4.4.1），并且谐振器网络会收敛到非整数的 FPE 编码，即使码本仅包含整数的编码（图 4a 和 b）。严格来说，超越整数的这种扩展不再是残数数系统，乘法绑定也不再有明确的定义。然而，对于网格细胞的理论分析中已经考虑了向小数分辨率的扩展，例如在 [11]，[30] 中，我们展示了谐振器动态实现了这个小数分辨率。

图 4b 建议了一个有效的小数精度解码程序。码本状态和最终谐振器网络状态之间的内积可以通过将狄拉克梳与 sinc 函数卷积来很好地描述（补充材料 B）。对于整数编码，这个函数将在所有不在峰值附近的特征上评估为 0，但对于非整数，情况不再如此。尽管如此，我们还是能找到最匹配谐振器网络状态的小数偏移量，以便解码小数值（方法 4.4.2）。

相位噪声是解码小数状态的限制因素。为了更严格地量化这一点，我们在不同的噪声环境下（κ 分别为 16 和 1）评估了具有不同有效范围 M 的谐振器网络。然后，我们将每个单位间隔分割成 r 个分区，这样就有 M · r 个不同的数字被表示。图 4c 和 4e 分别显示了在 κ = 16 和 κ = 1 下，不同分区数量的解码精度。为了考虑精度和区分的不同状态数量，我们还报告了“每个向量的比特数”指标 [31]，在图 4d 和 4f 中。这个指标验证了在较低噪声下，我们可以更可靠地解码更多的状态

2.6 应用

2.6.1 从图像中高效分离物体形状和姿态

在这里，我们研究视觉中的分离问题——即在仅知道图像像素值的情况下，恢复场景的底层组成部分的任务。这类问题在视觉感知中比比皆是；示例包括从运动中推断结构或者将由于3D形状和照明产生的阴影与光谱反射属性分离。大脑如何通常分离这些变化因素是未知的，并且由于因素组合创建任何给定场景的方式在计算上是具有挑战性的，因为存在组合爆炸[32]。

我们通过两个阶段解决这个问题。首先，我们通过卷积稀疏编码（方法 4.5）形成图像的潜在特征表示。这一步反映了初级视觉皮层中的神经表示，据推测这种表示是用少量图像特征来描述图像内容的[33]。我们观察到这一步是有用的，因为它有助于去相关化图像模式，从而实现更高的精度和加速谐振器网络的收敛。

其次，我们将潜在的特征表示编码成高维向量，然后可以通过谐振器网络将其分解为其组成部分（Oa、Hb、Vc）。这是通过将每个图像特征的位置的残数编码叠加成一个单一的场景向量 s（方法 4.5，方程 10）来完成的。得到的向量 s 可以等价地表示为代表物体形状和位置的向量的乘积，因此，分离这些因素的问题本质上就变成了一个向量分解问题。

标准的方法来分解场景向量（例如，在[34]中）将是使用三个码本，分别对应形状、水平位置和垂直位置，总共有 10 + 105 * 2 = 220 个码本向量。相比之下，具有模数 {3, 5, 7} 的残数数系统使用 7 个因子，但只需要 10 + (3 + 5 + 7) * 2 = 40 个向量。图 5b 展示了两种问题设置的示例运行。

图 5c 展示了残数谐振器与标准谐振器基线相比的两个主要优势：内存需求的减少（正如所描述的）和所需的迭代次数。虽然在模拟中，标准谐振器平均需要超过 2,000 次码本评估，但残数谐振器平均只需要 ≈ 800 次码本评估。（与蛮力搜索相比，两者都有显著改进，蛮力搜索需要 110,250 次码本评估）。关键的教训是，对谐振器网络的这一简单改变导致了所需计算数量的乘法减少。

2.6.2 产生子集和问题的确切解

最后，我们将我们的子集和算法与蛮力搜索以及解决决策问题的指数时间算法进行了比较。谐振器网络找到解决方案所需的平均迭代次数大大少于蛮力搜索指数增长的成本（见图 6e），并且随着维度的提高而改善。我们发现，在 CPU 上，对于 |S| > 28 的情况，谐振器网络的时钟时间比指数时间算法更快（见图 6f，方法 4.6）；大部分计算时间都花在生成向量表示上，而不是谐振器网络动态本身。更重要的是，虽然基线算法需要 O(2^|S|) 的内存来保存内存中的候选子集，但谐振器网络只需要 O(D · |S|) 的内存，因为它永远不需要明确表示每个子集。我们强调，谐振器网络的 CPU 实现主要是作为概念验证，而且如果在新兴的计算平台上实现谐振器网络，可能会获得进一步的性能提升，如 [34]，[39] 中所述。

3 讨论

我们的研究首次定义了与超维计算相结合的残数数系统。该框架继承了两个系统的益处：来自残数数系统的无进位算术和中国剩余定理的理论保证，以及超维计算的鲁棒性和叠加计算特性[40]。该框架提供了一种有利的方式来编码、转换和解码对噪声具有鲁棒性的变量。综合这些属性，使得残数超维计算成为一个吸引人的框架，用于有效解决困难的计算问题，特别是那些涉及组合优化的问题。它还对模拟大脑中的群体编码，特别是网格细胞，具有意义。

计算神经科学中的先前工作[11]，[30]强调残数数系统赋予网格细胞有用的计算属性，包括高空间分辨率、模块化更新和错误校正。我们展示了残数超维计算如何在工作神经实现中成功实现这些编码属性（第2.2节和2.3节）。反过来，我们的代数框架对计算神经科学有两个贡献。首先，我们展示了如何将残数数系统扩展到一个自洽的非负六边形坐标系统。其次，我们提供了一种新的算法，通过谐振器网络集体耦合空间位置到网格细胞模块。我们框架对系统神经科学的核心预测是，每个网格细胞模块对应于谐振器网络中的一个因子估计。更具体地说，每个模块实现了一个环面吸引子网络，与海马体和其他网格细胞模块的乘法耦合使错误校正成为可能。这一预测既与支持单个网格细胞模块中连续吸引子网络存在的最新实验分析一致[41]，也与海马体和内侧内嗅皮层联合吸引子动力学的最新理论一致[42]。

该框架还对神经群体如何解决困难的优化问题，如视觉场景的分离，具有意义。最近的工作强调了超维计算作为类脑计算抽象的前景[34]，[40]，[43]。残数超维计算大幅减少了解决解码问题和组合优化所需的存储和平均操作数量，提供了一个简单而强大的改进。此外，我们框架建议的相位表示直接映射到Q态相位网络[44]，预示着在尖峰神经网络[45]中的有前景的实现，以及解决组合优化问题的策略[46]。

最后，我们的框架在子集和问题上的性能表明了一条新途径，用于解决具有分布式表示和非传统硬件的优化问题。子集和问题特别适合我们的框架，因为它可以通过高维向量的哈达玛德积操作轻松实现。由于其他难题，如3-SAT，可以有效地映射到子集和问题上，我们的结果可能为有效解决NP难问题指明了一类新的并行算法。

4 方法

4.1 代数运算的定义

4.1.1 加性绑定运算的定义

我们在余数超维计算中通过使用Hadamard积操作（逐元素相乘，⊙）来实现加法：即，。Hadamard积正确地实现了加法，因为它是交换的。可以如下解释：

4.1.2乘法绑定操作的定义

4.2 解码方法

4.2.2 谐振器网络细节

g 是一个非线性函数，保留每个复数分量的相位并丢弃角度。在解码余数数的表示时，每个因子（或模数）Zj 的码书由 mj 个条目组成，这些条目是余数的向量编码。在所有实验中，我们使用异步更新规则，在每个时间步仅更新一个因子的估计，每组时间步中，每个向量更新一次。算法运行直到收敛或达到最大迭代次数为止。当两个连续状态之间的归一化余弦相似度超过阈值 α 时，我们认为谐振器已收敛（在所有实验中，α = 0.95）。

4.2.3 谐振器网络解码准确性、容量和噪声鲁棒性的评估

我们评估了谐振器网络的准确性，作为向量维度 (D)、有效范围 (M)、模数数量 (K) 和噪声水平（依赖于 κ）的函数。在图2f所示的实验中，我们仅添加了噪声，除非另有说明，否则 K = 2。图2d中 D = 1024，图2f中 D = 512。为了计算与 M 相关的曲线的数据点，我们生成了一个递增的质数列表，并选择 K 个连续的质数作为模数。有效范围 M 是这些模数的乘积。我们继续在固定的 D 和越来越大的 M 上进行实验，直到经验准确性低于给定的阈值（图2a和2c中为0.95，其他情况下为0.05）。为了报告图2a所需的比较次数，我们将平均内积迭代次数按准确性进行归一化，并仅在高准确性范围内（95%以上）可视化曲线。

4.3 六边形余数编码

要将二维向量 x 投影到三维六边形坐标 y，我们将其乘以矩阵 Ψ：

4.4 子整数精度解码

4.4.1 编码方案向有理数的扩展

我们通过与方程4中描述的相同过程来形成余数（模 mk）的表示。如果 q 是一个整数，那么此过程与定义2.2.1一致。但一般情况下，。这很重要，因为虽然我们仍然可以通过内积来评估相似性并执行加法运算，但乘法运算则不再明确定义。

4.4.2 使用谐振器网络进行子整数解码

使用谐振器网络进行子整数解码包括三个步骤。首先，让谐振器更新其因子估计，直到收敛到一个固定点。我们强调，即使谐振器的码书中只包含整数，子整数编码也是谐振器的固定点（第2.5节）。其次，我们为每个模数找到最接近的整数码书，并生成在该解码整数范围内的分数值的最近码书（共r个）。第三，我们使用这些编码分数值的向量进行码书解码，返回我们的结果。

4.4.3 噪声情况下的子整数解码评估

我们固定 D = 512，并设置 κ = {16.0, 1.0}。我们让谐振器网络运行到最大迭代次数或收敛，并评估最接近的整数和最接近的分数状态是否正确。如果正确，我们认为解是正确的，并报告准确性和每个向量的比特数。

4.4.4 计算每个向量的比特数

为了衡量解码的总信息量，我们考虑了解码的准确性和区分的状态数量。单个数字解码的信息量（记为 I n u m ）使用相应的准确性（ a ）和总搜索空间的大小（ P ）计算，公式如下：

关于该公式的详细推导，请参见[31]的第2.2.3节。根据这一指标，当准确性处于随机水平（1/P）时，解码的信息量为0。

4.5 视觉场景分解实验

卷积稀疏编码通过最小化以下能量函数 E 为每个图像 I(x, y) 学习一组基础函数的字典 {ϕj (x, y)} 并推断出一组稀疏潜在表示 {Aj (x, y)}:

对于我们的对象示例，我们使用 MNIST 数据集中的 10 张图像。稀疏编码字典元素在 MNIST 数据集的一个子集上进行了优化。在为每个图像推断出稀疏码后，我们将其编码为高维向量（D = 10,000）。我们使用基数为 {3, 5, 7} 的余数数系统来处理水平和垂直维度，然后可以选择枚举所有 105 个单因素码书（标准方法）或使用分别具有 3、5 和 7 个码书的 3 个因素（余数方法）。在这两种情况下，我们都运行谐振器网络直到收敛到一个匹配场景表示的向量（包括重新初始化，如果在固定次数迭代后没有收敛或陷入局部最小值），并记录平均迭代次数乘以平均码书评估次数（对于余数编码来说，这个值较小）。

4.6 子集和实验

我们使用具有 3 个模数的余数数系统，{m − 1, m, m + 1}，其中 m 是一个正整数，确保我们的模数是互质的。为了生成随机子集和问题，我们首先定义一个最大和范围为 M/2。对于图6b 和 6c，m = 200，。

然后，我们从均匀分布中抽取随机变量（缩放到0和最大集合大小的和的一半之间）。我们接着选择集合的一个随机子集（所有子集的可能性相等）并计算其和。这个和作为输入提供给谐振器网络，我们认为其解决方案是正确的，如果它收敛到相同的和。如果谐振器网络返回错误的输出，我们将从不同的随机初始化重新启动它，直到达到最大试验次数。我们改变向量维度 (D) 和集合大小 (|S|)，在多次模拟后报告准确性。对于图6d，D = 400。

为了比较相对于暴力破解的方法所需的评估次数（图6e），我们记录每个集合大小的平均评估次数。我们将暴力破解评估所需的内积比较次数除以每次谐振器网络迭代所需的比较次数。此外，我们将谐振器迭代次数按准确性进行归一化，以确保公平比较。在将我们的算法与解算器进行比较时，我们实现了一个精确的子集和算法作为基准 [48]。我们设置 m = 1,000，D = {10,000, 20,000}，并从范围 [0, 5000] 中均匀抽取整数。