支持向量机

对于一个线性分类问题，有数据, 即有N个数据样本需要分类，每个样本为维向量，取值为
上一节将支持向量机模型转化为如下凸二次规划问题
通常，当比较小的时候，可以直接交给库函数来求解。但是当很大或者引入核方法后，可能会导数样本维度为巨大甚至为无穷大，此时可以通过拉格朗日乘子法引入其对偶问题来求解。
通过求解对偶问题得到原始问题的最优解，就是支持向量机的对偶算法。采用对偶算法，有优点：
  • 对偶问题一般更容易求解
  • 自然引入核函数，进而推广到非线性分类问题。

原优化问题的对偶问题

首先构造其拉格朗日函数，为此，对每一个不等式约束引入拉格朗日乘子, I = 1,2,..,N, 拉格朗日函数如下：
这时，原优化问题就等价于如下无约束问题：
原问题和以上无约束问题为什么等价？理解如下（逻辑理解，非数理证明）
原问题对于的约束为 . 观察约束问题的 部分
如果不满足原始问题约束，则有,此时无约束优化问题没有意义，因为
如果满足原始问题的约束，则有.，此时：
综上，无约束问题等价于如下
所以，虽然无约束问题没有对进行显式的约束，但是已经把不满足原始问题的约束的给去掉了。
上述无约束问题（P）的对偶问题（D）为如下极大极小问题：
所以，为了得到对偶问题的解，需要先对对求极小，再求对的极大。
  1. 求
      2. 将拉格朗日函数分别对求偏导并令其为0。
      先对进行化解，如下：
      对求偏导如下：
      令偏导为0,则有
      将求得的w（式(4)）带入拉格朗日函数（式）,并利用式(5)，可得
      即
  1. 求对的极大，即对偶问题
      2. 将上式子的目标函数由求极大转换为求极小，就得到下面与之等价的对偶最优化问题
考虑原始最优化问题 (1) (3) 和对偶优化问题（8)。原始优化问题与对偶问题为强对偶关系。所以存在, 使得是原问题的解，为对偶问题的解。这意味着求解原始问题(1)(3)可以转换为求解对偶问题(8)。此外因为是强对偶关系，所以满足KKT条件（强对偶与KKT条件为充要关系）。
假设对偶问题最优化问题对的解为，那么可以由根据KKT条件求得原始最优化问题对的解如下，其中为任意一边界上的数据点。
证明 KKT条件如下：
由条件(9)得
由条件(11)可得，必定存在，（证明：用反证法，假设, 由式(9)可知, ，但不是原优化问题的解，产生矛盾）对此有
对式(15)左右同乘y_k，因为y_k ^2 = 1，可得
将式(14)带入式(16)可得:
综上，分离超平面可写为：
分类决策函数可以写为：
分类决策函数只依赖于输入 和训练样本输入的内积
注可以发现， 均为输入数据的线性组合。
但根据互补松弛条件的推理:
可知只有边界上的点对应的 不为，非边界的点对应的均为，所以本质上， 是由边界上的点决定的。

总结

对于给定的线性可分训练数据集，可以首先求其对偶问题的解，再求得原始问题的解。从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法。
具体来看，SVM原始优化问题为凸二次规划问题，由拉格朗日对偶性将原始问题转为对偶问题，因为SVM原始优化问题为凸二次规划，所以原始问题与对偶问题满足强对偶关系，所以求得对偶问题的解即为原始问题的解。因为满足强对偶关系，进而满足kkt条件，所以求解对偶问题的时候，可以用 求出 。
notion imagenotion image