记录记录，好记性不如烂笔头，本系列博客是我以后复习使用，所以没有按照顺序来写。这一篇blog讲SVM的两个难题，一个是拉格朗日乘子，一个是KKT条件。

支持向量机SVM

支持向量机（SVM），全称是support vector machine,简单来说，它是一种二类分类器，基本模型就是在特征空间上寻找间隔最大的线性分类器，基于这个模型我们更改核函数就可以把它应用于非线性问题之中，首先我们看他的定义，什么是“在特征空间中寻找间隔最大的线性分类器”？首先我们应该知道什么是线性分类器，详情见上一篇博文，其中描述的logistic regression 便是我们的基础，假设SVM是一个二分类器，那么显而易见，我们需要将输出结果转换为两种类别。下面举一个简单的例子

二分类问题

圆圈与叉叉分别表示两种不同的种类，显而易见，我们可以通过logistic regression来拟合一条直线分类这两种不同的类别，拟合之后他大概长这个样子。

logistic regression

因为w*x+b输出的是一个连续值，比如说0.8,1.5，需要将他同1,-1,0比较，上图中最左边那条虚线表示的是通过了最近的一个反例，同理最右边那条虚线表示的是通过了最近的一个正例，这些被边缘线通过的点被叫做支持向量，他们是最重要的，哪怕不要其他点。因为他们规定了正例以及反例的边缘。

关于求解SVM时候的拉格朗日乘子以及KKT条件

我们再重新看一遍关于SVM的定义，目的是取得间隔最大化的学习器，当超平面距离数据点越远时候，分类的确信度也越大，为了让确信度足够高我们应该让所选择的超平面最大化这个“间隔”值，两个经过异类支持向量点的超平面之间距离为2/||w||,就是我们需要最大化的间隔。如下图所示

支持向量机

我们的超平面对数据进行正常分类那么必定存在下面的不等式，对于正例y=+1，我们的超平面需要将他预测为>=1的情况，如果y=-1那么我们的超平面需要将他预测为<=-1。

这是很容易理解的，当样例为正例时我们应该把他预测至少=1或者>1,反之也是成立的。那么问题现在就清楚了，我们应该在他满足正常分类的条件下，求得||w||的最小值，也就是我们想要最大化||w||^2

目标函数与约束条件

上式中w,b是模型参数，现在我们面临的是一个最优化问题，怎么求解呢？这是一个凸优化问题（y(x),h(x)是凸函数，并且h(x)为仿射函数），我们可以用现成的工具包来解，但是我们这里采用的是另一种解法，可以顺势引出核函数等。
这时候我们需要构造一个拉格朗日函数，拉格朗日函数就是将约束条件分别和拉格朗日乘子相乘，然后再与目标函数相加，这样我们的关系式就可以用一个方程标示出来了，但是我们面临一个问题，就是约束条件可能是等式，也可能是不等式，我们要分开考虑两种情况。

等式约束

考虑一个简单的问题目标函数f(x) = x1 + x2，等式约束h(x)=x1^2 + x2^2 −2，求解极小值点。f(x)在二维平面上画出等高线（contour）就是一条条斜率相同的直线，h(x)=0在二维平面上画出等高线就是一个圆，如下图所示。可以明显的看出，在圆圈h(x)的限制下，直线f(x)的最小值为-2，在左下角直线x1+x2=2和圆的交点上。

我们从梯度方向考虑一下，如果不考虑限制条件的话，目标函数将会向他梯度的反方向移动，如下方深蓝色箭头。但是如果考虑限制的话我们只能取得圆圈上的值那么他只能向h(x)梯度正切方向移动，(注意h(x)函数是那个圆，梯度是指向圆外的)，红粗线表示目标函数移动方向，细红线表示限制函数的梯度。

我们可以发现，在关键的极小值处，我们的目标函数和限制条件的梯度是在一条直线上的，可能是同向的也可能是反向的，在极小值点有如下情况

在最小值时候梯度共线

梯度关系

也就是说，我们对于f(x)以及h(x)来说当满足上面的式子时候，就是目标函数和限制条件在同一条直线时候，并且此时的h(x)=0（因为是在圆上）时候解得的x就是我们需要的极值点，为了做到上面这个条件，我们构造一个拉格朗日函数，对函数令偏导数为0求解，这时候恰好等价于“满足上面那个式子，并且h(x)=0”，那么此时我们求解出来的x就是我们所需要的极值点，和就是拉格朗日乘子法。

上面我们提到的求||w||^2的最小值，限制条件是要求正确分类那些点，那么就可以转换成拉格朗日函数来求解。

拉格朗日函数

其中第二张图片中的x就是我们需要求解的变量，也就是上面问题中的w，接下来我们就需要该函数分别对x和拉格朗日乘子分别求偏导数等于0，对x求偏导为0表示满足梯度在一条直线，对拉格朗日乘子求偏导为0表示h(x)=0，这样求解出来的x就是极值点。

不等式约束

在不等式约束中有两种情况我们需要讨论，这里需要注意以下，很多blog上面都没有写清楚为什么g(x)<0情况下约束条件是不起作用的，参阅了另外一篇博客时候发现了解释，最后写出参考的blog网址，在不等式约束g(x)<0情况下，我们将极值点情况分为两类，这是一种分类思想，将极值点分为在约束域中以及约束域外，首先我们来看极值点在约束域内的话是什么情况。

极值点在约束域内

考虑目标函数f(x)=x1²+x2²，不等值约束g(x)=x1²+x2²−1，显然f(x)的极小值为原点(0,0)，落在可行域内。可行域以原点为圆心，半径为1。

极值点在内

极值点在约束域外

考虑目标函数f(x)=(x1−1.1)²+(x2+1.1)² ，不等值约束g(x)=x1²+x2²−1，显然f(x)的极小值为原点(1.1, -1.1)，落在可行域外。可行域以原点为圆心，半径为1。这种情况下我们的约束条件是有效的，因为极值点在约束域外，所以我们的取值不能取到全局的极值点，只能取到在约束域上的极小值。

极值点在外

我们可以总结一下不等式情况下有什么特点，我们可以发现，不管是极值点在约束域内亦或者是在约束域外，我们都会有这个关系

当极值点在约束域内的时候因为约束条件是没用的，所以我们应该让拉格朗日乘子等于0，如果极值点在约束域之外的时候存在g(x)=0。

KKT条件

上面哪个关系式子是我们将目标函数转换成为拉格朗日函数之后的一个限制条件，并且我们知道在不等式的两种情况下拉格朗日乘子都是>0的，同样的这也是拉格朗日函数的一个限制条件。如果在凸优化问题中这两个条件都满足那么我们求出来的极值点就是全局最小的极值点，如果不是凸优化问题那么上述条件只是必要条件不是充分条件，我们求解出来的可能不是全局极值点也可能是驻点。而我们上述的条件就是KKT条件

KKT条件

上述所有就是我们在求解SVM时候需要考虑的两个难点，过了这道坎之后SVM大概也完成了不到一半吧，后面还有一个SMO算法以及关于核函数的问题，任重而道远哦~