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

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


Error 比較

當 \(y=1\) 時
$$ \begin{align*} err_{0/1}(s,y) &= [sign(ys)\neq 1]\\ err_{SQR}(s,y) &= (ys-1)^2\\ err_{CE}(s,y) &= ln(1+e^{-ys})\\ err_{SCE}(s,y) &= log_2(1+e^{-ys}) \end{align*} $$
為了方便會將 \(err_{CE}(s,y)\) 調整為 \(err_{SCE}(s,y)\)，如右下圖
對於任意 \(ys\) 當 \(s=\mathbf{w^Tx}\)
$$ err_{0/1}(s,y)\leq err_{SCE}(s,y)=\frac{1}{ln2}err_{CE}(s,y)\\ \Rightarrow \left\{\begin{matrix} E_{in}^{0/1}(\mathbf{w}) & \leq E_{in}^{SCE}(\mathbf{w}) & = \frac{1}{ln2} E_{in}^{CE}(\mathbf{w})\\ E_{out}^{0/1}(\mathbf{w}) & \leq E_{out}^{SCE}(\mathbf{w}) & = \frac{1}{ln2} E_{out}^{CE}(\mathbf{w})\\ \end{matrix}\right. $$ $$ \begin{align*} E_{out}^{0/1}(\mathbf{w}) &\le E_{in}^{0/1}(\mathbf{w})+\Omega ^{0/1}\\ &\le \frac{1}{ln2}E_{in}^{CE}(\mathbf{w})+\Omega ^{0/1}\\ \end{align*} $$ 故當 \(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_0}\)，然後再使用 logistic regression 最佳化

Stochastic Gradient

logistic Regression 更新公式如下，那麼有辦法改成像 PLA 一樣，看見一個 \((\mathbf{x_n},y)\) 就更新一次嗎？
$$ \mathbf{w_{t+1}}\leftarrow \mathbf{w_t}+\eta \frac{1}{N}\sum_{n=1}^{N}\theta (-y_n\mathbf{w^T_tx_n})(y_n\mathbf{x_n}) $$
換個想法，平均是否跟期望值很接近，那麼用隨機抽點的方法再平均抽出來的點，是否也是 ok 的？
$$ \triangledown _\mathbf{w}E_{in}(\mathbf{w})=\underset{random\ n}{\varepsilon }\triangledown _\mathbf{w}err(\mathbf{w,x_n},y_n)\\ \triangledown _\mathbf{w}err(\mathbf{w,x_n},y_n)=\triangledown _\mathbf{w}err(\mathbf{w})+zero\ mean\ "noise" $$
演算法
  1. 將原先的梯度 \(\triangledown _\mathbf{w}err(\mathbf{w})\) 改為 stochastic gradient \(\triangledown _\mathbf{w}err(\mathbf{w,x_n},y_n)\) 
  2.  經過足夠的次數
    •  平均 \(\triangledown _\mathbf{w}err(\mathbf{w}) \approx \) 平均 \(\triangledown _\mathbf{w}err(\mathbf{w,x_n},y_n)\)
  3.  優缺點
    • 優點：簡單快速，可用在 online 學習
    • 缺點：不夠穩定，因可能一下走對，一下走錯
SGD logistic regression
$$ \mathbf{w_{t+1}}\leftarrow \mathbf{w_t}+\eta \underset{-\triangledown err(\mathbf{w_t,x_n},y_n)}{\underbrace{\theta (-y_n\mathbf{w^T_tx_n})(y_n\mathbf{x_n})}}\\ \mathbf{w_{t+1}}\leftarrow \mathbf{w_t}+ \underset{\eta }{\underbrace{1}} \cdot \underset{\mathbf{v}}{\underbrace{([sign(\mathbf{w_t^Tx_n}\neq y_n)]\cdot y_n\mathbf{x_n})}} $$
SGD 與 PLA 相似處，如上
  • SGD 可視為 soft PLA，錯多少就更新多少
  • \(\eta =1\) 時，\(\mathbf{w_t^Tx_n}\) 又很大，兩者可視為一樣
實際經驗運用的方式
  • 停止條件 => 跑夠多次，因若還 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 上，\(2(y_n-\mathbf{w_t^Tx_n})\mathbf{x_n}\)

多類別分類


One-Versus-All (OVA)

如下，但若出現在中間區域或重疊的部分，又該如何決定呢？
那改為可能性表示呢？例如用 logistic regression 選出最大可能性
且因為 \(\theta \) 為 monotonic 的，所以只需比較 \(\mathbf{w^T_{[k]}x}\) 大小
演算法
  1. \(k \in \mathbf{y}\)， \(\mathbf{y}\) 表示有多少類別
    • 利用 logistic regression，得到 \(\mathbf{w_{[k]}}\)
      邊跑邊重新定義資料即可
      \(D_{[k]}=\left \{(\mathbf{x_n},{y}'_n=2[y_n=k]-1)  \right \}^N_{n=1}\)
  2. 回傳最大的可能性 \(g(\mathbf{x})=argmax_{k \in \mathbf{y}}(\mathbf{w^T_{[k]}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_{[k,l]}}\)
      邊跑邊重新定義資料即可
      \(D_{[k,l]}=\left \{(\mathbf{x_n},{y}'_n=2[y_n=k]-1):y_n=k\ or\ y_n=l  \right \}\)
  2. 回傳最多票數 \(g(\mathbf{x})=\left \{ \mathbf{w^T_{[k,l]}x}  \right \}\)
優缺點
  • 優點：穩定有效率，因資料變小，可搭配任何二元分類的方法
  • 缺點：使用 \(C^K_2\) 個 \(\mathbf{w_{[k,l]}}\)，需要更多的空間、預測時間更長、更多的訓練
計算效率
若有個二元分類的方法，需用 \(N^3\) 時間計算大小為 \(N\) 的資料
有 K-class 的資料時，假設每個類別的大小皆為 \(N\)/K，若 K = 10 那麼需花多少時間？
$$ \begin{align*} T &= (\frac{2N}{K})^3 \times C^K_2\\ &= (\frac{8N^3}{1000}) \times 45\\ &= \frac{9}{25}N^3 \end{align*} $$
若是 OVA 呢？
$$ \begin{align*} T &= {N}^3 \times K\\ &= 10N^3 \end{align*} $$
所以在這種情況 OVA 比 OVO 沒效率

留言

張貼留言