感知机概述

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

感知机模型

输入空间到输出空间的函数：

感知机学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面即确定感知机模型参数w、b，需要确定一个学习策略，即定义损失函数并将损失函数极小化。
一般想法是通过误差点的个数来定义损失函数，但这样的损失函数不是参数w和b的连续可导函数，不易优化。所以采用输入空间中所有误分类点到超平面的距离再乘w的二范数即||w||得到

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

求得使损失函数极小化问题的w与b的值

在求解极小化问题时，对于凸函数，常常采取梯度下降法，这里采用随机梯度下降法来求解使得损失函数最小的w与b的值。

具体过程：
首先，任取一个超平面w0，b0，再用梯度下降法不断极小化目标函数，极小化过程中不是一次使所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
假设误分类点集合M是固定的，那么损失函数L(w,b)的梯度由

给出。
随机选出一个误分类点(xi,yi),对w，b进行更新：

其中η（0<η<=1)是步长，也称为学习率，这样，通过迭代可以期待损失函数L(w,b)不断减小，直至为零。

感知机的收敛性

当数据集是线性可分并有限时即可收敛。

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

为什么要引进对偶形式

由上式可知，当经过n次修改后，w和b会更新为如下的形式：

（其中αi=ηiη）
当η=1时，αi表示第i个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离超平越近，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。

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

输出α和b
感知机模型

如果

更新αi和b后再重复上述步骤，直至没有错误点为止。