SVM的数学问题求解


上篇文章中，我们将SVM转化成了如下的最优化问题：


svm


s.t.

svm2


这里，我们再做一个小小的转化，将求最大值转化成求最小值，因为总的来说，我们对求最小值的问题更加熟悉一点，转化后是这个样子：


svm标准数学形式


这个问题的求解，数学家们已经给出了完美的办法。就是拉格朗日对偶法,但是要彻底讲清楚这个方法涉及到很多数学知识，如果粗略讲讲，忽略那些数学知识，就容易造成理解上的困惑。所以，搞机器学习，到底需要多少数学知识？


这个问题没有一定的正确答案，完全取决于你工作的需要和个人的兴趣 。如果你的工作只是理解这些模型的原理以便正确地使用它，那么，只要你觉得你的数学知识能够让你理解这个模型就可以了，如果你的工作可能会需要对模型求解的性能进行优化(这样的工作岗位我觉得是比较少的)，那么肯定是理解地越透彻越好，数学知识多多益善。


最后，如果你对数学上的原理很感兴趣，那么 follow your heart即可。


本文的目的是在于说明模型的原理，所以只会在不得已时给出一些数学知识，而且也会尽可能以结论的形式给出。即数学只是我们的工具，我们的目的在于理解模型。


上面的问题， 在求解上，数学上给出了一个拉格朗日对偶求解法。该方法简单明了，我觉得对这个方法的数学证明，可以留给对数学特别有兴趣的朋友，一般情况下，我们只要知道具体的过程就可以了。这就像将大象关进冰箱，我们只需知道打开冰箱门，将大象放进去，关上冰箱门就可以了。好了，相信你已经准备好接受这个方法了，其步骤如下：


1、定义拉格朗日函数

image.png


这个函数其实就是将上面的m个大于等于0的约束条件，两边乘以-1转为小于等于0的约束条件，然后每一个约束条件左侧表达式乘以一个alpha再与目标函数相加就可以了。请注意，这里的alpha都是大于等于0的。


2、对w，b求导，令导数为0，求解


image.png


3、将第2步求得的结果代回拉格朗日函数，得到对偶问题


image.png


image.png


4、求解对偶问题，解出alpha，进而求出w，b


image.png


你可能对这样的方法为什么可行有疑问，还是那句话，这只是数学家告诉我们的一个办法，他们也证明过了，做机器学习的我们，直接拿来使用就可以了。如果你非要问清楚为什么，请参阅wiki。


你还可能觉得这个问题成对偶问题后，和原来问题相比，难度一样啊，还是一个二次规划问题，为什么非要费这么大劲呢。


答案同样是简单的，因为这个对偶的二次规划问题，已经有了高效的求解方法，就是SMO算法。我有篇文章就是专门讲解SMO算法的，请参阅（绝对原创，绝对心血结晶，强烈推荐阅读！）。第二呢 ，就是对偶问题会更便于引入核函数的概念。后续会专门讲解核函数。


当样本线性不可分时，SVM还能使用吗？



在上面的求解过程中，我们的目标是找到一个超平面，将正负样本分开。这里的一个前提假设是确实存在一个超平面，能够将正负样本分开。但理想很丰满，现实很骨感，大部分情况下，正负样本都不是能严格分开的，原因是多样的，比如数据采集有误差，或者数据本身就是不能完全分开的。


那怎么办呢？


此时，我们要回到SVM最初的思想上，SVM就是找一个将正负样本分得最开的超平面，从这个思想出发，我们一路推导，最后得出了一个数学上的最优化问题：

image.png


最小化目标函数(即二分之一的ω的二范数)就相当于最大化超平面与样本的间隔。对ω的约束就是能正确分开正负样本，并且与最近的样本点的函数间隔是1。我们称存在这样的超平面的样本集为线性可分样本集，此时的SVM也叫做线性可分SVM。


那么现在，满足约束条件的超平面已经不存在了。按理说，我们的SVM就不能用了。但是，正负样本线性不可分也是有程度之分的，一种是彻底的混乱不可分，一种是总体看来是可分，少数点使得其不可分。


对于彻底混乱不可分的情况，用核函数的办法可以使得我们继续使用SVM，简单讲就是将样本集进行映射，使得映射后的样本集正负线性可分，然后再使用SVM。如下图所示：


image.png


这个做法要在讲核函数时才能透彻说明。暂时按下不表。


对于基本线性可分，少数样本使得其不可分的情况，我们可以“放松”原来的SVM的要求，从而使其能适用这种情况。放松的思想非常简单，就是不再执着于寻找将正负样本分得最开的超平面，转而寻找将最多的样本分开且分得尽可能开，将最少的样本分不开，且分不开的程度尽可能低的超平面。这句话需要停下来反复体味一下。下面就来看看怎么来“放松”吧。


假设我们现在有一个超平面H，然后我们努力寻找它的特定表示，即ω，b，以便使得对每一个样本满足：

image.png


但是费了九牛二虎之力，找到的最好的表示ω，b仍然不能使得所有样本满足上面的条件。那么，此时，我们需要一个指标来告诉我们，这个超平面在区分正负样本方面怎么样？是不是达到了我们所要求的将能分开的样本分得尽可能开，将不能分开的样本分不开的程度降得尽可能低。


我们先来看看这个超平面对能分得开的样本分开的程度吧，对这些样本而言，都是满足上面的函数间隔大于等于1的要求的，所以，超平面将这些样本分开的程度可以用


image.png


来表示，这个值越小，表示超平面将这些样本分得越开。


对那些不满足函数间隔大于等于1的样本，如何衡量超平面对它们分不开的程度呢？就是看这些样本离满足函数间隔大于等于1的要求有多远。比如对样本(xi,yi),如果对它的函数间隔加上某个数ζi,就能使得该样本对超平面的函数间隔满足大于等于1的要求，我们就称超平面对这个样本分不开的程度为ζi。将所有分不开的样本的ζi加起来就可以衡量超平面对分不开的样本的分不开的程度。显然，对于那些满足函数间隔大于等于1的样本， 它们对应的ζi为0。


至此，我们知道了如何衡量超平面对那些满足函数间隔大于等于1的样本的分得开的程度，也知道了如何衡量超平面对那些不满足函数间隔大于等于1的样本的分不开的程度。将二者结合结合起来，就是能够衡量一个超平面，对于一个线性不可分的样本的分得开的程度。这就是基本线性可分SVM，如下图所示：


image.png


对这个问题的求解仍然是使用拉格朗日对偶法，过程和上面一样，这里不再赘述。


对基本线性可分SVM的思考



回顾本文，我觉得最重要的不是SVM的对偶求解方法，也不是线性可分SVM（啥意思，通篇文章不就讲了这两个事儿吗，逗我呢？）

我这么说是认真的，因为我觉得最重要的是我们从线性可分SVM，结合现实中样本都不是完全线性可分的实际，进而调整得到基本线性可分SVM的思维过程。这样的思维方式体现了将理论与实践结合的过程，这是我觉得最可贵的思维品质。


在当前AI快速发展的形势下，新的算法每天都在涌现，很多相关工作岗位都要求能够跟踪最新技术，并结合实际运用它，为公司创造利益。“结合实际”需要的就是这种将理论结合实践的思维品质。之前，听汪榕的智能营销实践课程，我最大的收获就是学习到他那种紧紧地将理论与实际业务结合的优秀思维习惯，所以，这里也强烈推荐下他的课程，即使你不是做智能营销，也应该能从中受益。


所以，如果读完本文，让你对理论结合实际有了更深一点的体会，我觉得就值了。


软间隔是在硬间隔的基础上针对现实问题做出的调整，这是有普遍意义的，就是目标函数要能够灵活结合实际变化。