第2章 感知机
感知机（Perceptron）是Rosenblatt于1957年提出的简单线性分类模型，属于神经网络与支持向量机的基础。感知机模型是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别（取+1或-1）。感知机模型旨在学习一个将特征空间中的数据划分到两个不同类别的超平面。本章详细介绍感知机模型、学习策略、求解算法以及相关理论分析。
2.1 感知机模型
感知机模型是一种最基本的线性分类模型。给定训练数据集
其中 \(x_i \in \mathcal{X} = \mathbf{R}^n\) 为输入实例的特征向量，\(y_i \in \mathcal{Y} = \{+1, -1\}\) 为输出类别，感知机模型将输入空间划分到两个类别之一。
感知机模型由权重向量 \(w = (w^{(1)}, w^{(2)}, \ldots, w^{(n)})^T\) 和偏置项 \(b \in \mathbf{R}\) 决定。其数学表达式为
其中 \(w \cdot x\) 表示两个向量的内积（点积），即
符号函数 \(\text/sign\) 的定义如下：
当 \(w \cdot x + b > 0\) 时，模型输出 +1；当 \(w \cdot x + b < 0\) 时，模型输出 -1。
2.1.1 几何解释
从几何角度来看，感知机模型对应于特征空间 \(\mathbf{R}^n\) 中的一个超平面。方程
表示一个 \(n\) 维超平面，其中 \(w\) 是该超平面的法向量，\(b\) 是截距（偏置项）。这个超平面将特征空间划分为两个半空间：一个半空间中的点满足 \(w \cdot x + b > 0\)（对应类别 +1），另一个半空间中的点满足 \(w \cdot x + b < 0\)（对应类别 -1）。
具体而言，给定一个点 \(x_0\)，它到超平面 \(w \cdot x + b = 0\) 的几何距离为
其中 \(\|w\| = \sqrt{w \cdot w} = \sqrt{\sum_{i=1}^{n} (w^{(i)})^2}\) 是权重向量的欧几里得范数。
感知机学习的目标就是找到这样一个超平面，使得训练数据集中所有正类点（\(y_i = +1\)）位于超平面的一侧，所有负类点（\(y_i = -1\)）位于超平面的另一侧。
2.1.2 感知机的假设空间
感知机的假设空间 \(\mathcal{H}\) 定义为所有可能的线性分类器集合：
这意味着感知机的假设空间是特征空间中所有线性函数的集合。需要注意的是，感知机只能处理线性可分的数据，对于非线性可分的数据，感知机无法找到满足条件的超平面。
2.2 学习策略
感知机学习的目标是找到一个能够将训练数据集中所有正类和负类点完全分开的超平面。为了达到这个目标，需要定义一个损失函数来衡量当前超平面的优劣，然后通过优化算法最小化这个损失函数。
2.2.1 损失函数的定义
感知机学习采用的损失函数是误分类点到超平面的总距离。给定超平面 \((w, b)\)，误分类点集合记为 \(M\)，则损失函数定义为
这个损失函数具有明确的直观意义。对于误分类点 \(x_i\) 而言：
- 当 \(y_i = +1\) 且 \(w \cdot x_i + b < 0\) 时，\(y_i(w \cdot x_i + b) < 0\)，贡献负值；
- 当 \(y_i = -1\) 且 \(w \cdot x_i + b > 0\) 时，同样有 \(y_i(w \cdot x_i + b) < 0\)，贡献负值。
取负号后，误分类点的损失为正值，且误分类越严重（\(|w \cdot x_i + b|\) 越大），损失值越大。
为什么不直接使用误分类点的个数作为损失函数？这是因为误分类点个数是不可导的离散函数，难以进行优化。而上述距离损失函数是关于 \(w\) 和 \(b\) 的连续可导函数，便于使用梯度下降等优化算法。
2.2.2 经验风险最小化
感知机学习的策略是经验风险最小化，即最小化上述损失函数：
需要强调的是，感知机学习仅在数据集线性可分时才能保证找到最优解。如果数据集本身不是线性可分的，优化过程将无法收敛，学习算法将在误分类点之间来回振荡。
2.3 原始形式学习算法
感知机学习算法采用随机梯度下降法（Stochastic Gradient Descent, SGD）来最小化损失函数。下面详细介绍算法的具体步骤。
2.3.1 算法描述
算法 2.1（感知机学习算法——原始形式）
输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}\)，其中 \(x_i \in \mathbf{R}^n\)，\(y_i \in \{+1, -1\}\)；学习率 \(\eta\)（也称为步长，\(0 < \eta \leq 1\)）。
输出：权重向量 \(w\) 和偏置项 \(b\)，感知机模型 \(f(x) = \text{sign}(w \cdot x + b)\)。
算法步骤：
1。 初始化：选取初值 \(w_0, b_0\)。通常可以取 \(w_0 = 0\) 或很小的随机数，\(b_0 = 0\)。
2。 在训练数据集中选取数据点 \((x_i, y_i)\)。
3。 如果该数据点 \((x_i, y_i)\) 被误分类，即 \(y_i(w \cdot x_i + b) \leq 0\)，则更新参数： $\(w \leftarrow w + \eta y_i x_i\)$ $\(b \leftarrow b + \eta y_i\)$
4。 转到步骤 2，直到训练数据集中没有误分类点。
上述算法的核心思想是：每当遇到一个误分类点时，根据该点的类别和特征向量对权重向量和偏置进行更新，使得超平面朝着减少该误分类点错误的方向移动。
2.3.2 算法收敛性分析
关于感知机学习算法的收敛性，有著名的Novikoff定理（也称为Novikoff收敛定理）。该定理表明，当训练数据集线性可分时，感知机学习算法能够在有限步内收敛找到一个将所有数据正确分类的超平面。
Novikoff收敛定理：设训练数据集 \(T\) 是线性可分的，即存在超平面 \(\bar{w} \cdot x + \bar{b} = 0\) 能够将所有训练样本正确分类，且存在常数 \(\gamma > 0\) 和 \(R > 0\) 使得对所有 \(i\) 有
则感知机学习算法在原始形式下最多经过 \(R^2 / \gamma^2\) 次迭代即可收敛。
该定理的证明依赖于权重向量的更新规则和线性可分假设。通过分析权重向量在每次更新后的变化，可以证明误分类的次数有上界，从而保证算法收敛。
2.3.3 算法特点
感知机学习算法具有以下特点：
- 在线学习：算法每次只处理一个训练样本，符合随机梯度下降的思想。
- 迭代更新：参数在每次遇到误分类点时进行更新。
- 不唯一性：由于初始值选择和数据点处理顺序的不同，最终学到的超平面可能不唯一。
- 对偶形式：除了原始形式外，感知机学习算法还有对偶形式，可以进一步优化计算效率。
2.4 对偶形式学习算法
感知机学习算法的对偶形式是另一种等价的求解方法，它将权重向量表示为训练样本的线性组合。通过引入系数 \(\alpha_i\)（一个样本被误分类的次数），可以直接计算最终的权重向量。
2.4.1 算法描述
算法 2.2（感知机学习算法——对偶形式）
输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}\)，其中 \(x_i \in \mathbf{R}^n\)，\(y_i \in \{+1, -1\}\)；学习率 \(\eta\)（\(0 < \eta \leq 1\)）。
输出：权重向量 \(w\) 和偏置项 \(b\)，感知机模型 \(f(x) = \text{sign}(w \cdot x + b)\)。
算法步骤：
1。 初始化：\(\alpha \leftarrow 0\)（长度为 \(N\) 的零向量），\(b \leftarrow 0\)。
2。 在训练数据集中选取数据点 \((x_i, y_i)\)。
3。 计算 \(w \cdot x_i + b = \sum_{j=1}^{N} \alpha_j y_j (x_j \cdot x_i) + b\)。
4。 如果 \(y_i(w \cdot x_i + b) \leq 0\)，更新参数： $\(\alpha_i \leftarrow \alpha_i + \eta\)$ $\(b \leftarrow b + \eta y_i\)$
5。 转到步骤 2，直到训练数据集中没有误分类点。
对偶形式的核心优势在于它只依赖于样本之间的内积 \(x_j \cdot x_i\)。在后续的支持向量机学习中，这种内积表示将被进一步发展为核技巧。
2.4.2 Gram矩阵
在对偶形式中，计算过程中需要大量使用样本之间的内积。为了提高计算效率，可以预先计算并存储样本之间的内积矩阵，即Gram矩阵：
通过查表获取内积值，可以显著减少重复计算，特别是在样本维数较高时效果更为明显。
2.4.3 对偶形式与原始形式的对比
| 对比项 | 原始形式 | 对偶形式 |
|---|---|---|
| 参数表示 | 直接学习 \(w\) 和 \(b\) | 学习 \(\alpha\) 和 \(b\)，通过 \(\alpha\) 间接得到 \(w\) |
| 计算复杂度 | 每次更新 \(O(n)\) | 每次更新需要计算 \(O(n)\) 的内积，或查表 \(O(1)\) |
| 存储需求 | 仅需存储 \(w\) 和 \(b\) | 需要存储 Gram 矩阵 \(O(N^2)\) |
| 适用场景 | 样本维数较低时 | 样本数量较少、维数较高时 |
2.5 收敛定理（Novikoff定理）
Novikoff定理是感知机学习理论中最重要的收敛性结果之一。该定理证明了在线性可分训练数据上，感知机学习算法必然在有限步内收敛。
2.5.1 定理陈述
设训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}\) 是线性可分的，即存在超平面 \(\bar{w} \cdot x + \bar{b} = 0\) 和常数 \(\gamma > 0\) 使得对所有 \(i = 1, 2, \ldots, N\) 有
同时假设 \(\|x_i\| \leq R\)（所有样本点落在半径为 \(R\) 的球内）。
则感知机学习算法最多经过 \(R^2 / \gamma^2\) 次误分类就可以停止，此时学到的超平面能够正确分类所有训练样本。
2.5.2 定理证明概要
Novikoff定理的证明基于以下关键观察：
1。 设 \(\bar{w}\) 是目标超平面的法向量（归一化后 \(\|\bar{w}\| = 1\)），则对所有 \(i\) 有 \(y_i(\bar{w} \cdot x_i) \geq \gamma\)。
2。 感知机算法初始化时取 \(w_0 = 0\)。在第 \(k\) 次误分类更新时，有 \(w_k = w_{k-1} + y_i x_i\)。
3。 分析 \(w_k\) 与 \(\bar{w}\) 的内积：可以证明 \(w_k\) 与 \(\bar{w}\) 的内积随误分类次数增加而增大。
4。 分析 \(\|w_k\|^2\) 的增长：每次误分类更新使 \(\|w_k\|^2\) 增加不超过 \(R^2\)。
5。 综合以上两点，可以得到误分类次数的上界：\(k \leq R^2 / \gamma^2\)。
这个收敛界虽然不是最优的（支持向量机的收敛界更紧），但它清楚地表明了感知机算法在线性可分情况下的收敛性。
2.5.3 收敛界的意义
Novikoff定理的收敛界 \(R^2 / \gamma^2\) 具有直观的解释：
- \(R\) 反映了训练数据的分布范围（数据点距原点的最大距离）；
- \(\gamma\) 反映了数据线性可分的程度（几何间隔）；
- 可分程度越好（\(\gamma\) 越大），收敛越快；
- 数据分布范围越小（\(R\) 越小），收敛越快。
需要注意的是，这个界是非常宽松的上界，实际收敛步数往往远小于这个值。
2.6 Pocket算法
标准感知机学习算法要求训练数据必须线性可分才能保证收敛。然而在实际应用中，许多数据集并不是严格线性可分的，或者数据中存在噪声。这时，标准感知机算法可能无法终止（会陷入无限循环）。
Pocket算法（口袋算法）是为了处理线性不可分数据而提出的改进算法，它旨在找到一个尽可能少犯错的超平面。
2.6.1 算法描述
算法 2.3（Pocket算法）
输入：训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}\)，其中 \(x_i \in \mathbf{R}^n\)，\(y_i \in \{+1, -1\}\)；学习率 \(\eta\)；最大迭代次数 \(T\)。
输出：权重向量 \(w\) 和偏置项 \(b\)，感知机模型 \(f(x) = \text{sign}(w \cdot x + b)\)。
算法步骤：
1。 初始化：将最佳权重 \((w_{\text{best}}, b_{\text{best}})\) 初始化为 \((0, 0)\)，记录最佳错误数 \(E_{\text{best}} = N\)（或一个很大的数）。
2。 对于迭代 \(t = 1, 2, \ldots, T\)： (a) 随机选取一个训练样本 \((x_i, y_i)\)。 (b) 计算预测值 \(\hat{y} = \text{sign}(w_t \cdot x_i + b_t)\)。 (c) 如果 \(\hat{y} \neq y_i\)（即样本被误分类），执行更新： $\(w_{t+1} \leftarrow w_t + \eta y_i x_i\)$ $\(b_{t+1} \leftarrow b_t + \eta y_i\)$ (d) 计算当前权重 \((w_{t+1}, b_{t+1})\) 在整个训练集上的错误数 \(E_{\text{new}}\)。 (e) 如果 \(E_{\text{new}} < E_{\text{best}}\)，则更新最佳权重： $\(w_{\text{best}} \leftarrow w_{t+1}\)$ $\(b_{\text{best}} \leftarrow b_{t+1}\)$ $\(E_{\text{best}} \leftarrow E_{\text{new}}\)$
3。 返回 \((w_{\text{best}}, b_{\text{best}})\) 作为最终模型。
2.6.2 算法特点
Pocket算法的核心思想是“口袋”中始终保存目前见到的最好的超平面。与标准感知机算法相比，Pocket算法具有以下特点：
- 可处理线性不可分数据：即使数据不是线性可分的，算法也能在有限迭代后停止。
- 保优机制：始终保存迄今为止遇到的错误数最少的超平面。
- 收敛保证：由于参数更新是有限的，算法必然在 \(T\) 次迭代后终止。
- 时间复杂度增加：每次更新后需要遍历整个训练集计算错误数，计算开销较大。
2.6.3 与标准感知机的对比
| 特性 | 标准感知机 | Pocket算法 |
|---|---|---|
| 数据要求 | 必须线性可分 | 可处理线性不可分数据 |
| 收敛性 | 线性可分时收敛 | 迭代固定次数后终止 |
| 输出模型 | 最后一次更新的模型 | 历史上最佳模型 |
| 计算开销 | 每次只处理一个样本 | 每次需计算全部样本的错误 |
| 解的稳定性 | 可能不稳定 | 相对稳定 |
2.7 感知机的局限性
尽管感知机是一个简洁优美的模型，但它存在固有的局限性，了解这些局限性有助于理解后续更复杂的模型（如支持向量机、神经网络）。
2.7.1 线性可分假设
感知机只能处理线性可分的数据。如果训练数据不是线性可分的，标准感知机算法将无法收敛。以经典的XOR问题为例：四个点 \((0,0)\)、\((0,1)\)、\((1,0)\)、\((1,1)\) 分别标注为负类和正类，无法用一条直线将两类点完全分开，因此感知机无法解决XOR问题。
2.7.2 解的不唯一性
当数据线性可分时，满足条件的超平面有无穷多个。感知机学习算法最终的解依赖于参数初始化和数据点的处理顺序。不同的随机种子或数据排列顺序可能导致完全不同的超平面。
2.7.3 过拟合风险
感知机模型简单，容易欠拟合；但在某些情况下，如果权重向量模值过大，也可能导致对噪声过于敏感。虽然感知机本身结构简单，通常不会严重过拟合，但在实际应用中仍需注意模型选择。
2.7.4 与支持向量机的关系
感知机是支持向量机的重要基础。两者的主要区别在于：
- 感知机只要求找到将数据分开的超平面，不考虑几何间隔；
- 支持向量机要求最大化几何间隔，因此解是唯一的。
支持向量机可以看作是间隔最大化的感知机，这一观点在后续章节中将详细阐述。
公式汇总表
| 编号 | 公式名称 | 公式表达 |
|---|---|---|
| (2.1) | 感知机模型 | \(f(x) = \text{sign}(w \cdot x + b)\) |
| (2.2) | 内积展开 | \(w \cdot x = \sum_{i=1}^{n} w^{(i)} x^{(i)}\) |
| (2.3) | 符号函数 | \(\text{sign}(z) = \begin{cases} +1 & z \geq 0 \\ -1 & z < 0 \end{cases}\) |
| (2.4) | 点到超平面距离 | \(\frac{\|w \cdot x_0 + b\|}{\|w\|}\) |
| (2.5) | 感知机损失函数 | \(L(w, b) = -\sum_{x_i \in M} y_i (w \cdot x_i + b)\) |
| (2.6) | 原始形式参数更新 | \(w \leftarrow w + \eta y_i x_i\) |
| (2.7) | 原始形式偏置更新 | \(b \leftarrow b + \eta y_i\) |
| (2.8) | 对偶形式权重表示 | \(w = \sum_{j=1}^{N} \alpha_j y_j x_j\) |
| (2.9) | Gram矩阵 | \(g_{ij} = x_i \cdot x_j\) |
| (2.10) | Novikoff收敛界 | \(k \leq R^2 / \gamma^2\) |
本章小结
本章系统介绍了感知机模型的相关知识。感知机是神经网络和支持向量机的基础模型，它结构简单、易于实现。感知机模型对应于特征空间中的一个超平面 \(w \cdot x + b = 0\)，通过符号函数 \(\text{sign}\) 进行二类分类。学习策略采用经验风险最小化，损失函数定义为误分类点到超平面的总距离。学习算法采用随机梯度下降法，包括原始形式和对偶形式两种。Novikoff定理证明了算法在线性可分数据上的收敛性。Pocket算法则扩展了感知机处理线性不可分数据的能力。理解感知机的局限性对于学习后续更复杂的模型具有重要意义。