谷歌网站建设代理,济南企业如何建网站,wordpress题库制作,汉中专业网站建设服务前言
本文主要是讲了如何构建SVM的模型#xff0c;并利用KKT条件构造其对偶型#xff0c;从而求解问题#xff0c;并讲述了SVM的硬间隔#xff0c;软间隔和核函数三个境界。主要参考了周志华的《机器学习》#xff0c;并在其中补充了自己的想法。由于内容较多#xff0c…前言
本文主要是讲了如何构建SVM的模型并利用KKT条件构造其对偶型从而求解问题并讲述了SVM的硬间隔软间隔和核函数三个境界。主要参考了周志华的《机器学习》并在其中补充了自己的想法。由于内容较多所以很多细节都省略掉了只留下了整体的框架该说的东西应该都说了。
SVM基本型
首先我们先假设一个数据集线性可分的情况也就是硬间隔的情况如下图所示。 图1线性可分情况可以看到数据集可以被无数条直线正确划分为两类然而我们希望找到其中最好的一条线来划分这两个数据集这条直线最好有较好的泛化能力也就是说在面对未知的数据集的时候也能够较为正确地划分数据有较强的抗干扰性。那么怎么样的直线是最好的呢我们来看下下面这幅图此图出自林轩田的机器学习技法。 图2划分方式抗干扰能力比较从图中看出我们假设每个数据点都带有一定的噪声也就是说在数据点周围的灰色区域可能都是和这个数据点相同类型的数据点只不过因为某些噪声干扰产生了一些偏移就是有方差的意思。那么上图中的第三种情况是最能容忍这种噪声的也就是我们最希望得到的划分方式。 换另一种方式来说假设我们有一条直线或超平面wTxb0w^Tx+b=0正确划分了数据集将直线分别往上方和下方平移直到碰到数据点我们假设网上和往下平移的截距是相同的比如都是aa（如果不同的话就平移一下wTx+b=0w^Tx+b=0即改变bb的值，总能找到满足条件的一条wTx+b=0w^Tx+b=0。 {wTxbawTxb−a\begin{cases}w^Tx+b=a \\ w^Tx+b=-a\end{cases}为了之后方便处理我们统一一下将等式两边同时除以一个aa，即
{w:=w/ab:=b/a\begin{cases}w:=w/a \\ b:=b/a\end{cases} 于是我们现在就有三条直线或超平面 ⎧⎩⎨wTxb1wTxb0wTxb−1\begin{cases}w^Tx+b=1 \\ w^Tx+b=0 \\ w^Tx+b=-1\end{cases}如下图所示。 图3支持向量与间隔其中在直线上的点就被称为支持向量。我们现在的目的就是找到使得wTxb1w^Tx+b=1和wTxb−1w^Tx+b=-1之间距离最大的参数ww和bb。 那个这个距离或者说这个间隔怎么求呢这就要用到我们的支持向量了这个间隔是由它们决定的。 假设有支持向量x1x_1和x2x_2分别满足 {wTx1b1wTx2b−1\begin{cases}w^Tx_1+b=1 \\ w^Tx_2+b=-1\end{cases}两式相减则有 w⋅(x1−x2)2w \cdot (x_1-x_2)=2注意到ww，x1x_1x2x_2都是向量那么由向量点乘的性质可以得到 ||w||⋅||x1−x2||⋅cosθ2||w|| \cdot ||x_1-x_2|| \cdot cos\theta =2注意到了吗这里的||x1−x2||⋅cosθ||x_1-x_2|| \cdot cos\theta就是间隔不信可以自己画下图看。于是 d||x1−x2||⋅cosθ2||w||d=||x_1-x_2|| \cdot cos\theta=\dfrac{2}{||w||}我们假设现在是一个二分类问题两类分别标记为{1,−1}\{+1, -1\}于是现在问题就转化为了 maxw,b 2||w||s.t.{yi1, wTxib≥1yi−1,wTxib≤−1 \mathop{max}_{w,b}\ \dfrac{2}{||w||} \\ s.t. \begin{cases}y_i=1, \quad \ \ \ w^Tx_i+b\geq 1 \\ y_i=-1, \quad w^Tx_i+b\leq -1\end{cases}将式子合起来并将求最大改成求最小则是 minw,b ||w||22s.t. yi(wTxib)≥1,i1,2,...,m \mathop{min}_{w,b}\ \dfrac{||w||^2}{2} \\ s.t. \ y_i(w^Tx_i+b) \geq 1, \quad i=1,2,...,m这就是SVM的基本型。 这是一个凸二次规划问题可以直接解决但效率不高我们希望找到更高效的方法所以就去找它的对偶问题。这也是求不等式约束求极值的通用手段。 既然都讲到这里了干脆先把拉格朗日乘子法和KKT条件都给讲了。拉格朗日乘子法
拉格朗日乘子法针对的是等式约束基本形式如下
minx f(x)s.t.hi(x)0,i1,2,...,m\mathop{min}_{x} \ f(x) \\ s.t. h_i(x)=0, \quad i=1,2,...,m拉格朗日乘子法做的就是将约束条件添加到目标函数当中使其变成一个无约束优化问题。可以这么做的原因是只要满足hi(x)0h_i(x)=0那么不管加多少个都是不改变目标值的。 minx,λL(x,λ)f(x)∑mi1λihi(x) \mathop{min}_{x,\lambda} L(x, \lambda) = f(x) +\sum_{i=1}^m\lambda_i h_i(x)我们假设xx有pp个特征那么上式的极值点有如下的必要条件 ⎧⎩⎨⎪⎪⎪⎪⎪⎪∂L∂xk∂f∂xk∑mi1λi∂hi(x)∂xk0,k1,2,...,p∂L∂λihi(x)0,i1,2,...,m\begin{cases} \dfrac{\partial L}{\partial x_k}=\dfrac{\partial f}{\partial x_k} + \sum_{i=1}^m\lambda_i \dfrac{\partial h_i(x)}{\partial x_k}=0, \quad k=1,2,...,p \\ \dfrac{\partial L}{\partial \lambda_i} =h_i(x)=0, \quad i=1,2,...,m\end{cases}上式有pp个xkx_k和mm个λi\lambda_i是待求的参数kmk+m个未知数同时有pmp+m个等式方程所以是可以求解得到xkx_k和λi\lambda_i的值。 值得注意的是以上的只是必要条件并不是充分条件所以求得结果后最好再检验一下虽然实际情况下都忽略了这一步。KKT条件
KKT条件是在拉格朗日乘子法的基础上多了不等式的约束其针对的问题的基本型如下所示。
minxf(x)s.t.{hi(x)0, i1,2,..,mgj(x)≤0, j1,2,...,n\mathop{min}_x f(x) \\ s.t.\begin{cases} h_i(x)=0,\ i=1,2,..,m \\ g_j(x) \leq 0, \ j=1,2,...,n \end{cases}其对偶型为 minx,λ,μL(x,λ,μ)f(x)∑mi1λihi(x)∑nj1μjgj(x)\mathop{min}_{x,\lambda,\mu}L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m\lambda_ih_i(x)+\sum_{j=1}^n\mu_jg_j(x)此时最优解要满足的条件为 ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∂L∂xk∂f∂xk∑mi1λi∂hi(x)∂xk∑nj1μj∂gj(x)∂xk0,k1,2,...,p∂L∂λihi(x)0,i1,2,...,mμjgi(x)0,j1,2,...,nμj≥0,j1,2,...,n\begin{cases}\dfrac{\partial L}{\partial x_k}=\dfrac{\partial f}{\partial x_k} + \sum_{i=1}^m\lambda_i \dfrac{\partial h_i(x)}{\partial x_k}+\sum_{j=1}^n\mu_j\dfrac{\partial g_j(x)}{\partial x_k}=0, \quad k=1,2,...,p \\ \dfrac{\partial L}{\partial \lambda_i} =h_i(x)=0, \quad i=1,2,...,m \\ \mu_jg_i(x)=0, \quad j=1,2,...,n \\ \mu_j \geq 0, j=1,2,...,n\end{cases} 至于为什么是这样参考一下
这个吧这里偷下懒。SVM对偶问题
我们再来回顾一下我们得到的SVM基本型。
minw,b ||w||22s.t. 1−yi(wTxib)≤0,i1,2,...,m \mathop{min}_{w,b}\ \dfrac{||w||^2}{2} \\ s.t. \ 1-y_i(w^Tx_i+b) \leq 0, \quad i=1,2,...,m很显然这是一个只有不等式的约束的KKT条件问题。 于是我们可以将问题转化为 minw,b,αL(w,b,α)||w||22∑mi1αi(1−yi(wTxib))\mathop{min}_{w,b,\alpha} L(w,b,\alpha)=\dfrac{||w||^2}{2} + \sum_{i=1}^{m}\alpha_i(1-y_i(w^Tx_i+b))这个时候最优解满足的条件为 ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∂L∂ww−∑mi1αiyixi0∂L∂b∑mi1αiyi0αi(yif(xi)−1)0, i1,2,...,mαi≥0,i1,2,...,m\begin{cases}\dfrac{\partial L}{\partial w} = w-\sum_{i=1}^{m}\alpha_i y_i x_i=0 \\ \dfrac{\partial L}{\partial b}=\sum_{i=1}^m\alpha_iy_i=0 \\ \alpha_i(y_if(x_i)-1)=0, \ i=1,2,...,m \\ \alpha_i \geq 0,\quad i=1,2,...,m\end{cases}值得注意的是这里的ww，xx都是向量f(xi)wTxibf(x_i)=w^Tx_i+b。 我们将上述方程组的前2个带入到原问题中消去参数ww和bb则原问题转化为 minα L(α)12∑mi1∑mj1αiαjyiyjxTixj−∑mi1αi\mathop{min}_{\alpha} \ L(\alpha)= \dfrac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^m\alpha_i这个时候仍然需要满足 ⎧⎩⎨∑mi1αiyi0αi≥0,i1,2,...,mαi(yif(xi)−1)0, i1,2,...,m\begin{cases}\sum_{i=1}^m\alpha_iy_i=0 \\ \alpha_i \geq 0,\quad i=1,2,...,m \\ \alpha_i(y_if(x_i)-1)=0, \ i=1,2,...,m \end{cases}这个时候我们就可以用一个叫做SMO的算法来求解α\alpha这里不详细介绍这种算法了不然篇幅太长了。求得α\alpha之后可以通过w−∑mi1αiyixi0w-\sum_{i=1}^{m}\alpha_i y_i x_i=0这个式子来求得ww，而剩下的一个参数bb则要通过支持向量代入求解。软间隔
有时候噪声太大会因为某几个点而产生线性不可分的情况。这个时候就要引入软间隔这个概念了。说白了就是我们允许某些点是可以被错误分类的但这种错分的情况要尽可能地少。 图4软间隔示意图所以我们引入了松弛变量和惩罚函数。 minw,b ||w||22C∑mi1ϵis.t. yi(wTxib)≥1−ϵi,ϵi≥0,i1,2,...,m\mathop{min}_{w,b}\ \dfrac{||w||^2}{2} + C\sum_{i=1}^m \epsilon_i \\ s.t. \ y_i(w^Tx_i+b) \geq 1-\epsilon_i, \quad \epsilon_i\geq 0, \quad i=1,2,...,m容易看出当CC为无穷大的时候，就成了硬间隔的状态；当CC越小的时候允许被错分的点就越多。 同样是利用KKT条件我们可以得到其对偶问题 maxα ∑mi1αi−12∑mi1∑mj1αiαjyiyjxTixjs.t.{∑mi1αiyi00≤αi≤C,i1,2,...,m\mathop{max}_{\alpha} \ \sum_{i=1}^m\alpha_i-\dfrac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t.\begin{cases}\sum_{i=1}^m \alpha_iy_i=0 \\ 0\leq \alpha_i \leq C, \quad i=1,2,...,m\end{cases}同样地这也是可以利用SMO算法求解的这里不详细介绍。核函数
以上问题是针对线性可分或者是针对由于噪声而产生的个别点线性不可分总体线性可分的情况。那么对于下图左这样本来就线性不可分的数据集该怎么处理呢 图5非线性映射没错就像上图所示的这样我们把低维的样本空间映射到一个更高为的空间使得样本点在高维空间上线性可分。我们用ϕ(x)\phi(x)表示映射后的特征向量于是在特征空间中超平面所对应的模型为 f(x)wTϕ(x)bf(x)=w^T\phi(x)+b类似上述的问题我们有 minw,b ||w||22C∑mi1ϵis.t. yi(wTϕ(xi)b)≥1−ϵi,ϵi≥0,i1,2,...,m\mathop{min}_{w,b}\ \dfrac{||w||^2}{2} + C\sum_{i=1}^m \epsilon_i \\ s.t. \ y_i(w^T\phi(x_i)+b) \geq 1-\epsilon_i, \quad \epsilon_i\geq 0, \quad i=1,2,...,m其对偶问题为 maxα ∑mi1αi−12∑mi1∑mj1αiαjyiyjϕ(xi)Tϕ(xj)s.t.{∑mi1αiyi00≤αi≤C,i1,2,...,m\mathop{max}_{\alpha} \ \sum_{i=1}^m\alpha_i-\dfrac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j) \\ s.t.\begin{cases}\sum_{i=1}^m \alpha_iy_i=0 \\ 0\leq \alpha_i \leq C, \quad i=1,2,...,m\end{cases}但是这样的处理会导致维度灾难也就是说本来几百维的一个东西会变成几千维这样的计算量是无法接受的。于是核函数就出现了核函数是在低维空间上计算高维空间点积的一种方法大大减少了数据量也就是说我们完全不用考虑ϕ(x)\phi(x)是什么东西就能够计算ϕ(xi)Tϕ(xj)\phi(x_i)^T\phi(x_j)我们将核函数记作 κ(xi,xj)ϕ(xi)Tϕ(xj)\kappa(x_i,x_j)=\phi(x_i)^T\phi(x_j)常用的核函数有如下几种这里不详细介绍核函数。 表1常用核函数于是我们的问题就转化为了 maxα ∑mi1αi−12∑mi1∑mj1αiαjyiyjκ(xi,xj)s.t.{∑mi1αiyi00≤αi≤C,i1,2,...,m\mathop{max}_{\alpha} \ \sum_{i=1}^m\alpha_i-\dfrac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\kappa(x_i,x_j) \\ s.t.\begin{cases}\sum_{i=1}^m \alpha_iy_i=0 \\ 0\leq \alpha_i \leq C, \quad i=1,2,...,m\end{cases}利用上式我们可以求出α\alpha然而这并没有什么卵用。由于我们不知道ϕ(x)\phi(x)是什么所以仍旧求不出f(x)wTϕ(x)bf(x)=w^T\phi(x)+b。 真的是这样吗别急。 在求对偶型的过程当中我们会求∂L∂w\dfrac{\partial L}{\partial w}对吧。由该式我们可以知道 w∑mi1αiyiϕ(xi)w=\sum_{i=1}^m\alpha_iy_i\phi(x_i)我们将其代入f(x)f(x)可得 f(x)wTϕ(x)b∑mi1αiyiϕ(xi)Tϕ(x)b∑mi1αiyiκ(x,xi)bf(x)=w^T\phi(x)+b \\ \quad \quad =\sum_{i=1}^m\alpha_iy_i\phi(x_i)^T\phi(x)+b \\ \quad \quad = \sum_{i=1}^m\alpha_iy_i\kappa(x,x_i)+b这样不就求出来了吗核函数是不是很神奇结束语
本文讨论了SVM是怎么来的以及硬间隔软间隔核函数这三个SVM的核心问题。许多细节都省略了只留下了整体框架。 如有不足还请指正~
参考文献
[1] 周志华. 机器学习 : Machine learning[M]. 清华大学出版社, 2016. [2] http://www.onmyphd.com/?plagrange.multipliers [3] http://www.onmyphd.com/?pkkt.karush.kuhn.tucker
