Fractional Binding in Vector SymbolicRepresentations for Efficient Mutual Information Exploration

向量符号表示中的分数绑定用于高效的互信息探索

https://www.compneuro.uwaterloo.ca/files/publications/furlong.2021.pdf

摘要

互信息（MI）是驱动探索的标准目标函数。使用高斯过程计算信息增益受到时间和内存复杂度的限制，这些复杂度随着观察数据数量的增加而增长。我们通过将矢量符号架构与贝叶斯线性回归相结合，提出了一种高效的MI驱动探索实现方法。我们展示了与基于高斯过程的方法相当的性能，但内存和时间复杂度在样本数量上保持恒定，而非分别随样本数量的平方和立方增长，从而实现了长期探索。

关键词——互信息采样，贝叶斯优化，矢量符号架构，分数绑定

I. 引言

互信息（MI）是量化探索过程中好奇心的标准目标函数 [1], [2]。本文以贝叶斯优化为框架来实现好奇心，并提出了一种MI驱动的探索算法，其时间和内存需求在观察数量上保持恒定，优于高斯过程方法计算MI时所需的时间复杂度 t³ 和内存复杂度 t²。

一种常见的信息采样方法是使用高斯过程（GPs）计算信息增益，例如 [3]-[6]。然而，计算MI所需的方差需要对一个与采样数据点数量 t 的平方成比例增长的矩阵进行求逆。内存的无限制增长以及评估采样位置所需时间的相应增加，与使用有限内存系统的长期运行不兼容。

为了克服高斯过程的局限性，研究人员通过高效的算法改进了占据网格方法 [7]，用于计算信息增益 [8], [9]。这些方法的复杂度通常与网格单元数量呈线性增长。然而，占据网格存在高斯过程所没有的限制——分辨率固定，且仅对网格中的点建模。这些缺点可以通过使用非规则和自适应表示（例如三角化网格或KD树）来缓解，但它们需要额外的机制来表示函数域，并需要更多内存来表示更大的区域。

我们提出了一种结合两种方法优点的算法。该算法在观察数量上的内存和时间需求是恒定的，并且与候选采样位置的数量呈线性关系，但仍能对函数域中的所有点进行定义。我们通过将矢量符号架构（VSA）中的分数绑定概念与贝叶斯线性回归（BLR）相结合实现了这一点，以建模函数域上的不确定性。

VSAs 用于建模认知过程 [10]-[14]。符号被表示为向量，而认知则通过对这些向量的操作来实现。绑定是一个关键操作，通过绑定两个现有符号 A 和 B 创建一个新符号 C，记作 C = A ~ B，通常表示 A 和 B 之间的槽填充关系。认知语义指针（Cognitive Semantic Pointers）是一种神经实现的 VSA，其绑定操作符为循环卷积。整数量、原子符号（如单词）和结构化表示（如句子）可以通过绑定在语义指针中表示。为了表示整数量，绑定会迭代整数次，记作 Sᵏ = S ~ ... ~ S，其中 k ∈ N，S ∈ Rᵈ 是一个固定维度 d 的语义指针，我们称其为“轴指针”或“轴向量”。

空间语义指针（SSPs）通过分数绑定扩展了语义指针，以表示实数 [13], [15]。分数绑定通过傅里叶变换实现，公式为 Sˣ = F⁻¹{F{S}ˣ}，其中 x ∈ R 是通过轴指针 S 的傅里叶变换逐元素指数编码的实数值。使用 SSPs 可以让我们在生物学表征与信息论模型的好奇心之间建立联系。SSPs 通过建模网格细胞和位置细胞连接到生物学 [16], [17]，这些表征与生物体的位置相关 [18]。此外，空间关系的组织可能在其他脑区中也被使用 [19]。

SSPs 通过 SSP 向量点积诱导的核函数与信息论探索建立了联系。SSPs 诱导了一个 sinc 核函数 [20]，并且 sinc 核函数已被证明是核密度估计器的高效核函数 [21], [22]。诱导核函数的向量表示可以用于构建内存和时间高效的核密度估计器，如 EXPoSE 算法 [23]。但 Schneider 等人 [23] 构建的是核密度估计器（KDE），而我们将 SSPs 与贝叶斯线性回归结合，以近似高斯过程回归。

其他方法也结合了向量表示与 BLR 来提高计算效率。ALPaCA 利用向量空间上的不确定性进行元学习 [24], [25]。Perrone 等人 [26] 将数据投影到向量空间中，以实现更高效的贝叶斯优化。然而，这些技术需要学习从输入数据到向量空间的投影。SSPs 的优势在于其表示不需要学习，而是可以设计，从而进一步提高了效率。

在本文中，我们将我们的算法——空间语义指针互信息贝叶斯优化（SSP-MI），与 [6] 中开发的高斯过程互信息贝叶斯优化（GP-MI）算法进行了性能比较。我们通过实验表明，该算法实现的后悔性能至少与 GP 算法相当，但其时间和内存复杂度在样本数量 t 上保持恒定，而基于 GP 的方法分别为 O(t³) 和 O(t²)。SSP-MI 的恒定时间和内存需求意味着它可以部署在有限硬件上进行长期运行操作。

II. 方法

两种算法都通过十个观测值进行初始化，这些观测值用于优化超参数。初始化点通过随机打乱候选位置的顺序并使用前 10 个点来选择。对于两种算法，超参数仅在初始的 10 个样本上进行优化，并且之后不再修改。

A. 实验

我们在 Himmelblau、Branin-Hoo 和 Goldstein-Price 函数上测试了这些算法，这些函数在文献 [6] 中被用作基准。我们对这些函数进行了缩放，以将问题转化为最大化问题，从而确保高斯过程超参数拟合收敛，并获得与文献 [6] 中报告的类似的后悔值。这些函数在受限域上进行评估，评估时没有添加噪声，域内的点沿着每个轴均匀分布，形成一个 100 × 100 的网格。智能体被赋予 250 次采样的预算。域和缩放因子见表 I。

III. 结果

图1在左侧展示了算法遗憾值的演变，在右侧展示了评估采样位置所花费的累积时间。阴影区域表示N=30 次试验的95%置信区间。

除了最初的几个样本外，各算法的平均遗憾值基本无法区分。表II报告了各算法的 的均值和标准差的差异。正值表示SSP-MI算法的遗憾值和标准差更低。在样本量为125和250时进行的贝叶斯假设检验发现，SSP-MI算法的性能要么优于GP-MI算法，要么与GP-MI算法在95%的概率下无法区分。在存在统计差异的地方，效应量（Cohen's d）为中等到大。在测试场景下，从遗憾值性能来看，没有理由选择GP-MI而不是SSP-MI。

SSP-MI的优势在选择采样位置的时间上变得明显。在每次迭代中，算法都会重新计算候选采样位置的采集函数。对于GP-MI，计算时间随着收集的样本数量增加而增长。对于SSP-MI，计算采集函数的时间与收集的样本数量无关，因此图1中观察到的是线性趋势.

IV. 讨论

我们已经证明了，使用生物学上合理的表示方法，基于互信息（MI）驱动的探索可以实现在连续空间中具有固定内存和计算时间限制的探索。将空间语义指针（Spatial Semantic Pointers，SSP）和贝叶斯线性回归（Bayesian Linear Regression，BLR）相结合，能够在有限的内存空间内进行操作，并在任意空间中长期运行。

在三个标准优化目标上，我们的经验遗憾值性能要么与基于高斯过程（GP）的基线方法在统计上无法区分，要么优于基线方法。与基于GP的方法不同，评估候选采样位置的时间与收集的样本数量无关，并且其内存需求为 ，其中 d 是SSP的维度，而GP-MI的内存需求为 ，其中 t 是观测数量。请注意，我们在图1中对计算时间的估计保守地包括了一次性编码成本。尽管需要超过100个样本才能摊销这一成本，但编码可以在操作开始之前完成，这将进一步有利于SSP-MI。与占用网格方法类似，评估时间随着候选位置数量的增加而线性增长，但SSP-MI仍然在连续空间中定义。

我们的算法是使用向量表示进行好奇心引导探索的初步概念验证。如果SSP是模拟认知的统一工具，如Eliasmith等 [14] 所述，那么我们的方法也可以模拟概念空间中的好奇心。然而，尽管我们使用SSP对数据进行了编码，但也可以使用其他能够诱导核函数的向量编码方法。仍有算法改进的空间。六边形SSP [17] 可能会提高编码候选采样位置的效率，并进一步将工作与空间表示的神经模型整合。对噪声的性能退化仍有待研究。

由于计算采集函数是高效的，因此在有限集合中选择采样点 x 以最大化采集函数应该是可行的，从而避免因任意采样函数域而产生的遗憾。此外，我们或许能够评估整个轨迹，而不仅仅是单个采样位置。单个SSP可以表示轨迹和空间区域，这些特性或许可以被利用来高效地评估轨迹的信息量，并通过计算点积来评估其在配置空间中的可行性。由于我们的好奇心模型是通过采集函数中的 以实现目标驱动的，因此通过调整预期奖励和信息增益的权重，可以在任务驱动的探索与类似游戏的探索之间进行切换。

我们展示了一种高效实现好奇心的方法，这可能适用于内存和时间受限的场景。尽管这项工作还处于初步阶段，但它为高效的自主探索提供了一个起点。

原文链接：https://www.compneuro.uwaterloo.ca/files/publications/furlong.2021.pdf