---
tags: 機器學習技法
---

Ch3 Kernel Support Vector Machine
===

## Content
[TOC]

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

## [Kernel Trick](https://www.youtube.com/watch?v=oOi7kqUTqxw&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=10)

### Dual SVM Revisited
- variable 有 $N$ 個 ($\alpha_n$)
- 條件的數量也是 $N$ 個
- 看似跟 $\tilde d$ 沒關係了，但其實要計算 $Q_D$ 裡面的每個 element 都要計算 $q_{n,m}=y_ny_mz_n^Tz_m$
- 而計算內積 $z_n^Tz_m$ 的複雜度是 $O(\tilde d)$，因為 $z_n,z_m\in\mathbb R^{\tilde d}$
- 本來是計算完 $\phi(x)$ 再做內積，現在能不能直接合起來算，算快點呢?

### Fast Inner Product for $\phi_2$
- $d$ 維 data 的 $2$ 次式轉換
- $\phi_2(x)=\\(1,\\x_1,x_2,...,x_d,\\x_1^2,x_1x_2,...,x_1x_d,\\x_2x_1,x_2^2,...,x_2x_d,\\\vdots\\...x_d^2)$
- 這邊有的 term 重複了，例如 $x_1x_2,x_2x_1$ 其實一樣，不過我們這邊還是分開寫，等等比較容易列式子
- 那現在有兩個 data points ($x,x'$)，則經過 feature transform 之後再做內積會得到 $\phi_2(x)^T\phi_2(x')\\=1+\sum_ix_ix_i'+\sum_i\sum_j x_ix_jx_i'x_j'\\=1+\sum_ix_ix_i'+(\sum_ix_ix_i')(\sum_jx_jx_j')\\=1+x^Tx'+(x^Tx')(x^Tx')$
- 也就是說最右邊只需要先做內積，再平方即可
- 第三行就是先整理成 $x_i x_i'x_j x_j'$，然後 $x_i x_i'$ 跟 $j$ 無關所以可以從 $\sum_j$ 提出來得到 $\sum_i[x_i x_i'\sum_j x_j x_j']$；然後後面的 summation 部分都只有 $j$，跟 $i$ 無關所以也可以提出來得到 $(\sum_jx_jx_j')(\sum_ix_ix_i')$
- 本來時間複雜度 $O(\tilde d)=O(d^2)$，現在只需要 $O(d)$

### Kernel: Transform + Inner Product
- **把 transform 跟 inner product 合併在一起的偷吃步作法，就叫 kernel function**
- 例如 transform $\phi_2$ 對應到的 kernel function 就是 $K_{\phi_2}(x,x')=1+(x^Tx')+(x^Tx')^2$
- 那在 SVM 裡面有哪些地方可以用 kernel function 來減少計算量？
- 計算 $Q_D$ 的 elements $q_{n,m}=y_ny_mz_n^Tz_m$：經由 $\phi$ 轉換到 $z$ 空間之後的 inner product 可以換成 kernel function，所以 $q_{n,m}=y_ny_mK(x_n,x_m)$
- 計算 $b=y_s-w^Tz_s$ ($z_s$ 是隨便一個 support vector)：
- 因為 $w=\sum_n\alpha_ny_nz_n$
- 所以 $b\\=y_s-(\sum_n\alpha_ny_nz_n)^Tz_s\\=y_s-\sum_n\alpha_ny_nz_n^Tz_s\\=y_s-\sum_n\alpha_ny_nK(x_n,x_s)\\=y_s-\sum_\limits{\text{SV indices}\,n}\alpha_ny_nK(x_n,x_s)$
- 下個 slide 老師會提到，雖然理論上任何 SV 計算出的 $b$ 都會是同個值，但其實可以把所有的 support vector 都拿來計算 $b$ 再做平均，比較穩定。
> 留言：實務上除了計算誤差外，還因為最佳化的演算法通常只能求到「接近」最佳解的答案而非「絕對」的最佳解，所以每個 SV 的 b 可能會有微小的不同，用平均或是找個比較中間的選擇都是常見的方式。
- 計算 SVM prediction $g_{SVM}(x)=\text{sign}(w^T\phi(x)+b)$
- $g_{SVM}(x)\\=\text{sign}((\sum_n\alpha_ny_nz_n)^T\phi(x))\\=\text{sign}((\sum_n\alpha_ny_nz_n)^Tz)\\=\text{sign}(\sum_n\alpha_ny_nK(x_n,x)+b)$
- nice 喔，這下子所有運算都只依賴 $x$ 而跟 $\tilde d$ 無關了，爽

### Kernel SVM with QP
- 各步驟利用 kernel trick 所需的 time complexity 時間複雜度
1. $O(N^2)\cdot t_{kernel}$
- $t_{kernel}$ 指計算 kernel function 的時間複雜度
2. QP with $N$ variables & $N+1$ constraints 的複雜度
3. $O(N_{SV})\cdot t_{kernel}$
4. $O(N_{SV})\cdot t_{kernel}$
- 各步驟「本來」不使用 kernel function 所需的 time complexity? (not sure)
- 好像就是把 $t_{kernel}$ 全部換成 $O(\tilde d)$ 嗎？
- $\tilde d=O(d^2)$ ?
- 如果是 $Q$ 次多項式是不是就是 $\tilde d=O(d^Q)$ ？
- Kernel SVM：避免在 $\tilde d$ 維空間做計算，且只用 support vectors 做計算

### Fun Time: Kernel Function

## [Polynomial Kernel](https://www.youtube.com/watch?v=Fb-WSBvsPak&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=11)

### General Poly-2 Kernel
- 其實二次式還有各種不同的轉換方式，這邊來介紹一下
- 本來教的版本：
- $\phi_2(x)=(1,x_1,...,x_d,x_1^2,...,x_d^2)$
- 則 $K_{\phi_2}(x,x')=1+x^Tx'+(x^Tx')^2$
- 把 feature transform 的一次項都乘上 $\sqrt 2$
- $\phi_2(x)=(1,\sqrt 2x_1,...,\sqrt 2x_d,x_1^2,...,x_d^2)$
- 則 $K_{2}(x,x')=1+2x^Tx'+(x^Tx')^2$
- 把 feature transform 的一次項都乘上 $\sqrt {2\gamma}$；二次項都乘上 $\gamma$
- $\phi_2(x)=(1,\sqrt {2\gamma}x_1,...,\sqrt {2\gamma}x_d,\gamma x_1^2,...,\gamma x_d^2)$
- 則 $K_{2}(x,x')=1+2\gamma x^Tx'+\gamma^2(x^Tx')^2$
- 常用的是 $K_{2}(x,x')=1+2\gamma x^Tx'+\gamma^2(x^Tx')^2=(1+\gamma x^Tx')^2$
- $\gamma>0$
- 這種轉換較容易 generalize 到高次項
- 注意，不同的 transform 其實也定義了不同的 inner product，這樣也就定義了不同的「distance (距離)」
- 雖然 space 有同樣的 power
- 但是不同的 distance 就決定了不同的 margin，有不同的幾何意義 (好玄

### Poly-2 Kernels in Action
- 以剛剛的 kernel function $K_{2}(x,x')=(1+\gamma x^Tx')^2$ 來說，不同的 $\gamma$
- 會解出不同的 decision boundary
- support vectors 的數量也會不同
- > Q: 小的 $\gamma$ 似乎會解出較簡單的 decision boundary?
- 之前我們說要對 feature transform $\phi$ 做選擇，現在是說對 kernel $K$ 做選擇

### General Polynomial Kernel
- 假設除了 $\gamma$ 再加上一個自由度 $\zeta$(發音zeta) 也可以像剛剛那樣代換變數。
- 這樣的 kernel 可以 generalize 到任意 $Q$ 次方
- $K_Q(x,x')=(\zeta+\gamma x^Tx')^Q$ with $\gamma>0,\zeta\geq 0$
- 即使 $Q$ 很大，也不會這麼容易 overfitting，因為有 large-margin 對複雜度做限制
- 可以看到我們雖然用了 10 次多項式，但做出來的 hyperplane 並不差，**而且 support vectors 數量也不多**
- **一般我們叫這個 Polynomial SVM**

### Special Case: Linear Kernel
- 那我們極端一點只想做一次轉換呢？
- $K_1(x,x')=(0+1\cdot x^Tx')^1$
- 不需要常數項 $\zeta$，因為會被 $b$ 處理掉
- $\gamma=1$ 即可，因為設別的也只是縮放資料
- **其實就是對應到原始的資料，不做任何 feature transform 啊**
- **稱為 linear kernel**
- 這樣可能甚至不需要解對偶問題 (dual problem)
- **linear kernel 值得先嘗試**

### Fun Time: Polynomial Kernel

## [Gaussian Kernel](https://www.youtube.com/watch?v=_-fIkbSBdF8&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=12)

### Kernel of Infinite Dimensional Transform
- 能不能利用 kernel 這個偷吃步，來計算無窮多維的 inner product 呢？
- 假設我們定義 $K(x,x')=\exp(-(x-x')^2)$ 那它到底對應到怎麼樣的 feature transform $\phi$，使得 $\phi(x)^T\phi(x')=\exp(-(x-x')^2)$ 呢？
- $\exp(-(x-x')^2)\\=\exp(-(x)^2)\exp(-(x')^2)\exp(2x^Tx')$
- **注意 $\exp(-(x-x')^2)$ 其實就是一個 高斯函數**
- 註：Gaussian function 
- $=\exp(-(x)^2)\exp(-(x')^2)(\sum_\limits{i=0}^\infty\dfrac{(2xx')^i}{i!})$
- 回想 **exponential 函數的 泰勒展開式(Taylor series)** $\exp(a)=\sum_\limits{i=0}^\infty \dfrac {a^i}{i!}$
- $=\sum_\limits{i=0}^\infty(\exp(-(x)^2)\exp(-(x')^2)\sqrt{\dfrac{2^i}{i!}}\sqrt{\dfrac{2^i}{i!}}(x)^i(x')^i)$
- 把 summation 放到外面
- $=\phi(x)^T\phi(x')$
- 把 $x$ 相關的放一邊；$x'$ 相關的放另一邊
- $\phi(x)=\exp(-x^2)\cdot\begin{bmatrix}1\\\sqrt{\frac 2{1!}}x\\\sqrt{\frac{2^2}{2!}}x^2\\\vdots\end{bmatrix}$
- $K(x,x')=\exp(-\gamma\|x-x'\|^2)$ with $\gamma>0$
- 跟上面推導 polynomial kernel 一樣，就算前面乘上一個 $\gamma$，也可以得到無窮多維的 feature transform 的內積

## [Comparison of Kernels](https://www.youtube.com/watch?v=sacJmcs8TKE&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=13)

### Linear Kernel: Cons and Pros

### Polynomial Kernel: Cons and Pros
- 缺點
- hyperparameter 有點多，難選
- 如果 degree $Q$ 很大，那很難對 kernel function 做 numerical computation
- 不論 $|\zeta+\gamma x^Tx'|$ 是大於或小於 1，對 QP solver 來說都很困難 (連乘多次後會太大或者太接近 0)
- 所以 **polynomial kernel 通常用比較小的 degree $Q$**
- 其實如果是很小的 degree $Q$(例如 2 或 3)，那麼直接展開出 $\phi_Q(x)$，再用特殊的 solver 解 primal problem，會比 dual 的還要快。

### Gaussian Kernel: Cons and Pros
- 缺點
- 解釋性低 (無法定義 $w$)
- 比 linear 慢
- 比較容易 overfitting

### Other Valid Kernels (Customize Kernels)
- 能不能自訂 kernel 呢? 可以，但要滿足條件
- kernel 是一種特別的相似度 (因為是在 $\mathcal Z$ 空間的內積) $\phi(x)^T\phi(x')$
- 但不是任何 similarity 都可以是 kernel
- **Mercer's condition 是判斷 kernel 的充分且必要條件**，假設 matrix $\text K$ 的每個 element $k_{ij}=K(x_i,x_j)$，則
- $\text K$ 是 **symmetric matrix**
- 也就是 $K(x_i,x_j)=K(x_j,x_i)$ 吧
- 因為 matrix $\text K$ 可以視為兩個 $Z$ 矩陣的相乘 $ZZ^T$，所以它必定是 **positive semi-definite** 的。
- 要檢查 Mercer's condition 還滿困難的，不過要自訂 kernel 就要檢查這些條件。

### Fun Time: Valid Kernel
- 線代沒學好，positive semi-definite 要怎判斷哈哈哈
- 
> k = (0,4,4,0) which is a 2-by-2 matrix. The first row is 0,4 and the second row is 4,0. This matrix has eigenvalue 4 and -4. So this is not a positive semi-definite matrix (definition is all eigenvalues are non-negative). hope this helps.

### Summary