统计学习方法（二）感知机

感知机，是二分类的线性分类模型。输入为实例的特征向量，输出为±1，旨在求出将训练数据进行线性划分的分离超平面，是神经网络与SVM的基础。

2.1 感知机模型

定义

$$\begin{gathered} f(x)=sign(w·x+b) \\ \mathcal{X}\subset R^n,\mathcal{Y}=\{-1,+1\} \end{gathered}$$

其中w和b为感知机模型参数，w称为权值（向量），b称为偏置（bias）。 $$sign(x)=\{\begin{array}{l}+1,x\ge 0\\ -1,x<0\end{array}$$

几何解释

线性方程 $$w·x+b=0$$ 对应于特征空间中的一个超平面S，w表示超平面的法向量，b为超平面的截距。

2.2 感知机学习策略

数据集的线性可分性

给定一个数据集，如果存在超平面S，能够将数据集的正实例点和负实例点完全正确划分，则称数据及为线性可分数据集。

损失函数

损失函数的一个自然选择是误分类点的总数，但这样不是参数的连续可导函数，不易优化。

感知机选择的损失函数是误分类点到超平面S的总距离，输入空间任一点到超平面S的距离为 $$\frac{1}{\Vert w\Vert }|w·x_0+b|,\mathrm{其}\mathrm{中}\Vert w\Vert \mathrm{为}w\mathrm{的}{L}_2\mathrm{范}\mathrm{数}$$ 对于误分类的数据来说，始终有 $$-y_i(w·x_i+b)>0$$ 所以距离为 $$-\frac{1}{\Vert w\Vert }{y}_i(w·x_i+b)$$ 假设误分类点集合为M，求和即得 $$-\frac{1}{\Vert w\Vert }\sum _{x_i\in M}{y}_i(w·x_i+b)$$ 不考虑系数，损失函数即为 $$L(w,b)=-\sum _{x_i\in M}{y}_i(w·x_i+b)$$ 误分类点越少，损失函数值越小，如果没有误分类点，损失函数值为0。

2.3 感知机学习算法

形式化

给定训练集 $$\begin{gathered} T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} \\ {x}_i\in \mathcal{X}=R^n,y_i\in \mathcal{Y}=\{-1,+1\} \end{gathered}$$ 求参数w和b，使得损失函数极小化 $$\underset{w,b}{min}L(w,b)=-\sum _{x_i\in M}{y}_i(w·x_i+b)$$ 学习算法是误分类驱动的，具体采用随机梯度下降法，首先任意选取一个超平面，之后用梯度下降法不断极小化目标函数。

损失函数的梯度为 $$\begin{gathered} {\mathrm{\nabla }}_{w}L(w,b)=-\sum _{x_i\in M}{y}_i{x}_i \\ {\mathrm{\nabla }}_{b}L(w,b)=-\sum _{x_i\in M}{y}_i \end{gathered}$$ 随机选取一个误分类点，对参数进行更新 $$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow b+\eta y_i \\ \eta \in (0,1] \end{gathered}$$

原始形式

1. 选取参数初值$w_0,b_0$$

2. 在训练集中选取数据$(x_i,y_i)$$

3. 如果$y_i(w{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直至没有误分类点

收敛性

(Novikoff) 存在满足条件的超平面，且感知机算法的误分类次数k满足不等式 $$k\le (\frac{R}{\gamma }{)}^2$$

对偶形式

基本想法是，将w和b表示为实例x与标记y的线性组合，通过求解系数求得w和b。

最后学习到的w和b可表示为 $$\begin{gathered} w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i \\ b=\sum _{i=1}^N{\alpha }_i{y}_i \end{gathered}$$ 训练过程

1. 选取α和b为0,

2. 在训练集中选取数据

3. 若$y_i(\sum _{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x_i+b)\le 0$，则更新参数

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

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

Gram矩阵？

Scikit-learn

from sklearn.linear_model import Perceptron

clf = Perceptron(fit_intercept=True,
                 max_iter=1000,
                 shuffle=True)
clf.fit(X, y)

# Weights assigned to the features.
print(clf.coef_)

# Constants in decision function.
print(clf.intercept_)

y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)
plt.plot(x_ponits, y_)