CS229 Note3 SVM(2)

这一部分的内容：

• 使用拉格朗日对偶解决线性可分支持向量机的最优化问题。
• 当样本空间线性不可分时，将原始特征空间映射到高维特征空间，再使用线性支持向量机算法求解。核函数是用于解决空间映射后维度爆炸的问题的。
• 当样本空间存在特异点时，引入松弛变量减少算法对特异点的敏感性。
• 求解拉格朗日优化问题的有效算法：SMO算法

最优边缘分类器(线性可分支持向量机)

原始问题

寻找最优边缘分类器的原始问题

$$min_{\gamma,w,b}\frac{1}{2}||w^2|| \\ s.t. \quad y^{(i)}(w^Tx^{(i)}+b) \geq 1,i=1,...,m$$

约束条件可以被写为拉格朗日函数中的形式：

$$g_i(w)=-y^{(i)}(w^Tx^{(i)}+b)+1\leq0$$

考虑到KKT对偶互补条件$\alpha_ig_i(w)=0$，仅仅对于函数间距等于1的训练样本有$\alpha_i>0$.在下图中，最大间距分离超平面用实线表示。

有着最小间距的点是离决策边界最近的点，在上图中只有三个点存在于与决策边界平行的虚线上，因此，只有这三个训练样本对应的$\alpha_i$在优化问题中是非0的，这三个点也叫做支持向量，这也是支持向量的数量远远小于训练样本数量的原因。

之所以列出优化问题的对偶形式，一个关键的思想是试图根据特征空间中点之间的内积形式($$)来构造算法,向量化的表示是$((x^{(i)})^Tx^{(j)})$，这正是接下来可以使用核技巧的关键。

现在根据优化问题构造拉格朗日函数：

$$\mathcal{L}(w,b,\alpha)=\frac{1}{2}||w^2||=-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]$$

没有$\beta_i$这个拉格朗日乘子，是因为没有不等约束条件。

对偶问题

考虑拉格朗日函数$\mathcal{L}(w,b,\alpha)$，首先将拉格朗日乘子$\alpha_i$看作常数，再对该函数进行最小化（固定$\alpha_i$后，求$w$和$b$的偏导为0）

$$\Delta_w\mathcal{L}(w,b,\alpha)=w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}=0 \\ w = \sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} \\$$ $$\frac{\partial}{\partial_b}\mathcal{L}(w,b,\alpha) = \sum_{i=1}^{m}\alpha_iy^{(i)}=0$$

将$w$的值代入原始问题，通过化简可以得到

$$\mathcal{L}(w,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)}.$$

上式最后一项为0，得到

$$\mathcal{L}(w,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}$$

现在对偶优化问题如下：

$$max_\alpha \quad W(\alpha) = \sum_{i=1}^m\alpha_i -\frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j<x^{(i)},x^{(j)}>. \\ s.t. \alpha \geq 0,i=1,...,m \\ \sum_{i=1}^m\alpha_iy^{(i)}=0$$

由于原始问题满足拉格朗日对偶问题中“存在$w^{\ast}$是原始问题的解,$\alpha^{\ast}$,$\beta^{\ast}$是对偶问题的解”的条件，因此求解原始问题可以转化为求解对偶问题。
假如我们能求解该优化问题，得到$\alpha^{\ast}$,那么$w^{\ast}=\sum_{i}\alpha_i^{\ast}y_ix_i$
这其中至少有一个$\alpha_j^{\ast}>0$,对此$j$有

$$y_j(w^{\ast}.x_j+b^{\ast})-1=0$$

将$w^{\ast}$的值代入上式，得到

$$b^{\ast}=y_j-\sum_{i=1}^{N}\alpha_i^{\ast}y_i<x_i,x_j>$$

上式是在《统计学习方法》中的计算方法，在CS229中，$b^{\ast}$的计算方法是

$$b^{\ast}=-\frac{max_{i:y^{(i)}=-1}{w^{\ast}}^Tx^{(i)}+min_{i:y^{(i)}=1}{w^{\ast}}^Tx^{(i)}}{2}$$

考虑在决策边界上，$b = -w^Tx$,因此分别假设间距最小的正样本或者负样本在决策边界上，再将他们对应的$b$取平均值，就是一个最合理的$b*$。
假如我们已经拟合出$\alpha$，现在要对一个新样本进行预估，那么就要计算

$$\sum_{i=1}^m\alpha_iy^{(i)}<x^{(i)},x>+b$$

由于只有支持向量的$\alpha_i$是非0的，因此我们其实只需要计算支持向量与样本之间的内积。接下来将核函数应用到支持向量机中，使其在高维空间中依然高效。

Kernels

特征空间的映射

之前所讨论的情况都是在训练样本线性可分的条件下进行的，如果训练样本如下图所示，要使用之前的线性可分支持向量机算法，就需要把当前特征空间映射到新的特征空间使训练样本线性可分。

在上图的二维空间中，决策边界可以用一个圆表示，其方程为

$$a_1X_1+a_2X1^2+a_3X_2+a_4X2^2+a_5X_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$$

上面的思路就是核方法处理非线性问题的基本思想。

通过映射$\phi(.)$将样本属性映射到一个高维空间中，使数据变得线性可分。但是映射空间的维度会随着原始空间的维度指数上升，还可能会出现新空间是无穷维导致无法计算的情况(高斯核函数)。此时就需要使用Kernel

核函数

假设有两个向量$x_1=(\eta_1,\eta_2)^T$和$x_2=(\xi_1,\xi_2)^T$,$\phi(.)$是之前所说的五维空间的映射。
这两个向量映射后的内积为：

$$<\phi(x_1),\phi(x_2)>=\eta_1\xi_1+\eta_1^2\xi_1^2+\eta_2\xi_2+\eta_2^2\xi_2^2+\eta_1\eta_2\xi_1\xi_2$$

另外

$$(<x_1,x_2>+1)^2=2\eta_1\xi_1+\eta_1^2\xi_1^2+2\eta_2\xi_2+\eta_2^2\xi_2^2+2\eta_1\eta_2\xi_1\xi_2+1$$

以上两个式子具有很多相似的地方，实际上如果把原始映射$\phi(.)$某几个维度线性缩放,再加上一个常数维度，定义为$Z_1=\sqrt2 X_1$,$Z_2=X_1^2$,$Z_3=\sqrt2 X_2$,$Z_4=X_2^2$,$Z_5=X_1X_2$,$Z_6=1$。这样定义映射之后。$<\phi(x_1),\phi(x_2)>$的内积与上式是相等的。他们的区别在于：定义映射$\phi(.)$后，需要将映射结果放到高维空间中计算内积，而$(+1)^2$就在原来的低维空间中进行计算，不需要知道映射$\phi(.)$。
所以在维度爆炸的情况下第一种方式无法计算，而第二种方法仍然能够从容处理。第一种的时间复杂度是$O(n^2)$,第二个的时间复杂度是$O(n)$,$n$为样本的属性数量。

计算两个向量在映射后空间中内积的函数叫做核函数(Kernel Function),在上面的例子中，核函数为:

$$K(X_1,X_2)=(<x_1,x_2>+1)^2$$

在支持向量机中正好有需要计算映射后空间中的内积的地方
在分类函数中：

$$\sum_{i=1}^{n}\alpha_iy_iK(x_i,x)+b$$

在优化对偶问题中的$\alpha$时：

$$max_\alpha \quad W(\alpha) = \sum_{i=1}^m\alpha_i -\frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_jK(x_i,x). \\ s.t. \alpha \geq 0,i=1,...,m \\ \sum_{i=1}^m\alpha_iy^{(i)}=0$$

通过运用核函数，就避免了空间映射时在高维空间中进行计算，但是计算结果却是等价的。

常用核函数

• 多项式核函数$K(x_1,x_2)=(+R)^d$，映射后的空间维度是$\bigl( \begin{smallmatrix} m+d \\ d \end{smallmatrix} \bigr)$,$m$是原始空间的维度
• 高斯核函数$K(x_1,x_2)=exp(-\frac{||x_1-x_2||^2}{2\sigma^2})$，当$\sigma$取值大，高次特征权重衰减很快，实际上映射的是一个低维子空间，反过来$\sigma$取值小时，可以将任意数据线性可分，但是会带来过拟合问题。
• 字符串核函数

正定核

如果一个核函数能够符合特征映射$\phi(.)$，那么它的Kernel martix K是一个半正定对称矩阵，$K_{ij}=K(x^{(i)},x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)})=\phi(x^{(j)})^T\phi(x^{(i)})=K(x^{(j)},x^{(i)})$

线性支持向量机与软间隔最大化

现实情况中，训练数据中会有一些特异点(outlier)，这些特异点去除后，剩下的样本点组成的几何是线性可分的。
这些特异点的存在会使样本点线性不可分，因为他们不满足最优边缘分类器$y^{(i)}(w^Tx^{(i)}+b) \geq 1,i=1,…,m$的约束条件。因此对每个样本点引入松弛变量$\xi_i\geq0$，使函数间隔加上松弛变量大于等于1，这样约束条件变为：

$$y_i(w.x_i+b)\geq1-\xi_i$$

对于每个松弛变量$\xi_i$，在优化问题中支付一个代价$\xi_i$，目标函数由$\frac{1}{2}||w||^2$变为:

$$\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i$$

C值大时，对误分类的惩罚大，该优化目标的含义有两层：即使间隔尽量大并且误分类的点的个数尽量小。对于存在特异点的样本集，这种方法称为软间隔最大化。

原始问题

$$min_{w,b,\xi} \quad \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i \\ s.t. \quad y_i(w.x_i+b) \geq 1-\xi_i, i=1,..,N \\ \xi_i \geq 0 \quad i=1,2,...,N$$

可以证明$w$的解是唯一的，但是$b$的解不唯一，存在于一个区间。

对偶问题

通过构造拉格朗日函数求极大极小问题，得到对偶问题

$$min_\alpha \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i.x_j)-\sum_{i=1}^N\alpha_i \\ s.t. \sum_{i=1}^N \alpha_iy_i = 0 \\ 0 \leq \alpha_i \leq C, i=1,2,...,N$$

求得最优解$\alpha^{\ast}$后,计算$w^{\ast}=\sum_{i=1}^N\alpha_iy_ix_i$，再选择一个合适的分量$\alpha_j$,计算$b^{\ast}=y_j-\sum_{i=1}^Ny_i\alpha_i^{\ast}$。最后得到分离超平面。

序列最小优化算法(SMO)

支持向量机问题可以形式化为求解凸二次规划问题，具有全局最优解，但是当训练样本很大时，很多优化方法都很低效，SMO算法就是一种快速求解拉格朗日对偶问题最优解$\alpha^{\ast}$的算法。

基本思路：每次选择两个$\alpha$的分量作为变量，其余分量作为固定的量，构建一个二次规划问题，该问题关于这两个分量的解会更接近于原始问题中这两个分量的解，因为这两个分量会使对偶问题的函数值越来越小，使整体越来越接近满足KKT条件。重要的是这样分解出来的问题能够通过解析方法求解，所以可以大大提高速度，子问题有两个变量，一个是违反KKT条件最严重那个$\alpha$的分量，另一个变量由优化问题的约束条件自动确定，因此不断将该问题分解为子问题求解，可以逐步求出$\alpha$的。

SMO算法包括两部分：求解子问题的解析方法与及选择子问题合适变量的启发式方法。

求解子问题的解析方法

基本思路：
由于选择了两个分量$\alpha_1,\alpha_2$作为变量，可以从约束条件$\sum_{i=1}^N\alpha_iy_i=0$得到：

$$\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^{N}y_i\alpha_i=\varsigma$$

在以$\alpha_1,\alpha_2$为变量的平面上，上式是一条斜率为1或者-1的直线

另外，$\alpha_2$本身处于$[0,C]$区间内，加上$\alpha_2$在一条直线上，运用线性规划的值，可以进一步细分$\alpha_2$的取值范围。

现在先求解出没有对$\alpha_2$进行取值范围约束时的解(将$\alpha_1$用$\alpha_2$表示，代入目标函数子问题，对$\alpha_2$求导置为0，解得此时$\alpha_2$的值)。

最后与约束条件进行比较，确定$\alpha_2$的值,再确定$\alpha_1$的值

变量的选择方法

• 选择第一个变量：外层循环，首先检验支持向量是否满足是否满足KKT条件，如果都满足，再遍历整个训练集，检验他们是否满足。
• 选择第二个变量：内层循环，假设已经找到不满足KKT条件的$\alpha_1$，寻找第二个变量$\alpha_2$的标准是希望$\alpha_2$的有足够大的变化($\alpha_2$的变化越快，$\alpha_1$的变化也越快，也越接近于最优解)，这里$\alpha_2$的变化受$E_1-E2$影响(这是在前面求解$\alpha_2$过程中得到的)，$E_i=g(x_i)-y_i$,即预测值与真实值的差。有了以上度量$\alpha_2$变化的标准，就可以确定该选择谁作为$\alpha_2$了，
• 计算阈值$b$和差值$E_i$:每次优化子问题的两个变量后，都要更新$b$,对于$\alpha1和\alpha_2$,根据KKT条件，观察形式可以代入$E_1,E_2$求得$b_1^{new},b_2^{new}$，如果$\alpha_1^{new},\alpha_2^{new}$在区间(0,C),那么两个b是相等的(此时这两个点都是支持向量),如果$\alpha_1^{new},\alpha_2^{new}$为0或者C，那么两个b之间的书都符合KKT条件的阈值，此时选择它们的中点，完成变量的优化后，还要更新对应的$E_i$，避免之后重复计算。

参考内容

• 核函数部分
• 《统计学习方法》