一、感知机模型

感知机是二类分类的线性分类模型，输入为实例的特征向量，输出为实例的类别，旨在求出将训练数据进行线性划分的分离超平面。

假设输入空间$X\subseteq R^n$，输出空间$Y={+1,-1}$。输入$x\in X$表示实例的特征向量，对应于输入空间的点。输出$y\in Y$表示实例的类别，则输入空间到输出空间的函数：

$$f(x)=sign(w\cdot x+b)$$

称为感知机。其中$w$称为权值向量，$b$称为偏置，sign时符号函数sign(x)= {+1(if x>=0), -1(if x<0)}。

二、感知机学习策略

2.1 数据集的线性可分性

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

2.2 学习策略

输入空间中任意一点$x_0$到超平面S的距离为：$\frac{1}{||w||}|w\cdot x_0+b|$

因此误分类点到超平面S的距离为：$-\frac{1}{||w||}y_i(w\cdot x_0+b)$

所有误分类点的总距离，即损失函数为：$L(w,b)=-\sum_{i=0}^M y_i(w\cdot x_0+b)$

显然损失函数是非负的，感知机的学习策略就是在假设空间中找到使损失函数最小的模型参数$w,b$

2.3 学习算法

感知机的学习算法采用随机梯度下降法。每次随机选取一个误分类点使其梯度下降。

输入：线性可分数据集T，学习率$\eta$

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

（1）选取初值$w_0,b_0$
（2）在训练集中选取数据$(x_i,y_i)$
（3）如果$y_i(w\cdot x_i+b)\le0$，更新参数$w=w+\eta y_i x_i$，$b=b+\eta y_i$，其中$\eta$为学习率，后项为两个参数的梯度
（4）重复上述过程，直到训练集中没有误分类点

当训练数据集线性可分时，感知机学习算法是收敛的，即经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。