支持向量机对线性不可分数据的处理
目标
本文档尝试解答如下问题:
在训练数据线性不可分时,如何定义此情形下支持向量机的最优化问题。如何设置CvSVMParams中的参数来解决此类问题。
动机
为什么需要将支持向量机优化问题扩展到线性不可分的情形? 在多数计算机视觉运用中,我们需要的不仅仅是一个简单的SVM线性分类器, 我们需要更加强大的工具来解决训练数据无法用一个超平面分割的情形。
我们以人脸识别来做一个例子,训练数据包含一组人脸图像和一组非人脸图像(除了人脸之外的任何物体)。 这些训练数据超级复杂,以至于为每个样本找到一个合适的表达 (特征向量) 以让它们能够线性分割是非常困难的。
最优化问题的扩展
还记得我们用支持向量机来找到一个最优超平面。 既然现在训练数据线性不可分,我们必须承认这个最优超平面会将一些样本划分到错误的类别中。 在这种情形下的优化问题,需要将错分类(misclassification)当作一个变量来考虑。新的模型需要包含原来线性可分情形下的最优化条件,即最大间隔(margin), 以及在线性不可分时分类错误最小化。
我们还是从最大化间隔这一条件来推导我们的最优化问题的模型(这在前一节已经讨论了):
在这个模型中加入错分类变量有多种方法。比如,我们可以最小化一个函数,该函数定义为在原来模型的基础上再加上一个常量乘以样本被错误分类的次数:
然而,这并不是一个好的解决方案,其中一个原因是它没有考虑错分类的样本距离同类样本所属区域的大小。 因此一个更好的方法是考虑错分类样本离同类区域的距离:
这里为每一个样本定义一个新的参数, 这个参数包含对应样本离同类区域的距离。 下图显示了两类线性不可分的样本,以及一个分割超平面和错分类样本距离同类区域的距离。
Note
图中只显示了错分类样本的距离,其余样本由于已经处于同类区域内部所以距离为零。
红色和蓝色直线表示各自区域的边际间隔, 每个表示从错分类样本到同类区域边际间隔的距离。
最后我们得到最优问题的最终模型:
关于参数C的选择, 明显的取决于训练样本的分布情况。 尽管并不存在一个普遍的答案,但是记住下面几点规则还是有用的:
C比较大时分类错误率较小,但是间隔也较小。 在这种情形下, 错分类对模型函数产生较大的影响,既然优化的目的是为了最小化这个模型函数,那么错分类的情形必然会受到抑制。C比较小时间隔较大,但是分类错误率也较大。 在这种情形下,模型函数中错分类之和这一项对优化过程的影响变小,优化过程将更加关注于寻找到一个能产生较大间隔的超平面。
源码
你可以从OpenCV源码库文件夹samples/cpp/tutorial_code/gpu/non_linear_svms/non_linear_svms下载源码和视频, 或者从此处下载.