机器学习（五）——SVM（1）

拉格朗日对偶（续）

上述约束优化问题也被称为原始优化问题（primal optimization problem）。为了求解这个问题，我们定义广义拉格朗日（generalized Lagrangian）函数：

L(w,α,β)=f(w)+∑i=1kαigi(w)+∑i=1lβihi(w)

利用这个函数可以将约束优化问题转化为无约束优化问题。其中的αi、βi也被称作拉格朗日乘子（Lagrange multiplier）。

θP(w)=maxα,β:αi≥0L(w,α,β)=maxα,β:αi≥0f(w)+∑i=1kαigi(w)+∑i=1lβihi(w)

其中，P代表原始优化问题，maxα,β:αi≥0表示在α,β变化，而其他变量不变的情况下，求最大值。

如果w不满足约束，也就是gi(w)>0或hi(w)≠0。这时由于L函数是无约束函数，αi、βi可以任意取值，因此∑i=1kαigi(w)或∑i=1lβihi(w)并没有极值，也就是说θP(w)=∞。

反之,如果w满足约束，则∑i=1kαigi(w)和∑i=1lβihi(w)都为0，因此θP(w)=f(w)。

满足约束不满足约束θP(w)={f(w),w满足约束∞,w不满足约束

我们定义：

p∗=minwθP(w)=minwmaxα,β:αi≥0L(w,α,β)

下面我们定义对偶函数：

θD(w)=minwL(w,α,β)

这里的D代表原始优化问题的对偶优化问题。仿照原始优化问题定义如下：

d∗=maxα,β:αi≥0θD(w)=maxα,β:αi≥0minwL(w,α,β)

这里我们不加证明的给出如下公式：

d∗=maxα,β:αi≥0minwL(w,α,β)≤minwmaxα,β:αi≥0L(w,α,β)=p∗

这样的对偶问题被称作拉格朗日对偶（Lagrange duality）。

https://mp.weixin.qq.com/s/IhvdhEnyRI2DRns9EkCy5Q

拉格朗日对偶理论

https://www.zhihu.com/question/58584814

如何通俗地讲解对偶问题？尤其是拉格朗日对偶lagrangian duality？

KKT条件

拉格朗日对偶公式中使p∗=d∗成立的条件，被称为KKT条件（Karush-Kuhn-Tucker conditions）：

∂∂wiL(w∗,α∗,β∗)=0,i=1,…,n∂∂βiL(w∗,α∗,β∗)=0,i=1,…,l(1)αi∗gi(w∗)=0,i=1,…,kgi(w∗)≤0,i=1,…,kαi∗≥0,i=1,…,k

其中的w∗,α∗,β∗表示满足KKT条件的相应变量的取值。条件1也被称为KKT对偶互补条件（KKT dual complementarity condition）。显然这些w∗,α∗,β∗既是原始问题的解，也是对偶问题的解。

严格的说，KKT条件是非线性约束优化问题存在最优解的必要条件。这个问题的充分条件比较复杂，这里不做讨论。

注：Harold William Kuhn，1925～2014，美国数学家，普林斯顿大学教授。

Albert William Tucker，1905～1995，加拿大数学家，普林斯顿大学教授。

William Karush，1917～1997，美国数学家，加州州立大学北岭分校教授。（注意，California State University和University of California是不同的学校）

https://mp.weixin.qq.com/s/AKTGyHlbCj0P949K-LAv6A

拉格朗日乘数法

https://www.zhihu.com/question/64834116

拉格朗日乘子法漏解的情况？

https://mp.weixin.qq.com/s/UyNpJZ7k_q1qVdcNhrzDcQ

直观详解：拉格朗日乘法和KKT条件

https://mp.weixin.qq.com/s/PELnlB5vMV0gGJbL6BzoIA

原始-对偶算法的设计原理

https://mp.weixin.qq.com/s/5655NgkxrbK3qtA4Ilxd4w

为何引入对偶问题

https://mp.weixin.qq.com/s/PRKEIW3HEafytUNscHSLpA

如何写对偶问题

针对最优边距分类问题，我们定义：

gi(w)=−y(i)(wTx(i)+b)+1≤0

由KKT对偶互补条件可知，如果αi>0，则gi(w)=0。

上图中的实线表示最大边距的分割超平面。由之前对于边距的几何意义的讨论可知，只有离该分界线最近的几个点（即图中的所示的两个x点和一个o点）才会取得约束条件的极值，即gi(w)=0。也只有这几个点的αi>0，其余点的αi=0。这样的点被称作支持向量（support vectors）。显然支持向量的数量是远远小于样本集的数量的。

为我们的问题构建拉格朗日函数如下：

(2)L(w,b,α)=12‖w‖2−∑i=1mαi[y(i)(wTx(i)+b)−1]θD(α)=minw,bL(w,b,α)∇wL(w,b,α)=w−∑i=1mαiy(i)x(i)=0(3)w=∑i=1mαiy(i)x(i)

对b求导可得：

(4)∂∂bL(w,b,α)=∑i=1mαiy(i)=0

把公式3代入公式2，可得：

L(w,b,α)=12‖w‖2−∑i=1mαi[y(i)(wTx(i)+b)−1]=12wTw−∑i=1mαiy(i)wTx(i)−∑i=1mαiy(i)b+∑i=1mαi=12wT∑i=1mαiy(i)x(i)−∑i=1mαiy(i)wTx(i)−∑i=1mαiy(i)b+∑i=1mαi=12wT∑i=1mαiy(i)x(i)−wT∑i=1mαiy(i)x(i)−∑i=1mαiy(i)b+∑i=1mαi=−12wT∑i=1mαiy(i)x(i)−b∑i=1mαiy(i)+∑i=1mαi=−12(∑i=1mαiy(i)x(i))T∑i=1mαiy(i)x(i)−b∑i=1mαiy(i)+∑i=1mαi=−12∑i=1mαiy(i)(x(i))T∑i=1mαiy(i)x(i)−b∑i=1mαiy(i)+∑i=1mαi(5)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj(x(i))Tx(j)−b∑i=1mαiy(i)

我们定义如下内积符号⟨x,y⟩=xTy，并将公式4代入公式5可得：

L(w,b,α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj⟨x(i),x(j)⟩

最终我们得到如下对偶优化问题：

maxαW(α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj⟨x(i),x(j)⟩s.t.αi≥0,i=1,…,m∑i=1mαiy(i)=0

这个对偶问题的求解，留在后面的章节。这里只讨论求解出α∗之后的情况。

首先，根据公式3可求解w∗。然后

b∗=−maxi:y(i)=−1w∗Tx(i)+mini:y(i)=1w∗Tx(i)2

除此之外，我们还有：

wTx+b=(∑i=1mαiy(i)x(i))Tx+b=∑i=1mαiy(i)⟨x(i),x⟩+b

在之前的讨论中，我们已经指出只有支持向量对应的αi才为非零值，因此：

wTx+b=∑i∈SVαiy(i)⟨x(i),x⟩+b

从上式可以看出，在空间维数比较高的情况下，SVM（support vector machines）可以有效降低计算量。

假设我们从样本点的分布中看到x和y符合3次曲线，那么我们希望使用x的三次多项式来逼近这些样本点。那么首先需要将特征x扩展到三维(x,x2,x3) ，然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射（feature mapping）。

映射函数记作ϕ(x)，在这个例子中

ϕ(x)=[xx2x3]

有的时候，我们希望将特征映射后的特征，而不是最初的特征，应用于SVM分类。这样做的情况，除了上面提到的拟合问题之外，还在于样例可能存在线性不可分的情况，而将特征映射到高维空间后，往往就可分了。如下图所示：

为此，我们给出核函数（Kernel）的形式化定义：

K(x,z)=ϕ(x)Tϕ(z)

之所以是形式化定义，这主要在于我们并不利用ϕ(x)来计算K(x,z)，而是给定K(x,z)，来倒推ϕ(x)，从而建立ϕ(x)和K(x,z)之间的对应关系。

K(x,z)=(xTz)2=(∑i=1nxizi)(∑i=1nxizi)=∑i=1n∑j=1nxixjzizj=∑i,j=1n(xixj)(zizj)

根据上式可得：（这里假设n=3）

ϕ(x)=[x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3]

可以看出ϕ(x)的计算复杂度是O(n2)，而(xTz)2的计算复杂度是O(n)。

下面我们讨论其他几种常用核函数和它对应的ϕ(x)。

K(x,z)=(xTz+c)2=∑i,j=1n(xixj)(zizj)+∑i=1n(2cxi)(2czi)+c2

同样的：（n=3）

ϕ(x)=[x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x32cx12cx22cx3c]

更一般的，对于K(x,z)=(xTz+c)d，其对应的ϕ(x)是(n+dd)维向量。

我们也可以从另外的角度观察K(x,z)=ϕ(x)Tϕ(z)。从内积的几何意义来看，如果ϕ(x)和ϕ(z)夹角越小，则K(x,z)的值越大；反之，如果ϕ(x)和ϕ(z)的夹角越接近正交，则K(x,z)的值越小。因此，K(x,z)也叫做ϕ(x)和ϕ(z)的余弦相似度。