感知机

感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。
假设输入空间（特征空间）是x⊆R^n，输出空间是y={+1,-1}。输入x∈X表示实例的特征向量，对应于输入空间（特征空间）的点，输出y∈Y表示实例的类别。由输入空间到输出空间的如下函数f(x)=sign(w*x+b)称为感知机。
感知机模型图如下：

感知机学习策略

数据集的线性可分性：给定一数据集T={(x1,y1),(x2,y2),…(xn,yn)}，其中xi∈X=R^n，yi∈Y={+1，-1}，i=1,2,3……n，如果存在某个超平面S：wx+b=0
能够将数据集的正实例点和负实例点完全正确的划分到超平面的两侧，即对所有yi=+1的实例i，有wxi+b>0；对所有yi=-1的实例i，有w*xi+b<0，则称数据集T为线性可分数据集，否则，称数据集T线性不可分。
为了将正实例点和负实例点完全正确分开需要找到一个分离超平面，要找到这个分离超平面我们需要确定感知机模型参数w，b，为了确定感知机模型参数我们就要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。
感知机的损失函数定义：

感知机学习算法

感知机学习问题转化为求解损失函数的最优化问题，最优化的方法是随机梯度下降法。
感知机学习算法是误分类驱动的，具体操作过程如下：首先，任意选取一个超平面w0，b0，然后用梯度下降法不断地极小化目标函数：

极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
感知机学习算法的原始形式
输入：训练数据集T={(x1,y1),(x2,y2),…(xn,yn)}，其中xi∈X=R^n，yi∈Y={+1，-1}，i=1,2,3……n；学习率η(0<η≤1）
输出：w，b；感知机模型f(x)=sign(wx+b)
(1) 选取初值w0，b0
(2) 在训练集中选取数据（xi，yi）
(3) 如果yi(wxi+b)≤0

(4) 转至(2)，直到训练集中没有误分类点。
例 如图所示的训练数据集，其正实例点是x1=(3,3)^T ， x2=(4,3) ^T，负实例点是x3=(1,1) ^T，试用感知机学习算法的原始形式求感知机模型f(x)=sign(wx+b)。这里，w=(w ^(1),w ^（2)) ^T ，x=(x ^(1),x ^（2)) ^T。

解： 构建最优化问题：

这里的学习率η=1
(1)选取初始值w0=0,b0=0
(2)对x1=(3,3) ^T,y1(w0x1+b0)=0，所以x1未能被正确分类，更新w,b
w1=w0+ηy1x1=(3,3)^T，b1=b0+y1=1
得到线性模型：

(3)对x1,x2,显然，yi(w1xi+b1)>0，被正确分类，不修改w,b；对x3=(1,1)^T，y3(w1x3+b1)<0，被误分类，更新w,b。

得到线性模型：

如此继续下去，直到

对所有数据点yi(w7*xi+b7)>0，没有误分类点，损失函数达到极小。
分离超平面为：

感知机模型为：

算法的收敛性
设训练数据集T={(x1,y1),(x2,y2),…(xn,yn)}是线性可分的，其中xi∈X=R^n，yi∈Y={+1，-1}，i=1,2,3……n则
(1)存在满足条件||w_opt||=1的超平面

将训练数据集完全正确分开；且存在γ＞0，对所有i=1,2,……n

(2)令R=max||xi||,1≤i≤n，则感知机算法在训练数据集上的误分类次数k满足不等式：

感知机学习算法的对偶形式
对偶形式的基本思想是，将w和b表示为实例xi和标记yi的线性组合的形式，通过求解其系数而求得w和b。
输入：训练数据集T={(x1,y1),(x2,y2),…(xn,yn)}，其中xi∈X=R^n，yi∈Y={+1，-1}，i=1,2,3……n；学习率η(0<η≤1）
输出：α,b；感知机模型：

其中α=(α1,α2,……αN)^T
(1)α←0，b←0
(2)在训练集中选取数据(xi,yi)
(3)

(4)转至（2）知道没有误分类数据。
对偶形式中训练实例仅以内积的形式出现，为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵