1. 感知機(jī)基礎(chǔ)

1.1 模型

感知機(jī)是最基礎(chǔ)的機(jī)器學(xué)習(xí)模型之一，它的類別為：

分類（√）、回歸、標(biāo)注
概率軟分類（√）、非概率硬分類
監(jiān)督（√）、無監(jiān)督、強(qiáng)化
線性（√）、非線性
判別（√）、生成

模型定義：
輸入空間 $X\subseteq\R ^n$ ，輸出空間 $Y=\left\{ +1,-1\right\}$ ，定義由輸入空間到輸出空間的函數(shù)映射為：
$f(x)=\mathrm{sign}(\omega \cdot x+b)$
該模型稱為感知機(jī)。其中 $\omega,b$ 為感知機(jī)參數(shù)， $\omega \in \R ^n$ 稱為權(quán)值， $b\in\R$ 稱為偏置， $\mathrm{sign}$ 為符號(hào)函數(shù)，即：
$\mathrm{sign}(x)= \left\{ \begin{aligned} &+1, \quad x\geq 0 \\ &-1, \quad x<0 \end{aligned} \right.$

該模型本質(zhì)上是在輸入空間定義了一個(gè)分離超平面： $\omega\cdot x+b=0$ ， $\omega$ 為該超平面的法向量， $b$ 為該超平面的截距。該超平面將輸入空間劃分為兩部分，位于兩側(cè)的點(diǎn)（輸入數(shù)據(jù)）分別屬于正負(fù)兩類。
給定一個(gè)線性可分的訓(xùn)練樣本集，通過尋找合適的 $\omega$ 和 $b$ 使得訓(xùn)練樣本集的數(shù)據(jù)被正確劃分到超平面的兩側(cè)，該過程即感知機(jī)模型的訓(xùn)練過程。
這里有一個(gè)前提“訓(xùn)練樣本集線性可分”，即對(duì)于訓(xùn)練樣本集： $T=\lbrace(x_1,y_1),(x_2,y_2,\cdots,(x_N,y_N)\rbrace$ ，其中， $x_i\in X=\R ^n,y_i\in Y=\lbrace+1,-1\rbrace,i=1,2,\cdots,N$ ，若存在某超平面 $S:\omega\cdot x+b=0$ ，使得 $\forall(x_i,y_i)\in T:y_i(\omega\cdot x_i+b)>0$ ，則稱 $T$ 為線性可分?jǐn)?shù)據(jù)集。

1.2 函數(shù)間隔與訓(xùn)練策略

為了尋找能正確劃分訓(xùn)練樣本集的超平面，需要定義損失函數(shù)，并將損失函數(shù)極小化。如何度量損失呢？如下圖所示，有A、B、C三點(diǎn)，表示三個(gè)樣本，都在分離超平面的正側(cè)，距離分離超平面的距離依次減小。距離越遠(yuǎn)，預(yù)測(cè)為正類的確信度越大，反之則不那么確信。

樣本距離分類超平面的距離與分類確信度.png

在超平面 $\omega\cdot x+b=0$ 確定的情況下， $|\omega\cdot x+b|$ 能夠相對(duì)地表示點(diǎn) $x$ 距離超平面的遠(yuǎn)近，而 $\omega\cdot x+b$ 的符號(hào)與類標(biāo)記 $y$ 的符號(hào)是否一致能夠表示分類是否正確。所以可以用 $y(\omega\cdot x+b)$ 來表示分類的正確性與確信度，這就是函數(shù)間隔（functional margin）的概念。
設(shè) $M$ 為 $T$ 上被超平面 $S$ 誤分類的所有點(diǎn)的集合，則 $\forall (x_i,y_i) \in M:y_i(\omega\cdot x_i+b)<0$
按照機(jī)器學(xué)習(xí)約定俗成的慣例，損失函數(shù)為正，對(duì)損失函數(shù)求極小值。因此，我們將感知機(jī)的損失函數(shù)定義為 $T$ 上所有被誤分類的點(diǎn)到超平面 $S$ 的函數(shù)間隔的絕對(duì)值，即： $-\sum_{x_i\in M}{y_i(\omega\cdot x_i+b)}$
感知機(jī)的學(xué)習(xí)策略是在假設(shè)空間中選取使上式最小的分離超平面系數(shù) $\omega$ 和 $b$ 。

1.3 學(xué)習(xí)算法

感知機(jī)的學(xué)習(xí)問題可轉(zhuǎn)化為求解使損失函數(shù)最小的最優(yōu)化問題，即求參數(shù) $\omega,b$ ，使其為以下極小化問題的解。 $\min_{\omega,b}L(\omega,b)=-\sum_{x_i\in M}{y_i(\omega\cdot x_i+b)}$
其中，M為誤分類點(diǎn)的集合。求解該問題可使用梯度下降算法。
損失函數(shù) $L(\omega,b)$ 的梯度為：
$\begin{aligned} \Delta _{\omega} L(\omega,b) &=-\sum_{x_i\in M}{y_ix_i} \\ \Delta _ L(\omega,b) &=-\sum_{x_i\in M}{y_i} \end{aligned}$
如果樣本集非常大，梯度下降算法每輪迭代都要計(jì)算全局梯度，這需要耗費(fèi)非常大的計(jì)算資源，實(shí)際應(yīng)用中通常使用隨機(jī)梯度下降算法代替，即每次隨機(jī)選取一個(gè)誤分類點(diǎn) $(x_i,y_i)$ ，對(duì) $\omega,b$ 沿梯度負(fù)方向更新。
$\begin{aligned} \omega \leftarrow & \omega +\eta y_ix_i \\ b\leftarrow & b+\eta y_i \end{aligned}$
其中 $\eta(0<\eta\leq 1)$ 為步長(zhǎng)，又叫做學(xué)習(xí)率。隨機(jī)梯度的期望為全局梯度，因此其收斂性與梯度下降算法一致。通過不斷迭代以上步驟，可以期待損失函數(shù) $L(\omega,b)$ 不斷減小，直到為0.
該算法的直觀理解為：當(dāng)一個(gè)實(shí)例點(diǎn)被誤分類，調(diào)整 $\omega,b$ 的值，使分離超平面向該誤分類點(diǎn)移動(dòng)，減小該誤分類點(diǎn)與超平面的距離，直至超平面越過該點(diǎn)，使其被正確分類。
該算法在訓(xùn)練開始時(shí)需要選取一個(gè)初始分類超平面 $(\omega_0,b_0)$ ，經(jīng)過 $k$ 輪迭代后：
$\begin{aligned} \omega _k &= \omega _0+\eta \sum_{i=1}^{k-1}{y_ix_i} \\ b_k &=b_0+\eta \sum_{i=1}^{k-1}{y_i} \end{aligned}$
其中， $(x_i,y_i)$ 為第 $i$ 輪迭代時(shí)隨機(jī)選取的誤分類點(diǎn)。當(dāng) $(\omega_0,b_0)=0$ 時(shí)，第 $k$ 輪迭代時(shí)的超平面方程為：
$\begin{aligned} &\quad\omega _k x+b_k=0 \\ \Rightarrow &\quad \eta\sum_{i=1}^{k-1}{y_ix_i}x+\eta \sum_{i=1}^{k-1}{y_i}=0 \\ \Rightarrow &\quad \sum_{i=1}^{k-1}{y_ix_i}x+\sum_{i=1}^{k-1}{y_i}=0 \end{aligned} \tag{1}$
可以看出，學(xué)習(xí)速率 $\eta$ 可以被約去，說明當(dāng) $(\omega_0,b_0)=0$ 時(shí)，算法收斂速度與 $\eta$ 無關(guān)。下面證明感知機(jī)訓(xùn)練算法收斂性，證明過程可進(jìn)一步驗(yàn)證該結(jié)論。

2. 算法收斂性證明

證明感知機(jī)訓(xùn)練算法是收斂的，即證明訓(xùn)練過程可在有限輪迭代內(nèi)完成，即迭代次數(shù) $k$ 存在一個(gè)上界。
為了便于敘述，將偏置 $b$ 并入權(quán)重向量 $\omega$ ，記作 $\hat{\omega}=(\omega^T,b)$ ，同時(shí)對(duì)輸入向量 $x$ 進(jìn)行擴(kuò)充，記作 $\hat{x}=(x^T,1)$ ，顯然 $\hat{\omega}\cdot \hat{x}=\omega\cdot x+b$ 。

Novikoff定理：
設(shè)訓(xùn)練數(shù)據(jù)集 $T=\lbrace(x_1,y_1),(x_2,y_2,\cdots,(x_N,y_N)\rbrace$ 是線性可分的，其中， $x_i\in X=\R ^n,y_i\in Y=\lbrace+1,-1\rbrace,i=1,2,\cdots,N$ ，令 $R=\max_{1\leq i\leq N}{||\hat{x}_i||}$ ，則感知機(jī)學(xué)習(xí)算法在訓(xùn)練數(shù)據(jù)集上的誤分類次數(shù) $k$ 滿足不等式：
$k\leq\left(\frac{R}{\gamma}\right)^2\Vert\hat{\omega}_{opt}\Vert^2$
其中 $\hat{\omega}_{opt}$ 為該訓(xùn)練數(shù)據(jù)集的任一分離超平面的擴(kuò)展系數(shù)向量。

證明：
訓(xùn)練數(shù)據(jù)集線性可分，則存在能將數(shù)據(jù)集完全正確分開的分離超平面，對(duì)任一滿足要求的分離超平面 $\hat{\omega}_{opt}\cdot\hat{x}=0$ ，存在 $\gamma>0$ ，對(duì)所有 $i=1,2,\cdots,N$ ：
$y_i(\hat{\omega}_{opt}\cdot \hat{x}_i)\geq\gamma \tag{2}$
初始時(shí)， $\hat{\omega}_0=0$ ，隨機(jī)選取某樣本，若被誤分類，則更新權(quán)重。令 $\hat{\omega}_{k-1}$ 是第 $k$ 次迭代時(shí)的擴(kuò)充權(quán)重向量，此次迭代隨機(jī)選擇的第 $k$ 個(gè)誤分類樣本滿足條件：
$y_i(\hat{\omega}_{k-1}\cdot\hat{x}_i)\leq 0 \tag{3}$
迭代時(shí)進(jìn)行如下更新：
$\hat{\omega}_k=\hat{\omega}_{k-1}+\eta y_i\hat{x}_i \tag{4}$
聯(lián)合(2)(4)式，有：
$\begin{aligned} \hat{\omega}_k\cdot\hat{\omega}_{opt} &=\hat{\omega}_{k-1}\cdot\hat{\omega}_{opt}+\eta y_i\hat{x}_i\cdot\hat{\omega}_{opt} \\ &\geq \hat{\omega}_{k-1}\cdot\hat{\omega}_{opt}+\eta \gamma \\ &\geq \hat{\omega}_{k-2}\cdot\hat{\omega}_{opt}+2\eta \gamma \\ &\cdots \\ &\geq k\eta \gamma \end{aligned} \tag{5}$
聯(lián)合(3)(4)式，有：
$\begin{aligned} |Vert\hat{\omega}_k\Vert^2&=\Vert\hat{\omega}_{k-1}+\eta y_i\hat{x}_i \Vert^2 \\ &=\Vert\hat{\omega}_{k-1}\Vert^2+2\eta y_i\hat{\omega}_{k-1}\cdot\hat{x}_i+\eta^2\hat{x}_i^2 \\ &\leq\Vert\hat{\omega}_{k-1}\Vert^2+\eta^2\hat{x}_i^2 \\ &\leq\Vert\hat{\omega}_{k-1}\Vert^2+\eta^2R^2 \\ &\leq\Vert\hat{\omega}_{k-2}\Vert^2+2\eta^2R^2 \\ &\cdots \\ &\leq k\eta^2R^2 \end{aligned} \tag{6}$
聯(lián)合(5)(6)式，有：
$\begin{aligned} &k\eta \gamma \leq\hat{\omega}_k\cdot\hat{\omega}_{opt}\leq\Vert\hat{\omega}_k\Vert\Vert\hat{\omega}_{opt}\Vert\leq\sqrt{k}\eta R\Vert\hat{\omega}_{opt}\Vert \\ \Rightarrow &k^2\gamma ^2\leq kR^2 \Vert\hat{\omega}_{opt}\Vert^2 \\ \Rightarrow &k\leq\left(\frac{R}{\gamma}\right)^2\Vert\hat{\omega}_{opt}\Vert^2 \end{aligned} \tag{7}$
定理得證。
從(7)式可知，迭代次數(shù) $k$ 存在上界，這說明當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時(shí)，感知機(jī)學(xué)習(xí)算法是收斂的。
進(jìn)一步地，通過調(diào)整 $\eta$ 可以改變 $\Vert\hat{\omega}_{opt}\Vert^2$ 的取值。算法經(jīng)過 $k$ 次迭代結(jié)束后得到分離超平面 $\hat{\omega}_{opt}\hat{x}=0$ ，由(1)式可知， $\hat{\omega}_{opt}=\eta\sum_{i=1}^{k}{y_ix_i}$ ，令 $\eta=\frac{1}{\Vert\sum_{i=1}^{k}{y_ix_i}\Vert}$ ，則可使得 $\Vert\hat{\omega}_{opt}\Vert=1$ ，從而得到感知機(jī)迭代次數(shù)收斂上界的精簡(jiǎn)形式：
$k\leq\left(\frac{R}{\gamma}\right)^2$

3. 附錄

from sklearn.datasets import make_blobs
from matplotlib import pyplot as plt
import numpy as np
import random

X,Y=make_blobs(n_samples=100,
               n_features=2,
               centers=2,
               cluster_std=2.5,
               random_state=1)
Y[Y==0]=-1

fig=plt.figure(figsize=(7,5))
ax=fig.add_subplot(111)
plt.show()
ax.scatter(X[:,0],X[:,1],c=Y, s=5, cmap='rainbow')

w=np.zeros(2)
b=0
eta=0.1
watcher=True
i=0
while(watcher):
    watcher=False
    for k in range(100):
        xk=X[k]
        yk=Y[k]
        if yk*(np.dot(w,xk)+b)>0:
            continue
        w=w+eta*yk*xk
        b=b+eta*yk
        i+=1
        print('第%d個(gè)誤分類樣本，w=%s,b=%s'%(i,w,b))
        watcher=True
        x1=np.arange(-7.5,1,0.01)
        x2=-(w[0]*x1+b)/w[1]
        ax.plot(x1,x2)
        plt.pause(0.01)

感知機(jī)學(xué)習(xí)算法.png

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

感知機(jī)的收斂性

感知機(jī)的收斂性

1. 感知機(jī)基礎(chǔ)

1.1 模型

1.2 函數(shù)間隔與訓(xùn)練策略

1.3 學(xué)習(xí)算法

2. 算法收斂性證明

3. 附錄

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

感知機(jī)的收斂性

1. 感知機(jī)基礎(chǔ)

1.1 模型

1.2 函數(shù)間隔與訓(xùn)練策略

1.3 學(xué)習(xí)算法

2. 算法收斂性證明

3. 附錄

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av