[ML] 機器學習基石：第十講 Logistic Regression

ML：基礎學習
課程：機器學習基石
簡介：第十講 Logistic Regression

$$\begin{gathered} \mathbf{x}=(x_0,x_1,x_2,\cdots ,x_d) \\ s=\sum _{i=0}^d{w}_i{x}_i \\ \theta (s)=\frac{e^s}{1+e^s}=\frac{1}{1+e^{-s}} \\ h(\mathbf{x})=\frac{1}{1+e^{-{\mathbf{w}}^{\mathbf{Tx}}}} \end{gathered}$$

比較

$$s={\mathbf{w}}^{\mathbf{Tx}}$$

$E_{in}(\mathbf{w})$ 的定義

cross-entropy error $$\begin{gathered} err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n)=ln(1+e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}}) \\ {E}_{in}(\mathbf{w})=\frac{1}{N}\sum _{n=1}^{N}err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n) \end{gathered}$$

$$targetfunctionf(\mathbf{x})=P(+1|\mathbf{x})\iff P(y|\mathbf{x})=\{\begin{array}{cc}f(\mathbf{x})& fory=+1\\ 1-f(\mathbf{x})& fory=-1\end{array}$$ $f$ 是正確的，所以 $f$ 產生 $D$ 這些資料的機率是很大的，甚至是 1
所以從 $h$ 找出最大機率的 $g$ 就能接近 $f$
$$\begin{array}{rl}Assume& likelihood(h)\approx probabilityusingf\approx large\\ IfD& =\{({\mathbf{x}}_{\mathbf{1}},\mathrm{o}),({\mathbf{x}}_{\mathbf{2}},\mathrm{x})\cdots \}\\ P(\mathrm{o})=P({\mathbf{x}}_{\mathbf{1}})P(\mathrm{o}|{\mathbf{x}}_{\mathbf{1}})& =P({\mathbf{x}}_{\mathbf{1}})f({\mathbf{x}}_{\mathbf{1}})\approx P({\mathbf{x}}_{\mathbf{1}})h({\mathbf{x}}_{\mathbf{1}})\\ P(\mathrm{x})=P({\mathbf{x}}_{\mathbf{2}})P(\mathrm{x}|{\mathbf{x}}_{\mathbf{2}})& =P({\mathbf{x}}_{\mathbf{2}})(1-f({\mathbf{x}}_{\mathbf{2}}))\approx P({\mathbf{x}}_{\mathbf{2}})(1-h({\mathbf{x}}_{\mathbf{2}}))\\ ⋮& =⋮\\ g=\underset{h}{argmax}& likelihood(h)\\ h(\mathbf{x})=\theta ({\mathbf{w}}^{\mathbf{Tx}})& \Rightarrow 1-h(\mathbf{x})=h(\mathbf{-}\mathbf{x})\\ likelihood(h)& =P({\mathbf{x}}_{\mathbf{1}})h({\mathbf{x}}_{\mathbf{1}})\times P({\mathbf{x}}_{\mathbf{2}})(1-h({\mathbf{x}}_{\mathbf{2}}))\times \cdots P({\mathbf{x}}_{\mathbf{n}})(1-h({\mathbf{x}}_{\mathbf{n}}))\\ & =P({\mathbf{x}}_{\mathbf{1}})h({\mathbf{x}}_{\mathbf{1}})\times P({\mathbf{x}}_{\mathbf{2}})(h(\mathbf{-}{\mathbf{x}}_{\mathbf{2}}))\times \cdots P({\mathbf{x}}_{\mathbf{n}})(h(\mathbf{-}{\mathbf{x}}_{\mathbf{n}}))\\ \because P({\mathbf{x}}_{\mathbf{1}})& =P({\mathbf{x}}_{\mathbf{2}})=\cdots =P({\mathbf{x}}_{\mathbf{n}})\\ \therefore likelihood(h)& \propto \prod _{n=1}^{N}h(y_n{\mathbf{x}}_{\mathbf{n}})\\ \\ hislogisticfunction\\ \underset{h}{max}likelihood(logistich)& \propto \underset{h}{max}\prod _{n=1}^{N}h(y_n{\mathbf{x}}_{\mathbf{n}})\\ \underset{\mathbf{w}}{max}likelihood(\mathbf{w})& \propto \underset{\mathbf{w}}{max}\prod _{n=1}^N\theta (y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})\\ & \propto \underset{\mathbf{w}}{max}ln\prod _{n=1}^N\theta (y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})\\ & \propto \underset{\mathbf{w}}{max}\sum _{n=1}^{N}ln\theta (y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})\\ & \propto \underset{\mathbf{w}}{min}\sum _{n=1}^N-ln\theta (y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})\\ & \propto \underset{\mathbf{w}}{min}\frac{1}{N}\sum _{n=1}^N-ln\theta (y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})\\ \\ \theta (s)=\frac{1}{1+e^{-s}}& :\underset{w}{min}\frac{1}{N}\sum _{n=1}^N-ln(\frac{1}{1+e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}}})\\ & =\underset{w}{min}\frac{1}{N}\sum _{n=1}^{N}ln(1+e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}})\\ & =\underset{w}{min}\frac{1}{N}\sum _{n=1}^{N}err(\mathbf{w}\mathbf{,}{\mathbf{x}}_{\mathbf{n}},y_n)\\ & =\underset{w}{min}{E}_{in}(\mathbf{w})\end{array}$$ 那為何跟 cross-entropy error 有關呢？
首先 cross-entropy 的定義為 $$H(p,q)=-\sum _{x}p(x)\cdot \log q(x)$$ 因 $p(x)$ 是目標值，不是 1 就是 0
而 $q(x)$ 則是實際的機率，代入 logistic function 做為機率的模型，也可用其他的 sigmoid function 取代
再利用 cross-entropy 比較兩者的差異
$$\begin{array}{rl}{E}_{in}& =-\sum _{x}p(x)\cdot \log q(x)\\ & =-\sum _{x}p(x)\cdot \log q(x)+(1-p(x))\cdot \log (1-q(x))\\ \because q(x)=\frac{1}{1+e^{-x}}& =-\sum _{x}p(x)\cdot \log \frac{1}{1+e^{-x}}+(1-p(x))\cdot \log (1-\frac{1}{1+e^{-x}})\\ & =-\sum _x-p(x)\cdot \log (1+e^{-x})+(1-p(x))\cdot \log (\frac{e^{-x}}{1+e^{-x}})\\ & =-\sum _x-p(x)\cdot \log (1+e^{-x})+(1-p(x))\cdot (-x-\log (1+e^{-x}))\\ & =\sum _{x}p(x)\cdot \log (1+e^{-x})-(1-p(x))\cdot (-x-\log (1+e^{-x}))\\ & =\sum _{x}p(x)\cdot \log (1+e^{-x})+x+\log (1+e^{-x})-p(x)x-p(x)\cdot \log (1+e^{-x}))\\ & =\sum _{x}x+\log (1+e^{-x})-p(x)x\end{array}$$ 而在之前的推導，若不將 $1-h(\mathbf{x})=h(\mathbf{-}\mathbf{x})$，而是維持，改用 $f(\mathbf{x})$ 表示
$$\begin{array}{rl}Assume& likelihood(h)\approx probabilityusingf\approx large\\ IfD& =\{({\mathbf{x}}_{\mathbf{1}},\mathrm{o}),({\mathbf{x}}_{\mathbf{2}},\mathrm{x})\cdots \}\\ P(\mathrm{o})=P({\mathbf{x}}_{\mathbf{1}})P(\mathrm{o}|{\mathbf{x}}_{\mathbf{1}})& =P({\mathbf{x}}_{\mathbf{1}})f({\mathbf{x}}_{\mathbf{1}})\approx P({\mathbf{x}}_{\mathbf{1}})h({\mathbf{x}}_{\mathbf{1}})\\ P(\mathrm{x})=P({\mathbf{x}}_{\mathbf{2}})P(\mathrm{x}|{\mathbf{x}}_{\mathbf{2}})& =P({\mathbf{x}}_{\mathbf{2}})(1-f({\mathbf{x}}_{\mathbf{2}}))\approx P({\mathbf{x}}_{\mathbf{2}})(1-h({\mathbf{x}}_{\mathbf{2}}))\\ ⋮& =⋮\\ g=\underset{h}{argmax}& likelihood(h)\\ likelihood(h)& =P({\mathbf{x}}_{\mathbf{1}})h({\mathbf{x}}_{\mathbf{1}})\times P({\mathbf{x}}_{\mathbf{2}})(1-h({\mathbf{x}}_{\mathbf{2}}))\times \cdots P({\mathbf{x}}_{\mathbf{n}})(1-h({\mathbf{x}}_{\mathbf{n}}))\\ \because P({\mathbf{x}}_{\mathbf{1}})& =P({\mathbf{x}}_{\mathbf{2}})=\cdots =P({\mathbf{x}}_{\mathbf{n}})\\ \therefore likelihood(h)& \propto h({\mathbf{x}}_{\mathbf{1}})\times (1-h({\mathbf{x}}_{\mathbf{2}}))\times \cdots (1-h({\mathbf{x}}_{\mathbf{n}}))\\ & =\prod _{n=1}^N(h({\mathbf{x}}_{\mathbf{n}}){)}^{f({\mathbf{x}}_{\mathbf{n}})}(1-h({\mathbf{x}}_{\mathbf{n}}){)}^{1-f({\mathbf{x}}_{\mathbf{n}})}\\ \therefore likelihood(h)& \propto \log \prod _{n=1}^N(h({\mathbf{x}}_{\mathbf{n}}){)}^{f({\mathbf{x}}_{\mathbf{n}})}(1-h({\mathbf{x}}_{\mathbf{n}}){)}^{1-f({\mathbf{x}}_{\mathbf{n}})}\\ & =\sum _{n=1}^{N}f({\mathbf{x}}_{\mathbf{n}})\cdot \log (h({\mathbf{x}}_{\mathbf{n}})+(1-f({\mathbf{x}}_{\mathbf{n}}))\cdot \log (1-h({\mathbf{x}}_{\mathbf{n}}))\end{array}$$ 可看到此項與先前推導的 cross-entropy 的第二項是一樣的
而 $y$ 的值會影響 $f(\mathbf{x})$
$$\{\begin{array}{cc}f(\mathbf{x})=1& fory=+1\\ f(\mathbf{x})=0& fory=-1\end{array}$$

最小化 $E_{in}(\mathbf{w})$

因為 $E_{in}(\mathbf{w})$ 連續可微、二次可微、convex function，故可用梯度求解 $▽E_{in}(\mathbf{w})=0$

$$▽E_{in}(\mathbf{w})=\frac{1}{N}\sum _{n=1}^N\theta (-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})(-y_n{\mathbf{x}}_{\mathbf{n}})=0$$

利用微分連鎖率 $$\begin{array}{rl}{E}_{in}(\mathbf{w})& =\frac{1}{N}\sum _{n=1}^{N}ln(1+e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}})\\ \frac{\partial E_{in}(\mathbf{w})}{\partial w_i}& =\frac{1}{N}\sum _{n=1}^{N}ln(1+e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}})\\ & =\frac{1}{N}\sum _{n=1}^N\frac{1}{1+e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}}}\times e^{-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}}}\times -y_n{x}_{n,i}\\ & =\frac{1}{N}\sum _{n=1}^N\theta (-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})\times -y_n{x}_{n,i}\\ ▽E_{in}(\mathbf{w})& =\frac{1}{N}\sum _{n=1}^N\theta (-y_n{\mathbf{w}}_{\mathbf{n}}^{\mathbf{Tx}})(-y_n{\mathbf{x}}_{\mathbf{n}})\end{array}$$

更新方程式

$${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}+\eta \mathbf{v}$$ 以 PLA 為例 $$\text{Double subscripts: use braces to clarify}$$

最小化的方法

$$\begin{gathered} {\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}+\eta \mathbf{v} \\ {\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}-\eta \frac{▽E_{in}({\mathbf{w}}_{\mathbf{t}})}{\Vert ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\Vert } \end{gathered}$$

$$\underset{\Vert \mathbf{v}\Vert =1}{min}{E}_{in}({\mathbf{w}}_{\mathbf{t}}+\eta \mathbf{v})for\eta >0$$ 從一小段線段來看且 $\eta$ 夠小，從泰勒展開的餘項，或微分定理都可得到
$$\begin{gathered} f{}^{\prime }(x)=\underset{dx\to 0}{lim}\frac{f(x+dx)-f(x)}{dx} \\ {E}_{in}({\mathbf{w}}_{\mathbf{t}}+\eta \mathbf{v})\approx E_{in}({\mathbf{w}}_{\mathbf{t}})+\eta {\mathbf{v}}^{\mathbf{T}}▽E_{in}({\mathbf{w}}_{\mathbf{t}}) \end{gathered}$$ 那麼如何最小化 error 呢？
也就是令 ${\mathbf{v}}^{\mathbf{T}}▽E_{in}({\mathbf{w}}_{\mathbf{t}})$ 為負最多
故
$$\mathbf{v}=-\frac{▽E_{in}({\mathbf{w}}_{\mathbf{t}})}{\Vert ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\Vert }$$

如何選定 $\eta$？

$\eta$ 隨 $\Vert ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\Vert$ 遞減

令 $\eta =\eta \Vert ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\Vert$ $$\begin{array}{rl}{\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}& \leftarrow {\mathbf{w}}_{\mathbf{t}}-\eta \frac{▽E_{in}({\mathbf{w}}_{\mathbf{t}})}{\Vert ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\Vert }\\ & \leftarrow {\mathbf{w}}_{\mathbf{t}}-\eta ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\end{array}$$ $\eta$ 為 fixed learning rate

演算法

1. 初始化 ${\mathbf{w}}_{\mathbf{0}}$
2. For $t=0,1,\cdots$
1. 計算
$$\text{Double subscripts: use braces to clarify}$$
2. 修正錯誤
$${\mathbf{w}}_{\mathbf{t}\mathbf{+}\mathbf{1}}\leftarrow {\mathbf{w}}_{\mathbf{t}}-\eta ▽E_{in}({\mathbf{w}}_{\mathbf{t}})$$
3. 直到 $\Vert ▽E_{in}({\mathbf{w}}_{\mathbf{t}})\Vert =0$ 或 大概為 0 或 足夠的次數
3. 得到 $g$

Python 原始碼

import matplotlib.pyplot as plt
import numpy as np
import operator
import math
 
# 網路上找的 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.sub, w, u)
    return list(w)
 
 
# LogisticRegression 演算法實作
def LogisticRegression(dataset):
    # 初始化 w
    w = [0] * 3
 
    t = 0
    n = 0.1
    max_number = 100
    while True:        
        g = gradient(w, dataset)
        print("g {:.5f} => {}: {}".format(vlen(g), t, tuple(w)))
        
        w = update(w, n, g)
        
        t += 1
 
        if vlen(g) < 0.2 or t > max_number:
            break
 
    return w
 
 
# 主程式
def main():
    # 執行
    w = LogisticRegression(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()

參考

如何通俗地解释泰勒公式？
損失函數
tf.nn.sigmoid_cross_entropy_with_logits
cross entropy的直觀理解
Cross entropy