【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.对偶问题
我们希望求解
minw,b12‖w‖2s.t.yi(wTxi+b)⩾1,i=1,2,...,m来得到最大间隔划分超平面所对应的模型：
f(x)=wTx+b其中w,b是模型参数。注意到式(1.1)本身是一个凸二次规划(convex quadratic programming)问题，能直接用现成的优化计算包求解，但我们可以有更高效的办法。
“二次规划”相关内容见本文第2部分。
对式(1.1)使用拉格朗日乘子法可得到其“对偶问题”(dual problem)。具体来说，对式(1.1)的每条约束添加拉格朗日乘子αi⩾0，则该问题的拉格朗日函数可写为：
L(w,b,α)=12‖w‖2+m∑i=1αi(1−yi(wTxi+b))其中α=(α1;α2;…;αm)。令L(w,b,α)对w和b的偏导为零可得：
w=m∑i=1αiyixi 0=m∑i=1αiyi将式(1.4)代入式(1.3)，即可将L(w,b,α)中的w和b消去，再考虑式(1.5)的约束，就得到式(1.1)的对偶问题：
maxαm∑i=1αi−12m∑i=1m∑j=1αiαjyiyjxTixjs.t.∑mi=1αiyi=0αi⩾0,i=1,2,...,m关于“对偶问题”的讲解请见：对偶问题。
解出α后，求出w与b即可得到模型：
f(x)=wTx+b=m∑i=1αiyixTix+b从对偶问题式(1.6)解出的αi是式(1.3)中的拉格朗日乘子，它恰对应着训练样本(xi,yi)。注意到式(1.1)中有不等式约束，因此上述过程需满足KKT条件，即要求：
{αi⩾0yif(xi)−1⩾0αi(yif(xi)−1)=0于是，对任意训练样本(xi,yi)，总有αi=0或yif(xi)=1。若αi=0，则该样本将不会在式(1.7)的求和中出现，也就不会对f(x)有任何影响；若αi>0，则必有yif(xi)=1，所对应的样本点位于最大间隔边界上，是一个支持向量。⚠️这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
那么我们该如何求解式(1.6)，得到α呢？有两种方法：
- 这是一个二次规划问题，可使用通用的二次规划算法来求解。
- 使用更为高效的其他算法，例如SMO（Sequential Minimal Optimization）算法。
求出α后，可通过式(1.4)求得w的值。
如何确定偏移项b呢？注意到对任意支持向量(xs,ys)都有ysf(xs)=1，即：
ys(∑i∈SαiyixTixs+b)=1其中S={i∣αi>0,i=1,2,…,m}为所有支持向量的下标集。理论上，可选取任意支持向量并通过求解式(1.9)获得b，但现实任务中常采用一种更鲁棒的做法：使用所有支持向量求解的平均值：
b=1∣S∣∑s∈S(ys−∑i∈SαiyixTixs)2.二次规划
二次规划(Quadratic Programming，简称QP)是一类典型的优化问题，包括凸二次优化和非凸二次优化。在此类问题中，目标函数是变量的二次函数，而约束条件是变量的线性不等式。
假定变量个数为d，约束条件的个数为m，则标准的二次规划问题形如：
minx12xTQx+cTxs.t.Ax⩽b非标准二次规划问题中可以包含等式约束。注意到等式约束能用两个不等式约束来代替；不等式约束可通过增加松弛变量的方式转化为等式约束。
其中x为d维向量，Q∈Rd×d为实对称矩阵，A∈Rm×d为实矩阵，b∈Rm和c∈Rd为实向量，Ax⩽b的每一行对应一个约束。
若Q为半正定矩阵，则式(2.1)目标函数是凸函数，相应的二次规划是凸二次优化问题；此时若约束条件Ax⩽b定义的可行域不为空，且目标函数在此可行域有下界，则该问题将有全局最小值。若Q为正定矩阵，则该问题有唯一的全局最小值。若Q为非正定矩阵，则式(2.1)是有多个平稳点和局部极小点的NP难问题。
常用的二次规划解法有椭球法(ellipsoid method)、内点法(interior point)、增广拉格朗日法(augmented Lagrangian)、梯度投影法(gradient projection)等。
Gitalking ...
