SVM中文叫做支持向量机,是一种监督学习方法,旨在找到具有最大几何间隔的分隔超平面,也就是找到一个线性或者非线性的分类器.原始版本的SVM线性分类器,由Vapnik在1963年提出,1992他又通过核方法引入了非线性分类器的可能.支持向量指的是离分隔超平面最近的点,我们下面会深入.
根据Novikoff定理 给一组线性可分的带标签的数据集,感知机算法的错误边界是$ \frac{R^2}{\gamma ^2}$,其中$R,\gamma $分别为数据集中元素的长度的最大值和数据集中元素到分割超平面的最小几何距离.
通俗地讲,一组带标签的d维数据线性可分.比如一组2维向量带有"正""负"的标签,分布在在平面上,一条线完美得把所有的"正"点分在下面,"负"点分在上面,这条线是分割超平面.
$R$是数据点的最大长度,$\gamma$是数据点到分割超平面的最小几何距离,感知机算法最多在$ \frac{R^2}{\gamma ^2}$个数据上犯错或者经过这么多次迭代,这个距离叫做几何边界.在例子里面,$R$就是数据点到原点的最大距离,$\gamma$就是数据点到那条线的最小距离.
所以,当我们面对一组(假设)线性可分的点序列时,最大化几何边界就可以最小化错误边界,就可以最小化经验风险.SVM方法最初就是对$\gamma$这个几何边界的凸优化方法.
我们这里介绍最基本的SVM算法,也就是假设算法可以完美区分训练集.给定一组带标签的数据集,${(\vec{x_i}, y_i)}_{i \in [1,n]}$,算法完美区分训练集便是$ y_i* (\vec{w} \vec{x_i} +b) >0, \forall i \in [1,n] $.
正如之前所说,SVM是一种最大化几何边界的算法.在满足训练集被完美区分的假设的约束下,最大化几何边界.数学上表示就是:
$ \max\limits_{\vec{w}, b} \min\limits_{i \in [1,n]} f(\vec{x_i}) = \max\limits_{\vec{w}, b} \min \limits_{i \in [1,n]}\frac{\vec{w} \vec{x_i} +b}{|\vec{w}|}$
$s.t. y_i* (\vec{w} \vec{x_i} +b) > 0, \forall i \in [1,n]$
可这样的目标函数不是凸函数,优化起来比较复杂.我们就换个思路,因为几何距离$\gamma$和函数距离 $\min\limits_{i \in [1,n]} f(\vec{x_i})$的关系是 $ \gamma = \frac{\min _{i \in [1,n]} f(\vec{x_i})}{|\vec{w}|}$,所以我们限定最小的函数距离为1,最小化$|\vec{w}|$,便是最大化几何边界.
但是$|\vec{w}|$既不凸也不可微函数,我们用$\frac{1}{2}* |\vec{w}|^2$来替换.这里的$\frac{1}{2}$是为了让导数的系数为1.
数学上写成
$ \min\limits_{\vec{w}, b} \frac{1}{2}*|\vec{w}|^2$
$ s.t. y_i* (\vec{w} \vec{x_i} +b) \geq 1 , \forall i \in [1,n]$
这是带有等式约束和不等式约束的凸优化,并且满足KKT条件,所以我们得到一个拉格朗日函数:
$L(\vec{w}, b, \vec{\alpha}) = \frac{1}{2}*|\vec{w}|^2 - \displaystyle{\sum_{i=1}^{n}} {\alpha_i * ( y_i* (\vec{w} \vec{x_i} +b) -1})$
分别对$\vec{w}, b$求偏导,得到
$\frac{\partial L}{\partial \vec{w}} = 0 \implies \vec{w} = \sum \limits_{i =1}^n {\alpha_i * y_i* \vec{x_i} }$
$\frac{\partial L}{\partial b} = 0 \implies \sum \limits_{i =1}^n {\alpha_i * y_i} = 0$
我们可以求出 $\vec{w}, b$.进而得到分类函数
$f(\vec{x}) =(\sum \limits_{i =1}^n {\alpha_i * y_i* \vec{x_i} })^T \vec{x} +b =\sum \limits_{i =1}^n {\alpha_i * y_i* <\vec{x_i}, \vec{x} >} +b $,其中$<\vec{x_i}, \vec{x} >$为两个向量的积.
In [ ]: