动机
核方法不用逐一写出所有特征,也能表示非线性函数。不过,这项便利仍留下必须处理的计算对象:训练输入之间的核值矩阵。若有 个输入,矩阵便有 个元素。随机特征构造以 代替它,其中 只有 列。当 适中时,存储特征矩阵并在这些列上拟合线性模型,可以减少计算负担。
我们要分开回答三个问题。近似是否保留核方法所需的半正定几何?要抽多少特征,才能在指定数据集上控制近似误差?矩阵的误差又会怎样改变拟合预测?以下会给出条件完整的初等界。这三个答案本身都不是对新观察预测能力的保证。
这里的随机性首先来自特征抽样;输入及标签暂时固定。因此,观察数 与随机特征数 有不同作用。增加 是改善一个指定的计算近似,并没有增加训练观察。
定义
定义 12.1.1
(标量随机特征表示)
设 为输入集, 为概率空间。对每个固定 ,实值特征 对 可测,并假设每个 均有 。定义
令 ,独立抽取同分布于 的 ,并设
由 Cauchy–Schwarz 不等式,定义 的期望存在。固定 个输入 ,容许重复。定义 、,以及 。每一列是同一次特征抽样在所有输入上的值。同一个拟合模型的训练及测试特征映射,必须使用同一组抽样。
集中定理另假设存在已知 ,使选定输入同时满足:对 -几乎处处的 ,有 。整个输入域上的一致界当然足够,但比这个有限数据假设更强。记 ,并以 表示欧氏(Euclidean)算子范数。全文的 表示自然对数。除非另有说明,下文的概率只针对独立特征抽样。
概念视角结构
把 Gram 矩阵看成二阶矩矩阵
令 。则 是这个随机向量的二阶矩矩阵,而 是它的样本二阶矩矩阵。于是半正定性、秩上界和无偏性都只是 个秩一外积平均的熟悉性质;近似 也就变成估计 中一个随机向量的矩的问题。
定理/命题
定理 12.1.2
(无偏半正定近似与有限数据集中)
与 都半正定,且 。逐元素有 。在上述有界假设下,对任意 ,
因此,若 且
则至少以 的概率,每个元素的误差都不超过 ,算子误差不超过 。此外,
因子 是元素数目,不表示各元素独立。概率上界可以大于一;此时它只是没有提供有效信息。利用对称性可略微改善计数,这里保留较简单而仍正确的常数。
定理 12.1.3
(半正定 Gram 扰动下的岭回归预测稳定性)
设 为任意实对称半正定 矩阵,,。令 ,定义
若 ,则
特别地,在首个定理的事件上,。这些都是给定矩阵后的确定性扰动结论,不需假设标签的分布。
若 , 正是特征岭回归的训练预测;其目标为最小化 。正规方程是 。直接相乘可核对,唯一解为 。因子 已包含在 中;这个约定不需要再把 除以 。
证明思路或证明
几何与无偏性的真正意思
证明
(半正定性、秩与无偏性)
对任意 ,利用有限求和及特征表示可得
因此,即使抽出的近似很不准确,它仍然半正定。 的列数立即给出秩上界。对每个元素的平均取期望,便证明无偏性;这一步其实不需独立性。独立性会在方差及指数界出现。无偏的对象是矩阵,不是对矩阵求逆或拟合预测等非线性操作。
有界变量的指数估计
下面直接证明集中步骤,而不诉诸一个未具名的不等式。
证明
(倾斜方差界,再对元素用并集界)
设实随机变量 落在 ,定义 。有界性容许对每个实数 微分。在密度正比于 的倾斜概率测度下, 就是 的方差。取 ,则
因为 ,把二阶导数界积分两次,就得到对所有实数 都成立的 。若 ,沿 到零的线段积分,同样得到这个非负二次界。
固定 ,设 。这些变量独立,落在 ,期望为 。联合指数矩因此分解成乘积。对 应用 Markov 不等式,得
选 ,右侧成为 。对 重复论证,再加上两侧尾概率。最后对 对指标用并集界,便得到矩阵概率估计。解出令右侧不超过 的条件,就是特征预算;实现时须向上取整数。
若 ,则对任意单位向量 ,先用三角不等式、再用 Cauchy–Schwarz,给 。把 个坐标界平方后相加,得到 。至于均方结论,独立性给出每个平均元素的方差等于单次方差除以 。把这些方差沿所有元素相加即可;又因 ,每个方差至多 。平方 Frobenius 范数本来就是元素平方和,所以不会出现跨元素的协方差。
证明透视
真正需要哪一种独立性?
三个不同的事实支撑这个证明,各用不同的假设。有界性 (只在所选输入上)只通过每个乘积 的范围 进入,供倾斜方差界使用。抽样的独立性只用来把指数矩 分解成 个相同的因子;正是这个分解把单次抽样的控制变成关于 的速率。
矩阵各元素共享这些抽样,通常并不独立。最后的并集界只是把概率相加,不需要元素之间独立,所以代价是计数 ,而不是任何协方差计算。若每一列都复制同一个随机特征,沿 的分解便失效;增加列数也未必改善准确度。算子界 是另一个确定性步骤,与概率无关。
从矩阵误差到拟合预测
证明
(预解恒等式与预测的消去)
半正定性保证 及 的所有特征值都至少为 ,故两个逆矩阵的范数至多 。设 、。直接相乘可证预解恒等式
把恒等式作用于 ,再乘上三个算子范数界,便得到系数估计。对预测而言,关键消去是
相减得到 ,从而得到预测界。此证明不要求两个 Gram 矩阵有共同特征向量,也不要求误差小于 。即使 或输入有重复,正则化参数为正仍保证可逆。
同一个位移 也可以逐个特征值理解。
概念视角代数
正则化如何提供谱缓冲
在 Gram 特征值为 的方向,训练岭回归把标签坐标乘以 。正位移 防止除以接近零的特征值。上面的扰动证明即使没有共同特征基也成立;标量图像则解释了正则化参数趋近零时,界为何变差。这个图像不能用来把定理的参数直接设成零。
例题
例题 12.1.4
(两点核与一次精确的 Gram 抽样)
取 ,以相同概率抽 ,定义 、。此时 ,。在输入 上,精确 Gram 矩阵是 。
抽四个特征,其中三个 ,一个 。依此排序,
特征值为 及 ,均非负。逐元素及算子误差都等于 。若 次抽样中有 次是常数特征,非对角估计便是 ,而两个对角元素一直精确等于一。由 ,非对角元素无偏。 时恰有 个常数特征的概率是 。上面的矩阵是一个可能结果,不是平均矩阵。
例题 12.1.5
(三角特征与保守的特征预算)
输入为实数,令 均匀分布于 ,设 。乘积恒等式给
第二项积分为零,所以核是 。核值可以是负数,但特征表示保证 Gram 矩阵半正定。这里 ,;这个有界估计不用限制固定输入坐标的大小。
若 、、,特征界为 时,充分预算是 。对本例的三角特征,则是 。这些是最坏情况的充分预算,并非声称较少特征一定失败。所得矩阵范数界只有 ;每个元素都准确,不表示算子误差同样小。
例题 12.1.6
(同一矩阵误差经岭回归后的影响)
回到两点例,选 、,所以 。标签向量在 的特征值一方向,亦在抽样矩阵的特征值二分之一方向。因此
预测差的范数为 。确定性算子误差界用 ,给出 ,正确但不紧。由一般逐元素误差推出的界更松。保证可以有用,却未必要精确预测实际误差。本例也分清两种改动:输入与标签完全不变,只改变特征近似,拟合预测也会改变。
常见错误
反例模式
特征二阶矩有限,不等于指数集中
令 的密度为 ,对所有 设 。此时 而 。特征二阶矩存在,核是常数 。估计器是 个独立 的平均,所以仍然无偏且半正定。
对每个整数 ,事件 迫使平均值超过四。由 时的 ,可得
此多项式下界最终超过任何固定正常数 所给的 。所以不能只把有界特征假设换成特征二阶矩有限,然后保留原集中定理。其他尾部条件或稳健估计器需要另外论证。
常见错误
(把有限列表上的界推广到整个输入域)
有限数据集也是这个并集界结论的重要部分。看一个极端但有界的例子:输入是 的所有有限子集 , 在 均匀抽取,设 。对每个固定有限 ,特征几乎必然为零,故真核恒为零。但在 次抽样后选 ,就有 。于是对整个输入族取上确界,对每一份实现的抽样列表,误差都等于一。这没有违反固定有限列表定理,因为 是看过抽样后才选的。要从有限网推广到连续域,需要规律性及覆盖论证等额外控制;单靠有界性并不够。
若 配备 sigma-代数, 联合可测, 固定,训练输入随机且与特征抽样独立,而且同一个 对所有可能输入都有效,便可先以输入为条件应用定理,再平均条件失败概率,保留相同概率界。如果输入是看过这批特征抽样后才选的,这个条件化论证便不适用。
常见错误
(把训练预测比较误读为测试或总体保证)
岭回归结论比较的是同一数据上的两个训练预测向量。对新测试输入,还需要控制它与训练输入之间的核值近似;有限个事先指定的测试点可加入原固定列表。即使如此,核近似仍只是比较两个预测器。要谈总体风险,必须另设观察抽样、损失及训练程序的条件,再作统计论证。核估计无偏或训练矩阵误差小,都不会自行证明泛化。
总结
同一组独立随机特征给出无偏半正定 Gram 近似。有界特征包络给固定有限输入列表上的明确指数逐元素界,再给较保守的算子界。正的岭正则化把算子误差转成确定性的训练预测比较。特征数控制的是计算近似,不能代替从观察学习的统计分析。
练习
快速检查
(在两点特征模型中,求任意 下非对角估计的精确方差。若全部 列复制同一个随机抽样,无偏性与集中会怎样?为什么对每个矩阵元素分别抽取新特征也可能破坏半正定保证?)
解答 · 答案
每个非对角求和项以相同概率为一或负一,故期望零、方差一。独立平均的方差是 。若只重复同一次抽样,估计一直等于一或负一,与声称的列数无关;期望仍为零,方差却一直是一,绝对误差也一直是一。独立性,或更一般的两两不相关性,都给出 的方差;本例的完全依赖则破坏这个改善。其他依赖结构需要另行分析。
按元素分别抽样甚至未必对称:两点模型的两个有序非对角估计可能不同。更强的是,一般而言即使强制对称,也不保证半正定。取输入 ,抽取坐标彼此独立、各为 Rademacher 正负号的 ,定义 ,则真 Gram 矩阵为 。对每个无序非对角对,分别用一次独立特征抽样估计,然后把结果对称放置,对角定为一。每个元素都无偏,却以正概率得到
这个对称矩阵不定,行列式为 。共享完整特征向量并取外积,才在每次抽样保留半正定性。元素分别抽样,即使对称而无偏,也没有这个保证。
快速检查
(目标 Gram 矩阵为 ,且 。证明任何只有 列的近似 ,算子误差至少为一。逐元素误差 因此受什么限制?这是否推翻集中定理?)
解答 · 答案
的秩至多 ,故其零空间含一个单位向量 。于是 ,算子误差至少一。由逐元素到算子的界,得到 。所以在此秩范围下,逐元素误差不可能小于 。没有矛盾。在 的任何有界表示中,对角条件 迫使 。若 ,我们的充分特征预算超过 。保守算子估计亦保留因子 。低秩、逐元素准确及算子准确是不同要求。
快速检查
(在抽取特征前固定测试输入 。设训练分块有 ,测试点对训练点的核值有 ,而这些点的特征都以 为界。用 、、、 及 给出 的界。)
解答 · 答案
设 。预测差为 。假设给 、,以及 。训练分块界给 ,因此岭定理给 。所以
这是在所述近似事件上的确定性界。对扩大的固定列表应用集中定理,可给该事件的概率。这两步都不是总体风险界。
快速检查
(只有一个输入,特征平方以相同概率为 或 。取 、标签 、,计算核估计及岭预测的期望,并与精确值比较。这排除了哪个推论?)
解答 · 答案
精确核为一,而估计为零或二,期望确实是一。精确岭预测是 ;抽样预测则为零或 ,期望为 。核近似无偏,不表示拟合预测无偏:求逆及矩阵乘法合起来,是随机 Gram 矩阵的非线性映射。这里所有期望都精确算出,并未使用有限样本集中近似。