【统计学习方法】感知机

感知机（perceptron）是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

感知机模型

假设输入空间（特征空间）X = R^n，输出空间Y = {-1，+1}。输入x∈X表示实例的特征向量，对应于输入空间（特征空间）的点；y∈Y表示实例的类别。

则输入空间到输出空间的如下函数：

 称为感知机。 其中，w,b为感知机模型参数，w属于R^n叫权值（weight）或权值向量(weight vector)，b∈R称为偏置（bias）。

sign是符号函数：

 感知机的假设空间是定义在特征空间的所有线性分类模型：

感知机学习策略

 给定一个线性可分数据集：

 损失函数设为误分类点个数：

 则损失函数不可导，不方便优化，故更改为：

其中，误分类点的集合M：

感知机学习算法

感知机学习算法等价于求以下损失函数极小化问题的解：                                          

采用随机梯度下降（stochastic gradient descent）: 任取一个超平面w0, b0, 然后利用随机梯度下降不断的极小化损失函数——一次随机选取一个误分类点使其梯度下降。

损失函数梯度：

 随机选取误分类点，对w,b进行更新：

 式中表示步长，又称学习率（learning rate）

 算法1（原始形式）：

 输入：训练数据集，其中  学习率

 输出：w,b: 感知机模型

 （1）选取初值w0, b0;

 （2）在训练集选取数据

 （3）如果,

 （4）转至（2），直到训练集中没有误分类点

算法2（对偶形式）：

 输入：训练数据集，其中  学习率

 输出：a,b: 感知机模型

 （1）

 （2）训练集中选取数据

 （3）如果

 （4）转至（2）直至没有误分数据

对偶形式中训练实例仅以内积形式出现， 为方便，可以预先将训练集中实例间的内积计算出来并以矩阵形式储存——Gram矩阵:

可以证明，感知机学习算法收敛。