前言
写感知机模型时有种和老朋友相遇的感觉，因为本科的毕业论文做的是 “基于深度学习的手写数字图像识别”。当时在里面用的就是神经网络模型实现的图像识别，而感知机模型就是复杂的神经网络的基本组成单元。用这篇文章致敬我的本科大四整个学年！
正文
感知机模型
感知机 (perceptron) 是模拟真实生物神经元的构造和功能，进而抽象提取出来的一种模型,下图为感知机的基本结构。
简单地解释一下上图。假设我们拥有训练样本集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)} $，其中$x_i\in \chi=R^n, y_i\in \gamma ={+1,-1}$。$x_{i}^{j}$代表的是第 $i$ 个样本的第 $j$ 个特征作为信号输入至神经元。那么该神经元就可以提供一种非线性的假设模型$y_{w,b}(x)$，该模型含有两个参数，分别是权重$w$和偏置$b$。通过训练模型得到这两个模型参数后，就可以将新的样本输入至模型进行预测。
\[f(x)=sign(w\cdot x+b) \tag{1}\]感知机の定义： 假设我们的输入空间是 $\chi\subseteq R^n$ (即单个样本$x$的维度为$n$)，对应的输出空间 $\gamma={+1, -1}$。输出空间表示该数据集中的样本只有正负两类。由输入空间到输出空间经过如下变换：
式 $(1)$ 为感知机定义式。 其中 $w$ 和 $b$ 就是上文提到的权重和偏置参数，也是我们所要求解的参数。$sign$ 是符号函数，即：
\[sign(x) = \begin{cases} +1 & x \geq 0 \\ -1 & x < 0 \end{cases} \tag{2}\]感知机在输入空间中将实例划分为正负两类（取值为+或－），是一种线性分类模型。并且由于感知机的策略是直接学习最终的判别函数 $f(y\mid x)$，故其属于判别模型。
针对感知机中的权重参数 $w$ 和偏置参数 $b$ 有如下几何解释：线性方程
\[w\cdot x+b=0 \tag{3}\]对应于输入空间 $R^n$ 中一个的一个划分超平面。其中权重参数 $w$ 有一个另外一个重要的身份 — 划分超平面的法向量，偏置参数 $b$ 是超平面的截距。这个超平面将所有样本划分成正负两类。该超平面也被对应的称之为决策边界 (Decision boundary)。如下图所示：
（图片来自《统计机器学习》 -李航）
在这里我们要明确：
- 数据集是线性可分
- 数据集中只有正负两类
因此对于正确分类的样本来说下式总是成立：
\[y_i(w\cdot x_i + b) > 0 \tag{4}\]其实对于上式 $(4)$ 很好理解：在正确分类的情况下，在 $Negtive (-)$ 的一侧 $w \cdot x_i +b$ 与其类别 $y_i$ 皆为负，故其乘积大于 $0$，正侧同理。
对于被错误分类的样本：
\[y_i(w\cdot x_i + b) < 0 \tag{5}\]同时，误分类点 $x_i$ 到分离超平面 $S$ 的距离为：
\[-\frac{1}{||w||}y_i(w\cdot x_i +b) \tag{6}\]我们标记所有误分类点的集合为 $M$，那么所有被错误分类的样本点到分离超平面的距离之和为：
\[-\frac{1}{||w||} \sum_{x_i\in M}y_i(w\cdot x_i + b) \tag{7}\]此时，我们根据最小化损失函数的定义，就自然地将 $(7)$ 式用作为损失函数，并且由于 $\frac{1}{\mid \mid w\mid \mid}$ 是常数项，对最小化损失函数没有影响，故可以忽略。 因此，感知机的损失函数为：
\[L(w,b) = -\sum_{x_i\in M}y_i(w\cdot x_i + b) \tag{8}\]接下来就要明确我们的目标：在数据集是线性可分的情况下，找到一个能将正负两类实例完美分开的超平面。
- 通过训练找到合适权重参数$w$、偏置参数$b$和激活函数，构建出感知机模型 $f(x)=sign(w\cdot x+b)$。
- 遇到新的样本后将新样本 $x^{new}$ 与权重参数$w$做点乘运算，然后加上偏置参数$b$之后放入激活函数计算。（此处的激活函数为符号函数 $sign$）
- 最后判断激活函数的输出值的正负就可以知道该样本的类别了。
根据上述思路，写出如下 感知机的原始学习算法：
输入：训练集 $T={(x_1, y_1), (x_2, y_2), … , (x_n, y_n)}$， 其中 $x_i\in R^n$，$y_i\in \gamma={+1, -1}$, 学习速率 $\eta \in (0,1]$。
输出：权重参数 $w$, 偏置参数 $b$。即感知机模型：$f(x)=sign(w\cdot x+b)$。
- 初始化权重参数 $w$ 和偏置参数 $b$ 即任意选择一个超平面。 通常选择随机初始化或直接赋零;
- 在数据集中选取样本点 $(x_i,y_i)$;
- 如果该样本点被误分类，即：$y_i(w\cdot x_i + b) < 0$ 则利用 梯度下降法 (Gradient Decending) 更新 $w$, $b$ ：
- 转至第二步，循环直至数据集中所有样本皆被正确分类。
对上述算法更直观的解释就是：当找到误分类的样本时，根据步骤 $3$ 分离超平面就会向正确的方向一侧旋转，直至所有的样本点都能够被正确的分类。
插个眼，有时间的补上图片）
由于算法对分离超平面只要求能够完全地将正负两类样本分离开来，因此感知机算法对于线性可分的数据集来说拥有无穷多个解。并且这些解不仅依赖于初值的选择，也依赖于算法步骤 $2$ 中样本点的选择顺序。
通过观察 $(9)$ 式中参数的更新方式我们可以发现，最终我们得到的 $w$, $b$ 只与误分类点有关，并且只是关于所有误分类点的增量计算。即假设在训练模型的过程中第 $6$ 个样本 $(x_6, y_6)$ 被分类错误4次，则 $(x_6, y_6)$ 对最终的 $w$, $b$ 结果的贡献分别是 $\eta4x_6y_6$ 及 $4\eta y_6$。关于被误分类 $n_i$ 次的样本点 ${(x_i, y_i), i\in M}$ 更普遍的描述如下：
\[\begin{aligned} & 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{aligned} \tag{10}\]此处新定义一个变量 $\alpha_i$，其等于变量 $x_i$ 因为被误分类而用于更新参数 $w$, $b$ 的次数 $n_i$ 与学习速率 $\eta$ 的乘积：
\[\alpha_i = n_i \times \eta\]直观上来看，若一个样本点 $(x_i, y_i)$ 被误分类的次数 $n_i$ 非常多，则也说明该样本点距离分离超平面非常近以至于难以被正确分类。
现在我们根据上述定义写出 感知机算法的对偶形式：
输入：训练集 $T={(x_1, y_1), (x_2, y_2), … , (x_n, y_n)}$， 其中 $x_i\in R^n$，$y_i\in \gamma={+1, -1}$, 学习速率 $\eta \in (0,1]$。
输出：$\alpha$, 偏置参数 $b$。即感知机模型：$f(x)=sign(\sum_{j=1}^{N} \alpha_j y_j x_j\cdot x+b)$, 其中 $\alpha = (\alpha_1, \alpha_2,…, \alpha_n)^T$。
- 初始化 $\alpha \gets 0$, $b \gets 0$
- 在训练集 $T$ 中选出一个数据 $(x_i, y_i)$
- 如果 $y_i(\sum_{j=1}^{N} \alpha_j y_j x_j\cdot x+b) <0$，说明第 $i$ 个样本点被误分类了，则更新参数 $w$, $b$ ：
- 转至步骤 $2$ 直至所有数据点都被正确分类
我来讲一下之前我对这个对偶算法的一些困惑吧，希望能帮助到大家。
之前一直搞懂 $\alpha$ 与 $\alpha_i$ 之间的关系有点混乱，后来在反复的阅读中才明白它们之间的区别与关系。
这里要明确训练集中的每个样本点都拥有属于自己的 $\alpha_i$，这个 $\alpha_i$ 是用来算样本点 $x_i$ 对参数 $w$ 和 $b$ 的增量贡献。若样本点 $x_i$ 至始至终都没有被误分类过，则 $\alpha_i=0$ 意味着该样本点对参数 $w$ 和 $b$ 没有起到任何作用。这与我们后面将要提到的 支持向量机(Support Vector Machine) 的定义非常相似。
计算完所有的 $\alpha_i$ 之后，只需按定义 $(10)$ 就可以得到权重参数 $w$。 再加上计算得到的偏置 $b$ 我们就得到完整的感知机模型 $f(x)=sign(w\cdot x+b)$。
到这里还没结束，前辈们总能想出非常厉害的优化方法！我们再回过头来观察感知机对偶算法的步骤 $3$。 我们发现判断式 $y_i(\sum_{j=1}^{N} \alpha_j y_j x_j\cdot x+b) <0$ 中的训练实例 $x_i, x_j$ 仅以内积的形式出现。这意味着我们可以提前将训练集中所有训练实例的内积计算出来并以矩阵的形式存储下来，在判断式中便可以直接调用对应的值（即第 $i$ 行，第 $j$ 列）。
这个矩阵就是大名鼎鼎的 $Gram$ 矩阵：
\[G=[x_i\cdot x_j]_{N\times N}\]到这里关于感知机的部分就介绍完啦~ 大家要是发现有错误或者疑问可以私聊阿南共同进步！
:)
