高维向量计算

Computing with high-dimensional vectors

高维向量计算

https://scholar.google.com/scholar?cluster=11620543245696520872&oi=gsr-r&hl=zh-CN&as_sdt=0,5

摘要 -

“计算能力”通常意味着数字、速度、高精度运算、大内存、以不妥协的可靠性和合理的能源需求运行。这些要求之间的矛盾导致计算能力增长放缓，通俗地说就是“摩尔定律失去了动力”。在这里，我们考虑通过计算高维（10,000维）向量来增加计算能力的可能性，这些向量不需要极其可靠或精确。理论可以指导纳米技术的发展，应用广泛存在于现在属于人工智能、神经网络和深度学习领域的各个领域。

关键词 - 计算代数、全息减少表示、鲁棒性、能效、并行性、纳米技术

I. 大规模计算

我们通常认为计算是操作位、数字和内存指针，我们用专门用于布尔逻辑、算术和内存的电路构建计算机。所有其他东西都是通过将这些基本操作组织成程序来构建的。冯·诺依曼架构的天才之处在于程序存储在内存中，并使用与数据相同的操作进行操作 - 对机器来说，程序就是数据。由此产生的灵活性导致了编译器和符号编程的出现，这反过来又使得将无穷无尽的任务视为计算成为可能。

第一台数字计算机被设计用于计算，它们取代了被称为“计算机”的专业人员，这些专业人员使用计算器和对数表等工具工作。数字计算机很快取代了对数表等的需求，随着时间的推移，越来越多地用于记录保存，正如我们见证的主机时代。计算和记录保存都需要准确性和可靠性，因此计算机被设计为以确定性机器运行：相同的输入总是产生相同的输出。尽管确定性是一个无法实现的理想，但通过使用数字逻辑和宽设计裕度可以实现近乎完美的操作。传统的计算理论假设确定性，并仅处理由于数字表示精度而产生的不准确性，这催生了数值分析。

然而，高速运行的可靠性是有代价的：它需要大量的能量。减小电路元件的尺寸已经减少了它们的运行所需能量，但我们正接近一个极限，超过这个极限，尺寸的进一步减小会使电路变得不可靠。我们只能在物理允许的范围内推动发展，否则事物将开始崩溃。同时，计算机越来越多地被用于不需要终极速度、精度和可靠性的应用，或者在这些应用中，所需的可靠性是通过非超可靠电路元件的其他手段实现的。这类功能的典型例子来自神经科学。

动物大脑是自然界中最接近计算机的事物。作为数百万年进化的产物，它们对于它们所服务的功能来说可能是接近最优的。大脑轻松完成的许多事情，我们试图用计算机来完成，但充其量只能部分成功。它们涉及的行为使动物能够在不断变化的世界中生存和繁荣。非常笼统地说，我们的大脑使我们能够理解和对周围发生的事情做出反应。这在计算机术语中意味着什么；关于构建用于这些和类似功能的计算机，我们可以得出什么结论？

粗略检查大脑显示其电路非常大（扇入和扇出可以达到数万），布局没有规定到最后的细节，活动在电路内部和不同电路之间广泛分布，单个神经元不需要特别可靠（神经元可以死亡），它们运行所需的能量非常少——人脑大约运行在20瓦特。所有这些都与计算机的构建和运行方式如此不同，以至于我们需要重新思考和扩展我们对计算的模型。

受大脑电路启发的计算模型和数字计算机一样古老[1]。这些模型被称为人工神经网络，它们在认知科学研究中发挥了重要作用，现在作为深度学习网络被商业化。神经网络模型建立在线性代数之上，它们使用向量和矩阵进行计算。它们在标准计算机上使用精确算法（如梯度下降和主成分）进行训练。训练是计算密集型的，尽管最终的网络可以快速运行并且运行所需的能量非常少。这些网络是特定于问题的，缺乏我们与大脑控制的行为相关的灵活性和适应性。

在本文中，我们考虑了使用高维随机向量作为基本对象进行计算的可能性，与之对比的是使用位和数字的传统计算。这种计算方式由Plate在1990年代初提出，在《全息减少表示》[2]一书中进行了彻底讨论，并在《超维计算》[3]的论文中进行了简化。

操作涉及向量，即使是通过位和数字实现的。存在一种加法运算和一种乘法运算，它们保持向量的维度。此外，向量使得可以使用坐标排列作为第三种操作——事实上，排列为我们提供了除加法和乘法之外大量可能的操作。计算高维向量的能力部分来自于高维度（例如，n = 10,000），部分来自于操作及其相互之间的交互，即它们的代数。底层数学与线性代数有很多共同点，但方法足够不同，值得更仔细的检查。

II. 高维计算：一个例子

我们将通过一个例子演示这三种操作：根据字母使用统计识别语言（不依赖字典）。对于每种语言，我们从大约一百万字的文本中计算出一个高维配置文件向量。我们使用相同的算法计算测试句子的配置文件，然后将其与语言配置文件进行比较，选择最相似的一个作为系统的答案。

我们例子中的配置文件基于称为三元组的三个字母序列，它们的计算方法如下。首先，字母表中的字母被分配n维随机向量，其中包含+1和-1。所有语言和测试句子都使用相同的字母向量。字母向量用于通过排列和乘法制作三元组向量。例如，三元组the的向量是通过两次排列t向量，排列h向量一次，保持e向量不变，并将三个组件逐位相乘来计算的。这产生了一个随机放置的±1的n维三元组向量。最后，通过一次一个三元组地遍历文本，将三元组向量相加到配置文件向量中。结果是一个n维整数向量。这些向量的余弦可以用来衡量它们的相似性。

在涉及21个欧洲联盟语言的这样一个实验中，得到了以下结果[4]。所有向量都是10,000维的。语言配置文件根据语言家族进行聚类：波罗的海、日耳曼、罗曼、斯拉夫。当测试句子配置文件与语言配置文件进行比较时，97%的时间选择了正确的语言，当查询英语中th之后最常出现的字母的配置文件时，答案是e。算法的数学基础将在下面解释。

III. 高维向量与鲁棒性

我们习惯了这样的想法：如果A接近B，B接近C，那么A不可能离C很远。如果我们从给定距离内“领土”（向量/点的数量）的角度来考虑，这种直觉在10,000维空间中完全不适用。在二维空间中，距离加倍会使领土增加四倍，而在高维空间中，它可能增加数十亿倍。例如，对于10,000位的向量，其中仅有十亿分之一的向量与任意向量A的距离在4,700位以内，但几乎所有向量都位于5,300位以内。将汉明距离从4,700增加到5,300，领土将增加十亿倍。实际上，这意味着，例如，如果使用10,000位来表示一个人，超过三分之一的位可以在时间上发生变化或被噪声或故障破坏，而产生的位向量仍然比任何其他人的10,000位表示更接近原始向量。这种情况在大的高维空间中是普遍存在的，被称为测度集中现象。

这种类型的鲁棒性对于自然界中的动物至关重要，因为事物永远不会完全重复，因此对于大脑来说，能够识别相似的感觉刺激为相同（不相似的为不同）是至关重要的。即使单个神经元功能不稳定或死亡，大脑也能做到这一点。这种能力可以基于用高维向量表示世界和其中的事物，并用这些向量进行计算。一旦原则上理解了这一点，我们就可以开始构建具有类似能力的系统。

要从高维固有的鲁棒性中受益，系统必须能够将新输入与系统内存中已存储的事物识别出来。这个功能被称为联想记忆，本质上是存储在内存中的向量之间的最近邻搜索。在高维计算提出的工程挑战中，联想记忆可能被证明是最苛刻的。

IV. 向量操作及其代数

首先要注意的是，向量没有被细分为不重叠的字段。编码到向量中的任何内容都均匀分布在其所有组件上。因此，向量的任何部分都代表与整个向量相同的东西，只是可靠性较低。这种表示被称为全息或整体的。然而，可以使用全息向量的三种操作来编码和解码普通计算中熟悉的所有数据结构——集合、序列、列表，即加法、乘法和排列，以及相似性度量。这些操作具体是什么，取决于向量的性质，无论是二进制、双极、整数、实数还是复数。在语言示例中，我们使用了具有等概率的+1和-1的n维随机双极向量（向量平均值为0）：。不同种类的高维向量共享这些属性，但在双极向量中最容易演示。向量的相似性基于距离。上面使用汉明距离来说明鲁棒性。点积A · B可以用于双极向量，它从-n（向量相反）变化到n（它们相同）。余弦和（皮尔逊）相关性也可以使用，其中余弦（或相关性）= 1表示向量最相似（相同），0表示它们最不相似或正交，-1表示它们相反。两个随机选择的双极向量的余弦接近于0——向量是准正交的。

数字计算的多功能性部分是因为加法和乘法构成了一个称为域的代数结构。我们可以期待使用高维向量进行计算同样强大，因为加法和乘法近似于一个域，并且与排列相结合，在有用的方式来补充加法和乘法。

A. 再次审视语言识别：数学运算详解

我们通过一个例子引入了高维计算，即从三元组统计数据中识别语言。让我们从操作及其属性的角度来审视算法。字母表中的字母由10,000维的随机、独立、同分布（i.i.d.）、等概率的±1向量A、B、C等表示，因此它们大致上彼此正交。通过排列和乘法制作的三元组向量也大致上彼此正交，并且与字母向量正交，因为乘法和排列（在例子中使用了坐标旋转）产生的向量与它们的参数不相似。然而，加法产生的向量与它们的参数相似，因此语言配置文件向量类似于加入其中的每个三元组向量。这就是为什么相似的三元组直方图产生相似的语言配置文件——语言配置文件不过是被随机投影到10,000维的直方图。最后，通过将英语配置文件与（ρ2(T) ∗ ρ(H)的逆）相乘，找到了在英语中th之后最常出现的字母。

乘法分布在配置文件中加入的每个三元组上，并在任何地方取消初始的th。特别是，它从三元组向量the中释放出E，即从ρ2(T) ∗ ρ(H) ∗ E中释放；它也释放出跟在th后面的任何其他字母，但由于e是最频繁的，E与转换后的配置文件具有最高的点积。它的期望值是th后面es的数量的10,000倍。

请注意，点积与配置文件向量和三元组向量the之间的点积相同。

这个例子展示了高维计算的重要方面。相同的算法用于训练和制作测试句子的配置文件。算法非常简单，它容易适应于广泛的分类问题，并且它在单次数据遍历中工作——算法是增量的。频率和概率可以通过逆转用于编码配置文件的操作来近似恢复——表示是透明的。

B. 非双极向量

使用双极向量演示操作特别简单，因为逐位加法和乘法使用普通算术。然而，这个想法更加通用：向量可以是二进制的、实数的或复数的，只要它们是高维的。每种类型都存在适当的加法和乘法操作符，并且所有向量都可以排列。

基于二进制向量的系统最简单易行。密集二进制（等概率的0和1）在数学上等同于双极：双极1映射到二进制0，加法变成逐位阈值（多数）求和，带有打破平局的政策，乘法变成XOR，向量的相似性基于汉明距离。基于实数向量的系统使用从均值为0、方差为1/n的正态分布中随机抽取的分量。加法是普通向量加法后跟归一化，乘法是通过循环卷积，向量的相似性基于归一化向量之间的欧几里得距离。基于复数向量的系统使用随机相位角作为分量，加法是向量加法后跟归一化，乘法是逐位相加相位角，两个向量的相似性基于它们差异的长度。使用复数向量的高维计算很可能是相对于潜在振荡或时钟的尖峰时间进行计算的模型。

这些不同的框架实际上是相互关联的。二进制与双极的等价性已经被讨论过。实数和复数通过快速傅里叶变换（FFT）相关联，当相位角限制为0和π时，双极与复数等价[2]。

V. 小规模实验与大规模应用

高维计算已经在语言识别[4, 5]和生物信号分类[6]的实验中得到演示，并在商业上用于制造语义向量。这些实验专注于算法的简单性、透明性和通用性，它们对组件变化和故障的容忍度，适合并行执行，以及能效。

简单性和透明性来自于上一节指出的操作代数。我们可以通过观察操作与联想记忆一起足以实现一个完全通用的编程语言（如Lisp）来论证通用性。

高维计算的鲁棒性是极端冗余的结果，这种冗余来自于分布式（全息）表示，其中每个坐标独立于其他坐标计算相同的事情，尽管精度非常低。例如，忽略一半的坐标允许算法在产生不太可靠的结果的同时工作。此外，坐标的独立性允许它们并行计算：在10,000维中，所有10,000个坐标可以同时进行加法或乘法，因为不必担心进位，就像数字算术那样。排列是唯一跨坐标操作的操作，它仅通过重新排序它们来实现。

我们已经注意到大脑在不断变化的世界中无与伦比的学习和适应能力，仿佛它拥有一台运行在极少能量上的超级计算机的能力。类似大脑的计算并不需要在千兆赫兹速率下切换的超可靠组件。如果速率低，我们可以以非常少的能量进行计算，而且我们可以容忍偶尔出现变化和故障的组件。这种计算的理论最有可能在其核心包含高维向量[7]。

高维计算已经被瑞典文本分析公司Gavagai AB（成立于2008年）商业化使用，网址为 http://gavagai.se/about/ 。其服务基于一种称为随机索引的高维向量算法[8]，这是一种随机投影的形式。该算法体现了语言学中的分布假设，通过2,000维的语义向量来实现。语义向量背后的思想是，具有相似意义的词汇具有相似的语义向量，这在搜索引擎中很有用。该算法通过为词汇表中的每个单词分配一个随机索引向量——一个2,000维的随机标签——来工作，类似于语言识别实验中的随机字母向量。然后，这些随机标签被用来通过阅读文本来为单词制作语义向量。每次单词出现时，它的语义向量就会通过添加相邻单词的随机标签来更新，通常是两边的两到三个单词，称为上下文窗口。作为和向量，语义向量与它们上下文单词的随机标签相似，因此共享的上下文产生相似的语义向量。

更知名的语义向量算法包括潜在语义分析（LSA）[9]和Word2vec[10]，这两种算法都没有采用高维性和随机性。LSA使用奇异值分解制作几百维的语义向量，当词汇量增长到数十万，文档数量增长到数百万时，它变得不切实际。Word2vec能够更好地处理大型数据集。它的语义向量是优化问题的一个解决方案，这个问题被表述为单词和短语在大型文本语料库中预测附近单词和短语的能力。该算法涉及显式地制表频率和概率，并通过在高维向量空间中的梯度下降来解决问题——维度通常是1,000或更少。相比之下，在基于代数的高维向量计算中，我们尽量避免显式制表概率和计算梯度，因为它们的计算成本，也因为这样做会将批量处理引入数据流中。

关于您提到的网页 http://gavagai.se/about/ ，由于网络原因，我无法获取该网页的内容。这可能是由于链接不正确或网络连接问题。请检查链接的有效性并稍后重试。如果您有其他问题或需要进一步的帮助，请随时告诉我。

今天使用的所有语义向量实际上都是相当粗糙的。它们捕捉到了单词意义的元素，但缺乏语言结构。语言的结构分析和语法对意义的重要性一直是符号人工智能的领域。然而，我们可以期待这种情况会改变，这要归功于高维向量操作编码（语法）结构的能力。这是语言理解研究的一个明显主题。

VI. 前景和机遇

我们在文章开头强调了大脑用缓慢、低精度、不可靠的组件产生对我们生存至关重要的有趣行为的能力，并将其与我们通常与计算能力相关的特征：速度、精度和可靠性进行了对比。大脑和计算机共享并从中获得力量的一件事就是大容量的内存。如果一个突触代表一个比特的信息，那么人脑就相当于30兆字节。

无论使用高维向量计算是否解释了大脑的计算，都可以在计算代数的基础上建立一系列新的机器学习算法。这些算法可以将从数据中进行的统计学习与数据结构的构建和操作结合起来。由于操作的属性（如分配律和可逆性），代数使算法变得透明。透明性通常被认为是基于规则的系统的优势，并与被比作黑箱的神经网络的不透明性形成对比。

高维向量操作简单，并且适合增量（在线、“一次性”）学习，如在计算语言配置文件和语义向量时所见。正如已经指出的，它们也适合高度并行处理。

我们已经用语言和生物信号分类的例子证明了高维计算的合理性。这些是明显的应用领域，但理论暗示了更多。当一个来源的信号在高维空间中以伪随机向量表示时，它可以很容易地与以类似方式表示的其他来源的信号结合，它们的联合统计数据随后可以被捕获在高维向量中。此外，通过与可逆向量操作相结合，可以追溯到不同来源的贡献。这表明高维计算可以用于多传感器集成，从而在传感、监控、控制和机器人技术中应用。

整体架构将模仿神经生物学。它将由特定于传感器的前端处理器、高维向量处理器、高维内存和特定于效应器的后端处理器组成。前端处理将把原始感官输入转换为伪随机向量，后端处理将产生驱动电机的信号，而集成和在线学习将使用向量操作在高维空间中进行。传统的神经网络和深度学习在这个架构中也有一席之地，即作为可训练的前端和后端处理器。

由于不同感觉模式的信号——例如，视觉、声音和触觉——非常不同，它们需要非常特定的预处理才能使它们成为适合集成的向量。只要最终系统快速，这种外围处理器的训练就可以慢。这再次与生物学相符，当我们还是孩子的时候学习一种语言的声音，而作为成年人无法听到另一种语言所依赖的区别。将深度学习与高维计算相结合的策略已在图像分析的初步实验中显示出效果。

高维计算的要求与纳米技术的性质之间显著的一致性不应被忽视。随着电子组件变得更小，被构建进越来越大的电路中，并且需要以很少的能量运行，它们的运行变得容易出错。当用作传统数字计算机的组件时，每个比特都必须非常可靠。这是通过使电路冗余来实现的，但这在材料和能量上都有成本。显然存在一个物理极限，超过这个极限，进一步的微型化不再划算。

全息表示也是冗余的，但在比特级别上不需要高可靠性。这本身就可以节省能量，如果我们利用材料的模拟特性，例如可编程电阻，这种节省甚至可以更大。使用高维向量运行可以从具有比二进制更宽范围的存储元素中受益。

传统计算机的数字算术和逻辑需要复杂的电路，这些电路被构建进物理上与内存分离的算术逻辑单元（ALU）中。这造成了不断需要在两者之间移动数据的永久需求。与数字算术相比，高维向量操作非常简单，像逐位XOR这样的操作可以内置到内存中，消除了将10,000位向量移入和移出一个ALU的需要。通过分布式算术，这种“内存内计算”节省了时间和能量[6]。

传统计算在许多领域都提供了非常好的服务。然而，也有一些领域，我们长期以来的努力并没有产生我们所希望的结果。特别是，掌握依赖于日常情境中学习的任务证明特别困难。通过使用高维向量进行计算，我们希望能够在这些领域取得进展。

为了突出差异，被送往木星卫星的火箭将由传统计算机控制，但探索卫星的机器人将拥有一个使用高维向量进行计算的大脑。

原文链接：https://scholar.google.com/scholar?cluster=11620543245696520872&oi=gsr-r&hl=zh-CN&as_sdt=0,5