SVM,指的是支持向量机(support vector machines)。

支持向量机,假设数据是线性可分的,那么我们就能找到一个超平面,将数据分成两类。但是一旦线性可分,我们就可能找到无数的超平面,都可以将数据分成两类:

但是很明显,上图中虽然a, c都对数据进行了有效的分割。但很明显,都不如b分割的好。

我们可以用“间隔”这个概念来定义这个超平面(在二维上是线)对数据的分割优劣。在分类正确的情况下,间隔越大,我们认为对数据的分类越好。

我们的目标是得到数据的分类:$y \in \lbrace -1, +1 \rbrace$。

这个超平面,则可以表示成$w^Tx+b$,其中$w=[\theta_1, \ldots, \theta_n]^T, b=\theta_0$。这个超平面可以表达成一个$n+1$维向量。

判别函数: $$ g(z)=\begin{cases} +1, & \text{如果$z\geq0$} \\ -1, & \text{otherwise} \end{cases} $$ 假设则可以表示成:$h_{w,b}(x)=g(w^Tx+b)$

间隔

函数间隔(functional margin)

某个超平面$(w,b)$和训练样本$(x^{(i)}, y^{(i)})$之间的函数间隔被表示成: $$ \hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b) $$ 于是,我们可以知道:

  1. 当$y^{(i)}=1$,于是我们想获得更大的函数间隔(这是我们的目标),就需要使得$w^Tx^{(i)}+b \gg 0$
  2. 相反,当$y^{(i)}=-1$,我们想获得更大的函数间隔,就需要使得$w^Tx^{(i)}+b \ll 0$

并且,很明显,只有当函数间隔$\hat{\gamma}>0$时,分类结果是正确的。

最后,超平面与数据集$\lbrace (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \ldots \rbrace$之间的函数间隔,被定义为所有函数间隔中的最小值: $$ \hat{\gamma}=\min_i\hat{\gamma}^{(i)} $$

几何间隔(geometric margin)

从点$(x^{(i)}, y^{(i)})$出发,对超平面做垂线,得到点D,我们知道他们之间的距离,就是该超平面到数据点$(x^{(i)}, y^{(i)})$的几何间隔。

经过推导,D的坐标可以表示为: $$ x^{(i)}-\gamma^{(i)}\frac{w}{||w||} $$ 又因为,D在超平面$w^Tx+b=0$上,所以: $$ \begin{align} & w^T(x^{(i)}-\gamma^{(i)}\frac{w}{||w||})+b=0 \\ & \Rightarrow w^Tx^{(i)}+b=\gamma^{(i)} \cdot \frac{w^Tw}{||w||}=\gamma^{(i)} \cdot ||w|| \\ & \Rightarrow \gamma^{(i)}=(\frac{w}{||w||})^T \cdot x^{(i)}+\frac{b}{||w||} \end{align} $$ 加上正负分类的判断: $$ \gamma^{(i)}=y^{(i)} \cdot ((\frac{w}{||w||})^T \cdot x^{(i)}+\frac{b}{||w||}) $$ 我们可以看到,几何间隔跟函数间隔之间存在如下的关系: $$ \hat{\gamma}^{(i)} = \frac{\gamma^{(i)}}{||w||} $$

同样的,超平面与数据集$\lbrace (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \ldots \rbrace$之间的几何间隔,被定义为所有几何间隔中的最小值: $$ \gamma=\min_i\gamma^{(i)} $$ 最后,我们导出最优间隔分类器Optimal Margin Classifier)问题:选择$w, b$,最大化$\gamma$,同时满足$\forall(x^{(i)}, y^{(i)})$,$ y^{(i)} \cdot ((\frac{w}{||w||})^T \cdot x^{(i)}+\frac{b}{||w||}) \geq \gamma$(所有数据点的几何间隔都大于该最小几何间隔)。

目前为止,已经是SVM问题的一个简化版本。


Copyright 2017-2019, All Rights Reserved.
粤ICP备18085907号 深圳市磐创网络科技有限公司

Documentation built with MkDocs.