支持向量机的对偶问题推导及核函数的Mercer条件

支持向量机（SVM）是一种强大的分类算法，其核心思想是寻找一个能最大化“间隔”的超平面来分隔不同类别的数据。为了处理更复杂的情况，并高效地引入核技巧，我们需要推导其对偶形式。

1. 理解原始问题与拉格朗日乘子法

我们的目标是解决一个带约束的优化问题，这称为原始问题。

写出原始优化目标。我们希望最小化模型的复杂度，同时确保所有数据点都被正确分类（或满足软间隔条件）。用数学语言描述，我们希望找到法向量 $w$ 和截距 $b$，使得：

$$ \min_{w, b} \frac{1}{2} \|w\|^2 \quad \text{满足约束} \quad y_i(w \cdot x_i + b) \geq 1, \forall i $$

这里 $\frac{1}{2} \|w\|^2$ 是目标函数， $y_i$ 是样本 $x_i$ 的标签（取值为 $+1$ 或 $-1$）， $w \cdot x_i + b$ 是模型的判别函数。

应用拉格朗日乘子法。为了处理不等式约束，我们为每个约束条件引入一个非负的拉格朗日乘子 $\alpha_i$。构建拉格朗日函数：

$$ L(w, b, \alpha) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^{n} \alpha_i [y_i(w \cdot x_i + b) - 1] $$

其中 $\alpha_i \geq 0$。

分析拉格朗日函数。原问题的最优解必须满足 KKT 条件。其中的关键条件是互补松弛条件： $\alpha_i [y_i(w \cdot x_i + b) - 1] = 0$。这意味着，对于每个样本点，要么其对应的乘子 $\alpha_i = 0$（该点不是支持向量），要么该点恰好位于间隔边界上（即 $y_i(w \cdot x_i + b) = 1$），此时 $\alpha_i$ 可以大于 $0$（该点是支持向量）。

2. 推导对偶问题

对偶问题的目标是通过改变优化的顺序，将问题转化为一个更容易求解的形式。

求解内部最小化问题。我们首先固定 $\alpha$，求 $L$ 关于 $w$ 和 $b$ 的极小值。分别求偏导并令其为零：

$$ \frac{\partial L}{\partial w} = 0 \implies w = \sum_{i=1}^{n} \alpha_i y_i x_i $$

$$ \frac{\partial L}{\partial b} = 0 \implies \sum_{i=1}^{n} \alpha_i y_i = 0 $$

这两个方程将最优的 $w$ 表示为所有样本点的线性组合（只有 $\alpha_i > 0$ 的支持向量真正起作用），并给出了 $\alpha_i$ 必须满足的一个约束。

将求得的 $w$ 和 $b$ 的关系代回拉格朗日函数 $L$。经过一系列代数化简（合并同类项、应用约束 $\sum \alpha_i y_i = 0$），得到仅关于 $\alpha$ 的对偶问题目标函数：

$$ \max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) $$

施加约束条件。对偶问题的变量 $\alpha_i$ 必须满足从拉格朗日法和KKT条件得到的约束：

1. $\alpha_i \geq 0$，对所有 $i$
2. $\sum_{i=1}^{n} \alpha_i y_i = 0$

现在，我们求解这个关于 $\alpha$ 的约束优化问题。一旦得到最优的 $\alpha^*$，就可以通过 $w^* = \sum \alpha_i^* y_i x_i$ 恢复出原始问题的最优解 $w^*$。对于截距 $b$，通常选取一个满足 $\alpha_i^* > 0$ 的支持向量 $x_s$，利用 $y_s(w^* \cdot x_s + b) = 1$ 解出 $b^*$。

3. 理解对偶形式与核技巧

观察对偶问题的目标函数，关键项是 $x_i \cdot x_j$，即两个样本数据点之间的内积。

发现核技巧的入口。整个对偶问题的求解过程，以及最终的决策函数，都只依赖于样本点之间的内积。定义决策函数：对于一个新样本 $x$，其预测类别为：

$$ \text{sign} \left( \sum_{i=1}^{n} \alpha_i^* y_i (x \cdot x_i) + b^* \right) $$

替换内积为核函数。定义一个映射函数 $\phi(x)$，它将原始数据 $x$ 从低维空间映射到一个高维（甚至无穷维）的特征空间。在这个高维空间中，数据可能变得线性可分。计算高维空间的内积 $\phi(x) \cdot \phi(z)$ 的过程可能非常复杂。

核技巧的精髓在于，直接定义一个函数 $K(x, z)$，使得 $K(x, z) = \phi(x) \cdot \phi(z)$。这样，我们无需显式地知道或计算映射 $\phi$，就能得到高维空间的内积。

应用核函数。将对偶问题和决策函数中所有的内积 $x_i \cdot x_j$ 替换为 $K(x_i, x_j)$：

对偶目标变为：
$$ \max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j K(x_i, x_j) $$

决策函数变为：
$$ \text{sign} \left( \sum_{i=1}^{n} \alpha_i^* y_i K(x, x_i) + b^* \right) $$

现在，问题完全转换成了在“核空间”中的线性问题。常用的核函数有：

• 线性核： $K(x, z) = x \cdot z$
• 多项式核： $K(x, z) = (x \cdot z + c)^d$
• 高斯径向基函数核： $K(x, z) = \exp\left(-\gamma \|x - z\|^2\right)$

4. Mercer条件：核函数的合法性判定

并非任意一个二元函数 $K(x, z)$ 都可以作为合法的核函数。它必须对应于某个特征空间中的内积。判断一个函数是否是有效核函数的准则，就是 Mercer条件。

表述 Mercer条件。一个对称函数 $K(x, z)$ 是一个有效核函数的充要条件是：对于任意有限的样本点集 $\{x_1, x_2, ..., x_m\}$，由 $K$ 构造出的 Gram矩阵 $K$ 是半正定的。

理解 Gram矩阵。对于给定的 $m$ 个样本点，其Gram矩阵是一个 $m \times m$ 的方阵，其第 $i$ 行 $j$ 列的元素为 $K(x_i, x_j)$。

理解半正定性。一个实对称矩阵是半正定的，意味着对于任何非零的实向量 $\alpha = [\alpha_1, \alpha_2, ..., \alpha_m]^T$，都有 $\alpha^T K \alpha \geq 0$。计算 $\alpha^T K \alpha$ 的展开式为：

$$ \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j K(x_i, x_j) \geq 0 $$

这个不等式保证了 $K(x, z)$ 所对应的“内积”具有内积的基本性质（如非负的“长度”），从而可以构成一个合法的再生核希尔伯特空间。

应用 Mercer条件。当我们设计或选择一个核函数时，可以通过验证任意数据点集上构造的Gram矩阵是否半正定来确认其有效性。实际上，许多常用的核函数（如高斯核、多项式核）都已经被证明满足 Mercer 条件。这个条件是核函数能够将数据映射到高维空间并保证优化问题凸性的理论基石。