SVM(1): Hard-SVM

支持向量机（Support Vector Machine）， 是一种解决分类和回归的经典机器学习模型。以解决分类问题为例，它的核心思想是，最大化输入向量到超平面的间隔。之前在 感知机 里面我们已经了解到其思想为找到一个超平面，来划分特征空间为正负空间，从而实现分类的目的（如下图）。

但是，这样的超平面不只一个，怎么来从中找到一个最优的超平面呢？ 如何评价超平面的优劣呢？这就是SVM解决分类问题的思想。

1. Hard-SVM

1.1 模型

SVM的思想，通俗来讲是，最大化 Margin(x), Margin(x)代表为，所有点到超平面距离中的最小距， 即 i = 1,2,3…,n
化为最优化的标准型为：

由于 y = 1 or -1， 且分类正确时 , 因此
这里假设，, 此时问题改写为：

由于我们可以等比例的修改 w和b是的， 变为 1， 这样做并不改变问题的解。同时，等同于，此时问题修改为：

由于该问题是典型的二次优化问题，可以采用优化工具包来解决，也可以转化为对偶问题解决。

2. 策略

如何求解式（1）中的二次优化问题，这里可以采用拉格朗日乘法来解决。采用拉格朗日乘法有一个前提，即该问题满足 KKT 条件

2.1 Dual Problem

优化问题的标准形式为:

这里引入广义拉格朗日乘法：

考虑x的函数

如果x不满足式（2）中的约束条件，即存在 或者 , 此时总存在 一个 或者 使得，

而当 x符合（2）中条件时，。

因此考虑极小化问题，

设：

则有：

当 优化问题的解满足 KKT条件时，

2.2 KKT条件

把下面的条件记作 KKT 条件：

证明：

2.3 模型求解

因此，原问题可以转化为对偶问题

求解：

1. 对 w，b 求偏导数并令其等于0

1. 将（4),(5）带入到(3)中，可得：

此时优化问题为:

1. 对G函数求极大值，即可得到解 ， 带入到 (4),(5) 可以求解出 。

2. 求解b, 易知存在 （可以使用反证法证明，若全部均为0，则 w为0，而w=0不是原始优化问题的解）。此时，有,可得 。

2.4 支撑向量

由2.3 第3、4步可知，如果只保留 对应的x,y，求得的结果w和b不变。 因此把这些向量称之为支撑向量，即 support vector。

reference

1. 统计学习方法. 李航. chapter 7
2. 机器学习. 周志华