二次項使變量靠近觀測值,絕對值懲罰卻可把它精確設為零。兩者的平衡引出軟閾值。我們分別在不可微點與其他位置推導規則,再證明映射不會放大擾動。
純量問題
定義 9.1.1
(純量軟閾值問題)
對 、,考慮
把目標函數記作 。數 是觀測值, 是閾值。
目標函數連續,且當 時趨向 ,因此最小點存在。二次項嚴格凸, 凸,所以它們的和嚴格凸,最小點唯一。因此 是定義明確的數,餘下的工作是把它算出來。
定理 9.1.2
(軟閾值公式)
對每個 及每個 ,
其中 。
特別地 。大幅度觀測值向零移動 ;閾值內的觀測值,包括邊界 ,被映到零。
為何零分支對應一段區間
證明使用 的凸次微分,以及以下事實:對凸函數而言, 屬於其次微分恰好發生在最小點。
證明
(最優條件的三種情況)
的凸次微分在 時為 ,在 時為 ,在 時為 。最後一項可直接由對所有 都有 看出:當且僅當 時成立。
凸最優條件為
若 ,方程給出 ,恰在 時與假設相容。若 ,得到 ,恰在 時相容。在 ,條件為 ,即 。三種情況涵蓋所有 ,包括 ;唯一性確保所得分段規則就是最小點。
證明透視
尖點提供一個斜率區間
離開零點時目標函數可微,方程 只給出一個候選點;這個候選點仍須與所假設的符號核對,嚴格條件 和 正是由此而來。關鍵一步在 :次微分是整個區間 ,方程於是變成包含關係 ,一整段觀測值共享最小點零。三個條件 、、 把實數線分割開,所以每個觀測值恰有一種相容情況。論證能夠閉合,是因為最優條件既必要亦充分;充分性正是使用 的地方,因為它保證目標函數是凸的。
閾值的符號條件不能刪去,即使條件不成立時目標函數仍有最小點。
反例模式
負閾值使公式失效
有人或會在 時套用同一公式。在 ,目標函數是 ,公式預測輸出 。但 ,而 ,所以零不是最小點;兩個最小點 亦顯示唯一性失效。此時 不是凸函數,包含關係 不再保證最小值。只有在所述假設 下,公式才成立。
擾動不會放大
定理 9.1.3
(軟閾值不擴張)
對每個 及所有 ,
證明
(單調次梯度與一次相減)
令 、。最優條件給出 和 ,其中 、。把次梯度不等式 與 相加,可得
兩個最優方程相減並利用 ,得
若 ,所需不等式直接成立;否則取絕對值後除以 ,得到
這是映射的穩定性敘述,並非說所有使用它的迭代最優化算法都收斂。此證明沒有除以 ,也包括 。
向量計算
對 ,目標函數 是互相獨立的純量目標函數之和。其唯一最小點可逐座標使用 得到。逐座標的不擴張性平方後相加,給出向量估計 。此可分計算不對一般含交叉項的二次式作出結論。
例題 9.1.4
(三個座標,其中一個在閾值內)
當 、,頭兩個座標的絕對值超過閾值,第三個沒有。因此
其目標函數值為 :二次部分為 ,懲罰部分為 ,而 。
例題 9.1.5
(觀測值恰好等於閾值)
取 、。公式給出 。直接計算,,而對
對 則 的兩項都比在零點時大。所以 是唯一最小點。正分支表達式 在這裏也等於 ,但 的情況在等號時並不相容;邊界點屬於零分支。
例題 9.1.6
(不擴張界何時取等、何時嚴格)
設 。對 、,兩者都在正分支,所以 ,界取等號。對 、,輸出為 和 ,所以
一般而言,若 而 ,則 :跨越零分支恰好扣去其寬度 。
檢查與練習
常見錯誤
(縮小閾值卻漏了取最大值)
對每個 都寫 ,在閾值內是錯的。取 、,它給出 ,連符號也改變了;然而 ,而 。與 取最大值,正好對應零分支 。
常見錯誤
(把軟閾值與硬閾值混淆)
「若 就保留 ,否則設為 」是硬閾值,它並不最小化這個目標函數。取 、,它給出 ,但 ,而 。絕對值懲罰除了移除小值,也把保留下來的值縮小 。
快速檢查
(當 會怎樣?)
在等號處比較零分支與正分支。
解答 · 答案
輸出為 。正分支表達式 在該處等於 ,但等號處不符合 ,所以適用零分支 。
快速檢查
(當 時,映射是甚麼?)
把目標函數中的懲罰設為零。
解答 · 答案
它是恆等映射 ,不擴張不等式取等號。
快速檢查
(為何對含交叉項的一般二次式不能逐座標套用純量規則?)
想想目標函數是否仍是單變量函數之和。
解答 · 答案
改變一個座標也會改變涉及其他座標的項,目標函數未必可分成互相獨立的純量問題。
快速檢查
(閾值規則是否表示不可能有小的非零輸出?)
試一個略高於閾值的觀測值。
解答 · 答案
不是。若 且 ,輸出就是 。
推導使用所述歐氏二次項及非負懲罰。