感知机是二分类的线性分类器，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机将特征空间中的实例划分为正负两类，属于判别模型。

感知机模型

模型

输入空间：$\mathcal{X}\subseteq {\mathbf{R}}^{\mathbf{n}}$

输出空间：$\mathcal{Y}=\{+1,-1\}$

决策函数：$f(x)=sign(w\cdot x+b)$

其中sign是符号函数，即
$$sign(x)=\{\begin{array}{l}1,x\ge 0\\ -1,x<0\end{array}$$
感知机将特征空间中的实例划分为正负两类，属于判别模型。

模型的几何解释

线性方程：
$$w\cdot x+b=0$$
对应特征空间${\mathbf{R}}^{\mathbf{n}}$ 中的一个超平面 $\mathbf{S}$ ，其中$w$ 是超平面的法向量，$b$ 是超平面的截距。

超平面将样本点分成两类。感知机的目标就是确定这个超平面。即确定模型的参数$w,b$ ，这就需要一个损失函数，并将损失函数极小化。

损失函数

选择误分类点到超平面$\mathbf{S}$ 的总距离作为损失函数。

首先，找出一个误分类点到超平面的距离

因为输入空间$\bf R^n $ 中任一点$x_0$到超平面$S$ 的距离：
$$\frac{1}{||w||}|w\cdot x_0+b|$$
对于误分类点来说： $w\cdot x_0+b$ 与 $y_i$ 总是符号相反。即：
$$-y_i(w\cdot x_0+b)>0$$
所以一个误分类点到超平面之间的距离是：
$$-\frac{1}{||w||}{y}_i(w\cdot x_0+b)$$
其次，假设所有的误分类点的集合是$M$，所以所有误分类点到平面的总距离为：
$$-\frac{1}{||w||}\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$
令$||w||=1$，得到损失函数：
$$L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$
注意：损失函数是非负的，若不存在误分类点，则损失函数为0。

有了损失函数，接下来就是极小化损失函数，确定模型参数。

学习算法

学习算法的原始形式

给定一个训练集:
$$\begin{gathered} T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\} \\ {x}_i\in \mathcal{X}={\mathbf{R}}^{\mathbf{n}},{\mathbf{y}}_{\mathbf{i}}\in \mathcal{Y}=\{-1,+1\},i=1,2,\dots ,N;0<\eta ⩽1 \end{gathered}$$

求$w,b$，使得损失函数极小化：
$$\underset{w,b}{\min }L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$
采用梯度下降算法。假设误分类点M是固定的。所以有：
$$\begin{gathered} \frac{\partial L(w,b)}{\partial w}=-\sum _{x_i\in M}{x}_i{y}_i \\ \frac{\partial L(w,b)}{\partial b}=-\sum _{x_i\in M}{y}_i \end{gathered}$$
对于每一个分类点，对$w,b$ 进行更新：
$$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow b+\eta y_i \end{gathered}$$
具体算法流程如下：

输入：
$$\begin{gathered} T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\} \\ {x}_i\in \mathcal{X}={\mathbf{R}}^{\mathbf{n}},{\mathbf{y}}_{\mathbf{i}}\in \mathcal{Y}=\{-1,+1\},i=1,2,\dots ,N;0<\eta ⩽1 \end{gathered}$$

输出：$w,b;f(x)=sign(w\cdot x+b)$

1. 选取初值$w_0,b_0$
2. 训练集中选取数据$(x_i,y_i)$
3. 如果$y_i(w\cdot x_i+b)⩽0$

$$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow b+\eta y_i \end{gathered}$$

4. 转至(2)，直至训练集中没有误分类点

学习算法的对偶形式

对偶形式的基本思想是：将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$w$和$b$。

回顾$w,b$ 的更新过程：
$$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow b+\eta y_i \end{gathered}$$
对于某一个误分类点$(x_i,y_i)$ 而言，他可能参与了$n_i$次的$w,b$ 的更新过程，直至超平面能使他成为正确分类点，他才不参与$w,b$ 的更新。所以此误分类点对$w,b$ 所贡献的增量分别为 $n_i\eta y_i x_i $和$n_i\eta y_i$，这是一个误分类点的情况。令$\alpha_i = n_i\eta$，对于多个分类点，我们对其累加即可：
$$\begin{gathered} w=\sum _{i=1}^N{n}_i\eta y_i{x}_i=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i \\ b=\sum _{i=1}^N{n}_i\eta y_i=\sum _{i=1}^N{\alpha }_i{y}_i \end{gathered}$$
这样我们就实现了将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式

输入：
$$\begin{gathered} T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\} \\ {x}_i\in \mathcal{X}={\mathbf{R}}^{\mathbf{n}},{\mathbf{y}}_{\mathbf{i}}\in \mathcal{Y}=\{-1,+1\},\mathbf{i}=1,2,\dots ,\mathbf{N};0<\eta ⩽1 \end{gathered}$$

输出：
$$\begin{gathered} \alpha ,b;\alpha =({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_N{)}^T \\ f(x)=sign\left(\sum _{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x+b\right) \end{gathered}$$

1. $\alpha \leftarrow 0,b\leftarrow 0$
2. 训练集中选取数据$(x_i,y_i)$
3. 如果$y_i\left({\sum }_{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x_i+b\right)⩽0$

$$\begin{gathered} {\alpha }_i\leftarrow {\alpha }_i+\eta \\ b\leftarrow b+\eta y_i \end{gathered}$$

4. 转至(2)，直至训练集中没有误分类点

Gram matrix

对偶形式中，训练实例仅以内积的形式出现。

为了方便可预先将训练集中的实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵
$$G=[x_i\cdot x_j{]}_{N\times N}$$

感知机不能用于异或

现感知机是一种线性分类模型。而异或可以表示为如下形式：

由图可知，这个问题是线性不可分的，所以不能用感知机。