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

Ch6 Support Vector Regression
===

## Content
[TOC]

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

## RoadMap

## [Kernel Ridge Regression](https://www.youtube.com/watch?v=5uUob0VX83Y&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=23&t=0s)

### Recall: Representer Theorem
- 回想一下 Representer Theorem，任何 L2-regularzed 的 linear model，最佳解 $w_*$ 都會是 (transformed) feature 的線性組合
- for any L2-regularized linear model $\min_\limits w \frac\lambda Nw^Tw+\frac 1N\sum_nerr(y_n,w^Tz_n)$
- optimal solution $w_*=\sum_n\beta_nz_n$
- 所以任何 L2-regularized linear model 都可以被 kernelize
- linear regression 做 L2-regularization 就變 ridge regression
- $err(y,w^Tz)=(y-w^Tz)^2$
- **我們接下來就要把 ridge regression 給 kernelize，而且希望它跟 linear regression 一樣，有一步登天的解 (analytic/closed-form solution)**

### Kernel Ridge Regression Problem
- 直接把 $w_*=\sum_n\beta_nz_n$ 帶入 ridge regression 的 objective function，然後把 $z^Tz'$ 用 $K(x,x')$ 帶入
- 得到 $\min_\limits\beta\frac\lambda N\sum_n\sum_m\beta_n\beta_mK(x_n,x_m)+\frac 1N\sum_n(y_n-\sum_m\beta_mK(x_n,x_m))$
- $=\frac\lambda N\beta^TK\beta+\frac 1N(y-K\beta)^2$
- > Q: 這裡不太知道怎變的，可能要自己算一下
- $=\frac\lambda N\beta^TK\beta+\frac 1N(\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty)$
- 這樣問題就只剩下解 $\beta\in\mathbb R^N$

### Solving Kernel Ridge Regression
- $E_{aug}=\frac\lambda N\beta^TK\beta+\frac 1N(\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty)$
- 可以發現這是一個 $\beta$ 的二次式，來看看對 $\beta$ 的 gradient 怎麼算
- 對 $\lambda\beta^TK\beta$ 偏微分
- 得到 $2\lambda K\beta$，而 $K$ 是 symmetric 的，所以 $K=K^T$
- $=2\lambda K^TI\beta$
- 對 $\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty$ 偏微分
- 得到 $2K^TK\beta-2K^Ty$
- 所以 $\nabla E_{aug}(\beta)=\frac 2N(\lambda K^TI\beta+K^TK\beta-K^Ty)=\frac 2NK^T((\lambda I+K)\beta-y)$，若希望它等於 0，那麼
- 一種可能的解是 $(\lambda I+K)\beta-y=0$，這時候 $\beta=(\lambda I+K)^{-1}y$
- 而 $\lambda I+K$ 一定是 invertible 因為 $K$ 是半正定 (positive semi-definite)，可以複習 Mercer's condition
- 但是這樣要花 $O(N^3)$ 的 time complexity
- **現在終於可以透過 kernel 直接去 closed-form 解 $\mathcal Z$ 空間中的問題了。**

### Linear versus Kernel Ridge Regression
- linear ridge regression
- $\lambda I+X^TX$ 是 $d\times d$ 維
- 只能 linear
- time complexity 較低
- training $O(d^3+d^2N)$
- prediction $O(d)$
- kernel ridge regression
- $\lambda I+K$ 是 $N\times N$ 維
- 可以 feature transform
- time complexity 較高
- training $O(N^3)$
- prediction $O(N)$
- 計算資源多可以用 kernel，data 量太大不適合用 kernel

### Fun Time: Kernel Ridge Regression
- 直接把 $w_*=\sum_n\beta_nz_n$ 帶進去
- > Q: 這裡的 $w$ 應該已經包含 $b$ 嗎？

## [Support Vector Regression Primal](https://www.youtube.com/watch?v=rMTD31FFY3g&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=24&t=0s)

### Soft-Margin SVM versus Least-Squares SVM
- 之前在基石課說過，regression 得到的 weights 也可以拿來做 classification
- **用 kernel ridge regression 來做 classification 就叫做 least-squares SVM，簡稱 LSSVM**
- 叫他 least-squares 就是在強調它的 error function 是 squared error
- 之前的 soft-margin Gaussian SVM 跟 現在的 Gaussian LSSVM 有啥差別？
- 學出來的 boundary 幾乎一樣，但是 LSSVM 的 support vectors 數量多很多，因為 $\beta$ 大多不是 0
- 會導致 predict 速度很慢
- 圖中方框框就是 support vectors
- kernel logistic regression 其實也類似，$\beta$ 大多不是 0
- **那能不能在做 regression 的時候，做出 sparse 的 representation $\beta$ 呢？**

### Tube Regression
- > Q: x軸？ y軸是 $y$ 和 $\hat y$？
- 落在 tube(管子) 範圍內就當 error 是 0
- $|s-y|\leq\epsilon$：$0$
- 落在 tube 外面就計算它到 tube 的差距(y軸距離)
- $|s-y|>\epsilon$：$|s-y|-\epsilon$
- **所以可以把 error measure 寫成 $err(y,s)=\max(0,|s-y|-\epsilon)$**
- **通常被稱為 $\epsilon$-insensitive error**
- $\epsilon >0$

### Tube versus Squared Regression
- tube：$err(y,s)=\max(0,|s-y|-\epsilon)$
- squared：$err(y,s)=(s-y)^2$
- 比較一下 tube 和一般的 squared regression
- 當誤差小的時候，tube 和 squared regression 是差不多的
- 當誤差大的時候，squared error 會極速放大 error，所以 squared 更容易受到 outlier 影響
- 等等會說，tube regression 可以找到更 sparse 的 solution(representation?)。

### L2-Regularized Tube Regression
- L2 regularized tube regression 的 optimization problem $\min_\limits w\frac\lambda Nw^Tw+\frac 1N\sum_n\max(0,|w^Tz_n-y_n|-\epsilon)$
- 一般的 SVM 比 L2-regularized tube regression 多了些好處
- 雖然跟 tube 一樣不是處處可微，但是可以用 QP 解
- 雖然跟 tube 一樣都有 kernel trick，但是
- SVM 是利用 dual 和 KKT conditions 導致解有 sparsity
- 而 regularized tube regr. 是利用 representer theorem 來做 kernelize，因此並沒有 sparsity
- 那我們就來模仿一下 SVM 的 optimization problem，把原本的 L2 regularized tube 改成這樣，希望可以和 SVM 產生連結。
- $\min_{b,w}\frac 12w^Tw+C\sum_n\max(0,|w^Tz_n+b-y_n|-\epsilon)$
- 把 $b$ 從 $w$ 中獨立出來，把 $\lambda$ 變成 $C$

### Standard Support Vector Regression Primal
- 複習 [soft-margin SVM primal](https://hackmd.io/@johnnyasd12/BJ2kx1oy8#Soft-Margin-SVM)
- 想和 SVM 相似，我們就設置一些可以違反的量 $\xi$，把 $\xi$ 加到 minimize 的 objective function 還有 constraint 中
- 得到 optimization problem
- $\min_\limits{b,w,\xi}\quad\frac 12w^Tw+C\sum_n\xi_n$
- $\text{s.t.}\quad|w^Tz_n+b-y_n|\leq\epsilon+\xi_n\\\qquad \xi_n\geq 0$
- 但是這樣不是 quadratic programming 的 problem，因為 constraint 有絕對值，所以把 violation 拆成兩個
- 這樣就是一個標準的 Support Vector Regression (SVR) 的問題。
- minimize regularizer
- upper tube violation $\xi_n^\land$
- lower tube violation $\xi_n^\lor$

### Quadratic Programming for SVR
- $C$ 用來控制 regularization 和 tube violation 之間的 trade-off
- $\epsilon$ 用來控制 tube 的 (y軸)寬度
- 終於成了一個 QP 問題
- $\tilde d+1+2N$ 個 variables
- $2N+2N$ 個 constraints
- **再跟之前一樣轉成 dual problem 之後用 kernel trick，就可以移除 $\tilde d$ 的依賴。**

### Fun Time: SVR Primal

## [Support Vector Regression Dual](https://www.youtube.com/watch?v=0ZIKMdSAJio&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=25&t=0s)

### Lagrange Multipliers $\alpha^\land$ & $\alpha^\lor$
- 我們把 $|y_n-w^Tz_n-b|\leq\epsilon+\xi_n$ 拆成 $2N$ 個 constraint，所以共有 $2N$ 個 Lagrange multiplier $\alpha$
- 回想之前 $\xi_n>0$ 對應到的 Lagrange multiplier，其實都可以被 $\alpha$ 表示，所以就不寫了，專心解 $\alpha$
- > Q: 忘記在哪了ㄎㄎ
- 接下來幾乎就是重複 [Lec2](https://hackmd.io/@johnnyasd12/HkyoeuCRS#Starting-Point-Constrained-to-%E2%80%98Unconstrained%E2%80%99) 或 [Lec4](https://hackmd.io/@johnnyasd12/BJ2kx1oy8#Lagrange-Dual) 做過的事情，像是
- 把 Lagrange multiplier 乘上 constraint 加進 objective function 就得到 Lagrange function
- KKT condition
- 解 Lagrange function 對 $w,b$ 偏微分等於 0
- complementary slackness：Lagrange multiplier 和 constraint 乘積為 0
- 剩下的 dual problem 推導都和 Lec4 差不多，留給我們自己做
- > Q: 懶得做ㄏㄏ，下次ㄅ

### SVM Dual and SVR Dual
- 下面的藍色就是從上面的藍色來的，依此類推
- > Q: 之後再複習前面的ㄅ
- 原本 SVM 的 primal 跟 dual 其實都跟 SVR 很像
- 可以用類似的 QP solver 來解

### Sparsity SVR Solution
- 當 data 在 tube 內部(不在 boundary 上)，則
- $|w^Tz_n+b-y_n|<\epsilon$
- $\xi_n^\land=\xi_n^\lor=0$
- 就導致了 $\beta_n=0$
- 所以 support vectors 只能在 tube boundary 上或外面，也就是有了 sparse 的 $\beta$

### Fun Time: SVR Dual

## [Summary of Kernel Methods](https://www.youtube.com/watch?v=9OBWkHnzr2k&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=26&t=0s)

### Map of Linear Models
- column 1：解 classification 問題
- column 2：解 regression 問題
- column 3：解 soft classification 問題
- row 2：在 LIBSVM 常用

### Map of Linear/Kernel Models
- row 4：在 LIBSVM 常使用
- row 1：較少使用因為 performance 較差
- row 3：較少使用，因為 $\beta$ 很 dense，預測要花較多力氣

### Kernel Models

### Summary