優化證書說明計算所得向量接近某個目標函數的最小值。統計問題則不同:當觀測響應有雜訊時,擬合值與未知信號相差多少?答案取決於懲罰的尺度,也取決於設計矩陣如何作用於優化問題允許的誤差方向。
固定設計模型
設 為正整數, 固定,,選取 。對每個座標都加懲罰,定義任一精確最小解
目標連續且趨於無窮,因此最小解存在,但未必唯一。若截距不受懲罰,下文論證須先作相應調整,例如一致地對響應及各列中心化。這裏的預測誤差 是這 個設計點上的差異,不是未來輸入上的誤差。
假設 的非零座標包含於 ,且 ; 內仍可有零座標。記 為只保留 中座標所得的向量。考慮錐
定義 1.6.1
(錐上的限制特徵值)
如果對每個 都有
則稱設計對 有限制特徵值常數 。條件只涉及一部分方向;即使 、 奇異,也可能成立。常數依賴所選的集合及錐中的係數。
概念視角幾何
限制特徵值存在恰好等於核與錐只交於零
存在某個 適用於 ,當且僅當 。若錐中有非零 使 ,則 ,因為 迫使 ;於是對任何正的 ,不等式都不成立。反過來,錐中滿足 的向量組成閉集,而且其上 ,所以有界,因而是緊緻集。若核與錐只交於零,連續函數 在這個集合上恆為正,並取得正的最小值,這就是可用的 ;再以縮放推廣到整個錐。因此這個分析不等式其實是幾何陳述:LASSO 誤差可能取的方向,沒有一個是設計矩陣看不見的。
主要結果是確定性的:它假設雜訊相關量有界,而不假設分布。
定理 1.6.2
(固定設計預測界)
假設上述限制特徵值條件成立,而且雜訊滿足事件
那麼每個精確最小解都滿足
這是確定性結論,不需要概率分布假設。
證明
(基本不等式、錐條件與兩個界)
記 ,。比較最小解與 的目標值,展開平方並消去 ,得
雜訊事件把第一項控制在 以內。對 中座標,反三角不等式給出 ;在 外,懲罰差恰為 。因此
特別地,。由柯西–施瓦茨(Cauchy–Schwarz)不等式與限制特徵值條件,
當 時除以 ;當 時同樣的上界顯然成立,於是得到預測界。限制特徵值條件也給出 ,包括 的情況。再由錐條件,
證明透視
誤差為甚麼落在錐中
證明中每個假設恰好用一次。 的最優性給出基本不等式;論證完全不涉及最小解如何求得,所以界對每個最小解都成立。雜訊事件把隨機的交叉項轉化為 。
關鍵一步是把懲罰差分拆到 與 。在 上,三角不等式最多損失 ;在 為零的 上,懲罰卻完整地賺回 。這份收益一半用來抵銷雜訊,餘下部分把 放進錐中: 上的 對比 上的 ,比值正是 。
設計矩陣直到這時才出場。限制特徵值只需在錐上成立,這正是它在 奇異時仍可成立的原因。論證以自我約束的一步收結: 被 的倍數控制,相除便得到速率。
這裏的係數 來自雜訊事件中的 ,不是 LASSO 獨有的固定常數。這些條件充分,但不表示所有有用的設計都必須滿足這一特定條件。不過,雜訊事件本身不能省去。
反例模式
懲罰低於雜訊水平時界失效
斷言:只要限制特徵值條件成立,預測界對每個 都成立。取 、、、 及 ,於是 且 。取 ,最小解是 在閾值 下的軟閾值,即 。其預測誤差為 ,但聲稱的界只是 。
此處雜訊事件不成立: 超過 。修正方法是取 ,使事件成立。取 時最小解為 ,誤差 滿足界 。
為事件賦予概率
誤差一旦是隨機的,雜訊事件也就是隨機事件。高斯(Gauss)尾界說明 須有多大,事件才很可能成立。
推論 1.6.3
(以高斯雜訊校準懲罰)
假設雜訊分量獨立且服從 ,其中 ;每列滿足 ;並且限制特徵值條件成立。對 取
則對固定的 ,固定設計定理的兩個誤差界以至少 的概率同時成立。
證明
(高斯尾界與聯集界)
每個 都是均值為零、方差為 的高斯變量。對方差為 的情形使用高斯尾界 ,取 ,再對 列使用聯集界,得
在概率至少為 的餘事件上,確定性定理適用。
若雜訊為零,可以直接對任意正 使用確定性定理。較小的懲罰可能改善實際擬合,但上面的計算不再自動保證相同概率。實際問題中 也可能未知。
例題 1.6.4
(正交設計)
設 ,,,且 。取 ,雜訊事件以等號成立,。因為 ,最小化分解為逐座標的軟閾值問題。無懲罰係數為 ,故 。
實際預測誤差為 ,定理給出的界則為 。係數 雖然被保留,仍被收縮。有效的上界可以相當保守,它不是對本次誤差的精確預測。
例題 1.6.5
(解讀校準後的速率)
取 、、、、 及 。則 ,且
把 代入定理,預測界為 , 界為 ,兩者以至少 的概率成立。 變為四倍時,預測界除以四,約為 。把 乘以一百, 只升至 ,界約增至 :維數只以對數方式進入。
為甚麼需要設計條件
例題 1.6.6
(相同的列:一個擬合,多種歸因)
令 ,,,雜訊為零,。平方損失只通過 取決於係數,且 。一維目標 的最優和是 ;把 任意分配到兩個非負座標都取得最小值。擬合值相同,特徵歸因卻不同。取 , 屬於錐,且 、,因此不存在正的 。相同的列可以保留預測,卻使歸因不可能唯一。
常見錯誤
(預測界不等於精確恢復非零座標)
定理控制預測誤差和係數的總誤差,並不保證估計的非零座標集合等於 。懲罰可能刪去小的真實係數,相關雜訊也可能引入其他座標。精確支撐集恢復需要額外假設及單獨論證;定理也不能直接證明新設計點上的誤差或近似數值解的誤差。
常見錯誤
(列未歸一化時套用校準懲罰)
懲罰公式假設 。若各列反而滿足 ,每個相關量的方差為 ,同一個 只給出失敗概率界 。當 、 時,此界約為 ,毫無資訊。應先把各列重新縮放,或把 乘以 的最大值。
練習與解答
快速檢查
(確定性檢查。設 、、,且雜訊事件成立。求預測誤差界和 誤差界。)
解答 · 答案
分別為 與 。這些界未必緊。
快速檢查
(事件不成立。設 、、、、。求最小解並判斷定理是否適用。)
解答 · 答案
對 使用閾值 得 。雜訊相關量 ,故雜訊假設失敗。取 時界為 ,誤差 恰好滿足它:假設失敗本身不令結果變差,只說明此證明不能提供證書;上文的反例顯示,更小的 可以令界不成立。
快速檢查
(正交情形。若 ,說明任意支撐集都可取 ,並在雜訊事件上直接推導較好的預測界。)
解答 · 引導解答
對任意 ,。在 外,無懲罰係數的絕對值至多 ,軟閾值後為零。在 內,軟閾值與其輸入相差至多 ,故 。預測誤差至多 ,優於一般設計的界。
快速檢查
(零信號。若 且雜訊事件成立,不用限制特徵值條件證明每個最小解都是零。)
解答 · 答案
對 ,基本不等式給出 。兩項非負且 ,故 。
LASSO 優化一節解釋如何計算及檢驗最小解;本節討論進一步連接精確最小解與固定信號所需的假設。