SVM支持向量机

线性分类问题

对于一个二维线性可分的样本,往往分割开这些样本的直线有许多条,这些直线的样本内误差皆为零,但这些直线都一样好吗,这不尽然

![avatar][]

对于相同的样本点,直觉上会认为第三个分割线会更好,因为它具有更宽的间隔(绿色区域)

大间隔意味着对假设式进行约束,减少了假设空间,获得了更好的泛化能力

约束及目标

SVM最大间隔法是保持分割平面(约束)同时最大化间隔(优化目标)

名词转换

这里将\(x_0和w_0\)从之前的约定中提取出来,现在

\(\mathtt{w}=(w_1,…,w_d)\)

\(\mathtt{x}=(x_1,…,x_d)\)

\(\mathtt{y=sign(w^Tx+b)}\)

分割平面定义(约束)

分割的平面就是\(\mathtt{w^Tx}+b=0\)(一个平面由\(\mathtt{w}\)和b来定义)

分割平面要满足正确分类每一个样本点,也就是说对于任意样本点\(\mathtt{x_1,…x_n}\)(正正得正,负负得正)

\(y_n(\mathtt{w^Tx_n+b})>0\)

取特殊的一个值(\(\mathtt{x’}\)是距离分割平面最近的点)

\(\rho=\min\limits_{n=1,…,N}y_n\mathtt{(w^Tx’+b)},\rho>0\)

利用\(\rho\)对\(\mathtt{w,b}\)进行缩放得到相同的平面(\(b/\rho,\mathtt{w}/\rho\))

就如同\(2x+3y+z+1=0\)和\(4x+6y+2z+2=0\)是相同的平面,这里的缩放只是改变了信号\(y_n(\mathtt{w^Tx_n+b})\)的大小,对分类结果没有影响

\(\min\limits_{n=1,…,N}y_n\mathtt{(\frac{w^T}{\rho}x_n+\frac{b}{\rho})}=\min\limits_{n=1,…,N}\frac{1}{\rho}y_n\mathtt{(w^Tx_n+b)}=1\)

也就是说分割平面满足

\(\min\limits_{n=1,…,N}y_n\mathtt{(w^Tx_n+b)}=1\)

间隔距离(目标)

间隔定义为离分割线/平面/超平面(以下皆称为平面)最近的点到其的垂直距离

\(\mathtt{w}\)是垂直于分割平面(\(\mathtt{w^Tx}+b=0\))的,证明如下:

对于平面上任意的两点\(\mathtt{x’,x’’}\)

\(\mathtt{w^Tx’}+b=0\),\(\mathtt{w^Tx’’}+b=0\)

两者相减 \(\mathtt{w^T(x’-x’’)}=0\)

这意味着\(\mathtt{w}\)和平面上任意向量垂直,也就是说\(\mathtt{w}\)是垂直于该平面的

根据高中知识,平面外一点到一平面的距离等于平面上任一点指向该点的向量投影到平面单位法向量的绝对值

![avatar][]

\(\hat{\mathtt{w}}\),单位法向量

\(\mathtt{x}\)平面上一点

\(\mathtt{x’}\)平面外一点

\(\hat{\mathtt{w}}=\mathtt{\frac{w}{||w||}}\)

\(distance=|\hat{\mathtt{w}}^T\mathtt{(x’-x)}|\)

硬间隔SVM

硬间隔SVM就是在正确分类的前提下(满足分割平面),使得离平面最近的点到平面的距离(间隔)最大

提出优化问题

任一点到平面的距离是

\(distance=|\hat{\mathtt{w}}^T\mathtt{(x’-x)}|\)

离平面最近的点到平面的距离是(离平面最近的点满足\(y_n\mathtt{(w^Tx’+b)}=1\)),化简

\(distance=\frac{1}{||\mathtt{w}||}|\mathtt{w^T}\mathtt{(x’-x)}=\frac{1}{||\mathtt{w}||}|\mathtt{w^Tx’-w^Tx|}=\frac{1}{||\mathtt{w}||}|\mathtt{w^Tx’+b-w^Tx-b|}=\frac{1}{||\mathtt{w}||}\)

最大化\(distance\)等同于最小化\(||\mathtt{w}||\),即最小化\(\frac{1}{2}\mathtt{w^Tw}\)

优化问题:

\(\begin{equation}\begin{split}\min \quad&\frac{1}{2}\mathtt{w^Tw}\\s.t.\quad &\min\limits_{n=1,…,N}y_n\mathtt{(w^Tx_n+b)}=1\end{split}\end{equation}\)

约束条件中含有\(min\)对于优化问题不好解决,转换如下

\(\begin{equation}\begin{split}\min \quad&\frac{1}{2}\mathtt{w^Tw}\\s.t.\quad &y_n\mathtt{(w^Tx_n+b)}\ge1\end{split}\end{equation}\)

拉格朗日函数及KKT

原问题

\(\begin{equation}\begin{split}\min \quad&f(\mathtt{x})\\s.t.\quad &h_i(\mathtt{x})=0,i=1,2,…,m\\&g_i(\mathtt{x})\le0,i=1,2,…,n\end{split}\end{equation}\)

转换为拉格朗日函数

\(L\)(\(\mathtt{x,\lambda,\mu}\))=\(f(\mathtt{x})+\sum_{i=1}^m\lambda_ih_i(\mathtt{x})+\sum_{i=1}^n\mu_ig_i(\mathtt{x})\)

将带约束优化问题转化为拉格朗日函数即

\(\min\quad\mathcal{L}(\mathtt{w},b,\alpha)=\frac{1}{2}\mathtt{w^Tw}-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1),\alpha_n\ge0\)

最优解\(\mathtt{x^*}\)满足KKT条件:
\[ \begin{cases} \ g_i(\mathtt{x^*})\le0,h_i(\mathtt{x^*})=0;\\ \ \mu_i\ge0;\\ \ \mu_ig_i(\mathtt{x^*})=0;\\ \end{cases} \]

对偶问题

上述拉格朗日函数又等价于

\(\min\limits_{\mathtt{w,b}}\max\limits_{\alpha\ge0}\mathcal{L}(\mathtt{w},b,\alpha)\)

其对偶问题

\(\max\limits_{\alpha\ge0}\min\limits_{\mathtt{w,b}}\mathcal{L}(\mathtt{w},b,\alpha)\)

原问题是先满足约束,再最大化间隔,对偶问题是先最大化间隔,再满足约束

对偶问题给出原问题的下界,当原问题与对偶问题是强对偶,可以通过对偶问题求出原问题的最优解,而且对偶问题万网更容易解决

先解决内部的\(\min\)

\(\min\limits_{\mathtt{w,b}}\mathcal{L}(\mathtt{w},b,\alpha)\)

拉格朗日函数对\(\mathtt{w,b}\)求导等于零带入原函数 \(\min\limits_{\mathtt{w,b}}\mathcal{L}(\mathtt{w},b,\alpha)=\frac{1}{2}\mathtt{w^Tw}-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1),\alpha_n\ge0\)

对\(\mathtt{w},b\)变量求导得到0

\(\nabla_\mathtt{w}\mathcal{L}=\mathtt{w}-\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}=0\)

\(\nabla_b\mathcal{L}=-\sum_{n=1}^N\alpha_ny_n=0\)

可以得出 \(\mathtt{w}=\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}\),\(\sum_{n=1}^N\alpha_ny_n=0\)

带入到拉格朗日式子中

\(\begin{equation}\begin{split}\min\limits_{\mathtt{w,b}}\mathcal{L}(\mathtt{w},b,\alpha)&=\frac{1}{2}\mathtt{w^Tw}-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1)\\&=\sum_{n=1}^N\alpha_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Ny_ny_m\alpha_n\alpha_m\mathtt{x_n^Tx_m}\end{split}\end{equation}\\\)

对偶问题转化为

\(\begin{equation}\begin{split}\max\limits_{\alpha\ge0}\min\limits_{\mathtt{w,b}}\mathcal{L}(\mathtt{w},b,\alpha)&=\max\limits_{\alpha\ge0}\sum_{n=1}^N\alpha_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Ny_ny_m\alpha_n\alpha_m\mathtt{x_n^Tx_m}\\&=\min\limits_{\alpha\ge0}\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Ny_ny_m\alpha_n\alpha_m\mathtt{x_n^Tx_m}-\sum_{n=1}^N\alpha_n\end{split}\end{equation}\\\)

问题转化为

\(\begin{equation}\begin{split}\min\quad&\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Ny_ny_m\alpha_n\alpha_m\mathtt{x_n^Tx_m}-\sum_{n=1}^N\alpha_n\\s.t\quad&\sum_{n=1}^N\alpha_ny_n=0\\&\alpha_n\ge0\end{split}\end{equation}\\\)

参数计算

计算\(\alpha\)

优化问题转化为二次规划的形式

\(\begin{equation}\begin{split}\min\limits_{\alpha}\frac{1}{2}\alpha^T\begin{bmatrix}{y_1y_1\mathtt{x_1^Tx_1}}&{y_1y_2\mathtt{x_1^Tx_2}}&{\ldots}& {y_1y_N\mathtt{x_1^Tx_N}}\\{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{y_Ny_1\mathtt{x_N^Tx_1}}&{y_Ny_2\mathtt{x_N^Tx_2}}&{\ldots}& {y_Ny_N\mathtt{x_N^Tx_N}}\\\end{bmatrix}\alpha+(-1^T)\alpha\end{split}\end{equation}\\\)

subject to \(\mathtt{y^T\alpha}=0,0\le\alpha\le\infin\)

\(-1^T\)是指一个全是-1的行向量,上边分开写的矩阵称为二次系数矩阵\(Q\)

\(\alpha\)由二次规划给出

计算\(\mathtt{w}\)

由对偶问题中的\(\nabla_\mathtt{w}\mathcal{L}=\mathtt{w}-\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}=0\)可以得出

\(\mathtt{w}=\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}\)

计算\(b\)

从\(\alpha\)中选一个非零的\(\alpha_n\),其对应的\(\mathtt{x’}\)即为支持向量,即满足

\(y_n\mathtt{(w^Tx’+b)}=1\)

\(b=\frac{1}{y_n}-\mathtt{w^Tx’}\)

计算目标函数

\(g(\mathtt{x})=sign(\mathtt{w^Tx+b})\)

软间隔SVM

当数据是不可分的,适当地容忍一些违反最大间隔的点往往可以获得更好的泛化能力

黄色区域是最大间隔,其中的蓝色的点是违反最大间隔的点,它到间隔边缘的距离衡量了违反的程度

![avatar][]

当一点\(\mathtt{x_n}\)违反最大间隔时(分割平面的点满足\(y_n\mathtt{(w^Tx_n+b)}\ge1\))

\(y_n\mathtt{(w^Tx_n+b)}<1\)

量化一个点\(\mathtt{x_n}\)的违反程度即

\(\xi_n=1-y_n\mathtt{(w^Tx_n+b)},\xi\ge0\)

衡量所有点的违反程度

\(\sum_{n=1}^N\xi_n\)

优化问题

\(\begin{equation}\begin{split}\min \quad&\frac{1}{2}\mathtt{w^Tw}+C\sum_{n=1}^N\xi_n\\s.t.\quad &y_n\mathtt{(w^Tx_n+b)}\ge1-\xi_n\\&\xi_n\ge0\end{split}\end{equation}\)

C是加在违反程度上的权值,当C很大意味着违反惩罚很大,所以问题会接近硬间隔SVM,当C很小意味着你可以随意违反间隔,也就是说会得到一个很大的间隔,但分类效果较差

拉格朗日函数

\(\min\mathcal{L}(\mathtt{w},b,\xi,\alpha,\beta)=\frac{1}{2}\mathtt{w^Tw}+C\sum_{n=1}^N\xi_n-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1+\xi_n)-\sum_{n=1}^N\beta_n\xi_n,\alpha_n,\beta_n\ge0\)

对偶问题

原问题等价

\(\min\limits_{\mathtt{w,b,\xi}}\max\limits_{\alpha\ge0,\beta\ge0}\mathcal{L}(\mathtt{w},b,\xi,\alpha,\beta)\)

对偶问题

\(\max\limits_{\alpha\ge0,\beta\ge0}\min\limits_{\mathtt{w,b,\xi}}\mathcal{L}(\mathtt{w},b,\xi,\alpha,\beta)\)

先解决内部的\(\min\),拉格朗日函数对\(\mathtt{w,b,\xi}\)求导等于零带入原函数

\(\nabla_\mathtt{w}\mathcal{L}=\mathtt{w}-\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}=0\)

\(\nabla_b\mathcal{L}=-\sum_{n=1}^N\alpha_ny_n=0\)

\(\nabla_{\xi}\mathcal{L}=C-\alpha_n-\beta_n=0\)

回头看看拉格朗日函数

\(\mathcal{L}(\mathtt{w},b,\xi,\alpha,\beta)=\frac{1}{2}\mathtt{w^Tw}+C\sum_{n=1}^N\xi_n-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1+\xi_n)-\sum_{n=1}^N\beta_n\xi_n,\alpha_n,\beta_n\ge0\)

\(\begin{equation}\begin{split}\mathcal{L}(\mathtt{w},b,\xi,\alpha,\beta)&=\frac{1}{2}\mathtt{w^Tw}+C\sum_{n=1}^N\xi_n-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1+\xi_n)-\sum_{n=1}^N\beta_n\xi_n\\&=\frac{1}{2}\mathtt{w^Tw}-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1)+C\sum_{n=1}^N\xi_n-\sum_{n=1}^N\alpha_n\xi_n-\sum_{n=1}^N\beta_n\xi_n\\&将\nabla_b\mathcal{L}=C-\alpha_n-\beta_n=0带入\\\min\limits_{\mathtt{w,b,\xi}}\mathcal{L}(\mathtt{w},b,\xi,\alpha,\beta)&=\frac{1}{2}\mathtt{w^Tw}-\sum_{n=1}^N\alpha_n(y_n\mathtt{(w^Tx_n+b)}-1)\\&=\mathcal{L}(\alpha)(这里是指和硬间隔的对偶优化问题相同)\end{split}\end{equation}\\\)

结果和硬间隔SVM相似,所以优化问题为

\(\begin{equation}\begin{split}\min\quad&\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Ny_ny_m\alpha_n\alpha_m\mathtt{x_n^Tx_m}-\sum_{n=1}^N\alpha_n\\s.t\quad&\sum_{n=1}^N\alpha_ny_n=0\\&C\ge\alpha_n\ge0\end{split}\end{equation}\\\)

参数计算

计算\(\alpha\)

优化问题转化为二次规划的形式

\(\begin{equation}\begin{split}\min\limits_{\alpha}\frac{1}{2}\alpha^T\begin{bmatrix}{y_1y_1\mathtt{x_1^Tx_1}}&{y_1y_2\mathtt{x_1^Tx_2}}&{\ldots}& {y_1y_N\mathtt{x_1^Tx_N}}\\{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{y_Ny_1\mathtt{x_N^Tx_1}}&{y_Ny_2\mathtt{x_N^Tx_2}}&{\ldots}& {y_Ny_N\mathtt{x_N^Tx_N}}\\\end{bmatrix}\alpha+(-1^T)\alpha\end{split}\end{equation}\\\)

subject to \(\mathtt{y^T\alpha}=0,0\le\alpha\le C\)

\(-1^T\)是指一个全是-1的行向量,上边分开写的矩阵称为二次系数矩阵\(Q\)

\(\alpha\)由二次规划给出

计算\(\mathtt{w}\)

由对偶问题中的\(\nabla_\mathtt{w}\mathcal{L}=\mathtt{w}-\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}=0\)可以得出

\(\mathtt{w}=\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}\)

计算\(b\)

从\(\alpha\)中选一个非零且小于C的\(\alpha_n\),其对应的\(\mathtt{x’}\)即为支持向量,即满足

\(y_n\mathtt{(w^Tx’+b)}=1\)

\(b=\frac{1}{y_n}-\mathtt{w^Tx’}\)

计算目标函数

\(g(\mathtt{x})=sign(\mathtt{w^Tx+b})\)

核函数

可以发现在SVM的对偶问题中关于输入\(\mathtt{x}\)的运算只涉及到\(\mathtt{x^Tx}\),如果我们能很快速的计算出\(\mathtt{x}\)映射到高维的\(\mathtt{z}\)的\(\mathtt{z^Tz}\)运算,那么就可以很轻易地运用高维拟合数据而不用付出太多代价

二次规划:

\(\begin{equation}\begin{split}\min\limits_{\alpha}\frac{1}{2}\alpha^T\begin{bmatrix}{y_1y_1\mathtt{x_1^Tx_1}}&{y_1y_2\mathtt{x_1^Tx_2}}&{\ldots}& {y_1y_N\mathtt{x_1^Tx_N}}\\{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{y_Ny_1\mathtt{x_N^Tx_1}}&{y_Ny_2\mathtt{x_N^Tx_2}}&{\ldots}& {y_Ny_N\mathtt{x_N^Tx_N}}\\\end{bmatrix}\alpha+(-1^T)\alpha\end{split}\end{equation}\\\)

subject to \(\mathtt{y^T\alpha}=0,0\le\alpha\le C\)

由\(\mathtt{w}=\sum_{n=1}^N\alpha_ny_n\mathtt{x_n}\)和\(g(\mathtt{x})=sign(\mathtt{w^Tx+b})\)

可得

\(b=y_m-\sum\limits_{\alpha>0}\alpha_ny_nK(\mathtt{x_n,x_m}),\mathtt{x_m}是一个支持向量\)

\(g(\mathtt{x})=sign(\sum\limits_{\alpha_n>0}\alpha_ny_nK(\mathtt{x_n,x})+b)\)

综上可看出支持向量机的关于输入\(\mathtt{x}\)的运算确实只涉及到\(\mathtt{x^Tx}\)

核函数定义

\(\mathtt{x,x’\in \mathcal{X};z,z’\in\mathcal{Z}}\)

\(\Phi(\mathtt{x})=\mathtt{z}\)

核函数:

\(K(\mathtt{x,x’})=\mathtt{z^Tz’}\)

核函数就是一种快速计算两个点映射到高维点的内积的函数

多项式核函数(Q是指Q次)

\(K(\mathtt{x,x’})=\mathtt{(1+x^Tx’)}^Q=(1+x_1x_1’+x_2x_2’+…+x_dx_d’)^Q\)

可以通过缩放调整的多项式核函数

\(K(\mathtt{x,x’})=\mathtt{(b+ax^Tx’)}^Q\)

高斯核函数(无限维度)

\(K(\mathtt{x,x’})=exp(-\gamma||\mathtt{x-x’}||^2)\)

![avatar][]

对于无限维度的说明(贴张图吧,敲着好累,高数不太行)

支持向量机和正则化的对比

转载于//www.cnblogs.com/redo19990701/p/11521886.html

[avatar]: