机器学习——支持向量机

发表于 2025-04-16 更新于 2025-06-12 分类于大二下，机器学习阅读次数：

正文

下面我将为你详细解释KKT（Karush-Kuhn-Tucker）条件。KKT条件是优化理论中用于求解带约束非线性规划问题的一组必要条件，广泛应用于支持向量机（SVM）等机器学习算法中。我会使用内联数学公式（如 f(x)）来展示相关表达式。

1. 优化问题的一般形式

我们考虑一个带有约束的优化问题，数学形式如下： - 目标：min_xf(x) - 不等式约束：g_i(x) ≤ 0，其中 i = 1, 2, …, m - 等式约束：h_j(x) = 0，其中 j = 1, 2, …, p

这里： - f(x) 是目标函数，通常是我们希望最小化的函数。 - g_i(x) ≤ 0 表示 m 个不等式约束。 - h_j(x) = 0 表示 p 个等式约束。

KKT条件的目标是找到满足这些约束的局部最优解 x。

2. 拉格朗日函数

为了引入KKT条件，我们首先定义拉格朗日函数： $$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i g_i(\mathbf{x}) + \sum_{j=1}^{p} \mu_j h_j(\mathbf{x})$$

其中： - λ = (λ₁, λ₂, …, λ_m) 是与不等式约束 g_i(x) ≤ 0 对应的拉格朗日乘子。 - μ = (μ₁, μ₂, …, μ_p) 是与等式约束 h_j(x) = 0 对应的拉格朗日乘子。

拉格朗日函数将目标函数和约束条件结合在一起，通过引入乘子 λ_i 和 μ_j 来平衡约束对优化的影响。

3. KKT条件的组成部分

KKT条件由以下四个部分组成，只有当某些正则性条件（如Slater条件）满足时，局部最优解 x 才会同时满足这些条件。以下是具体的KKT条件：

3.1 梯度条件（Stationarity）

拉格朗日函数对 x 的梯度必须为零，即： $$\nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = \nabla f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i \nabla g_i(\mathbf{x}) + \sum_{j=1}^{p} \mu_j \nabla h_j(\mathbf{x}) = 0$$

这意味着在最优解处，目标函数的梯度可以通过约束函数梯度的线性组合来表示。

3.2 原始可行性（Primal Feasibility）

解 x 必须满足原始问题的所有约束： - 不等式约束：g_i(x) ≤ 0，其中 i = 1, 2, …, m - 等式约束：h_j(x) = 0，其中 j = 1, 2, …, p

这确保了解仍在问题的可行域内。

3.3 对偶可行性（Dual Feasibility）

对于不等式约束对应的拉格朗日乘子，必须满足： λ_i ≥ 0，其中 i = 1, 2, …, m

这表明不等式约束的乘子非负，反映了约束对优化方向的影响。

3.4 互补松弛条件（Complementary Slackness）

对于每个不等式约束，乘子与约束函数的乘积必须为零： λ_ig_i(x) = 0，其中 i = 1, 2, …, m

这意味着： - 如果某个约束不“紧”（即 g_i(x) < 0），则对应的乘子 λ_i = 0。 - 如果 λ_i > 0，则该约束必须是“紧”的（即 g_i(x) = 0）。

4. KKT条件的意义

梯度条件：表明最优解处目标函数的改变方向被约束完全平衡。
原始可行性：确保解满足所有约束条件。
对偶可行性：限制拉格朗日乘子的符号，保证优化方向的合理性。
互补松弛条件：揭示哪些约束在最优解处起作用（紧约束），哪些不起作用。

5. KKT条件在SVM中的应用示例

KKT条件在支持向量机（SVM）中尤为重要。SVM的原始优化问题为： - 目标：$$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$$ - 约束：y_i(w ⋅ x_i + b) ≥ 1，其中 i = 1, 2, …, n

将其改写为标准形式的不等式约束：1 − y_i(w ⋅ x_i + b) ≤ 0。

拉格朗日函数为： $$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 + \sum_{i=1}^{n} \alpha_i \left[ 1 - y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \right]$$

应用KKT条件： 1. 梯度条件： - 对 w：$$\nabla_{\mathbf{w}} \mathcal{L} = \mathbf{w} - \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i = 0$$ - 对 b：$$\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^{n} \alpha_i y_i = 0$$ 2. 原始可行性：y_i(w ⋅ x_i + b) ≥ 1 3. 对偶可行性：α_i ≥ 0 4. 互补松弛条件：α_i[y_i(w ⋅ x_i + b) − 1] = 0

这些条件帮助我们识别支持向量（α_i > 0 的点）并求解最优的 w 和 b。

6. 总结

KKT条件是求解带约束优化问题的核心工具，它通过梯度条件、原始可行性、对偶可行性和互补松弛条件，确保了解既是最优的，又满足所有约束。在机器学习中，KKT条件为SVM等算法提供了理论支持，是理解和实现这些模型的关键。

作业

关于支持向量机，推导目标函数的原始问题转换为对偶问题的过程和条件。（使用拉格朗日乘子法）

下面我们将推导支持向量机（SVM）中目标函数从原始问题转换为对偶问题的过程和条件，使用拉格朗日乘子法。我们将一步步展开，确保推导清晰且完整。

1. 原始问题

支持向量机（SVM）的目标是找到一个超平面，能够最大化到最近数据点的间隔。对于线性可分的情况，原始优化问题可以定义为：

目标函数：
$$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$$
约束条件：
y_i(w ⋅ x_i + b) ≥ 1, i = 1, 2, …, n

其中： - w 是超平面的法向量； - b 是超平面的截距； - x_i 是训练样本，y_i ∈ {−1, 1} 是对应的类别标签； - ∥w∥² 表示法向量的平方范数，目标是最小化它以最大化间隔； - 约束条件确保所有样本点被正确分类，并且到超平面的归一化距离至少为 1。

2. 引入拉格朗日乘子法

由于这是一个带不等式约束的优化问题，我们使用拉格朗日乘子法将其转换为无约束形式。引入拉格朗日乘子 α = (α₁, α₂, …, α_n)，其中 α_i ≥ 0，构造拉格朗日函数：

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^{n} \alpha_i \left[ y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1 \right]$$

第一项 $$\frac{1}{2} \|\mathbf{w}\|^2$$ 是原始目标函数；
第二项 $$-\sum_{i=1}^{n} \alpha_i \left[ y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1 \right]$$ 将约束条件引入，由于是 ≥ 不等式，乘子 α_i ≥ 0。

我们的目标是通过拉格朗日函数，将原始问题转换为对偶问题。

3. 转换为对偶问题

对偶问题的核心思想是：先对 w 和 b 求拉格朗日函数的极小值，然后对 α 求极大值。即：

max_α ≥ 0min_w, bℒ(w, b, α)

3.1 对 w 和 b 求偏导

为了找到 ℒ 关于 w 和 b 的极小值，分别求偏导并令其为零：

对 w 求偏导：
$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i = 0$$
解得：
$$\mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i$$
对 b 求偏导：
$$\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^{n} \alpha_i y_i = 0$$
解得：
$$\sum_{i=1}^{n} \alpha_i y_i = 0$$

这两个结果是后续推导的关键。

3.2 代入拉格朗日函数

将 $$\mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i$$ 代入拉格朗日函数，并利用 $$\sum_{i=1}^{n} \alpha_i y_i = 0$$ 简化：

$$\mathcal{L} = \frac{1}{2} \left\| \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i \right\|^2 - \sum_{i=1}^{n} \alpha_i \left[ y_i \left( \left( \sum_{j=1}^{n} \alpha_j y_j \mathbf{x}_j \right) \cdot \mathbf{x}_i + b \right) - 1 \right]$$

计算第一项：
$$\left\| \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i \right\|^2 = \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j)$$
计算第二项中的内积部分：
$$y_i \left( \sum_{j=1}^{n} \alpha_j y_j \mathbf{x}_j \right) \cdot \mathbf{x}_i = y_i \sum_{j=1}^{n} \alpha_j y_j (\mathbf{x}_j \cdot \mathbf{x}_i)$$
所以：
$$\sum_{i=1}^{n} \alpha_i y_i \left( \sum_{j=1}^{n} \alpha_j y_j (\mathbf{x}_j \cdot \mathbf{x}_i) \right) = \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j)$$
考虑 b 项：
$$\sum_{i=1}^{n} \alpha_i y_i b = b \sum_{i=1}^{n} \alpha_i y_i = 0 \quad (\text{因为} \sum_{i=1}^{n} \alpha_i y_i = 0)$$

代入后，拉格朗日函数变为：
$$\mathcal{L} = \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) - \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) + \sum_{i=1}^{n} \alpha_i$$

化简：
$$\mathcal{L} = -\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) + \sum_{i=1}^{n} \alpha_i$$

3.3 对偶优化问题

于是，对偶问题是：
$$\max_{\boldsymbol{\alpha}} \left[ \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 (\mathbf{x}_i \cdot \mathbf{x}_j) \right]$$

约束条件：
$$\sum_{i=1}^{n} \alpha_i y_i = 0$$
α_i ≥ 0, i = 1, 2, …, n

为了与标准优化形式一致，常将其写为最小化问题：
$$\min_{\boldsymbol{\alpha}} \left[ \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) - \sum_{i=1}^{n} \alpha_i \right]$$

约束条件不变：
$$\sum_{i=1}^{n} \alpha_i y_i = 0$$
α_i ≥ 0

4. 转换的条件

原始问题与对偶问题之间的关系由强对偶性保证。在SVM中： - 目标函数 $$\frac{1}{2} \|\mathbf{w}\|^2$$ 是凸函数（二次函数）； - 约束条件 y_i(w ⋅ x_i + b) ≥ 1 是线性不等式； - 对于线性可分数据，Slater条件满足（存在可行解使约束严格成立）。

因此，强对偶性成立，原始问题的最优解可以通过对偶问题求解得到。

此外： - 最优的 α 通过对偶问题求解； - $$\mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i$$； - 对于支持向量（α_i > 0 的样本），y_i(w ⋅ x_i + b) = 1，可据此解出 b。

5. 总结

原始问题：
$$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$$
受约束：y_i(w ⋅ x_i + b) ≥ 1
对偶问题：
$$\max_{\boldsymbol{\alpha}} \left[ \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 (\mathbf{x}_i \cdot \mathbf{x}_j) \right]$$
受约束：$$\sum_{i=1}^{n} \alpha_i y_i = 0$$，α_i ≥ 0
转换条件：
通过拉格朗日乘子法，基于凸优化和强对偶性完成转换。对偶形式不仅便于求解，还为引入核函数奠定了基础。

以上就是SVM目标函数从原始问题到对偶问题的推导过程和条件。

正文