[ML] 機器學習基石：第十四講 Regularization

ML：基礎學習
課程：機器學習基石
簡介：第十四講 Regularization

如何倒退回較低次的 model 呢？

regularized hypothesis set \(H(C)\)

$$ H(C)=\left \{ \mathbf{w} \in \mathbb{R}^{Q+1}\ while\ \left \| \mathbf{w} \right \|^2 \le C \right \} $$

在 \(H_{10}\) 中：\(w_0+w_1x+w_2x^2+w_3x^3+\cdots +w_{10}x^{10}\)
那麼若要表達成 \(H_{2}\) 呢？
加上限制式 \(w_3=w_4=\cdots =w_{10}=0\) 即可
那麼若是 \({H}'_2\) 至少不特定的 8 個係數為 0 呢？
\(\sum_{q=0}^{10}[w_q \neq 0] \le 3\) 且 \(H_2 \subset {H}'_2 \subset H_{10}\) 但卻是 NP hard
那是否能改成容易解的方式？
\(H(C)\)限制式改為 \(\sum_{q=0}^{10}w_q^2 \le C\)
\(H(0) \subset H(1.126) \subset \cdots \subset H(1126) \subset \cdots \subset H(\infty ) = H_{10}\)

如何解？

$$ \begin{align*} \underset{\mathbf{w} \in \mathbb{R}^{Q+1}}{min}E_{in}(\mathbf{w}) &= \frac{1}{N}\underset{(Z\mathbf{w-y})^T(Z\mathbf{w-y})}{\underbrace{\sum_{n=1}^{N}(\mathbf{w^Tz_n}-y_n)^2}}\\ s.t.\ & \underset{\mathbf{w^Tw}}{\underbrace{\sum_{q=0}^{Q}w_q^2}} \le C \end{align*} $$

1. 往 \(-\triangledown E_{in}(\mathbf{w})\) 的方向走，可得原本最佳解
2. 目前有限制式，\(\mathbf{w}\) 只能在紅色球中，故取切線方向，才不會超出球
3. 往 \(-\triangledown E_{in}(\mathbf{w})\) 在球的切線方向走，直到 \(-\triangledown E_{in}(\mathbf{w})\) 平行於球的法線量
4. 故當為最佳解 \(\mathbf{w_{REG}}\) 時，因 \(\mathbf{w_{REG}}\) 也為法線量 (球中心為原點)
   \(-\triangledown E_{in}(\mathbf{w_{REG}}) \propto \mathbf{w_{REG}}\)

得 Lagrange multiplier \(\lambda > 0\)
\(\triangledown E_{in}(\mathbf{w_{REG}})+\frac{2\lambda }{N}\mathbf{w_{REG}}=0\)

$$ \lambda >0 \\ \begin{align*} \triangledown E_{in}(\mathbf{w_{REG}})+\frac{2\lambda }{N}\mathbf{w_{REG}} &= 0 \\ \frac{2}{N}(Z^TZ \mathbf{w_{REG}}-Z^T\mathbf{y})+\frac{2\lambda }{N}\mathbf{w_{REG}} &= 0 \\ \mathbf{w_{REG}} = (Z^TZ+\lambda I)^{-1}Z^T\mathbf{y}& \end{align*} $$

因 \(Z^TZ\) 為半正定矩陣，且 \(\lambda I\) 為正定矩陣，故反矩陣存在

或換個角度來看

解

$$ \triangledown E_{in}(\mathbf{w_{REG}}) + \frac{2\lambda }{N}\mathbf{w_{REG}} = 0 $$

相當於最小化

$$ E_{aug} = E_{in}(\mathbf{w}) + \frac{\lambda }{N}\mathbf{w^Tw} $$

那麼 \(\mathbf{w^Tw}\) 只是 regularizer 項目，而 \( \lambda \) 為調整的參數，可為 =0 或 >0
\(\mathbf{w_{REG}} = \underset{\mathbf{w}}{argmin}\ E_{aug}(\mathbf{w})\ given\ \lambda >0\ or\ \lambda =0 \)
\(\frac{\lambda }{N}\mathbf{w^Tw}\) weight-decay regularization，不同 \(\lambda\) 值的差別

因大的 \(\lambda\) 等同懲罰長的或大的 \(\mathbf{w}\)
大的 \(\lambda\) <=> 短的 \(\mathbf{w}\) <=> 小的 C
此方法可應用在 任何轉換 + 線性 model

Legendre Polynomials

$$ \underset{\mathbf{w} \in \mathbb{R}^{Q+1}}{min}\frac{1}{N}\sum_{n=0}^{N}(\mathbf{w^T}\Phi (x_n)-y_n)^2+\frac{\lambda }{N}\sum_{q=0}^{Q}w_q^2 $$

若使用 \(\Phi(\mathbf{x})=(1,x,x^2,\cdots , x^Q)\)，當 \(x\) 落在 \(x_n \in [-1, +1]\) 之間
高維度會需要較大的 \(w_q\) 導致會被過度懲罰
所以改用 Legendre Polynomials 可改善此問題，因是 orthonormal basis functions

與 VC 比較

Augmented Error	VC Bound
\(E_{aug}=E_{in}(\mathbf{w})+\frac{\lambda }{N}\underset{\Omega (\mathbf{w})}{\underbrace{\mathbf{w^Tw}}}\)	\(E_{out}(\mathbf{w}) \le E_{in}(\mathbf{w})+\Omega (H)\)
\(\Omega (\mathbf{w})\) 單一 hypothesis 的複雜度	\(\Omega (H)\) hypothesis set 的複雜度
若 \(\Omega (\mathbf{w})\) 與 \(\Omega (H)\) 有關聯，那麼 \(E_{aug}\) 似乎會比 \(E_{in}\) 更接近 \(E_{out}\)
model 複雜度：\(d_{VC}=\tilde{d}+1\) 因考慮了所有的 \(\mathbf{w}\)
但實際上 \(\mathbf{w}\) 並不是全部都拿來用，定義：有效 \(d_{EFF}(H,\underset{min\ E_{aug}}{\underbrace{A}})\) 視不同的演算法而有不同

如何運用 Regularizer \(\Omega (\mathbf{w})\)

• 目標函數已知特性
• 對稱性 regularizer：\(\sum [q\ is\ odd]w_q^2\)
• 合理性
• 較平滑或簡單：sparsity (L1) regularizer \(\sum \left \| w_q \right \|\)
• 友好的
• 容易最佳化：weight-decay (L2) \(\sum  w_q^2\)
• 將 \(\lambda =0\) 放進選擇，成為最後的保護

L2 & L1 比較

L1 通常會在頂點得解，故有的 \(w_q\) 會為 0

最佳化 \(\lambda\)

• 越多的 noise 越需要加大 \(\lambda\)
• 但 noise 未知，如何選擇，可參考下一講