【机器学习】SVM和核函数

上了吴恩达教授在Coursera上的课程之后，在网上找到了他在斯坦福课程的资料CS229 。下面会结合这两个课程的资料，整理一篇笔记。

背景

从之前的逻辑回归的模型中，我们可以看到，如果一个样本越远离决策边界(Decision Boundary)，那么我们就越能确保这个样本被正确分类。所以一个比较好的决策边界是尽量能让所有样本到决策边界的距离最大。从下图中可以看到，如果margin越大，我们对样本的正确分类就越有信心。

SVM就是一种能帮你得到margin最大的决策边界的算法。

SVM数学推导

在接下来的推导中，定义$y^{(i)}\in\{-1,1\}$y(i)∈{−1,1}，而不是$y\in\{0,1\}$y∈{0,1}。首先定义函数间隔(functional margin) 为:
$\hat{\gamma}^{(i)}=y^{(i)}(w^{T}x^{(i)}+b)$γ^​(i)=y(i)(wTx(i)+b)

如果$y^{(i)}=1$y(i)=1，那么我们希望$w^{T}x^{(i)}+b$wTx(i)+b能是一个很大的正数，相反，如果$y^{(i)}=-1$y(i)=−1，那么$w^{T}x^{(i)}+b$wTx(i)+b需要是一个很小的负数，这样就能使得样本离决策边界越远，分类效果越好。因此，得到的functional margin $\hat{\gamma}$γ^​越大，分类效果越好。
对于一个样本集$S=\{(x^{(i)},y^{(i)});i=1,...n\}$S={(x(i),y(i));i=1,...n}，定义：
$\hat{\gamma}=\min_{i=1,...n}\hat{\gamma}^{(i)}$γ^​=i=1,...nmin​γ^​(i)

那么接下来讨论 几何间隔(geometric margin) 。

从上图中可以看到，向量$w$w一定是与超平面垂直的，我们取超平面上的任意两点$x_1,x_2$x1​,x2​，$x_1,x_2$x1​,x2​满足$wx_1+b=0$wx1​+b=0和$wx_2+b=0$wx2​+b=0，两式相减得到$w(x_1-x_2)=0$w(x1​−x2​)=0。因为向量$x_1-x_2$x1​−x2​肯定在超平面上，所以可以得到向量$w$w与这个超平面正交。
假设A为样本点，如何求A到超平面的几何间距$\gamma^{(i)}$γ(i)呢？假设点B是A到超平面的投影，那么向量B可以表示为$x^{(i)}-\gamma^{(i)}*\frac{w}{||w||}$x(i)−γ(i)∗∣∣w∣∣w​。而且由于B点位于决策边界上，所以：
$w^T(x^{(i)}-\gamma^{(i)}*\frac{w}{||w||})+b=0$wT(x(i)−γ(i)∗∣∣w∣∣w​)+b=0

得到$\gamma^{(i)}$γ(i)为：
$\gamma^{(i)}=(\frac{w}{||w||})^Tx^{(i)}+\frac{b}{||w||}$γ(i)=(∣∣w∣∣w​)Tx(i)+∣∣w∣∣b​

由于我们的样本是有正负之分的，综合正负样本可以得到：
$\gamma^{(i)}=y^{(i)}((\frac{w}{||w||})^Tx^{(i)}+\frac{b}{||w||})$γ(i)=y(i)((∣∣w∣∣w​)Tx(i)+∣∣w∣∣b​)

同时定义$\gamma=\min\limits_{i=1,...n}\gamma^{(i)}$γ=i=1,...nmin​γ(i)
从geometric margin的表达式可以看到，$w$w和$b$b的缩放对$\gamma$γ的值没有影响，所以我们可以把要求的最优化问题写成:
$\max_{y,w,b}\gamma\\ s.t.\space \space y^{(i)}(w^{T}x^{(i)}+b)\ge\gamma, i=1,...,n\\ ||w||=1$y,w,bmax​γs.t.  y(i)(wTx(i)+b)≥γ,i=1,...,n∣∣w∣∣=1
但这个问题并不是一个直接可解的优化问题。我们首先用functional matrix来代替geometric matrix：
$\max_{y,w,b}\frac{\hat{\gamma}}{||w||}\\ s.t.\space \space y^{(i)}(w^{T}x^{(i)}+b)\ge\hat{\gamma}, i=1,...,n$y,w,bmax​∣∣w∣∣γ^​​s.t.  y(i)(wTx(i)+b)≥γ^​,i=1,...,n

为了剔除$\hat{\gamma}$γ^​的影响，我们可以对$w$w和$b$b进行缩放，使得$\hat{\gamma}$γ^​为1.前面讨论过，对$w$w和$b$b同时缩放，并不会影响geometric function的大小，也不会影响最终的结果。
因此，上述问题可以简化成:
$\min_{w,b}\space \frac{1}{2}||w||^2\\ s.t. \space \space y^{(i)}(w^{T}x^{(i)}+b)\ge1, i=1,...,n$w,bmin​ 21​∣∣w∣∣2s.t.  y(i)(wTx(i)+b)≥1,i=1,...,n

现在我们把这个问题转换成能用已知的优化问题求解的形式了。

正则化

为了解决某些离散点存在使得我们没办法保证functional margin永远都等于1，所以我们为上式加上一个补偿因子$\xi$ξ.
$\min_{w,b}\space \frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i\\ s.t. \space \space y^{(i)}(w^{T}x^{(i)}+b)\ge1-\xi_i, \space i=1,...,n\\ \xi_i\ge0, \space i=1,...,n$w,bmin​ 21​∣∣w∣∣2+Ci=1∑n​ξi​s.t.  y(i)(wTx(i)+b)≥1−ξi​, i=1,...,nξi​≥0, i=1,...,n
其中 C是惩罚系数，即对误差的宽容度。C越高，说明越不能容忍出现误差,容易过拟合。C越小，容易欠拟合。

核函数

如果我们想要拟合一种比较复杂的情况，通常需要把样本映射到更高维，但如果样本量比较大的时候，模型就会变得很复杂，所以我们需要寻找一种新的表达方式。
对于给定的样本集$(x^{(1)},y^{1}),(x^{(2)},y^{2}),...,(x^{(m)},y^{(m)})$(x(1),y1),(x(2),y2),...,(x(m),y(m))
选取 $l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},...l^{(m)}=x^{(m)}$l(1)=x(1),l(2)=x(2),...l(m)=x(m)
然后计算$x$x和$l^{(i)}$l(i)之间的相似度，记作$f^{(i)}$f(i)
$f^{(i)}=similarity(x,l^{(i)})$f(i)=similarity(x,l(i))

其中$f^{(0)}=1$f(0)=1.
其中最常用的一种核函数就是高斯核函数。
高斯核函数计算相似度的公式为：
$f^{(i)}=similarity(x,l^{(i)})=exp(-\frac{||x-l^{(i)}||^2}{2\sigma^2})$f(i)=similarity(x,l(i))=exp(−2σ2∣∣x−l(i)∣∣2​)

原先的模型就变成了 $h=g(\theta^Tf)$h=g(θTf)

如果不用核函数，就是线性核，即$h=g(\theta^Tx)$h=g(θTx)
在用高斯核之前一定要先进行特征缩放。

当n很大，但m很小的时候，不建议用高斯核，因为样本量太少，不太好训练一个复杂的模型。
当n很小，但m很大时，也不建议用高斯核，因为高斯核算法训练地很慢。
只有当n比较小，m适中时，才推荐用高斯核。