深入理解感知机：从原始形式到核技巧

感知机（Perceptron）是神经网络和支持向量机（SVM）的鼻祖。虽然它只是一个简单的线性二分类模型，但其背后的思想——包括Novikoff收敛定理、对偶形式以及核技巧（Kernel Trick）的应用，构成了现代机器学习的重要基石。

本文将基于相关课程内容，系统梳理感知机的核心逻辑，并重点展开介绍其对偶形式与核感知机的原理。

1. 感知机模型基础

1.1 定义

感知机旨在求得一个能够将训练数据集的正实例点和负实例点完全正确分开的分离超平面。

• 输入空间：$\mathcal{X} \subseteq \mathbb{R}^n$
• 输出空间：$\mathcal{Y} = {+1, -1}$
• 模型公式： $$f(x) = \text{sign}(w \cdot x + b)$$ 其中，$w$ 为权值向量（超平面的法向量），$b$ 为偏置（截距）。

1.2 几何解释

线性方程 $w \cdot x + b = 0$ 对应于特征空间中的一个超平面 S。

• 位于超平面一侧的点被归为正类（+1）；
• 位于另一侧的点被归为负类（-1）。

1.3 学习策略

感知机假设数据是线性可分的。它的学习目标是最小化误分类点到超平面的总距离。
损失函数定义为：

$$L(w, b) = - \sum_{x_i \in M} y_i (w \cdot x_i + b)$$

其中 $M$ 是误分类点的集合。对于误分类点，$-y_i(w \cdot x_i + b) > 0$，因此损失函数总是非负的。

---

2. 原始形式 (Primal Form)

原始形式是感知机最直观的解法，采用随机梯度下降法 (SGD)。

算法流程

1. 选取初值 $w_0, b_0$（通常为0）。
2. 在训练集中选取数据 $(x_i, y_i)$。
3. 若该点被误分类（即 $y_i(w \cdot x_i + b) \le 0$），则进行更新： $$w \leftarrow w + \eta y_i x_i$$ $$b \leftarrow b + \eta y_i$$ 注：$\eta$ 为学习率（步长），通常取 $(0, 1]$。
4. 转至步骤2，直到训练集中没有误分类点。

Novikoff 定理（收敛性保证）

Novikoff 定理证明了：只要数据线性可分，感知机算法一定会在有限步内收敛。
设训练数据集的间隔为 $\gamma$，最大模长为 $R$，则最大修正次数 $k$ 满足：

$$k \le \left( \frac{R}{\gamma} \right)^2$$

这给算法吃了一颗“定心丸”：只要路是通的，感知机就不会陷入死循环。

---

3. 对偶形式 (Dual Form)

对偶形式并不是一种新的算法，而是原始形式的另一种数学表达。引入对偶形式的核心目的有两个：

1. 计算效率：当特征维度很高而样本数量相对较少时，对偶形式通过预计算 Gram 矩阵 可以大幅加速。
2. 引入核函数：对偶形式是将线性模型推广到非线性模型（核感知机）的必经之路。

3.1 推导逻辑

在原始形式中，我们不断地修改 $w$：$w \leftarrow w + \eta y_i x_i$。
假设初值为 0，经过若干次迭代后，最终的 $w$ 其实就是训练数据实例的线性组合。

假设第 $i$ 个样本 $(x_i, y_i)$ 在整个过程中被用来修正了 $n_i$ 次（即它被误分类了 $n_i$ 次），设 $\alpha_i = n_i \eta$。
那么最终的参数可以表示为：

$$w = \sum_{i=1}^N \alpha_i y_i x_i$$ $$b = \sum_{i=1}^N \alpha_i y_i$$

这里，$N$ 是样本总数，$\alpha_i \ge 0$。如果 $\alpha_i > 0$，说明该样本点对超平面的形成有贡献（类似于SVM中的支持向量）。

3.2 对偶形式的模型

将 $w$ 和 $b$ 的表达式代入原始模型 $f(x)$，我们得到对偶形式的模型公式：

$$f(x) = \text{sign}\left( \sum_{j=1}^N \alpha_j y_j (x_j \cdot x) + b \right)$$

注意：这里的核心计算变成了两个向量的内积 $(x_j \cdot x)$。

3.3 对偶形式的算法

1. 初始化 $\alpha = (0,0,…,0)^T, b=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) \le 0$$
4. 更新该点的系数： $$\alpha_i \leftarrow \alpha_i + \eta$$ $$b \leftarrow b + \eta y_i$$
5. 直到没有误分类点。

3.4 Gram 矩阵 (Gram Matrix)

在步骤3的判断条件中，我们需要频繁计算样本之间的内积 $(x_j \cdot x_i)$。
为了加速，我们可以预先计算所有样本之间的内积，存储在一个 $N \times N$ 的矩阵中，这就是 Gram 矩阵：

$$G = [x_i \cdot x_j]_{N \times N}$$ $$G_{ij} = x_i \cdot x_j$$

这样在迭代过程中，只需要查表即可，极大提高了计算速度。

---

4. 核感知机 (Kernel Perceptron)

感知机最大的局限性在于它只能解决线性可分问题。对于著名的 XOR 问题（异或问题，了解一下这个问题的具体细节，简单的），普通感知机束手无策。
核技巧 (Kernel Trick) 的引入，让感知机拥有了处理非线性数据的能力。

4.1 基本思想

如果数据在原始空间（低维）不可分，我们可以通过一个映射函数 $\phi(x)$ 将数据映射到一个高维特征空间。
在高维空间中，原本纠缠在一起的数据往往变得线性可分了。

4.2 为什么需要核函数？

在对偶形式中，我们看到分类决策完全依赖于内积：

$$f(x) = \text{sign}\left( \sum_{j=1}^N \alpha_j y_j (\mathbf{x_j \cdot x}) + b \right)$$

如果我们将数据映射到高维空间，公式就变成了：

$$f(x) = \text{sign}\left( \sum_{j=1}^N \alpha_j y_j (\mathbf{\phi(x_j) \cdot \phi(x)}) + b \right)$$

问题：直接计算高维映射 $\phi(x)$ 及其内积 $\phi(x_j) \cdot \phi(x)$ 计算量可能极其巨大（甚至无穷维）。
解决：我们定义一个核函数 $K(x, y)$，满足：

$$K(x, y) = \phi(x) \cdot \phi(y)$$

核函数的魔力在于：我们可以直接在低维空间计算出高维空间的内积，而不需要知道 $\phi(x)$ 到底长什么样。

4.3 核感知机算法

只需将对偶形式中的内积 $(x_j \cdot x_i)$ 替换为核函数 $K(x_j, x_i)$ 即可：

1. 误分类条件变为： $$y_i \left( \sum_{j=1}^N \alpha_j y_j K(x_j, x_i) + b \right) \le 0$$
2. 常见的核函数：
   • 多项式核 (Polynomial Kernel)：$K(x, z) = (x \cdot z + 1)^p$
   • 高斯核 (Gaussian / RBF Kernel)：$K(x, z) = \exp(-\frac{||x-z||^2}{2\sigma^2})$

通过使用高斯核，感知机实际上获得了一个拥有无穷维特征空间的非线性分类界面，这使得它能够对极其复杂的数据分布进行分类。

---

5. 总结

特性	原始形式 (Primal)	对偶形式 (Dual)	核感知机 (Kernel)
参数	权值向量 $w$, 偏置 $b$	实例系数 $\alpha$, 偏置 $b$	实例系数 $\alpha$, 偏置 $b$
核心运算	向量加法	向量内积	核函数计算
优势场景	特征维度低，样本多	特征维度高，样本少	数据线性不可分
加速手段	无	Gram 矩阵	核技巧

感知机虽然古老，但它不仅演示了“错误驱动学习”的基本原理，其对偶形式更是通向 SVM 和核方法的桥梁。理解了 Novikoff 定理的界限、对偶形式的转化以及核技巧的升维打击，就掌握了线性分类器的精髓。