---
# System prepended metadata

title: Ch14 Regularization
tags: [機器學習基石下：方法篇]

---

---
tags: 機器學習基石下：方法篇
---

Ch14 Regularization
===

## Content

[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Regularized Hypothesis Set](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/Gg6ye/regularized-hypothesis-set)

### Regularization: The Magic
![](https://i.imgur.com/14pguSe.png)
- regularization 是對抗 overfitting 的一種方式
- 左圖就是我們希望的 **'regularized fit'**
- 希望從高次多項式的 $\mathcal H$ 走回到低次多項式的 $\mathcal H$
- regularization 名字來由是一些人在做 function approximation 的 ill-posed problem
    - **ill-posed problem 是在說有很多 function 都滿足我們想要的 solution，不知道要用哪個**
    - 所以要限縮一下，不然這樣解會有很多問題，我們解 ML 問題的時候也是一樣啊~
- 那要怎麼限縮呢？



![](https://i.imgur.com/Iczqlnq.png)
- 從這邊開始，簡單起見，就先用 $w$ 來代替 $\tilde w$ 的 notation
    - 經過 feature transform 之後找到的 weight (在 $\mathcal Z$ space 上作用)
- 可以看出來所有 2 次多項式就只是 10 次多項式加上一些限制 ($w_3=0,w_4=0...,w_{10}=0$)


### Regression with Constraint
![](https://i.imgur.com/U23OPX2.png)
- 所以要找出最好的 2 次多項式也只是找出最好的 [10 次多項式加上一些限制]
- 幹嘛不直接解 2 次就好呢？
    - 這一步只是為了拓展視野，方便後面推導。

### Regression with Looser Constraint
![](https://i.imgur.com/iUe6Y6m.png)
- 那不如我們放寬一下標準，說我們的 $w$ 只要有夠多的 0，也可以構成一個比較簡單的 function
- 現在 $\mathcal H_2\subset\mathcal H_2'\subset\mathcal H_{10}$，它也許沒這麼 $\mathcal H_{10}$ 容易 overfit 了
- 但因為 boolean function 的 discrete 的特性，所以難以優化，這是一個 NP-hard 的問題


### Regression with Softer Constraint
![](https://i.imgur.com/p4EcApF.png)
- 不然再寬鬆一點，我們只說 $w$ 的長度平方不要超過 $C$
- 所以只要決定了 $C$ 就決定 hypothesis set 的大小，我們先取名叫 $\mathcal H(C)$
    - 只要 $C$ 是有限的數字，那 $\mathcal H(C)\subset \mathcal H_{10}$ 必定成立
- **$\mathcal H(C)$ 我們叫 regularized hypothesis set**
- **$w_{REG}$ 是在 regularized hypothesis set 下找到的最好的 $w$**


## [Weight Decay Regularization](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/ydemq/weight-decay-regularization)

### Matrix Form of Regularized Regression Problem
![](https://i.imgur.com/vh1nG7C.png)
- $\min_\limits w (Zw-y)^T(Zw-y) \\\text{ s.t. } w^Tw\leq C$


### The Lagrange Multiplier
![](https://i.imgur.com/1zx1rAw.png)
- 如果有一個 $w$ 它已經在 $w^Tw=C$ 的那個球形的邊邊了，我要怎麼知道它現在是不是我們能接受的最佳解？
- 球形告訴我們，它不能往球的法向量那邊滾(圖中紅色箭頭)，但是沿著切線是ok的(圖中綠色箭頭)
    - 球的法向量其實就是當前的 $w$ (紅色箭頭)
- 既然如此，那只要我們想走的方向 $-\nabla E_{in}$ 的其中一個分量是綠色箭頭(球的切線)，那我只要往那邊滾一點點，並不會違反條件
    - > Q: 這裡怎麼怪怪ㄉ，只要滾一點點就會違反了吧？
        - 真的微乎其微的話就不會
- 那就代表，符合條件的 optimal point 它的 gradient 就只能是它所在位置的球的法向量
    - **也就是找到的 optimal point $w_{REG}$ 它的 gradient 要跟 $w_{REG}$ 平行，$-\nabla E_{in}(w_{REG})\propto w_{REG}$**
    - 注意 $w_{REG}$ 代表做 regularization 之後找到的 optimal point。
- 這樣子我們的目標就變成
    - 找 $w_{REG}$ 和 $\lambda$ 使得 $\nabla E_{in}(w_{REG})+\frac{2\lambda}{N}w_{REG}=0$
    - $\lambda$ 就是 Lagrange Multiplier，前面說的那些其實就是它的幾何意義
- 自行思考：
    - high-level 的說 Lagrange Multiplier 應該是：在 optimal point 時objective function 要 parameter 走的方向，要跟 constraint 要 parameter 走的方向相反。
    - 因此 $-\nabla E_{in}$ 要和 $-w$ 方向相反，所以可以寫 $-\nabla E_{in}\propto w$
- 可是現在變成同時要找 $w_{REG}$ 又要找 $\lambda$ 啊，這樣不是變麻煩了嗎？$\downarrow$


### Augmented Error I
![](https://i.imgur.com/Z1tlOkT.png)
- 如果有人告訴我 $\lambda$ 是某個正數，解 $\nabla E_{in}(w_{REG})+\frac{2\lambda}{N}w_{REG}=0$
    - $\lambda$ 是正數很合理，因為 $\frac {2\lambda}N$ 是 $w_{REG}$ 向量跟它 gradient 的比值，啊這兩個東西方向要相同啊所以 $\lambda$ 是正的。
- 回顧一下 linear regression 的 gradient，就可以知道這裡 $\nabla E_{in}(w_{REG})=\frac 2N(Z^TZw_{REG}-Z^Ty)$
- 所以我們要解 $\frac 2N(Z^TZw_{REG}-Z^Ty)+\frac{2\lambda}{N}w_{REG}=0$，這其實是一個關於 $w_{REG}$ 的線性方程式，用 linear regression 輕易可以求出解
    - 就是解 $(Z^TZ-\lambda I)w_{REG}=Z^Ty$
    - 最後得出的最佳解 $w_{REG}=(Z^TZ+\lambda I)^{-1}Z^Ty$ (因為只要 $\lambda>0$，那麼 $Z^TZ+\lambda I$ 一定可逆)
        - $Z^TZ$ 是 positive semi-definite 半正定矩陣
        - 又加上正的 $\lambda I$ 一定是 positive definite 正定矩陣，正定矩陣一定可逆。
    - 這個東西統計上又叫 ridge regression


### Augmented Error II
![](https://i.imgur.com/jIUXecF.png)
- 如果今天不是 linear regression 而是 logistic regression 或者其他的問題呢？有沒有更 generalize 的寫法？
- 我們本來想要 minimize $E_{in}$，所以去找微分等於零的點，也就是 $\nabla E_{in}(w_{REG})=0$
- 那我們現在在找 $\nabla E_{in}(w_{REG})+\frac{2\lambda}{N}w_{REG}=0$ 的點，其實也可以看成想要 minimize 這個 term 的積分。
- 所以可以把上面這件事看成是在 minimize $E_{in}(w)+\frac \lambda N w^Tw$
    - 這整個 term 我們稱 augmented error (因為是在原本 error 再加上另外一項 $\frac\lambda Nw^Tw$
    - 而這個 $\frac\lambda Nw^Tw$ 被稱為 regularizer，因為它起到 regularization 的作用。
- 所以我們本來想要解一個有條件的 $E_{in}$，現在把問題轉化成了，只要 minimize 加上有 $\lambda$ 那一項的 augmented error 就可以了
    - 一個 $C$ 對應到一個 $\lambda$ 啊，那本來給定 $C$ 解 constrained 的 $E_{in}$，不如直接給定 $\lambda$ 來解 unconstrained 的 augmented error，這樣我就不用再去找那個 $\lambda$ 了。
    - 對使用者來說，給 $C$ 跟給 $\lambda$ 可能差不多意思，但是對我(要解這個 optimization problem 的演算法)來說，就差很多了，你直接給我 $\lambda$，我就不用再多去解那個 $\lambda$。


### The Results
![](https://i.imgur.com/Z84Baud.png)
- 比較大的 $\lambda$ 對應到：
    - 比較短的 $w$
    - 比較小的 $C$
- **通常稱為 weight-decay regularization**
- **可以跟任何 transform + linear model 做搭配**
    - 不一定是 polynomial transform
    - linear model 可以是 logistic regression 之類的


### Some Detail: Legendre Polynomials
![](https://i.imgur.com/yLMiaDW.png)
- 其實要得到前面 show 的好看的結果，要多做一件細節
- 當我的 $x$ 是小於 1 的數字，那我的高次項 $x^q$ 就會是一個很小很小的數字，導致我的 $w_q$ 需要變得很大才能影響我的 hypothesis
- 但是 weight-decay 又限制我的 $w$ 只能很小，變相地對我的高次項做了太強的 regularization
- 這一切的成因是：我的每個維度不是垂直的 (orthogonal)
    - > Q: 為何把各維度變 orthogonal 就可以防止這個問題?
- 所以一個 detail 是：我對之前說的這些 $(1,x,x^2,...,x^Q)$ 把它們做成了 orthonormal basis
    - 這些基底通常叫做 Legendre Basis


### Fun Time: Weight-Decay Regularization
![](https://i.imgur.com/8Mx8d4f.png)
- 1 跟 2 很簡單，不贅述
- 3 可以回頭看一下那個圖的幾何意義，當 $C\geq\|w_{LIN}\|^2$，代表那個球已經包住最佳解 $w_{LIN}$ 了，所以 regularization 有加跟沒加一樣。


## [Regularization and VC Theory](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/JSkfV/regularization-and-vc-theory)

### Regularization & VC Theory
![](https://i.imgur.com/Uw9rbiT.png)
- 把 $\lambda$ 考慮進去之後，我只用了一小部分的 $w$，那這一小部分的 $w$ 應該可以用來計算 VC Guarantee 是什麼。


### Another View of Augmented Error
![](https://i.imgur.com/PXM0KFN.png)
- 仔細觀察會發現，augmented error $E_{aug}$ 其實跟 VC bound 有點相似
- $E_{aug}(w)=E_{in}(w)+\frac\lambda Nw^Tw$
    - $w^Tw$ 可以視為 $w$ 這個 hypothesis 的複雜度
    - 既然這樣我們乾脆叫它 $\Omega(w)=w^Tw$
- $E_{aug}(w)=E_{in}(w)+\frac\lambda N\Omega(w)$
    - $\Omega(w)$ 是單一個 $w$ 的複雜度。
- $E_{out}(w)\leq E_{in}(w)+\Omega(\mathcal H)$
    - $\Omega(\mathcal H)$ 是整個 hypothesis set 的複雜度
- 如果 $w$ 很複雜，那也許我可以說它屬於一個比較複雜的 hypothesis set $\mathcal H$
- 這樣的話 $E_{aug}$ 某種程度上就比 $E_{in}$ 更好去代替 $E_{out}$。
- minimizing $E_{aug}$:
    - **(heuristically) operating with the better proxy;**
    - **(technically) engoying flexibility of whole $\mathcal H$**


### Effective VC Dimension
![](https://i.imgur.com/0ghC1bN.png)
- 雖然看起來我的確考慮了所有的 $w$，我的 VC dimension 是 $d_{VC}(\mathcal H)=\tilde d+1$
- 但其實在 optimization 谷底的 $w$ 就只有 $\mathcal H(C)$ 這麼多
    - $C$ 就是 $\lambda$ 對應到的 $C$ 是多少。
- 所以實務上等效的 VC dimension 會考慮進我演算法 $\mathcal A$ prefer 的 hypothesis (也就是比較短的 $w$)
    - 這樣 effective VC dimension $d_{EFF}(\mathcal H,\mathcal A)$ 就會比本來的 VC dimension $d_{VC}(\mathcal H)$ 小。


### Fun Time: Effective VC Dimension
![](https://i.imgur.com/z76quR7.png)


## [General Regularizers](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/xx7aK/general-regularizers)

### General Regularizers $\Omega(w)$
![](https://i.imgur.com/Z9Oq3xL.png)
- 一個好的 regularizer 是會指引 target function 的「方向」的
- target-dependent：如果我知道我 target function 的一些特性，那麼也許可以用來限制 $\mathcal H$
    - 例如我知道 target function 應該會是 symmetry 的，那我就只限制奇數次方的 weight，不限制偶數次方的。
        - symmetry regularizer $\sum 1[q\text{ is odd}]w_q^2$
- plausible：可以說服自己的，例如平滑的 function，為什麼要平滑？回顧一下，不論是 deterministic 還是 stochastic 的 noise 都是跳來跳去的，所以我們的 target function 應該要相對平滑。
    - 例如 sparsity regularizer $\sum |w_q|$
- friendly：容易 optimize 的 regularizer
    - 例如剛剛的 weight-decay regularizer $\sum w_q^2$
- regularizer 很爛怎麼辦？ $\lambda$ 設 0 啊ㄏㄏ
- augmented error = error $\widehat{\text{err}}$ + regularizer $\Omega$
- 可以發現 regularizer 跟 error measure 的挑選方式其實頗像。
    - regularizer: target-dependent, plausible, or friendly
    - error measure: user-dependent, plausible, or friendly


### L2 and L1 Regularizer
![](https://i.imgur.com/al7nkNm.png)
- L2 Regularizer
    - **convex**
    - **differentiable everywhere**
    - easy to optimize
- L1 Regularizer
    - **convex**
    - **not** differentiable everywhere
        - 這樣會稍稍難解
    - **sparsity** in solution
    - 為什麼解到最後會是 sparse 的呢？
        - 回想一下，我們要找到最佳解，就代表 gradient $-\nabla E_{in}$ 不能有「平行於 $w$ 所在邊界」的分量
        - 如果今天 $w$ 是在這個菱形的邊邊上而不是頂點，那麼平行於邊界的向量會一直都是 $\begin{bmatrix}\text{sign}(w_1)\\\text{sign}(w_2)\end{bmatrix}$ 不太會變動，直到走到頂點的地方，也就是有 0 的地方。


### The Optimal $\lambda$
![](https://i.imgur.com/CD4OBR0.png)
- 這裡是用 15 次多項式去 fit 這些有(或沒有) noise 的 data
    - $\sigma^2=0$ 跟 $Q_f=15$ 都相當於沒有 noise。
- 越多 noise 需要越大的 $\lambda$
- 可是實務上又不知道 noise 到底多大？
- 那到底要怎麼選 $\lambda$ 呢？
- 下次上課會說明
    - 如何選擇 $\lambda$
    - 如何選擇 $\phi$
    - 如何選擇不同的 linear model


### Summary
![](https://i.imgur.com/4fvLHAM.png)

