重温SSM(四):有理生成函数的新视角
By 苏剑林 | 2024-06-27 | 15354位读者 | 引用在前三篇文章中,我们较为详细地讨论了HiPPO和S4的大部分数学细节。那么,对于接下来的第四篇文章,大家预期我们会讨论什么工作呢?S5、Mamba乃至Mamba2?都不是。本系列文章主要关心SSM的数学基础,旨在了解SSM的同时也补充自己的数学能力。而在上一篇文章我们简单提过S5和Mamba,S5是S4的简化版,相比S4基本上没有引入新的数学技巧,而Mamba系列虽然表现优异,但它已经将$A$简化为对角矩阵,所用到的数学技巧就更少了,它更多的是体现了工程方面的能力。
这篇文章我们来学习一篇暂时还声名不显的新工作《State-Free Inference of State-Space Models: The Transfer Function Approach》(简称RFT),它提出了一个新方案,将SSM的训练、推理乃至参数化,都彻底转到了生成函数空间中,为SSM的理解和应用开辟了新的视角
基础回顾
首先我们简单回顾一下上一篇文章关于S4的探讨结果。S4基于如下线性RNN
\begin{equation}\begin{aligned}
x_{k+1} =&\, \bar{A} x_k + \bar{B} u_k \\
y_{k+1} =&\, \bar{C}^* x_{k+1} \\
\end{aligned}\label{eq:linear}\end{equation}
重温SSM(三):HiPPO的高效计算(S4)
By 苏剑林 | 2024-06-20 | 20207位读者 | 引用前面我们用两篇文章《重温SSM(一):线性系统和HiPPO矩阵》和《重温SSM(二):HiPPO的一些遗留问题》介绍了HiPPO的思想和推导——通过正交函数基对持续更新的函数进行实时逼近,其拟合系数的动力学正好可以表示为一个线性ODE系统,并且对于特定的基底以及逼近方式,我们可以将线性系统的关键矩阵精确地算出来。此外,我们还讨论了HiPPO的离散化和相关性质等问题,这些内容奠定了后续的SSM工作的理论基础。
接下来,我们将介绍HiPPO的后续应用篇《Efficiently Modeling Long Sequences with Structured State Spaces》(简称S4),它利用HiPPO的推导结果作为序列建模的基本工具,并从新的视角探讨了高效的计算和训练方式,最后在不少长序列建模任务上验证了它的有效性,可谓SSM乃至RNN复兴的代表作之一。
基本框架
S4使用的序列建模框架,是如下的线性ODE系统:
\begin{equation}\begin{aligned}
x'(t) =&\, A x(t) + B u(t) \\
y(t) =&\, C^* x(t) + D u(t)
\end{aligned}\end{equation}
重温SSM(二):HiPPO的一些遗留问题
By 苏剑林 | 2024-06-05 | 18583位读者 | 引用书接上文,在上一篇文章《重温SSM(一):线性系统和HiPPO矩阵》中,我们详细讨论了HiPPO逼近框架其HiPPO矩阵的推导,其原理是通过正交函数基来动态地逼近一个实时更新的函数,其投影系数的动力学正好是一个线性系统,而如果以正交多项式为基,那么线性系统的核心矩阵我们可以解析地求解出来,该矩阵就称为HiPPO矩阵。
当然,上一篇文章侧重于HiPPO矩阵的推导,并没有对它的性质做进一步分析,此外诸如“如何离散化以应用于实际数据”、“除了多项式基外其他基是否也可以解析求解”等问题也没有详细讨论到。接下来我们将补充探讨相关问题。
离散格式
假设读者已经阅读并理解上一篇文章的内容,那么这里我们就不再进行过多的铺垫。在上一篇文章中,我们推导出了两类线性ODE系统,分别是:
\begin{align}
&\text{HiPPO-LegT:}\quad x'(t) = Ax(t) + Bu(t) \label{eq:legt-ode}\\[5pt]
&\text{HiPPO-LegS:}\quad x'(t) = \frac{A}{t}x(t) + \frac{B}{t}u(t) \label{eq:legs-ode}\end{align}
其中$A,B$是与时间$t$无关的常数矩阵,HiPPO矩阵主要指矩阵$A$。在这一节中,我们讨论这两个ODE的离散化。
重温SSM(一):线性系统和HiPPO矩阵
By 苏剑林 | 2024-05-24 | 32796位读者 | 引用前几天,笔者看了几篇介绍SSM(State Space Model)的文章,才发现原来自己从未认真了解过SSM,于是打算认真去学习一下SSM的相关内容,顺便开了这个新坑,记录一下学习所得。
SSM的概念由来已久,但这里我们特指深度学习中的SSM,一般认为其开篇之作是2021年的S4,不算太老,而SSM最新最火的变体大概是去年的Mamba。当然,当我们谈到SSM时,也可能泛指一切线性RNN模型,这样RWKV、RetNet还有此前我们在《Google新作试图“复活”RNN:RNN能否再次辉煌?》介绍过的LRU都可以归入此类。不少SSM变体致力于成为Transformer的竞争者,尽管笔者并不认为有完全替代的可能性,但SSM本身优雅的数学性质也值得学习一番。
尽管我们说SSM起源于S4,但在S4之前,SSM有一篇非常强大的奠基之作《HiPPO: Recurrent Memory with Optimal Polynomial Projections》(简称HiPPO),所以本文从HiPPO开始说起。
《新理解矩阵6》:为什么只有方阵有行列式?
By 苏剑林 | 2014-07-15 | 66120位读者 | 引用学过线性代数的朋友都知道,方阵和非方阵的一个明显不同是,对于方阵我们可以计算它的行列式,如果不是方阵的话,就没有行列式这个概念了。在追求统一和谐的数学系统中,为什么非方阵却没有行列式?也许对于这个问题最恰当的回答是——因为不够美。对于非方阵,其实也可以类似地定义它的行列式,定义出来的东西,跟方阵的行列式具有同样的性质,比如某行乘上一个常数,行列式值也就乘以一个常数,等等;而且还可以把其几何意义保留下来。但是,非方阵的行列式是不够美的,因为对于一个一般的整数元素的方阵,我们的行列式是一个整数;而对于一个一般的整数元素的非方阵,却导致了一个无理数的行列式值。另外,一个也比较重要的原因是,单单是方阵的行列式也够用了。综合以上两个理由,非方阵的行列式就被舍弃不用了。
非方阵的行列式不够漂亮
$n$阶方阵的行列式是每个向量的线性函数,它代表着向量之间的线性相关性;从几何上来讲,它就是向量组成的平行n维体的(有向)体积。我们当然期望非方阵的行列式也保留这些性质,因为只有这样,方阵行列式的那些运算性质才得以保留,比如上面说的,行列式的一行乘上一个常数,行列式值也乘上一个常数。我们考虑$m\times n$的矩阵,其中$ m < n $,我们将它看成是$m$个$n$维向量的组合。最简单的,我们先考虑$1\times 2$矩阵的行列式,也就是二维向量$(a,b)$的行列式。
在讨论曲线坐标系的积分时,通常都会出现行列式这个东西,作为“体积元”的因子。在广义相对论中,爱因斯坦场方程的作用量就带有度规的行列式,而在对其进行变分时,自然也就涉及到了行列式的求导问题。我参考了朗道的《场论》以及《数理物理基础--物理需用线性高等数学导引》,了解到相关结果,遂记录如下。
推导
设
\begin{equation}\boldsymbol{A}(t)=\left(a_{ij}(t)\right)_{n\times n}\end{equation}
是一个n阶矩阵,其中每个矩阵元素都是t的函数。其行列式为$|\boldsymbol{A}|$,自然地,考虑
\begin{equation}\frac{d}{dt}|\boldsymbol{A}|\end{equation}
[问题解答]有多少位数字?
By 苏剑林 | 2013-02-21 | 15531位读者 | 引用解决完上一题《有多少个5?》后,子瑞表示看到一道类似的题目,当然,这道题比上一道难一些:
一个数,各个数字加起来等于900,乘以2后各个数字加起来还是等于900,已知这个数字只有3、4、5、6组成,请问满足条件的最大数与最小数的积有多少位数?
要解答这个问题,我们只需要知道最大数和最小数分别有多少位即可。因为最大数必然是6...3的形式,而最小数只能是3...6的形式,它们的位数之和就是所求的位数。
怎样比较两个数的大小呢?显然,在不同位数的数时,位数多的数要大,同样位数才从高到低逐位比较。因此,我们应当考虑位数的最大与最小。
矩阵化简二次型(无穷小近似处理抛物型)
By 苏剑林 | 2012-12-25 | 24152位读者 | 引用(阅读本文最好有一定的线性代数基础,至少对线性代数里边的基本概念有所了解。)
这学期已经接近尾声了,我们的《解析几何》已经讲到化简二次曲线了。可是,对于没有线性代数的其他同学们,直接用转轴和移轴这个计算公式来变换,那计算量会让我们很崩溃的;虽然那个“不变量”方法计算上有些简单,却总让人感到很诡异,总觉得不知从何而来,而且又要记一堆公式。事实上,如果有线性代数的基础,这些东西变得相当好理解的。我追求用统一的方法求解同一种问题,即用统一的方式处理所有的二次型,当然也希望计算量简单一点。
一般的模型
一般的二次型可以写成
$$x^T A x + 2 b^T x + c=0$$
其中$x,b$都是n维列向量(各元素为$x_i$和$b_i$),A是n阶方阵(各元素为$a_{ij}$),c是常数。在这里,我们只讨论n=2和n=3的情况。化简二次型的过程,可以归结为A矩阵的简化。
最近评论