---
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
- regularization 是對抗 overfitting 的一種方式
- 左圖就是我們希望的 **'regularized fit'**
- 希望從高次多項式的 $\mathcal H$ 走回到低次多項式的 $\mathcal H$
- regularization 名字來由是一些人在做 function approximation 的 ill-posed problem
- **ill-posed problem 是在說有很多 function 都滿足我們想要的 solution，不知道要用哪個**
- 所以要限縮一下，不然這樣解會有很多問題，我們解 ML 問題的時候也是一樣啊~
- 那要怎麼限縮呢？

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

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

### Regression with Looser Constraint
- 那不如我們放寬一下標準，說我們的 $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
- 不然再寬鬆一點，我們只說 $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
- $\min_\limits w (Zw-y)^T(Zw-y) \\\text{ s.t. } w^Tw\leq C$

### The Lagrange Multiplier
- 如果有一個 $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
- 如果有人告訴我 $\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
- 如果今天不是 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
- 比較大的 $\lambda$ 對應到：
- 比較短的 $w$
- 比較小的 $C$
- **通常稱為 weight-decay regularization**
- **可以跟任何 transform + linear model 做搭配**
- 不一定是 polynomial transform
- linear model 可以是 logistic regression 之類的

### Some Detail: Legendre Polynomials
- 其實要得到前面 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
- 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
- 把 $\lambda$ 考慮進去之後，我只用了一小部分的 $w$，那這一小部分的 $w$ 應該可以用來計算 VC Guarantee 是什麼。

### Another View of Augmented Error
- 仔細觀察會發現，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
- 雖然看起來我的確考慮了所有的 $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

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

### General Regularizers $\Omega(w)$
- 一個好的 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
- 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$
- 這裡是用 15 次多項式去 fit 這些有(或沒有) noise 的 data
- $\sigma^2=0$ 跟 $Q_f=15$ 都相當於沒有 noise。
- 越多 noise 需要越大的 $\lambda$
- 可是實務上又不知道 noise 到底多大？
- 那到底要怎麼選 $\lambda$ 呢？
- 下次上課會說明
- 如何選擇 $\lambda$
- 如何選擇 $\phi$
- 如何選擇不同的 linear model

### Summary