脑洞大开:非线性RNN居然也可以并行计算?
By 苏剑林 | 2023-09-26 | 51786位读者 | 引用近年来,线性RNN由于其可并行训练以及常数推理成本等特性,吸引了一定研究人员的关注(例如笔者之前写的《Google新作试图“复活”RNN:RNN能否再次辉煌?》),这让RNN在Transformer遍地开花的潮流中仍有“一席之地”。然而,目前看来这“一席之地”只属于线性RNN,因为非线性RNN无法高效地并行训练,所以在架构之争中是“心有余而力不足”。
不过,一篇名为《Parallelizing Non-Linear Sequential Models over the Sequence Length》的论文有不同的看法,它提出了一种迭代算法,宣传可以实现非线性RNN的并行训练!真有如此神奇?接下来我们一探究竟。
求不动点
原论文对其方法做了非常一般的介绍,而且其侧重点是PDE和ODE,这里我们直接从RNN入手。考虑常见的简单非线性RNN:
\begin{equation}x_t = \tanh(Ax_{t-1} + u_t)\label{eq:rnn}\end{equation}
数值方法解方程之终极算法
By 苏剑林 | 2010-04-04 | 44322位读者 | 引用呵呵,做了一回标题党,可能说得夸张了一点。说是“终极算法”,主要是因为它可以任意提高精度、而且几乎可以应付任何非线性方程(至少理论上是这样),提高精度是已知的迭代式上添加一些项,而不是完全改变迭代式的形式,当然在提高精度的同时,计算量也会随之增大。其理论基础依旧是泰勒级数。
我们考虑方程$x=f(y)$,已知y求x是很容易的,但是已知x求y并不容易。我们考虑把y在$(x_0,y_0)$处展开成x的的泰勒级数。关键是求出y的n阶导数$\frac{d^n y}{dx^n}$。我们记$f^{(n)}(y)=\frac{d^n x}{dy^n}$,并且有
$$\frac{dy}{dx}=\frac{1}{(\frac{dx}{dy})}=f'(y)^{-1}$$
(原创)切抛物线法解方程
By 苏剑林 | 2010-03-06 | 32306位读者 | 引用牛顿法使用的是函数切线的方程的零点来逼近原函数的零点,他所使用的是“切直线”,要是改为同曲率的“切抛物线”,则有更稳定的收敛效果以及更快的收敛速度
设函数$y=f(x)$在$(x_0,y_0)$处有一条“切抛物线”$y=ax^2+bx+c$,则应该有
$a(x_0+\Delta x)^2+b(x_0+\Delta x)+c=f(x_0+\Delta x)$-------(A)
$ax_0^2+bx_0+c=f(x_0)$-------(B)
$a(x_0-\Delta x)^2+b(x_0-\Delta x)+c=f(x_0-\Delta x)$-------(C)
其中$lim_{\Delta x->0}$
最近评论