# Regularization

神奇的倒退魔法。

## 歷程

如果不小心用了太多參數，希望可以在訓練過程中「自動地」減少參數的使用。

那就弄一個 $\mathcal{H}$ 可以限制 $\mathbf{w}$ 的數量。

## 初始

$$
\mathcal{H}_{10}=\mathbf{w}\in \mathbb{R}^{10+1}\\
\min_{\mathbf{w}\in \mathbb{R}^{10+1}} E_{in}(\mathbf{w})
$$

這是原版的 regression。

## 進程 1

$$
\mathcal{H}_{2}=\mathbf{w}\in \mathbb{R}^{10+1}\\
while\ \mathbf{w}_{3}=\mathbf{w}_{4}=...\mathbf{w}_{10}=0
$$

$$
\min_{\mathbf{w}\in \mathbb{R}^{10+1}} E_{in}(\mathbf{w}),s.t.\ \mathbf{w}_{3}=\mathbf{w}_{4}=...\mathbf{w}_{10}=0
$$

但是這種我們不知道怎麼處裡。

## 進程 2

$$
\mathcal{H}_{2}^{'}=\mathbf{w}\in \mathbb{R}^{10+1}\\
\text{while the number of } \mathbf{w}_{q}=0 \ge 8
$$

$$
\min_{\mathbf{w}\in \mathbb{R}^{10+1}} E_{in}(\mathbf{w}),s.t.\ \sum_{q=0}^{10}[[\mathbf{w}_{q}\ne 0]]\le 3
$$

很不幸的是這個我們也不知道怎麼處裡，但是條件比上面的寬鬆許多。

## 進程 3

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

$$
\min_{\mathbf{w}\in \mathbb{R}^{10+1}} E_{in}(\mathbf{w}),s.t.\ \sum_{q=0}^{10} \mathbf{w}_{q}^{2} \le C
$$

這個，雖然跟上面的進程 2 有所重疊，但如果 C 變成無限大，就會變回原本的 $\mathcal{H}_{10}$。

所以可以看做是原本 $\mathcal{H}_{10}$ 的寬鬆版本。

而這個，我們就會解了。

# The Lagrange Multiplier

微積分的一項好工具，求有條件時的極值。

假如有一個不包含 $E_{in}$ 的最低點，半徑 C 構成的超平面球，可以由梯度的方向，得知要如何在球的邊緣移動：

- 如果負梯度跟球法向量存在夾角，代表仍然存在著可以讓錯誤率降低的方向，所以可以沿著該方向在球的邊緣前進。
- 最後直到移動到某一點的負梯度方向跟球的法向量平行，才會停止在球的邊緣移動。

因此可以知道其實解是存在的。

$$
-\nabla E_{in}(\mathbf{w}_{REG})\propto \mathbf{w}_{REG}
$$

由於超平面球是以圓點維中心，所以向量本身就是超平面球的法向量。所以我們可以推得：

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

如果是 Linear Regression 的 $E_{in}$ ，那麼：

$$
\frac{2}{N}\left(\mathbf{Z}^{T}\mathbf{Z}\mathbf{w}_{REG}-\mathbf{Z}^{T}\mathbf{y}\right)+\frac{2\lambda}{N}\mathbf{w}_{REG}=0
$$

可以得到最佳解為：

$$
\mathbf{w}_{REG}=\left(\mathbf{Z}^{T}\mathbf{Z}+\lambda\mathbf{I}\right)^{-1}\mathbf{Z}^{T}\mathbf{y}
$$

這在統計叫做 ridge regression。

## 過大的 C

但如果 C 的值太大以至於包含了最低點，那麼最佳解就跟一般的 Regression 一樣。

# Augmented Error

如果要求解：

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

其實就等同於要最小化：

$$
\min_{\mathbf{w}} E_{in}(\mathbf{w}_{REG})+\frac{\lambda}{N}\underbrace{\mathbf{w}^{T}\mathbf{w}}_{regularizer}
$$

這樣的話就算有些 $E_{in}$ 不好微分，我們也可以用其他方式去處理最小化問題。([參考 Kernel Logitic Regression](https://hackmd.io/@ShawnNTU-CS/S1T4Q9Thn))

這個被我們多加了東西的就叫做 Augmented Error，而我們加上去的 $\mathbf{w}^{T}\mathbf{w}$ 就是 regularizer。

$$
E_{aug}(\mathbf{w}_{REG})=E_{in}(\mathbf{w}_{REG})+\frac{\lambda}{N}\underbrace{\mathbf{w}^{T}\mathbf{w}}_{regularizer}
$$

也就是說原本是有某限制的 Error，但被我們轉換成另一個沒有限制的 Error。

## Weight-decay regularization

$$
\frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}
$$

這個部分就是 weight-decay regularization。

只要 $\lambda$ 上升，就會把 $\mathbf{w}$ 的大小壓下來。

通常來說 $\lambda$ 只要一點點(0.0001)就很有效果。

## Legendre Polynomials

上面採用 $\mathbf{Z}$ 作為資料的代號，是代表經過單純的 Polynomial 特徵轉換的資料。

有一種特殊的轉換 Legendre Polynomials，是 normalized polynomial transform，每個 functions 之間彼此是 orthonormal 的。

效果會比單純的 Polynomial 轉換好一些。

因為後者在高次項的時候，如果資料值是小於 1 的小數，那麼該項所對應的權重可能會需要很大；但是這樣就會被 L2 給壓下來反而沒有好效果。

---

# Regularizer

## VC Theory

在原本的 $\mathcal{H}(C)$，VC 理論說：

$$
E_{out}(\mathbf{w})\le E_{in}(\mathbf{w})+\Omega(\mathcal{H}(C))
$$

但是實際上我們並沒有真的使用某個 C，以得到該不等式的保證；我們是間接找一個 $\lambda$ ，由此構成新的 $E_{aug}(\mathbf{w})$，以這個 Error function 作為目標。

換句話說，我們間接的獲得了 VC 的保證，不用去真正的找一個 C，使用具有限制的 $E_{in}$。

## Model complexity

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

Regularizer 記為 $\Omega(\mathbf{w})$，可以看做是單一 Hypothesis 的 complexity。

而在 VC Bound 所提到的 $\Omega(\mathcal{H})$ 則是對整個 $\mathcal{H}$ 的 Model complexity。

在一開始，我們是希望可以透過 $E_{in}$ 來把 $E_{out}$ 做好，也就是 VC Bound 所提到的：

$$
E_{out}(\mathbf{w})\le E_{in}(\mathbf{w})+\Omega(\mathcal{H})
$$

但現在我們有了 $E_{aug}$，如果 $\Omega(\mathbf{w})$ 跟 $\Omega(\mathcal{H})$ 有關連性，或者說 $\Omega(\mathbf{w})$ 可以很好的表現 $\Omega(\mathcal{H})$，那麼 $E_{aug}$ 就會很接近 $E_{out}$：

$$
E_{out}(\mathbf{w}) \approx E_{aug}(\mathbf{w})
$$

也就是說 $E_{aug}$ 相比 $E_{in}$ 來講會是更好的代理人(proxy)，把 $E_{aug}$ 做好，可以把 $E_{out}$ 做更好。

## Effective VC Dimension

由於我們有對 Hypothesis 加上限制，所以其實：

$$
d_{vc}(\mathcal{H}(C))
$$

這個才是我們 Hypothesis 的有效 vc dimension。

不過由於我們是透過 $E_{aug}$ 間接達成的，所以可以寫為：

$$
d_{EFF}(\mathcal{H},\underbrace{\mathcal{A}}_{min \ E_{aug}})
$$

上面表示了在 Regularizer 的作用下，並非全部的參數都會有作用，所以真實的 VC Dimension 會小於 $d_{vc}(\mathcal{H})$；也就是說雖然 $d_{vc}(\mathcal{H})$ 很大，但實際有效的 $d_{vc}$ 很小。

## General Regularizers $\Omega(\mathbf{w})$

可以根據需求，設置自己想要的 Regularizers，像是：

$$
\sum [[\text{q is odd}]]w_{q}^{2}
$$

## sparsity (L1) regularizer

算是常見的一種 regularizer；但是因為有轉角，所以轉角處事不可為分的情形。

由於並非長度平方，所以在超平面上會是有直直的面而非曲面，也就是說在可微的地方梯度都一樣，所以就會一直走一直走直到轉角處而停下，而轉角處的特色就是某些 $w_{i}$ 會是 0。

$$
\Omega(\mathbf{w})=\sum_{q=0}^{Q}|\mathbf{w}_{q}|=\left\|\mathbf{w}\right\|_{1}
$$
>是把 $\mathbf{w}_{q}$ 的每個 $w_{i}$ 取絕對值後相加

會讓 $\mathbf{w}$ 變得很稀疏。

## Weight-decay (L2) regularizer

前面的主角。

$$
\Omega(\mathbf{w})=\sum_{q=0}^{Q}\mathbf{w}_{q}^{2}=\left\|\mathbf{w}\right\|_{2}^{2}
$$

會讓 $\mathbf{w}$ 整體長度變小；但是不會變的稀疏。