svm原理简介

1. 模式识别总论

第一种是经典的（参数）统计估计方法。现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性。

首先，它需要已知样本分布形式，这需要花费很大代价，还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。

我觉得NB、ME、CRF等算法都属于这一类。

第二种方法是不考虑概率分布，直接进行分类。比如线性分类器、非线性分类器。如人工神经网络 （ANN）。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。

这个路线的后期就是SVM，过去各种分类器都只考虑经验风险最小化，SVM提出了结构风险最小化。

这两种路线之间存在关系，我还不是特别明白。不过直观上想，经典的统计方法有清晰的概率含义，而且还能够通过规定模型的结构来融合更多的知识。而SVM不关心模型的含义。

2．Maximum Margin Classifier

最大边缘分类器就是早期的SVM，它是一个线性分类器，还没有引入kernel呢。但是已经体现了SVM的基本特点：结构风险最小化。

经验风险是Remp[f]，期望风险是R[f]，则R[f]<=(Remp[f]+g(h/n))。其中g(h/n)是VC维 h 的增函数，也是样本数n的减函数。右端称为结构风险。VC维h是模型复杂度的度量。总的来看，就是在经验风险一样的情况下，训练样本数n越大，则结构风险越小，模型复杂度h越小，则结构风险越小。结构风险最小化，就是平衡了经验风险和模型复杂度。过去的模型常常不考虑这个问题，比如多项式函数显然比线性函数表达能力强，但是它们的模型复杂度更高。

VC维的定义如下：对于一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2的h次幂种形式分开，则称函数集能够把h个样本都打散，h的最大值就是函数集的VC维。VC维是SLT中的一个重要概念，它是函数集学习性能的重要指标。目前尚没有通用的关于任意函数集VC维计算的理论，只知道一些特殊的函数集的VC维。比如，在n维空间中线性分类器和线性实函数的VC维是 n+1，而 f(x,a) = sin(ax) 的VC维则为无穷大。对于给定的学习函数集，如何（用理论或实验的方法）计算其VC维是当前统计学习理论中有待研究的一个问题。

这时的SVM有一个另外的重要概念，就是margin。现在我们假设数据线性可分。所谓margin，就是从分类面生成两个与分类面平行的平面，分别向正例和负例数据集靠拢，直到这两个平面首次通过某个正例或负例点。

这两个平面间的距离称为margin。设margin为a，则超平面集合的 VC 维 h 满足下面关系：

h=f(1/(a^2))

其中， f是单调增函数，即 h 与a的平方成反比关系。因此，当训练样本给定时，分类间隔越大，则对应的分类超平面集合的 VC 维就越小。

因为数据是线性可分的，所以总可以找到一个超平面使得经验风险等于0，接下来，我们就要在所有的超平面中找到边缘最大的。另外，边缘等于2/||w|| ，所以，整个问题是：

在满足c_i(w*x_i-b)>=1的情况下，最小化||w||。一个等价的问题是：在满足c_i(w*x_i-b)>=1的情况下，最小化0.5*(||w||)^2。

3. Soft Margin

当数据不是线性可分的时候，以上的理论出现瑕疵了，我们无法在经验风险为0的情况下最大化margin。这时，我们允许c_i(w*x_i-b)<1。然后就得到了SVM最常见的定义：

4.Kernel

http://en.wikipedia.org/wiki/Kernel_trick

kernel是一个独立的方法，就是帮助线性分类器解决非线性问题的。

在传统的分类方法中，如果分类模型的复杂性提高，很容易就出现过拟合的情况。所以，传统上有两种方法解决：1、使用模型选择，使用较简单的模型；2、用Regulation。虽然使用了更复杂的模型，但是还是避免模型过分拟合数据。SVM中，选择各种不同的核就对应于第一种方法，而SVM自己的结构风险最小化中就包含了regulation，对应第二种方法。