# Kernel Ridge Regression

既然 LogReg 可以 Kernelize，那我們也來把原本的 [Ridge Regression 問題](https://hackmd.io/@ShawnNTU-CS/B1Be6DN3n)給 Kernelize：

$$
\min_{\mathbf{w}} \frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum_{n=1}^{N}(y_{n}-\mathbf{w}^{T}\mathbf{z}_{n})^{2}
$$

再搭配上一章提過的 Representer Theorem，可改成解 $\boldsymbol{\beta}$ 的 Linear model；並且由於這是 [Ridge Regression 問題](https://hackmd.io/@ShawnNTU-CS/B1Be6DN3n)，所以可以使用一些線性代數和微積分的操作，找到公式解：

$$
\boldsymbol{\beta}=\left(\lambda\mathbf{I}+\mathbf{K}\right)^{-1}\mathbf{y}
$$

根據 Mercer's Condition，可以知道 $\lambda\mathbf{I}+\mathbf{K}$ 這個部分只要 $\lambda > 0$ 必定存在反矩陣。

因此我們在原版的 Linear Ridge Regression 上成功的使用了 Kernel Trick，可以容易解出 non-Linear Ridge Regression。

:::info
要注意 $I$ 是對角線都是 1 的矩陣，也就是 np.eye。不是 np.ones。
:::

## Tradeoff

線性的最佳解：

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

非線性最佳解：

$$
\boldsymbol{\beta}=\left(\lambda\mathbf{I}+\mathbf{K}\right)^{-1}\mathbf{y}
$$

可以看出：

- 線性：
- 比較有限制
- 訓練需要 $O(d^{3}+d^{2}N)$
- 反矩陣運算會多一個次方
- 預測需要 $O(d)$
- 當 $N \gg d$ 時比較有效率
- 非線性
- 因為有了 $\mathbf{K}$ 所以比較有彈性
- 訓練需要 $O(N^{3})$
- 預測需要 $O(N)$
- 一旦當 $N$ 很大 效率就不太好

所以線性跟非線性就是效率跟彈性的取捨。

## Least-Squares SVM (LLSVM)

跟之前提到過的一樣， Regression 也可以拿來做分類；而拿來做分類的 KRR 又叫做 Least-Squares SVM。

$$
g(\mathbf{x})=sign\left(\sum_{n=1}^{N}\beta_{n}K(\mathbf{x}_{n},\mathbf{x})\right)
$$

:::info
要注意如果沒有用 kernel trick 需要自己補 $x_{0}$。
:::

## dense $\boldsymbol{\beta}$

但是 KLR 跟 KRR 有個共同的缺點，$\boldsymbol{\beta}$ 通常是緻密矩陣，也就是說 SV 的數量很多，人人都是 SV (?，一旦 N 很大運算就會很慢。

而 SVM 的 $\boldsymbol{\alpha}$ 反而是大多是 0 的 sparse matrix 稀疏矩陣。

所以對於 KRR 我們也希望可以有稀疏的 $\boldsymbol{\beta}$ 矩陣，於是我們想了新的 Regression err。

# Tube Regression

## $\epsilon$-insensitive error

「管子」內的不算錯，管子外的才開始算錯：

$$
err(y,s)=max(0,|s-y|-\epsilon)
$$

由於 err 是線性的，所以相比原本 Regression 的 二次 err，當 s 跟 y 偏差越大，也就是發生 outlier 的時候，更不容易被影響。

## L2-Regularized Tube Regression

$$
\min_{\mathbf{w}} \frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum_{n=1}^{N}max(0,|\mathbf{w}^{T}\mathbf{z}_{n}-y_{n}|-\epsilon)
$$

要解這個會面臨兩個問題：

- 雖然沒有限制，但 max 存在不可微分的點
- 就算 kernelize 用下去，也看不出可以產生稀疏矩陣的地方

此時回想原本 SVM：

- 雖然可以表示成 max 形式，但是其對應著一個 QP 的形式，所以可以用 QP 來解
- 因為可以轉成 dual，在 KKT 條件下會產生稀疏矩陣的解

所以我們來模仿 SVM ，但是在那之前先轉換一下表示法：

$$
\min_{\mathbf{w},b} \frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum_{n=1}^{N}max(0,|\mathbf{w}^{T}\mathbf{z}_{n}+b-y_{n}|-\epsilon)
$$

通常在 SVM 中習慣將 b 單獨列出來。

# Standard Support Vector Regression Primal

回想當初 SVM 為甚麼可以轉換成如下形式：

$$
\frac{1}{2}\mathbf{w}^{T}\mathbf{w}+C\sum_{n=1}^{N}max\left(1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b),0\right)
$$

- 如果 $1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b)\le0$，代表沒有犯任何錯
- 所以會導致取 max 後為 0
- 如果 $1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b)>0$，代表犯了錯
- 所以會導致取 max 後產生了錯誤量 $\xi_{n}$

所以對於沒有犯錯的點，$1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b)\le0$，那如果是有犯錯的點，**「如果我想要維持 $\le$ 的關係」**，我就必須在右側加上犯錯量，也就是 $1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b)\le \xi_{n}$，這樣就成功地維持了 $\le$ 的關係，也就代表我們成功的把 max 換成了 QP 問題中的線性條件：

$$
1 - y_{n}(\mathbf{w}^{T}\mathbf{x}+b)\le \xi_{n}\\
\xi_{n} \ge 0
$$

原本問題就可以轉成：

$$
\min_{b,\mathbf{w},\boldsymbol{\xi}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}\xi_{n}
$$

所以依樣畫葫蘆：

$$
\min_{\mathbf{w},b} \frac{\lambda}{N}\mathbf{w}^{T}\mathbf{w}+\frac{1}{N}\sum_{n=1}^{N}max(0,|\mathbf{w}^{T}\mathbf{z}_{n}+b-y_{n}|-\epsilon)
$$

- 如果 $|\mathbf{w}^{T}\mathbf{z}_{n}+b-y_{n}|-\epsilon\le0$，代表落在管子內，沒有犯任何錯
- 所以會導致取 max 後為 0
- 如果 $|\mathbf{w}^{T}\mathbf{z}_{n}+b-y_{n}|-\epsilon>0$，代表落在管子外，犯了錯
- 所以會導致取 max 後產生了錯誤量 $\xi_{n}$

所以如果要維持 $\le$ 關係，就是一樣加上錯誤量：

$$
|\mathbf{w}^{T}\mathbf{z}_{n}+b-y_{n}|-\epsilon\le\xi_{n}\\
\xi_{n}\ge0
$$

原本問題就可以轉成...，可以嗎？還不行，因為條件中有絕對值，所以要拆開：

$$
|\mathbf{w}^{T}\mathbf{z}_{n}+b-y_{n}|\le\epsilon+\xi_{n}\\
\Rightarrow -(\epsilon+\xi_{n})\le y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b \le \epsilon+\xi_{n}
$$

但是既然變成了兩邊，我們可以知道一個點到時候只會需要看其中一邊就好，另一邊錯誤量是 0，所以兩個錯誤量要分開：

$$
-\epsilon-\xi_{n}^{\vee}\le y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b \le \epsilon+\xi_{n}^{\wedge}\\
\xi_{n}^{\vee}\ge0\\
\xi_{n}^{\wedge}\ge0
$$

有了線性條件後才可以把原問題轉成 QP 問題：

$$
\min_{b,\mathbf{w},\boldsymbol{\xi^{\vee}},\boldsymbol{\xi^{\wedge}}} \frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}\xi_{n}^{\vee}+\xi_{n}^{\wedge}
$$

所以我們成功的找到了 Support Vector Regression (Linear SVR) 的 Primal Problem。

- 有 $\tilde{d}+1$ 加上 $2N$ 個變數
- 有 $2N$ 加上 $2N$ 個條件

:::warning
將 max 轉換成線性限制的流程應該是重要的技巧，要記起來，也就是「保持 $\le$ 的話要...」的部分
:::

# SVR Dual

使用我們早已熟稔的傳統藝能，轉換成 dual 問題：

$$
\min_{\boldsymbol{\alpha^{\vee}},\boldsymbol{\alpha^{\wedge}}}\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{M}(\alpha^{\wedge}_{n}-\alpha^{\vee}_{n})(\alpha^{\wedge}_{m}-\alpha^{\vee}_{m})K_{n,m}+\sum_{n=1}^{N}\left((\epsilon-y_{n})\alpha^{\wedge}_{n}+(\epsilon+y_{n})\alpha^{\vee}_{n}\right)
$$

$$
\sum_{n=1}^{N}\alpha^{\wedge}_{n}-\alpha^{\vee}_{n} = 0\\
0\le\alpha^{\wedge}_{n}\le C \\
0\le\alpha^{\vee}_{n}\le C \\
$$

- 有 $2N$ 個變數
- 有 $2N+1$ 個條件

所以一樣可以使用寫好的工具包解 QP 問題。其中：

$$
\mathbf{w}=\sum_{n=1}^{N}(\alpha^{\wedge}_{n}-\alpha^{\vee}_{n})\mathbf{z}_{n}
$$

恰好符合之前提到的線性組合的形式。

## Sparsity

之前是從 primal feasibilty 推導出誰是 SV 誰不是，所以：

$$
-\epsilon-\xi_{n}^{\vee}\le y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b \le \epsilon+\xi_{n}^{\wedge}\\
\Downarrow \\
-\epsilon-\xi_{n}^{\vee} - (y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b )\le 0\\
y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b - (\epsilon+\xi_{n}^{\wedge})\le 0\\
\Downarrow\\
\alpha_{n}^{\vee}(-\epsilon-\xi_{n}^{\vee} - (y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b ))=0\\
\alpha_{n}^{\wedge}(y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b - (\epsilon+\xi_{n}^{\wedge}))=0\\
\Downarrow\\
\alpha_{n}^{\vee}(\epsilon+\xi_{n}^{\vee} + y_{n} - \mathbf{w}^{T}\mathbf{z}_{n} - b )=0\\
\alpha_{n}^{\wedge}(\epsilon+\xi_{n}^{\wedge} - y_{n} + \mathbf{w}^{T}\mathbf{z}_{n} + b)=0\\
$$

所以對於任何落在管子內的點，$|\mathbf{w}^{T}\mathbf{z}_{n} + b - y_{n}|<\epsilon$，可以知道並沒有犯任何錯，也就是說 $\xi_{n}^{\wedge}=\xi_{n}^{\vee}=0$；這樣的話，根據 complementary
slackness 就可以知道 $\alpha_{n}^{\vee}=\alpha_{n}^{\wedge}=0$，也就說：

$$
\mathbf{w}=\sum_{n=1}^{N}\underbrace{(\alpha^{\wedge}_{n}-\alpha^{\vee}_{n})}_{\beta_{n}}\mathbf{z}_{n}=\sum_{n=1}^{N}0\mathbf{z}_{n}\\
\beta_{n}=0
$$

我們成功透過 dual problem 的 KKT 條件，得到了想要的稀疏矩陣。

---

# Map of Linear and Kernel Models

Linear 的實務上：

- PLA/pocket 在處裡非線性可分的表現上， linear soft-margin SVM (primal by QP) 比較好。
- linear SVR(Regularized Tube) by QP 的 err 是線性的，如果希望是二次的 err，要用 Linear Ridge Regression。

所以 Linear 的 soft-margin SVM、ridge Regression 跟 regularized logistic regession 比較常用。

:::info
這三個在 LIBLINEAR 工具包中都有。
:::

而加上 Kernel 的話，KRR 跟 KLR 會因為緻密矩陣的問題而不常用，常用的是 SVM、SVR 跟 Probabilistic SVM。

:::info
這三個 LIBSVM 工具包有。
可以看到非線性的是比較常用的工具，名字就是代表性的縮寫；所以通常來說講 SVM 是指採用了 kernel 的 SVM 而非線性的 SVM
:::