7. 支持向量机
写在前面的话：距离上篇博客竟过去快一个月了，写完神经网络博客正式进入考试模式，几次考试+几篇报告下来弄得心颇不宁静了，今日定下来看到一句鸡血：Tomorrow is another due！也许生活就需要一些deadline~~
上篇主要介绍了神经网络。首先从生物学神经元出发，引出了它的数学抽象模型–MP神经元以及由两层神经元组成的感知机模型，并基于梯度下降的方法描述了感知机模型的权值调整规则。由于简单的感知机不能处理线性不可分的情形，因此接着引入了含隐层的前馈型神经网络，BP神经网络则是其中最为成功的一种学习方法，它使用误差逆传播的方法来逐层调节连接权。最后简单介绍了局部/全局最小以及目前十分火热的深度学习的概念。本篇围绕的核心则是曾经一度取代过神经网络的另一种监督学习算法–支持向量机（Support Vector Machine），简称SVM。
6、支持向量机
支持向量机是一种经典的二分类模型，基本模型定义为特征空间中最大间隔的线性分类器，其学习的优化目标便是间隔最大化，因此支持向量机本身可以转化为一个凸二次规划求解的问题。
6.1 函数间隔与几何间隔
对于二分类学习，假设现在的数据是线性可分的，这时分类学习最基本的想法就是找到一个合适的超平面，该超平面能够将不同类别的样本分开，类似二维平面使用ax+by+c=0来表示，超平面实际上表示的就是高维的平面，如下图所示：
对数据点进行划分时，易知：当超平面距离与它最近的数据点的间隔越大，分类的鲁棒性越好，即当新的数据点加入时，超平面对这些点的适应性最强，出错的可能性最小。因此需要让所选择的超平面能够最大化这个间隔Gap（如下图所示）， 常用的间隔定义有两种，一种称之为函数间隔，一种为几何间隔，下面将分别介绍这两种间隔，并对SVM为什么会选用几何间隔做了一些阐述。
6.1.1 函数间隔
在超平面w’x+b=0确定的情况下，|w’x*+b|能够代表点x距离超平面的远近，易知：当w’x+b>0时，表示x在超平面的一侧（正类，类标为1），而当w’x+b<0时，则表示x在超平面的另外一侧（负类，类别为-1），因此（w’x+b）y* 的正负性恰能表示数据点x*是否被分类正确。于是便引出了函数间隔的定义（functional margin）:
而超平面（w,b）关于所有样本点（Xi，Yi）的函数间隔最小值则为超平面在训练数据集T上的函数间隔：
可以看出：这样定义的函数间隔在处理SVM上会有问题，当超平面的两个参数w和b同比例改变时，函数间隔也会跟着改变，但是实际上超平面还是原来的超平面，并没有变化。例如：w1x1+w2x2+w3x3+b=0其实等价于2w1x1+2w2x2+2w3x3+2b=0，但计算的函数间隔却翻了一倍。从而引出了能真正度量点到超平面距离的概念–几何间隔（geometrical margin）。
6.1.2 几何间隔
几何间隔代表的则是数据点到超平面的真实距离，对于超平面w’x+b=0，w代表的是该超平面的法向量，设x为超平面外一点x在法向量w方向上的投影点，x与超平面的距离为r，则有x=x-r(w/||w||)，又x在超平面上，即w’x+b=0，代入即可得：
为了得到r的绝对值，令r呈上其对应的类别y，即可得到几何间隔的定义：
从上述函数间隔与几何间隔的定义可以看出：实质上函数间隔就是|w’x+b|，而几何间隔就是点到超平面的距离。
6.2 最大间隔与支持向量
通过前面的分析可知：函数间隔不适合用来最大化间隔，因此这里我们要找的最大间隔指的是几何间隔，于是最大间隔分类器的目标函数定义为：
一般地，我们令r^为1（这样做的目的是为了方便推导和目标函数的优化），从而上述目标函数转化为：
对于y(w’x+b)=1的数据点，即下图中位于w’x+b=1或w’x+b=-1上的数据点，我们称之为支持向量（support vector），易知：对于所有的支持向量，它们恰好满足y(w’x+b)=1，而所有不是支持向量的点，有y(w’x+b)>1。
6.3 从原始优化问题到对偶问题
对于上述得到的目标函数，求1/||w||的最大值相当于求||w||^2的最小值，因此很容易将原来的目标函数转化为：
即变为了一个带约束的凸二次规划问题，按书上所说可以使用现成的优化计算包（QP优化包）求解，但由于SVM的特殊性，一般我们将原问题变换为它的对偶问题，接着再对其对偶问题进行求解。为什么通过对偶问题进行求解，有下面两个原因：
* 一是因为使用对偶问题更容易求解；
* 二是因为通过对偶问题求解出现了向量内积的形式，从而能更加自然地引出核函数。对偶问题，顾名思义，可以理解成优化等价的问题，更一般地，是将一个原始目标函数的最小化转化为它的对偶函数最大化的问题。对于当前的优化问题，首先我们写出它的朗格朗日函数：
上式很容易验证：当其中有一个约束条件不满足时，L的最大值为 ∞（只需令其对应的α为 ∞即可）；当所有约束条件都满足时，L的最大值为1/2||w||^2（此时令所有的α为0），因此实际上原问题等价于：
由于这个的求解问题不好做，因此一般我们将最小和最大的位置交换一下（需满足KKT条件） ，变成原问题的对偶问题：
这样就将原问题的求最小变成了对偶问题求最大（用对偶这个词还是很形象），接下来便可以先求L对w和b的极小，再求L对α的极大。
（1）首先求L对w和b的极小，分别求L关于w和b的偏导，可以得出：
将上述结果代入L得到：
（2）接着L关于α极大求解α（通过SMO算法求解，此处不做深入）。
（3）最后便可以根据求解出的α，计算出w和b，从而得到分类超平面函数。
在对新的点进行预测时，实际上就是将数据点x*代入分类函数f(x)=w’x+b中，若f(x)>0，则为正类，f(x)<0，则为负类，根据前面推导得出的w与b，分类函数如下所示，此时便出现了上面所提到的内积形式。
这里实际上只需计算新样本与支持向量的内积，因为对于非支持向量的数据点，其对应的拉格朗日乘子一定为0，根据最优化理论（K-T条件），对于不等式约束y(w’x+b)-1≥0，满足：
6.4 核函数
由于上述的超平面只能解决线性可分的问题，对于线性不可分的问题，例如：异或问题，我们需要使用核函数将其进行推广。一般地，解决线性不可分问题时，常常采用映射的方式，将低维原始空间映射到高维特征空间，使得数据集在高维空间中变得线性可分，从而再使用线性学习器分类。如果原始空间为有限维，即属性数有限，那么总是存在一个高维特征空间使得样本线性可分。若∅代表一个映射，则在特征空间中的划分函数变为：
按照同样的方法，先写出新目标函数的拉格朗日函数，接着写出其对偶问题，求L关于w和b的极大，最后运用SOM求解α。可以得出：
（1）原对偶问题变为：
（2）原分类函数变为：
求解的过程中，只涉及到了高维特征空间中的内积运算，由于特征空间的维数可能会非常大，例如：若原始空间为二维，映射后的特征空间为5维，若原始空间为三维，映射后的特征空间将是19维，之后甚至可能出现无穷维，根本无法进行内积运算了，此时便引出了核函数（Kernel）的概念。
因此，核函数可以直接计算隐式映射到高维特征空间后的向量内积，而不需要显式地写出映射后的结果，它虽然完成了将特征从低维到高维的转换，但最终却是在低维空间中完成向量内积计算，与高维特征空间中的计算等效（低维计算，高维表现），从而避免了直接在高维空间无法计算的问题。引入核函数后，原来的对偶问题与分类函数则变为：
（1）对偶问题：
（2）分类函数：
因此，在线性不可分问题中，核函数的选择成了支持向量机的最大变数，若选择了不合适的核函数，则意味着将样本映射到了一个不合适的特征空间，则极可能导致性能不佳。同时，核函数需要满足以下这个必要条件：
由于核函数的构造十分困难，通常我们都是从一些常用的核函数中选择，下面列出了几种常用的核函数：
6.5 软间隔支持向量机
前面的讨论中，我们主要解决了两个问题：当数据线性可分时，直接使用最大间隔的超平面划分；当数据线性不可分时，则通过核函数将数据映射到高维特征空间，使之线性可分。然而在现实问题中，对于某些情形还是很难处理，例如数据中有噪声的情形，噪声数据（outlier）本身就偏离了正常位置，但是在前面的SVM模型中，我们要求所有的样本数据都必须满足约束，如果不要这些噪声数据还好，当加入这些outlier后导致划分超平面被挤歪了，如下图所示，对支持向量机的泛化性能造成很大的影响。
为了解决这一问题，我们需要允许某一些数据点不满足约束，即可以在一定程度上偏移超平面，同时使得不满足约束的数据点尽可能少，这便引出了“软间隔”支持向量机的概念
* 允许某些数据点不满足约束y(w'x+b)≥1；
* 同时又使得不满足约束的样本尽可能少。这样优化目标变为：
如同阶跃函数，0/1损失函数虽然表示效果最好，但是数学性质不佳。因此常用其它函数作为“替代损失函数”。
支持向量机中的损失函数为hinge损失，引入“松弛变量”，目标函数与约束条件可以写为：
其中C为一个参数，控制着目标函数与新引入正则项之间的权重，这样显然每个样本数据都有一个对应的松弛变量，用以表示该样本不满足约束的程度，将新的目标函数转化为拉格朗日函数得到：
按照与之前相同的方法，先让L求关于w，b以及松弛变量的极小，再使用SMO求出α，有：
将w代入L化简，便得到其对偶问题：
将“软间隔”下产生的对偶问题与原对偶问题对比可以发现：新的对偶问题只是约束条件中的α多出了一个上限C，其它的完全相同，因此在引入核函数处理线性不可分问题时，便能使用与“硬间隔”支持向量机完全相同的方法。
SVM
对于第(1),(3)条决策边界, 离边界近的点, 可能加点噪点(pertubation), 就会被错误分类, 不够robust.
对于第(2)条决策边界, 它是最好的, 因为它的安全区域/margin足够大, robust to perturbation. 所以SVM就是一个Max-Margin Method.
Maximize the Margin
图中, w 垂直于 $w^Tx+b = 0$这条线, 证明:
$wx_1+b=0, \;\;\; wx_2+b=0$$w(x_1-w_2)=0$$w \perp (w_1-x_2) $因为 斜率不存在时直线与x轴垂直, 斜率为0时直线与x轴平行
在$w^Tx+b=1, \;\;\; w^Tx+b=-1$ 这两条线上各取一点 $x_+, x_-$, 求margin
$$
\begin{align}
\left\{
\begin{array}{**lr**}
w^Tx_++b=1 & [1] \\ \tag{1}
w^Tx_-+b=-1 & [2] \\
x_+ = x_- +\lambda w & 因为x_+,x_-都在w的方向 & [3]
\end{array}
\right.
\end{align}
$$
margin就是$x_+, x_-$的距离
$$
\begin{equation}
margin = |x_+ - x_-|
\end{equation}
$$
$$
\begin{align*}
w^T(x_- +\lambda w)+b=1 \tag{3} \\
w^Tx_- +\lambda w^T w+b=1 \tag{4}\\
\lambda w^T w - 1 =1 \tag{5}\\
\lambda w^T w =2 \tag{6}\\
\lambda =\frac{2}{w^T w } \tag{7}\\
\end{align*}
$$
- 将(1)中的[3]带入(1)中的[1]得到(3)
- 将(1)中的[2]带入(4)得到(5)
最后:
$$
\begin{align*}
margin &= |\lambda w| \tag{8} \\
&= \lambda ||w|| \tag{9}\\
&= \frac{2}{w^T w } ||w|| \tag{10}\\
&= \frac{2}{||w||} \tag{11}\\
\end{align*}
$$
- 将(1)中的[3]带入(2)得到(8)
- 将(7)带入(9)得到(10)
- w是列向量, 列向量的转置乘以列向量, 就变成向量各个元素的平方之和, 最终得到(11)
Hard Constraint
$$
\begin{align*}
& Maximize \frac{2}{||w||} \;==>\; Minimize ||w||^2\\
& s.t. \\
& w^tx_i+b \geq 1 \;\;\; if\;\; y_i=1 \\
& w^tx_i+b \leq 1 \;\;\; if\;\; y_i=-1 \\
\end{align*}
$$
Soft Constraint
hard-constraint 容易过拟合
- soft-constraint容忍错误, 在目标函数上加一个对epsilon的惩罚项
- 从hard到soft的转变就是 由 1 变成 1-epsilon, epsilon>=0
- epsilon相当于允许犯错的空间
Hinge Loss
Convert to hinge loss
👆Linear SVM
- 约束可以转换成epsilon >= 1-(wx+b)yi
- 由于是最小化目标函数, 所以epsilon取最小值, 即1-(wx+b)yi
- 又因为epsilon>=0, 所以1-(wx+b)yi>=0
- 所以有了hinge loss ==> max(0,1-(wx+b)yi)
SGD for hinge loss
多了一个判断 1-(wx+b)yi 是否小于0
Prime dual
转换成dual form的原因:
- 在prime form上找不到最优解, 但是可能会在dual form上找到 最优解 或者是 sub-optimal
- 转换成dual form后容易使用Kernel trick (把数据映射到高维度, 但是使用kernel trick, 相当于计算原始空间的复杂度)
Linear SVM的缺点:
- 解决不了非线性的问题
解决方法:
- 利用非线性模型 - neural network
- 把数据映射到高维空间(在高维空间, 区别度更加明显, 所以可能一个线性模型即可区分开数据), 然后学习一个线性模型
Mapping feature to High Dimensional Space
缺点:
- 转为高维, 时间复杂度增加
- 构建模型的复杂度增加 O(D) => O(D`)
- 解决方法: kernel trick (step1和step2的结合)
拉格朗日: 等号条件处理
泛化:
拉格朗日: 不等号条件处理
KKT条件
KKT condition of SVM
👆prime problem
转换成dual problem的理由
- prime问题有可能比较难解决
- 在dual问题上发下一些有趣的insight (SVM使用kernel trick)
👇dual problem
Kernel Trick
现象: 原本空间映射到高维空间后, 仅依赖原本空间内积的运算, 不依赖高维空间的计算
核心: 如何设计非线性变换器$\phi(x)$, 使得内积的计算的时间复杂度保持不变. 又称核函数
kernel trick 不仅仅是针对SVM, 只要目标函数有内积的计算(dot product)
Linear Kernel: $K(x,y) = x^T \cdot y$ => linear SVM
Polynomial Kernel: $K(x,y) = (1+x^T \cdot y)^d$
Guassian Kernel: $K(x,y) = exp(\frac{-||x-y||^2}{2 \sigma^2})$
Mercer’s Theorem
SVM
一、SVM算法要解决什么问题
Support Vector Machine(SVM) 支持向量机
- 主要用于解决模式识别领域中的数据分类问题
- 属于有监督学习算法的一种
用一个二分类问题来描述SVM, 如图1所示, 红色和蓝色的二维数据点显然是可以被一条直线分开的, 称为线性可分问题. 然而将两类数据点分开的直线显然不止一条. 图1(b)和©分别给出了A、B两种不同的分类方案，其中黑色实线为分界线，术语称为“决策面”. 每个决策面对应了一个线性分类器.
图1 二分类问题描述
SVM算法认为图1中的分类器A在性能上优于分类器B，其依据是A的分类间隔比B要大.
分类间隔如虚线所示, 虚线的位置由决策面的方向和距离决策面最近的几个样本的位置决定. 两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔.
具有“最大间隔”的决策面就是SVM要寻找的最优解. 而这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为“支持向量”.
对于图1中的数据，A决策面就是SVM寻找的最优解，而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量.
实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量. 而在经过公式推导后，其实与线性决策面的方向和位置直接相关的参数都会被约减掉，最终结果只取决于样本点的选择结果. SVM算法要解决的是一个最优分类器的设计问题。既然叫作最优分类器，其本质必然是个最优化问题。所以，接下来我们要讨论的就是如何把SVM变成用数学语言描述的最优化问题模型，这就是我们在第二部分要讲的“线性SVM算法的数学建模”。
在图1里，样本是二维空间中的点(数据的维度是2), 因此1维的直线可以分开它们. 但是在更加一般的情况下，样本点的维度是n，则将它们分开的决策面的维度就是n-1维的超平面, 所以叫“决策面”更加具有普适性
二、线性SVM算法的数学建模
一个最优化问题通常有两个最基本的因素：
- 目标函数, 即你希望什么东西的什么指标达到最好
- 优化对象, 即你期望通过改变哪些因素来使你的目标函数达到最优
在线性SVM算法中，目标函数显然就是那个“分类间隔”，而优化对象则是决策面.
2.1 决策面方程
二维空间中的直线方程式: $y=ax+b$ (2.1)
现在做个小小的改变，让原来的x轴变成x1轴，y变成x2轴，于是公式(2.1)中的直线方程会变成下面的样子 $x_2=ax_1+b$ (2.2)
$ax_1+(-1)x_2+b=0$ (2.3)
公式（2.3）的向量形式可以写成
$[a,-1]\left[\begin{matrix}x_1\ x_2\end{matrix}\right]+b=0$ (2.4)
考虑到在等式两边乘上任何实数都不会改变等式的成立，所以可以写出一个更加一般的向量表达形式:
$w^T x+b=0$ (2.5)
w,x都是向量. 一般提到向量的时候, 都默认他们是个列向量. 所以在公式(2.5)里面w后面的转置符号T，会把列向量又转回到行向量. 这样一个行向量$w^T$和一个列向量$x$就可按照矩阵乘法的方式结合，变成一个标量，然后好跟后面的标量b相加后相互抵消变成0.
参数w和b的几何意义:
- w控制了直线的方向
- b就是截距, 它控制了直线的位置
公式(2.2)中的a, 是直线的斜率. 如果构造一个向量$\phi = [1,a]^T$，它应该跟公式(2.2)描述的直线平行. 然后求一下两个向量的点积$w^Y \phi$, 结果是0. 管这种现象叫作“两个向量相互正交”, 即两个向量相互垂直. 比如让$a=\sqrt{3}$, 会发现$\phi = [1,a]^T$在第一象限，与横轴夹角为60°，而$w = [a,-1]^T$在第四象限与横轴夹角为30°，所以很显然他们两者的夹角为90°. 所以向量$w=[w_1,w_2]^T$跟直线$w^T x+b=0$是相互垂直的.
上面描述一个很简单的超平面方程（其实只是个直线方程), 这里真正有价值的是控制方向的参数w.
2.2 分类“间隔”的计算模型
间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍，如图2所示.
图2 分类间隔计算
所以分类间隔计算似乎相当简单，就是点到直线的距离公式:
$d = \frac{|w^T x+b|}{||w||}$ (2.6)
- 这里$||w||$是向量w的模，表示在空间中向量的长度
- $x=[x_1,x_2]^T$就是支持向量样本点的坐标
- $w,b$就是决策面方程的参数.
- 而追求图中 W 的最大化也就是寻找图中 d 的最大化
2.3 约束条件
需要注意👇几个为题：
- 并不是所有的方向都存在能够实现100%正确分类的决策面，如何判断一条直线是否能够将所有的样本点都正确分类？
- 即便找到了正确的决策面方向，还要注意决策面的位置应该在间隔区域的中轴线(轴对称图形的中心线)上，所以用来确定决策面位置的截距b也不能自由的优化，而是受到决策面方向和样本点分布的约束
- 即便取到了合适的方向和截距，公式(2.6)里面的x不是随随便便的一个样本点，而是支持向量对应的样本点. 对于一个给定的决策面，该如何找到对应的支持向量？
以上三条麻烦的本质是“约束条件”，也就是说要优化的变量的取值范围受到了限制和约束. SVM算法通过一些巧妙的小技巧，将这三条约束条件融合在了一个不等式里面.
首先考虑一个决策面是否能够将所有的样本都正确分类的约束. 图2中的样本点分成两类（红色和蓝色), 为每个样本点$x_i$加上一个类别标签$y_i$：
$ y_i=\left{\begin{aligned}+1 && for\;\;blue\;\;points \-1 && for\;\;red\;\;points \ \end{aligned}\right.$ (2.7)
如果决策面方程能够完全正确地对图2中的样本点进行分类，就会满足下面的公式
$ \left{\begin{aligned}& w^T x_i +b > 0 && fory_i=1 \& w^T x_i +b < 0 && fory_i=-1 \ \end{aligned}\right.$ (2.8)
如果要求再高一点，假设决策面正好处于间隔区域的中轴线上，并且相应的支持向量对应的样本点到决策面的距离为d，那么公式(2.8)就可以进一步写成：
$ \left{\begin{aligned}& \frac{w^T x_i +b}{||w||} \geq d && \forall y_i=1 \& \frac{w^T x_i +b}{||w||} \leq -d && \forall y_i=-1 \ \end{aligned}\right.$ (2.9)
符号$\forall$是“对于所有满足条件的” 的缩写. 对公式(2.9)中的两个不等式的左右两边除上d，就可得到：
$ \left{\begin{aligned}& w^T_d x_i +b_d \geq 1 && \forall y_i=1 \& w^T_d x_i +b_d \leq -1 && \forall y_i=-1 \ \end{aligned}\right.$ (2.10)
其中
$w_d= \frac{w}{||w||d},\;\;\;b_d = \frac{b}{||w||d}$
把$w_d, b_d$就当成一条直线的方向矢量和截距. 其实没有发生任何变化，因为直线$w^T_d x_i +b_d=0$和直线$w^T x_i +b=0$其实是一条直线. 用$w, b$来代替$w_d, b_d$, 现在可以直接说：“对于存在分类间隔的两类样本点，一定可以找到一些决策面，使其对于所有的样本点均满足下面的条件：”
$ \left{\begin{aligned} & w^T x_i +b \geq 1 && \forall y_i=1 \ & w^T x_i +b \leq -1 && \forall y_i=-1 \ \end{aligned}\right.$ (2.11)
公式(2.11)可以认为是SVM优化问题的约束条件的基本描述.
2.4 线性SVM优化问题基本描述
公式(2.11)里面$w^T x_i +b = 1 or -1$的情况什么时候会发生呢? 只有当$x_i$是决策面$w^T x_i +b=0$所对应的支持向量样本点时，等于1或-1的情况才会出现. 这一点给了我们另一个简化目标函数的启发: 回头看看公式(2.6), 无论原来$w^T x_i +b$是1或者-1，其绝对值都是1. 所以对于这些支持向量样本点有：
$d = \frac{|w^T x_i +b|}{||w||} = \frac{1}{||w||}, ~if~x_i~is~a~support~vector $ (2.12)
公式(2.12)的几何意义就是，支持向量样本点到决策面方程的距离就是$\frac{1}{||w||}$. 原来的任务是找到一组参数$w,b$使得分类间隔$W=2d$最大化，根据公式(2.12)就可以转变为$||w||$的最小化问题，也等效于$\frac12 ||w||^2$的最小化问题. 之所以要在$||w||$上加上平方 & 1/2的系数, 是为了以后进行最优化的过程中对目标函数求导时比较方便, 但这绝不影响最优化问题最后的解.
另外还可以尝试将公式(2.11)给出的约束条件进一步在形式上精练，把类别标签$y_i$和两个不等式左边相乘，形成统一的表述：
$y_i(w^T x_i +b) \geq 1 ~~~ \forall ~ x_i$ （2.13）
最终, 可以给出线性SVM最优化问题的数学描述了：
$min_{w,b} ~ \frac{1}{2} ||w||^2 \ s.t.~~ y_i(w^T x_i +b) \geq 1 ,~~ i=1,2,…,m$ （2.14）
这里m是样本点的总个数，缩写s.t. 表示“Subject to”，是“服从某某条件”的意思. 公式(2.14)描述的是一个典型的不等式约束条件下的二次型函数优化问题，同时也是支持向量机的基本数学模型.
三、有约束最优化问题的数学模型
3.1 有约束优化问题的几何意象
约束条件一般分为等式约束和不等式约束两种，前者表示为$g(x)=0$; 后者表示为$g(x) \leq 0$
假设$x\in \mathbb{R}^d$（就是这个向量一共有d个标量组成），则$g(x)=0$的几何意象就是d维空间中的d-1维曲面，如果函数$g(x)$是线性的，$g(x)=0$则是个d-1维的超平面. 那么有约束优化问题就要求在这个d-1维的曲面或者超平面上找到能使得目标函数最小的点，这个d-1维的曲面就是“可行解区域”.
对于不等式约束条件，$g(x) \leq 0$，则可行解区域从d-1维曲面扩展成为d维空间的一个子集. 可以从d=2的二维空间进行对比理解. 等式约束对应的可行解空间就是一条线；不等式约束对应的则是这条线以及线的某一侧对应的区域，就像下面这幅图的样子（图中的目标函数等高线其实就是等值线，在同一条等值线上的点对应的目标函数值相同）.
图3 有约束优化问题的几何意象图
3.2 拉格朗日乘子法
如何利用代数方法找到这个被约束了的最优解呢？这就需要用到拉格朗日乘子法.
首先定义原始目标函数$f(x)$，拉格朗日乘子法的基本思想是把约束条件转化为新的目标函数$L(x,\lambda)$的一部分，从而使有约束优化问题变成无约束优化问题.
分析可行解区域中最优解的特点:
1）最优解的特点分析
这里比较有代表性的是等式约束条件. 观察一下图3中的红色虚线（可行解空间）和蓝色虚线（目标函数的等值线), 发现这个被约束的最优解恰好在二者相切的位置(绿色×).
梯度的概念 - 梯度可以直观的认为是函数的变化量，可以描述为包含变化方向和变化幅度的一个向量. 然后给出一个推论：
推论1：“二者相切的位置(相遇点)$x^$（也就是等式约束条件下的优化问题的最优解), 原始目标函数$f(x)$的梯度向量$\Delta f(x^)$必然与约束条件$g(x)=0$的切线方向垂直。”
关于推论1的粗浅的论证如下：
如果梯度矢量[公式]不垂直于[公式]在[公式]点的切线方向，就会在[公式]的切线方向上存在不等于0的分量，也就是说在相遇点[公式]附近，[公式]还在沿着[公式]变化。这意味在[公式]上[公式]这一点的附近一定有一个点的函数值比[公式]更小，那么[公式]就不会是那个约束条件下的最优解了。所以，梯度向量[公式]必然与约束条件[公式]的切线方向垂直。
推论2：“函数$f(x)$的梯度方向也必然与函数自身等值线切线方向垂直.”
推论2的粗浅论证：与推论1 的论证基本相同，如果[公式]的梯度方向不垂直于该点等值线的切线方向，[公式]就会在等值线上有变化，这条线也就不能称之为等值线了。
根据推论1和推论2，函数[公式]的梯度方向在[公式]点同时垂直于约束条件[公式]和自身的等值线的切线方向，也就是说函数[公式]的等值线与约束条件曲线[公式]在[公式]点具有相同（或相反）的法线方向，所以它们在该点也必然相切。
让我们再进一步，约束条件[公式]也可以被视为函数[公式]的一条等值线。按照推论2中“函数的梯度方向必然与自身的等值线切线方向垂直”的说法，函数[公式]在[公式]点的梯度矢量[公式]也与[公式]的切线方向垂直。
到此我们可以将目标函数和约束条件视为两个具有平等地位的函数，并得到推论3：
推论3：“函数$f(x)$与函数$g(x)$的等值线在最优解点$x^$处相切，即两者在$x^$点的梯度方向相同或相反”
于是我们可以写出公式(3.1)，用来描述最优解[公式]的一个特性：
这里增加了一个新变量[公式],用来描述两个梯度矢量的长度比例。那么是不是有了公式（3.1）就能确定[公式]的具体数值了呢？显然不行！从代数解方程的角度看，公式（3.1）相当于d个方程（假设[公式]是d维向量，函数[公式]的梯度就是d个偏导数组成的向量，所以公式(2.15)实际上是1个d维矢量方程，等价于d个标量方程），而未知数除了[公式]的d个分量以外，还有1个[公式]。所以相当于用d个方程求解d+1个未知量，应有无穷多组解；从几何角度看，在任意曲线[公式]（k为值域范围内的任意实数）上都能至少找到一个满足公式(3.1)的点，也就是可以找到无穷多个这样的相切点。所以我们还需要增加一点限制，使得无穷多个解变成一个解。好在这个限制是现成的，那就是：
把公式(3.1)和(3.2)放在一起，我们有d+1个方程，解d+1个未知数，方程有唯一解，这样就能找到这个最优点[公式]了。
2）构造拉格朗日函数
虽然根据公式(3.1)和(3.2),已经可以求出等式约束条件下的最优解了，但为了在数学上更加便捷和优雅一点，我们按照本节初提到的思想，构造一个拉格朗日函数，将有约束优化问题转为无约束优化问题。拉格朗日函数具体形式如下：
新的拉格朗日目标函数有两个自变量[公式]，根据我们熟悉的求解无约束优化问题的思路，将公式(3.3)分别对[公式]求导，令结果等于零，就可以建立两个方程。同学们可以自己试一下，很容易就能发现这两个由导数等于0构造出来的方程正好就是公式(3.1)和(3.2)。说明新构造的拉格朗日目标函数的优化问题完全等价于原来的等式约束条件下的优化问题。
至此，我们说明白了“为什么构造拉格朗日目标函数可以实现等式约束条件下的目标优化问题的求解”。可是，我们回头看一下公式(2.14)，也就是我们的SVM优化问题的数学表达。囧，约束条件是不等式啊！怎么办呢？
3.3 KKT条件
对于不等式约束条件[公式]的情况，如图4所示，最优解所在的位置[公式]有两种可能，或者在边界曲线[公式]上或者在可行解区域内部满足不等式[公式]的地方。
第一种情况：最优解在边界上，就相当于约束条件就是[公式]。参考图4，注意此时目标函数[公式]的最优解在可行解区域外面，所以函数[公式]在最优解[公式]附近的变化趋势是“在可行解区域内侧较大而在区域外侧较小”，与之对应的是函数[公式]在可行解区域内小于0，在区域外大于零，所以在最优解[公式]附近的变化趋势是内部较小而外部较大。这意味着目标函数[公式]的梯度方向与约束条件函数[公式]的梯度方向相反。因此根据公式(3.1)，可以推断出参数[公式].