支持向量机（SVM）的数学推导与核函数应用
题目描述：我们将深入探讨支持向量机（SVM）算法，特别是其核心的数学推导过程以及如何应用核函数处理非线性可分问题。SVM的目标是寻找一个最优超平面，使得两类数据点之间的间隔最大化。当数据线性不可分时，核函数通过将数据映射到高维特征空间，使其在该空间中线性可分。
解题过程：
-
基本概念与问题定义
- 目标：对于一个二分类任务，假设存在一个超平面 \(w^T x + b = 0\) 可以将两类数据分开。SVM的目标是找到那个“最优”超平面，这个“最优”的标准是超平面到两侧最近数据点的距离（即“间隔”）最大。
- 函数间隔：对于一个数据点 \((x_i, y_i)\)（其中 \(y_i \in \{-1, +1\}\)），其到超平面的函数间隔是 \(\hat{\gamma_i} = y_i(w^T x_i + b)\)。函数间隔可以表示分类的正确性和确信度（值越大，分类确信度越高），但其大小会随 \(w\) 和 \(b\) 的等比例缩放而改变，缺乏确定的尺度。
- 几何间隔：几何间隔是函数间隔除以 \(w\) 的范数，即 \(\gamma_i = \frac{\hat{\gamma_i}}{\|w\|} = \frac{y_i(w^T x_i + b)}{\|w\|}\)。几何间隔是点到超平面的实际欧氏距离，它不随 \(w\) 和 \(b\) 的缩放而改变，具有确定的尺度。我们追求最大化的是这个几何间隔。
-
间隔最大化与优化问题建立
- 我们的目标是最大化这个几何间隔。对于整个数据集，我们关心的是所有数据点中最小的那个几何间隔（即“间隔”），即 \(\gamma = \min_{i=1,\dots,m} \gamma_i\)。
- 因此，问题可以表述为：
\[ \begin{align*} & \max_{w, b} \gamma \\ & \text{s.t.} \quad y_i(w^T x_i + b) \geq \gamma \|w\|, \quad i=1,\dots,m \end{align*} \]
* 由于几何间隔依赖于 $\|w\|$，我们通过固定函数间隔来简化问题。我们令最小函数间隔 $\hat{\gamma} = 1$（因为函数间隔可以随意缩放，这个设定是可行的且不影响优化目标）。那么，几何间隔就变成了 $\gamma = \frac{1}{\|w\|}$。
* 最大化 $\frac{1}{\|w\|}$ 等价于最小化 $\frac{1}{2}\|w\|^2$（加上 $\frac{1}{2}$ 和平方是为了后续求导方便）。于是，优化问题重写为一个经典的凸二次规划问题：
\[ \begin{align*} & \min_{w, b} \frac{1}{2} \|w\|^2 \\ & \text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i=1,\dots,m \end{align*} \]
这个公式描述的是数据**线性可分**的情况。
- 处理线性不可分：软间隔SVM
- 现实中数据往往不是严格线性可分的，或者存在噪声。为了允许一些样本被错分，我们引入松弛变量 \(\xi_i \geq 0\)。约束条件放宽为 \(y_i(w^T x_i + b) \geq 1 - \xi_i\)。
- 同时，我们在目标函数中增加一个对松弛变量的惩罚项 \(C\sum_{i=1}^m \xi_i\)，其中 \(C > 0\) 是一个惩罚参数，控制对误分类的容忍度。\(C\) 越大，容忍度越低，模型越倾向于在训练集上做到完全正确分类（可能过拟合）；\(C\) 越小，容忍度越高，模型允许更多的误分类（可能欠拟合）。
- 最终的软间隔SVM优化问题为：
\[ \begin{align*} & \min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^m \xi_i \\ & \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \quad i=1,\dots,m \\ & \qquad \xi_i \geq 0, \quad i=1,\dots,m \end{align*} \]
- 拉格朗日对偶与求解
- 上面得到的问题是一个带约束的优化问题，我们可以通过拉格朗日乘子法将其转化为无约束问题。构建拉格朗日函数：
\[ L(w, b, \xi, \alpha, \mu) = \frac{1}{2}\|w\|^2 + C\sum_{i=1}^m \xi_i - \sum_{i=1}^m \alpha_i [y_i(w^T x_i + b) - 1 + \xi_i] - \sum_{i=1}^m \mu_i \xi_i \]
其中 $\alpha_i \geq 0$ 和 $\mu_i \geq 0$ 是拉格朗日乘子。
* 原问题是 $\min_{w,b,\xi} \max_{\alpha,\mu} L(w,b,\xi,\alpha,\mu)$，根据拉格朗日对偶性，我们可以求解其对偶问题 $\max_{\alpha,\mu} \min_{w,b,\xi} L(w,b,\xi,\alpha,\mu)$，这两个问题在满足KKT条件时具有相同的解。
* 首先，求 $L$ 对 $w, b, \xi$ 的极小值。令偏导数为零：
\[ \begin{align*} \frac{\partial L}{\partial w} = 0 &\Rightarrow w = \sum_{i=1}^m \alpha_i y_i x_i \\ \frac{\partial L}{\partial b} = 0 &\Rightarrow \sum_{i=1}^m \alpha_i y_i = 0 \\ \frac{\partial L}{\partial \xi_i} = 0 &\Rightarrow C - \alpha_i - \mu_i = 0 \end{align*} \]
* 将这三个结果代回拉格朗日函数 $L$，消去 $w, b, \xi$ 和 $\mu_i$，得到对偶问题的目标函数（只关于 $\alpha$）：
\[ \begin{align*} & \max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j \\ & \text{s.t.} \quad \sum_{i=1}^m \alpha_i y_i = 0, \\ & \qquad 0 \leq \alpha_i \leq C, \quad i=1,\dots,m \end{align*} \]
这里 $0 \leq \alpha_i \leq C$ 是由 $C - \alpha_i - \mu_i = 0$ 和 $\mu_i \geq 0$ 推导出的。
* 求解这个对偶问题（通常使用序列最小优化SMO等算法）得到 $\alpha_i$ 的最优解。那些 $\alpha_i > 0$ 对应的样本点 $x_i$ 被称为**支持向量**，它们决定了最终的最优超平面。
* 求出 $\alpha$ 后，可以恢复 $w = \sum_{i=1}^m \alpha_i y_i x_i$。利用任一个满足 $0 < \alpha_j < C$ 的支持向量（此时 $\xi_j = 0$），可以通过 $y_j(w^T x_j + b) = 1$ 求解 $b$：$b = y_j - w^T x_j$。为了数值稳定，通常使用所有满足此条件的支持向量求解 $b$ 后取平均。
- 核函数的引入与应用
- 上述推导都基于样本间的内积 \(x_i^T x_j\)。当数据在原始空间中线性不可分时，我们可以通过一个映射函数 \(\phi\) 将数据映射到一个更高维（甚至是无限维）的特征空间，希望其在新空间中线性可分。
- 在特征空间中，SVM的优化目标变为：
\[ \max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j) \]
* 直接计算高维空间的内积 $\phi(x_i)^T \phi(x_j)$ 可能非常困难（“维数灾难”）。**核函数** 巧妙地解决了这个问题。核函数 $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$ 是一个函数，它能在原始低维空间中直接计算，其结果等于在高维特征空间中的内积。
* 这样，我们无需知道映射 $\phi$ 的具体形式，只需将算法中所有的内积 $x_i^T x_j$ 替换为核函数 $K(x_i, x_j)$ 即可。这被称为**核技巧**。
* 最终的决策函数变为：$f(x) = \text{sign}(\sum_{i=1}^m \alpha_i y_i K(x_i, x) + b)$。
* 常用的核函数包括：
* **线性核**：$K(x_i, x_j) = x_i^T x_j$。这就是线性SVM。
* **多项式核**：$K(x_i, x_j) = (x_i^T x_j + r)^d$。其中 $d$ 是多项式次数。
* **高斯径向基函数核**：$K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$。这是一种强大的核，能将数据映射到无限维空间。参数 $\gamma$ 控制函数的宽度。
* **Sigmoid核**：$K(x_i, x_j) = \tanh(\beta x_i^T x_j + \theta)$。
通过以上步骤，我们完成了从线性可分SVM的数学推导，到处理线性不可分的软间隔SVM，再到利用核技巧解决非线性问题的完整过程。核函数的应用极大地扩展了SVM的适用性。