凸优化基础
拉格朗日对偶性 – 原问题
对于上述约束化问题首先引入拉格朗日函数 ( 将等式和不等式约束融入到一个目标函数中去，从而只用一个函数表达我们的问题。)：
与原问题等价，即有相同的解。（因为当趋向无穷时，问题无解，因此必须 满足约束条件）。
广义拉格朗日函数的极小极大问题：
拉格朗日对偶性 – 对偶问题
- 构建关于α 和 β 的函数：
- 则其极大化问题称为广义拉格朗日函数的极大极小问题
- 将其表示为约束最优化问题，称为原始问题的对偶问题
原问题与对偶问题之间的关系
- 弱对偶性：若原始问题与对偶问题都有最优解，则对偶问题最优解与原问题最优解具备以下关系
- 强对偶性：满足 d*= p*
- 强对偶是一个非常好的性质，因为在强对偶成立的情况下，可以通过求解对偶问题来得到 原始问题的解，在
SVM中就是这样做的。 - 当然并不是所有的对偶问题都满足强对偶性 ，在
SVM中是直接假定了强对偶性的成立， 其实只要满足一些条件，强对偶性是成立的，比如说KKT条件。
线性可分支持向量机
线性可分SVM
设有如下两类样本的训练集：
线性可分情况意味着存在超平面，使训练点中的正类和负类样本分别位于该超平面的两侧。
如果能确定这样的参数对(w , b ) 的话，就可以构造决策函数来进行识别新样本。
硬间隔最大化
存在的问题：这样的参数对(w , b )有许多。
解决办法是采用最大间隔原则：即选择使得训练集 D 对于线性函数 w ⋅ x + b 的几何间隔取最大值的参数对(w , b )，并由此构造优化问题。
目标函数：
约束条件：
基于对偶的线性可分SVM学习算法
构建拉格朗日对偶函数：
可以得到：
(2) 将结果代入拉格朗日函数中，整理后可得：
根据拉格朗日对偶性，原问题的对偶问题是极大极小问题：
对偶问题：
(4) 求解上述问题可得到最优的α ∗ ，进而求得w ∗ ， b ∗ ，最终获得分离超平面和分类决策函数：
分类超平面：
分类决策函数：
以上是推导过程，实际使用过程是这样的：
- 构造并求解最优化问题
- 求得分离超平面：
- 获得分类决策函数：
- 我们得到的原问题的对偶问题的目标函数为：
第一项为正则化项，第二项为模型精度。
- 如果x i 是支持向量的话，上式中y i ( w x + b ) − 1 = 0 (因为此向量到分类超平面的函数间隔为1)；
- 对于非支持向量来说，函数间隔会大于1，因此会有y i ( w x + b ) − 1 > 0 ，由于有约束条件α i ≥ 0 ，因此为了满足最大化，在最优解α ∗ 中，必须有α i = 0
- 结构风险最小化：目标函数第二项为模型精度，第一项为正则化项，有效保证稀疏性，以降低置信风险，因而
SVM是基于结构风险最小化的学习方法。
