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

Ch5 Kernel Logistic Regression
===

## Content
[TOC]

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

## [Soft-Margin SVM as Regularized Model](https://www.youtube.com/watch?v=Bc8bg5ZkRdk&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=18)

### Wrap Up (SVM)
- 複習一下
- Hard-Margin Primal
- Hard-Margin Dual
- Soft-Margin Primal
- Soft-Margin Dual
- 實用的 library (台大 林志仁老師實驗室 開發)
- LIBLINEAR：專門解 linear SVM
- LIBSVM：專門解 kernel dual SVM

### Slack Variable $\xi_n$
- 之前說過
- $\xi_n$ 可以看成是在記錄 data point 違反 fat boundary 的量 (margin violation)
- 然後我們對 $\xi_n$ 加到 objective function 中做懲罰，希望可以一起 minimize
- 不過我們可以用另外一種觀點看 $\xi_n$
- 若有違反 fat boundary，則 $\xi_n=1-y_n(w^Tz_n+b)$
- 若無違反 fat boundary，則 $\xi_n=0$
- **所以又可以寫成 $\xi_n=\max(1-y_n(w^Tz_n+b),0)$**
- **這樣我們就可以把本來的 soft-margin SVM 問題寫成 'unconstrained' form $\min_\limits{b,w}\frac 12w^Tw+C\sum_n\max(1-y_n(w^Tz_n+b),0)$**
- > 林老师，您好！请问下第三个slide里面,怎么确定the unconstrained form of soft-margin SVM 没有损失optimality呢？谢谢！
>> 也許可以想想對每一組可能的 (w, b)，constrained form 和 unconstrained form 所得到的objective value 是不是一樣的……

### Unconstrained Form
- 這個形式其實就跟 L2 regularization 的形式很像啊
- 差別只在
- 這裡的 $w$ 並不包含 $b$，是個比較短的 $w$
- 本來的 $\lambda$ 現在變成 $C$ 的形式
- error function $\widehat{err}$ 現在變得比較複雜 $\widehat{err}=\max(1-y_n(w^Tz_n+b),0)$
- 那怎不直接解這個問題？
- 沒了 dual 和 QP，沒辦法用 kernel trick
- $\max(\cdot,0)$ 函數並非處處可微，較難 optimize

### SVM as a Regularized Model
- 看一下**表格，比較這四種 model 的差異**
- regularization by constraint
- hard-margin SVM
- L2 regularization
- soft-margin SVM
- 我們可以總結一下
- **large margin $\leftrightarrow$ 更少的 hypothesis $\leftrightarrow$ L2 regularization 想要的更短的 $w$**
- **soft margin $\leftrightarrow$ 特別的 $\widehat{err}$**
- **更大的 $C$ (不論是 regularization 的 constraint 還是 soft-margin SVM 的懲罰係數) $\leftrightarrow$ 更小的 regularization $\lambda$**
- 用這種觀點看是希望 SVM 可以延伸到其他的 models，產生連結。

### Fun Time: SVM as a Regularized Model

## [SVM versus Logistic Regression](https://www.youtube.com/watch?v=5K44AgZvcDk&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=19)

### Algorithmic Error Measure of SVM
- 現在把 $w^Tz+b$ 看成是 score $s$
- > Q: 感覺應該把 slide 上的 $n$ 拿掉？要嘛寫 $s=w^Tz+b$ 要嘛寫 $s_n=w^Tz_n+b$ 吧？
- 0/1 error 可以寫成 $err_{0/1}(s,y)=1[\![ys\leq 0]\!]$
- SVM error 可以寫成 $\widehat{err}_{SVM}(s,y)=\max(1-ys,0)$
- 畫圖可以看出 SVM error 是 0/1 error 的 upper bound
- SVM error 又稱為 **hinge error measure**
- SVM error 有兩個很好的性質：
- **是 0/1 error 的 upper bound，所以做好 SVM error 就是間接的做好 0/1 error**
- **SVM error 是 convex 的，所以很好 optimize**

### Connection between SVM and Logistic Regression
- 再來看看 SVM 和 (scaled) logistic regression 的 error
- $\widehat{err}_{SVM}=\max(1-ys,0)$
- $err_{SCE}=\log_2(1+\exp(-ys))$
- 複習一下基石，(scaled) logistic regression error 也是 0/1 error 的 upper bound
- 注意要以 2 為底的 log 才會是 upper bound
- 圖中的這一小段可以發現 SVM error 和 scaled cross entropy error 長得差不多
- 而且就算拉長來看，當 $ys$ 接近無限大或負無限大的時候，scaled logistic regression error 乘上一個常數也幾乎跟 SVM error 差不多
- $ys\rightarrow\infty$
- $\widehat{err}_{SVM}(s,y)=0$
- $\ln 2\cdot err_{SCE}(s,y)\approx 0$
- $ys\rightarrow -\infty$
- $\widehat{err}_{SVM}(s,y)\approx -ys$
- $\ln 2\cdot err_{SCE}(s,y)\approx -ys$
- **所以我們可以說 SVM 跟 L2-regularized logistic regression 非常相似**

### Linear Models for Binary Classification
- 這邊又印證了一次，如果解了 regularized LogReg，那就幾乎等於是解了 SVM
- ~~我有一個大膽的想法~~ 反過來說，如果解了 SVM，是不是就幾乎得到 logistic regression(以下簡稱 LogReg) 的解，那就可以把它的 weight 拿到 LogReg 裡面用來輸出 soft probability 呢？

### Fun Time: Error Measure of SVM

## [SVM for Soft Binary Classification](https://www.youtube.com/watch?v=pNfvZYH5iFg&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=20)

### SVM for Soft Binary Classification: Naïve Idea
- 那我能不能讓 SVM 有 soft probability 的 output 呢？
- Naïve Idea 1：直接解 SVM 的 weight 和 bias，然後代入 sigmoid function $\theta$
- 實務上會得到還不錯的解，因為 SVM 和 regularized LogReg 很相似
- **但是這樣就缺少了 LogReg 的思想，例如 maximum likelihood**
- Naïve Idea 2：那就用解 SVM 得到的 weight 和 bias 當成 LogReg 的初始值 $w_0$ 來解 LogReg？
- 其實直接解 LogReg 還比較快，因為它是 convex 的，很好解
- **而且這樣解也沒辦法做 kernel trick**
- 那到底能不能融合 SVM 和 LogReg 各自的優點呢？

### A Possible Model: Two-Level Learning
- 用 SVM 解出 $w_{SVM},b_{SVM}$ 之後 fix 住，在外面加上兩個自由度 $A,B$ 用 logistic regression 的 maximum likelihood 方式訓練
- 如果前面 SVM 解得好的話，通常之後解出來的 $A>0,B\approx 0$
- 我們可以把這種操作想成：先用 SVM 做 feature transform $\phi_{SVM}(x_n)=w_{SVM}^T\phi(x_n)+b_{SVM}$ 到一維，再做單維度的 logistic regression

### Probabilistic SVM
- 總結一下
- Probabilistic SVM 跟本來的 SVM boundary 不一定會一樣，因為有 $B$ 會 shift ($A$ 只是 scale 不影響)
- 解 LogReg 在這邊只有兩個變數，可以用更簡單的 solver 解
- 我們並不是真的在 $\mathcal Z$ 空間找到 logistic regression 的解，而是在 $\mathcal Z'$ 空間解 LogReg
- 那如果我們真的想在 $\mathcal Z$ 空間解出一個最好的 LogReg 該怎麼做？下節課會說明。

### Fun Time: Probabilistic SVM

## [Kernel Logistic Regression](https://www.youtube.com/watch?v=AbaIkcQUQuo&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=21)

### Key behind Kernel Trick
- 為什麼之前 SVM 可以用 kernel trick？
- 因為我們在求 feature transform $\phi(x)$ 的內積 $z^Tz'$
- 既然如此，若我們可以把解出來的 $w_*$ represent 成 $z_n$ 的 linear combination，就可以用 kernel trick 來解這個問題。
- $w_*=\sum_n\beta_nz_n$
- $w_*^Tz=\sum_n\beta_nz_n^Tz=\sum_n\beta_nK(x_n,x)$
- 其實我們之前就學過這樣的 algorithm 啦，複習
- SVM
- PLA
- LogReg by SGD
- 那什麼時候最好的 $w_*$ 可以 represented by 這些 $z_n$ 呢？

### Representer Theorem
- **Representer Theorem：任何 L2-regularized 的 linear model，它得到的 optimal solution 會是所有 $z_n$ 的 linear combination。**
- 也就是說
- for any $\min_\limits w\dfrac\lambda Nw^Tw+\dfrac 1N\sum_\limits{n=1}^N err(y_n,w^Tz_n)$
- optimal $w_*=\sum_\limits{n=1}^N\beta_nz_n$
- 這麼猛的嗎？證明？
- 這部分可能需要回想一些**線性代數**了
- 來，假設 optimal solution $w_*=w_\|+w_\perp$
- $w_\|\in span(z_1,z_2,...,z_N)$
- $w_\perp\perp span(z_1,z_2,...,z_N)$
- 也就是說 $w_*$ 可以分解成
- 落在 span 中的 vector $w_\|$
- 垂直於 span 的 vector $w_\perp$
- representer theorem 告訴我們 $w_\perp=0$，那我們就用反證法先假設 $w_\perp\neq 0$
- 發現 $err(y_n,w_*^Tz_n)=err(y_n,(w_\|+w_\perp)^Tz_n)=err(y_n,w_\|^Tz_n)$，$w_*$ 和 $w_\|$ 的 error function 有相同值
- 然後 $w_*^Tw_*=w_\|^Tw_\|+w_\perp^Tw_\perp>w_\|^Tw_\|$，發現 $w_\|$ 居然比 $w_*$ 還要更 optimal，矛盾！
- 所以 $w_\perp=0$，得證。
- **我們在這邊知道了，任何 L2-regularized 的 linear model 都可以被 kernelize**

### Kernel Logistic Regression
- 既然我們知道 **L2 regularized linear model 的 optimal solution $w_*$ 可以表示成 $\sum_n\beta_nz_n$**，就來 kernelize 一下 L2-regularized logistic regression 好ㄌ
- 那麼把符號代換一下就可以得到新的 optimization problem
- $\min_\limits\beta \frac\lambda N\sum_\limits{n=1}^N\sum_\limits{m=1}^N\beta_n\beta_mK(x_n,x_m)+\frac 1N\sum_n\log(1+\exp(-y_n\sum_\limits{m=1}^N\beta_mK(x_m,x_n)))$
- **現在成了優化 $\beta_1,...,\beta_N$ 的 unconstrained optimization**

### Kernel Logistic Regression (KLR): Another View
- 我們也可以把算出來的分數 $\sum_m\beta_mK(x_m,x_n)$ 看成是 $\beta$ vector 和 feature transformed data $K(x_n)$ 的 inner product
- $\beta = [\beta_1, \beta_2, ..., \beta_N]^T\in\mathbb R^N$
- $K(x_n)=[K(x_1,x_n),K(x_2,x_n),...,K(x_N,x_n)]^T\in\mathbb R^N$
- **因為 $K(x_n)$ 可以看成是對 $x_n$ 做某種 feature transform，output vector 是它和其他所有 data point 之間的相似性，而 $\beta$ 就扮演了這些 feature 的 weight。**
- 而左邊那項可以想成是 special regularizer $\beta^TK\beta$，比平常的 regularizer 多了 $K$ 矩陣做些縮放轉換而已。
- 所以 KLR 可以有兩種觀點
- 可以看成是 $\beta$ 的 linear model，而 kernel function 是 transform 並有 kernel regularizer
- 也可以看成是 $w$ 的 linear model，而 $\phi$ 是 (藏在 kernel function 裡的) transform，並有一般的 L2-regularizer
- 這些解釋也可以套到 SVM 上
- > Q: 幹這段好玄哦什麼 Gaussian SVM 給你一堆 Gaussian 的 linear combination 下次再回來看好ㄌ
- **但是這些 $\beta_n$ 大部分都不是 0，跟 SVM 差很多。**

### Fun Time:

### Summary
- 剛剛講的是 kernel for LogReg，**下次要講 kernel for 一般的 regression 問題。**