机器学习·SVM

SVM基本形式

因为是参考了两份资料，并且一开始比较有时间就把自己认为是向量的全部加粗了，后来添加的就懒得加粗，将就吧……

学习对象和目标

首先确定SVM研究的训练数据集：

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$

其中：

$$x_i\in\mathcal{X}=\mathbf{R}^n, y_i\in\mathcal{Y}=\{+1,-1\},i=1,2,\cdots,N$$

$x_i$是第$i$个特征向量，称为实例，$y_i$标记$x_i$为正例还是反例

SVM的目标：在特征空间中找到一个分界超平面，能将实例分类到不同的超平面

要得到的分界超平面：

$$\omega^*\cdot x+b^*=0$$

以及相应的决策函数：

$$f(x)=\text{sign}(\omega^*\cdot x+b^*)$$

函数间隔与几何间隔

$w\cdot x+b$为样本点到超平面的距离，可以表示分类预测的确信度，计算得到的符号与其类标记$y$的符号是否一致表示分类是否正确，由此定义样本点的函数间隔：

$$\hat{\gamma}_i=y_i(w\cdot x_i+b)$$

整个训练集的函数间隔：

$$\hat{\gamma}=\min_{i=1,\cdots,N}\hat{\gamma_i}$$

由于如果成比例地改变$w$和$b$，分离超平面实际上不会改变，而函数间隔却会改变，这是函数间隔的不足，对其规范化得到几何间隔

$$\gamma_i=y_i\left(\dfrac{w}{||w||}\cdot x_i+\dfrac{b}{||w||}\right)$$

整个训练集的几何间隔：

$$\hat{\gamma}=\min_{i=1,\cdots,N}\gamma_i$$

函数间隔与几何间隔之间的关系：

$$\gamma_i=\dfrac{\hat{\gamma_i}}{||w||}$$ $$\gamma=\dfrac{\hat{\gamma}}{||w||}$$

超平面之间的距离：

$$d=\dfrac{2}{\mathbf{w}^T\mathbf{w}}=\dfrac{2}{||w||}$$

间隔越大的SVM自然分类效果越好，通过上面的概念，很显然选择几何间隔进行最大化。

$$\max_{w,b}\gamma$$ $$s.t.\quad y_i\left(\dfrac{w}{||w||}\cdot x_i+\dfrac{b}{||w||}\right)\ge\gamma,\quad i=1,2,\cdots,N$$

找一组超平面的 𝒘, 𝒃使分类超平面间隔最大化：

$$\max\dfrac{2}{\mathbf{w}^T\mathbf{w}}\Rightarrow\max\dfrac{2}{\mathbf{w}^T\mathbf{w}}\Rightarrow\min\dfrac{1}{2}\mathbf{w}^T\mathbf{w}$$

得出SVM的基本形式：对于$n$个样本$(x_i, y_i),x_i\in\mathbb{R}^N, y_i\in\{+1,-1\}$

$$\min\dfrac{1}{2}\mathbf{w}^T\mathbf{w},$$ $$s.t.\quad \mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})\ge1$$

这是SVM的硬间隔，但是在实际情况中，可以设置一些容忍度提高模型的泛化能力，即

$$\mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})\ge1-\xi_i,\quad\xi_i\ge0$$

但是软间隔也不应太大，引入一个惩罚系数平衡模型的“软硬程度”，由此得出SVM的另一个形式：

对于$n$个样本$(x_i, y_i),x_i\in\mathbb{R}^N, y_i\in\{+1,-1\}$

$$\min\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_i\xi_i$$ $$s.t.\quad \mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})\ge1-\xi_i,\quad\xi_i\ge0$$

*凸优化

凸优化问题：指约束最优化问题：

$$\min_wf(w)$$ $$s.t.\quad g_i(w)\le0,\quad i=1,2,\dots,k\qquad h_i(w)=0,\quad i=1,2,\dots,l$$

其中，目标函数$f(w)$和约束函数$g(w)$都是$\mathbf{R}^n$上连续可微的凸函数，约束函数$h_i(w)$是$\mathbf{R}^n$上的仿射函数

当目标函数为二次函数，约束函数$g(w)$是仿射函数时，为凸二次规划问题。

支持向量

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量，是使约束条件式等号成立的点，即

$$y_i(w\cdot x_i+b)-1=0$$

计算步骤

1. 构造并求解约束最优化问题：

   $$\min_{w,b}\dfrac{1}{2}||w||^2$$ $$s.t.\quad y_i(w\cdot x_i+b)-1\ge0,\quad i=1,2,\dots,N$$

2. 得到分界超平面

   $$\omega^*\cdot x +b^*=0$$

   分类决策函数

   $$f(x)=\text{sign}(\omega^*x+b^*)$$

拉格朗日对偶

原问题是有约束的凸优化问题，对这类问题可以采用拉格朗日乘子法处理。首先将原问题转化为一个与之等价的极小极大问题。

拉格朗日乘子是一种寻找多元函数在一组约束下的极值的方法，通过引入拉格朗日乘子，可将有d个变量和k个约束条件的最优化问题转化为具有d+k个变量的无约束优化问题。

SVM hard margin

对于线性可分的数据集，硬间隔SVM目标和约束条件：

$$\min\dfrac{1}{2}\mathbf{w}^T\mathbf{w},$$ $$s.t.\quad \mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})\ge1$$

构造拉格朗日函数

$$L(\mathbf{w}, \mathbf{b}, \alpha)=\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+\sum_i\alpha_i[1-\mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})]\quad s.t.\quad\alpha_i\ge0$$ $$\min_{\mathbf{w},\mathbf{b}}\dfrac{1}{2}\mathbf{w}^T\mathbf{w}=\min_{\mathbf{w},\mathbf{b}}\max_{\alpha}L(\mathbf{w}, \mathbf{b}, \alpha)$$

得到对偶问题：

$$\min_{\mathbf{w},\mathbf{b}}\max_{\alpha}L(\mathbf{w}, \mathbf{b}, \alpha)=\max_{\alpha}\min_{\mathbf{w},\mathbf{b}}L(\mathbf{w}, \mathbf{b}, \alpha)$$

经过一系列的推导……

$$L(\mathbf{w}, \mathbf{b}, \alpha)=\sum_i\alpha_i-\dfrac{1}{2}\sum_i\sum_j\alpha_i\alpha_j\mathbf{y}_i\mathbf{y}_j(\mathbf{x}_i^T\mathbf{x}_j),$$ $$s.t.\quad\alpha_i\ge0,\sum_i\alpha_i\mathbf{y}_i=0$$

得到

$$\max\sum_i\alpha_i-\dfrac{1}{2}\sum_i\sum_j\alpha_i\alpha_j\mathbf{y}_i\mathbf{y}_j(\mathbf{x}_i^T\mathbf{x}_j)$$ $$s.t.\quad\alpha_i\ge0,\sum_i\alpha_i\mathbf{y}_i=0$$

其中，$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_i)^T$​为拉格朗日乘子向量

最后可以得出$w^*$和$b^*$的解：

$$w^*=\sum^N_{i=1}\alpha^*_iy_ix_i$$ $$b^*=y_j-\sum^N_{i=1}\alpha^*_iy_i(x_i\cdot x_j)$$

由上述结论，分离超平面可以写成：

$$\sum^N_{i=1}\alpha_i^*y_i(x\cdot x_i)+b^*=0$$

分类决策函数可以写成：

$$f(x)=\text{sign}\left(\sum^N_{i=1}\alpha^*_iy_i(x\cdot x_i)+b^*\right)$$

总结(线性可分支持向量机学习算法)

输入：线性可分训练集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中$x_i\in\mathcal{X}=\mathbf{R}^n$，$y_i\in\mathcal{Y}=\{+1,-1\}$，$i=1,2,\cdots,N$；

输出：分离超平面和分类决策函数

1. 构造并求解约束最优化问题：

   $$\min_\alpha\dfrac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum^N_{i=1}\alpha_i$$ $$s.t.\sum^N_{i=1}\alpha_iy_i=0,\alpha_i\ge0,i=1,2,\cdots,N$$

   求得最优解$\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_i^*)^T$

2. 计算

   $$w^*=\sum^N_{i=1}\alpha_i^*y_ix_i$$

   并选择$\alpha^*$的一个正分量$\alpha^*_j>0$，计算

   $$b^*=y_j-\sum^N_{i=1}\alpha^*_iy_i(x_i\cdot x_j)$$

3. 求得分离超平面和分离决策函数

   $$w^*\cdot x+b^*=0$$ $$f(x)=\text{sign}(w^*\cdot x+b^*)$$

支持向量

训练集中对应于$\alpha^*>0$的样本点$(x_i,y_i)$的实例$x_i\in\mathbf{R}^n$称为支持向量。满足：

$$y_i(w^*\cdot x_i+b^*)-1=0$$

即$x_i$一定在间隔边界上

例题：训练集中正例点是$x_i=(3,3)^T,x_2=(4,3)^T$，负例点事$x_3=(1,1)^T$，求线性可分支持向量机

SVM soft margin

如果训练数据是线性不可分的，意味着某些样本点不能满足函数间隔大于等于1的约束条件，则需要修改硬间隔最大化称为软间隔最大化。这里引入松弛变量$\xi_i\ge0$使函数间隔加上松弛变量大于等于1，得出的下面的凸二次规划问题就是SVM软间隔的原始问题

$$\min\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_i\xi_i$$ $$s.t.\quad \mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})\ge1-\xi_i,\quad\xi_i\ge0$$

这里$C>0$称为惩罚参数，其值越大则对误分类的惩罚越大。

构造拉格朗日函数

$$L(\mathbf{w}, \mathbf{b}, \alpha)=\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_i\xi_i+\sum_i\alpha_i[1-\xi_i-\mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})]+\sum_i\mu_i(-\xi_i)\quad s.t.\quad\alpha_i\ge0$$ $$\min_{\mathbf{w},\mathbf{b},\xi}\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_i\xi_i=\min_{\mathbf{w},\mathbf{b}, \xi_i}\max_{\alpha, \mu}L(\mathbf{w}, \mathbf{b}, \alpha, \mu, \xi)$$

对偶问题

$$\min_{\mathbf{w},\mathbf{b}, \xi_i}\max_{\alpha, \mu}L(\mathbf{w}, \mathbf{b}, \alpha, \mu, \xi)=\max_{\alpha, \mu}\min_{\mathbf{w},\mathbf{b}, \xi_i}L(\mathbf{w}, \mathbf{b}, \alpha, \mu, \xi)$$

得到目标函数

$$\min_{\mathbf{w},\mathbf{b}, \xi_i}\max_{\alpha, \mu}L(\mathbf{w}, \mathbf{b}, \alpha, \mu, \xi)=\max_{\alpha, \mu}\min_{\mathbf{w},\mathbf{b}, \xi_i}L(\mathbf{w}, \mathbf{b}, \alpha, \mu, \xi)$$ $$s.t.\quad\alpha_i\ge0,\mu\ge0, \xi\ge0$$ $$L(\mathbf{w}, \mathbf{b}, \alpha)=\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_i\xi_i+\sum_i\alpha_i[1-\xi_i-\mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})]+\sum_i\mu_i(-\xi_i)$$

对拉格朗日函数的各参数求偏导，也就是求拉格朗日函数对各参数的极小得到：

$$\dfrac{\partial L}{\partial\mathbf{w}}=0\Rightarrow\mathbf{w}-\sum_i\alpha_i\mathbf{y}_i\mathbf{x}_i=0$$ $$\dfrac{\partial L}{\partial\mathbf{b}}=0\Rightarrow\sum_i\alpha_i\mathbf{y}_i=0$$ $$\dfrac{\partial L}{\partial\xi_i}=0\Rightarrow C-\alpha_i-\mu_i=0$$

结果为：

$$w=\sum^N_{i=1}\alpha_iy_ix_i$$ $$\sum^N_{i=1}\alpha_iy_i=0$$ $$C-\alpha_i-\mu_i=0$$

代入拉格朗日函数

$$\begin{equation} \begin{split} L(\mathbf{w}, \mathbf{b}, \alpha) & =\dfrac{1}{2}\mathbf{w}^T\mathbf{w}+C\sum_i\xi_i+\sum_i\alpha_i[1-\xi_i-\mathbf{y_i}(\mathbf{w}^T\mathbf{x}_i+\mathbf{b})]+\sum_i\mu_i(-\xi_i)\\ & =\sum_i\alpha_i-\dfrac{1}{2}\sum_i\sum_j\alpha_i\alpha_j\mathbf{y}_i\mathbf{y}_j(\mathbf{x}_i^T\mathbf{x}_j), \end{split} \end{equation}$$ $$s.t.\quad\alpha_i\ge0,\mu_i\ge0,\xi_i\ge0,\sum_i\alpha_i\mathbf{y}_i=0,C-\alpha_i-\mu_i=0$$

最后得到软间隔的形式

$$\max\sum_i\alpha_i-\dfrac{1}{2}\sum_i\sum_j\alpha_i\alpha_j\mathbf{y}_i\mathbf{y}_j(\mathbf{x}_i^T\mathbf{x}_j)$$ $$s.t.\quad C\ge\alpha_i\ge0,\mu_i\ge0,\xi_i\ge0,\sum_i\alpha_i\mathbf{y}_i=0$$

结论：

$$w^*=\sum^N_{i=1}\alpha_i^*y_ix_i$$ $$b^*=y_j-\sum^N_{i=1}y_i\alpha^*_i(x_i\cdot x_j)$$

分离超平面可以写成

$$\sum^N_{i=1}\alpha^*_iy_i(x\cdot x_i)+b^*=0$$ $$f(x)=\text{sign}\left(\sum^N_{i=1}\alpha^*_iy_i(x\cdot x_i)+b^*\right)$$

总结（线性支持向量机学习算法）

输入：训练集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中$x_i\in\mathcal{X}=\mathbf{R}^n$，$y_i\in\mathcal{Y}=\{+1,-1\}$，$i=1,2,\cdots,N$；

输出：分离超平面和分类决策函数

1. 选择惩罚参数$C>0$​，构造并求解凸二次规划问题

   $$\min_\alpha\dfrac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum^N_{i=1}\alpha_i$$ $$s.t.\sum^N_{i=1}\alpha_iy_i=0,0\le\alpha_i\le C,i=1,2,\cdots,N$$

   求得最优解 $\alpha^* = (\alpha_1^*,\alpha_2^*,\cdots,\alpha_i^*)^T$ 。

2. 计算 $w^*=\displaystyle\sum^M_{i=1}\alpha^*_iy_ix_i$

   选择$\alpha^*$的一个分量$\alpha^*_j$适合条件$0<\alpha^*_j<C$计算

   $$b^*=y_j-\sum^N_{i=1}y_i\alpha_i^*(x_i\cdot x_j)$$

3. 求得分离超平面

   $$w\cdot x+b^*=0$$

   分类决策函数

   $$f(x)=\text{sign}(w^*\cdot x+b^*)$$

   支持向量

   支持向量有多种情况：

条件	结论
若$\alpha^*_i<C$	则$\xi_i=0$，$x_i$落在间隔边界上
若$\alpha^*_i=C,0<\xi<1$	分类正确，$x_i$在间隔边界与分离超平面之间
若$\alpha^*_i=C,\xi=1$	$x_i$在分离超平面上
若$\alpha^*_i=C,\xi>1$	$x_i$在分离超平面上负例侧

Kernel Trick

核技巧是为了解决当前维度线性不可分的情况，使用核函数进行升维会获得更好的分类效果，直接给出形式

对于$n$个样本$(x_i, y_i),x_i\in\mathbb{R}^N, y_i\in\{+1,-1\}$

$$\max\sum_i\alpha_i-\dfrac{1}{2}\sum_i\sum_j\alpha_i\alpha_j\mathbf{y}_i\mathbf{y}_jK(x_i,x_j)$$ $$s.t.\quad C\ge\alpha_i\ge0,\mu_i\ge0,\xi_i\ge0,\sum_i\alpha_i\mathbf{y}_i=0$$

SMO(Sequential Minimal Optimization)

SMO算法是对SVM的优化

我们已经有了如下结论

$$\max\sum_i\alpha_i-\dfrac{1}{2}\sum_i\sum_j\alpha_i\alpha_j\mathbf{y}_i\mathbf{y}_jK(x_i,x_j)$$ $$s.t.\quad C\ge\alpha_i\ge0,\mu_i\ge0,\xi_i\ge0,\sum_i\alpha_i\mathbf{y}_i=0$$

如果每次都调整所有变量则过于复杂，可以每次只调整2个变量，固定其余的，不妨设

$$\alpha_1\mathbf{y}_1+\alpha_2\mathbf{y}_2=\mathbf{D},$$ $$\alpha_1=\dfrac{(\mathbf{D}-\alpha_2\mathbf{y}_2)}{\mathbf{y}_1}=\mathbf{y}_1(\mathbf{D}-\alpha_2\mathbf{y}_2),\quad\alpha_i\in[0,C]$$