【机器学习】支持向量机（上）

支持向量机（上）

一、导言

支持向量机作为传统机器学习算法中的霸主，其背后的数学知识是相当复杂且精密的。对于每个学习机器学习的同学而言，理解并掌握支持向量机的思路对于认识和学习其他算法也会起到非常巨大的推动作用。遗憾的是，鲜有博客能真正说清楚它的美妙之处，这也包括一些高校的老师。要么卡在 KKT 条件，要么说不清什么是对偶问题。为此，我花了几周的时间来对这些知识进行梳理和整合，在参考大量文献和相关博文后，最终完成了本文。由于这一章的内容过多，因此将该文分为上下两节。第一节主要是讲解支持向量机的数学推导过程，第二节则是对支持向量机涉及到的核函数、软间隔等问题进行讨论分析。

本文将通过严密的数学推导，以最简单易懂的例子来对支持向量机进行剖析，带领大家完整细致地理解传统机器学习算法中最厉害的算法——支持向量机。

二、何为支持向量机

支持向量机（Support Vector Machine, SVM）是一类按监督学习方式对数据进行二元分类的广义线性分类器，其决策边界是对学习样本求解的最大边距超平面。假设存在样本集 $D=\{({\text{x}}_1,y_1),({\text{x}}_2,y_2),\dots ,({\text{x}}_n,y_n)\},{\text{x}}_i=[x_1^{(i)},x_2^{(i)},\dots ,x_m^{(i)}{]}^T$，其中 $n$ 表示数据集规格，$m$ 表示数据集的特征维度。则支持向量机的核心思想就是基于训练集 𝐷 在样本空间中寻找一个划分超平面 $\psi$，使得 $\psi$ 能将不同类别的样本分开。但能将训练样本分开的超平面可能有很多，如下图所示，哪一个才是我们最需要的昵?

直观上看，应该是位于两类训练样本 “正中间” 的划分超平面（即上图中的绿色线条），因为该划分超平面对训练样本局部扰动的 “容忍性” 最好。例如，由于训练集的局限性或噪声的因素，训练集之外的样本可能比该图中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而绿色的划分超平面受影响最小。换言之，这个划分超平面所产生的分类结果是最稳定的，对未见示例的泛化能力最强。

那要如何才能确定一个分类效果最好的划分超平面呢？
Vapnik 提出了一种方法：对每个可能的超平面，将它进行平移，直到它与空间中的样本向量相交（我们称这两个向量为支持向量）。之后我们计算支持向量到该划分超平面的距离 $d$，分类效果最好的划分超平面应该使 $d$ 最大。

三、点到平面的距离计算

距离 $d$ 的计算本质上就是点到平面的距离计算。下面我们先讨论如何计算点到平面的距离。

假设存在一个平面 $\psi :{\text{w}}^T\text{x}+b=0$，则 $\text{w}=[w_1,w_2,\dots ,w_m{]}^T$ 为该平面的法向量，$b$ 为位移项（决定了超平面与原点之间的距离）。
为什么说 $\text{w}$ 是该平面的法向量？假设该平面中存在两个数据点 ${\text{x}}_1=[x_1^{(1)},x_2^{(1)},\dots ,x_m^{(1)}{]}^T,{\text{x}}_2=[x_1^{(2)},x_2^{(2)},\dots ,x_m^{(2)}{]}^T$，则有：

$$\begin{array}{r}\{\begin{array}{l}{\text{w}}^T{\text{x}}_1+b=0\\ {\text{w}}^T{\text{x}}_2+b=0\end{array}\end{array}$$

由于 $\text{w}$ 为向量， $x_1-x_2$ 可表示该平面中的任意向量，且 $({\text{w}}^T{\text{x}}_1+b)-({\text{w}}^T{\text{x}}_2+b)={\text{w}}^T({\text{x}}_1-{\text{x}}_2)=0$。因此说 $w$ 是该平面的法向量。
现假设我们要计算某个样本点 $x$ 到平面 $\psi$ 的距离 $dist(\text{x},\psi )$ ，此时，可过点 $x$ 向平面 $\psi$ 作垂线（交点为 $\text{p}$），则 $dist(\text{x},\psi )$ 。也就是说，距离 $dist(\text{x},\psi )$ 就等于垂线段 $\text{xp}$ 的长度。

但要如何计算这个长度呢？我们知道，对于欧氏空间中的任意向量 $\alpha$ ，若将该向量与某个方向的单位方向向量进行点乘（内积），就能得到该向量在指定方向上的长度。例：存在向量 $\alpha =(3,4,5)$ ，则向量 $\alpha$ 在方向 $n=(1,1,1)$ 上的长度为：

∣ α → ⋅ n 0 → ∣ = ∣ α → ⋅ n → ∣ n → ∣ ∣ = ∣ ( 3 , 4 , 5 ) ⋅ ( 1 , 1 , 1 ) ∣ ( 1 , 1 , 1 ) ∣ ∣ = ∣ 3 × 1 + 4 × 1 + 5 × 1 ∣ 3 = 12 3 = 4 3 \left|\overrightarrow{\alpha}·\overrightarrow{n_0}\right| =\left|\overrightarrow{\alpha}·\frac{\overrightarrow{n}}{\left|\overrightarrow{n}\right|}\right| =\left|(3,4,5)·\frac{(1,1,1)}{\left|(1,1,1)\right|}\right| =\frac{\left| 3\times1+4\times1+5\times1 \right|}{\sqrt{3}} =\frac{12}{\sqrt{3}} =4\sqrt{3} ​α ⋅n0​ ​ ​= ​α ⋅ ​n ​n ​ ​= ​(3,4,5)⋅∣(1,1,1)∣(1,1,1)​ ​=3 ​∣3×1+4×1+5×1∣​=3 ​12​=43 ​

由于平面 $\psi$ 的法向量 $w$ 正是其垂线，因此，若在平面 $\psi$ 中任选一个数据点 ${\text{x}}^{{}^{\prime }}$，并基于这两点构建向量 $\alpha =\text{x}-{\text{x}}^{{}^{\prime }}$，则点 $\text{x}$ 到指定平面 $\psi$ 的距离为：

d i s t ( x , ψ ) = ∣ α → ⋅ w 0 ∣ = ∣ ( x − x ′ ) ⋅ w ∣ w ∣ ∣ = ∣ w T ∣ w ∣ ( x − x ′ ) ∣ = ∣ w T x − w T x ′ ∣ ∣ w ∣ = 1 ∣ w ∣ ∣ ( w T x + b ) ∣ dist(\text{x},\psi) = \left| \overrightarrow{\alpha}·w_0 \right| = \left| \left(\text{x}-\text{x}^{'}\right)·\frac{w}{|w|} \right| = \left| \frac{w^T}{|w|}\left(\text{x}-\text{x}^{'}\right) \right| = \frac{|w^T\text{x}-w^T\text{x}^{'}|}{|w|} = \frac{1}{|w|}\left| \left( w^T\text{x}+b \right) \right| dist(x,ψ)= ​α ⋅w0​ ​= ​(x−x′)⋅∣w∣w​ ​= ​∣w∣wT​(x−x′) ​=∣w∣∣wTx−wTx′∣​=∣w∣1​ ​(wTx+b) ​

上式含有绝对值，这会给后续的计算带来麻烦，因此需要想办法处理。

注意到一件事：对于某个决策方程（即划分超平面的方程）：$y(\text{x})=w^T\Phi (\text{x})+b$（ $\Phi (\text{x})$ 是对输入数据 $\text{x}$ 做了某种变换，后面会解释），当把某个样本点 ${\text{x}}_i$ 带入时， $y(\text{x})$ 总有以下 3 类取值：

$$\begin{array}{r}\{\begin{array}{l}y(\text{x})<0,样本点在划分超平面之下（视为负例）\\ y(\text{x})=0,样本点在划分超平面之内\\ y(\text{x})>0,样本点在划分超平面之上（视为正例）\end{array}\end{array}$$

因此，对于样本集 $D=\{({\text{x}}_1,y_1),({\text{x}}_2,y_2),\dots ,({\text{x}}_n,y_n)\}$ 而言，若规定数据标签 y i ∈ { − 1 , 1 } y_i \in \{−1,1\} yi​∈{−1,1} 。则可将样本点 ${\text{x}}_i$ 到指定划分超平面 $\psi$ 的距离 $d$ 表示为：

$$d=y_i\times \left(\alpha \cdot w_0\right)=y_i\times \left(\left({\text{x}}_i-{\text{x}}^{{}^{\prime }}\right)\cdot \frac{w}{|w|}\right)=y_i\times \left(\frac{w^T}{|w|}\left({\text{x}}_i-{\text{x}}^{{}^{\prime }}\right)\right)=y_i\times \left(\frac{w^T{\text{x}}_i-w^T{\text{x}}^{{}^{\prime }}}{|w|}\right)=\frac{y_i}{|w|}\left(w^T{\text{x}}_i+b\right)$$

上式通过额外添加绝对值为 1 的标签值 $y_i$ 来巧妙地消除了原始 $dist(\text{x},\psi )$ 为负的情况，从而将绝对值去掉（此时，负例的标签为 $-1$；正例的标签为 $+1$）。根据这个距离公式，我们可以进一步构建目标函数。

四、构建目标函数（支持向量机的基本型推导）

前面说到：在给定数据集中，支持向量到划分超平面的距离越大，这样的超平面效果越好。这里有两个关键点：

1. 支持向量到划分超平面的距离（所有样本点中距离划分超平面最近的数据点），即 $mi{n}_{({\text{x}}_i,y_i)\in D}\frac{y_i}{|w|}\left(w^T{\text{x}}_i+b\right)$；
2. 该距离尽可能远，即 $ma{x}_{w,b}\left\{mi{n}_{({\text{x}}_i,y_i)\in D}\frac{y_i}{|w|}\left(w^T{\text{x}}_i+b\right)\right\}$。

这便是我们所需要优化的目标函数，由于该式过于复杂，接下来我们讨论如何对其进行进一步化简。

若假设超平面 $\psi$ 能将训练样本正确分类，即对于任意 $({\text{x}}_i,y_i)\in D$，若 $y_i=-1$，则有 $w^T{\text{x}}_i+b<0$；若 $y_i=+1$，则有 $w^T{\text{x}}_i+b>0$。则总存在放缩变换 $v=\xi w$ ，使下式成立：

$$\begin{array}{r}\{\begin{array}{l}{v}^T{\text{x}}_i+b\le -1,y_i=-1\\ v^T{\text{x}}_i+b\ge 1,y_i=1\end{array}\end{array}$$

显然，使上式等号成立的正是支持向量，此时取 $w=v$ ，则支持向量到划分超平面的距离为：

$$mi{n}_{({\text{x}}_i,y_i)\in D}\frac{y_i}{|w|}\left(w^T{\text{x}}_i+b\right)=\frac{1}{|w|}$$

所以，两个异类支持向量到超平面的距离之和 $d$ 为 $\frac{2}{|w|}$，它也被称为 “间隔”。
于是，欲找到具有 “最大间隔(maximum margin)” 的划分超平面，也就是要找能使 $\frac{2}{|w|}$ 最大的 𝑤, 𝑏 ，即（𝑠.𝑡. 表示 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ，表示 “受限于” 的意思）：

$$\begin{array}{rl}& ma{x}_{w,b}\frac{2}{|w|}\\ & s.t.y_i\left(w^T{\text{x}}_i+b\right)\ge 1i=1,2,\dots ,n\end{array}$$

不难看出，最大化间隔问题其实就是一个凸二次规划问题。
所有机器学习算法的设计都无外乎一种固定模式：问题分析，问题抽象，提出数学问题，构建目标函数，执行最优化。在构建目标函数时，我们通常希望将其描述为一个求解最小值的方程，支持向量机也是如此。显然，最大化间隔 $\frac{2}{|w|}$，仅需要最大化 $|w{|}^{-1}$，这
等价于最小化 $|w|$ 。于是上式可写为（对于原始式子中的常系数，可以任意置换而不影响极值点）：

$$\begin{array}{rl}& mi{n}_{w,b}\frac{1}{2}|w|\\ & s.t.y_i\left(w^T{\text{x}}_i+b\right)\ge 1i=1,2,\dots ,n\end{array}$$

为消去式中的求模运算，可将其进一步改写为：

$$\begin{array}{rl}& mi{n}_{w,b}\frac{1}{2}{w}^2\\ & s.t.y_i\left(w^T{\text{x}}_i+b\right)\ge 1i=1,2,\dots ,n\end{array}$$

这便是支持向量机的基本型。
下面我们讨论如何求解该目标函数。

五、利用 KKT 条件对目标函数进行转换

对于最优化问题，可进行一个简单分类：

• 无约束优化问题：直接求导、最速下降法、共轭梯度法、牛顿法等。
• 等式约束优化问题：消元法、拉格朗日(Lagrange)乘数法。
• 不等式约束优化问题：KKT条件。

1、拉格朗日乘数法的引入

由于目标函数存在约束条件：$y_i\left(w^T{\text{x}}_i+b\ge 1\right)$，这不免使我们想到 消元法 或 拉格朗日乘数法。消元法比较简单不再赘述，这里主要提一下拉格朗日乘数法，因为后面提到的 KKT 条件正是对拉格朗日乘子法的一种泛化。拉格朗日乘数法（以数学家约瑟夫·路易斯·拉格朗日命名）是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有 $n$ 个变量与 $k$ 个约束条件的最优化问题转换为一个有 $n+k$ 个变量的方程组的极值问题，其变量不受任何约束。这种方法引入了一种新的标量未知数，即拉格朗日乘数：约束方程梯度（gradient）的线性组合里每个向量的系数（简单来说：这个系数是为了强制要求所有的不等式条件被满足）。

若给定二元函数 $z=f(x,y)$ 和约束条件 $\varphi (x,y)=0$，为寻找 $z=f(x,y)$ 在约束条件下的极值点，先做拉格朗日函数：

$$F(x,y,\lambda )=f(x,y)+\lambda \varphi (x,y)$$

其中 $\lambda$ 为参数（$\lambda \ne 0$ ，为拉格朗日乘数）。接下来令 $F(x,y,\lambda )$ 分别对 $x$、$y$ 和 $\lambda$ 求一阶偏导数，并取偏导为零，即：

$$\begin{array}{r}\{\begin{array}{l}{F}_x{}^{\prime }(x,y,\lambda )=f_x^{{}^{\prime }}(x,y)+\lambda {\varphi }_x^{{}^{\prime }}(x,y)=0\\ F_y{}^{\prime }(x,y,\lambda )=f_y^{{}^{\prime }}(x,y)+\lambda {\varphi }_y^{{}^{\prime }}(x,y)=0\\ F_{\lambda }{}^{\prime }(x,y,\lambda )={\varphi }_x(x,y)=0\end{array}\end{array}$$

得到：

$$\begin{array}{r}\{\begin{array}{l}{f}_x^{{}^{\prime }}(x,y)=-\lambda {\varphi }_x^{{}^{\prime }}(x,y)\\ f_y^{{}^{\prime }}(x,y)=-\lambda {\varphi }_y^{{}^{\prime }}(x,y)\\ {\varphi }_x(x,y)=0\end{array}\end{array}$$

由上述方程组可解出 $x$、$y$ 和 $\lambda$，如此求得的 $x,y$ ，就是函数 $z=f(x,y)$ 在约束条件 $\varphi (x,y)=0$ 下可能的极值点（可将函数 $z=f(\cdot )$ 推广至任意维度）。若这样的点只有一个，则由实际问题可直接认为此点即为所求。

需要注意的是，消元法或拉格朗日乘数法，其求解目标方程的约束条件通常是等式，不等式情况在低维情况下可以计算（比如二维时，最优解通常在图形的边缘处），但是维度一旦变高，就非常难解了。而这里的目标函数的约束条件为 $y_i\left(w^T{\text{x}}_i+b\ge 1\right)$ ，是一个不等式，并且在讨论通解时我们肯定要视目标数据集为高维数据。因此对 SVM 的标准型求解需要用到 KKT 条件（由发现它的三个科学家的名字命名：Karush-Kuhn-Tucker）来进行求解。

2、KKT 条件的引入

为便于讲解，设目标函数为 $f(x_1,x_2)$ （现实情况下该函数可为任意维度），不等式约束为 $g(x_1,x_2)$ ，有的情况下还存在等式约束 $h(x_1,x_2)$ 。此时，带约束的优化问题描述如下：

$$\begin{array}{rl}& minf(x_1,x_2)\\ & s.t.h(x_1,x_2)=0\\ & g(x_1,x_2)\le 0\end{array}$$

在运用 KKT 条件求解时，上式中的等式约束 $h(x_1,x_2)$ 与在拉格朗日数乘法中的处理方式一致，为便于讲解，下面假设仅含无等式约束，即问题为：

$$\begin{array}{rl}& minf(x_1,x_2)\\ & s.t.g(x_1,x_2)\le 0\end{array}$$

实际上，不等式约束 $g(x_1,x_2)$ 所围成区域即为目标函数的可行区（取值范围）。由于 $g(x_1,x_2)$ 有可能是非线性函数，此时可行区不能确保是凸集；即使是凸集，该凸集也有可能含无数个极点，故此时不能像传统方法那样迭代每个极点以获得极值。注意到可行区与目标函数的定义域位置关系主要有以下两种情形：

情形一：目标函数（ $y=f(x_1,x_2)=x_1^2+x_2^2-10$ ）的全局最小点在可行区内，如下图所示（在 $x_{1}O{x}_2$ 平面上的投影）：

红色环线代表目标函数的等值线，灰色空间代表了不等式 $x_1+x_2\le 2$ 约束限定的可行区，这种情形直接用梯度法求解目标函数即可获得极值（极值点为 $(0,0)$ ，取到极小值 $-10$）。此时，约束条件不起任何作用（KKT条件不是专门针对这种情形）。

情形二：目标函数的全局最小点不在可行区内，如下图所示（在 𝑥1𝑂𝑥2 面上的投影） ：

观察图像可以发现，目标函数等值线与约束边界相切时得到极值点（极值点为 $(-\sqrt{2},-\sqrt{2})$ ，取得极小值 $-6$ ）。与等式约束条件一样，此处目标函数 $f(x_1,x_2)$ 的梯度与边界函数 $g(x_1,x_2)$ 梯度有如下关系（梯度 $grad$ 通常用 $\nabla$ 来表示）：

$$\nabla f(x_1,x_2)=-\lambda \nabla (x_1,x_2)\lambda \ge 0$$

实际上，目标函数 $f(x_1,x_2)$ 梯度指向函数增大方向，即指向可行区内；而在可行区内，约束函数 $g(x_1,x_2)$ 的梯度指向可行区域外。因此，在这情况下（求目标函数最小值时），$f(x_1,x_2)$ 的梯度与约束函数 $g(x_1,x_2)$ 的梯度方向正好相反。但如果不等式约束是 $x_1+x_2\ge -2\sqrt{2}$ ，则两个梯度朝向一个方向。这样的情况在求目标函数的最大值时则正好相反。基于此，为限定梯度系数 $\lambda$ 在公式里恒正，我们规定：对目标函数求极小值时，总是使不等式约束为小于等于（ ≤ ）；对目标函数求极大值时，则让不等式约束为大于等于（ ≥ ）。若以仅含一个不等式约束的情形为例，最小化和最大化的优化问题可分别整理成如下形式：

极小值
$$\begin{array}{rl}& minf(X)\\ & s.t.g(X)\le 0\end{array}$$

极大值
$$\begin{array}{rl}& minf(X)\\ & s.t.g(X)\ge 0\end{array}$$

3、松弛互补条件的引入

前面演示的是等值线与一个条件边界相切的情形（目标函数与可行区相交于一点）。当约束条件具有多个时，该点可能是多个约束边界的交点，如下图所示。

该图中，蓝色点代表极值点，它是 $g_1(x_1,x_2)\le 0,g_2(x_1,x_2)\le 0,g_3(x_1,x_2)\ge 0$ 三个约束条件边界的交点，由于最值必定出现在边界上，所以不等式约束情形可以转化为等式约束的情形，则由拉格朗日乘数法表达式有：

$$\nabla f(x_1,x_2)=-\sum _{i=1}^m{\lambda }_i\nabla g_i(x_1,x_2)$$

上式中，$m$ 表示不等式约束条件的个数；从前面的等式约束条件分析可知，该式代表了 $n$ 个等式（这里的 $n$ 为原函数 $f(x_1,x_2)$ 的维度，此处为 2），而我们目标是求出 $n+m$ 个变量，即变量 { x 1 , x 2 , … , x n ; λ 1 , λ 2 , … , λ m } → { x 1 ∗ , x 2 ∗ ; λ 1 , λ 2 , λ 3 } \{ x_1,x_2,…,x_n; \lambda_1,\lambda_2, … ,\lambda_m\} \rightarrow \{ x_1^*,x_2^*; \lambda_1,\lambda_2, \lambda_3\} {x1​,x2​,…,xn​;λ1​,λ2​,…,λm​}→{x1∗​,x2∗​;λ1​,λ2​,λ3​} ，目前方程组的方程只有 $n$ 个，这显然是解不出来的。

根据最值点 $p^{\ast }$ 的所在位置，可把不等式约束分为两类：一类约束的边界不是最值点的所在曲线，如上图的边界 $g_2(x_1,x_2)\le 0$，将最值点 $p^{\ast }$ 带入后恒有 $g_2(p^{\ast })\le 0$，即最终的极值点相对于 $g_2(x_1,x_2)\le 0$ 这个约束可以自由移动一段距离而不会违反这个约束，换言之 $g_2(x_1,x_2)\le 0$ 这个不等式相对于最值点没有起到任何约束作用。因此，这时 $g_2(p^{\ast })\le 0$ 对应的梯度系数 ${\lambda }_2$ 可设为 0；另一类约束的边界是最值点的所在曲线，如上图的 $g_1(x_1,x_2)\le 0,g_3(x_1,x_2)\ge 0$，这类约束对应的梯度系数 ${\lambda }_i$ 大于 0，但本身是边界函数，函数本身值为 0。综上所述，对于所有的不等式，无论最终是否起到约束作用，都有以下等式：

$${\lambda }_i{g}_i(x_1,x_2)=0$$

该公式也被称为互补松弛条件，得到这 $m$ 个等式松弛条件后，联合前面的式子即可解出所有变量，从而得到极值（$n+m$ 个变量， $n+m$ 个线性无关方程，则存在唯一解）。
在不等式约束的非线性规划问题中，每一个不等式是否起到约束作用，是根据最值点位置来确定的，通过引入互补松弛条件本质是一种待定系数法。

4、总结

以上从几何角度说明了 KKT 条件在非线性规划问题中求极值点的思路，下面对其进行汇总说明。

设目标函数为 $f(X)$ ，等式约束为 $h_i(X)$ ，不等式约束条件为 $g_j(X)$ ，此时，带约束的优化问题描述如下（以求最小值为例）：

$$\begin{array}{rl}& minf(X)\\ & s.t.h_i(X)=0i=1,2,\dots ,p\\ & g_j(X)\le 0j=1,2,\dots ,q\end{array}$$

则可定义在不等式约束下的拉格朗日函数 $L$：

$$L(X,\mu ,\lambda )=f(X)+\sum _{i=1}^p{\mu }_i{h}_i(X)+\sum _{j=1}^q{\lambda }_j{g}_j(X)$$

其中，${\mu }_i$ 为第 $i$ 个等式约束条件的约束系数，${\lambda }_j$ 为第 $j$ 个不等式约束条件的约束系数。
此时若要求解上述优化问题，就必须满足以下条件（即 KKT 条件）：

{ ∂ L ∂ X ∣ X = X ∗ = 0 对拉格朗日函数取极值时的必要条件 μ i ≠ 0 拉格朗日系数约束（同等式情况） λ j ≥ 0 不等式约束 λ j g j ( X ∗ ) = 0 互补松弛条件 h i ( X ∗ ) = 0 原约束条件 g j ( X ∗ ) ≤ 0 原约束条件 \left\{ \begin{aligned} &\left. \cfrac{\partial L}{\partial X} \right|_{X=X^*}=0 && 对拉格朗日函数取极值时的必要条件\\ &\mu_i \neq 0 && 拉格朗日系数约束（同等式情况）\\ &\lambda_j \geq0 && 不等式约束\\ &\lambda_jg_j(X^*)=0 && 互补松弛条件\\ &h_i(X^*)=0 && 原约束条件\\ &g_j(X^*) \leq0 && 原约束条件\\ \end{aligned} \right. ⎩ ⎨ ⎧​​∂X∂L​ ​X=X∗​=0μi​=0λj​≥0λj​gj​(X∗)=0hi​(X∗)=0gj​(X∗)≤0​​对拉格朗日函数取极值时的必要条件拉格朗日系数约束（同等式情况）不等式约束互补松弛条件原约束条件原约束条件​

充分性、必要性说明
首先需要强调的是，KKT 条件是判断某点是极值点的必要条件，而不是充分条件。换句话说，最优解一定满足KKT条件，但KKT条件的解不一定是最优解。但如果问题是凸规划，则 KKT 条件就是充要条件。此时，只要某个点满足 KKT 条件，就一定是极值点，且得到的一定还是全局最优解

六、基于 KKT 求解目标函数

接下来继续讨论支持向量机的最大间隔问题，前面已经得到该问题的优化目标为：

$$\begin{array}{rl}& mi{n}_{w,b}\frac{1}{2}{w}^2\\ & s.t.y_i(w^T{x}_i+b)\ge 1i=1,2,\dots ,n\end{array}$$

在运用 KKT 条件求解目标函数的极小值时，其不等式约束应该为“小于等于”，即：

$$\begin{array}{rl}& minf(X)\\ & s.t.g(X)\le 0\end{array}$$

为此，可将最大间隔问题的优化目标改写为：

$$\begin{array}{rl}& mi{n}_{w,b}\frac{1}{2}{w}^2\\ & s.t.1-y_i(w^T{x}_i+b)\le 0i=1,2,\dots ,n\end{array}$$

这是一个含不等式约束的凸二次规划问题，一定存在全局最优解。

首先将有约束的原始目标函数转换为无约束的拉格朗日函数：

$$\begin{array}{rl}L(w,b,\lambda )& =\frac{1}{2}{w}^2+\sum _{i=1}^n{\lambda }_i\left(1-y_i(w^T{x}_i+b)\right)\\ & =\frac{1}{2}{w}^2-\sum _{i=1}^n{\lambda }_i\left(y_i(w^T{x}_i+b)-1\right)\end{array}$$

其中， λ = { λ 1 , λ 2 , … , λ n } \lambda=\{ \lambda_1,\lambda_2 ,…,\lambda_n\} λ={λ1​,λ2​,…,λn​} 为拉格朗日乘子，分别对应样本集中的 $n$ 个样本，且 ${\lambda }_i\ge 0$ （强制约束条件被满足）。

接下来求该函数的一阶偏导数便能得到最终所需的 $w,b$，即：

{ ∂ L ∂ w ∣ = w − ∑ i = 1 n λ i y i x i = 0 ∂ L ∂ b ∣ = ∑ i = 1 n λ i y i = 0 \left\{ \begin{aligned} &\left. \cfrac{\partial L}{\partial w} \right|=w-\sum_{i=1}^n\lambda_iy_i\text{x}_i=0\\ &\left. \cfrac{\partial L}{\partial b} \right|=\sum_{i=1}^n\lambda_iy_i=0\\ \end{aligned} \right. ⎩ ⎨ ⎧​​∂w∂L​ ​=w−i=1∑n​λi​yi​xi​=0∂b∂L​ ​=i=1∑n​λi​yi​=0​

解得：

$$\{\begin{array}{rl}& w=\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\\ & \sum _{i=1}^n{\lambda }_i{y}_i=0\end{array}$$

上式 $w={\sum }_{i=1}^n{\lambda }_i{y}_i{\text{x}}_i$ ，这表明，每次在计算 $w$ 时都会遍历全部数据并执行计算。而由 ${\sum }_{i=1}^n{\lambda }_i{y}_i=0$ 可知，遍历全部数据并执行计算时，会有很多次得到的结果都是 0 ，这无疑浪费了很多时间。实际上我们知道，决定最终划分超平面方程的仅仅是有限条（少量的）支持向量（最终可直接拍板的甚至只有 2 条），所以上面的求解方式并没有充分利用 “很多 ${\lambda }_i$ 都是 0” 的关键信息。因此这样的求解方式虽然能行，但是不够好（在数据维度不高的情形下，该方法可通过批量梯度下降的传统方式进行求解）。

为了找到更好的求解方法（一方面降低问题的求解难度，另一方面将该模型推广至数据量更大的情况），引入原问题的对偶问题。

七、对偶问题的引入

前面介绍了有约束条件的最优化问题求解，对于有约束的最优化问题，可以通过 KKT 条件把有约束的最优化问题转化成无约束的最优化问题，但是有时候直接求解 KKT 条件也很困难，甚至无法求解，这时，我们可以通过求解原问题的对偶问题来得到原问题的一个下界估计。

原问题（Prime Problem）

设目标函数为 $f(X)$ ，等式约束为 $h_i(X)$ ，不等式约束条件为 $g_j(X)$ ，此时，带约束的优化问题描述如下（以求最小值为例）：

$$\begin{array}{rl}& minf(X)\\ & s.t.h_i(X)=0i=1,2,\dots ,p\\ & g_j(X)\le 0i=1,2,\dots ,q\end{array}$$

则可定义原问题的拉格朗日函数 $L$ ：

$$\begin{array}{rl}L(X,\mu ,\lambda )& =f(X)+\sum _{i=1}^p{\mu }_i{h}_i(X)+\sum _{j=1}^q{\lambda }_j{g}_j(X)\\ & =f(X)+{\mu }^{T}H(X)+{\lambda }^{T}G(X)\end{array}$$

对偶问题（dual problem）

m a x θ ( μ , λ ) = inf { L ( X , μ , λ ) } s . t . λ i ≥ 0 , i = 1 , 2 , … , q \begin{align*} &max \hspace{4px} \theta(\mu,\lambda)=\text{inf} \{L(X,\mu,\lambda)\} \\ &s.t. \hspace{1em} \lambda_i \geq 0, \hspace{1em} i=1,2,…,q\\ \end{align*} ​maxθ(μ,λ)=inf{L(X,μ,λ)}s.t.λi​≥0,i=1,2,…,q​

其中， $\text{inf}(\cdot )$ 为求下确界（最小值）函数； inf { L ( X , μ , λ ) } \text{inf} \{L(X,\mu,\lambda)\} inf{L(X,μ,λ)} 表示 “在固定 $\mu ,\lambda$ 的前提下，遍历所有 $X$ 以求 $L(X,\mu ,\lambda )$ 的最小值”。

1、对偶问题的性质

性质一（弱对偶定理）：如果 $X^{\ast }$ 是原问题的解，${\mu }^{\ast },{\lambda }^{\ast }$ 是对偶问题的解，则 $f(X^{\ast })\ge \theta ({\mu }^{\ast },{\lambda }^{\ast })$。

证明

由于 $h_i(X^{\ast })=0$，则 ${{\mu }^{\ast }}^{T}H(X^{\ast })={\sum }_{i=1}^p{\mu }_i{h}_i(X^{\ast })=0$
由于 $g_j(X^{\ast })\le 0,{\lambda }_j>0$，则 ${{\lambda }^{\ast }}^{T}G(X^{\ast })={\sum }_{j=1}^q{\lambda }_j{g}_j(X^{\ast })\le 0$
所以 θ ( μ ∗ , λ ∗ ) = inf { L ( X ∗ , μ ∗ , λ ∗ ) } ≤ L ( X ∗ , μ ∗ , λ ∗ ) = f ( X ∗ ) + μ ∗ T H ( X ∗ ) + λ ∗ T G ( X ∗ ) ≤ f ( X ∗ ) \theta(\mu^*,\lambda^*)=\text{inf}\{L(X^*,\mu^*,\lambda^*)\} \leq L(X^*,\mu^*,\lambda^*)=f(X^*)+{\mu^*}^TH(X^*)+{\lambda^*}^TG(X^*) \leq f(X^*) θ(μ∗,λ∗)=inf{L(X∗,μ∗,λ∗)}≤L(X∗,μ∗,λ∗)=f(X∗)+μ∗TH(X∗)+λ∗TG(X∗)≤f(X∗)

性质二（强对偶定理）：如果 $f(X)$ 是凸函数，$h(X)=AX+b,g(X)CX+d$，则此优化问题的原问题与对偶问题的间距（Duality gap）$G=f(X^{\ast })-\theta ({\mu }^{\ast },{\lambda }^{\ast })=0$

2、将原问题转变为对偶问题

支持向量机的原问题：

$$mi{n}_{w,b}L(w,b,\lambda )=\frac{1}{2}{w}^2-\sum _{i=1}^n{\lambda }_i\left(y_i(w^T{\text{x}}_i+b)-1\right)$$

根据前面的讨论，可得到其对偶问题。首先定义：

θ ( λ ) = inf { L ( w , b , λ ) } = m i n X , b L ( w , b , λ ) \theta(\lambda)=\text{inf}\{ L(w,b,\lambda) \}=min_{X,b}L(w,b,\lambda) θ(λ)=inf{L(w,b,λ)}=minX,b​L(w,b,λ)

则原问题的对偶问题为：

$$\begin{array}{rl}& ma{x}_{\lambda }\theta (\lambda )=mi{n}_{X,b}L(w,b,\lambda )\\ & s.t.{\lambda }_i\ge 0,i=1,2,\dots ,n\end{array}$$

由于目标函数 $f(w)$ 是凸函数，因此根据对偶问题的性质二（强对偶定理）可知： $f(w^{\ast })=\theta ({\lambda }^{\ast })$ 。其中， $w^{\ast }$ 是原问题的解，${\lambda }^{\ast }$ 是对偶问题的解）。也就是说，借助拉格朗日对偶性从原算法推出的对偶算法，两者完全等价，只是求解了不同的条件极值。

接下来我们尝试对新问题进行求解：

$$\begin{array}{rl}& ma{x}_{\lambda }mi{n}_{w,b}\frac{1}{2}{w}^2-\sum _{i=1}^n{\lambda }_i\left(y_i(w^T{\text{x}}_i+b)-1\right)\\ & s.t.{\lambda }_i\ge 0,i=1,2,\dots ,n\end{array}$$

3、求解对偶问题

第一步，求 $mi{n}_{w,b}L(w,b,\lambda )$

这一步和前面一样，先求偏导：

{ ∂ L ∂ w ∣ = w − ∑ i = 1 n λ i y i x i = 0 ∂ L ∂ b ∣ = ∑ i = 1 n λ i y i = 0 \left\{ \begin{aligned} &\left. \cfrac{\partial L}{\partial w} \right|=w-\sum_{i=1}^n\lambda_iy_i\text{x}_i=0\\ &\left. \cfrac{\partial L}{\partial b} \right|=\sum_{i=1}^n\lambda_iy_i=0\\ \end{aligned} \right. ⎩ ⎨ ⎧​​∂w∂L​ ​=w−i=1∑n​λi​yi​xi​=0∂b∂L​ ​=i=1∑n​λi​yi​=0​

解得：

$$\{\begin{array}{rl}& w^{\ast }=\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\\ & \sum _{i=1}^n{\lambda }_i{y}_i=0\end{array}$$

接下来将 $w^{\ast },b^{\ast }$ 回带目标函数（消去 $w,b$），从而将原问题转换为仅含 $\lambda$ 的式子，即：

$$ma{x}_{\lambda }mi{n}_{w,b}L(w,b,\lambda )=ma{x}_{\lambda }L(\lambda )$$

于是有：

$$\begin{array}{rl}{L(X,\mu ,\lambda )|}_{w^{\ast },b^{\ast }}& =\frac{1}{2}{w}^2-\sum _{i=1}^n{\lambda }_i\left(y_i(w^T{\text{x}}_i+b)-1\right)\\ & =\frac{1}{2}{w}^{T}w+\sum _{i=1}^n{\lambda }_i-\sum _{i=1}^n{\lambda }_i{y}_i{w}^T{\text{x}}_i-\sum _{i=1}^n{\lambda }_i{y}_{i}b\\ & =\frac{1}{2}{w}^T\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i-w^T\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i+\sum _{i=1}^n{\lambda }_i-b\sum _{i=1}^n{\lambda }_i{y}_i\\ & =\sum _{i=1}^n{\lambda }_i-\frac{1}{2}{w}^T\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\\ & =\sum _{i=1}^n{\lambda }_i-\frac{1}{2}{\left(\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\right)}^T\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\\ & =\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i^T\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\\ & =\sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j{\text{x}}_i^T{\text{x}}_j\end{array}$$

第二步，求 $ma{x}_{\lambda }L(\lambda )$

在优化问题中，我们通常倾向于求解目标函数的最小值，因此在这里将目标函数再做一个转变：

$$\begin{array}{rl}& mi{n}_{\lambda }\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j{\text{x}}_i^T{\text{x}}_j-\sum _{i=1}^n{\lambda }_i\\ & s.t.\sum _{i=1}^n{\lambda }_i{y}_i=0\\ & {\lambda }_i\ge 0\end{array}$$

这便是对偶问题的最终形式。该式的求解仅涉及一个变量，且把原问题的不等式约束变为了等式约束，因此在求解时可直接采用求导法。通过对 $\lambda$ 求导，并令其为 0，即能得到 $\lambda$ 的值，此时再根据：$w^{\ast }={\sum }_{i=1}^n{\lambda }_i{y}_i{\text{x}}_i$ 或 $b^{\ast }=y_j-{\sum }_{i=1}^n{\lambda }_i{y}_i{\text{x}}_i{\text{x}}_j$ ，并任选一个点即可算出划分超平面。即最终待求的划分超平面方程为：

$$w^{\ast }\cdot \text{x}+b^{\ast }=\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\text{x}+b^{\ast }=0$$

进而得到分类决策函数：

$$f(\text{x})=sign({w^{\ast }}^T\text{x}+b^{\ast })=sign(\sum _{i=1}^n{\lambda }_i{y}_i{\text{x}}_i\text{x}+b^{\ast })$$

其中，$sign(\cdot )$ 为阶跃函数。
由上式以及 $b^{\ast }$ 的表达式可以知道，划分超平面与分类决策函数都只与输入向量 $\text{x}$ 及其内积有关。

4、为什么要转换成对偶形式求解？

下面是原算法与对偶算法的目标方程对比：

从上面的对比可以看出，对偶算法主要有三点改进使得决策边界的求解不再困难：文章来源地址https://www.toymoban.com/news/detail-541113.html

1. 对偶问题将原始问题中的不等式约束转为了对偶问题中的等式约束；
2. 充分利用了 “很多 ${\lambda }_i$ 都是 0” 这个关键信息（即 ${\sum }_{i=1}^n{\lambda }_i{y}_i=0$），使得求解过程更快；
3. 方便核函数的引入（后面会详细解释）；
4. 改变了问题的复杂度。由求特征向量 $w$ 转化为求比例系数 $\lambda$。在原始问题下，求解的复杂度与样本的维度有关，即 $w$ 的维度。在对偶问题下，只与样本数量有关。

【机器学习】支持向量机（下）

END

到了这里，关于【机器学习】支持向量机（上）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！