向量机SVM.docVIP

支持向量机SVM的研究 支持向量机(Support Vector Machine，SVM)是Corinna Cortes和Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。机器学习系统的训练样本集大小，对学习系统的泛化能力有很大的制约。如果样本集太小，训练的结果无法达到效果，而支持向量机能够很好地解决这个问题。与特征空间降低维数的方法不同，支持向量机能够将非线性问题映射到高维空间，然后在高维空间构造线性函数。SVM 可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器使类与类的间隔最大化，因而有较好的适应能力和较高的识别率。 支持向量机算法的本质是寻找一个最优超平面。最优超平面不但能将两类样本正确分开，而且使分类间隔最大，使分类间隔最大实际上就是对模型推广能力的控制。从一个超平面的任意点x的垂直距离y(x) = 0，即超级平面即用y(x)=0来表示。其中边缘就是任意样品和决策面之间的最小距离如图（1）。样品点xn到决策面的距离可以用如下公式（2）表示。 边缘的概念（1） 点xn到决策面的距离（2） 边缘公式（3） （3） （3） 其中 w → κw and b → κb 为比例，若 则表示最近点表面，若 则表示所有样本点。 为了保证边缘距离最小，则需要求出样品到决策面的最大的距离。大括号内求最小值，是在样本空间内求取样品点到决策面的距离的最小值，从而求出各样本空间内的最小值。只要保证各样本空间的最小值最大，即可求出所有样品到决策面的最大距离。 由以上式子可以得出为了最大化分类间隔，即||w||-1最大化。则要求||w||最小化即可。则求解最优超平面问题就可以表示成约束优化问题，则在条件式子 的约束下，最小化函数： 为求解此约束最优化问题，引入拉格朗日函数： 现在就是关于w和b求解L的最小值。把拉格朗日函数分别对w和b进行求导并令其等于0，就可以把上述问题转化为一个简单的对偶问题。即求L的最大值，其约束条件为L关于w和b的梯度均为0以及 。 对偶式子如下 其中 这是一个不等式约束下的二次函数的机制问题。原始的优化只有一个变量m，这种双配方的优化，有两个变量n和m，其中m比n小。这种双配方的方法，允许模型被重新定义和使用，并且可以应用于维数大于数据点个数的模型，其中包括无限特征空间。 新数据点进行分类则 y(x) = wTφ(x) + b 其中 根据KKT条件即由前面拉格朗日函数提到的约束条件可以推出 an= 0或者tny(xn) = 1 由此可以确定阈值参数b 则 假设线性可分空间为φ(x)，但是在实际中样本点的重叠会导致泛化，即样本集不可分，则需要引入松弛变量ξn≥0。 其中ξn=0表示正确边缘和边界内的数据点 ξn=|tn? y(xn)|则表示其他点。 由于存在分类错误，则需要在目标函数中额外为分类误差分配一个额外的代价函数，即引入错误惩罚分量C. C 0 相应的拉格朗日函数为 之后的方法与前面未加入惩罚分量类似，求梯度，对偶化等，不再赘述。 我们主要详细介绍了当样本集线性可分时，并且是针对两类样本进行分类时，如何利用最有分类线将两类无错误的分开，此外还简略介绍了出现错误样本时如何进行分类。推广到高维平面最优分类线就变成了最优分类面。 我们常用的SVM算法是二次规划算法，也是比较常见的。二次规划是我们常见的优化问题，有比较成熟的理论。从上面我们的推倒可以看出，在二次规划过程中，其实已经转变为数学中的求条件极值的问题。二次规划也存在一个问题，如果训练样本比较庞大，则会面临维数灾难或者由于内存限制无法用计算机正常处理。这样，我们就需要通过其他算法来进行分类。比如分解算法，增量算法，CSVM算法等等。 支持向量机的应用方面