SVM理论与算法分析.docx

硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集：其中，,,, 为第i个特征向量或实例，为的类标记，当时，称为正例，当时，称为负例；为样本点。假设训练数据集是线性可分的（存在硬间隔），那么学习的目标是在特征空间找到一个分离超平面，能将实例分到不同的类。分离超平面方程，它由法向量w和截距b决定，可用表示。分离超平面将特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得分离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面，解唯一。一、模型推导1.函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面确定的情况下，能够相对地表示（注意：真实距离为）点距离超平面的远近。而的符号与类标记的符号是否一致能够表示分类是否正确。所以可用标量来表示分类的正确性及确信度，值为正表示分类正确，值为负表示分类错误。超平面关于样本点的函数间隔为：超平面关于训练数据集T的函数间隔：2.几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，虽然超平面并没有改变，但函数间隔（它是的线性函数）却依原比例同等改变。为了将表示的超平面的唯一化，即每个超平面对应中的唯一向量，可以对法向量w加以规范化约束，这时函数间隔称为几何间隔。超平面关于样本点的几何间隔为：超平面关于训练数据集T的几何间隔为：3.间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点（离超平面最近的点）也有足够多大的确信度将它们分开。因此所要优化的问题表示为：改写为，的取值不影响最优化问题的解（如果是最优解，那么也是最优解，因此是变动的可以取到任意值，如果固定，也就变得唯一了），令,等价变换为，（目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化）等价变换为（标准无等式约束的凸二次规划，这是为了运算方便），凸二次规划问题存在全局最优解。（4）分离超平面与分类决策函数分离超平面:分类决策函数:（5）支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即，对于正例点，支撑向量在超平面上，对于负例点，支撑向量在超平面上，没有实例点落在这两个平行的超平面（间隔边界）之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量w，等于。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中重要的样本。二、模型求解将原始问题转化为Lagrange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入Lagrange乘子，1．Lagrange对偶函数：其中为拉格朗日乘子向量，，。2.对偶问题：求得出带入拉格朗日函数，得出（2）求，转换为求极小，根据对偶理论，对上述对偶优化存在，使是原始问题的解，是对偶问题的解，因此求解原始问题，可以转化为求解对偶问题。3.最优解根据KKT条件--------------------------（a）----------------------------------（b）---------------------------------（c）---------------------------------------（d）-----------------------------------------------------------（e）由（a）求得其中至少有一个（如果，那么，无解，显然它不是原始最优化问题的解），结合KKT条件（c），得出将带入KKT条件，得出两边同时乘以，由于因此分类决策函数为从中可以看出它们仅仅依赖于的特征点，即支撑向量（因为，所有在分隔边界上）；软间隔线性支撑向量机一、模型推导如果样本集中存在特异点使得样本集线性不可分，即不能满足函数间隔大于等于1不等式约束条件，为了解决这个问题，可以对每个样本点引入一个松弛变量，使函数间隔加上松弛变量大于等于1.这样约束条件变为同时对每个松弛变量，支付一个代价，目标函数