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

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

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

regularized hypothesis set $H(C)$

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

在 $H_{10}$ 中：$w_0+w_{1}x+w_2{x}^2+w_3{x}^3+\cdots +w_{10}{x}^{10}$
那麼若要表達成 $H_2$ 呢？
加上限制式 $w_3=w_4=\cdots =w_{10}=0$ 即可
那麼若是 $H_2^{\prime }$ 至少不特定的 8 個係數為 0 呢？
$\sum _{q=0}^{10}[w_q\ne 0]\le 3$ 且 $H_2\subset H_2^{\prime }\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(\mathrm{\infty })=H_{10}$

如何解？

$$\begin{array}{rl}\underset{\mathbf{w}\in {\mathbb{R}}^{Q+1}}{min}{E}_{in}(\mathbf{w})& =\frac{1}{N}\underset{(Z\mathbf{w}\mathbf{-}\mathbf{y}{)}^T(Z\mathbf{w}\mathbf{-}\mathbf{y})}{\underbrace{\sum _{n=1}^N({\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tz}}-y_n{)}^2}}\\ s.t.& \underset{{\mathbf{w}}^{\mathbf{Tw}}}{\underbrace{\sum _{q=0}^Q{w}_q^2}}\le C\end{array}$$

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

得 Lagrange multiplier $\lambda >0$
$▽E_{in}({\mathbf{w}}_{\mathbf{REG}})+\frac{2\lambda }{N}{\mathbf{w}}_{\mathbf{REG}}=0$

$$\begin{gathered} \lambda >0 \\ \begin{array}{rl}▽E_{in}({\mathbf{w}}_{\mathbf{REG}})+\frac{2\lambda }{N}{\mathbf{w}}_{\mathbf{REG}}& =0\\ \frac{2}{N}(Z^{T}Z{\mathbf{w}}_{\mathbf{REG}}-Z^T\mathbf{y})+\frac{2\lambda }{N}{\mathbf{w}}_{\mathbf{REG}}& =0\\ {\mathbf{w}}_{\mathbf{REG}}=(Z^{T}Z+\lambda I{)}^{-1}{Z}^T\mathbf{y}& \end{array} \end{gathered}$$

因 $Z^{T}Z$ 為半正定矩陣，且 $\lambda I$ 為正定矩陣，故反矩陣存在

或換個角度來看

解

$$▽E_{in}({\mathbf{w}}_{\mathbf{REG}})+\frac{2\lambda }{N}{\mathbf{w}}_{\mathbf{REG}}=0$$

相當於最小化

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

那麼 ${\mathbf{w}}^{\mathbf{Tw}}$ 只是 regularizer 項目，而 $\lambda$ 為調整的參數，可為 =0 或 >0
${\mathbf{w}}_{\mathbf{REG}}=\underset{\mathbf{w}}{argmin}{E}_{aug}(\mathbf{w})given\lambda >0or\lambda =0$
$\frac{\lambda }{N}{\mathbf{w}}^{\mathbf{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}}^{\mathbf{T}}\mathrm{\Phi }(x_n)-y_n{)}^2+\frac{\lambda }{N}\sum _{q=0}^Q{w}_q^2$$

若使用 $\mathrm{\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{\mathrm{\Omega }(\mathbf{w})}{\underbrace{{\mathbf{w}}^{\mathbf{Tw}}}}$	$E_{out}(\mathbf{w})\le E_{in}(\mathbf{w})+\mathrm{\Omega }(H)$
$\mathrm{\Omega }(\mathbf{w})$ 單一 hypothesis 的複雜度	$\mathrm{\Omega }(H)$ hypothesis set 的複雜度
若 $\mathrm{\Omega }(\mathbf{w})$ 與 $\mathrm{\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 $\mathrm{\Omega }(\mathbf{w})$

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

L2 & L1 比較

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

最佳化 $\lambda$

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