SVM

2018-09-08 本文已影响0人习惯了千姿百态

原文：http://blog.pluskid.org/?p=682
$f(x)=w^Tx + b$
$f(x)=0$ 的时候，这就是分割两个不同类别的超平面方程。当 $f(x)>0$ ，我们把它归为一类，其对应的 $y=1$ ；当 $f(x)<0$ 时，归为另一类，其对应的 $y=-1$ 。所以新来一个样本，我们只要计算 $f(x)$ 的值，就可以将其归类。因为超平面会随着数据集的增长，会发生一些变化的，所以那些比较靠近超平面的点比较容易分错类。SVM就是用来找到一个超平面，使得那些最容易分错的点具有最大的可能性不被分错。

函数间隔functional margin:
$\hat{\gamma}=y(w^Tx+b)=yf(x)$
显然：
$\hat{\gamma}=\min_{i=1,...,m} \hat{\gamma}^{(i)}$
几何间隔geometrical margin:点到超平面的距离

几何间隔示意图

$x=x_0+\gamma\frac{w}{||w||}$
$x_0$ 是超平面上的点，满足 $f(x_0)=0$ ，带入超平面方程：
$\gamma=\frac{w^Tx+b}{||w||}=\frac{f(x)}{||w||}$
这里的 $\gamma$ 带符号，所以定义几何间隔为：
$\widetilde{\gamma}=y\gamma=\frac{\hat{\gamma}}{||w||}$
分类的目标函数定义为：
$\max \widetilde{\gamma}$
为了推导的方便，固定 $\hat{\gamma}=1$ ，所以得到新的目标函数：
$\max \frac{1}{||w||} \Leftrightarrow \min\frac{1}{2}||w||^2 \\ s.t.y_i(w^Tx_i+b)\ge1$
这是一个二次优化问题。

利用拉格朗日乘子来计算：
$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b)-1)$
然后令
$\theta(w)=\max_{\alpha_i\ge0}L(w,b,\alpha)$

$\theta(w) = \left\{ \begin{array}{} \frac{1}{2}||w||^2 & \textrm{if 满足约束条件}\\ \infty& \textrm{else} & \end{array} \right.$
所以我们只要求 $\theta(w)$ 的最小值即可：
$p^*=\min_{w,b}\theta(w)=\min_{w,b}\max_{\alpha_i\ge0}L(w,b,\alpha)$
$p^*$ 表示这个问题的最优值
根据拉格朗日对偶，kkt(省略10000字...)：
$d^*=\max_{\alpha_i\ge0}\min_{w,b} L(w,b,\alpha)$
现在我们只要求解第二个问题即可：
首先求 $\min_{w,b} L(w,b,\alpha)$ 这部分，让L分别关于w和b最小化：
$\begin{align} \frac{\partial {L}}{\partial w}=0 &\Rightarrow w=\sum_{i=1}^n \alpha_i y_i x_i \\ \frac{\partial {L}}{\partial b} = 0 &\Rightarrow \sum_{i=1}^n \alpha_i y_i = 0 \end{align}$
带回L得到：
$\begin{align} {L}(w,b,\alpha) &= \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j – b\sum_{i=1}^n\alpha_iy_i + \sum_{i=1}^n\alpha_i \\ &= \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{align}$
所以对偶问题就变成了：
$\begin{align} \max_\alpha &\sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t., &\alpha_i\geq 0, i=1,\ldots,n \\ &\sum_{i=1}^n\alpha_iy_i = 0 \end{align}$
由于之前推导得到 $w=\sum_{i=1}^n\alpha_iy_ix_i$ ,所以我们可以得到:
$\begin{align} f(x)&=\left(\sum_{i=1}^n\alpha_i y_i x_i\right)^Tx+b \\ &= \sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b \end{align}$
(<,>表示内积)
所有非 Supporting Vector 所对应的系数 α 都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。
（如果 $x_i$ 是支持向量的话，上式中红颜色的部分是等于 0 的（因为支持向量的 functional margin 等于 1 ），而对于非支持向量来说，functional margin 会大于 1 ，因此红颜色部分是大于零的，而 $α_i$ 又是非负的，为了满足最大化，αi 必须等于 0 。）

使用Kernel处理非线性问题：

比如这个数据集中，就无法使用线性方法来进行分类。
我们知道一条二次曲线的方程可以写成以下的形式：

a_1X_1 + a_2X_1^2 + a_3 X_2 + a_4 X_2^2 + a_5 X_1X_2 + a_6 = 0

如果我们构造另外一个五维的空间，其中五个坐标的值分别为

Z_1 = X_1\\Z_2=X_1^2\\Z_3=X_2\\Z_4=X_2^2\\Z_5=X_1X_2

那么在新的坐标系下可以写作：

\sum_{i=1}^5a_iZ_i + a_6 = 0

这就是我们熟悉的关于Z的超平面方程。

之前推导的分类函数：
$f(x) = \sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b$
使用Kernel后的函数：
$f(x) = \sum_{i=1}^n\alpha_i y_i \langle \phi(x_i), \phi(x)\rangle + b$
（ $\phi(X)$ 表示 $X$ 映射后的向量）
我们把两个向量在映射后得出的向量的内积称为核函数
所以，现在我们的分类函数为：
$\sum_{i=1}^n\alpha_i y_i \color{red}{\kappa(x_i,x)} + b$
其中 $\alpha$ 这样计算：
$\begin{align} \max_\alpha &\sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j \color{red}{\kappa(x_i, x_j)} \\ s.t., &\alpha_i\geq 0, i=1,\ldots,n \\ &\sum_{i=1}^n\alpha_iy_i = 0 \end{align}$
核函数分类：

多项式核 $\kappa(x_1,x_2) = \left(\langle x_1,x_2\rangle + R\right)^d$ ，显然刚才我们举的例子是这里多项式核的一个特例（R=1,d=2）。虽然比较麻烦，而且没有必要，不过这个核所对应的映射实际上是可以写出来的，该空间的维度是 $\binom{m+d}{d}$ ，其中 m 是原始空间的维度。
高斯核 $\kappa(x_1,x_2) = \exp\left(-\frac{\|x_1-x_2\|^2}{2\sigma^2}\right)$ ，这个核就是最开始提到过的会将原始空间映射为无穷维空间的那个家伙。不过，如果 σ 选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果 σ 选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数 σ ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。
线性核 $\kappa(x_1,x_2) = \langle x_1,x_2\rangle$ ，这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了。
对于非线性的情况，处理的方式：先选择一个核函数 $\kappa(\cdot,\cdot)$ ,将低维向量映射到高维空间

SVM

猜你喜欢

热点阅读