超维度计算中的线性码（解码性能优化）

Linear Codes for Hyperdimensional Computing

超维度计算中的线性码

https://arxiv.org/pdf/2403.03278

解读总结：

本文的核心观点是将线性码引入高维计算（HDC）领域，以提升性能、效率和可扩展性。以下是本文的重点及主要观点解读：

1. 线性码的优势：

- 线性码通过布尔线性代数定义，随机选择时具有良好的非相干性特性，与非线性码相比无性能损失。

- 其代数结构为 ⊕-恢复问题提供了快速解决方案，并显著加速了 Σ-恢复中的穷举搜索方法。

2. 高效性与存储优化：

- 线性码的生成矩阵支持高效编码（仅需异或操作），且存储需求大幅降低（只需存储生成矩阵而非整个码）。

- 验证线性码的非相干性特性比非线性码更高效，运行时间从二次关系降至线性关系。

3. 应用广泛：

- 线性码在实现数据结构（如键值存储、集合、视觉场景分析等）中表现优异，支持组合结构的表示和分解。

- 提供了几乎瞬时的恢复能力，在实验中显著优于现有的谐振网络和穷举搜索方法。

4. 未来研究方向：

- 探索线性码在近似计算中的应用，进一步优化恢复算法。

- 将线性码扩展到学习任务（如分类、聚类、回归）以及实值或复值高维计算领域。

观点总结：

本文提出了一种基于线性码的高维计算框架，解决了传统方法在效率和存储上的瓶颈，同时保持甚至提升了性能。这一方法不仅在理论上有坚实的基础，还为实际应用提供了强大的工具，展示了线性码在高维计算中的巨大潜力。

后续改进：《All You Need is Unary: End-to-End Bit-Stream Processing in Hyperdimensional Computing》

摘要

高维计算（HDC）是一种新兴的计算范式，用于将组合信息表示为高维向量，并在从机器学习到神经形态计算的广泛应用中展现出巨大的潜力。HDC 长期以来的一个挑战是如何将组合表示分解为其组成因子，这一问题被称为恢复问题。在本文中，我们提出了一种解决恢复问题的新方法，并建议使用随机线性码。这些码是布尔域上的子空间，是信息论中一个被广泛研究的主题，在数字通信中有多种应用。我们首先证明，使用随机线性码进行高维编码保留了当前主流（普通）随机码的良好特性，因此这两种方法生成的高维表示具有相当的信息存储能力。接着，我们展示了随机线性码具有一种丰富的子码结构，可以用来构建键值存储，这涵盖了 HDC 的大多数用例。最重要的是，我们证明，在我们开发的框架下，随机线性码允许简单的恢复算法来分解（无论是捆绑还是绑定的）组合表示。前者依赖于构建布尔域上的某些线性方程系统，其解可显著缩小搜索空间，并在许多情况下严格优于穷举搜索。后者利用这些码的子空间结构实现可证明正确的因式分解。两种方法都比现有的最先进的谐振网络快得多，通常快一个数量级。我们在 Python 中使用基准软件库实现了我们的技术，并展示了有前景的实验结果。

I. 引言

高维计算（HDC，也称为向量符号架构）是一种新兴的计算范式，旨在模糊信息的基于位置的普遍表示方式，其中比特的意义与其相对位置相关联 [1]。与传统计算不同，传统计算通过对象的上下文定位构建数据结构（例如列表、树、向量等），而 HDC 范式将原子项识别为无上下文比特的高维向量，然后通过各种代数操作将其用作构建更复杂数据结构的构建块——这些数据结构同样是高维（HD）向量。HDC 框架受到广泛的科学挑战和工程应用的推动，涵盖从认知模型 [2, 3, 4] 到机器学习的基础任务 [5, 6, 7, 8]，再到 DNA 测序 [9]、语音识别 [10]、机器学习硬件 [11]、机器人 [12] 等各种应用。HDC 近年来吸引了大量研究，包括几项理论研究 [13, 14] 和综述 [15, 16, 17]。

HDC 范式进一步划分为不同的架构，每种架构都指定了字母表、捆绑运算符和绑定运算符。字母表的选择决定了原子 HD 向量的条目；常见选择是“密集”（即 {±1}）、“稀疏”（即 {0, 1}），或在某些情况下复数 [5, 18]（另见 [19]）。捆绑运算符接收两个 HD 向量作为输入，并输出与两者相似的 HD 向量；常见选择是实值加法 [13, 14]、布尔 OR [5] 或多数运算符 [11]。绑定运算符接收两个 HD 向量作为输入，并输出与两者均不相似的 HD 向量。总的来说，几乎所有 HDC 工作都将绑定定义为逐点（或 Hadamard）乘积，这在密集（即 {±1}）表示的情况下等同于异或（XOR）。

显然，特定架构的选择在很大程度上取决于 HDC 实现的系统规范。在本文中，我们专注于最常见的架构，通常称为 Multiply-Add-Permute（MAP，尽管我们的方法消除了对置换操作的需求），在这种架构中，HD 向量是密集的，捆绑运算是实值加法“+”，绑定运算是异或“⊕”。

在 HDC 应用的系统规范背景下出现了各种计算挑战，其中包括回忆（即识别给定对象是否存储在内存中）、比较（即两个给定表示有多“相似”）或对 HD 表示进行训练 [7]。回忆和比较已被 [13] 理论分析，并显示出与一种称为非相干性的属性密切相关，该属性概括了不同 HD 表示之间的不相似程度，并源自准正交性 [20]。HDC 中最重要的开放问题之一，也是 [15] 综述中提到的第一个开放问题，是恢复问题。在各种应用中，人们会收到一个复杂数据结构的表示作为输入，并需要将其分解为其组成元素；输入可能是多个 HD 向量捆绑的结果（即捆绑恢复）和/或绑定这些向量的结果（即绑定恢复）。恢复是一些重要 HDC 系统（如通用键值存储，它将大多数其他数据结构实例化为特殊情况）或更具体领域应用（如视觉场景分析或搜索树查询 [21]）的关键组成部分。已经提出了几种启发式方法来处理恢复问题 [21, 22]，但迄今为止尚无严格的解决方案。

在本文中，我们的主要动机是高效的恢复算法，因此我们建议在 HDC 中使用随机线性码。“线性码”是指布尔域上的子空间，具有较大的两两汉明距离。这些对象在信息和编码理论中得到了广泛研究，主要用于通信系统中的纠错 [23]。随机选择线性码很有吸引力，因为获得具有良好特性的码的概率很高，例如较大的汉明距离。

我们首先证明，通过将 HDC 编码过程指定为随机线性码，基本上不会丢失任何东西。也就是说，如前所述，[13] 使用非相干性属性衡量的 HDC 系统的信息容量不会因在线性结构上施加编码过程而受到不利影响。事实上，随机线性码比非线性码在选择合适码的概率上提供了更好的界限。此外，使用任何线性码进行编码都可以通过简单的逻辑运算完成（特别是异或和与运算），可以在软件/硬件中轻松实现，并且需要指数级更少的空间来存储。此外，线性码还可以支持按需随机选择码字，这是 HDC 范式的核心，只需付出少量额外努力即可实现。

接着，我们继续展示在 HDC 中使用线性码所带来的显著收益，具体体现在三个方面：

1) 键值存储的简单实现，为研究和实现多种 HD 数据结构提供了一种统一的方法。

2) 在捆绑恢复问题中显著缩小搜索空间的大小。

3) 高效且可证明正确的绑定恢复问题解决方案。

我们的捆绑恢复算法依赖于对某些码字子集的穷举搜索，尽管其规模比整个码本小得多（呈指数级缩小）。然而，我们的绑定恢复算法既不依赖穷举搜索，也不依赖任何启发式方法，事实上适用于所有线性码，无论其非相干性特性如何。它基于一个简单的线性代数事实，即子空间中的向量在该子空间的一组基上具有唯一的表示，并且可以通过求解线性方程组在线性时间内找到这种表示。我们使用现成的 Python 库实现了这两种算法，并展示了令人鼓舞的结果。

具体而言，与穷举搜索相比，我们的捆绑恢复算法在运行时间上表现出显著减少，并且令人惊讶的是，在穷举搜索失败的情况下（例如由于非相干性不足），我们的算法仍然能够一致成功。此外，我们的绑定恢复算法为所有线性码提供了几乎即时且正确的解决方案，远远优于最近一种称为谐振网络技术 [21, 25] 的基准实现 [24]。例如，我们的算法通常在不到一秒内完成，而谐振网络往往需要数分钟仅用于生成所有码字的列表。我们还评论道，由于我们使用线性码的特定方式，捆绑和绑定向量的组合也可以被恢复。例如，要恢复一组绑定向量中的所有码字，可以首先应用我们的捆绑恢复算法，然后对每个结果绑定向量应用绑定恢复算法。

本文的结构如下。在第二节中，我们简要介绍了 HDC，包括 [13] 对信息容量与非相干性之间关系的分析。同样在第二节中，我们提供了布尔线性代数和线性码的基础知识，并重申了（已知的）事实，即随机线性码具有高信息容量（即低相干性），并且其概率界优于不一定线性的随机码。在第三节中，展示了线性码的子码结构如何适应键值存储的简单实现，这将 HDC 的大多数用例作为特殊情况实例化。为了说明我们构建键值存储的统一方法的优势，我们提供了几个特殊案例的例子，其中我们的方法涵盖了有限集、向量（序列）、搜索树和视觉场景分析。在第四节中，我们提出了捆绑和绑定恢复算法，并正式证明了它们的保证。第五节提供了实验结果，第六节得出了结论。

II. 预备知识

我们在第二节 A 部分开始介绍 HDC，从理论角度展示 HDC 并聚焦于恢复问题。随后，我们对线性码进行简要介绍，使读者熟悉布尔代数和编码理论，并展示 HDC 和编码理论之间的若干相似之处。

A. 高维计算 (HDC)

更复杂的数据结构（如句子或图像）通过原子向量的代数操作获得。许多框架被提出以促进这些操作，其中我们重点关注最常见的 Multiply, Add, Permute (MAP) 框架 [3]。总的来说，所有这些框架都包含“绑定”和“捆绑”操作。在 MAP 框架中，用于生成与两个输入向量相似的向量的捆绑操作通过普通整数加法实现，记作“+”。绑定操作通过逐点乘积（或 Hadamard 积）实现，记作“⊕”。

B. 线性码简介

a) µ-非相干码与 ǫ-平衡码

如第 II-A 节所述，成功的高维计算（HDC）的核心在于使用 µ-非相干码 （定义 1），更重要的是，随机（不一定是线性的）码以高概率满足 µ-非相干性。我们现在展示一个简单的事实，即 µ-非相干码等价于 ǫ-平衡码 ；ǫ-平衡线性码 是一个被广泛研究的概念 [27, 28, 29, 30]，在计算机科学中有广泛的应用。

III. 基于线性码的键值存储

我们现在展示如何利用线性码实现高维键值（KV）存储。一些提议的技术需要使用 ⊕-恢复和 Σ-恢复算法；目前我们将这些算法视为黑箱，并在后文详细阐述。

键值（KV）存储是一种基本的数据结构，它用索引（键）存储条目（值），并应能够回答“给定键对应的值是什么？”这样的查询。在本节中，我们将展示为键和值进行线性编码提供了一种使用高维向量维护 KV 存储的框架。我们首先介绍 KV 存储必须支持的基本操作，展示如何使用线性码在实践中实现这些操作，证明其正确性并分析复杂度。

随后，我们展示我们的框架可以无缝扩展（再次利用子码结构）到键或值（或两者）具有组合结构的情况，即某个给定的键（或值）可以进一步分解为具有某种上下文意义的原子部分。一个需要这种组合结构的例子是将搜索树实现为高维向量；由于键表示该树中的路径，它们可以进一步分解为表示该路径的一系列整数。最后，为了展示我们框架的通用性，我们演示了其在存储集合和向量（序列）、视觉场景分析以及搜索树中的应用。

形式上，一个 KV 存储 S 是由形如 k, v 的键值对组成的集合，其中键 k 来自某个集合 K ，值 v 来自某个集合 V ，并且存储的键必须彼此不同（允许值相同）。 S 的大小，即其中键值对的数量，记为 s 。KV 存储必须支持以下操作：

从定理 1 可以明显看出，在选项 (A) 和选项 (B) 之间进行选择的关键因素是密钥空间 |V| 的大小，相对于执行 Σ-恢复算法和 s 次奇偶校验的复杂性之间的权衡。

A. 组合键和组合值

在高维计算的许多应用中，需要一组具有组合结构的键或值。例如，在表示搜索树的键值存储（KV-store）中，一个键 k 表示树中的一条路径，而一个值 v 表示该路径末端叶子节点的内容（详见随后的第 III-B 节中的详细示例）。在这种情况下，路径是组合性的，因为它描述了在 q-叉树中从根节点出发应沿着哪些 q 个兄弟节点行进以到达指定的叶子节点。

另一个例子是视觉场景分析（也将在第 III-B 节中详细讨论），即每个“场景”是一个“键存储”（即具有单一元素的平凡值集 V 的 KV-store）。每个场景是由场景中多个对象的捆绑组成的，而每个对象则是由多个属性（如类型、颜色、位置等）绑定而成的。因此，每个这样的键（或对象）是组合性的，因为它通过绑定多个高维向量生成。如果要对场景的高维表示进行因式分解，首先会应用 Σ-恢复来获取场景中所有单个对象的列表，然后对每个对象进一步应用 ⊕-恢复以提取其颜色、位置等属性。

B. 示例
在本节中，我们将展示上述键值存储（KV-store）实现如何通过适当选择一个非相干码 C 及其子码 K 和 V，涵盖文献中最近讨论的许多高维数据结构用例。

1) 有限集合

可以说是最简单的数据结构，有限集合必须支持添加和删除元素，以及测试某个给定元素是否属于该集合。为了存储来自全集 K 的大小至多为 s 的集合，按照第 III 节中的构造方法进行如下操作：

定理 1 表明，这些过程能够以规定的复杂度正确实现集合操作。

备注 3 ：如果不希望预先选择整个码 C，或者 K 中元素的比特表示不可用，则可以通过轻量级的簿记动态随机选择码字，同时保持 C 的线性结构。详细内容见附录 B。

备注 4 ：使用线性码构建的集合数据结构在假设的非相干性方面与使用不一定线性的码构建的结构相同，因此它们的信息容量（即保证成功执行添加、删除和成员操作的最大集合大小 s）也相同。因此，任何依赖于底层码相干性证明的性质都会自动被我们的线性码变体继承。例如，我们使用线性码表示集合的方法自动继承了 [13, 定理 8、9、10] 中提到的大小估计、交集计算和噪声鲁棒性。

4) 视觉场景分析

另一个展示线性码组合能力的用例是一种描述场景的数据结构，该场景包含叠加的对象，每个对象包含多个属性。例如，想象一幅图片，其中有多个数字以不同的位置和颜色叠加在一起 [21, 图 3]。人们希望构建一个单一的高维向量来描述这样的场景，以便能够高效解码，即给定的组合高维向量可以被分解为其组成对象，而每个对象可以进一步分解为其组成属性。一个自然的解决方案是使用四个码分别描述对象的颜色、数字、纬度和经度。然后，场景是对对象向量的捆绑，每个对象向量是从这些码中各取一个码字的绑定结果。我们评论说，这种技术在为机器学习模型添加推理能力方面非常有用。通过训练这些模型识别组合结构，然后将这些结构解码为其组成元素，可以极大地提高这些模型的解释能力。

我们还评论说，为了在机器学习中成功应用该技术（见上文），必须能够处理噪声。也就是说，一个训练用于输出组合向量的机器学习模型极有可能犯某些错误（例如，由于模型最后一层激活函数的输入不准确而导致的比特翻转）。为了纠正这种情况，必须在将其输入我们的 Σ-恢复和 ⊕-恢复算法之前，应用额外的解码算法来去除噪声。

IV. 恢复算法

一般来说，这是一个困难的问题，尽管作者尚未发现任何关于该问题的复杂性结果（例如，NP 完全性）。在 [21, 25] 中提出了一种使用谐振网络的启发式解决方案。然而，正如我们即将展示的，如果 是线性码，则该问题可以通过直接的布尔代数求解。

备注 8：我们的实验表明，这些界限是过于悲观的，我们的算法通常比穷举搜索快一个数量级。

备注 9：需要提到的是，一个类似于线性码的 Σ-恢复问题的研究此前已经存在。所谓的二进制加法信道 [36] 是一种多发送方与单接收方之间的通信模型，接收方接收到发送方二进制消息的和，并需要将该和分解为其组成元素。然而，在二进制加法信道中没有“召回”的概念，因此针对二进制加法信道的传统码构造不一定是非相干的，这使得它们不适合用于高维计算（HDC）。此外，针对二进制加法信道的传统码构造通常不是线性的。一个例外是 [37]，它研究了带有两个发送方和线性码的二进制加法信道，并提出了一种解码算法，这是上述 s = 2 的 Σ-恢复算法的一个特例。

V. 实验

A. 当前最先进的方法

当前最先进的 ⊕-恢复和 Σ-恢复方法是谐振网络 [21, 25]，以及其改进版本 [26] 和 [38]。尽管谐振网络从形式上是为了处理 ⊕-恢复问题而设计的（见 [25, 第 2 节]），但它们可以通过“解释消除”扩展到执行 Σ-恢复。也就是说，实验表明（例如 [21, 图 4]），如果对捆绑的绑定向量应用谐振网络，网络往往会收敛到其中一个绑定向量，然后可以从捆绑中减去或“解释消除”该向量。

具体来说，在谐振网络中，为每个输入子码维护一个估计向量。在收敛后，这些估计向量被绑定，生成的绑定向量作为输出，并从输入向量中减去。减去之后，可以再次应用谐振网络，直到最终得到零向量（或接近零向量）。

第六章 总结与讨论

本文提出在高维计算（HDC）中使用线性码，这些码通过布尔线性代数定义。当随机选择时，这些码相对于不一定线性的码保留了良好的非相干性特性，因此可以在不损失性能的情况下安全地用于 HDC。然而，它们的代数结构为 ⊕-恢复问题提供了几乎即时的解决方案，并可用于显著加速 Σ-恢复中的穷举搜索方法。

另一个额外的好处是可以更快地验证线性码是否具有某些非相干性特性，相较于非线性码更为高效。在关键应用中，人们希望确保随机选择的码确实具有所需的非相干性特性。为了验证非线性码的非相干性，必须计算任何两个码字之间的内积，导致运行时间与码的大小呈二次关系。然而，由于非相干性与最小距离（在所有码中）以及最小距离与最小重量（在线性码中，见定义 2 及其后续讨论）之间的等价性，验证线性码的非相干性只需要验证最小重量。这使得运行时间与码的大小呈线性关系。

未来工作的方向非常广泛，其中最显著的方向似乎是研究用于近似计算的线性码（计算应以高概率成功），以及寻找更快的 Σ-恢复算法。此外，我们的重点在于诸如召回、恢复和各种数据结构的实现等简单计算任务；线性码在更面向学习的任务（如分类、聚类或回归 [41]）中的作用仍有待探讨。最后，编码理论方法可能会在二值域之外找到用途，编码理论思想在实值 [13] 或复值 [5] HDC 中的应用仍有待研究。

后续：《单比特流处理：超维计算中的端到端比特流处理》

原文链接：https://arxiv.org/pdf/2403.03278