V 支持向量机

以下内容参考《机器学习》周志华（西瓜书）以及《机器学习公式详解》datawhale（南瓜书）

支持向量

给定训练样本D，分类学习最基本的想法就是基于训练集D，在样本空间中找到一个划分超平面，将不同类别的样本分开。

问题在于：选择什么样的超平面？

直观上，中间的超平面鲁棒性最强

超平面可以表示为：

$w^Tx+b = 0, 其中w为法向量，b为位移项（超平面与原点之间的距离）。$

$样本空间中任意点x到超平面（w,b）的距离可以写为：r=\frac{|w^T+b|}{\|w\|}$ .

如果超平面能够将样本正确分类，y值为正负1，对于正样本有 $w^Tx_i+b > 0$ ，负样本 $w^Tx_i+b < 0$ , 所以存在缩放，成立：

$\left\{ \begin{array}{**r**} w^Tx_i+b\geq+1, y_i=+1 \\ w^Tx_i+b\leq -1, y_i=-1 \end{array} \right.$

使的等式成立的样本称为支持向量，两个异类支持向量到超平面的距离： $\gamma = \frac{2}{\|w\|}$ ,称为间隔。

支持向量与间隔

于是，找到最大间隔，也即：

$\max_{w,b} \frac{2}{\|w\|},\\s.t.\qquad y_i(w^Tx_i+b)\geq1,i=1,2,...,m$

等价于

$\min_{w,b} \frac{1}{2}\|w\|^2 \\s.t.\qquad y_i(w^Tx_i+b)\geq1,i=1,2,...,m$

称为SVM的基本型。

对偶问题

对于上式使用拉格朗日乘子法，得到

$L(w,b,\alpha) = \frac{1}{2}\|w\|^2+\sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b)),\alpha_i\geq0$

令L对w,b的偏导数为0，可转化为：

$\max_{\alpha}\sum_{I=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t. \qquad \sum_{i=1}^m\alpha_iy_i=0, \\\alpha_i\geq0,i=1,2,...,m$

解出 $\alpha$ 即可求出w,b，进而获取模型。

求解方法：SMO算法，避开问题规模正比于训练样本数的障碍。不断执行如下步骤直至收敛。

* 选取一对需要更新的变量 $\alpha_i、\alpha_j$

* 固定之外的参数，求解目标函数获得更新后的 $\alpha_i、\alpha_j$

由于KKT条件：

$\left\{ \begin{array}{**l**} \alpha_i\geq0; \\ y_if(x_i)-1\geq0;\\ \alpha_i(y_if(x_i)-1)=0. \end{array} \right.$

于是，对于任意的训练样本有： $\alpha_i =0 或y_if(x_i)=1$ ,前者对f没有影响，后者代表支持向量。

SMO算法：选择两变量对应样本之间的间隔最大，这样更新后能够对目标函数值带来更大的变化。

求出 $\alpha$ 后可以获取w，利用支持向量的平均值可以获取b

$b=\frac{1}{S}\sum_{s\in S}(y_s-\sum_{i\in S}\alpha_iy_ix_i^Tx_s)$

核函数

对于线性不可分的问题，可以将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间线性可分。利用 $\Phi(x)$ 作为映射，超平面可以记为： $f(x)=w^T\Phi(x)+b$ .

类似未做映射的SVM，可以得知计算w，b 需要 $\Phi(x_i)^T\Phi(x_j)$ ,设想函数 $\kappa(x_i,x_j) = <\Phi(x_i),\Phi(x_j)>=\Phi(x_i)^T \Phi(x_j)$ ,

于是可以得到 $f(x) = \sum_{i=1}^m\alpha_iy_i\kappa(x,x_i)+b$

$\kappa$ 即核函数。

什么样的函数可以做核函数？

一个对称函数，对应的核矩阵半正定，就能作为核函数使用。

注意，核函数可以通过组合得到：

1. 若 $\kappa_1、\kappa_2$ 为核函数，任意正数 $\gamma_1、\gamma_2$ ，线性组合 $\gamma_1\kappa_1+\gamma_2\kappa_1$ 为核函数；

2. 若 $\kappa_1、\kappa_2$ 为核函数，直积 $\kappa_1\otimes \kappa_2(x,z) = \kappa_1(x,z)\kappa_2(x,z)$ 为核函数；

2. 若 $\kappa_1$ 为核函数，对于任意 $g(x)$ , $\kappa(x,z) = g(x)\kappa_1(x,z)g(z)$ 是核函数。