数学视角下的支持向量机（SVM）：优化问题求解

支持向量机（SVM）是机器学习中的经典算法。本文聚焦于SVM中的公式推导，如间隔距离公式的详细推理，以及原问题与对偶问题公式化阐述。深入探讨优化问题，包括构建拉格朗日函数来处理约束优化问题，利用KKT条件求解最优解的过程。同时涉及多项式核函数与高斯核函数公式特性。

间隔距离推理

在支持向量机（SVM）中，正超平面和负超平面的式分别为： $$ \vec{w} \cdot \vec{x} + b = 1 \quad \text{(正超平面)} $$ $$ \vec{w} \cdot \vec{x} + b = -1 \quad \text{(负超平面)} $$ 其中$\vec{w}=(w_1, w_2)$是权重向量，$b$是偏置项，$\vec{x}=(x_1, x_2)$是数据点。

假设$\vec{x_m}$是正超平面上的点，$\vec{x_n}$是负超平面上的点，则有： $$ w_1 x_{1m} + w_2 x_{2m} + b = 1 \quad \text{(1)} $$ $$ w_1 x_{1n} + w_2 x_{2n} + b = -1 \quad \text{(2)} $$

用式(1)减去式(2)，得到： $$ w_1 (x_{1m} - x_{1n}) + w_2 (x_{2m} - x_{2n}) = 2 $$ 写成向量形式： $$ \vec{w} \cdot (\vec{x_m} - \vec{x_n}) = 2 \quad \text{(3)} $$ 考虑决策超平面上的两个点$\vec{x_0}$和$\vec{x_p}$，它们满足决策超平面式$\vec{w} \cdot \vec{x} + b = 0$，即： $$ w_1 x_{10} + w_2 x_{20} + b = 0 $$ $$ w_1 x_{1p} + w_2 x_{2p} + b = 0 $$ 两式相减得到： $$ w_1 (x_{10} - x_{1p}) + w_2 (x_{20} - x_{2p}) = 0 $$ 写成向量形式： $$ \vec{w} \cdot (\vec{x_0} - \vec{x_p}) = 0 \quad \text{(4)} $$ 式(4)表明$\vec{w}$与决策超平面上任意两点的向量差是垂直的。

从式(3)和(4)可知，$\vec{w}$与$(\vec{x_m} - \vec{x_n})$的点积为2，根据向量点积的定义$\vec{a} \cdot \vec{b}=|\vec{a}| \cdot |\vec{b}| \cdot \cos \theta$，这里$\theta$是$\vec{w}$与$(\vec{x_m} - \vec{x_n})$的夹角，我们有： $$ |\vec{x_m} - \vec{x_n}| \cdot \cos \theta \cdot |\vec{w}| = 2 $$ 令$L = |\vec{x_m} - \vec{x_n}| \cdot \cos \theta$，则： $$ L \cdot |\vec{w}| = 2 $$ 解得： $$ L=\frac{2}{|\vec{w}|} $$

这里$L$就是SVM的间隔（margin）距离。

在推导间隔距离时，我们利用了向量点积的几何意义，即$\vec{a} \cdot \vec{b}=|\vec{a}| \cdot |\vec{b}| \cdot \cos \theta$，其中$\theta$是两向量的夹角。通过这个关系，我们将点积转化为向量模长和夹角的关系，从而得出间隔距离的表达式。

对偶等价证明

在线性支持向量机(SVM)中，原问题是找到最小化目标函数的权重向量$w$和偏置$b$：

$$ \min_w f(w) = \frac{1}{2} |w|^2 $$

这里的$|w|^2$代表向量$w$的欧几里得范数平方，即$L_2$范数。目标是最小化决策边界的宽度，以获得更好的泛化能力。该问题受到以下约束：

$$ y_j (w^T x_j + b) - 1 \geq 0 $$

这里$x_j$是第$j$个训练样本，$y_j$是对应的标签，取值为+1或-1，这确保了所有数据点都被正确分类，并且距离决策边界至少有一个单位的距离。

为了处理这个带约束的优化问题，我们构建拉格朗日函数：

$$ L(w, b, \alpha) = f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) $$

这里$\alpha_j \geq 0$是拉格朗日乘子，用于引入原始问题中的约束条件$g_j(w, b) = y_j (w^T x_j + b) - 1 \geq 0$。

接下来，我们定义对偶函数$q(\alpha)$为：

$$ q(\alpha) = \min_{w, b} L(w, b, \alpha) = \min_{w, b} \left( f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) \right) $$

因为$\alpha_j \geq 0$ 和$g_j(w^{*}, b^{*}) \geq 0$ ，我们可以得出：

$$ q(\alpha) = \min_{w, b} \left( f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) \right) \leq f(w^*) - \sum_{j = 1}^n \alpha_j g_j(w^*, b^*) \leq f(w^*) \leq f(w) $$

这意味着对偶函数给出了原问题的一个下界。接下来，我们需要找到一个$\alpha^*$，使得：

$$ q(\alpha) \leq q(\alpha^*) \leq f(w^*) \leq f(w) $$

SVM的原问题和对偶问题可以表述为：

$$ \max_{\alpha} q(\alpha) = \max_{\alpha} \min_{w, b} L(w, b, \alpha) $$

其约束条件为：$ \alpha_i \geq 0 $

并且，当满足弱对偶性时，我们有$q(\alpha^*) \leq f(w^*)$；而当满足强对偶性时，即Slater条件成立时，我们有$q(\alpha^*) = f(w^*)$。Slater条件要求存在一个可行解使得所有不等式约束严格成立，而线性支持向量机是线性可分的，能自动满足Slater条件。

至此，我们有：

$$ f(w) \geq q(\alpha^*) = f(w^*) \geq q(\alpha_i) $$

根据上面这个式子，我们能得到：

$$ q(\alpha^*) \geq q(\alpha_i) $$ $$ f(w^*) \leq f(w) $$

$f(w)$ 找到了最小值（原问题），$q(\alpha)$找到了最大值（对偶问题），原问题和对偶问题的最优解是相等的，即：

$ w^*, b^* $是原问题的解，$\alpha^*$是对偶问题的解，且$f(w^*) = q(\alpha^*)$。

我们可以看到在线性SVM中，当满足特定条件（Slater条件）时，原问题和对偶问题的解是一致的。这为是解决复杂的优化问题的一种有效途径，尤其是在原问题难以直接求解时，可以通过求解对偶问题来间接解决问题。

简单的例子

为了更直观地理解上面原问题和对偶问题的解是相同的，考虑一个简单的优化问题，原问题定义如下：

原问题为： $$ \min_x f(x) = x^2 $$ 约束条件为： $$ x - 1 \geq 0 $$

这个问题的目标是最小化函数$f(x) = x^2$，同时$x$需要满足$x \geq 1$。直观上，我们知道当$x = 1$时，$f(x) = 1$，这是在给定约束下的最小值。

为了验证对偶性，我们构造拉格朗日函数：

$$ q(\alpha) = \min_x L(x, \alpha) = \min_x (x^2 - \alpha(x - 1)) $$

这里$\alpha \geq 0$是拉格朗日乘子，用来引入原问题中的约束条件$x - 1 \geq 0$。通过构造拉格朗日函数，我们将有约束的优化问题转换成了一个无约束的问题。

接下来，我们对$L(x, \alpha)$关于$x$求偏导数，并令其等于0：

$$ \frac{\partial L}{\partial x} = 0 2x - \alpha = 0 $$

解得：

$$ x = \frac{\alpha}{2} $$

将$x = \frac{\alpha}{2}$代入$q(\alpha)$中：

$$ q(\alpha) = - \frac{\alpha^2}{4} + \alpha $$

现在我们已经得到了对偶函数$q(\alpha)$的形式。接下来，我们需要求解对偶问题的最大值$\max_{\alpha} q(\alpha) $

为此，我们对$q(\alpha)$关于$\alpha$求导，并令其等于0：

$$ \frac{dq}{d\alpha} = - \frac{\alpha}{2} + 1 = 0 $$

解得$$ \alpha = 2 $$

将$\alpha = 2$代入$x = \frac{\alpha}{2}$，得到：$$ x = 1 $$

此时，将$\alpha = 2$代入$q(\alpha)$，计算得到：

$$ q(\alpha) = - \frac{2^2}{4} + 2 = 1 $$

通过这个简单例子，我们可以看到，原问题的解$x = 1$，$f(x) = 1$，与对偶问题的解$\alpha = 2$，$q(\alpha) = 1$是等价的。这验证了在满足一定条件下，对偶问题的解与原问题的解是一致的。

通过对偶理论的应用，我们不仅找到了原问题的解，还通过求解对偶问题得到了相同的结果，从而验证了对偶问题解的等价性。

KKT条件求解

SVM满足KKT条件

SVM的原始优化问题是一个凸优化问题。SVM的目标函数 $\frac{1}{2}|w|^2$ 是一个二次函数，它是关于 $w$ 的凸函数。同时，约束条件 $y_i(w \cdot x_i + b) \geq 1$ 是线性的（仿射约束），因此也是凸的。在凸优化问题中，局部最优解就是全局最优解，而且KKT条件是必要且充分的条件。这意味着如果一个点满足KKT条件，那么它就是全局最优解。

目标函数 $\frac{1}{2}|w|^2$ 是连续且可微的，约束条件 $y_i(w \cdot x_i + b) \geq 1$ 也是连续且可微的。这种光滑性保证了梯度的存在性和唯一性，从而让KKT条件中的梯度条件（即对 $w$ 和 $b$ 求偏导数并设置为零）能够有效应用。

在凸优化问题中，KKT条件不仅是必要条件，而且是充分条件。也就是说如果一个点满足KKT条件，那么它一定是全局最优解。对于SVM来说，通过求解KKT条件，我们可以找到最优的 $w^*$ 和 $b^*$，从而确定最佳的分离超平面。

利用KKT条件求解线性支持向量机

原始的SVM优化问题是最小化 $\frac{1}{2}|w|^{2}$，同时满足约束条件 $y_{i}(w\cdot x_{i}+b)\geqslant1$，这里 $i = 1,2,\cdots,N$。

首先，构建拉格朗日函数 $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}\geqslant0$ 是拉格朗日乘子。根据KKT条件，我们有：

$$ \nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0 $$

$$ \nabla_{b}L(w^*,b^*,\alpha^*)=-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}=0 $$

$$ \alpha_{i}^*(y_{i}(w^*\cdot x_{i}+b^*)-1)=0 $$

$$ y_{i}(w^*\cdot x_{i}+b^*)-1\geqslant0 $$

$$ \alpha_{i}^*\geqslant0 $$

这些条件适用于所有 $i = 1,2,\cdots,N$ 的情况。

从 $\nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0$ 可以得出

$$ w^*=\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i} \quad \text{(5)} $$ 由于至少有一个 $\alpha_{j}^*>0$（如果假设 $\alpha_{i}^*=0$，则会导致由式 $\nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0$ 给出的解产生矛盾）。

对于 $b^*$ 的求解，可以通过将 $w^*=\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}$ 代入到 $y_{j}(w^*\cdot x_{j}+b^*)-1 = 0$（考虑到存在 $\alpha_{j}^*>0$ 的情况），并注意到 $y_{j}^{2}=1$，从而得到：

$$ b^*=y_{j}-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x_{i}\cdot x_{j}) \quad \text{(6)} $$

基于上述理论，分离超平面可以表达为：

$$ \sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x\cdot x_{i})+b^*=0 $$

从而分类决策函数则可以写作：

$$ f(x)=\text{sign}(\sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x\cdot x_{i})+b^*) $$

在SVM中，互补松弛条件 $\alpha_i (y_i(w \cdot x_i + b) - 1) = 0$ 表明，如果一个样本点 $x_i$ 不是支持向量（即 $y_i(w \cdot x_i + b) > 1$），那么对应的拉格朗日乘子 $\alpha_i$ 必须为零。相反，如果一个样本点是支持向量（即 $y_i(w \cdot x_i + b) = 1$），那么对应的 $\alpha_i$ 可以是非零的。这种条件确保了只有支持向量对优化问题的解有贡献，从而简化了问题的求解过程。

多项式核函数与高斯核函数

如果现有的问题不是线性可分的，我们可以对现有的数据映射到高维空间，使其在高维空间成为一个线性可分的问题。但直接在高维特征空间中进行计算会非常复杂。由式（5）和式（6）可知，我们其实不需要真的去把数据映射到高维空间，只要知道数据点之间的内积就可以了。核函数的作用就是避免显式地进行高维特征映射，通过在原始特征空间中计算核函数值来间接实现高维特征空间中的内积计算。

高斯核函数是一种常见的核函数，其形式为： $$ K(x, y) = \exp\left(-\gamma |x - y|^2\right) $$

其中 $\gamma$ 是一个正的参数，控制着核函数的宽度。

我们可以对指数函数进行泰勒展开：

$$ \exp(z) = \sum_{k=0}^{\infty} \frac{z^k}{k!} $$

将 $ z = -\gamma |x - y|^2 $ 代入上述公式，得到：

$$ K(x, y) = \exp\left(-\gamma |x - y|^2\right) = \sum_{k=0}^{\infty} \frac{(-\gamma |x - y|^2)^k}{k!} $$

多项式核函数的形式为：

$$ K_{\text{poly}}(x, y) = (x \cdot y + c)^d $$

其中 $ c $ 是常数项，$ d $ 是多项式的次数。

$|x - y|^2$ 可以展开为：

$$ |x - y|^2 = (x - y) \cdot (x - y) = x \cdot x + y \cdot y - 2 x \cdot y $$

将这一表达式代入高斯核函数的泰勒展开式中：

$$ K(x, y) = \sum_{k=0}^{\infty} \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $$

可以看到，每一项 $ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $ 实际上是一个多项式项，也就是说每一项都可以表示为 $ x $ 和 $ y $ 的不同幂次的组合。

如果我们仔细观察每一项，可以发现高斯核函数实际上是通过将不同阶次的多项式核函数进行加权求和得到的。每一项 $ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $ 可以看作是一个 $ k $-阶多项式核函数的加权形式。

例如，当 $ k = 1 $ 时：

$$ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^1}{1!} = -\gamma (x \cdot x + y \cdot y - 2 x \cdot y) $$

当 $ k = 2 $ 时：

$$ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^2}{2!} = \frac{\gamma^2 (x \cdot x + y \cdot y - 2 x \cdot y)^2}{2} $$

这些项都是 $ x $ 和 $ y $ 的多项式形式，并且通过阶乘 $ k! $ 进行加权。

高斯核函数可以被视为在无穷维度上通过不同阶次的多项式核函数进行调和得到的。这种调和使得高斯核函数能够在高维特征空间中捕捉到更复杂的非线性关系。因此，在一半的非线性任务场景中，高斯核函数都是很不错的一个选择。