Peter教你谈情说AI | 11支持向量机(中)—用拉格朗日解决SVM原型

可视化约束条件对函数的约束

如果在三维直角坐标系中将 f ( x , y ) 做出图来——把 f ( x , y ) “画出图来”——会是一个三维空间的曲面——这样一个函数实际上表达了 x ， y ， z 三者之间的关系。

函数 f ( x , y ) 的约束条件为： g ( x , y ) = 0 。

那么，一个二维图形对一个三维图形的约束从何体现呢？如图：

在这个例子中，我们可以看到 f ( x , y ) 是存在极大值的，同时因为约束条件是 g ( x , y ) = 0 ，所以，如果我们要取如下目标的话：

对应点一定位于 g ( x , y ) = 0 投影到 f ( x , y ) 上之后形成的那条曲线上，比如上图中的点 B。尽管它不一定是 z = f ( x , y ) 的极大值，但却是符合约束条件 g ( x , y ) = 0 的极大值！

拉格朗日乘子法

目标函数转换：

上一节介绍了线性可分 SVM 的目标函数：

们可以再抽象一步，将其概括为：

这个约束条件其实可以写作：

因为不等式约束条件难度稍大，我们先从等式约束条件开始。

等式约束条件：

我们的目标函数变为：

现在我们在一张图中做出f(x,y)和g(x,y)的等高线（三维图形投影到二维平面后的结果），形如图：

绿线是g(x,y)的等高线，蓝线是f(x,y)的等高线。图中两条蓝线具体对应的函数分别是f(x,y)=d1和f(x,y)=d2。d1和d2是两个常数，对应上图中两个蓝圈对应的z轴坐标。此处d2<d1。

我们设红点的自变量值为

，则在红点处

的梯度与f(x,y)=d2在

处的切线垂直，

的梯度与g(x,y)=0在

处的切线垂直。

又因为f(x,y)=d2对应的蓝线与g(x,y)=0对应的绿线在

处是相切的。所以在

点处f(x,y)与g(x,y)的梯度，要么方向相同，要么方向相反。

所以，一定存在

，使得：

这时我们将 λ 称为拉格朗日乘子！

定义拉格朗日函数：

——其中 λ 是拉格朗日乘子。

拉格朗日函数把原本的目标函数和其限制条件整合成了一个函数。于是，原本有约束的优化问题，就可以转化为对拉格朗日函数的无约束优化问题了。

不等式约束条件

了解了约束条件是等式的情况，我们再来看约束条件是不等式的情况。

原命题如下：

首先，仍然构造拉格朗日函数：

令：

那么原命题就等价于：

拉格朗日对偶问题

现在我们已经把不等式的约束问题也转变为了一个p*的问题。

但仍然个很难解决的问题，因为我们要先解决不等式约束的max问题，然后再在w上求最小值。怎么办呢？如果能把顺序换一下，先解决关于w的最小值，在解决关于a的不等式约束问题就好了。即:

这个d*就是p*的对偶形式，也即原问题的对偶形式，可惜的是，对偶归对偶，却未必相等！因为:

这个不等式叫弱对偶性质（Week Duality），最大值中最小的一个，也要大于等于最小值中最大的一个。这个性质从常识上想想，也是可以理解的。同时，我们可以得到一个对偶间隙，即p*-d*。

在凸优化理论中，有一个Slater定理，当这个定理满足，那么对偶间隙就会消失，即：

此时称为强对偶性质（strong Duality）。幸运的是，我们这里满足Slater定理。