---
tags: 機器學習基石下：方法篇
---

Ch11 Linear Models for Binary Classification
===

## Content

[TOC]

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

## [Linear Models for Binary Classification](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/W274w/linear-models-for-binary-classification)

### Linear Models Revisited
- 看起來 linear regression 跟 logistic regression 的 optimization 比較好解，那能不能用來幫助我們的 linear classification?

- 先定義一下 linear scoring function $s=w^Tx$
- 我們就可以重新寫下三種 linear model 的 error function
- $\text{err}=1[\text{sign}(ys)\neq 1]$ for **linear classification**
- 注意這裡的 $1[...]$ 表示如果中括號裡面是 true，就是1，否則0
- $\text{err}=(ys-1)^2$ for **linear regression**
- 注意這裡只用在正負 1 的輸出上，所以才會導出這結果 (把 $y$ 乘進去就導出來了)
- $\text{err}=\ln(1+\exp(-ys))$ for **logistic regression**
- 注意這個本來就長這樣
- **$ys$ 的物理意義可以看成我們 classification 的 correctness score**
- **也就是說我的 $ys$ 越大，代表我正確方向的分數越大**

### Visualizing Error Functions
- 藍色那條是 0/1 error
- 紅色那條是 squared error
- 它在 $ys=+1$ 時，的確有 0 的 error
- 但是在 $ys > +1$ 時，卻提高 error，這樣不好
- 灰色那條是 cross-entropy error
- 0/1 error 小 $\leftrightarrow$ cross-entropy error 小
- 為了推導方便，我們常常把 cross-entropy error 的 log 換成以 2 為底
- 其實就是除以 $\ln 2$
- 
- 現在 scaled cross-entropy 成了 0/1 error 的 upper bound

### Theoretical Implication of Upper Bound
- $E_{in}$ 會成立剛剛說的 scaled cross-entropy 會是 0/1 error 的 upper bound
- 同理，$E_{out}$ 也成立。
- 不管用左邊那種方式還是右邊那種方式計算，都會得到結論：
- $E_{out}^{0/1}(w)\leq\frac 1{\ln 2}E_{in}^{CE}(w)$
- **也就是說，若我們努力把 cross-entropy error 做好，那某種角度來看 0/1 error 也可以做得不錯**
- 其實同理，linear regression 也可以這樣，只不過 linear regression 是更寬鬆的 bound 而已。

- 前面說的做法叫 regression for classification，就是我拿到 data 就直接做 regression，但是在回傳 $g$ 的時候我是回傳 $\text{sign}(w^Tx)$
- 好處壞處看圖
- 大多數的人會使用 logistic regression 來取代 pocket
- 較容易 optimize
- (又有 soft classification)

## [Stochastic Gradient Descent](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/Ec6Qv/stochastic-gradient-descent)

### Two Iterative Optimization Schemes
- PLA 的一次 iteration 只需要花 $O(1)$ 的時間複雜度
- logistic regression 卻需要花 $O(N)$ 的時間複雜度，跟 pocket 差不多了
- 能不能不要花 $O(N)$?

### Logistic Regression Revisited
- 現在要計算 gradient 必須要對那個 term 取平均，要計算 $N$ 次那個 term
- 隨機抽 $n$ 個點，然後平均，期望值上來說，會跟我把 $N$ 個點直接做平均很接近。
- 那我們現在做比較 extreme 的 case 就是 $n=1$。

### Stochastic Gradient Descent (SGD)
- 可以視為真正的 gradient 加上 zero-mean 的 noise
- 只要走夠多步，那平均來說就跟真正的 GD 差不多
- pros:
- simple & cheaper computation
- useful for **big data** or **online learning**
- cons:
- less stable in nature
- 現在把 logistic regression 的 GD 換成 SGD
- $w_{t+1}\leftarrow w_t+\eta\theta(-y_nw_t^Tx_n)(y_nx_n)$
- 有沒有覺得很眼熟？~~(沒有)~~

### PLA Revisited
- 觀察 SGD 的規則，我們發現可以把 SGD logistic regression 看成是 PLA 的 soft 版本
- PLA 是：有錯就更新，沒錯就不更新
- SGD logistic regression 是：看它錯多少就更新多少

### Fun Time: SGD for Linear Regression
- 只要把之前 gradient 的 $X$ 換成單一資料點 $x_n$ 即可。
- **物理意義是：我們也是往 $x_n$ 的方向更新，錯越多，就更新越多。**

## [Multiclass via Logistic Regression](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/cdEeC/multiclass-via-logistic-regression)

### Multiclass Classification
- 我們想要利用之前已經學會的 binary classification 來解 multi-class classification 的問題。

### One Class at a Time
- 一次只分類一個 class，看是不是它，這樣我們就得到 4 個 classifier

#### Multiclass Prediction: Combine Binary Classifiers
- 然後再根據剛剛這 4 個分類器決定是誰
- 但這樣會有問題
- 可能有兩個分類器都說是它
- 或者所有分類器都說不是它

### One Class at a Time Softly
- 既然如此那我要求我的每個分類器都告訴我，到底多大機率是它
- 就用 logistic regression 吧！

#### Multiclass Classification: Combine Soft Classifiers
- 然後選那個 estimated probability 最大的
- 其實不需要考慮 logistic function，所以把它漆成灰色的。

### One-Versus-All (OVA) Decomposition
- pros
- 有效率，我們有 $k$ 個 class 就做 $k$ 次 binary classification 就好
- 可以在不同機器上做平行運算。
- 只要演算法是可以輸出機率，或者輸出可以比大小數值的都適用
- cons
- 當 $k$ 很大，那麼對這 $k$ 個 classifier 來說，資料集是 unbalanced 的，也就是說 classifier 會有 trivial solution 是全都猜叉叉，它們就覺得自己做得很好了。
- 我們之前並沒有說機率加起來要是 1，而統計上其實有人做了真正的多類別 logistic regression

## [Multiclass via Binary Classification](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/boH6v/multiclass-via-binary-classification)

- 之前說 OVA 會 unbalanced，那就用 One Versus One 吧

### One versus One at a Time
- 每次就只拿兩個 class 的 data 出來，這樣一共會訓練 $C_2^k$ 個 classifier

- 可以把這些 classifier 看成是各個 class 之間的循環賽，最後有一個 class 會勝出
- $g(x)$ 就是 voting of classifiers

### One-versus-one (OVO) Decomposition
- pros:
- efficient (每個 classifier 用的 dataset 比較小)
- 任何 binary classification 都可以用
- cons:
- 我要花 $C^k_2$ 或者說 $O(K^2)$ 的力氣去儲存這些 $w$

### Fun Time: OVO
- $C^{10}_2(\dfrac{2N}{10})^3=\frac{9}{25}N^3$
- 可以注意到 OVA 花的時間多超多

### Summary