跳转至

感知机 (Perceptron)⚓︎

约 2841 个字 预计阅读时间 9 分钟 总阅读量 次

介绍⚓︎

感知机模型是一种用于二分类问题的线性分类模型，它通过寻找一个线性决策边界将不同类别的样本分开。目标是寻找一个线性函数（即一个超平面），能够将两类数据点分开。

假设样本输入为向量 \(\mathbf{x} = (x_1, x_2, \dots, x_n)\)，对应的标签为 \(y \in \{-1, +1\}\) 。也就是训练集为：\(T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{M}, y_{M}\right)\right\}\)，我们希望找到一个权重向量 \(\mathbf{w}\) 和一个偏置 \(b\)，使得感知机模型的输出满足：

\[f(\mathbf{x}) = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b)\]

其中 \(\text{sign}\) 是符号函数，决定了输入样本属于哪一类。也就是：

\(\operatorname{sign}(x)=\left\{\begin{array}{ll}{+1,} & {x \geqslant 0} \\ {-1,} & {x<0}\end{array}\right.\)

对比线性回归（输出一个实数），Softmax 回归 （输出 N 个元素的 logits），这里输出的是2分类的类别。

在训练过程中，感知机通过调整权重 \(\mathbf{w}\) 和偏置 \(b\) 来使得误分类样本数最小。也就是极小化损失函数：

\[
\min _{w, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)
\]

损失函数对应于误分类点到分离超平面的总距离。

训练算法⚓︎

训练过程中使用 随机梯度下降（SGD） 方法来更新权重和偏置，具体步骤如下：

  • 初始化权重向量 \(\mathbf{w}\) 和偏置 \(b\) 为零或小的随机值。
  • 对训练数据进行迭代，对于每个误分类样本 \((\mathbf{x}_i, y_i)\)，按照以下规则更新权重和偏置：
\[\mathbf{w} = \mathbf{w} + \eta y_i \mathbf{x}_i\]
\[b = b + \eta y_i\]

其中 \(\eta\) 是学习率，用于控制步长大小。

当实例点被误分类，即位于分离超平面的错误侧，则调整\(w\), \(b\)的值，使分离超平面向该无分类点的一侧移动，直至误分类点被正确分类。

这等价于使用批量为 1 的进行梯度下降。损失函数：\(L(x, y, w) = \max (0, y < w, x>)\)

实现⚓︎

模型：决策函数为 \(f(x) = \text{sign}(w^T x + b)\)。为了简化推导，我们通常将偏置 \(b\) 吸收到权重 \(w\) 中。做法是：将所有输入向量 \(x\) 增加一个恒为1的维度，即 \(x' = [x_1, x_2, ..., x_d, 1]\)，同时权重向量也增加一个维度 \(w' = [w_1, w_2, ..., w_d, b]\)。这样， \(w^T x + b\) 就等价于 \((w')^T x'\)。在下文推导中，我们默认使用这种增广向量，并仍记作 \(w\) 和 \(x\)。

决策规则：\(\text{sign}(w^T x)\) 更新规则：当且仅当一个样本 \((x_i, y_i)\) 被错误分类时，即 \(y_i(w^T x_i) \le 0\) 时，才更新权重。

\[w_{k+1} \leftarrow w_k + \eta \cdot y_i x_i\]

其中 \(k\) 是更新的次数，\(\eta\) 是学习率。为了简化，我们可以令 \(\eta=1\)。

总结⚓︎

  1. 对于线性可分的数据，感知机算法在有限次迭代内可以收敛到正确分类的解。（证明见后）
\[
f(x)=\operatorname{sign}(w \cdot x+b)
\]

感知机模型对应于输入空间（特征空间）中的分离超平面\(w \cdot x+b=0\)。

  1. 感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。

  2. 当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数\(k\)满足不等式：

\[
k \leqslant\left(\frac{R}{\gamma}\right)^{2}
\]

\(R\) 为所有训练样本中最大的模长。\(R = \max_{i} \|x_i\|\)， \(\gamma\) 为一个常数

当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。

  1. 单层感知机一个被诟病的点是，无法对 XOR 操作进行区分。导致了AI发展的第一次低谷。

证明思路⚓︎

我们将构造两个不等式，来“夹住”经过 \(k\) 次错误更新后的权重向量 \(w_k\)。 1. 下界：证明 \(w_k\) 与一个理想的、能够完美分开数据的权重向量 \(w_{opt}\) 的内积，会随着每次更新而稳定增长，其增长量有一个下限。 2. 上界：证明 \(w_k\) 自身模长的平方 \(\|w_k\|^2\) 也会增长，但其增长是受控的，每次增长量有一个上限。

最后，通过这两个看似矛盾的增长趋势（一个内积增长很快，一个模长增长很慢），我们会推导出更新次数 \(k\) 不可能无限增加，它必然有一个上限。因此，算法必定收敛。

推导 (By Gemini 2.5 Pro)⚓︎

1. 前提与定义

  • 线性可分假设（关键！）：数据集 \(D = \{(x_i, y_i)\}\) 是线性可分的。这意味着，存在一个完美的权重向量 \(w_{opt}\)（我们不知道它是什么，但我们知道它存在），它能正确分类所有样本。为了更严格，我们假设它不仅能分开，而且是以一个大于0的间隔（margin）分开。
    • 数学上，存在 \(w_{opt}\) 和一个常数 \(\gamma > 0\)，使得对于所有样本 \((x_i, y_i)\)，都满足：\(y_i(w_{opt}^T x_i) \ge \gamma\)

  • 数据大小有界：所有输入向量的模长都有一个上限。我们定义 \(R\) 为所有训练样本中最大的模长。

    \[
R = \max_{i} \|x_i\|
\]

  • 初始条件：我们从零向量开始，即 \(w_0 = \mathbf{0}\)。

2. 推导下界（内积的增长）

假设在第 \(k\) 次迭代时，模型错误地分类了样本 \((x_i, y_i)\)，并进行了第 \(k\) 次更新，从 \(w_k\) 变为 \(w_{k+1}\)。

考虑 \(w_{k+1}\) 与我们假设存在的 \(w_{opt}\) 的内积：

\[
\begin{align*}
w_{opt}^T w_{k+1} &= w_{opt}^T (w_k + y_i x_i) & & \text{(根据更新规则)} \\
&= w_{opt}^T w_k + w_{opt}^T (y_i x_i) \\
&= w_{opt}^T w_k + y_i (w_{opt}^T x_i) & & \text{(提出标量 } y_i)
\end{align*}
\]

现在，使用我们的线性可分假设：\(y_i (w_{opt}^T x_i) \ge \gamma\)。代入上式得到：

\[
w_{opt}^T w_{k+1} \ge w_{opt}^T w_k + \gamma
\]

这是一个递推关系。经过 \(k\) 次错误更新后，从 \(w_0=0\) 开始，我们有：

\[
\begin{align*}
w_{opt}^T w_k &\ge w_{opt}^T w_{k-1} + \gamma \\
&\ge w_{opt}^T w_{k-2} + 2\gamma \\
& \dots \\
&\ge w_{opt}^T w_0 + k\gamma \\
&= k\gamma & & \text{(因为 } w_{opt}^T w_0 = 0)
\end{align*}
\]

所以我们得到了第一个重要结果 (下界):

\[
\boxed{w_{opt}^T w_k \ge k\gamma} \quad (1)
\]

3. 推导上界（模长的增长）

同样，在第 \(k\) 次更新时，考察 \(w_{k+1}\) 的模长平方：

\[
\begin{align*}
\|w_{k+1}\|^2 &= \|w_k + y_i x_i\|^2 \\
&= (w_k + y_i x_i)^T (w_k + y_i x_i) \\
&= \|w_k\|^2 + 2 w_k^T (y_i x_i) + \|y_i x_i\|^2 \\
&= \|w_k\|^2 + 2 y_i (w_k^T x_i) + y_i^2 \|x_i\|^2
\end{align*}
\]

我们来分析后面两项： * 因为 \(y_i \in \{-1, +1\}\)，所以 \(y_i^2 = 1\)。 * 更新条件：权重更新的前提是发生了错误分类，即 \(y_i (w_k^T x_i) \le 0\)。

将这两点代入上式，中间项 \(2 y_i (w_k^T x_i)\) 是一个非正数，所以我们可以得到一个不等式：

\[
\|w_{k+1}\|^2 \le \|w_k\|^2 + \|x_i\|^2
\]

现在，使用我们对数据大小的定义 \(R = \max_i \|x_i\|\)，因此 \(\|x_i\|^2 \le R^2\)。代入得到：

\[
\|w_{k+1}\|^2 \le \|w_k\|^2 + R^2
\]

这又是一个递推关系。经过 \(k\) 次错误更新后，从 \(w_0=0\) 开始：

\[
\begin{align*}
\|w_k\|^2 &\le \|w_{k-1}\|^2 + R^2 \\
&\le \|w_{k-2}\|^2 + 2R^2 \\
& \dots \\
&\le \|w_0\|^2 + kR^2 \\
&= kR^2 & & \text{(因为 } \|w_0\|^2 = 0)
\end{align*}
\]

所以我们得到了第二个重要结果 (上界):

\[
\boxed{\|w_k\|^2 \le kR^2} \quad (2)
\]

4. 结合上下界，得到结论

我们现在有两条关于 \(w_k\) 的信息： 1. \(w_{opt}^T w_k \ge k\gamma\) 2. \(\|w_k\|^2 \le kR^2\)

根据柯西-施瓦茨不等式，我们知道 \((u^T v)^2 \le \|u\|^2 \|v\|^2\)。 将 \(u = w_{opt}\) 和 \(v = w_k\) 代入，得到：

\[
(w_{opt}^T w_k)^2 \le \|w_{opt}\|^2 \|w_k\|^2
\]

现在，将我们推导出的不等式 (1) 和 (2) 代入这个不等式： * 左边用不等式(1): \((k\gamma)^2 \le (w_{opt}^T w_k)^2\) * 右边用不等式(2): \(\|w_{opt}\|^2 \|w_k\|^2 \le \|w_{opt}\|^2 (kR^2)\)

把它们串起来：

\[
(k\gamma)^2 \le (w_{opt}^T w_k)^2 \le \|w_{opt}\|^2 \|w_k\|^2 \le \|w_{opt}\|^2 (kR^2)
\]

我们就得到了：

\[
k^2 \gamma^2 \le k \|w_{opt}\|^2 R^2
\]

因为 \(k\) 是犯错次数，如果 \(k>0\)，我们可以安全地在不等式两边除以一个正数 \(k\)：

\[
k \gamma^2 \le \|w_{opt}\|^2 R^2
\]

最后，整理得到 \(k\) 的上限：

\[\boxed{ k \le \frac{\|w_{opt}\|^2 R^2}{\gamma^2} }\]

结论：这个不等式告诉我们，犯错的次数 \(k\) 不可能无限增长，它有一个由数据自身性质（\(\gamma\) 和 \(R\)）决定的上界。因此，在有限次更新之后，算法必然会停止更新，即找到了一个能够完美分对所有训练样本的权重向量 \(w\)，从而证明了算法的收敛性。

提问：感知机和支持向量机的区别是什么？

感知机（Perceptron）和支持向量机（SVM）都是用于二分类的线性分类模型，但它们在模型构建和优化目标上存在一些关键区别。

  1. 决策边界的定义

  2. 感知机：感知机的目标是找到一个线性边界，将所有训练样本正确分类，主要关注的是让每个样本的分类正确。感知机不关心样本到决策边界的距离，只要样本被正确分开即可。

  3. 支持向量机：支持向量机的目标是找到一个最大间隔（margin）的线性边界，即不仅正确分类，还要使得分类间隔最大化。最大化间隔能够提高模型的泛化能力，帮助模型在未见过的数据上表现更好。

  4. 优化目标

  5. 感知机：感知机的损失函数基于误分类点的数量，模型通过最小化误分类数来调整参数。感知机算法采用随机梯度下降法，每次仅更新误分类的样本。

  6. 支持向量机：SVM 的优化目标是最大化间隔，通过优化如下目标函数来实现：
\[\min \frac{1}{2} \|\mathbf{w}\|^2\]

同时满足所有样本点的分类约束，即使得靠近决策边界的样本到边界的距离最大。SVM 是一个凸优化问题，通常通过拉格朗日对偶理论和二次规划（Quadratic Programming, QP）来解决。

  1. 对非线性数据的处理

  2. 感知机：传统感知机无法直接处理非线性可分的数据。对于非线性数据，感知机无法找到合适的线性边界。

  3. 支持向量机：SVM 引入了核函数（如线性核、RBF 核、高斯核等）来将数据映射到高维空间，使得原本在低维空间中非线性可分的数据在高维空间中变得线性可分。这种方法称为核技巧，它使得 SVM 能够处理更多种类的分类问题。

  4. 泛化能力

  5. 感知机：感知机没有最大间隔的概念，容易受到噪声的影响，因此其泛化能力不如 SVM 稳定。

  6. 支持向量机：SVM 通过最大化间隔的策略，提高了模型的鲁棒性和泛化能力，尤其在样本分布复杂或存在噪声的情况下，SVM 的表现往往优于感知机。

  7. 算法的收敛性

  8. 感知机：当数据线性可分时，感知机算法可以在有限次更新后收敛到正确分类的解。但如果数据不可分，感知机会出现不收敛的情况。

  9. 支持向量机：SVM 是一个凸优化问题，总能找到全局最优解，因此具有更好的收敛性和稳定性。

总结⚓︎

  • 感知机适用于简单的、线性可分的数据，优化目标是减少误分类。

  • 支持向量机优化目标是最大化分类间隔，引入了核函数以处理非线性数据，适合复杂数据集，且泛化能力更强。