Machine LearningAI

初探支持向量机

由于 Ghost 博客对 LateX 的识别语法和标准的 LateX 语法有差异,为了更加通用性,所以以下文章中 LateX 公式可能出现乱码,如果出现乱码,不嫌弃的话可以在笔者的 Github 上看这篇无乱码的文章。笔者有空会修复这个乱码问题的。请见谅。

GitHub Repo:Halfrost-Field
Follow: halfrost · GitHub
Source: https://github.com/halfrost/Halfrost-Field/blob/master/contents/Machine_Learning/Support_Vector_Machines.ipynb

一. 引子

在逻辑回归中,我们的预测函数为:

$$h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}$$

对于每一个样本 (x,y) 而言(注意是每一个),其代价函数为:

$$
\begin{align*}
J(\theta)&=-(ylogh_\theta(x)+(1-y)log(1-h_\theta((x)))\
&=-ylog\frac{1}{1+e^{-\theta^Tx}}-(1-y)log(1-\frac{1}{1+e^{-\theta^Tx}})
\end{align*}\
$$

那么当 y=1 的时候, $J(\theta)=-ylog\frac{1}{1+e^{-\theta^Tx}}$ ,其代价函数的图像入左下图所示。

当 y=0 的时候, $J(\theta)=-(1-y)log(1-\frac{1}{1+e^{-\theta^Tx}})$ ,其代价函数的图像入右下图所示。

对于支持向量机而言,

$y=1$ 的时候:

$$cost_1(\theta^Tx^{(i)})=(-logh_\theta(x^{(i)}))$$

$y=0$ 的时候:

$$cost_0((\theta^Tx^{(i)})=((-log(1-h_\theta(x^{(i)})))$$

当 y=1 时,随着 z 取值变大,预测代价变小,因此,逻辑回归想要在面对正样本 y=1 时,获得足够高的预测精度,就希望 $z= \theta^Tx\gg 0 $ 。而 SVM 则将上图的曲线拉直为下图中的折线,构成了 y=1 时的代价函数曲线 $cost_1(z)$ :

当 y=1 时,为了预测精度足够高,SVM 希望 $\theta^Tx\geqslant 1$ 。

同样,在 y=0 时,SVM 定义了代价函数 $cost_0(z)$ ,为了预测精度足够高,SVM 希望 $\theta^Tx \leqslant -1$ :

在逻辑回归中,其代价函数是:

$$J(\theta)=min_{\theta} \frac{1}{m}[\sum_{i=1}^{m}{y^{(i)}}(-logh_\theta(x^{(i)}))+(1-y^{(i)})((-log(1-h_\theta(x^{(i)})))]+\frac{\lambda}{2m}\sum_{j=1}^{n}{\theta_j^2}$$

对于逻辑回归而言,其代价函数是有两项决定的,第一项是来自训练样本的代价函数,第二项是正则化项,这就相当于我们用最小化 A 加上正则化参数 $\lambda$ 乘以参数平方项 B,其形式大概是: $A+\lambda B$ 。这里我们是通过设置不同的正则参数 $\lambda$ 来达到优化的目的。但是在支持向量机这里,把参数提到前面,用参数 C 作为 A 的参数,以 A 作为权重。所以其形式是这样的: $CA+B$ 。

在逻辑回归中,我们通过正规化参数 $\lambda$ 调节 A、B 所占的权重,且 A 的权重与$\lambda$ 取值成反比。而在 SVM 中,则通过参数 C 调节 A、B 所占的权重,且 A 的权重与 C 的取值成反比。亦即,参数 C 可以被认为是扮演了 $\frac{1}{\lambda}$ 的角色。

所以 $\frac{1}{ m}$ 这一项仅仅是相当于一个常量,对于最小化参数 $\theta$ 是没有完全任何影响的,所以这里我们将其去掉。

支持向量机的代价函数为:

$$min_{\theta} C[\sum_{i=1}^{m}{y^{(i)}}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{j=1}^{n}{\theta_j^2}$$

有别于逻辑回归假设函数输出的是概率,支持向量机它是直接预测 y 的值是0还是1。也就是说其假设函数是这样子的:

$$h_{\theta}(x)=\left{\begin{matrix}
1,;;if; \theta^{T}x\geqslant 0\
0,;;otherwise
\end{matrix}\right.$$

二. Large Margin Classification 大间距分类器

支持向量机是最后一个监督学习算法,与前面我们所学的逻辑回归和神经网络相比,支持向量机在学习复杂的非线性方程时,提供了一种更为清晰、更加强大的方式。

支持向量机也叫做大间距分类器(large margin classifiers)。

假如我们有一个数据集是这样的,可以看出,这是线性可分的。但是有时候我们的决策边界就好像图中绿色线或者粉红色线一样,这样的决策边界看起来都不是特别好的选择。支持向量机就会选择黑色这一条决策边界。黑色这条边界相比之前跟正负样本有更大的距离,而这个距离就叫做间距(margin)。这也是为什么我们将支持向量机叫做大间距分类器的原因。

支持向量机模型的做法是,即努力将正样本和负样本用最大的间距分开。

$$min_{\theta} C[\sum_{i=1}^{m}{y^{(i)}}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{j=1}^{n}{\theta_j^2}$$

当 y=1 时,SVM 希望 $\theta^Tx\geqslant 1$ 。在 y=0 时,SVM 希望 $\theta^Tx \leqslant -1$,对于前面的那一项 A 最小化代价函数,那么最理想当然是为0。所以这就变成了:

$$min_{\theta}\frac{1}{2}\sum_{i=1}^{n}{\theta_j^2};;;;;; \left{\begin{matrix}
\theta^Tx\geqslant 1,if ;y^{(i)}=1 \
\theta^Tx\leqslant 1 ,if ;y^{(i)}=0
\end{matrix}\right.
$$

推导

以两个二维向量为例,我们把向量 v 投影到向量 u 上,其投影的长度为 p,$\left | u \right |$ 为向量 u 的模,那么向量的内积就等于$p*\left | u \right |$。在代数定义向量内积可表示为: $u_1v_1+u_2v_2$ ,根据此定义可以得出: $u^Tv=u_1v_1+u_2v_2$ 。

$\left | u \right |$为 $\overrightarrow{u}$ 的范数,也就是向量 $\overrightarrow{u}$ 的欧几里得长度。

最小化函数为: $$min_{\theta}\frac{1}{2}\sum_{i=1}^{n}{\theta_j^2}$$

这里以简单的二维为例:

$$min_{\theta}\frac{1}{2}\sum_{i=1}^{n}{\theta_j^2}=\frac{1}{2}(\theta_1^2+\theta_2^2)=\frac{1}{2}(\sqrt{\theta_1^2+\theta_2^2})^2=\frac{1}{2}\left | \theta \right |^2$$

毕达哥拉斯定理:

$$ \left | u \right | = \sqrt{u_{1}^{2} + u_{2}^{2}}$$

只要 $\theta$ 能最小,最小化函数就能取到最小。

当垂直的时候 $\theta$ 取最小值。这就解释了为什么支持向量机的决策边界不会选择左图绿色那条。因为方便理解所以 $\theta_0=0$ ,这就意味着决策边界要经过原点。然后我们可以看到在垂直于决策边界的 $\theta $和 $x^{(i)}$ 的关系(红色投影和粉红色投影),可以看到其投影 $p^{(i)}$ 的值都比较小,这也就意味着要 $||\theta||^2$ 的值很大。这显然是与最小化公式 $\frac{1}{2}||\theta||^2$ 矛盾的。所以支持向量机的决策边界会使 $p^{(i)}$ 在 $\theta$ 的投影尽量大。这就是为什么决策边界会是右图的原因,也就是为什么支持向量机能有效地产生最大间距分类的原因。