SVM软间隔与对偶问题

在上一篇文章中，掌柜分别介绍了什么是支持向量机以及如何通过sklearn来完成整个SVM的建模过程；然后还介绍了什么是线性不可分与核函数。在接下来的这节内容中，掌柜将继续介绍SVM中的软间隔与sklearn相关SVM模型的实现，以及SVM中的软间隔与对偶问题。

1 SVM中的软间隔1.1 软间隔定义1.2 最大化软间隔1.3 SVM软间隔示例代码1.4 小结2 拉格朗日乘数法2.1 条件极值2.2 求解条件极值2.3 小结3 对偶性与KKT条件3.1 广义拉格朗日乘数法3.2 原始优化问题3.3 对偶优化问题3.4 KKT条件3.5 计算示例3.6 小结引用

1 SVM中的软间隔

1.1 软间隔定义

上一篇文章 $\phi(x)$ 映射到高维空间之后“线性可分”。为什么后面这个“线性可分”要加上引号呢？这是因为在上一节中其实有一件事没有和各位读者交代，即虽然通过将原始样本映射到高维空间的方法能够很大程度上使得原先线性不可分的样本点线性可分，但是这也并不能够完全保证每个样本点都是线性可分。或者是保守点说，即使完全线性可分了，但也极大可能会出现过拟合的现象。这可能是因为超平面对于异常点过于敏感，或者数据本身的属性所造成，如图1所示。

图 1. SVM软间隔与硬间隔图

在图1中，实线为相应的决策面，黑色方块和黑色圆点分别为两个类别的样本。在图(a)中，通过SVM建模得到的决策面已经完美的将两种类别的样本点进行了区分。但是，如果此时训练样本中加入一个异常点，并且继续用SVM建模求解，那么将会得到图(b)中所示的分类决策面。可以发现，虽然此时决策面也成功的区分开了每一个样本点，但是相较于(a)中的决策面却发生了剧烈的摆动，决策面到支持向量的距离也变得十分狭窄。在SVM中，将图(a)和(b)中决策面到支持向量的间隔称之为硬间隔（Hard Margin），即不允许任何样本出现错分的情况，即使可能导致过拟合。当然，理想情况下期望的应该是图(c)中的这种情况，容许少量样本被错分从而得到一个次优解，而这个容忍的程度则通过目标函数来调节。或者再极端一点就是根本找不到一个超平面能够将样本无误的分开，必须得错分一些样本点。此时图(c)中决策面到支持向量的间隔就被称之为软间隔（Soft Margin）。

1.2 最大化软间隔

${{\xi }_{i}}\ge 0$ ）来使得函数间隔加上松弛变量大于等于1。

y^{(i)} (w^{T} x^{(i)} + b) \geq 1 - ξ_{i} (1)

那么此时的目标函数可以重新改写为如下形式

\begin{aligned} min_{w, b, ξ} \frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{m} ξ_{i} \\ s . t . y^{(i)} (w^{T} x^{(i)} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0, i = 1, 2, . . . m \end{aligned} (2)

$C>0$ $C$ $\lambda$ $C\xi_i$ 的代价，并且为了使得目标函数尽可能小，那么就需要整个惩罚项相对要小。因此，如果使用较大的惩罚系数，那么将会得到较窄的分类间隔，即惩罚力度大允许错分的样本数就会减少；如果使用较小的惩罚系数，则会得到相应较宽的分类间隔，即惩罚力度小允许多的错分样本。

1.3 SVM软间隔示例代码

在1.1节内容中，掌柜大致列出了SVM分类器中常见的几个重要参数，如下所示：


xxxxxxxxxx
6
1
def init(self,
2
    C=1.0, 
3
    kernel='rbf', 
4
    degree=3, 
5
    gamma='scale',
6
    coef0=0.0):

$C$ $(2)$ $C$ $C=1$ $C=1000$ ）。参数kernel表示选择哪种核函数，当kernel='poly'时可以用参数degree来选择多项式的次数。但是通常情况下都会选择效果更好的高斯核（kernel=’rbf’）来作为核函数，因此该参数用得比较少。参数gammacoef0 $r$ 。

图 2. SVM不同惩罚系数下的决策平面

下面掌柜将采用网格搜索来选择一个最佳的SVM分类器对数据集iris进行分类。从上面对sklearn中SVM的API的介绍可知，SVC中需要用到的超参数有5个，其取值这里分别设为：'C': np.arange(1, 10, 5)， 'kernel': ['rbf', 'linear', 'poly']， 'degree': np.arange(1, 10, 2)，'gamma':[ 'scale', 'auto']'coef0': np.arange(-10, 10, 5) $2\times 3\times 5\times 2\times 4=240$ 个备选模型。同时，这里以3折交叉验证进行训练，则一共需要拟合720次模型。完整示例代码参见Book/Chapter09/02_soft_margin_svm.py文件。

模型选择

首先，需要根据列举出的超参数在数据集上根据交叉验证搜索得到最优超参数组合，代码如下：


xxxxxxxxxx
11
1
def model_selection(x_train, y_train):
2
    model = SVC()
3
    paras = {'C': np.arange(1, 10, 5),
4
             'kernel': ['rbf', 'linear', 'poly'],
5
             'degree': np.arange(1, 10, 2),
6
             'gamma': ['scale', 'auto'],
7
             'coef0': np.arange(-10, 10, 5)}
8
    gs = GridSearchCV(model, paras, cv=3, verbose=2, n_jobs=3)
9
    gs.fit(x_train, y_train)
10
    print('best score:', gs.best_score_,'best 
11
                    parameters:', gs.best_params_)

在完成超参数搜索后，便能够得到一组最优的参数组合，如下所示：


xxxxxxxxxx
7
1
Fitting 3 folds for each of 240 candidates, totalling 720 fits
2
[CV] END ..C=1, coef0=-10,degree=1,gamma=scale,kernel=rbf;total time=  0.0s
3
[CV] END ..C=1, coef0=-10,degree=1,gamma=scale,kernel=rbf;total time=  0.0s
4
…
5
[CV] END ...C=6, coef0=5, degree=9,gamma=auto,kernel=rbf; total time= 0.5s
6
best score: 0.986
7
best parameters: {'C': 6, 'coef0': -10, 'degree': 1, 'gamma': 'scale', 'kernel': 'rbf'}

从上面的结果可以看出，当惩罚系数 C=6，以及选取高斯核函数时对应的模型效果最好，准确率为0.986。并且由于最后选取的是高斯核，所以此时coef0和degree这两个参数无效。

训练与预测

在通过网格搜索找到对应的最优模型后，可以再次以完整的训练集对该模型进行训练，代码如下：


xxxxxxxxxx
6
1
def train(x_train, x_test, y_train, y_test):
2
    model = SVC(C=6, kernel='rbf',gamma='scale')
3
    model.fit(x_train, y_train)
4
    score = model.score(x_test, y_test)
5
    y_pred = model.predict(x_test)
6
    print("测试集上的准确率: ", score)# 0.985

可以看出，此时模型在测试集上的准确率为0.985左右。当然，如果有需要的话还可以将训练好模型进行保存以便于后期复用，具体方法将在第7章中进行介绍。

1.4 小结

在本节中，掌柜首先介绍了什么是软间隔及其原理；然后以iris分类数据集为例，再次介绍了在 sklearn中如何用网格搜索来寻找最佳的模型参数。到此，掌柜就介绍完了SVM算法第一阶段的主要内容，可以发现内容不少并且也有相应的难度。在接下来的几节内容中，掌柜将首先和读者朋友们一起回顾一下好久不见的拉格朗日乘数法；然后再介绍求解模型参数需要用到的对偶问题；最后便是SVM的整个优化求解过程。

2 拉格朗日乘数法

在正式介绍SVM算法的求解过程之前，掌柜先来带着各位读者回顾一下拉格朗日乘数法，因为这同时也是第10章中用来对聚类算法求解的工具。可能对于一部分读者来说，使用拉格朗日乘数法已经是很多年前的事情了，其中的细节也自然是慢慢模糊了起来。但是对于拉格朗日乘数法的作用几乎是大家都不会忘记的，那就是用来求解条件极值。既然大多数读者的记忆都停留在这个地方，那么掌柜下面就从条件极值开始来简单的介绍一下拉格朗日乘数法。

$z=xy$ $x+y=1$ 的条件极值。

首先作拉格朗日函数

F (x, y, λ) = x y + λ (x + y - 1) (3)

$(3)$ $F$ 的驻点为

\begin{aligned} F_{x} = y + λ = 0 \\ F_{y} = x + λ = 0 \\ F_{λ} = x + y - 1 = 0 \end{aligned} (4)

$(4)$ $x,y,\lambda$ 分别为

x = \frac{1}{2}; y = \frac{1}{2}; λ = - \frac{1}{2} (5)

$z=xy$ $x+y=1$ $z=0.5\times 0.5=0.25$ 。不过为什么可以通过这样的方法来求得条件极值呢？

2.1 条件极值

在数学优化问题中，拉格朗日乘数法（Lagrange multipliers ）是一种用于求解等式约束条件下局部最小（最大）值的策略。它的基本思想是通过将含约束条件的优化问题转化为无约束条件下的优化问题，以便于得到各个未知变量的梯度，进而求得极值点[1]。因此，一句话总结就是拉格朗日乘数法是一种用来求解条件极值的工具。那么什么又是条件极值呢? 所谓条件极值是指，在一定约束条件下（通常为方程）目标函数的极值就称为条件极值。

$z=f(x,y)$ $z=f(x_1,y_1)$ $\varphi(x,y)=0$ $z=f(x,y)$ $z=f(x,y)$ $\varphi(x,y)=0$ $(x_0,y_0)$ $\varphi(x_0,y_0)=0$ $\varphi(x_1,y_1)\neq0$ 即不满足约束条件）。

图 3. 条件极值图

现在，相信各位读者朋友对条件极值已经有了一个直观上的理解，那么接下来要探究的就是怎么才能求得这个极值。

2.2 求解条件极值

$Z=f(x,y,z,...)$ $\varphi(x,y,...)=0,\phi(x,y,...)=0,...$ 下的条件极值，利用拉格朗日乘数法求解的步骤可以总结为[2]：

1) 作拉格朗日函数

F (x, y, z, . . ., λ, μ, . . .) = f (x, y, z, . . .) + λ φ (x, y, . . .) + μ ϕ (x, y, . . .) + . . . (6)

$\lambda,\mu$ 称为拉格朗日乘子。

$F(x,y,z,...,\lambda,\mu,...)$ 的驻点

$(x_0,y_0,z_0,...,\lambda_0,\mu_0,...)$ 。

\begin{matrix} {\begin{cases} F_{x} = 0 \\ F_{y} = 0 \\ \dots \\ F_{λ} = 0 \\ \dots \end{cases} (7) \end{matrix}

$f(x_0,y_0,z_0,...,)$ 便是可能的条件极值。

2.3 小结

在本节中，掌柜首先介绍通过一个引例介绍了如何通过拉格朗日乘数法来求解条件极值；然后总结了如何用拉格朗日乘数法来求解多元函数的条件极值。对于拉格朗日乘数法，我们在后续介绍聚类算法的求解过程中同样也会用到，因此有必要知道其具体求解步骤。

3 对偶性与KKT条件

在上一节内容中，掌柜介绍了什么是拉格朗日乘数法以及它的作用。同时掌柜还特意说到，拉格朗日乘数法只能用来求解等式约束条件下的极值。但是当约束条件为不等式的时候又该如何进行求解呢？

3.1 广义拉格朗日乘数法

由拉格朗日乘数法可知，对于如下等式条件的约束问题

\begin{aligned} min_{w} f (w) \\ s . t . h_{i} (w) = 0, i = 1, \dots, l . \end{aligned} (8)

$w$ $n$ 维向量。

$(8)$ 可以很明显看出这是一个含有等式约束条件下的条件极值问题，因此用拉格朗日乘数法就能解决。进一步可构造如下拉格朗日函数

L (w, β) = f (w) + \sum_{i = 1}^{l} β_{i} h_{i} (w) (9)

$\beta_i$ 是拉格朗日乘子。最后，通过对式子中所有的参数求偏导，令其为0便可求解得到所有未知变量。

此时，我们接着看如下优化问题

\begin{aligned} min_{w} f (w) \\ s . t . & g_{i} (w) \leq 0, i = 1, \dots, k . \\ h_{i} (w) = 0, i = 1, \dots, l . \end{aligned} (10)

$(10)$ $(8)$ $(10)$ 中多了不等式约束条件。因此，为了解决这类问题需要定义如下所示的广义拉格朗日乘数法（Generalized Lagrangian）[3] ：

L (w, α, β) = f (w) + \sum_{i = 1}^{k} α_{i} g_{i} (w) + \sum_{i = 1}^{l} β_{i} h_{i} (w) (11)

$\alpha_i$ $\beta_i$ 都是拉格朗日乘子，但接下来的求解过程与之前就大相径庭了。

3.2 原始优化问题

$(10)(11)$ 考虑如下定义：

θ_{P} (w) = max_{α, β : α_{i} \geq 0} L (w, α, β) (12)

$(12)$ $\mathcal{L}(w,\alpha ,\beta )$ $\alpha,\beta$ $\alpha,\beta$ $w$ $\theta_{\mathcal{P}}$ $w$ $g_i(w)\leq0$ $h_i(w)=0$ $(12)$ 即等价为

max_{α, β : α_{i} \geq 0} [\sum_{i = 1}^{k} α_{i} g_{i} (w) + \sum_{i = 1}^{l} β_{i} h_{i} (w)] (13)

$\theta_{\mathcal{P}}(w)=f(w)+0$ 。

$g_i$ $h_i$ ${{g}_{i}}(w)>0\$ $\ {{h}_{i}}(w)\ne 0$ $\theta_\mathcal{P}$ ${{g}_{i}}(w)>0$ $\mathcal{L}$ $\alpha_i$ $\mathcal{L}$ ${{h}_{i}}(w)\ne 0$ $\beta$ ${{h}_{i}}$ $\beta$ $\theta_{\mathcal{P}}(w)=\infty$ 。

进一步，结合上述两种情况就能得到下面这个式子：

\begin{matrix} θ_{P} (w) = {\begin{cases} f (w), & if w satisfies primal constraints \\ \infty, & otherwise \end{cases} (14) \end{matrix}

$\theta_{\mathcal{P}}(w)$ $(10)$ 中所要求解的问题。于是便能得到如下定义

p^{*} = min_{w} θ_{P} (w) = min_{w} max_{α, β : α_{i} \geq 0} L (w, α, β) (15)

$(15)$ 其称为原始优化问题（Primal Optimization Problem）。

3.3 对偶优化问题

接下来继续定义

θ_{D} (α, β) = min_{w} L (w, α, β) (16)

$(16)$ $\mathcal{L}(w,\alpha ,\beta )$ $w$ $w$ $\alpha,\beta$ $\theta_{\mathcal{D}}$ $\alpha,\beta$ 的函数。此时便能定义出原问题的对偶问题

d^{*} = max_{α, β : α_{i} \geq 0} θ_{D} (α, β) = max_{α, β : α_{i} \geq 0} min_{w} L (w, α, β) (17)

$(17)$ $(15)$ $(17)$ 的唯一区别就是求解顺序发生了变化，前者是先最大化再最小化；而后者是先最小化然后再最大化。

那么原始问题和对偶问题有什么关系呢？为什么又要用对偶问题？通常情况下两者满足以下关系

d^{*} = max_{α, β : α_{i} \geq 0} min_{w} L (w, α, β) \leq min_{w} max_{α, β : α_{i} \geq 0} L (w, α, β) = p^{*} (18)

证明 $(12)(16)$ $w,\alpha,\beta$ 有

θ_{D} (α, β) = min_{w} L (w, α, β) \leq L (w, α, β) \leq max_{α, β : α_{i} \geq 0} L (w, α, β) = θ_{P} (w) (19)

所以有

θ_{D} (α, β) \leq θ_{P} (w) (20)

$(20)$ 有

max_{α, β : α_{i} \geq 0} θ_{D} (α, β) \leq min_{w} θ_{P} (w) (21)

$(18)$ 中的不等式。在上述过程中，之所以要用对偶问题是因为直接对原始问题进行求解异常困难，所以一般会通过将其转转换为对偶问题进行求解。但就目前来看，两者并不完全等同，其解也就必然不会相同。所以下面就需要进一步介绍KKT条件。

3.4 KKT条件

$f(w)$ $g_i(w)$ $h_i(w)$ $w$ $g_i(w)$ $i$ $g_i(w)<0$ ${{w}^{*}}$ ${{\alpha }^{*}},{{\beta }^{*}}$ ${{w}^{*}},{{\alpha }^{*}},{{\beta }^{*}}$ 满足（Karush-Kuhn-Tucker, KKT）条件[3]：

\frac{\partial}{\partial w_{i}} L (w^{*}, α^{*}, β^{*}) = 0, i = 1, \dots, n (22)

\frac{\partial}{\partial β_{i}} L (w^{*}, α^{*}, β^{*}) = 0, i = 1, \dots, l (23)

α_{i}^{*} g_{i} (w^{*}) = 0, i = 1, \dots, k (24)

g_{i} (w^{*}) \leq 0, i = 1, \dots, k (25)

α_{i}^{*} \geq 0, i = 1, \dots, k (26)

$(24)$ $\alpha _{i}^{*}>0$ $g_i(w)=0$ $\mathcal{L}(w,\alpha ,\beta )$ 中的未知数以及所有等式约束条件拉格朗日乘子的偏导数。

${{w}^{*}},{{\alpha }^{*}},{{\beta }^{*}}$ ${{w}^{*}},{{\alpha }^{*}},{{\beta }^{*}}$ 既是对偶问题的解同样也是原始问题的解。

3.5 计算示例

在介绍完对偶问题的相关求解原理后，下面再通过一个示例来进行说明。试求解以下优化问题：

\begin{array}{l} min_{x} & f (x) = x_{1}^{2} + x_{2}^{2} \\ s . t . & h (x) = x_{1} - x_{2} - 3 = 0 \\ g (x) = {(x_{1} - 3)}^{2} + x_{2}^{2} - 2 \leq 0 \end{array} (27)

$(27)$ 中的优化问题相对简单，所以可以先通过作图来直观的理解一下，如图4所示。

图 4.对偶问题计算示例图

$f(x)$ $h(x)$ $g(x)$ $f(x)$ $h(x)$ $h(x)$ $f(x)$ $g(x)$ $h(x)$ $g(x)$ $f(x)$ 在约束条件下的最小值，所以最优解就是图4中的黑色圆点。进一步，针对这一问题可以得到如下广义拉格朗日函数

L (x, α, β) = (x_{1}^{2} + x_{2}^{2}) + α [{(x_{1} - 3)}^{2} + x_{2}^{2} - 2] + β (x_{1} - x_{2} - 3) (28)

$(15)$ $(28)$ 对应的原始问题为

p^{*} = min_{x} max_{α, β : α \geq 0} L (x, α, β) (29)

$(29)$ 对应的对偶问题为

d^{*} = max_{α, β : α \geq 0} min_{x} L (x, α, β) (30)

$(30)$ 中的顺序来进行求解。

$\mathcal{L}(x,\alpha,\beta)$

$\alpha,\beta$ $L(x,\alpha,\beta)$ $x$ $L(x,\alpha ,\beta )$ 的最小值。故，此时有

\begin{matrix} {\begin{cases} \frac{\partial L}{\partial x_{1}} = 2 x_{1} + α (2 x_{1} - 6) + β = 0 \\ \frac{\partial L}{\partial x_{2}} = 2 x_{2} + 2 α x_{2} - β = 0 \end{cases} \end{matrix}