---

第二章 感知机

感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别

2.1感知机模型

假设输入空间（特征空间）是 x ∈ R n , 输出空间是 y = { − 1 , 1 } f ( x ) = s i g n ( w ∗ x + b ) w ∈ R n 称之为权值或权值向量， b ∈ R 叫做偏置。 s i g n ( x ) = { + 1 , x ≥ 0 − 1 , x < 0 假设输入空间（特征空间）是x\in{R^n},输出空间是y=\{-1,1\}\\f(x)=sign(w*x + b)\\ w\in{R^n}称之为权值或权值向量，b\in{R}叫做偏置。\\ sign(x)=

假设输入空间（特征空间）是x∈Rn,输出空间是y={−1,1}f(x)=sign(w∗x+b)w∈Rn称之为权值或权值向量，b∈R叫做偏置。sign(x)={+1,−1,​x≥0x<0​

2.2感知机学习策略

2.2.1数据集的可分性

$$\begin{gathered} 给定一个数据集T=\{(x_1,y_1),(x_2,y_2)\dots (x_N,Y_N)\} \\ w\ast x+b=0 \\ 能将数据集的正实例点和负实例点完全划分到超平面的两侧。 \\ 即对y_i=+1的实例i,有w\ast x_i+b>0,对所有的y_i=-1的实例有w\ast x_i+b<0 \end{gathered}$$

2.2.2感知机的学习策略

$$感知机的损失函数，L(w,b)=-\sum _{x_i\in M}{y}_i(w\ast x_i+b)$$

2.3感知机学习算法

2.3.1 感知机学习算法的原始形式

输入：训练数据集 T = { ( X 1 , Y 1 ) … } 其中 y i ∈ y = { − 1 , + 1 } , i = 1 、 2 … N ; 学习率 η ( 0 < η ≤ 1 ) T=\{(X_1,Y_1)\ldots\}其中y_i\in y=\{-1,+1\},i=1、2\ldots N; 学习率\eta(0<\eta\le1)\qquad T={(X1​,Y1​)…}其中yi​∈y={−1,+1},i=1、2…N;学习率η(0<η≤1)
输出：w,b；感知机模型f(x)=sign(w*x + b)

1. 选取初值$w_0,b_0$
2. 在训练集中选取数据$(x_i,y_i)$
3. 如果$y_i(w\ast x_i+b)\le 0$

$$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow b+\eta y_i \end{gathered}$$4. 转至2，直到训练集中没有误分类点

2.3.2算法的收敛性

输入：训练数据集 T = { ( X 1 , Y 1 ) … } 其中 y i ∈ y = { − 1 , + 1 } , i = 1 、 2 … N ; T=\{(X_1,Y_1)\ldots\}其中y_i\in y=\{-1,+1\},i=1、2\ldots N; T={(X1​,Y1​)…}其中yi​∈y={−1,+1},i=1、2…N;

1. 存在满足条件$||{\hat{w}}_{opt}||=1的超平面{\hat{w}}_{opt}\ast \hat{x}=w_{opt}\ast x+b_{opt}=0$将训练数据集完全分开；且存在$\gamma >0,对所有的i=1,2,\dots N$

$$y_i({\hat{w}}_{opt}\ast {\hat{x}}_i)=y_i(w_{opt}\ast x_i+b_{opt})\ge \gamma$$

2. $令R=\underset{1\le i\le N}{\max }||{\hat{x}}_i||$，则感知机在$f(x)=sign(w\times x+b)$在训练集上误分类次数k满足不等式

$$k\le (\frac{R}{\gamma }{)}^2$$

2.3.3 感知机学习算法的对偶形式

w,b关于$(x_i,y_i)$的增量分别为${\alpha }_i{y}_i{x}_i和{\alpha }_i{y}_i$

$$\begin{gathered} w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i \\ b=\sum _{i=1}^N{\alpha }_i{y}_i \end{gathered}$$

输入：线性可分的数据集 T = { ( X 1 , Y 1 ) … } 其中 y i ∈ y = { − 1 , + 1 } , i = 1 、 2 … N ; 学习率 η ( 0 < η ≤ 1 ) T=\{(X_1,Y_1)\ldots\}其中y_i\in y=\{-1,+1\},i=1、2\ldots N; 学习率\eta(0<\eta\le1) T={(X1​,Y1​)…}其中yi​∈y={−1,+1},i=1、2…N;学习率η(0<η≤1)

输出：$\alpha ,$b；感知机模型$f(x)=sign({\sum }_{j=1}^N{\alpha }_i{y}_i{x}_i\times x+b)$，其中$\alpha =({\alpha }_1,{\alpha }_1,\dots {\alpha }_N{)}^T$

1. $\alpha \leftarrow 0,b\leftarrow 0$
2. 在训练集中选取数据$(x_i,y_i)$
3. 如果$y_i({\sum }_{j=1}^N{\alpha }_i{y}_i{x}_i\times x+b)\le 0$

$$\begin{gathered} {\alpha }_i\leftarrow {\alpha }_i+\eta \\ b\leftarrow b+\eta y_i \end{gathered}$$

4. 转至2 直至没得误分类的数据

Gram矩阵：训练集的内积计算出来以矩阵的形式存储 $G=|x_i\times x_j{|}_{N\times N}$