SVM理论及算法分析

-.z硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集：T=其中，xi∈Rn,yi∈+1,-1,i=1,2,…,N,xi为第i个特征向量或实例，yi假设训练数据集是线性可分的〔存在硬间隔〕，则学习的目标是在特征空间找到一个别离超平面，能将实例分到不同的类。别离超平面方程w∙x+b=0，它由法向量w和截距b决定，可用w,b一般地，当训练数据集线性可分时，存在无穷个别离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得别离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优别离超平面，解唯一。一、模型推导1.函数间隔：一般来说，一个点距离别离超平面的远近可以表示分类预测确实信程度。在超平面w∙x+b=0确定的情况下，|w∙x+b|能够相对地表示〔注意：真实距离为|w∙x+b|∥w∥〕点超平面w,b关于样本点xiγ超平面w,b关于训练数据集T的函数间隔：γ2.几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择别离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，虽然超平面并没有改变，但函数间隔〔它是w,b的线性函数〕却依原比例同等改变。为了将w,b表示的超平面的唯一化，即每个超平面对应Rn+1中的唯一向量w,b，可以对法向量w加以规*化约束∥超平面w,b关于样本点xiγ超平面w,b关于训练数据集T的几何间隔为：γ3.间隔最大化支撑向量机学习的根本想法是求解能够正确划分训练数据集并且几何间隔最大的别离超平面。对于线性可分的训练数据集而言，线性可分别离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的别离超平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进展分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点〔离超平面最近的点〕也有足够多大确实信度将它们分开。因此所要优化的问题表示为：maxs改写为，maxsγ的取值不影响最优化问题的解〔如果w*,b*是最优解，则λw*,λbmaxs〔目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化〕等价变换为〔标准无等式约束的凸二次规划，这是为了运算方便〕，mins凸二次规划问题存在全局最优解w*〔4〕别离超平面与分类决策函数别离超平面:w分类决策函数:f〔5〕支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与别离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即1-yiw∙xi+b=在决定别离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中重要的样本。二、模型求解将原始问题转化为Lagrange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入Lagrange乘子αi1．Lagrange对偶函数：L其中α=α1,α2.对偶问题：max求min∇∇得出w=i=1带入拉格朗日函数，得出min=〔2〕求maxmaxsαi≥转换为求极小minsαi≥根据对偶理论，对上述对偶优化存在，使w*，b3.最优解根据KKT条件∇w∇bαiyiαi由〔a〕求得w其中至少有一个αk*>0〔如果α*=0，则w*y将w*带入KKTy两边同时乘以yk，由于yi=1b因此分类决策函数为f从w*，b*中可以看出它们仅仅依赖于αk*>软间隔线性支撑向量机一、模型推导如果样本集中存在特异点使得样本集线性不可分，即不能满足函数间隔大于等于1不等式约束条件，为了解决这个问题，可以对每个样本点xi，yi引入一个松弛变量y同时对每个松弛变量ξi，支付一个代价ξmin这里，C>0称为惩罚参数，一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化上述目标函数有两层含义，要使的12∥原始优化问题：minsξ这仍是一个二次凸优化，存在全局最优解，w的解是唯一的，但b的解不唯一，b的解存在于一个区间。二、模型求解仍使用Lagrange对偶方法求解1.Lagrange函数L其中，αi2.对偶问题：max(1)求min∇∇∇得出w=i=1C带入拉格朗日函数，得出min注意它与μ无关。〔2〕求maxmaxsαi≥μi≥C-α消去μi，minsαi≥0〔3〕最优解根据KKT条件∇w∇b∇ξαiμiξiyiαiμi由(a)求得w由〔c〕、〔e〕、〔i〕得出CC再结合〔f〕得出如果αi*<C，则ξi*=0；如果由(d)，〔h〕得出如果αi*>0，则yiw*∙x由(j)，(k)得出如果0<αi*<C，则b由(j)，(g)得出如果αi*=0，则ξi由(j)，(k)得出如果αi*=C，则此种情况下，进一步讨论：如果ξi*=如果0<ξi*<1如果ξi*=如果ξi*>因此可以看出，软间隔的支撑向量〔αi*>3.支撑向量的另一种解释最小化以下目标函数：i=1第一项为哪一项经历损失或经历风险，函数称为合页损失函数Lyw∙z也就是说，当样本点被正确分类且函数间隔大于1时，损失函数为0，否则〔xi为支撑向量时〕损失函数是1-yiw∙xi非线性支撑向量机对于分类问题是非线性的〔线性模型无法将正负实例正确分开〕，可以利用核技巧，进展一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。用线性分类方法求解非线性分类问题问题分两步：首先使用一个变换将原空间的数据映射到新空间；然后再新空间里用线性分类学习方法从训练数据中学习分类模型；核技巧应用到支持向量机，其根本思想：通过一个非线性变换将输入空间〔欧氏空间Rn或离散集合〕对应于一个特征空间〔希尔伯特空间H〕，使得在输入空间Rn中的超曲面模型对应于特征空间一、非线性支撑向量机在线性支撑向量机的对偶问题中，无论是目标函数还是决策函数〔别离超平面〕都只涉及输入实例与实例之间的內积，如果把这个內积xi∙xj看作是希尔伯特空间中的两个特征的內积ϕxi'∙ϕxj'=Kxi',使用核函数后的对偶问题的目标函数成为：W最优解成为wb分类决策函数成为f在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。二、核函数方法核函数：设*是输入空间〔欧氏空间Rn的子集或离散集合〕，H为特征空间〔希尔伯特空间〕，如果存在一个从*到Hϕ使得对所有x,z∈X，函数K则称Kx,z为核函数，ϕx为映射函数，ϕx∙ϕ〔希尔伯特空间是完备化的內积空间，其中的每个元素是一个向量〔可以无穷维〕，向量之间定义有內积运算，且空间关于內积诱导出的*数是完备的〕核技巧的想法是：在学习与预测中只定义核函数Kx,z，而不显示地定义映射函数ϕ，因为通常直接计算Kx,z比较容易，而通过ϕx和ϕz计算Kx,z并不容易。注意，ϕx是输入空间Rn到特征空间H的映射，特征空间H一般是高维的，甚至是无穷维的。我们需要的是特征空间中两个特征的內积结果，而不是特征的表示。对于给定的核函数Kx,z，特征空间H〔希尔伯特子空间〕和映射函数ϕ核函数判定定理：设K：X×X→R是对称函数，则Kx,z为正定核函数的充要条件是对任意xi对于一个具体函数Kx,z来说，检验它是否为正定核函数并不容易，因为要去对任意有限输入集验证K对应的Gram矩阵常用核函数：〔1〕多项式核函数：Kx,z=x∙〔2〕高斯核函数：Kx,z--------------------------------------------------------------------------------------------------------------〔3〕字符串核函数：1〕根本定义：有限字符表Σ;字符串s：s1s2…s|s|,字符串字符串连接：st，s和t分别是字符串；长度为n的字符串集合Σn所有字符串的集合：Σ*s的子串u：给定一个指标序列i=i1,i2,…,i2〕映射定义：假设S是长度大于或等于n字符串的集合，s是S的元素，建立字符串集合S到特征空间Hn=RΣn的映射ϕns，RΣn表示定义在Σn上的实数空间，其每一维对应一个字符串ϕn这里，0<λ≤1是一个衰减参数，li表示字符串i的长度，求和在说明：u代表维，如在字符串u维，显然空间有|Σ|n维，每一维是字母表si是表示通过指标序列i，表示的一个s的子串，这个子串可以不连续；si=u表示s的子串li是子串si在s中的指标序列例子：假设Σ为英文字符集，n为3，S为长度大于或等于3的字符串集合，考虑将字符集S映射到特征空间H3=RΣ3，H3的一维对应于字符串asd，这是，字符串“Nasdaq〞在这一维上的值是ϕnNasdaqasd=λ33〕核函数两个字符创s和t的字符串核函数是基于映射的特征空间中的內积：k它给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度。直观上，两个字符串一样的子串越多，它们就越相似，字符串核函数的值就越大，字符串核函数可以由动态规划快速计算。序列最小最优化算法支撑向量机的学习问题可以形式化为求解凸二次规划问题，具有全局最优解，并且有很多最优化算法可以用于求解这一问题。但是当训练样本容量很大时，这些算法往往变得非常低效。序列最小最优化算法，由Platt在1998年提出，它是一种启发式算法，相比照拟高效。SMO算法根本思路是：如果所有变量的解都满足次最优化问题的KKT条件，则这个最优化问题的解就得到了，因为KKT条件是该最优化问题的充分必要条件，否则，选择两个变量，固定其他变量，针对这个两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，算法将原问题不断分解为子问题并对子问题求解，进而到达求解原问题的目的。原始优化问题：mins.tξ对偶问题：mins.t.0子问题的两个变量只有一个是自由变量，假设α1，αα由于y1α如果α2确定，则α优化子问题：SMO算法包含两个局部：求解两个两个变量二次规划的解析方法和选择变量的启发式方法。不失一般性，假设选择的两个变量是α1，α2，其他变量mins.t.0其中，Kij=Kxi,xj〔1〕求解两变量二次规划的解析方法：可行解*围：假设子问题的初始可行解为α1old，0≤α2new0化简为0如果y20α1由〔a〕,〔b〕得出：如果y2=y1，则L如果y20α2由〔a〕,〔d〕得出：如果y2≠y1，则L如果最优解不在约束内，必须被剪辑。假设在沿着约束方向α1y1+α2y2=ς下面忽略不等式约束，求取迭代解α2min由于α1αα带入目标函数W对α2∂===令其为0，得到α将ς=α======令Ei=j=1NyjαjKji+bα=α因此α由y1yα〔2〕变量的〔启发式〕选择方法：SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。1〕第一个变量的选择SMO称选择第1个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量。具体地，检验训练样本点xi，yi是否满足如果αi*=0，则如果0<αi*<C，则如果αi*=C，则α0α该检验是在ϵ*围内进展的。在检验过程中，外层循环首先遍历所有满足条件0<αi<C的样本点，即在间隔边界上的支撑向量点，检验它们是否满足KKT2〕第二个变量的选择SMO称选择第2个变量的过程为内层循环。假设在外层循环中已经找到第1个变量α1，现在要在内层循环中找第2个变量α2。第2个变量的选择的标准是希望能使α2有足够大的变化〔这样新的α从上面的推导中可以发现，α2new依赖于|E1-E2|，为了加快计算速度，一种简单的做法是选择α2，使其对应的|E1-E2|最大。因为α1已定，在特殊情况下，如果内层循环通过以上方法选择的α2不能使目标函数有足够的下降，则采用以下启发式规则继续选择α2；遍历在间隔边界上的支撑向量点，依次将其对应的变量作为α2试用，直到目标函数有足够的下降。假设找不到适宜的α2，则遍历训练数据集；假设仍找不到适宜的α2，则放弃第3〕计算阈值b和差值E每次完成两个变量的优化后，都要重新计算阈值b和Ei，使用迭代的方法更新b根据定义预测误差E1EE1下面讨论如何迭代更新b，即获得bnew显然每次更新完α1new，α2a).如果0<α1newyi=1by带入〔f〕，得出Eb1同样，如果0<b2b).如果α1new=0yy带入〔f〕，得出yyy同样，如果α2yC).如果α1new=Cyy带入〔f〕，得出yyy同样，如果α2y综上可以得出结论：如果0<α1否则如果α1new=α因此α1new≠α2new，如果α1new,α2new中一个是在每次完成两个变量的优化后，还必须更新对应的Ei值，并将它们保存在列表中，Ei值得更新要用到bnewE其中，S是所有支撑向量xj的集合〔由于非支撑向量对用的αj=0序列最小最优化〔SMO〕算法实现输入：训练数据集T=x1，y1，x2，输出：近似解α；1.取初值α0=02.选取优化变量α1〔1〕选择第1个变量α1k+1：在ϵ*围内在训练样本中选取违反KKT条件最严重的样本点：首先遍历满足条件0<a).αib).0c).α〔2〕选择第二个变量α2k+1：如果E1是正，则选择最小的Ei作为E2；如果如