笔记——支持向量机
支持向量机
在 SVM 公式的推导中，优化问题的基本型是一个 凸二次规划问题，因此涉及到对偶问题与原问题等价性的论证。
Lagrange对偶问题
Q1：为什么要将原问题转换为对偶问题求解？
原问题往往难以求解，因为对偶问题总是个凹函数，因此转化为对偶问题则便于求解。
Q2：对偶问题的可行解是不是原问题的最优解？
对偶问题的可行解未必就是原问题的最优解。
Q3：满足什么条件时，对偶问题的最优解就是原问题的最优解？
当原问题满足 KKT 条件时，对偶问题的解就是原问题的最优解，否则得到的是次优解。
参考书籍：Boyd《凸优化》第五章
针对 Q1，为什么要将原问题转换为对偶问题求解？
这里首先定义相关的三个函数，原问题 f0，Lagrange 函数 L(x,λ,v)，Lagrange 对偶函数 g(λ,v)。
- 原问题
设原问题 f0的最优值为 p*。- Lagrange 函数
Lagrange函数 L(x,λ,v)是在原问题的基础上考虑其约束条件。- Lagrange 对偶函数
Lagrange 对偶函数g(λ,v)是 Lagrange 函数 L(x,λ,v)关于 x 取到的最小值，是一簇关于(λ,v)的仿射函数的逐点下确界，所以对偶问题总是凹的。对偶问题构成原问题的最优值 p* 的下界。
Lagrange 对偶函数和原函数的直观理解
- Lagrange 对偶函数和原函数的直观理解：最优值 p* 的下界
上图中，实线表示原目标函数 f0，虚线表示约束函数f1，可行集是图中两条垂直点线表示的区间[-0.46，0.46]，最优点(x*，p*)是图中的黑色圆点(-0.46，1.54)。点线表示一系列 Lagrange 函数 L(x,λ)，其中 λ取值分别为0.1，0.2，… ，1.0。每个 Lagrange 函数都有一个极小值，均小于原问题最优目标值 p*。因此对偶函数构成了原问题最优解 p* 的下界，根据原问题的不等式约束很容易验证。
下图是最优解和对偶函数 g 之间的关系，可以看到最优值 p* 和对偶函数的解之间是存在间隙的。
针对 Q2，对偶问题的可行解是不是原问题的最优解？
现在讲对偶问题。
- Lagrange 对偶问题
Lagrange 对偶问题是一个凸优化问题。从 Lagrange 函数能够得到的最好下界是什么？
上式的最优解(λ*,v*)称为对偶最优解或最优 Lagrange 乘子，记作 d*，是原问题最优值的最好下界。
因此原问题最优解 p* 和对偶问题最优解 d* 存在以下关系：
最优对偶间隙： p* - d*
弱对偶性：d* <= p*
强对偶性：d* = p*
因此，当对偶间隙存在时，对偶问题的最优解不是原问题的最优解。
针对Q3：满足什么条件时，对偶问题的最优解就是原问题的最优解？
现在讲 KKT 条件。
- KKT条件
满足 KKT条件的点就是原问题的最优解。设 x* 和(λ*,v*)分别是原问题和对偶问题的一对最优解，对偶间隙为0。因为L(x, λ*,v*)是 关于 x =x* 处取得的最小值，因此 x=x* 处的倒数为0，即
因此KKT 条件如下：
当原问题是个凸问题时，满足 KKT 条件的值也是原、对偶最优解，对偶间隙为0。- KKT条件和最优性的关系
当原问题是凸问题时，KKT 条件是强对偶性(最优性)的充分必要条件。
SVM 中的对偶问题
解释完凸问题的对偶问题及其最优性的关系，现在正式进入 SVM 问题中的对偶问题。
参考书籍：周志华《机器学习》第六章
下列公式是 SVM 的公式，这里称为原问题，现在是凸二次规划的形式。
考虑原问题的约束条件即添加约束条件的加权和，得到 如下的Lagrange 函数：
Lagrange 函数 是一个凹函数。令 L(w,b,α) 对 w 和 b 的偏导为 0 可得
代入 Lagrange 函数可得如下的对偶问题，仍是一个二次规划问题
解出α，求出 w和 b 即可得到最大间隔划分超平面：
至此，求解原问题的任务落到求解α。
满足 KKT 条件如下
即对于任意样本(xi,yi),总有αi=0，或 yif(xi)=1。
若αi=0，则样本对f(x)没有影响；
若αi>0，则 yif(xi)=1，所对应的样本点位于最大间隔边界上，是支持向量。
因此反映了支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
观察可知对偶问题的规模与样本规模是成正比的，会在实际任务中带来很大的开销，因此提出了 SMO 算法。