SVM原理的简要梳理,包括了hard-svm,soft-svm,拉格朗日,对偶等知识点。

VC维

VC维指的是在线性分类模型中,最多可以划分的簇的个数,例如2D平面中VC维为3.

对于非线性的模型来说,VC维是无限大的。通常来说,VC维越大分类器的分类性能越灵活。

硬间隔SVM

在对数据进行分两类的时候,尽可能找一条最粗的分界线,即margin最大,这条线恰好能够对数据进行分割。在分界线边上的点即为支撑向量。

平面中任意一点到分界面的距离为:
$$
d(\mathbf{x})=\frac{|\mathbf{x} \cdot \mathbf{w}+b|}{\sqrt{|\mathbf{w}|_{2}^{2}}}=\frac{|\mathbf{x} \cdot \mathbf{w}+b|}{\sqrt{\sum_{i=1}^{d} w_{i}^{2}}}
$$
我们找到所有样本点距离分界面最近的距离,作为当前样本的margin:

image-20200226224459260
$$
\operatorname{margin} \equiv \underset{\mathbf{x} \in D}{\arg \min } d(\mathbf{x})=\underset{\mathbf{x} \in D}{\arg \min } \frac{|\mathbf{x} \cdot \mathbf{w}+b|}{\sqrt{\sum_{i=1}^{d} w_{i}^{2}}}
$$
为了使margin最大,达到最鲁棒的效果,调整w,b使:
$$
\underset{\mathbf{w}, b}{\operatorname{argmax}} \arg \min _{\mathbf{x} \in D} \frac{\left|b+\mathbf{x}_{i} \cdot \mathbf{w}\right|}{\sqrt{\sum_{i=1}^{d} w_{i}^{2}}}\\
\text { subject to } \forall \mathbf{x}_{i} \in D: y_{i}\left(\mathbf{x}_{i} \cdot \mathbf{w}+b\right) \geq 0
$$
即最大化最小间距,上式成立必须满足一个条件,即所有的点都必须在正确的分类。

由于$|xw + b|$的取值不会影响函数优化的结果,因此我们将它设为1,方便计算,即可得到:
$$
\begin{array}{l}{\underset{\mathbf{w}, b}{\operatorname{argmin}} \sum_{i=1}^{d} w_{i}^{2}} \ {\text { subject to } \forall \mathbf{x}_{i} \in D: y_{i}\left(\mathbf{x}_{i} \cdot \mathbf{w}+b\right) \geq 1}\end{array}
$$
上式即为硬间距SVM的表达式,通过计算出其中的w得到分界线的位置。

soft-SVM

在有些数据中,大部分数据都是可分的,但是可能存在一些噪点,使得数据整体不可分。因此我们需要加上一些tradesoff来解决这个问题,修改后的函数如下:

image-20200226232159974

image-20200226232318315

每一个样本点对应一个tradesoff,通过最小化tradesoff的方式,使误分样本尽量少,同时鲁棒性好

hinge loss

hinge loss是一个可导的函数,可视为是0-1loss的上界。

image-20200226233815693

对偶问题

拉格朗日乘子

拉格朗提乘子满足下面的变换关系:

image-20200227001235311

KKT条件:

image-20200227001334193

用拉格朗日乘子求解SVM问题:

image-20200227001418834

将偏导结果带回上式,得到对偶问题:

image-20200227001548912

核函数

由于有些数据是非线性,不可分的。在低维空间中无法分隔开,因此需要使用核函数,对数据进行升维,使得数据可分。

核函数的表达式如下:
$$
K\left(x_{i}, x_{j}\right)=\phi\left(x_{i}\right) \cdot \phi\left(x_{j}\right)
$$
因此可以整体替换掉点乘项,使用核函数对数据进行升维。因为函数仅仅需要点乘的结果,我们不需要直接写出从低维到高维的映射函数。

image-20200227003536399

常见的核函数如下:

image-20200227003606023

总结

以上便是SVM的主要内容,下次回忆SVM算法的时候,可以从点到直线的距离开始,然后入手,将hard,soft,maxmin,拉格朗日,对偶,KTT,偏导那些东西全部过一遍便可。