感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此导入了基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知基模型对新的输入实例进行分类。感知机是神经网络与支持向量机的基础。

感知机模型

$$f(x) = sign(w \cdot x + b)$$
其中 sign 为符号函数，输出值为$+1,-1$。

感知机的几何解释为：使用线性函数$w \cdot x + b=0$作为超平面将特征空间的点分为正负两类。其中$w$代表权值向量，即超平面的法向量，b表示偏置，几何意义为超平面的截距。

感知机为线性模型，要求正负样本必须线性可分。

学习策略

损失函数

误分类点到超平面S的总距离
$$L(w, b)=-\sum_{x_i \in M} y_i(w \cdot x_i + b)$$
其中，$M$为误分类点集合，点到直线距离$\dfrac{1}{\left| w\right| _{2}
} (w \cdot x_i + b)$，损失函数没有考虑$\dfrac{1}{\left| w\right| _{2}}$。

学习算法

上面已经将感知机学习问题转化为优化问题，可使用梯度下降法求解。

随机梯度下降

随机梯度下降首先随机初始化一个超平面，然后不断极小化损失函数。极小化损失函数时，不是一次将所有误分类点的损失极小化，而是随机选取一个误分类点使其梯度下降，然后更新$w,b$，通过不断迭代可以使损失函数$L(w,b)$减小并趋近于0。

损失函数的梯度计算：
$$\frac{\partial L(w,b)}{\partial w}=- \sum_{x_i \in M}y_i x_i$$

$$\frac{\partial L(w,b)}{\partial b}=- \sum_{x_i \in M}y_i$$
则随机选取一个误分类点$(x_i,y_i)$，参数$w,b$可更新为：
$$w \leftarrow w + \eta y_i x_i$$

$$b \leftarrow b + \eta y_i$$

收敛性证明

对偶形式

对误分类点的参数更新方式为
$$w \leftarrow w + \eta y_i x_i$$

$$b \leftarrow b + \eta y_i$$
假设迭代了$n$次，且初始$w,b=0$，则
$$w= \sum_{i=1}^{N} \alpha_i y_i x_i$$

$$b= \sum_{i=1}^{N} \alpha_i y_i$$

输出为
$$f(x) = sign(\sum_{j=1}^{N} \alpha_j y_j x_j \cdot x + b)$$