【AI学习】Mamba学习（七）：HiPPO通用框架介绍

标签：HiPPO 函数框架 AI 多项式时间尺度投影 Mamba

HiPPO这篇论文《HiPPO: Recurrent Memory with Optimal Polynomial Projections》，提出了一个通用框架。
我们再重新看一下论文的摘要：
从连续数据中学习的一个核心问题是，随着更多数据的处理，以增量方式表示累积历史。我们介绍了一个通用框架（HiPPO），用于通过投影到多项式基上对连续信号和离散时间序列进行在线压缩。给定一个指定过去每个时间步长重要性的度量，HiPPO会产生一个自然在线函数近似问题的最优解。作为特例，我们的框架从第一性原理中对最近的勒让德记忆单元（LMU）进行了简短的推导，并推广了循环神经网络（如GRU）的普遍门控机制。这种形式化框架产生了一种新的内存更新机制（HiPPO LegS），该机制可随时间扩展以记住所有历史，避免在时间尺度上出现先验。HiPPO LegS具有时间尺度鲁棒性、快速更新和有界梯度的理论优势。通过将记忆动态结合到循环神经网络中，HiPPO-RNN可以经验性地捕捉复杂的时间依赖性。在打乱顺序的基准MNIST数据集上，HiPPO LegS设定了98.3%的最新精度。最后，在一项新的轨迹分类任务中，测试了对分布外时间尺度和缺失数据的鲁棒性，HiPPO-LegS的准确率比RNN和神经ODE基线高出25-40%。

一、方案介绍

摘要过于浓缩，看完后肯定理解不深入，继续看介绍部分。

作者在介绍的第一段，首先提出一个基本问题。

“从序列数据中建模和学习是现代机器学习中的一个基本问题，其基础任务包括语言建模、语音识别、视频处理和强化学习。对长期和复杂的时间依赖关系进行建模的一个核心方面是内存，即存储和合并来自先前时间步骤的信息。挑战在于使用有界存储来学习整个累积历史的表示，随着收到更多数据，必须在线更新。”

从这段描述，我联想到，是否人类的记忆也是面临同样的问题。脑容量（对应上面所述的内存）有限，而每天都有接收大量的信息输入，包括音视频、文字、其他感官等多种模态的输入，而人类的记忆也是不停的在线更新。所以，我认为，作者提出的这个基本问题，是一个非常本质的问题，是一个可能涉及有关人类的记忆这种智能机制的问题。

接下来，作者提到了已有的方法和存在的问题：

“一种既定的方法是对一个随着时间的推移而演变的状态进行建模，因为它包含了更多的信息。这种方法的深度学习实例是递归神经网络（RNN），众所周知，它存在有限的记忆范围[34,38,56]（例如，“消失梯度”问题）。尽管已经提出了各种启发式方法来克服这一点，例如成功的LSTM和GRU[34,16]中的门，或最近的傅里叶循环单元[79]和勒让德存储单元（LMU）[71]中的高阶频率，但对记忆的统一理解仍然是一个挑战。此外，现有的方法通常需要序列长度或时间尺度上的先验，在这个范围之外是无效的[66,71]；这在具有分布偏移的环境中可能是有问题的（例如，由于医学数据中的不同仪器采样率[62，63]）。最后，它们大多缺乏对如何捕捉长期依赖性的理论保证，比如梯度界限。为了设计更好的记忆表示，我们理想的情况是（i）对这些现有方法有一个统一的看法，（ii）能够解决任何长度的依赖关系，而不需要时间尺度上的先验，以及（iii）对它们的记忆机制有严格的理论理解。”

针对问题，作者提出了解决方法，即通过将函数投影到正交多项式（OP）的方法实现在线近似，并形成了新的框架：HiPPO框架（high-order polynomial projection operators）：

“我们的见解是将短语记忆视为在线函数近似的技术问题，其中函数 f（t）：ℝ+→ℝ
通过将其最优系数存储在一些基函数中来概括。根据指定过去每个时间重要性的度量来评估这种近似值。给定此函数近似公式，正交多项式（OP）作为自然基出现，因为它们的最优系数可以用封闭形式表示[14]。凭借其丰富而深入研究的历史[65]，以及在近似理论[68]和信号处理[57]中的广泛应用，OP为这个记忆表示问题带来了一系列技术。我们形式化了一个框架HiPPO（高阶多项式投影算子），它产生了将任意函数投影到给定度量的正交多项式空间上的算子。这个通用框架允许我们分析几个度量家族，其中该算子作为闭式常微分方程或线性递归，允许在输入函数随时间变化时快速增量更新最优多项式近似值。”

作者进一步指出HiPPO框架和已有方法的关系、HiPPO框架的优势:

“通过在循环序列模型下提出一个形式化的优化问题，HiPPO框架（第2节）概括并解释了以前的方法，解锁了适用于不同时间尺度的序列数据的新方法，并提供了几个理论保证。（i）例如，通过简短的推导，我们可以精确地恢复LMU[71]（第2.3节）的特殊情况，它提出了一种更新规则，可以随着时间的推移投影到固定长度的滑动窗口上。HiPPO还为LSTM和GRU的门控机制等经典技术提供了新的见解，这些技术在一个极端中仅使用近似中的低阶度（第2.5节）。（ii）通过选择更合适的度量，HiPPO产生了一种新的机制（Scaled Legendre或LegS），该机制始终考虑函数的完整历史，而不是滑动窗口。这种灵活性消除了对序列长度的超参数或先验的需求，使LegS能够推广到不同的输入时间尺度。（iii）与动力系统和近似理论的联系使我们能够展示HiPPO LegS的几个理论优势：对输入时间尺度的不变性、渐近更有效的更新以及梯度流和近似误差的界限（第3节）。”

最后，说明一下方法的验证效果：

“我们将HiPPO记忆机制整合到RNN中，并实证表明，它们在用于评估长期依赖性的标准任务上优于基线。在置换的MNIST数据集上，我们的无超参数HiPPO-LegS方法实现了98.3%的最新精度，比之前的RNN SoTA高出1个百分点以上，甚至优于具有全局上下文的模型，如transformer（第4.1节）。接下来，我们在一项新的轨迹分类任务上证明了HiPPO LegS的时间尺度鲁棒性，它能够泛化到看不见的时间尺度并处理缺失的数据，而RNN和神经ODE基线则失败了（第4.2节）。最后，我们验证了HiPPO的理论，包括计算效率和可扩展性，允许在数百万个时间步长内快速准确地进行在线函数重建（第4.3节）。复制我们实验的代码可在https://github.com/HazyResearch/hippo-code.”

一点说明

作者提到，LSTM和GRU的门控机制是使用近似的低阶度，这个没看到后面的方法不好理解。做一个解释，作者给出的通用的方法，是通过将函数投影到正交多项式，而LSTM和GRU也是这种OP投影方法的特例，只不过投影的阶数比较低，而HiPPO，使用了高阶多项式投影，也就是high-order polynomial projection operators。

二、具体案例

阅读了方案介绍，我们停下来，看一个案例。
苏神在《重温被Mamba带火的SSM：线性系统和HiPPO矩阵》一文中，以傅里叶级数为例，给出了一个精彩的案例，因为傅里叶级数大家都比较熟悉，所以根据容易理解。
按照论文作者指出：框架HiPPO（高阶多项式投影算子），是将任意函数投影到给定度量的正交多项式空间上的算子。理论上，这个正交多项式可以有很多选择，所以才是才能叫做框架！那么，当然，傅里叶级数也是可以的。作者没有选傅里叶技术，相比傅里叶基，勒让德多项式的好处是它是纯粹定义在实数空间中的，并且多项式的形式能够有助于简化后面的推导过程，并且采用勒让德（Legendre）多项式的推导得到的矩阵形式有后续的高效计算方法，所以采用了勒让德（Legendre）多项式作为正交基。

那我们先跟随苏神看看傅里叶级数的情况，通过熟悉的东西先理解框架方法。
HiPPO 的目标是：用一个有限维的向量来储存（或者说压缩）函数的信息。
我们使用在平方可积条件下的正交函数基展开，比如傅里叶（Fourier）级数，它的系数计算公式为：
在这里插入图片描述
这时候取一个足够大的整数N ，只保留n的绝对值小于等于N 的系数，那么就将函数u(t)压缩为一个2N+1 维的向量了。

在这里插入图片描述
接下来，就是一个新的问题，如何实现时间的映射？下面是一些方法：

这些不同的方法，就是HiPPO论文作者所说的“过去每个时间重要性的度量”。那对时间重要性的度量的不同方法，导致最后的公式形式也有所不同。
苏神先选择了其中滑窗的度量方法：
在这里插入图片描述

把上面的公式（9）对比一下SSM方程：

就得到了如式（1）所示的线性 ODE 系统。即当我们试图用傅里叶级数去记忆一个实时函数的最邻近窗口内的状态时，结果自然而言地导致了一个线性 ODE 系统。