机器学习实战_支持向量机（一）

支持向量机

支持向量机的思路和logistic回归的不同点：一个考虑局部（不关心已经确定远离的点），一个考虑全局（已经远离的点可能通过调整中间线使其能够更加远离）

Y∈{+1， -1}是样本的标签，分别代表两个不同的类。这里我们需要用这些样本去训练学习一个线性分类器（超平面）：f(x)=sgn(wTx + b)，也就是wTx + b大于0的时候，输出+1，小于0的时候，输出-1。sgn()表示取符号。而g(x) =wTx + b=0就是我们要寻找的分类超平面

也就是，对于任何一个正样本yi=+1，它都要处于超平面的一边，也就是要保证：y= wTx + b>=+1。对于任何一个负样本yi=-1，它都要处于超平面的另一边，也就是要保证：y = wTx + b<=-1。这两个约束，其实可以合并成同一个式子：yi (wTxi + b)>=1。

间隔:间隔表示距离划分超平面最近的样本到划分超平面距离的两倍,即
$$\gamma=2\min_i \frac{1}{\Vert w \Vert}\vert w^Tx_i+b \vert$$

线性支持向量机的目标是找到一组合适的参数(w, b), 在满足分割样本的条件下，使得上诉间隔最大
$$\max_{w,b} \min_i \frac{2}{\Vert w \Vert}\vert w^Tx_i+b \vert \\ \\ \\s.t. \quad y_i(w^T+b)>0, i=1,2,...,m$$

上面的优化问题十分复杂, 难以处理. 为了能在现实中应用, 我们希望能对其做一些简化, 使其变为可以求解的, 经典的凸二次规划 (QP) 问题

凸二次规划的优化问题是指目标函数是凸二次函数, 约束是线性约束的一类优化问题

支持向量机的缩放引理：若（w* ,b*）是上面优化问题的解，那么对任何的r>0,(rw*,rb*)仍是该问题的解。

由于对 (w, b) 的放缩不影响解, 为了简化优化问题,我们约束 (w, b) 使得
$$\min_i \quad \vert w^Tx_i+b \vert = 1$$

所以最后我们的优化目标可以等价为下面优化目标：
$$\min_{w,b} \quad \frac{1}{2}w^Tw \\ \\ \\s.t. \quad y_i(w^T+b)>0, i=1,2,...,m$$

推导证明：

这是一个凸二次规划问题，除了用解决QP问题的常规方法之外，还可以应用拉格朗日对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一是对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

基本推论定理

（完整证明过程要自己去了解拉格朗日子乘法和KKT条件）

线性支持向量推论

核函数

线性可分问题：既然在原始的特征空间$R^d$不是线性可分的, 支持向量机希望通过一个映射 $\phi$ :$R^d$ →
$R^{\widetilde{d}}$,使得数据在新的空间 $R^{\widetilde{d}}$ 是线性可分的.

令 $\phi$(x)代表将样本 x 映射到 $R^{\widetilde{d}}$中的特征向量,参数 w 的维数也要相应变为 $\widetilde{d}$维.

在上面的支持向量机对偶公式中，注意到，被映射到高维的特征向量总是以成对内积的形式存在，即 $\phi (x_i)^T\phi(x_j)$ ,如果先计算特征在$R^{\widetilde{d}}$ 空间的映射, 再计算内积, 复杂度是O($\widetilde{d}$) ,当特征被映射到非常高维的空间, 甚至是无穷维空间时, 这将会是沉重的存储和计算负担.

核技巧旨在将特征映射和内积这两步运算压缩为一步, 并且使复杂度由O($\widetilde{d}$)降为O($d$),即, 核技巧希望构造一个核函数 $\kappa (x_i,x_j) $ ,使得
$$\kappa(x_i,x_j)=\phi (x_i)^T\phi(x_j)$$
并且，$\kappa (x_i,x_j) $ 的计算复杂度是 O($d$) .