《SVM理论与算法分析》由会员分享，可在线阅读，更多相关《SVM理论与算法分析（20页珍藏版）》请在金锄头文库上搜索。
1、硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集：，其中，为第i个特征向量或实例，为的类标记，当时，称为正例，当时，称为负例；，为样本点。假设训练数据集是线性可分的（存在硬间隔），那么学习的目标是在特征空间找到一个分离超平面，能将实例分到不同的类。分离超平面方程，它由法向量w和截距b决定，可用表示。分离超平面将特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得分离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面，解唯一
2、。一、模型推导1 .函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面确定的情况下，能够相对地表示（注意：真实距离为）点距离超平面的远近。而的符号与类标记的符号是否一致能够表示分类是否正确。所以可用标量来表示分类的正确性及确信度，值为正表示分类正确，值为负表示分类错误。超平面关于样本点，的函数间隔为：超平面关于训练数据集T的函数间隔:2 .几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b,虽然超平面并没有改变，但函数间隔（它是的线性函数）却依原比例同等改变。为了将表示的超平面的唯一化，即每个
3、超平面对应中的唯一向量，可以对法向量w加以规范化约束，这时函数间隔称为几何间隔。超平面关于样本点，的几何间隔为：超平面关于训练数据集T的几何间隔为:3 .间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点（离超平面最近的点）也有足够多大的确信度将它们分开。因此所要优化的问题表示为：
4、改写为,的取值不影响最优化问题的解（如果是最优解，那么也是最优解，因此是变动的可以取到任意值，如果固定，也就变得唯一了），令，等价变换为，（目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化）等价变换为（标准无等式约束的凸二次规划，这是为了运算方便），二二次规划问题存在全局最优解（4）分离超平面与分类决策函数分离超平面：分类决策函数：（5）支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即，对于正例点，支撑向量在超平面上，对于负例点，支撑向量在超平面上，没有实例点落在这两个
5、平行的超平面（间隔边界）之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量w,等于在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中重要的样本。二、模型求解将原始问题转化为Lagrange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入Lagrange乘子,1.Lagrange对偶函数：其中2.对偶问题:为拉格朗日乘子向量,(1)求得出带入拉格朗日函数，得出(2)求转换为求极小根据对偶理论，对上述对偶优化存在，使，是原始问
6、题的解，是对偶问题的解，因此求解原始问题,可以转化为求解对偶问题。3.最优解根据KKT条件(a)(b)(c)(d)(e)KKT由（a）求得其中至少有一个（如果，那么，无解，显然它不是原始最优化问题的解），结合条件（c），得出将带入KKT条件，得出两边同时乘以，由于因此分类决策函数为从，中可以看出它们仅仅依赖于的特征点，即支撑向量（因为，所有在分隔边界上）；软间隔线性支撑向量机一、模型推导如果样本集中存在特异点使得样本集线性不可分，即不能满足函数间隔大于等于1不等式约束条件，为了解决这个问题，可以对每个样本点，引入一个松弛变量，使函数间隔加上松弛变量大于等于1.这样约束条件变为同时对每个松弛变量
7、，支付一个代价，目标函数变成这里，称为惩罚参数，一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化上述目标函数有两层含义，要使的-尽量小即间隔尽量大，同时使的误分类的点的个数尽量小，C是调和二者的系数。这时的间隔称为软间隔，因为间隔内含义特异点。原始优化问题：这仍是一个二次凸优化，存在全局最优解，w的解是唯一的，但b的解不唯一，b的解存在于一个区间二、模型求解仍使用Lagrange对偶方法求解I.Lagrange函数其中，2.对偶问题:得出带入拉格朗日函数，得出注意它与无关。(2)求消去，转换为求极小(3)最优解根据KKT条件(b)(c)(d)(e)(h)(i)
8、由(a)求得由(c)、(e)、(i)得出(j)不确定；-(k)再结合(f)得出如果，那么；如果由(d),(h)得出如果，那么；如果由(j),(k)得出如果，那么，由(j),(g)得出如果，那么，；这说明位于间隔边界上或以外；由(j),(k)得出如果，那么，；此种情况下，进一步讨论：如果，那么在间隔边界上；如果，那么分类正确，在间隔边界与分离超平面之间；如果，那么在分界面上；如果，那么在分离超平面误分一侧；因此可以看出，软间隔的支撑向量()或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。3.支撑向量的另一种解释最小化以下目标函数：第一项是经验损失或经验风险，函数称为合
9、页损失函数示以下取正值得函数。也就是说，当样本点被正确分类且函数间隔大于1时,损失函数为0,否则（为支撑向量时）损失函数是,第二项是系数为w范数，是正则化项；这两种优化是等价的（通过变量替换方法）；非线性支撑向量机对于分类问题是非线性的（线性模型无法将正负实例正确分开），可以利用核技巧，进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。用线性分类方法求解非线性分类问题问题分两步：首先使用一个变换将原空间的数据映射到新空间；然后再新空间里用线性分类学习方法从训练数据中学习分类模型;核技巧应用到支持向量机，其基本思想：通过一个非线性变换将输入空间（欧
10、氏空间或离散集合）对应于一个特征空间（希尔伯特空间H）,使得在输入空间中的超曲面模型对应于特征空间H中的超平面模型（支撑向量机），这样分类问题的学习任务通过在特征空间中求解线性支撑向量机就可以完成。一、非线性支撑向量机在线性支撑向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积，如果把这个内积看作是希尔伯特空间中的两个特征的内积，其中，那么对于在低维线性不可分的样本集，如果通过映射变换到高维希尔伯特空间变得线性可分（假设能找到这样的合适的映射），那么就可以使用核函数代替计算，这里，未知，但，已知。使用核函数后的对偶问题的目标函数成为:最优解成为分类决策
11、函数成为在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。二、核函数方法核函数：设X是输入空间（欧氏空间的子集或离散集合），H为特征空间（希尔伯特空间），如果存在一个从X到H的映射，使得对所有，函数满足条件则称为核函数，为映射函数，为和内积；（希尔伯特空间是完备化的内积空间，其中的每个元素是一个向量（可以无穷维），向量之间定义有内积运算，且空间关于内积诱导出的范数是完备的）核技巧的想法是：在学习与预测中只定义核函数，而不显示地定义映射函数，因为通常直接计算比较容易，而通过和计算并不容易。注意，是输入空间到特征空间H的映射，特征空间H一般是高维的，甚至是无穷维的。
12、我们需要的是特征空间中两个特征的内积结果，而不是特征的表示。如果我们能通过简单的函数得到的内积，那就简化了问题，不用考虑的形式，这正是核函数的妙用之处。对于给定的核函数，特征空间H（希尔伯特子空间）和映射函数的取法不唯一，因为核函数给出的是映射后的内积结果，所选取的映射过程可能是不同的。核函数判定定理：设：是对称函数，则为正定核函数的充要条件是对任意，,对应的Gram矩阵：是半正定的。对于一个具体函数来说，检验它是否为正定核函数并不容易，因为要去对任意有限输入集验证K对应的Gram矩阵是否为半正定。在实际问题中往往应用已有的核函数。常用核函数：（1）多项式核函数：，对应的支撑向量机是一个p次多
13、项式分类器；（2）高斯核函数：，对应的支撑向量机是高斯径向基函数分类器；（3）字符串核函数:1）基本定义：有限字符表；字符串s：,字符串s的长度，空字符串长度为0；字符串连接：，s和t分别是字符串；长度为n的字符串集合;所有字符串的集合：;s的子串u：给定一个指标序列，其长度记作，如果i是连续的，则；否则。2）映射定义：假设S是长度大于或等于n字符串的集合，s是S的元素，建立字符串集合S到特征空间的映射，表示定义在上的实数空间，其每一维对应一个字符串，映射将字符串s对应于空间中的一个向量，其在u维上的取值为，这里，是一个衰减参数，表示字符串i的长度，求和在s中所有与u相同的子串上进行。说明：u
14、代表维，如在字符串u维，显然空间有维，每一维是字母表上的一个长度为n的字符串；是表示通过指标序列i，表示的一个s的子串，这个子串可以不连续；表示s的子串等于u；是子串在s中的指标序列i的最后一个分量减去第一个分量然后加一；例子：假设W为英文字符集，n为3,S为长度大于或等于3的字符串集合，考虑将字符集S映射到特征空间，的一维对应于字符串asd，这是，字符串“Nasdaq”在这一维上的值是,只有一个子串asd，序号是234；字符串“lassdas”在这一维上的值是，因为有两个asd，序号分别为236,246;3）核函数两个字符创s和t的字符串核函数是基于映射的特征空间中的内积：它给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度。直观上，两个字符串相同的子串越多，它们就越相似，字符串核函数的值就越大，字符串核函数可以由动态规划快速计算。序列最小最优化算法支撑向量机的学习问题可以形式化为求解凸二次规划问题，具有全局最优解，并且有很多最优化算法可以用于求解这一问题。但是当训练样本容量很大时，这些算法往往变得非常低效。序列最小最优化算法，由Platt在1998年提出，它是一种启发式算法，相对比较高效。SMO算法基本思路是：如果所有变量的解都满足次最优化问题的KKT条件
