优化证书说明计算所得向量接近某个目标函数的最小值。统计问题则不同:当观测响应有噪声时,拟合值与未知信号相差多少?答案取决于惩罚的尺度,也取决于设计矩阵如何作用于优化问题允许的误差方向。
固定设计模型
设 为正整数, 固定,,选取 。对每个坐标都加惩罚,定义任一精确最小解
目标连续且趋于无穷,因此最小解存在,但未必唯一。若截距不受惩罚,下文论证须先作相应调整,例如一致地对响应及各列中心化。这里的预测误差 是这 个设计点上的差异,不是未来输入上的误差。
假设 的非零坐标包含于 ,且 ; 内仍可有零坐标。记 为只保留 中坐标所得的向量。考虑锥
定义 1.6.1
(锥上的限制特征值)
如果对每个 都有
则称设计对 有限制特征值常数 。条件只涉及一部分方向;即使 、 奇异,也可能成立。常数依赖所选的集合及锥中的系数。
概念视角几何
限制特征值存在当且仅当核与锥只交于零
存在某个 适用于 ,当且仅当 。若锥中有非零 使 ,则 ,因为 迫使 ;于是对任何正的 ,不等式都不成立。反过来,锥中满足 的向量构成闭集,并且其上 ,所以有界,从而是紧致集。若核与锥只交于零,连续函数 在这个集合上处处为正,并取到正的最小值,它就是可用的 ;再通过缩放推广到整个锥。因此这个分析不等式其实是几何陈述:LASSO 误差可能取的方向,没有一个是设计矩阵看不见的。
主要结果是确定性的:它假设噪声相关量有界,而不假设分布。
定理 1.6.2
(固定设计预测界)
假设上述限制特征值条件成立,而且噪声满足事件
那么每个精确最小解都满足
这是确定性结论,不需要概率分布假设。
证明
(基本不等式、锥条件与两个界)
记 ,。比较最小解与 的目标值,展开平方并消去 ,得
噪声事件把第一项控制在 以内。对 中坐标,反三角不等式给出 ;在 外,惩罚差恰为 。因此
特别地,。由柯西–施瓦茨(Cauchy–Schwarz)不等式与限制特征值条件,
当 时除以 ;当 时同样的上界显然成立,于是得到预测界。限制特征值条件也给出 ,包括 的情形。再由锥条件,
证明透视
误差为什么落在锥中
证明中每个假设恰好用一次。 的最优性给出基本不等式;论证完全不涉及最小解是如何求得的,所以界对每个最小解都成立。噪声事件把随机的交叉项转化为 。
关键一步是把惩罚差拆到 与 上。在 上,三角不等式最多损失 ;在 为零的 上,惩罚却完整地收回 。这份收益一半用来抵消噪声,剩下的部分把 放进锥中: 上的 对比 上的 ,比值正是 。
设计矩阵直到这时才登场。限制特征值只需在锥上成立,这正是它在 奇异时仍可能成立的原因。论证以自我约束的一步收尾: 被 的倍数控制,相除便得到速率。
这里的系数 来自噪声事件中的 ,不是 LASSO 独有的固定常数。这些条件充分,但不表示所有有用的设计都必须满足这一特定条件。不过,噪声事件本身不能省去。
反例模式
惩罚低于噪声水平时界失效
断言:只要限制特征值条件成立,预测界对每个 都成立。取 、、、 及 ,于是 且 。取 ,最小解是 在阈值 下的软阈值,即 。其预测误差为 ,而声称的界只有 。
这里噪声事件不成立: 超过 。修正方法是取 ,使事件成立。取 时最小解为 ,误差 满足界 。
为事件赋予概率
误差一旦是随机的,噪声事件也就是随机事件。高斯(Gauss)尾界说明 须多大,事件才很可能成立。
推论 1.6.3
(用高斯噪声校准惩罚)
假设噪声分量独立且服从 ,其中 ;每列满足 ;并且限制特征值条件成立。对 取
则对固定的 ,固定设计定理的两个误差界以至少 的概率同时成立。
证明
(高斯尾界与并集界)
每个 都是均值为零、方差为 的高斯变量。对方差为 的情形使用高斯尾界 ,取 ,再对 列使用并集界,得
在概率至少为 的对立事件上,确定性定理适用。
若噪声为零,可以直接对任意正 使用确定性定理。较小的惩罚可能改善实际拟合,但上面的计算不再自动保证相同概率。实际问题中 也可能未知。
例题 1.6.4
(正交设计)
设 ,,,且 。取 ,噪声事件以等号成立,。因为 ,最小化分解为逐坐标的软阈值问题。无惩罚系数为 ,故 。
实际预测误差为 ,定理给出的界则为 。系数 虽然被保留,仍被收缩。有效的上界可以相当保守,它不是对本次误差的精确预测。
例题 1.6.5
(解读校准后的速率)
取 、、、、 及 。则 ,且
把 代入定理,预测界为 , 界为 ,两者以至少 的概率成立。 变为四倍时,预测界除以四,约为 。把 乘以一百, 只升到 ,界约增至 :维数只以对数方式进入。
为什么需要设计条件
例题 1.6.6
(相同的列:一个拟合,多种归因)
令 ,,,噪声为零,。平方损失只通过 取决于系数,且 。一维目标 的最优和是 ;把 任意分配到两个非负坐标都取得最小值。拟合值相同,特征归因却不同。取 , 属于锥,且 、,因此不存在正的 。相同的列可以保留预测,却使归因不可能唯一。
常见错误
(预测界不等于精确恢复非零坐标)
定理控制预测误差和系数的总误差,并不保证估计的非零坐标集合等于 。惩罚可能删去小的真实系数,相关噪声也可能引入其他坐标。精确的支撑集恢复需要额外假设及单独论证;定理也不能直接证明新设计点上的误差或近似数值解的误差。
常见错误
(列未归一化时套用校准惩罚)
惩罚公式假设 。若各列反而满足 ,每个相关量的方差为 ,同一个 只给出失败概率界 。当 、 时,此界约为 ,没有任何信息。应先把各列重新缩放,或把 乘以 的最大值。
练习与解答
快速检查
(确定性检查。设 、、,且噪声事件成立。求预测误差界和 误差界。)
解答 · 答案
分别为 与 。这些界未必紧。
快速检查
(事件不成立。设 、、、、。求最小解并判断定理是否适用。)
解答 · 答案
对 使用阈值 得 。噪声相关量 ,故噪声假设失败。取 时界为 ,误差 恰好满足它:假设失败本身不使结果变差,只说明此证明不能提供证书;上文的反例表明,更小的 可以使界不成立。
快速检查
(正交情形。若 ,说明任意支撑集都可取 ,并在噪声事件上直接推导更好的预测界。)
解答 · 引导解答
对任意 ,。在 外,无惩罚系数的绝对值至多 ,软阈值后为零。在 内,软阈值与其输入相差至多 ,故 。预测误差至多 ,优于一般设计的界。
快速检查
(零信号。若 且噪声事件成立,不用限制特征值条件证明每个最小解都是零。)
解答 · 答案
对 ,基本不等式给出 。两项非负且 ,故 。
LASSO 优化一节解释如何计算及检验最小解;本节讨论进一步连接精确最小解与固定信号所需的假设。