二次项使变量靠近观测值,绝对值惩罚却可把它精确设为零。两者的平衡引出软阈值。我们分别在不可微点与其他位置推导规则,再证明映射不会放大扰动。
标量问题
定义 9.1.1
(标量软阈值问题)
对 、,考虑
把目标函数记作 。数 是观测值, 是阈值。
目标函数连续,且当 时趋向 ,因此最小点存在。二次项严格凸, 凸,所以它们的和严格凸,最小点唯一。因此 是一个确定的数,剩下的工作是把它算出来。
定理 9.1.2
(软阈值公式)
对每个 及每个 ,
其中 。
特别地 。大幅度观测值向零移动 ;阈值内的观测值,包括边界 ,被映到零。
为什么零分支对应一段区间
证明使用 的凸次微分,以及以下事实:对凸函数而言, 属于其次微分恰好发生在最小点。
证明
(最优条件的三种情形)
的凸次微分在 时为 ,在 时为 ,在 时为 。最后一项可直接由对所有 都有 看出:当且仅当 时成立。
凸最优条件为
若 ,方程给出 ,恰在 时与假设相容。若 ,得到 ,恰在 时相容。在 ,条件为 ,即 。三种情形涵盖所有 ,包括 ;唯一性确保所得分段规则就是最小点。
证明透视
尖点提供一个斜率区间
离开零点时目标函数可微,方程 只给出一个候选点;这个候选点仍须与所假设的符号核对,严格条件 和 正是由此而来。关键一步在 :次微分是整个区间 ,方程于是变成包含关系 ,一整段观测值共享最小点零。三个条件 、、 把实数轴分割开,所以每个观测值恰有一种相容情形。论证能够闭合,是因为最优条件既必要又充分;充分性正是使用 的地方,因为它保证目标函数是凸的。
阈值的符号条件不能删去,即使条件不成立时目标函数仍有最小点。
反例模式
负阈值使公式失效
有人可能在 时套用同一公式。在 ,目标函数是 ,公式预测输出 。但 ,而 ,所以零不是最小点;两个最小点 也说明唯一性失效。此时 不是凸函数,包含关系 不再保证最小值。只有在所述假设 下,公式才成立。
扰动不会放大
定理 9.1.3
(软阈值不扩张)
对每个 及所有 ,
证明
(单调次梯度与一次相减)
令 、。最优条件给出 和 ,其中 、。把次梯度不等式 与 相加,可得
两个最优方程相减并利用 ,得
若 ,所需不等式直接成立;否则取绝对值后除以 ,得到
这是映射的稳定性叙述,并非说所有使用它的迭代优化算法都收敛。此证明没有除以 ,也包括 。
向量计算
对 ,目标函数 是互相独立的标量目标函数之和。其唯一最小点可逐坐标使用 得到。逐坐标的不扩张性平方后相加,给出向量估计 。此可分计算不对一般含交叉项的二次式作出结论。
例题 9.1.4
(三个坐标,其中一个在阈值内)
当 、,前两个坐标的绝对值超过阈值,第三个没有。因此
其目标函数值为 :二次部分为 ,惩罚部分为 ,而 。
例题 9.1.5
(观测值恰好等于阈值)
取 、。公式给出 。直接计算,,而对
对 则 的两项都比在零点时大。所以 是唯一最小点。正分支表达式 在这里也等于 ,但 的情形在等号时并不相容;边界点属于零分支。
例题 9.1.6
(不扩张界何时取等、何时严格)
设 。对 、,两者都在正分支,所以 ,界取等号。对 、,输出为 和 ,所以
一般地,若 而 ,则 :跨越零分支恰好扣去其宽度 。
检查与练习
常见错误
(按阈值收缩却漏了取最大值)
对每个 都写 ,在阈值内是错的。取 、,它给出 ,连符号也变了;然而 ,而 。与 取最大值,正好对应零分支 。
常见错误
(把软阈值与硬阈值混淆)
“若 就保留 ,否则设为 ”是硬阈值,它并不最小化这个目标函数。取 、,它给出 ,但 ,而 。绝对值惩罚除了去掉小值,也把保留下来的值缩小 。
快速检查
(当 时会怎样?)
在等号处比较零分支与正分支。
解答 · 答案
输出为 。正分支表达式 在该处等于 ,但等号处不符合 ,所以适用零分支 。
快速检查
(当 时,映射是什么?)
把目标函数中的惩罚设为零。
解答 · 答案
它是恒等映射 ,不扩张不等式取等号。
快速检查
(为什么对含交叉项的一般二次式不能逐坐标套用标量规则?)
想一想目标函数是否仍是单变量函数之和。
解答 · 答案
改变一个坐标也会改变涉及其他坐标的项,目标函数未必可分成互相独立的标量问题。
快速检查
(阈值规则是否表示不可能有小的非零输出?)
试一个略高于阈值的观测值。
解答 · 答案
不是。若 且 ,输出就是 。
推导使用所述欧氏二次项及非负惩罚。