SVM 的拉格朗日乘数法解

### 原始问题（Primal Problem）

我们从 SVM 的优化目标开始：

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

约束条件：

$$
y_i(w^T x_i + b) \ge 1, \quad i=1,\dots,m
$$

找到最大间隔的超平面（即使 $\|w\|$ 尽量小），同时保证每个样本被正确分类。

### 拉格朗日乘子（Lagrange Multipliers）

当约束条件存在时，我们不能直接最小化目标函数。
于是引入拉格朗日乘子 $\alpha_i \ge 0$，建立拉格朗日函数：

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

每个 $\alpha_i$ 对应一个约束条件。
它的含义是：如果某个样本点违反了约束（即离间隔太近或分错），那它的 $\alpha_i$ 就会“发力”惩罚。然后：

1. **原始约束**：
   $$y_i(w^T x_i + b) - 1 \ge 0$$

2. **乘子非负**：
   $$\alpha_i \ge 0$$

3. **互补松弛性（Complementary Slackness）**：
   $$\alpha_i [y_i(w^T x_i + b) - 1] = 0$$

4. **梯度为零（Stationarity）**：
   对 $w$ 和 $b$ 求偏导：
   $$
   \frac{\partial \mathcal{L}}{\partial w} = 0, \quad
   \frac{\partial \mathcal{L}}{\partial b} = 0
   $$

### 求导并消去 $w$ 和 $b$

1️⃣ 对 $w$ 求偏导：

$$
\frac{\partial \mathcal{L}}{\partial w} = w - \sum_i \alpha_i y_i x_i = 0
\Rightarrow w = \sum_i \alpha_i y_i x_i
$$

2️⃣ 对 $b$ 求偏导：

$$
\frac{\partial \mathcal{L}}{\partial b} = -\sum_i \alpha_i y_i = 0
\Rightarrow \sum_i \alpha_i y_i = 0
$$

### 带回去得到**对偶问题（Dual Problem）**

把上面的 $w$ 代入原式中，得到仅关于 $\alpha$ 的优化：

$$
\mathcal{L}(w,b,\alpha)
= \frac{1}{2}\|w\|^2 - \sum_i \alpha_i[y_i(w^T x_i + b) - 1]
$$

化简后得到对偶形式：

$$
\boxed{
\max_{\alpha} \ W(\alpha) =
\sum_i \alpha_i
- \frac{1}{2}\sum_i\sum_j \alpha_i \alpha_j y_i y_j (x_i^T x_j)
}
$$

约束：

$$
\sum_i \alpha_i y_i = 0, \quad \alpha_i \ge 0
$$

### 为什么要用对偶形式？

对偶的好处非常关键：

1. **消掉了 $w, b$**，只剩下 $\alpha$；
2. 训练样本只以**内积 $x_i^T x_j$** 的形式出现，
   ⇒ 可以使用 **核函数（Kernel Trick）** 来扩展到高维空间；
3. 对偶问题是一个**凸二次规划问题（Quadratic Programming）**，有唯一全局最优解。

### 求得最优 $\alpha$ 后恢复分类器

当我们得到最优 $\alpha^*$ 后：

$$
w^* = \sum_i \alpha_i^* y_i x_i
$$

分类函数为：

$$
f(x) = \text{sign}(w^{*T}x + b^*)
$$

其中 $b^*$ 可通过任意一个支持向量（即 $0 < \alpha_i < C$ 的样本）求出：

$$
b^* = y_i - \sum_j \alpha_j^* y_j (x_j^T x_i)
$$

### 🧩 八、支持向量的意义

- 若 $\alpha_i = 0$：该样本不影响边界（离得远）
- 若 $0 < \alpha_i < C$：该样本恰在边界上，是**支持向量**
- 若 $\alpha_i = C$：该样本被误分类或在边界内侧

### ✅ 九、总结成一句话：

> SVM 的对偶问题通过拉格朗日乘子法把约束优化转化为仅依赖 $\alpha$ 的二次规划问题，既保证了凸性（一定能找到全局最优），又能自然地引入核函数扩展非线性问题。