动机
如果能看见权重如何构造、误差由什么量控制,以及需要多少运算单元,普适近似的存在结论便更具体。多变量不能只照搬一维插值:不同坐标的权重会相乘。ReLU 网络只有分段仿射运算,没有精确乘法门,所以必须近似乘法,再追踪误差如何沿构造累积。
本节分开两个任务。张量网格先给出经典连续插值器,误差由目标的连续模控制;有限 ReLU 电路再近似每个插值权重乘积。相加两种误差,便得到明确网络保证。所得大小随维数可能非常昂贵。把这个代价写出来,正是理解“普适”的内容,不能把它藏在一个名称后面。
架构也须交代清楚。我们计算无环电路中的标量 ReLU 门,仿射边可跨过中间层,然后说明如何转成通常逐层网络。门数不是稠密可训练参数数目,也不证明学习算法能用少量样本推回这些权重。近似、优化及统计问题不能互相偷换。
定义
定义 6.1.1
(目标类、网格帽函数与电路大小)
设 ,,且 、。取整数 ,网格宽度 ,定义
其中 、。帽函数非负且和为一。每个网格顶点 的权重为 。大小计算 ReLU 门,容许仿射组合及输出偏置;深度是输入至输出路径上最多经过的 ReLU 门数。
边界帽函数只是同一公式的限制。每个网格区间只有两个帽函数非零,就是通常线性插值权重。因此张量乘积亦非负且和为一。理想插值器为 ,顶点数 。
概念视角代数
张量帽插值器在每个格子上是多重线性的
在格子 上记 。此时 的每个因子是 或 ,因此 对每个 分别是至多一次的多项式;它是在 个角点取值 的唯一这类函数。 时就是双线性插值 ,而权重的乘积正是 ReLU 乘法器需要近似的对象。
对整数 ,令 是平方函数在 的等距 段线性插值器。令 为投影到 的截断映射,定义近似乘法
输入始终在 ,故平方评估留在已声明区间。这个截断公式没有声称在无界输入上近似乘法。
定理/命题
定理 6.1.2
(具明确误差预算的构造近似)
在上述假设下,有 ReLU 电路 满足
一个构造至多使用 个 ReLU 门,深度至多 。若 ,要误差不超过 ,充分选择是
一般连续目标也可任意准确近似,只须把 换成连续模 。
定理 6.1.3
(有限仿射区域限制精确性与准确度)
把通常 ReLU 网络限制在一条线段,若隐藏层宽度为 ,输出至多有 个仿射区间。任何至多 段的分段仿射函数,在 近似 的一致误差至少为 。因此有限 ReLU 网络不能在一个线区间上精确表示二阶导数非零的二次函数。
区域界通常不锐利,亦不表示每组权重都实现那么多区间。下界先依真实区间数成立,换成架构上界仍有效但可能较弱。它只用一条线的限制,未声称为最佳多维下界。
证明思路
下面依次证明两个定理。第一个证明把精确的插值误差与另行控制的乘法误差相加。
证明
(先精确插值,再近似乘法)
理想权重和为一,而在 有正权重的顶点都与它相距至多 。所以
一般连续目标用同一论证得到 。立方体的紧致性使连续模趋于零,也给出有限幅度界 。这一步的插值完全精确,尚未加入神经运算误差。
在区间 上,平方函数的线性插值比目标高出 。平方网格宽度为 ,故误差非负且至多 。插值函数还有折点公式
它只需 个 ReLU 加一个仿射项。由 ,未截断乘法的误差至多 。真实乘积在 中,而对该区间中的 有 ,故截断不会增大误差。记 ,乘法输出在 中、门数为 、深度至多为二。
逐次近似 个因子的乘积:先取 ,再取 。由于真实与近似部分乘积都在 中,
归纳得误差至多 。
对每个顶点这样构造 ,再令 。系数幅度界给出 ,与插值误差相加便得误差界。即使不共享帽函数,每个顶点也只需 个帽函数门,以及 个各有 个门的乘法器,这就证明了所述规模上界。先一层帽函数,再逐次接两层乘法,深度就是 。最后,当 时 ;当 时乘法项至多为 。
证明透视
截断与顶点数在哪里起作用
证明有两个相互独立的误差来源,由一次三角不等式连接:插值误差只用到 Lipschitz 假设与单位分解,电路误差只用到幅度界 与乘法器精度。两个估计互不相干,所以参数可以依次选取:先为插值选 ,再为电路选 ,因为 依赖于 。
截断用了两次,而归纳两次都需要它。它使每个近似部分乘积留在 中,于是下一个乘法器的自变量留在 具有所述精度的区间 内;它也使 可用,阻止较早的误差被放大。因子 之所以出现,是因为独立近似的乘积未必仍精确地和为一,所以要对全部系数的误差取绝对值相加。若要删去这个因子,须有新的归一化或局部性论证。有些特殊设计的乘法器保留额外的零值性质,可以支持更精细的构造,但不能未经证明就套用到当前电路上。
转成相邻层网络时,可用恒等 ReLU 传递之前的门输出及立方体输入,因为这些量非负。按电路深度排列,至多需要 个单元,再接仿射输出。这是有意粗糙的转换,只证明它属于通常的有限前馈架构,并非最小宽度。计算参数还须计算边;无环电路的加权有向边至多 条,这也只是未利用稀疏性的粗略界。
第二个定理只需一个计数论证和平方函数的一个恒等式。
证明
(逐层计算切点,再用二阶差分)
从输入线段上的一个区间开始。在每个已有区间上,下一层的各个预激活都是线参数的仿射函数;不恒为零者至多有一个零点,恒为零者不产生切点。因此宽度为 的一层至多把每段分成 段,归纳即得乘积界,输出仿射层不再切分。
至多 段中,必有一段长度 。若仿射函数 在这一段上近似平方函数,误差至多为 ,就从平方恒等式
中减去仿射恒等式 。三个误差项的绝对值总和至多为 ,故 。这同时证明了定量限制与不可能精确表示。
大小公式透露的限制
网格顶点数 随维数迅速增加,尚未计乘法精度已昂贵。这显示广泛目标类的维数困难。若目标只依赖少数坐标或本身有组合结构,可以另建较有效构造,但本定理没有这些假设,不能暗中借用例子里的特殊结构。
这个上界容许权重随目标与精度而改变,并未规定一套固定有限权重同时近似所有目标。输出系数由顶点函数值决定,网格斜率则随精度改变。若额外限制权重大小、量化精度或数据取得方式,就须重新追踪那些限制,不能直接声称现有门数已包含其成本。
Yarotsky 的研究论文分析更锐利的平方及乘法子网络。本节使用基本等距插值,自行追踪常数,并未声称平方门的多项式成本是深度相关结果中的最佳界。
例题详解
例题 6.1.4
(两个输入的乘积)
对 ,一个双线性格已精确插值:只有 的标签非零,权重就是 。直接把输入送入 ,至多需二十九个门、深度二,误差至多 。这利用了代数结构;若机械套用每顶点重复构造,会多算许多不必要门。
例题 6.1.5
(追踪保守但有效的预算)
取 。选 ,有 ;再选 ,因 。插值误差为 ,乘法项为 ,合计小于 。门数至多 ,深度三。这是构造上的充分预算,不代表每个目标都需要一万六千多个门。
例题 6.1.6
(线限制也约束多变量网络)
两个隐藏层宽度为三及四时,任何输入线上至多有 个仿射区间。若目标沿该线为 ,一致误差至少 。界虽弱但非零;其他方向维数增加不能移除这条线已有的限制。实际区间数更少时,下界还更强。
常见错误
反例模式
精确乘法不是有限 ReLU 运算
若有限网络能在单位正方形精确表示 ,沿 限制后便会精确表示 ,与有限区域定理矛盾。正确做法是在声明的有界范围使用近似乘法,再传播其误差。
一致连续性给足够细网格的存在,没有已知连续模则未提供数值速率。门数也不指定稠密参数、比特精度或样本复杂度。本构造使用全部顶点的真实目标值;数据不同的学习程序须另证如何取得相当信息。深度增加可以扩大区域上界,却未证明某算法一定用得到。
常见错误
(在选网格之前先定乘法精度)
电路项 含有 ,所以只能在定下 之后再选 。若按猜测的网格选定 ,之后再加密网格,电路项会随 增大,误差预算便不再成立。在 的例子中,保留 而把网格加密到 ,则 ,电路项约为 ,仅这一项就已超过 。
常见错误
(把未截断的部分乘积送入下一个乘法器)
乘法器的保证只对 中的输入成立。没有 ,近似部分乘积可能略微越出 ;下一次平方求值便可能离开 ,在那里 只是线性外推,没有 的保证,递推也失去 这个界。截断每个乘法器只多用两个门,却正是归纳成立的原因。
总结
张量帽函数控制经典插值,平方门近似乘法,截断维持组合运算的有效范围。于是误差与大小都可明确追踪。有限仿射区域同时给出真实限制,让构造普适性与架构约束并列研究。
练习
快速检查
(在一段网格上验证帽函数和为一,再推导张量权重和为一。)
在 到 的区间上记 。
解答 · 答案
在 与 之间,只有 与 为正,值为 与 ,其中 。它们的和为一,端点处也成立。所有张量乘积之和可分解为各坐标帽函数和的乘积,因此仍为一。
快速检查
(取 ,求平方门及乘法器的误差界,并计算乘法器的 ReLU 门数。)
解答 · 答案
平方误差至多 ,乘法误差至多 ,门数为 。它们是一致上界,截断可以改善个别位置的误差。
快速检查
(三个 中的数逐次相乘,每个模块误差至多 且输出截断到 。求总误差界,并指出所需的归纳条件。)
解答 · 答案
第一次乘法误差至多 。把这个近似值乘以第三个数时,由于第三个因子不超过一,传递下来的误差不会放大;新模块再加上至多 ,合计至多 。截断保证中间近似因子落在下一个模块误差保证所适用的定义域内,这正是归纳能继续的条件。
快速检查
(至多十段的分段仿射函数在 上近似 ,可得什么一致误差下界?与十段等距插值的误差比较。)
解答 · 答案
下界为 。取 ,等距线性插值的精确最大误差为 ,因为插值函数比 高出 。减去常数 后函数仍连续且分段仿射,误差落在 中,所以误差 可以达到:对十段而言这个下界是精确的。