机器学习——支持向量机

正文

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

---

1. 优化问题的一般形式

我们考虑一个带有约束的优化问题，数学形式如下：

• 目标：$\min_{\mathbf{x}} f(\mathbf{x})$
• 不等式约束：$g_i(\mathbf{x}) \leq 0$，其中 $i = 1, 2, \dots, m$
• 等式约束：$h_j(\mathbf{x}) = 0$，其中 $j = 1, 2, \dots, p$

这里：

• $f(\mathbf{x})$ 是目标函数，通常是我们希望最小化的函数。
• $g_i(\mathbf{x}) \leq 0$ 表示 $m$ 个不等式约束。
• $h_j(\mathbf{x}) = 0$ 表示 $p$ 个等式约束。

KKT条件的目标是找到满足这些约束的局部最优解 $\mathbf{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})$$

其中：

• $\boldsymbol{\lambda} = (\lambda_1, \lambda_2, \dots, \lambda_m)$ 是与不等式约束 $g_i(\mathbf{x}) \leq 0$ 对应的拉格朗日乘子。
• $\boldsymbol{\mu} = (\mu_1, \mu_2, \dots, \mu_p)$ 是与等式约束 $h_j(\mathbf{x}) = 0$ 对应的拉格朗日乘子。

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

---

3. KKT条件的组成部分

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

3.1 梯度条件（Stationarity）

拉格朗日函数对 $\mathbf{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）

解 $\mathbf{x}$ 必须满足原始问题的所有约束：

• 不等式约束：$g_i(\mathbf{x}) \leq 0$，其中 $i = 1, 2, \dots, m$
• 等式约束：$h_j(\mathbf{x}) = 0$，其中 $j = 1, 2, \dots, p$

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

3.3 对偶可行性（Dual Feasibility）

对于不等式约束对应的拉格朗日乘子，必须满足：

$$\lambda_i \geq 0$$，其中 $$i = 1, 2, \dots, m$$

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

3.4 互补松弛条件（Complementary Slackness）

对于每个不等式约束，乘子与约束函数的乘积必须为零：

$$\lambda_i g_i(\mathbf{x}) = 0$$，其中 $$i = 1, 2, \dots, m$$

这意味着：

• 如果某个约束不“紧”（即 $g_i(\mathbf{x}) < 0$），则对应的乘子 $\lambda_i = 0$。
• 如果 $\lambda_i > 0$，则该约束必须是“紧”的（即 $g_i(\mathbf{x}) = 0$）。

---

4. KKT条件的意义

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

---

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

KKT条件在支持向量机（SVM）中尤为重要。SVM的原始优化问题为：

• 目标：$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$
• 约束：$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1$，其中 $i = 1, 2, \dots, n$

将其改写为标准形式的不等式约束：$1 - y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \leq 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. 梯度条件：
   • 对 $\mathbf{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 (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1$
3. 对偶可行性：$\alpha_i \geq 0$
4. 互补松弛条件：$\alpha_i \left[ y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1 \right] = 0$

这些条件帮助我们识别支持向量（$\alpha_i > 0$ 的点）并求解最优的 $\mathbf{w}$ 和 $b$。

---

6. 总结

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

作业

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

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

---

1. 原始问题

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

• 目标函数：

  $$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$$

• 约束条件：

  $$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad i = 1, 2, \dots, n$$

其中：

• $\mathbf{w}$ 是超平面的法向量；
• $b$ 是超平面的截距；
• $\mathbf{x}_i$ 是训练样本，$y_i \in \{-1, 1\}$ 是对应的类别标签；
• $\|\mathbf{w}\|^2$ 表示法向量的平方范数，目标是最小化它以最大化间隔；
• 约束条件确保所有样本点被正确分类，并且到超平面的归一化距离至少为 1。

---

2. 引入拉格朗日乘子法

由于这是一个带不等式约束的优化问题，我们使用拉格朗日乘子法将其转换为无约束形式。引入拉格朗日乘子 $\boldsymbol{\alpha} = (\alpha_1, \alpha_2, \dots, \alpha_n)$，其中 $\alpha_i \geq 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]$ 将约束条件引入，由于是 $\geq$ 不等式，乘子 $\alpha_i \geq 0$。

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

---

3. 转换为对偶问题

对偶问题的核心思想是：先对 $\mathbf{w}$ 和 $b$ 求拉格朗日函数的极小值，然后对 $\boldsymbol{\alpha}$ 求极大值。即：

$$\max_{\boldsymbol{\alpha} \geq 0} \min_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})$$

3.1 对 $\mathbf{w}$ 和 $b$ 求偏导

为了找到 $\mathcal{L}$ 关于 $\mathbf{w}$ 和 $b$ 的极小值，分别求偏导并令其为零：

• 对 $\mathbf{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$$ $$\alpha_i \geq 0, \quad i = 1, 2, \dots, 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$$ $$\alpha_i \geq 0$$

---

4. 转换的条件

原始问题与对偶问题之间的关系由强对偶性保证。在SVM中：

• 目标函数 $\frac{1}{2} \|\mathbf{w}\|^2$ 是凸函数（二次函数）；
• 约束条件 $y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1$ 是线性不等式；
• 对于线性可分数据，Slater条件满足（存在可行解使约束严格成立）。

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

此外：

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

---

5. 总结

• 原始问题：

  $$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$$

  受约束：$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 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$，$\alpha_i \geq 0$

• 转换条件：
  通过拉格朗日乘子法，基于凸优化和强对偶性完成转换。对偶形式不仅便于求解，还为引入核函数奠定了基础。

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

2.已知训练数据集中正例点x1=(2,3)，x2=(3,3)，x3=(3,2)，负例点x4=(1,2)， x5=(2,1)，x6=(3,1)，训练线性SVM分类器。求最大间隔分类超平面和分类决策函数，并画出分类超平面、间隔边界以及支持向量。