下载文档原格式
⽀持向量机（SVM）原理详解SVM简介 ⽀持向量机（support vector machines, SVM）是⼀种⼆分类模型，它的基本模型是定义在特征空间上的间隔最⼤的线性分类器，间隔最⼤使它有别于感知机；SVM还包括核技巧，这使它成为实质上的⾮线性分类器。
SVM的的学习策略就是间隔最⼤化，可形式化为⼀个求解凸⼆次规划的问题，也等价于正则化的合页损失函数的最⼩化问题。
SVM的的学习算法就是求解凸⼆次规划的最优化算法。
⼀、⽀持向量与超平⾯在了解svm算法之前，我们⾸先需要了解⼀下线性分类器这个概念。
⽐如给定⼀系列的数据样本，每个样本都有对应的⼀个标签。
为了使得描述更加直观，我们采⽤⼆维平⾯进⾏解释，⾼维空间原理也是⼀样。
举个简单⼦：如下图所⽰是⼀个⼆维平⾯，平⾯上有两类不同的数据，分别⽤圆圈和⽅块表⽰。
我们可以很简单地找到⼀条直线使得两类数据正好能够完全分开。
但是能将据点完全划开直线不⽌⼀条，那么在如此众多的直线中我们应该选择哪⼀条呢？从直观感觉上看图中的⼏条直线，是不是要更好⼀些呢？是的，我们就是希望寻找到这样的直线，使得距离这条直线最近的点到这条直线的距离最短。
这读起来有些拗⼝，我们从如下右图直观来解释这⼀句话就是要求的两条外⾯的线之间的间隔最⼤。
这是可以理解的，因为假如数据样本是随机出现的，那么这样分割之后数据点落⼊到其类别⼀侧的概率越⾼那么最终预测的准确率也会越⾼。
在⾼维空间中这样的直线称之为超平⾯，因为当维数⼤于三的时候我们已经⽆法想象出这个平⾯的具体样⼦。
那些距离这个超平⾯最近的点就是所谓⽀持向量，实际上如果确定了⽀持向量也就确定了这个超平⾯，找到这些⽀持向量之后其他样本就不会起作⽤了。
⼆、SVM算法原理 2.1 点到超平⾯的距离公式既然这样的直线是存在的，那么我们怎样寻找出这样的直线呢？与⼆维空间类似，超平⾯的⽅程也可以写成⼀下形式：（1） 有了超平⾯的表达式之后之后，我们就可以计算样本点到平⾯的距离了。
支持向量机支持向量机，英文名为support vector machine，一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划（convex quadratic programming）问题的求解,支持向量机的学习算法是求解凸二次规划的最优化算法。
其方法包含构建由简到繁的模型：线性可分支持向量机、线性支持向量机和非线性支持向量机。
线性可分支持向量机假定一特征空间上的训练数据集T={(x1,y1),(x2,y2),⋯,(x N,y N)}，其中x i∈χ= R n,y i∈Y={+1,−1}，i=1,2,⋯,N，x i为第i个特征向量，也就是实例，y i为x i的类标记，当y i=+1时，称x i为正例；当y i=−1时，称x i为负例，(x i,y i)称为样本点。
再假设训练数据集是线性可分的，即存在某个超平面能够将正例和负例完全正确的分开，不妨设分离超平面方程为w∙x+b=0，法向量为w、截距为b。
一般地，当训练数据集线性可分时，存在无穷多个分离超平面可将两类数据正确分开，线性可分支持向量机利用间隔最大化求最优分离超平面，这是解是唯一的。
若最优分离超平面为w∗∙x+b∗=0,则分类决策函数为f(x)=sign(w∗∙x+b∗)。
在上图中，有A、B、C三个点，表示三个实例，设“。
”表示正类，“×”表示负类，则这三个点全在正类。
A距分类超平面较远，若预测该点为正类就比较确信预测是正确的；C距分类超平面较近，若预测该点为负类就不那么确信；B介于AC两者之间，预测为正类的确信度也在A与C之间。
故一般来说，点距离分离超平面的远近可以表示分类预测的确信程度。
在超平面w ∙x +b =0确定的情况下，|w ∙x +b |能够相对地表示点x 到超平面的远近，而w ∙x +b 的符号与类标记y 的符号是否一致可表示分类是否正确，所以y (w ∙x +b )可以来表示分类的真确性及确信度，我们称之为函数间隔。
支持向量机资料支持向量机1基本情况Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。
其原理也从线性可分说起，然后扩展到线性不可分的情况。
甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机（Support Vector Machine，简称SVM）。
支持向量机的提出有很深的理论背景支持向量机方法是在近年来提出的一种新方法。
SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；⑵它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。
例子如图：将1维的“线性不可分”上升到2维后就成为线性可分了。
在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论。
2一般特征⑴SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。
而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
⑵SVM通过最大化决策边界的边缘来控制模型的能力。
尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
⑶通过对数据中每个分类属性引入一个哑变量，SVM可以应用于分类数据。
⑷SVM一般只能用在二类问题，对于多类问题效果不好。
3原理简介SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）．一般的升维都会带来计算的复杂化，SVM 方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．这一切要归功于核函数的展开和计算理论．选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种：⑴线性核函数K(x,y)=x·y；⑵多项式核函数K(x,y)=[(x·y)+1]^d；⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2）⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b）．最优分类面：最优超平面SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用图2的两维情况说明。
⽀持向量机模型⽀持向量机模型(SVM)是⼀个⼆分类模型，基本思想是求解能够正确划分训练数据集并且⼏何间隔最⼤的分离超平⾯，其学习策略便是间隔最⼤化，最终化为⼀个凸⼆次规划问题的求解。
SVM可分为线性可分⽀持向量机、线性⽀持向量机和⾮线性⽀持向量机。
算法推导1. 线性可分⽀持向量机引⼊函数间隔和⼏何间隔线性向量机的基本思想是硬间隔最⼤化，即：\begin{aligned} \max_{w,b} \ \ \ \ &γ\\ s.t.\ \ \ \ \ &y_i·\frac{1}{||w||} ·(w·x_i+b)≥γ，i=1,2,…,N \end{aligned}即：\begin{aligned} \max_{w,b} \ \ \ \ &\frac{ŷ}{||w||}\\ s.t.\ \ \ \ \ &y_i·(w·x_i+b)≥ŷ，i=1,2,…,N \end{aligned}取ŷ=1，得\begin{aligned} \min_{w,b} \ \ \ \ &\frac{1}{2}{||w||}^2\\ s.t.\ \ \ \ \ &y_i·(w·x_i+b)-1≥0，i=1,2,…,N \end{aligned}这是⼀个凸⼆次规划问题，通过引⼊拉格朗⽇乘⼦法，构建拉格朗⽇对偶函数，通过求其对偶函数的解，从⽽得到原始问题的最优解。
定义拉格朗⽇函数：L(w,b,α)= \frac{1}{2}{||w||}^2-\sum_{i=1}^N{α_iy_i (w·x_i+b)}+\sum_{i=1}^N{α_i}其中，α={(α_1,α_2,…,α_N)}^T为拉格朗⽇乘⼦向量，α_i≥0，i=1,2,…,N原始问题的对偶问题是极⼤极⼩问题：\max_α{\min_{w,b} L(w,b,α)}求解对偶问题求\min_{w,b} L(w,b,α)分别对w,b求偏导数并令其为0：\begin{aligned} \nabla_w L(w,b,α)=w-\sum_{i=1}^N{α_i y_i x_i}=0 \\ \nabla_b L(w,b,α)=\sum_{i=1}^N{α_i y_i}=0 \end{aligned}得\begin{aligned} w=\sum_{i=1}^N{α_i y_i x_i} \\ \sum_{i=1}^N{α_i y_i}=0 \end{aligned}代⼊拉格朗⽇函数，得L(w,b,α)= \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j+b)-\sum_{i=1}^N{α_i y_i ((\sum_{j=1}^N{α_j y_jx_j})·x_i+b)}+\sum_{i=1}^Nα_i= -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i即\min_{w,b} L(w,b,α) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_i求\min_{w,b} L(w,b,α)对α的极⼤:\max_{α}\ \ \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)+\sum_{i=1}^Nα_is.t.\ \ \ \sum_{i=1}^N{α_i y_i}=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ α_i≥0，i=1,2,…,N即：\min_{α}\ \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N α_i α_j y_i y_j (x_i·x_j)-\sum_{i=1}^Nα_is.t.\ \ \ \sum_{i=1}^N{α_i y_i}=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ α_i≥0，i=1,2,…,N求得最优解1\alpha^x={({\alpha_1}^x,{\alpha_2}^x,…,{\alpha_N}^x)}^{T}计算w^*=\sum_{i=1}^N {α_i}^x y_i x_i并选择α^x的⼀个正分量{α_j}^x>0，计算b^x=y_i-\sum_{i=1}^N {α_i}^x y_i (x_i·x_j)求得分类决策函数：f(x)=sign(w^x·x+b^x)可知w^x，b^x只依赖训练数据中对应于{α_i}^x>0的样本点(x_i,y_i)，⽽其他样本点对w^x，b^x没有影响。
⽀持向量机的简单介绍⾸先说，这是我写的最烂的，因为我⾃⼰有⼀些也没有弄明⽩，强烈建议别看，强烈不建议看哦。
（我不暂时不想花太多时间去搞它，因为我⽤不着它，如果⽤到它的时候到好好看看吧，我了解⼀下原理，⼀些细节吧我有⼀些想不明⽩）下⾯这是我的简单介绍与理解，或者理解的不够深。
这玩意的作⽤就是⽤于解决问题的吧，⼀切算法都要向解决的问题去靠，如果单純停留在数学分析上，很迷迷糊糊的哦。
所以，我们站在⼀定⾼度上去看这个⽀持向量机哈它⼲什么的？⽀持向量机它本质上还是解决⼆分类问题的啦，如果你想要解决多分类问题，好啊，最简单的办法就是：你多分⼏次就可以了啊，对吧。
为什么叫⽀持向量机呢，外国⼈起的名字哎，不过后⾯会出现⽀持向量哦，也算是和名字相互对应吧。
⽀持向量机要⼲的事就是找到⼀个分界⾯，放到两个类别之间，就把它们分开了，如⼆维上，是⼀条直线，三维上就⼀个平⾯，四维上就是⼀个三维的东西了。
如果在低维不可分时，就先通过核函数把低维数据映射到⾼维，⾼维上变成线性可分的以后，然后呢，在⾼维上再⽤⽀持向量机进⾏分就可以了。
反正吧，⽀持向量机就是解决线性可分的问题的啦。
（解决线性不可分的问题，那是核函数的功劳，反正我认为是这样的）下⾯我们要解决⼀个优化问题：现在呢，我们要解决⼀个问题，如果所图1所⽰哈，我们现在现在把这两类分开，看上去很简单似的，我们就要画⼀条线就可以了哈，但是呢，仔细想想，这条线应该如何画呢？⽤⼈脑⼦⼀想就能想明⽩按图2画，怎么如何要⽤程序把它弄出来呢这就是优化理论的问题了吧，现在呢，就要把实际问题转化为数学描述了。
怎么办？？下⾯具体到数学上描述描述。
对于上⾯的两种类别，我们分为两类，⼀类⽤ 1 表⽰，⼀类⽤－1 表⽰。
采⽤logistic的回归⽅式，我们⽤公式表⽰为：，其中函数g(x) 是这样的：当 x >=0时， g(x) ＝1；当 x <0时， g(x) ＝－1,即相当于⼀个感知器；按如上定义，我们要画的那条线就是表⽰为 w T x + b ＝ 0 的那条线了；当w T x + b>>0时，或w T x + b<< 0说明正的样本点离的分界线的距离就越远哈。
机器学习基础篇：支持向量机（SVM）理论与实践您想知道的人工智能干货，第一时间送达编译 | AI有道什么是支持向量机（SVM）？支持向量机(SVM) 是一种相对简单的监督机器学习算法，用于解决分类或回归问题。
它更适合分类，但有时对回归也非常有用。
SVM 算法的本质是在不同的数据类型之间找到一个超平面来创建边界。
在二维空间中，这个超平面是一条直线。
在SVM算法中，我们在N 维空间中绘制数据集中的每个数据项，其中 N 是数据中特征/属性的数量。
接下来，我们找到最佳的超平面来对不同类型的数据进行分类。
因此我们可以了解到SVM 本质上只能解决二分类的问题（即，在两个类之间进行选择）。
但是，如今有多种技术可用于解决多分类的问题。
支持向量机（SVM）解决多分类问题为了在多分类问题上使用SVM，我们可以为每一类数据创建一个二元分类器。
每个分类器的两个结果将是：•数据点属于该类或•数据点不属于该类或例如，在水果分类问题中，要进行多类分类，我们可以为每个水果创建一个二元分类器。
例如，“芒果”类，将有一个二元分类器来预测它是芒果还是不是芒果。
选择得分最高的分类器作为 SVM 的输出。
复杂的 SVM（非线性可分）SVM对线性可分数据进行分类有比较好的表现。
线性可分数据是任何可以绘制在图形中并且可以使用直线进行分类的数据。
我们使用带内核的SVM 来处理非线性可分的数据。
比如说，我们把一维非线性可分的数据可以转换为二维数据，该数据将将在二维上线性可分。
这是通过将每个一维数据点映射到相应的二维有序对来完成的。
因此，对于任何维度的任何非线性可分数据，我们可以将数据映射到更高的维度，然后使其变得线性可分。
这是一个非常强大和普遍的转变。
内核不是数据点之间相似性的度量。
核化 SVM 中的核函数告诉您，给定原始特征空间中的两个数据点，新变换的特征空间中的点之间的相似度是多少。
现有各种可用的内核函数，其中两个比较流行：Radial BasisFunction Kernel (RBF)：变换后的特征空间中两点之间的相似度是向量与原始输入空间之间距离的指数衰减函数，如下所示。
第三十一章 支持向量机支持向量机是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问 题的新工具，最初由 V.Vapnik 等人提出，近几年来在其理论研究和算法实现等方面都 取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的 理论基础和实现途径的基本框架都已形成。
§1 支持向量分类机的基本原理根据给定的训练集lT = {(x 1,y 1 ), (x 2 ,y 2 ),L ,(x l ,y l )}∈ ( X ⨯ Y ) ，其中 x ∈ X = R n ， X 称为输入空间，输入空间中的每一个点 x 由 n 个属性特征组成， i i ny i ∈Y = {-1,1},i = 1,L ,l 。
寻找 R 上的一个实值函数 g (x ) ，以便用分类函数f (x ) = sgn(g (x )),推断任意一个模式 x 相对应的 y 值的问题为分类问题。
1.1 线性可分支持向量分类机考虑训练集 T ，若 ∃ω ∈ R n， b ∈ R 和正数 ε ，使得对所有使 y = 1的下标 i 有 i (ω ⋅ x i ) + b ≥ ε（这里 (ω ⋅ x i ) 表示向量 ω 和 x i 的内积），而对所有使 y i = -1 的下标 i 有 (ω ⋅ x i ) + b ≤ -ε ，则称训练集 T 线性可分，称相应的分类问题是线性可分的。
记两类样本集分别为 M = {x i | y i = 1, x i ∈T }， M = {x i | y i = -1, x i ∈T }。
定义 M + 的凸包 conv(M + ) 为+- ♣ N + N +↔ conv(M +) = ♦x = ∑λ x | ∑ λ λ ≥ 0, j = 1,L , N + ; x ∈ M + ←, = 1, j j j j j ♥ ↑j =1 j =1 M - 的凸包 conv(M - ) 为 ♣ N - N -↔ conv(M - ) = ♦x = ∑λ x | ∑λ λ ≥ 0, j = 1,L , N - ; x ∈ M - ←.= 1, j j j j j ♥ ↑j =1 j =1 其中 N + 表示 + 1 类样本集中样本点的个数， N - 表示 - 1类样本集中样本点的个数，定 理 1 给出了训练集 T 线性可分与两类样本集凸包之间的关系。
定理 1 训练集 T 线性可分的充要条件是， T 的两类样本集 M + 和 M - 的凸包相离。
如下图所示图 1 训练集 T 线性可分时两类样本点集的凸包证明：①必要性-762-+ -若 T 是线性可分的，M = {x i | y i = 1, x i ∈T }，M = {x i | y i = -1, x i ∈T }，由线 性可分的定义可知，存在超平面 H = {x ∈ R n: (ω ⋅ x ) + b = 0} 和 ε > 0 ，使得(ω ⋅ x i ) + b ≥ ε ， ∀x i ∈ M 且 (ω ⋅ x i ) + b ≤ -ε ， ∀x i ∈ M . + -而正类点集的凸包中的任意一点 x 和负类点集的凸包中的任意一点 x ' 可分别表示为N + N - x = ∑αi x i 和 x ' = ∑ β j x ' ji =1 j =1N +N -其中αi ≥ 0, β j ≥ 0 且 ∑αi= 1， ∑β j = 1。
i =1j =1于是可以得到N + N + N +(ω ⋅ x ) + b = ω ⋅ ∑αi x i + b = ∑αi ((ω ⋅ x i ) + b ) ≥ ε ∑αi = ε > 0i =1 i =1 i =1 N - N - N - ) + b ) ≤ -ε β = -ε < 0 j =1 ∑ j ∑ j ∑ j (ω ⋅ x ') + b = ω ⋅ β x ' + b = β ((ω ⋅ x ' j jj =1 j =1 由此可见，正负两类点集的凸包位于超平面 (ω ⋅ x ) + b = 0 的两侧，故两个凸包相离。
②充分性设两类点集 M +，M -的凸包相离。
因为两个凸包都是闭凸集，且有界，根据凸集 强分离定理，可知存在一个超平面 H = {x ∈ R n: (ω ⋅ x ) + b = 0} 强分离这两个凸包， 即存在正数 ε > 0 ，使得对 M +， M -的凸包中的任意点 x 和 x ' 分别有(ω ⋅ x ) + b ≥ ε(ω ⋅ x ') + b ≤ -ε显然特别的，对于任意的 x ∈ M + ，有 (ω ⋅ x ) + b ≥ ε ，对于任意的 x ∈ M -，有 i i i (ω ⋅ x i ) + b ≤ -ε ，由训练集线性可分的定义可知 T 是线性可分的。
由于空间 R n 中超平面都可以写为 (ω ⋅ x ) + b = 0 的形式，参数 (ω, b ) 乘以任意一个非零常数后得到的是同一个超平面，定义满足条件♠♣ y i ((ω ⋅ x i ) + b ) ≥ 0, i = 1,L , l ♦min ω ⋅ x (i ) + b = 1 ♠ ♥ i =1, ,lL 的超平面为规范超平面。
定理 2 当训练集样本为线性可分时，存在唯一的规范超平面 (ω ⋅ x ) + b = 0 ，使 得♣(ω ⋅ x i ) + b ≥ 1 y i = 1; （1）♦♥(ω ⋅ x i ) + b ≤ -1 y i = -1.证明：规范超平面的存在性是显然的，下证其唯一性。
假设其规范超平面有两个： (ω'⋅x ) + b ' = 0 和 (ω"⋅x ) + b ' = 0 。
由于规范超平面满 足条件-763-♠♣ y i ((ω ⋅ x i ) + b ) ≥ 0, i = 1,L , l , ♦minω ⋅ x ( i ) + b = 1. ♠♥i =1, ,lL 由第二个条件可知ω' = ω"， b ' = b ' ，或者ω' = -ω" ， b ' = -b ' .第一个条件说明 ω' = -ω" ， b ' = -b ' 不可能成立，故唯一性得证。
式（1）中满足 (ω ⋅ x i ) + b = ±1成立的 x i 称为普通支持向量，对于线性可分的情况 来说，只有它们在建立分类超平面的时候起到了作用，普通支持向量通常只占样本集很 小的一部分，故而也说明 SVM 具有稀疏性。
对于 y i = 1类的样本点，其与规范超平面 的间隔为(ω ⋅ x i ) + b 1ωmin y i =1 = ， ω 对于 y i = -1 类的样本点，其与规范超平面的间隔为(ω ⋅ x i ) + b 1 ωmin y i =-1 = ， ω 2 ω 2ω则普通支持向量间的间隔为 。
最优超平面即意味着最大化 。
如图 2 所示 图 2 线性可分支持向量分类机(ω ⋅ x ) + b = ±1称为分类边界，于是寻找最优超平面的问题可以转化为如下的二次规 划问题1 22ω min（2）s.t. y i ((ω ⋅ x i ) + b ) ≥ 1 i = 1,L , l 1 22ω 是 ω 的凸函数，并且约束条件都是线性的。
该问题的特点是目标函数 引入 Lagrange 函数-764-l+ ∑αi (1 - y i ((ω ⋅ x i) + b ))1 2 L (ω, b ,α ) = 2 ω i =1其中α = (α L ,α )T ∈ R l +为 Lagrange 乘子。
根据 wolfe 对偶的定义，通过对原问题 1l 中各变量的偏导置零可得l⇒ ω = ∑αi y i x ii =1l∂L ∂ω ∂L∂b = 0 ⇒ ∑α y = 0 = 0 i i i =1带入 Lagrange 函数化为原问题的 Lagrange 对偶问题1 2 l l l∑∑ i j i j i j ∑ i max - α y y α α (x ⋅ x ) + α i =1 j =1 i =1l∑ y i αis.t.= 0（3）i =1αi ≥ 0, i = 1,L ,l* * * T求解上述最优化问题，得到最优解α = (α ,Lα ) ，计算 1 l lω = ∑α y x **i i ii =1 由 KKT 互补条件知α * (1 - y ((ω* ⋅ x ) + b *)) = 0 i i i可得，只有当 x 为支持向量的时候，对应的 α 才为正，否则皆为零。
选择α 的一个 * *i i 正分量α *，并以此计算j lb = y j - ∑ y i α (x i ⋅ x j ),**i i =1于是构造分类超平面 (ω* ⋅ x ) + b *= 0 ，并由此求得决策函数lg (x ) = α* y (x ⋅ x ) + b *, i =1 得到分类函数lf (x ) = sgn( α* y (x ⋅ x ) + b * )i =1 从而对未知样本进行分类。
1.2 线性支持向量分类机 ∑ i i i∑ i i i （4）当训练集 T 的两类样本线性可分时，除了普通支持向量分布在两个分类边界 (ω ⋅ x i ) + b = ±1上外，其余的所有样本点都分布在分类边界以外。
此时构造的超平面 是硬间隔超平面。
当训练集 T 的两类样本近似线性可分时，即允许存在不满足约束条 件y i ((ω ⋅ x i ) + b ) ≥ 1-765-的样本点后，仍然能继续使用超平面进行划分。
只是这时要对间隔进行“软化”，构造 软间隔超平面。
简言之就是在两个分类边界 (ω ⋅ x i ) + b = ±1之间允许出现样本点，这 类样本点被称为边界支持向量。
显然两类样本点集的凸包是相交的，只是相交的部分较 小。
线性支持向量分类机如图 3 所示。
图 3 线性支持向量分类机软化的方法是通过引入松弛变量ξi ≥ 0, i = 1,L , l来得到“软化”的约束条件y i ((ω ⋅ x i ) + b ) ≥ 1 - ξi i = 1,L , l ,当 ξi 充分大时，样本点总是满足上述的约束条件，但是也要设法避免 ξi 取太大的 值，为此要在目标函数中对它进行惩罚，得到如下的二次规划问题1 2 l2+ C ξ ,∑ i ω min i =1s.t. y i ((ω ⋅ x i ) + b ) ≥ 1 - ξi , ξi ≥ 0, i = 1,L , l .其中 C > 0 是一个惩罚参数。
