soft-margin SVM

吴恩达机器学习CS229 支持向量机

在吴恩达CS229机器学习课程中，对加入 $\ell_{1} \text{ norm regularization}$ 的dual problem只给出结果而没有给出过程推导细节。本人对下面dual problem，给出推导细节：

$$\begin{array}{ll} \max _{\alpha} & W(\alpha)=\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} y^{(i)} y^{(j)} \alpha_{i} \alpha_{j}\left\langle x^{(i)}, x^{(j)}\right\rangle \\ \text { s.t. } & 0 \leq \alpha_{i} \leq C, \quad i=1, \ldots, m \\ & \sum_{i=1}^{m} \alpha_{i} y^{(i)}=0 \end{array}$$

首先对于一个training set，一般是线性不可分的，还有一些异常值点outlier。考虑到（1）线性不可分，（2）还有异常值点带来的负面影响，我们允许支持向量机对训练集某些样本点，如 $(x^{(i)}, y^{(i)})$ 的geometric margin有一定误差 $\xi{i}$ 。下图解释下 $\xi{i}$ 的几何意义。

上图中，左上角的⭕️就是一个异常值点outlier，我们想降低这个异常值点给我们的支持向量机带来的负面影响。虚线是理想的decision boundary，能合适地正确分类⭕️和❌。由于受到了异常值点的影响，虚线变到了实线所在位置。如何减少左上角这个异常值带来的的负面影响？对每个点我们加入误差 $\xi_{i}$ ，它代表的意义就是图中红线的长度，就是一个functional margin <= 1的点的functional margin： $\hat{\gamma}^{(i)}$ ，这个 $\hat{\gamma}^{(i)}$ 可以小于1，也可以小于0（被错误分类）。（functional margin和geometric margin的意义见吴恩达课程讲解）。

对于正确分类的点（除了支持向量），其 $\hat{\gamma}^{(i)}>1, \xi_{i} = 0$

对于支持向量，其 $\hat{\gamma}^{(i)}=1, \xi_{i} = 0$

对于异常值点，正确分类了，但是 $\hat{\gamma}^{(i)}<1, 0<\xi_{i}<1$

对于被错误分类的点，其 $\hat{\gamma}^{(i)}<0, \xi_{i}>1$

对每个样本点加入了误差 $\xi_{i}$ 后，我们就可以处理线性不可分的数据和降低异常值带来的负面影响。我们现在有：

$$\begin{array}{rlr} \underset{w, b, \xi}{\operatorname{minimize}} & \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{m} \xi_{i} & \\ \text { subject to } & y^{(i)}\left(w^{T} x^{(i)}+b\right) \geq 1-\xi_{i}, & i=1, \ldots, m, \\ & \xi_{i} \geq 0, & i=1, \ldots, m \end{array}$$

$C$ 控制着 $\frac{1}{2}|w|^{2}$ 和 $\sum{i=1}^{m} \xi{i}$ 的相对权重，一方面我们希望 $\frac{1}{2}|w|^{2}$ 越小越好，对应着支持向量的geometric margin越大越好。另一方面，我们能够容忍一定程度的误差 $\sum{i=1}^{m} \xi{i}$ ，但是这个误差尽管可以存在，但是也是越小越好。就像一个跷跷板，跷跷板的两端需要一个平衡。二者都要兼顾，雨露均沾，不能只顾一个，冷落了另一个。

我们把上面的优化问题，写出标准形式，并应用拉格朗日乘子法：

$$\begin{array}{rlr} \underset{w, b, \xi}{\operatorname{minimize}} & \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{m} \xi_{i} & \\ \text { subject to } & 1-\xi_{i}-y^{(i)}\left(w^{T} x^{(i)}+b\right) \leq 0, & i=1, \ldots, m, \\ & -\xi_{i} \leq 0, & i=1, \ldots, m . \end{array}$$

在不等式约束条件下，我们有拉格朗日函数generalized Lagrangian：

$\mathcal{L}(w, b, \xi, \alpha, \beta)=\frac{1}{2}|w|^{2}+C \sum{i=1}^{m} \xi{i}+\sum{i=1}^{m} \alpha{i}\left(1-\xi{i}-y^{(i)}\left(w^{T} x^{(i)}+b\right)\right)-\sum{i=1}^{m} \beta{i} \xi{i}$

注意，上面这个拉格朗日函数中，参数 $(w, b, \xi)$ 就相当于拉格朗日乘子法里面的 $x$ ， $(\alpha, \beta)$ 相当于拉格朗日乘子 $\lambda$ 。

给出这个问题的primal and dual optimization problems:

$$\begin{array}{rlrlr} \max _{\alpha, \beta: \alpha_{i} \geq 0, \beta_{i} \geq 0} & \theta_{D}(\alpha, \beta) & \text { where } \theta_{D}(\alpha, \beta):=\min _{w, b, \xi} & \mathcal{L}(w, b, \xi, \alpha, \beta), & & \text { (SVM-D) } \\ \min _{w, b, \xi} & \theta_{P}(w, b, \xi) & \text { where } \theta_{P}(w, b, \xi):=\max _{\alpha, \beta: \alpha_{i} \geq 0, \beta_{i} \geq 0} & \mathcal{L}(w, b, \xi, \alpha, \beta) . & & (\text { SVM-P }) \end{array}$$

上面是拉格朗日对偶，不懂需要看CS229支持向量机部分对它的的讲解。

1 Eliminating the primal variables

为了通过对偶dual问题来求解原始primal问题，我们计算 $\theta_{D}(\alpha, \beta)$ ：

$$\theta_{D}(\alpha, \beta)=\min _{w, b, \xi} \quad \mathcal{L}(w, b, \xi, \alpha, \beta)$$

这是一个无约束优化问题 。上面的拉格朗日函数 $\mathcal{L}(w, b, \xi, \alpha, \beta)$ 是可微的differentiable。根据拉格朗日对偶，对于固定的 $(\alpha, \beta)$ ，假设我们找到了 $(\hat{w}, \hat{b}, \hat{\xi})$ 最小化拉格朗日函数，一定有必要条件：拉格朗日函数对参数 $(w, b, \xi)$ 的梯度和偏导数为0向量或0。

$$\begin{aligned} &\nabla_{w} \mathcal{L}(\hat{w}, \hat{b}, \hat{\xi}, \alpha, \beta)=\hat{w}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}=0 \\ &\frac{\partial}{\partial b} \mathcal{L}(\hat{w}, \hat{b}, \hat{\xi}, \alpha, \beta)=-\sum_{i=1}^{m} \alpha_{i} y^{(i)}=0 \\ &\frac{\partial}{\partial \xi_{i}} \mathcal{L}(\hat{w}, \hat{b}, \hat{\xi}, \alpha, \beta)=C-\alpha_{i}-\beta_{i}=0 \end{aligned}$$

把 $-\sum{i=1}^{m} \alpha{i} y^{(i)}=0$ 和 $C-\alpha{i}-\beta{i}=0$ 代回拉格朗日函数：

$\begin{aligned} \theta{D}(\alpha, \beta) &=\mathcal{L}(\hat{w}, \hat{b}, \hat{\xi}) \ &=\frac{1}{2}|\hat{w}|^{2}+C \sum{i=1}^{m} \hat{\xi}{i}+\sum{i=1}^{m} \alpha{i}\left(1-\hat{\xi}{i}-y^{(i)}\left(\hat{w}^{T} x^{(i)}+\hat{b}\right)\right)-\sum{i=1}^{m} \beta{i} \hat{\xi}{i} \ &=\frac{1}{2}|\hat{w}|^{2}+C \sum{i=1}^{m} \hat{\xi}{i}+\sum{i=1}^{m} \alpha{i}\left(1-\hat{\xi}{i}-y^{(i)}\left(\hat{w}^{T} x^{(i)}\right)\right)-\sum{i=1}^{m} \beta{i} \hat{\xi}{i} \ &=\frac{1}{2}|\hat{w}|^{2}+\sum{i=1}^{m} \alpha_{i}\left(1-y^{(i)}\left(\hat{w}^{T} x^{(i)}\right)\right) \end{aligned}$

稍微解释下上面的推导过程，第一个等式就是对固定的 $(\alpha, \beta)$ 找到最佳解 $(\hat{w}, \hat{b}, \hat{\xi})$ ，第二个等式就是generalized Lagrangian拉格朗日函数的定义，第三和第四个等式就是分别把 $-\sum{i=1}^{m} \alpha{i} y^{(i)}=0$ 和 $C-\alpha{i}-\beta{i}=0$ 代入。

再代入 $\hat{w}=\sum{i=1}^{m} \alpha{i} y^{(i)} x^{(i)}$ ，有

$$\begin{aligned} \frac{1}{2}\|\hat{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y^{(i)}\left(\hat{w}^{T} x^{(i)}\right)\right) &=\sum_{i=1}^{m} \alpha_{i}+\frac{1}{2}\|\hat{w}\|^{2}-\hat{w}^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)} \\ &=\sum_{i=1}^{m} \alpha_{i}+\frac{1}{2}\|\hat{w}\|^{2}-\|\hat{w}\|^{2} \\ &=\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2}\|\hat{w}\|^{2} \\ &=\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{i} y^{(i)} y^{(j)}\left\langle x^{(i)}, x^{(j)}\right\rangle \end{aligned}$$

至此，我们通过 $-\sum{i=1}^{m} \alpha{i} y^{(i)}=0$ 和 $C-\alpha{i}-\beta{i}=0$ 和 $\hat{w}=\sum{i=1}^{m} \alpha{i} y^{(i)} x^{(i)}$ ，在拉格朗日函数中用dual variables $(\alpha, \beta)$ 替代了primal variables $(w, b, \xi)$ 。我们的对偶问题化简为：

$$\begin{aligned} \underset{\alpha, \beta}{\operatorname{maximize}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{i} y^{(i)} y^{(j)}\left\langle x^{(i)}, x^{(j)}\right\rangle \\ \text {s.t. } & \alpha_{i} \geq 0, \\ & \beta_{i} \geq 0, \\ & \alpha_{i}+\beta_{i}=C, \\ & \sum_{i=1}^{m} \alpha_{i} y^{(i)}=0 \end{aligned}$$

2. KKT complementary KKT互补条件

满足KKT条件，我们有对偶问题的解等于原始问题的解。

KKT complementarity需要对于任意原始最优解 $\left(w^{*}, b^{*}, \xi^{*}\right)$ 和对偶最优解 $\left(\alpha^{*}, \beta^{*}\right)$ ，有：

$$\begin{aligned} \alpha_{i}^{*}\left(1-\xi_{i}^{*}-y^{(i)}\left(w^{* T} x^{(i)}+b^{*}\right)\right) &=0 \\ \beta_{i}^{*} \xi_{i}^{*} &=0 \end{aligned}$$

对于支持向量，异常值和分类错误的点有 $\alpha_{i}>0$ ，根据KKT complementarity：

$$\alpha_{i}^{* }\left(1-\xi_{i}^{* }-y^{(i)}\left(w^{ * T} x^{(i)}+b^{* }\right)\right)=0$$

有

$$1-\xi_{i}^{ * }-y^{(i)}\left(w^{ * T} x^{(i)}+b^{ * }\right)=0$$ $$1-\xi_{i}^{ * }=y^{(i)}\left(w^{* T} x^{(i)}+b^{* }\right)\leq1$$

因为 $\xi^{*} \geq 0$ 。

而其他大多数样本点的 $\alpha{i}=0$ ，有 $y^{(i)}\left(w^{T} x^{(i)}+b\right) \geq 1-\xi{i}$ （primal constraint）。

最后，因为 $\beta{i}^{*}>0$ 等价于 $\alpha{i}^{*}<C\left(\text { since } \alpha^{*}+\beta_{i}^{*}=C\right)$ 。我们可以将KKT条件总结如下:

$$\begin{array}{r} \alpha_{i}^{*}=0 \Rightarrow y^{(i)}\left(w^{* T} x^{(i)}+b^{*}\right) \geq 1 \\ 0<\alpha_{i}^{*}<C \Rightarrow y^{(i)}\left(w^{* T} x^{(i)}+b^{*}\right)=1 \\ \alpha_{i}^{*}=C \Rightarrow y^{(i)}\left(w^{* T} x^{(i)}+b^{*}\right) \leq 1 \end{array}$$

3. 化简

我们观察到两个约束条件： $\beta{i} \geq 0 \quad \alpha{i}+\beta_{i}=C$

等价于单一约束条件： $\alpha_{i} \leq C$

我们解决如下优化问题：

$$\begin{array}{ll} \underset{\alpha, \beta}{\operatorname{maximize}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{i} y^{(i)} y^{(j)}\left\langle x^{(i)}, x^{(j)}\right\rangle \\ \text { subject to } & 0 \leq \alpha_{i} \leq C, \\ & \sum_{i=1}^{m} \alpha_{i} y^{(i)}=0 \end{array}$$

然后设 $\beta{i}=C-\alpha{i}$ ，那么 $(\alpha, \beta)$ 将是上述对偶问题的最优解。以上对偶优化问题就是CS229课程中吴恩达推导出的加入 $$ 后的最终形式，只是比没加入 $\ell{1} \text{ norm regularization}$ 之前多出一个 $\alpha{i} \leq C$ 。