[ML] 機器學習基石：第二講 Learning to Answer Yes/No

ML：基礎學習
課程：機器學習基石
簡介：第二講 Learning to Answer Yes/No

PLA (Perceptron Learning Algorithm)

1. 選擇 ${\mathbf{w}}_{\mathbf{0}}$，可設為 0
2. For $t=0,1,\cdots$
1. $({\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}},y_{n(t)})$ 找到 ${\mathbf{w}}_{\mathbf{t}}$ 的下一個錯誤 (可用依序 or 亂數 or 其他選擇點的方法)
$$sign\left[{\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\right]\ne y_{n(t)}$$
2. 修正錯誤
$${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}+y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}$$
3. 直到所有點皆無錯誤

基本定義

$\mathbf{x}=(x_1,x_2,\cdots ,x_d)y=\{+1,-1\}h\in H$
忽略 $y=0$
$$\begin{array}{rl}h(\mathbf{x})& =sign[\left(\sum _{i=1}^d{w}_i{x}_i\right)-threshold]\\ & =sign[\left(\sum _{i=1}^d{w}_i{x}_i\right)+\underset{w_0}{\underbrace{(-threshold)}}\cdot \underset{x_0}{\underbrace{(+1)}}]\\ & =sign[\left(\sum _{i=1}^d{w}_i{x}_i\right)+w_0\cdot x_0]\\ & =sign\left[\sum _{i=0}^d{w}_i{x}_i\right]\\ & =sign\left[{\mathbf{w}}^{\mathbf{Tx}}\right]\end{array}$$

更新原理

$${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}+y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}$$

• 當 $y=+1$ 時，但 $\mathbf{wx}$ 卻為負，則將 $\mathbf{w}$ 靠近 $\mathbf{x}$
• 當 $y=-1$ 時，但 $\mathbf{wx}$ 卻為正，則將 $\mathbf{w}$ 遠離 $\mathbf{x}$

必要條件

資料需是線性可分，也就是可被分為各一半

線性可分的 $D$ $\iff$ 存在一完美 ${\mathbf{w}}_{\mathbf{f}}$ 使得 $y_n=sign({\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}})$ 證明

$$\begin{gathered} \because {\mathbf{w}}_{\mathbf{f}}\mathrm{完}\mathrm{美} \\ {y}_{n(t)}{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\ge \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}>0 \end{gathered}$$ ${\mathbf{w}}_{\mathbf{t}}$ 是否越來越靠近 ${\mathbf{w}}_{\mathbf{f}}$？
也就是 ${\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}}$ 隨著 $({\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}},y_{n(t)})$ 更新，是否越來越大？
$$\begin{array}{rl}{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}& ={\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}({\mathbf{w}}_{\mathbf{t}}+y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}})\\ & \ge {\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}}+\underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}\\ & >{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}}+0\end{array}$$ 以上證明，只得出一半，內積的變大也有可能是 ${\mathbf{w}}_{\mathbf{t}}$ 長度越來越長導致的
若 ${\mathbf{w}}_{\mathbf{t}}$ 只在犯錯才更新
$$sign({\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}})\ne y_{n(t)}\iff y_{n(t)}{\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\le 0$$ $$\begin{array}{rl}{\Vert {\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\Vert }^2& ={\Vert {\mathbf{w}}_{\mathbf{t}}+y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\Vert }^2\\ & =\Vert {\mathbf{w}}_{\mathbf{t}}{\Vert }^2+2y_{n(t)}{\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}+\Vert y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}{\Vert }^2\\ & \le \Vert {\mathbf{w}}_{\mathbf{t}}{\Vert }^2+0+\Vert y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}{\Vert }^2\\ & \le \Vert {\mathbf{w}}_{\mathbf{t}}{\Vert }^2+\underset{n}{max}\Vert y_n{\mathbf{x}}_{\mathbf{n}}{\Vert }^2\end{array}$$ $\Vert {\mathbf{w}}_{\mathbf{t}}{\Vert }^2$ 會慢慢成長，即使更新的是最長的 $\Vert {\mathbf{x}}_{\mathbf{n}}{\Vert }^2$，因 $y_n$ 不影響長度
或是從以下公式也可看出，會持續更新直到上限
初始於 ${\mathbf{w}}_{\mathbf{0}}=0$,經過 $T$ 次的更新後
$$\frac{{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{T}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \Vert {\mathbf{w}}_{\mathbf{T}}\Vert }\ge \sqrt{T}\cdot constant$$ 證明如下
若 ${\mathbf{w}}_{\mathbf{f}}$ 完美 $$y_{n(t)}{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\ge \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}>0(1)$$ 若 ${\mathbf{w}}_{\mathbf{t}}$ 只在犯錯才更新
$$sign({\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}})\ne y_{n(t)}\iff y_{n(t)}{\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\le 0(2)$$ 更新的方法
$${\mathbf{w}}_{\mathbf{t}}={\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}+y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}(3)$$ 針對 ${\mathbf{w}}_{\mathbf{t}}$ $$\begin{array}{rl}{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}}& ={\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}({\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}+y_{n(t-1)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{)}})by(3)\\ & \ge {\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}+\underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}by(1)\\ & \ge {\mathbf{w}}_{\mathbf{0}}+T\cdot \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}byTtimes\\ & \ge T\cdot \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}\end{array}$$ 針對 $\Vert {\mathbf{w}}_{\mathbf{t}}\Vert$ $$\begin{array}{rl}\Vert {\mathbf{w}}_{\mathbf{t}}{\Vert }^2& =\Vert {\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}+y_{n(t-1)}{{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{)}}}^2\Vert by(3)\\ & =\Vert {\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}{\Vert }^2+2y_{n(t-1)}{\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{)}}+\Vert y_{n(t-1)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{)}}{\Vert }^2\\ & \le \Vert {\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}{\Vert }^2+0+\Vert y_{n(t-1)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{-}\mathbf{1}\mathbf{)}}{\Vert }^{2}by(2)\\ & \le \Vert {\mathbf{w}}_{\mathbf{t}\mathbf{-}\mathbf{1}}{\Vert }^2+\underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}{\Vert }^2\\ & \le \Vert {\mathbf{w}}_{\mathbf{0}}{\Vert }^2+T\cdot \underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}{\Vert }^2\\ & =T\cdot \underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}{\Vert }^2\end{array}$$ 代入得證： $$\begin{array}{rl}\frac{{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \Vert {\mathbf{w}}_{\mathbf{t}}\Vert }& \ge \frac{T\cdot \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \Vert {\mathbf{w}}_{\mathbf{t}}\Vert }\\ & \ge \frac{T\cdot \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \cdot \sqrt{T}\cdot \underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}\Vert }\\ & \ge \frac{\sqrt{T}\cdot \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \cdot \underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}\Vert }\\ & =\sqrt{T}\cdot constant\end{array}$$ 因為 $\frac{{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{w}}_{\mathbf{t}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \Vert {\mathbf{w}}_{\mathbf{t}}\Vert }\le 1$ ，內積最大也只是長度的相乘 $$\begin{array}{rl}\sqrt{T}\cdot constant& \le 1\\ \\ \frac{\sqrt{T}\cdot \underset{n}{min}{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert \cdot \underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}\Vert }& \le 1\\ \\ T\le \frac{\Vert {\mathbf{w}}_{\mathbf{f}}{\Vert }^2\cdot \underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}{\Vert }^2}{{\underset{n}{min}}^2{y}_n{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}}}& =\frac{R^2}{{\rho }^2}\end{array}$$ $$\begin{gathered} R=\underset{n}{max}\Vert {\mathbf{x}}_{\mathbf{n}}\Vert (\mathrm{最}\mathrm{遠}\mathrm{的}\mathrm{半}\mathrm{徑}) \\ \rho =\underset{n}{min}{y}_n\frac{{\mathbf{w}}_{\mathbf{f}}^{\mathbf{T}}}{\Vert {\mathbf{w}}_{\mathbf{f}}\Vert }{\mathbf{x}}_{\mathbf{n}}(\mathrm{最}\mathrm{接}\mathrm{近}\mathrm{分}\mathrm{隔}\mathrm{線}\mathrm{的}{\mathbf{x}}_{\mathbf{n}}\mathrm{與}\mathrm{法}\mathrm{向}\mathrm{量}\mathrm{的}\mathrm{內}\mathrm{積}) \end{gathered}$$

PLA 程式碼

Python 原始碼

import matplotlib.pyplot as plt
import numpy as np
import operator
 
# 網路上找的 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)]
 
# 加入 x0
dataset = [((1,) + x, y) for x, y in rawData]
 
 
# 內積
def dot(*v):
    return sum(map(operator.mul, *v))
 
 
# 取 sign (1, 0, -1)
def sign(v):
    if v > 0:
        return 1
    elif v == 0:
        return 0
    else:  # v < 0
        return -1
 
 
# 判斷有沒有分類錯誤
def check_error(w, x, y):
    if sign(dot(w, x)) != y:
        return True
    else:
        return False
 
 
# 更新 w
def update(w, x, y):
    u = map(operator.mul, [y] * len(x), x)
    w = map(operator.add, w, u)
    return list(w)
 
 
# PLA演算法實作
def pla(dataset):
    # 初始化 w
    w = [0] * 3
 
    t = 0
    while True:
        print("{}: {}".format(t, tuple(w)))
        no_error = True
        for x, y in dataset:
            if check_error(w, x, y):
                w = update(w, x, y)
                no_error = False
                break
        t += 1
 
        if no_error:
            break
 
    return w
 
 
# 主程式
def main():
    # 執行
    w = pla(dataset)
 
    # 畫圖
    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()
 
 
if __name__ == '__main__':
    main()
 

PLA 缺點

• 無法得知 $D$ 是否線性可分
• 即使線性可分，也無法得知要跑多久，因為需要 ${\mathbf{w}}_{\mathbf{f}}$

若資料不為線性可分 或 有雜訊

找到錯誤最少的線
$${\mathbf{w}}_{\mathbf{g}}\leftarrow \underset{\mathbf{w}}{argmin}\sum _{n=1}^N[y_n\ne sign({\mathbf{w}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}})]$$ 但為 NP-hard 需花費大量時間解，故使用 Pocket Algorithm (PLA 變形)

Pocket Algorithm (PLA 變形)

1. 初始化 $\hat{\mathbf{w}}$
2. For $t=0,1,\cdots$
1. $({\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}},y_{n(t)})$ 找到 ${\mathbf{w}}_{\mathbf{t}}$ 的下一個錯誤 (亂數選擇較佳)
$$sign\left[{\mathbf{w}}_{\mathbf{t}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}\right]\ne y_{n(t)}$$
2. 修正錯誤
$${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}+y_{n(t)}{\mathbf{x}}_{\mathbf{n}\mathbf{(}\mathbf{t}\mathbf{)}}$$
3. 假如 ${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}$ 的錯誤比 $\hat{\mathbf{w}}$ 少，則將 ${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}$ 設為 $\hat{\mathbf{w}}$
4. 直到足夠的次數 或 小於設定的錯誤門檻

Pocket Algorithm 程式碼

Python 原始碼

import matplotlib.pyplot as plt
import numpy as np
import operator
import random
 
# 網路上找的 dataset 再加上亂數的 data 不可以線性分割
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))
 
 
# 取 sign (1, 0, -1)
def sign(v):
    if v > 0:
        return 1
    elif v == 0:
        return 0
    else:  # v < 0
        return -1
 
 
# 判斷有沒有分類錯誤
def check_error(w, x, y):
    if sign(dot(w, x)) != y:
        return True
    else:
        return False
 
 
# 更新 w
def update(w, x, y):
    u = map(operator.mul, [y] * len(x), x)
    w = map(operator.add, w, u)
    return list(w)
 
 
# 總錯誤數
def sum_errors(w, dataset):
    errors = 0
    for x, y in dataset:
        if check_error(w, x, y):
            errors += 1
 
    return errors
 
 
# POCKET 演算法實作
def pocket(dataset):
    # 初始化 w
    w = [0] * 3
    min_e = sum_errors(w, dataset)
 
    max_t = 500
    for t in range(0, max_t):
        wt = None
        et = None
 
        while True:
            x, y = random.choice(dataset)
            if check_error(w, x, y):
                wt = update(w, x, y)
                et = sum_errors(wt, dataset)
                break
 
        if et < min_e:
            w = wt
            min_e = et
 
        print("{}: {}".format(t, tuple(w)))
        print("min erros: {}".format(min_e))
 
        t += 1
 
        if min_e == 0:
            break
 
    return (w, min_e)
 
 
# 主程式
def main():
    # 執行，並輸入新的 list
    w, e = pocket(list(dataset))
 
    # 畫圖
    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()
 
 
if __name__ == '__main__':
    main()
 

假設資料為線性可分，卻跑 Pocket Algorithm 的缺點

• Pocket Algorithm 比 PLA 慢
• 花力氣存檔，把最佳解存起來
• 要檢查所有資料的錯誤才能比較 ${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}$ 和 $\hat{\mathbf{w}}$
• 但跑夠久，仍可得到 ${\mathbf{w}}_{\mathbf{POCKET}}={\mathbf{w}}_{\mathbf{PLA}}$