[ML] 機器學習基石：第十一講 Linear Models for Classification

ML：基礎學習
課程：機器學習基石
簡介：第十一講 Linear Models for Classification

Error 比較

當 $y=1$ 時

$$\begin{array}{rl}er{r}_{0/1}(s,y)& =[sign(ys)\ne 1]\\ er{r}_{SQR}(s,y)& =(ys-1{)}^2\\ er{r}_{CE}(s,y)& =ln(1+e^{-ys})\\ er{r}_{SCE}(s,y)& =lo{g}_2(1+e^{-ys})\end{array}$$

為了方便會將 $er{r}_{CE}(s,y)$ 調整為 $er{r}_{SCE}(s,y)$，如右下圖

對於任意 $ys$ 當 $s={\mathbf{w}}^{\mathbf{Tx}}$
$$\begin{gathered} er{r}_{0/1}(s,y)\le er{r}_{SCE}(s,y)=\frac{1}{ln2}er{r}_{CE}(s,y) \\ \Rightarrow \{\begin{array}{ccc}{E}_{in}^{0/1}(\mathbf{w})& \le E_{in}^{SCE}(\mathbf{w})& =\frac{1}{ln2}{E}_{in}^{CE}(\mathbf{w})\\ E_{out}^{0/1}(\mathbf{w})& \le E_{out}^{SCE}(\mathbf{w})& =\frac{1}{ln2}{E}_{out}^{CE}(\mathbf{w})\end{array} \end{gathered}$$ $$\begin{array}{rl}{E}_{out}^{0/1}(\mathbf{w})& \le E_{in}^{0/1}(\mathbf{w})+{\mathrm{\Omega }}^{0/1}\\ & \le \frac{1}{ln2}{E}_{in}^{CE}(\mathbf{w})+{\mathrm{\Omega }}^{0/1}\end{array}$$ 故當 $E_{in}^{CE}(\mathbf{w})$ 變小時，也意味著 $E_{out}^{0/1}(\mathbf{w})$ 變小
linear regression 也可用同樣的方法得證之

實際運用方法

	PLA	linear regression	logistic regression
優點	線性可分時，很有效率	最簡單最佳化	簡單最佳化
缺點	無法得知是否線性可分，得使用 pocket 但效率與 logistic 差不多	當 $\left|ys\right|$ 太大，err 太過寬鬆	當 $-ys$ 太大，err 太過寬鬆

實務上會使用 linear regression 設定 ${\mathbf{w}}_{\mathbf{0}}$，然後再使用 logistic regression 最佳化

Stochastic Gradient

logistic Regression 更新公式如下，那麼有辦法改成像 PLA 一樣，看見一個 $({\mathbf{x}}_{\mathbf{n}},y)$ 就更新一次嗎？

$$\text{Double subscripts: use braces to clarify}$$

換個想法，平均是否跟期望值很接近，那麼用隨機抽點的方法再平均抽出來的點，是否也是 ok 的？

$$\begin{gathered} {▽}_{\mathbf{w}}{E}_{in}(\mathbf{w})=\underset{randomn}{\epsilon }{▽}_{\mathbf{w}}err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n) \\ {▽}_{\mathbf{w}}err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n)={▽}_{\mathbf{w}}err(\mathbf{w})+zeromean"noise" \end{gathered}$$

演算法

1. 將原先的梯度 ${▽}_{\mathbf{w}}err(\mathbf{w})$ 改為 stochastic gradient ${▽}_{\mathbf{w}}err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n)$ 
2.  經過足夠的次數
•  平均 ${▽}_{\mathbf{w}}err(\mathbf{w})\approx$ 平均 ${▽}_{\mathbf{w}}err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n)$
3.  優缺點
• 優點：簡單快速，可用在 online 學習
• 缺點：不夠穩定，因可能一下走對，一下走錯

SGD logistic regression

$$\text{Double subscripts: use braces to clarify}$$

SGD 與 PLA 相似處，如上

• SGD 可視為 soft PLA，錯多少就更新多少
• $\eta =1$ 時，$\text{Double subscripts: use braces to clarify}$ 又很大，兩者可視為一樣

實際經驗運用的方式

• 停止條件 => 跑夠多次，因若還 check gradient 就回到原先較沒效率的方式
• 經驗 $\eta =0.1$，若 $\mathbf{x}$ 範圍適當

Python 原始碼

import matplotlib.pyplot as plt
import numpy as np
import operator
import math
import random
 
# 網路上找的 dataset 可以線性分割
rawData = [
    ((-0.4, 0.3), -1),
    ((-0.3, -0.1), -1),
    ((-0.2, 0.4), -1),
    ((-0.1, 0.1), -1),
    ((0.9, -0.5), 1),
    ((0.7, -0.9), 1),
    ((0.8, 0.2), 1),
    ((0.4, -0.6), 1),
    ((0.2, 0.6), -1),
    ((-0.5, -0.5), -1),
    ((0.7, 0.3), 1),
    ((0.9, -0.6), 1),
    ((-0.1, 0.2), -1),
    ((0.3, -0.6), 1),
    ((0.5, 0.1), -1), ]
 
# 加入 x0
dataset = [((1,) + x, y) for x, y in rawData]
 
# 內積
def dot(*v):
    return sum(map(operator.mul, *v))
 
# 計算向量長度
def vlen(v):
    square = map(operator.mul, v, v)
    return sum(square) ** (1/2)
 
# 取 thita
def thita(v):
    return 1 / ( 1 + math.exp( -v ))
     
# 計算梯度
def gradient(w, dataset):
    setsV = []
    for x, y in dataset:
        setsV.append( map(operator.mul, [thita(-y*dot(w, x)) * (y)] * len(x), x) )
    sum = [0] * len(x)
    for v in setsV:
        sum = map(operator.add, sum, v)
    
    sum = map(operator.truediv, sum, [1]*len(x))
    return list(sum)
 
# 更新 w
def update(w, n, g):
    u = map(operator.mul, [n] * len(g), g)
    w = map(operator.add, w, u)
    return list(w)
 
# 用 w 畫圖 
def plotfig(w):
    # 畫圖
    fig = plt.figure()
 
    # numrows=1, numcols=1, fignum=1
    ax1 = fig.add_subplot(111)
 
    xx = list(filter(lambda d: d[1] == -1, dataset))
    ax1.scatter([x[0][1] for x in xx], [x[0][2] for x in xx],
                s=100, c='b', marker="x", label='-1')
    oo = list(filter(lambda d: d[1] == 1, dataset))
    ax1.scatter([x[0][1] for x in oo], [x[0][2] for x in oo],
                s=100, c='r', marker="o", label='1')
    l = np.linspace(-2, 2)
 
    # w0 + w1x + w2y = 0
    # y = -w0/w2 - w1/w2 x
    if w[2]:
        a, b = -w[1] / w[2], -w[0] / w[2]
        ax1.plot(l, a * l + b, 'b-')
    else:
        ax1.plot([-w[0] / w[1]] * len(l), l, 'b-')
 
    plt.legend(loc='upper left', scatterpoints=1)
    plt.show() 
 
# SGD Logistic Regression演算法實作
def SGD_logisticRegression(dataset):
    # 初始化 w
    w = [0] * 3
 
    t = 0
    n = 0.1
    max_number = 1000
    while True:     
        g = gradient(w,  [random.choice(dataset)])
        print("g {:.5f} => {}: {}".format(vlen(g), t, tuple(w)))
        
        w = update(w, n, g)
        
        t += 1
 
        if t > max_number:
            break
 
    return w
 
# 主程式
def main():
    # 執行
    w = SGD_logisticRegression(dataset)
    plotfig(w)
    
if __name__ == '__main__':
    main()
 

SGD 並不限定 logistic，例：也可用在 linear regression 上，$\text{Double subscripts: use braces to clarify}$

多類別分類

One-Versus-All (OVA)

如下，但若出現在中間區域或重疊的部分，又該如何決定呢？

那改為可能性表示呢？例如用 logistic regression 選出最大可能性
且因為 $\theta$ 為 monotonic 的，所以只需比較 ${\mathbf{w}}_{\mathbf{[}\mathbf{k}\mathbf{]}}^{\mathbf{T}}\mathbf{x}$ 大小

演算法

1. $k\in \mathbf{y}$， $\mathbf{y}$ 表示有多少類別
• 利用 logistic regression，得到 ${\mathbf{w}}_{\mathbf{[}\mathbf{k}\mathbf{]}}$
  邊跑邊重新定義資料即可
  $D_{[k]}={\{({\mathbf{x}}_{\mathbf{n}},y_n^{\prime }=2[y_n=k]-1)\}}_{n=1}^N$
2. 回傳最大的可能性 $g(\mathbf{x})=argma{x}_{k\in \mathbf{y}}({\mathbf{w}}_{\mathbf{[}\mathbf{k}\mathbf{]}}^{\mathbf{T}}\mathbf{x})$

優缺點

• 優點：非常有效率，可平行處理，可搭配類似 logistic 的方法
• 缺點：因 1 對多，資料容易不平衡，會出現一直說同一個答案的解法

計算效率
若有 K-class，大小為 N
需學習 K 個 logistic regressioin，每個大小皆為 N

One versus One (OVO)

演算法

1.  $(k,l)\in \mathbf{y}\times \mathbf{y}$
• 利用 linear binary classification 得到 ${\mathbf{w}}_{\mathbf{[}\mathbf{k}\mathbf{,}\mathbf{l}\mathbf{]}}$
  邊跑邊重新定義資料即可
  $D_{[k,l]}=\{({\mathbf{x}}_{\mathbf{n}},y_n^{\prime }=2[y_n=k]-1):y_n=kor{y}_n=l\}$
2. 回傳最多票數 $g(\mathbf{x})=\left\{{\mathbf{w}}_{\mathbf{[}\mathbf{k}\mathbf{,}\mathbf{l}\mathbf{]}}^{\mathbf{T}}\mathbf{x}\right\}$

優缺點

• 優點：穩定有效率，因資料變小，可搭配任何二元分類的方法
• 缺點：使用 $C_2^K$ 個 ${\mathbf{w}}_{\mathbf{[}\mathbf{k}\mathbf{,}\mathbf{l}\mathbf{]}}$，需要更多的空間、預測時間更長、更多的訓練

計算效率
若有個二元分類的方法，需用 $N^3$ 時間計算大小為 $N$ 的資料
有 K-class 的資料時，假設每個類別的大小皆為 $N$/K，若 K = 10 那麼需花多少時間？

$$\begin{array}{rl}T& =(\frac{2N}{K}{)}^3\times C_2^K\\ & =(\frac{8N^3}{1000})\times 45\\ & =\frac{9}{25}{N}^3\end{array}$$

若是 OVA 呢？

$$\begin{array}{rl}T& =N^3\times K\\ & =10N^3\end{array}$$

所以在這種情況 OVA 比 OVO 沒效率