感知机

1. 简介

感知机是二类分类的线性分类模型，属于监督学习中的判别模型：

• 输入：实例的特征向量；
• 输出：实例的类别，取 +1 和 -1 值。

感知机本质可以看作是输入空间（特征空间）中将实例划分为正负两类的分离超平面。其基于误分类的损失函数，并利用梯度下降法对损失函数进行极小化进行求解。

2. 模型

• 定义：假设输入空间（特征空间）是 \mathcal{X} \subseteq \mathbf{R}^n，输出空间是要 \mathcal{Y} = \{+1, -1\} 。输入 \boldsymbol{x} \in \mathcal{X}

表示实例的特征向量，对应于输入空间的点；输出 y \in \mathcal{Y}

表示实例的类别。由输入空间到输出空间的如下函数

称为感知机。其中，\boldsymbol{w} 和 b 称为感知机模型参数，\boldsymbol{w} \in \mathbf{R}^n 叫作权值，b \in \mathbf{R} 叫作偏置，\mathrm{sign} 为符号函数：

感知机模型是一种线性分类模型，其假设空间是定义在输入空间中的所有线性分类模型，即函数集合 \{f | f(\boldsymbol{x}) = \boldsymbol{w}^\top \boldsymbol{x} + b\} 。

• 训练数据集： T=\{(\boldsymbol{x}_{1}, y_{1}),(\boldsymbol{x}_{2}, y_{2}), \cdots,(\boldsymbol{x}_{N}, y_{N})\} ，其中 \boldsymbol{x}_i \in \mathcal{X} = \mathbf{R}^n ，y_i \in \mathcal{Y} = \{+1, -1\}, i=1,2,\cdots,N 。感知机学习由训练数据集求得模型参数 \boldsymbol{w} 和 b ；感知机预测则根据学 习到的模型对新的输入实例给出其对应的输出类别。

3. 策略

给出了感知机模型的定义后，下一步便是探究这个模型是否能够有效地实现分类目标。为此，我们先给出一个条件假设：数据集的线性可分性，然后基于此此假设验证感知机的有效性。

3.1 数据集的线性可分性

• 定义：给定一个数据集 T=\{(\boldsymbol{x}_{1}, y_{1}),(\boldsymbol{x}_{2}, y_{2}), \cdots,(\boldsymbol{x}_{N}, y_{N})\} ，其中 \boldsymbol{x}_i \in \mathcal{X} = \mathbf{R}^n ，y_i \in \mathcal{Y} = \{+1, -1\}, i=1,2,\cdots,N 。 如果存在某个超平面 S: \boldsymbol{w}^\top \boldsymbol{x} + b = 0 能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 y_i = +1 的实例 i ，有 \boldsymbol{w}^\top \boldsymbol{x}_i + b > 0 ，对所有 y_i = -1 的实例 i ，有 \boldsymbol{w}^\top \boldsymbol{x}_i + b < 0 ；则称数据集 T 为线性可分数据集，否则称数据集 T 为线性不可分数据集。

3.2 感知机的学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面 S ，即确定感知机模型参数 \boldsymbol{w} 和 b 。那如何确定这些参数就成为了我们需要解决的问题。为此，下面引出基于损失函数极小化的学 习策略：

为了采用梯度下降算法来优化损失函数，我们需要保证给出的损失函数是关于优化参数 \boldsymbol{w} 和 b 的可微函数。

• 损失函数：选择误分类点到超平面 S 的总距离作为损失函数。输入空间中任一点 \boldsymbol{x}_0 到超平面 S 的距离为：\frac{\lvert \boldsymbol{w}^\top \boldsymbol{x}_0 + b \rvert}{\lVert \boldsymbol{w} \rVert_2}

而对于误分类的数据 (\boldsymbol{x}_i, y_i)，-y_i(\boldsymbol{w}^\top \boldsymbol{x} + b) > 0 总成立。

因为当\boldsymbol{w}^\top \boldsymbol{x} + b>0 时，y_i = -1 ；当 \boldsymbol{w}^\top \boldsymbol{x} + b < 0 时，y_i = +1 。

故误分类点 \boldsymbol{x}_i 到超平面 S 的距离为-\frac{y_i (\boldsymbol{w}^\top \boldsymbol{x}_i + b)}{\lVert \boldsymbol{w} \rVert_2} 这样，假设超平面 S 的误分类点集合为 M，那么所有误分类点到超平面 S 的总距离为-\frac{\sum_{\boldsymbol{x}_i \in M} y_i (\boldsymbol{w}^\top \boldsymbol{x}_i + b)}{\lVert \boldsymbol{w} \rVert_2} 不考虑相同的分母 \frac{1}{\lVert \boldsymbol{w} \rVert} ，即得到感知机学习的损失函数：

式 (2) 即为感知机学 习的经验风险函数。显然，该损失函数是非负的，且关于参数 \boldsymbol{w}, b 连续可微。

4. 算法

上述学习策略验证了感知机在线性可分数据集上的有效性，下面就是要给出如何在训练数据集上具体实现感知机学习过程。感知机学习问题有两种形式，一种是最直观的原始形式，一种是原始形式的对偶形式。

4.1 原始形式

感知机学习算法是针对以下最优化问题的算法：

• 给定一个训练数据集 T=\{(\boldsymbol{x}_{1}, y_{1}),(\boldsymbol{x}_{2}, y_{2}), \cdots,(\boldsymbol{x}_{N}, y_{N})\}，其中 \boldsymbol{x}_i \in \mathcal{X} = \mathbf{R}^n ，y_i \in \mathcal{Y} = \{+1, -1\}, i=1,2,\cdots,N 。求参数 \boldsymbol{w} 和 b ，使其为以下损失函数极小化问题的解：

其中 M 为误分类点的集合。

感知机学习算法是误分类驱动的，具体采用随机梯度下降法：首先，任意选取一个超平面参数 \boldsymbol{w}_0, b_0 ；然后使用梯度下降法不降地极小化目标函数 (3) 。极小化过程不是一次使 M 中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。假设误分类点集合 M 是固定的，那么损失函数 L(\boldsymbol{w}, b) 的梯度由：

设学习率为 \eta(0 < \eta \leq 1)，则梯度下降法更新参数的方式为（即每次迭都加上负梯度）：

综上所述，可以总结为如下算法：

算法：感知机学习算法的原始形式 输入：训练数据集 T=\{(\boldsymbol{x}_{1}, y_{1}),(\boldsymbol{x}_{2}, y_{2}), \cdots,(\boldsymbol{x}_{N}, y_{N})\} ，其中 \boldsymbol{x}_i \in \mathcal{X} = \mathbf{R}^n ，y_i \in \mathcal{Y} = \{+1, -1\}, i=1,2,\cdots,N ；学 习率 \eta(0 < \eta \leq 1) ； 输出：\boldsymbol{w}, b ；感知机模型 f(x) = \mathrm{sign}(\boldsymbol{w}^\top \boldsymbol{x} + b) 。

1. 选取初值 \boldsymbol{w}_0, b ；
2. 在训练数据集中选取数据 (\boldsymbol{x}_i, y_i) ；
3. 如果 y_i(\boldsymbol{w}^\top \boldsymbol{x}_i + b) \leq 0 （即为误分类样本），更新参数

4. 转至 2.，直至训练集中没有误分类点。 给出了感知机的算法后，还需要验证该算法是否能收敛到最优值。为了便于叙述，将偏置并入权值向量，记作 \hat{\boldsymbol{w}} = (\boldsymbol{w}^\top, b)^\top ；同样也将输入向量加以扩充，加进常数 1 ，记作 \hat{\boldsymbol{x}} = (\boldsymbol{x}^\top, 1) ，从而有 \hat{\boldsymbol{w}}^\top \hat{\boldsymbol{x}} = \boldsymbol{w}^\top \boldsymbol{x} + b 。以下定理确保了感知机的算法能够准确收敛：

定理：设训练数据集 T=\{(\boldsymbol{x}_{1}, y_{1}),(\boldsymbol{x}_{2}, y_{2}), \cdots,(\boldsymbol{x}_{N}, y_{N})\} 是线性可分的，其中 \boldsymbol{x}_i \in \mathcal{X} = \mathbf{R}^n ，y_i \in \mathcal{Y} = \{+1, -1\}, i=1,2,\cdots,N ；则有

1. 存在满足条件 \lVert \hat{\boldsymbol{w}}_{\mathrm{opt}} \rVert_2 = 1 的超平面 \hat{\boldsymbol{w}}_{\mathrm{opt}}^\top \hat{\boldsymbol{x}} = \boldsymbol{w}_{\mathrm{opt}}^\top \boldsymbol{x} + b_{\mathrm{opt}} = 0 将训练数据集完全正确分开；且存在 \gamma > 0，对所有 i = 1,2,\cdots,N ，有

2. 令 R = \max_{1 \leq i \leq N} \lVert \hat{\boldsymbol{x}}_i \rVert ，则上述感知机算法在训练数据集上的误分类次数 k 满足不等式

该定理的具体证明可见《统计学习方法》P. 47，这里就不展开了。

4.2 对偶形式

除了使用原始形式来求解感知机模型外，也可以使用其对偶形式来求解，二者在求解最优参数时是等价的。原始形式下，我们将参数 \boldsymbol{w}, b 看作是超平面 \boldsymbol{w}^\top \boldsymbol{x} + b 的系数进行优化；而在对偶问题中，我们将参数 \boldsymbol{w}, b 看作是 \boldsymbol{x}, y 的函数。根据上文给出的算法，不失一般性，我们可以假定初始参数值 \boldsymbol{w}_0, b_0 均为 0，误分类点 (\boldsymbol{x}_i, y_i) 对参数 \boldsymbol{w}, b 的更新一共作用了 n_i 次，则最后学习到的参数为

其中，\alpha_i = n_i \eta 。

算法：感知机学习算法的对偶形式 输入：训练数据集 T=\{(\boldsymbol{x}_{1}, y_{1}),(\boldsymbol{x}_{2}, y_{2}), \cdots,(\boldsymbol{x}_{N}, y_{N})\} ，其中 \boldsymbol{x}_i \in \mathcal{X} = \mathbf{R}^n ，y_i \in \mathcal{Y} = \{+1, -1\}, i=1,2,\cdots,N ；学 习率 \eta(0 < \eta \leq 1) ； 输出：\boldsymbol{\alpha} ；感知机模型 f(x) = \mathrm{sign}(\sum_{i=1}^N \alpha_i y_i \boldsymbol{x}_i^\top \boldsymbol{x} + \sum_{i=1}^N \alpha_i y_i) 。\boldsymbol{\alpha} \leftarrow 0；

1. 在训练集中选取数据 (\boldsymbol{x}_j, y_j) ；
2. 如果 y_j(\sum_{i=1}^N \alpha_i y_i \boldsymbol{x}_i^\top \boldsymbol{x}_j + \sum_{i=1}^N \alpha_i y_i) \leq 0 ，则\alpha_i \leftarrow \alpha_i + \eta
3. 转至 2.，直至训练集中没有误分类点。

对偶形式中的训练实例 \boldsymbol{x}_i 仅以内积形式出现，因此为了方便可以事先计算出所有实例间的内积，即 Gram 矩阵：

与原始形式一样，感知机学习算法的对偶形式也是收敛的，存在多个解。

附录

• 《统计学习方法》by 李航

文章作者: hotarugali

文章链接: https://hotarugali.github.io/2022/04/24/Technique/MachineLearning/ 感知机 / 感知机 /

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。 转载请注明来自 お前はどこまで見えている！