软边界支持向量机

第五十四章

软边界支持向量机

如果点集u1，…，up和v1，…，vq不是线性可分的（使用ui，vj∈rn），我们可以使用线性规划的一个技巧，即引入非负的“松弛变量”来放松“硬”约束。

w>ui−b≥δi=1，…，p

−w>vj+b≥δj=1，…，q

从第49.5节到“软”约束的问题（SVMH1）

回想一下

如果为0，则点UI可能被错误分类，从某种意义上说，它可能属于边缘（板），甚至属于对负（红色）点进行分类的错误半空间。见图54.1（2）和（3）。同样，如果ξj>0，点vj可能被错误分类，从某种意义上说，它可能属于边缘（板），甚至属于对正（蓝）点进行分类的错误半空间。我们可以将i视为违反约束w>ui−b≥δ的程度的度量，而将ξj视为违反约束w>vj+b≥δ的程度的度量。如果=0，则恢复原始约束。通过足够大，这些约束总是可以满足的。我们加上约束w>w≤1，然后最小化−δ。

如果不是问题的约束（svmh1），我们使用硬约束

w>ui−b≥1 i=1，…，p

−w>vj+b≥1 j=1，…，q

问题（svmh2）（参见示例49.6），然后我们放松到软约束

在这种情况下，对w没有约束，但我们将（1/2）w>w最小化。

理想情况下，我们希望找到一个分离超平面，以最小化错误分类点的数量，这意味着变量应尽可能小，但在最大化利润（板的厚度）和最小化错误分类点的数量上存在权衡。这反映在目标函数的选择上，根据我们是最小化变量的线性函数，还是这些变量的二次函数，或者是否在目标函数中包含术语（1/2）b2，有几个选项。这些方法被称为支持向量分类算法（简称SVC算法）。

SVC算法寻求一个“最优”分离方程w>x-b=0的超平面h。如果有新的数据x∈rn出现，我们可以通过计算量w>x−b的符号，确定由超平面h确定的两个半空间中属于哪一个来对其进行分类。函数sgn:r→−1,1由下式给出：

然后我们定义了与方程w>x−b=0的超平面h相关的（二进制）分类函数，即f（x）=sgn（w>x−b）。

值得注意的是，所有已知的寻找超平面的优化问题都具有这样的性质：权重向量w和常数b是由只涉及输入数据点ui和vj内积的表达式给出的，分类函数也是如此

f（x）=sgn（w>x-b）。

这是一个关键的事实，它允许使用内核方法对支持向量机进行广泛的推广。

内核的方法包括假设输入空间rn嵌入一个更大（可能是无限维）的欧几里得空间f（内积h−−−i），通常称为特征空间，使用函数

⑨：RN→F

称为功能图。函数k:rn×rn→r由

κ（x，y）=h（x），（y）i

是嵌入的核心函数，见第53章。我们的想法是，特征映射“展开”输入数据，使其在高维空间f中更具线性。现在，即使我们不知道特征空间f是什么以及嵌入映射是什么，我们也可以假装在f中解决嵌入数据点的分离问题。ts（ui）和（vj）。因此我们求方程的超平面H

hw，ζi−b=0，ζ∈f，

在特征空间F中，尝试分离点（ui）和点（vj）。如我们所说，结果表明，w和b是通过只涉及内积的表达式给出的，其中κ（ui，uj）=h（ui），（uj）i，κ（ui，vj）=h（ui），（vj）i，和κ（vi，vj）=h（vi），（vj）i形成对称（p+q）×（p+q）矩阵k（核矩阵），由下式给出

）1≤I≤P，1≤J≤Q

κ（vi−p，vj−q）p+1≤i≤p+q，p+1≤j≤p+q。

然后是分类功能

f（x）=sgn（hw，（x）i-b）

对于原始数据空间中的点，Rn也仅用矩阵k和内积κ（ui，x）=h（ui），（x）i和κ（vj，x）=h（vj），（x）i表示。因此，在原始数据空间Rn中，超曲面

S=X∈RN HW，（X）I−B=0

分离数据点ui和vj，但它不是rn的仿射子空间。分类函数f告诉我们S的“边”是一个新的数据点x∈rn。因此，我们设法通过假设存在一个嵌入的瓒：rn→f，即使我们不知道它是什么，但通过给定的核函数κ：rn×rn→r可以访问f，将不可被仿射超平面、非仿射超曲面分离的数据点ui和vj分开。由内积k（x，y）=h（x），（y）i。

在实践中，使用内核方法的艺术就是选择正确的内核（就像《印第安纳琼斯》中的骑士所说的那样，“明智地选择”。

内核的方法非常灵活。它还适用于支持向量机的软边缘版本，也适用于回归问题、主成分分析（PCA）以及机器学习中出现的其他问题。

在sch–olkopf和smola[141]以及Shawe–Taylor和Christianini[154]中发现了对内核方法的全面介绍。另见Bishop[23]。

首先考虑问题产生的软边际支持向量机（SVMH1）。

54.1软边界支持向量机；（SVMS1）

在本节中，我们推导了与以下版本的问题（svmh1）产生的软边值svm相关的双函数g，其中边值δ的最大化被−δ的最小化所取代，并且在这里我们添加了一个“正则化项”，其目的是使和ξ∈RQ稀疏（即，尝试

make有尽可能多的零），其中k>0是一个固定常数，可以调整以确定这个正则化项的影响。如果原问题（svms1）有一个最优解（w，δ，b，，ξ），我们试图用对偶函数g来获得它，但是我们可以看到，在这个问题的特殊公式中，约束w>w≤1会引起问题，即使它是凸的。

软利润SVM（SVMS1）：

最小化

习惯上写`=p+q。

对于这个问题，原问题可能有一个Kwk=1且δ>0的最优解（w，δ，b，，ξ），但如果点集不是线性可分的，则对偶的最优解可能不会产生w。

我们问题的目标函数是仿射，唯一的非仿射约束w>w≤1是凸的。这个约束是合格的，因为对于任何w=06，这样w>w<1，对于任何δ>0和任何b，我们可以选取足够大的，从而满足常数。因此，根据定理49.16（2），如果原始问题（SVMS1）有一个最优解，那么对偶问题也有一个解，对偶间隙为零。

不幸的是，这并不意味着对偶的一个最优解产生一个原始解的最优解，因为定理49.16（1）的假设不成立。一般来说，可能没有一个唯一的向量（w，，ξ，b，δ），使得

如果集合ui和vj不是线性可分的，那么对偶问题可能有一个解γ=0，

，

和

，

因此定义了双函数g（λ，μ，α，β，γ），它是一个偏函数，其值为g（λ，μ，α，β，0）=0。这样一对（λ，μ）对应于两个凸组合的系数

十倍

2λiui=2μjvj

I=1 J=1

它对应于凸壳conv（u1，…，up）和conv（v1，…，vq）的（非空）交叉点中的相同点。结果表明，W与对偶函数的唯一联系是方程

，

当γ=0时，这个方程为0=0，所以对偶问题对于确定w是无用的。这一点在文献中似乎被遗漏了（例如，在Shawe–Taylor和Christianini[154]第7.2节）。对偶问题证明了δ≥0。然而，如果γ=06，则w由双组分的任何溶液（λ，μ）测定。

仍然需要计算δ和b，这可以在我们称之为标准裕度假设的温和假设下进行。

如果（w，δ，b，，ξ）是问题（svms1）的最优解，则将点ui和vj分为以下几类：

=0，则点ui被正确分类，位于蓝色边缘（方程w>x=b+η的超平面hw，b+η）或蓝色边缘的正确侧（蓝色侧）。同样，如果ξj=0，则点vj被正确分类，并位于红边（方程w>x=b−η的超平面hw，b−η）或红边（红边）的正确一侧。

（2）如果为0，则点ui位于边缘（板）内，但位于分离超平面的正确侧（蓝色侧）。如果，那么UI位于分离的超平面上。同样，如果0<ξj≤η，则点vj位于边缘（板）内，但位于分离超平面的正确侧（红色侧）。如果ξj=η，则vj位于分离超平面上。

，则点ui位于分离超平面的错误一侧（红色一侧）；它被错误分类。同样，如果ξj>η，那么点vj位于分离超平面（蓝色面）的错误一侧；它被错误分类。

设为与不等式相关联的拉格朗日乘数，设为拉格朗日乘数与不等式相关联−w>vj+b≥δ−ξj，设为与不等式相关联的拉格朗日乘数为与不等式相关联的拉格朗日乘数ξj≥0，a让γ∈r+是与不等式w>w≤1相关的拉格朗日乘子。

线性约束由2（p+q）×n+p+q+2）矩阵给出，该矩阵以块形式给出：

，

其中x是n×（p+q）矩阵

，

线性约束表示为

更明确地说，c是以下矩阵：

−U>1 . … γ −U>P γ v1> γ …… γ γ	1 … 零零 …	···… ········· ···…	零 … 1 零 …	零 … 0比1 …	···… ········· ···…	零 … 零零 …	一 … 1比1 …	1℃ 1 1 γ

VQ>0·····0··1·····C=

0−1····0 0··0 0 0··

 

…………………………………………………………

 

0 0························0 0 0

 

0 0·····0····1···0 0 0··

0 0·············0 0 0

目标函数由

给出了，和γ∈r+的拉格朗日

通过

自从

拉格朗日可以写成

为了找到双函数g（λ，μ，α，β，γ），我们将w，ξ，b和δ最小化。因为拉格朗日是凸的（

r×r，一个凸开集，根据定理39.11，拉格朗日在（iff=0）中有一个最小值，因此我们计算了关于w，，ξ，b，δ的梯度，得到

通过设置=0，我们得到方程

（W）

和

λ+α=k1pμ+β=k1q

1>pλ=1>qμ1>pλ+1>qμ=1。

第二和第三个方程等价于不等式

0≤λi，μj≤k，i=1，…，p，j=1，…，q，

通常称为箱约束，第四和第五个方程产生

首先让我们考虑一下奇异情况γ=0。在这种情况下，（w）意味着

，

而术语γ（w>w−1）在拉格朗日中缺失，考虑到上面的其他四个方程，它减少到

总之，我们证明了如果γ=0，那么

___0，如果g（λ，，α，β，0）=

__−∞其他方式和。

几何上，（λ，μ）对应于两个凸组合的系数

与凸壳conv（u1，…，up）和conv（v1，…，vq）交叉点的相同点相对应，如果集合ui和vj不是线性可分的。如果集合ui和vj是线性可分离的，那么凸壳conv（u1，…，up）和conv（v1，…，vq）是不相交的，这意味着γ>0。

现在假设γ>0。把方程（w）中的w插回到拉格朗日方程中，简化后，我们得到

因此，如果γ>0，双函数独立于α，β，并由下式得出：

−∞否则。

因为x>x是对称正定的，γ≥0，显然

g（λ，μ，α，β，γ）≤0

对于所有γ>0。

双程序由

最大化

γ=0时为0

从属于

同样，如果γ=0，那么

关于γ>0的最大化产生

所以我们得到

最后，由于g（λ，μ）=0和=0，双程序相当于以下最小化程序：

最小化

注意，约束意味着必须选择k，以便

通过使用基于梯度下降的数值程序（例如第51.6节中的ADMM）来求解双程序。如果原始问题是可解的，则会得到λ和μ的解。

如果最佳值为0，则γ=0和=0，因此在这种情况下不可能确定w。但是，如果最佳值大于0，则一旦通过（w）获得λ和μ的溶液，我们就可以

所以我们得到

，

这是生成单位向量的结果，因为

仍然需要找到b和δ，这不是由对偶程序给出的。

互补松弛条件根据λ和μ的值对点进行分类。事实上，我们有。

此外，如果λi>0，则相应的约束处于活动状态，同样，如果μj>0。因为

）=0，由于μj+βj=k，我们得到i，如果ξj>0，则μj=k。

因此，如果λi<k，则正确分类；同样，如果μj<k，则ξj=0和vj正确分类。我们有以下分类：

(1) 如果0<λi<k，则ui在边缘，分类正确。同样，如果0<μj<k，则Vj在边缘，并且分类正确。

(2) 如果λi=k，那么如果点ui可以正确分类，或者它位于正确边上的空白范围内，但是如果这样，它就被错误分类了。同样，如果μj=k，则如果ξj≤δ，则点vj可正确分类，或位于正确侧的边缘内，但如果ξj>δ，则其分类错误。

(3) 如果λi=0，则ui被正确分类。同样，如果μj=0，则Vj分类正确。

方程式

意味着存在一些i0，例如λi0>0和一些j0，例如μj0>0，但是先验的，没有什么能阻止所有非零的λi的λi=k或所有非零的μj的μj=k的情况。如果发生这种情况，我们可以用更大的k值重新运行优化方法。如果下面的温和假设sis保持，然后可以找到b和δ。

（SVMS1）的标准裕度假设。有一些指数i0，如0<λi0<k，有一些指数j0，如0<μj0<k。这意味着一些ui0被正确分类，在蓝边上，一些vj0被正确分类，在红边上。

如果（svms1）的标准裕度假设成立，那么=0和祆j0=0，那么我们就有了活动方程。

w>ui0−b=δ和−w>vj0+b=δ，

我们得到b和δ的值

如前所述，定理49.16（2）的假设成立，所以如果原始问题（SVMS1）有一个w=06的最优解，那么对偶问题也有一个解，对偶间隙为零。因此，对于最优解，我们有

，

也就是说

，

所以我们得到

因此，我们确定δ≥0。

需要注意的是，双重程序的目标功能

通过矩阵x>x只涉及到ui和vj的内积，同样，最优超平面方程也可以写成

，

一种只涉及x的内部产品与ui和vj以及ui和vj的内部产品的表达式。

如本章开头所述，这是一个关键的事实，允许使用内核方法对支持向量机进行泛化。我们可以定义以下“内核化”版本的问题（SVMS1）：软边界内核SVM（SVMS1）：

最小化

通过计算，我们找到双程序的以下版本：

最小化

式中，k是×核对称矩阵（其中`=p+q），由

）1≤I≤P，1≤J≤Q

κ（vi−p，vj−q）p+1≤i≤p+q，p+1≤j≤p+q。

我们也发现

在标准裕度假设下，有一些指数i0，如0<λi0<k，有一些指数j0，如0<μj0<k，我们得出b和δ的值为

利用上述w值，我们得到

因此，分类功能

f（x）=sgn（hw，（x）i-b）

由给出

，

仅用核κ表达。

支持向量机的核心方法在sch–olkopf和smola[141]以及Shawe–Taylor和Christianini[154]中进行了讨论。

由于约束w>w≤1引起了麻烦，我们将其交换为另一个目标函数，其中−δ替换为（1）。这样我们就只剩下纯仿射约束。在下一节中，我们将讨论通过添加线性正则化项得到的问题（SVMH2）的推广。

54.2软边界支持向量机；（SVMS2）

在这一节中，我们考虑问题的推广（svmh2），其中我们最小化

（1/2）w>w通过为一些k>0添加“正则化项”。

记住，裕度δ由δ=1/kwk给出。

软利润SVM（SVMS2）：

最小化

这是所有机器学习或模式分析书籍中讨论的经典问题，例如Vapnik[176]、Bishop[23]和Shawe–Taylor和Christianini[154]。所有变量都为0的平凡解被排除在外，因为不等式中存在1，但不清楚如果（w，b，，ξ）是最优解，那么w=0.6

证明了如果原问题有一个w=06的最优解（w，，ξ，b），则w由对偶的任何最优解（λ，μ）确定。我们还证明，对于一些i，λi>0，而对于一些j，μj>0。在我们称之为标准保证金假设的温和假设下，可以找到B。

如果（w，，ξ，b）是问题的最优解（svms2），那么点ui和vj的分类如下：

(1) 如果=0，则点ui被正确分类，位于页边距或页边距的正确一侧（蓝色一侧）。同样，如果ξj=0，则点vj被正确分类，并且位于边缘或边缘的正确一侧（红色一侧）。见图54.1（1）。

(2) 如果为0 1，则点UI位于边界（板）内，但位于分离超平面的正确一侧（蓝色一侧）。如果=1，则UI位于分离超平面上。同样地，如果0<ξj≤1，则点vj位于边缘（板）内，但位于分离超平面的正确侧（红色侧）。如果ξj=1，则vj位于分离超平面上。见图54.1（2）。

1，则点ui位于分离超平面（红色侧）的错误一侧；它被错误分类。同样，如果ξj>1，则点vj位于分离超平面（蓝色面）的错误一侧；它被错误分类。见图54.1（3）。

图54.1：图（1）说明了页边距中包含的UI的情况，并在

= 0。图（2）的左图是当ui在边界内，但仍在分离超平面w>x−b=0的正确一侧时；这在0 1时发生。右图描述了分隔超平面上的UI，只要=1。图（3）说明了用户界面的错误分类，并在

0）的点称为边缘误差；它们要么位于板内，要么被错误分类。

注意，这个框架对异常值仍然有些敏感，因为对错误分类的惩罚是线性的in和ξ。

首先，我们用矩阵形式写约束。2（p+q）×n+p+q+1）矩阵c以块形式写为

，

约束条件表示为

目标函数）由

带和带的拉格朗日由下式给出

自从

我们得到

，

从那以后

，

拉格朗日可以改写为

为了找到双函数g（λ，μ，α，β），我们将其最小化

. 由于拉格朗日是凸的（，一个凸的开集），根据定理39.11，拉格朗日在（=0）中有一个最小值，所以我们计算了它的梯度，得到

通过设置=0，我们得到方程

（W）

和

λ+α=k1pμ+β=k1q

1>pλ=1>qμ。

第一个和第四个方程与我们在示例49.10中得到的方程（1）和（2）相同。由于λ、μ、α、β≥0，第二个和第三个方程等于箱约束

0≤λi，μj≤k，i=1，…，p，j=1，…，q.

利用我们刚推导的方程，经过简化，我们得到

，

不依赖于α和β，与实施例49.10（4）中获得的双函数相同。要非常严格，

−∞否则。

如例49.10所示，双方案可表述为

最大化受试者

或同等

最小化

十倍

λi=μj i=1 j=1 0≤λi≤k，i=1，…，p

0≤μj≤k，j=1，…，q.

通过使用基于梯度下降的数值程序（例如第51.6节中的ADMM）来求解双程序。如果原始问题是可解的，则会得到λ和μ的解。

注：硬边值问题（svmh2）对应于特殊情况（svms2），其中=0，k=+∞。事实上，在问题（svmh2）中，拉格朗日方程中缺少涉及的项，其结果是缺少盒约束；我们只得到λi≥0和μj≥0。

我们可以用对偶程序来求解初等问题。一旦发现λ≥0，μ≥0，w由下式得出：

互补松弛条件根据λ和μ的值对点进行分类。事实上，对于j=1，…，q，我们有且ξjβj=0。

此外，如果λi>0，则相应的约束处于活动状态，同样，如果μj>0。因为

）=0，由于μj+βj=k，我们得到i，如果ξj>0，则μj=k。

因此，如果λi<k，则正确分类；同样，如果μj<k，则ξj=0和vj正确分类。我们有以下分类：

(1) 如果0<λi<k，则ui在边缘，分类正确。同样，如果0<μj<k，则Vj在边缘，并且分类正确。

(2) 如果λi=k，那么如果1，点ui可以正确分类，或者它位于正确侧的边缘内，但是如果1，那么它被错误分类。同样，如果μj=k，则如果ξj≤1，则点vj可正确分类，或位于正确侧的边缘内，但如果ξj>1，则其分类错误。

(3) 如果λi=0，则ui被正确分类。同样，如果μj=0，则Vj分类正确。

如果原始解w=06，那么方程

意味着要么存在一些指数i0，使得λi0>0，要么存在一些指数j0，使得μj0>0。约束条件

十倍

λi=μj i=1 j=1

意味着存在一些指数i0，使得λi0>0，并且存在一些指数j0，使得μj0>0。然而，先验的，没有什么能阻止所有非零的λi的λi=k或所有非零的μj的μj=k的情况。如果发生这种情况，我们可以用更大的k值重新运行优化方法。观察方程

意味着如果存在指数I0，如0<λI0<k，则存在指数J0，如0<μj0<k，反之亦然。如果下面的温和假设成立，那么可以找到b。

（SVMS2）的标准裕度假设。有一些指数i0，如0<λi0<k，有一些指数j0，如0<μj0<k。这意味着一些ui0被正确分类，在蓝边上，一些vj0被正确分类，在红边上。

如果（svms2）的标准裕度假设成立，那么=0和礹j0=0，那么我们就得到了活动方程。

w>ui0−b=1和−w>vj0+b=1，

我们得到

备注：有一个廉价版本的问题（SVM）s2），它将术语（1/2）w>w从目标函数中删除：

软边缘分类器（SVMS2L）：

最小化

上面的程序是一个线性程序，它可以最小化错误分类的点的数量，但不关心执行最小界限。Boyd和Vandenberghe给出了其使用示例；见[29]第8.6.1节。

问题（SVMS2）的“kernelized”版本如下：

软边缘内核SVM（SVMS2）：

最小化

在重新计算对偶函数时，我们发现对偶程序是由

最小化

其中，k是第54.1节末尾给出的`核对称矩阵（其中=p+q）。我们也发现

，

所以

，

以及分类功能

f（x）=sgn（hw，（x）i-b）

由给出

54.3软边界支持向量机；（SVMS20）

在这一节中，我们考虑问题（svms2）的泛化，对于来自问题（svmh2）的软边界svm的一个版本，通过增加额外的自由度，即代替边缘δ=1/kwk，我们使用边缘δ=η/kwk，其中η是我们希望最大化的某个正常数。为此，我们在目标函数中添加一个术语−kmη。

（1/2）w>w以及“正则化项”，其目的是使和ξ稀疏，其中km>0和ks>0是固定常数，可以调整以确定η和正则化项的影响。

软利润SVM（SVMS20）：

最小化

SVM问题的这一版本首先在scho–lkopf、smola、williamson和bartlett[143]中以ν-svc（或ν-svm）的名义进行了讨论，也用于sch–olkopf、platt、shawe–taylor和smola[142]。snu-svc方法在scho–lkopf和smola[141]中也有介绍（其中包含更多）。Chan和Lin[36]对第54.2节（有时称为c-svm方法）中所述的方法（即c-svm方法）与ν-svc方法之间的差异进行了彻底的研究。

对于这个问题，不再清楚如果（w，η，b，，ξ）是一个最优解，那么w=06，η>0。事实上，如果点集不是线性可分的，并且Ks选得太大，问题（SVMS20）可能无法得到最优解。

我们表明，为了解决这个问题，我们必须选择km和ks，以便

km≤最小2pks，2qks。

如果我们用

，

则km≤min 2pks，2qks等于

引入镟的原因是，镟（p+q）/2可以解释为未能达到边缘η的最大点数。如果集合ui和vj不是线性可分离的，那么我们必须选取ν，以便使方法的ν≥2/（p+q）具有光学解。如果v<3/（p+q），并且至少有三个点被错误分类，那么我们有一些有趣的保证；见54.5号提案和54.6号提案。

我们问题的目标函数是凸的，约束是仿射的。因此，根据定理49.16（2），如果原始问题（SVMS20）有一个最优解，那么对偶问题也有一个解，对偶间隙为零。这并不立即意味着对偶的最优解会产生原始解的最优解，因为定理49.16（1）的假设不成立。

我们证明，如果原问题有一个w=06的最优解（w，η，，ξ，b），那么对偶问题的任何最优解都确定了λ和礹，进而通过方程确定了w。

，（W）

且η≥0。

还有待确定。对偶的解不能直接确定b，η，，ξ，我们不知道确保它们可以被确定的必要和充分条件。我们能做的最好的就是使用KKT条件。

最简单的充分条件是我们称之为

（SVMS20）的标准裕度假设：存在一些I0，例如0<λi0<ks，存在一些μj0，例如0<μj0<ks。这意味着一些ui0被正确地分类，并且在蓝边上，一些vj0被正确地分类，并且在红边上。

在这种情况下，通过互补松弛度，可以证明=0，并且相应的不等式是活动的，也就是我们有方程

w>ui0−b=η，−w>vj0+b=η，

所以我们可以解b和η。然后，由于通过互补松弛度，如果0，则λi=ks，如果ξj>0，则μj=ks，与该0和μj>0对应的所有不等式都是有效的，我们可以解出i和ξj。

如果2/（p+q）≤ν<3/（p+q）且至少三个点被错误分类，那么我们可以保证存在一些i0，使得约束w>ui0−b=η处于活动状态，或者存在一些j0，使得约束−w>vj0+b=η处于活动状态。

如果（w，η，，ξ，b）是w=06的问题（svms20）的最优解，那么点ui和vj分类如下：

，则点ui位于分离超平面的错误一侧（红色一侧）；它被错误分类。同样，如果ξj>η，那么点vj位于分离超平面（蓝色面）的错误一侧；它被错误分类。

0）的点称为边缘误差；它们要么位于板内，要么被错误分类。

线性约束由（2（p+q）+1）×（n+p+q+2）矩阵给出，以块形式给出

，

线性约束表示为

目标函数由

给出了，和γ∈r+的拉格朗日

通过

自从

拉格朗日可以写成

为了找到双函数g（λ，μ，α，β，γ），我们用

关于w，，ξ，b和η。由于拉格朗日是凸的，（r×r，一个凸的开集，根据定理39.11，拉格朗日在（iff=0）中有一个最小值，因此我们计算了它相对于w，，ξ，b，η的梯度，得到

通过设置=0，我们得到方程

（W）

λ+α=ks1pμ+β=ks1q

1>pλ=1>qμ，

和

（γ）

第二和第三个方程等价于箱约束

0≤λi，μj≤ks，i=1，…，p，j=1，…，q，

因为γ≥0方程（γ）等于

将w从（w）插回拉格朗日，简化后，我们得到

因此，双函数独立于α，β，并由

双程序由

最大化受试者

最后，双程序相当于以下最小化程序：

最小化

通过使用基于梯度下降的数值程序（例如第51.6节中的ADMM）来求解双程序。如果原始问题是可解的，则会得到λ和μ的解。一旦得到λ和μ的溶液，我们就得到

如前所述，定理49.16（2）的假设成立，所以如果原始问题（SVMS20）有一个w=06的最优解，那么对偶问题也有一个解，对偶间隙为零。因此，对于最优解，我们有

，

也就是说

，

从那以后

我们得到

，

会产生

.（）

因此，η≥0。

评论：

(1) 问题的目标函数（SVMS20）是问题的目标函数（SVMS1）的一半，但有些约束是不同的。然而，问题（SVMS20）的主要优点是W总是被确定的。

(2) 因为我们证明了如果原始问题（SVMS20）有一个W=06的最优解，那么η≥0，人们可能会奇怪为什么约束η≥0被包括在内。如果我们删除这个约束，很容易看出唯一的区别是，它不是方程

我们得到了方程

因为方程式

在第一种情况下，我们获得

（1）

在第二种情况下，我们得到

.（2）

如果η>0，则通过互补松弛度γ=0，在这种情况下（1）和（2）是等效的。但如果η=0，则γ可以严格为正。

不清楚将约束η≥0包含在初始值中的选择是否有利，除非在对偶程序中，方程和不等式可能是有利的。

1>pλ=1>qμ1>pλ+1>qμ≥km

包括而不是方程式

也许使用不平等可以更容易地解决二元问题。为了解决这个问题，我们似乎需要对一些测试数据运行实际的解决方案。

回到问题（SVMS20），互补松弛条件根据λ和μ的值对点进行分类。事实上，我们有

当j=1，…，q时，ξjβj=0。同样，如果λi>0，那么相应的约束是激活的，同样，如果μj>0。既然=0，既然μj+βj=ks，我们有j j i i s，如果ξj>0，那么μj=ks。因此，如果i s=0和ui被正确分类，同样，如果μj<ks，则ξj=0和vj被正确分类。除了约束之外

0≤λi≤ks，0≤μj≤ks，

我们也有限制

这意味着

和。（？）

因为λ，μ都是非负的，如果所有i的λi=ks，如果所有j的μj=ks，那么

和

，

因此，除非km≤min 2pks，2qks，这些约束条件是不满足的，因此我们假设km≤min 2pks，2qks。（†）中的方程也意味着存在一些i0，例如λi0>0，一些j0，例如μj0>0。

我们有以下分类（记住，η>0）：

(1) 如果0<λi<ks，则ui在边缘，分类正确。同样，如果0<μj<ks，则Vj在边缘，并且分类正确。

(2) 如果λi=ks，那么我们不看=0就不能说更多，那么点ui在边界上，并且分类正确；如果0，那么ui在正确的边上的边界内，但是如果它被错误分类。同样，如果μj=ks，那么我们不看ξj就不能说更多。如果ξj=0，那么点vj在边缘上，分类正确，如果0<ξj≤η，那么vj在正确的边上的边缘内，但是如果ξj>η，那么它被错误分类。

(3) 如果λi=0，则ui被正确分类。同样，如果μj=0，则Vj分类正确。无法判断UI是否在页边空白处，同样对于VJ也是如此。

我们发现定义v>0很方便，这样

km=（p+q）ksν，

那就是

，

因此，目标函数）由

，

k=（p+q）ks，所以km=kν，ks=k/（p+q）。

观察条件km≤min 2pks，2qks等于

，

条件ks≤km/2等于

由于我们通过用一个公共的正因子重新标定来获得一个等价的问题，因此可以方便地将ks归一化为

，

在这种情况下，km=ν。这种方法被称为nv-支持向量机。

在（svms20）的标准裕度假设下，存在一些i0，例如0<λi0<ks，一些j0，例如0<μj0<ks，并且由互补松弛条件=0和ξj0=0，因此我们有两个主动约束。

w>ui0−b=η，−w>vj0+b=η，

我们可以解b和η，得到

方程（†）和盒子不等式

0≤λi≤ks，0≤μj≤ks

也意味着以下事实：

提案54.1.如果问题（SVMS20）的最优解w=06且η>0，则以下事实成立：

(1) 至多为ν（p+q）/2点ui未达到边缘η，至多为ν（p+q）/2点vj未达到边缘η。

(2) 其中，至少ν（p+q）/2点ui的裕度最大为η，至少ν（q+q）/2点的裕度最大为η。

证据。（1）回想一下，对于w=06且η>0的最优解，我们得到γ=0，因此通过（γ），我们得到了方程。

而且。

如果ui未能达到边缘η，则为0，并通过补充松弛度λi=ks=km/（ν（p+q）），因此，如果存在此类点，则

，

所以

如果VJ未能达到裕度η，用pqj=1μj代替（其中qf是未能达到裕度η的VJ点数），则采用类似的推理。

（2）点ui的最大裕度为ηiffλi>0。如果

im=i∈1，…，pλi>0和pm=im，

然后

，

由于λi≤ks=km/（ν（p+q）），我们得到

，

会产生

如果一个点vj的最大裕度为η，则采用类似的推理。

请注意，如果选择了ν，使之ν<2/（p+q），那么ν（p+q）/2<1，这意味着没有一个数据点被错误分类；换句话说，uis和vjs是线性可分的。因此，我们再次看到，如果uis和vjs不是线性可分离的，我们必须选择v，使2/（p+q）≤v≤min 2p/（p+q），2q/（p+q）方法成功。

下面的命题阐明了常数v在建立保证金宽度和保证金误差点数量之间的权衡中的作用。特别地，它表明如果问题（SVMS20）有一个w=06的最优解，并且如果v<min 2p/（p+q），2q/（p+q），那么至少一些UI或一些VJ被正确分类。显然我们有2/（p+q）≤min 2p/（p+q），2q/（p+q）。

提案54.2.假设是问题（SVMS20）的一个最优解，其中w=06且η>0，设pf为误分类的点Ui个数（qf为误分类的点Vj个数（ξj>0）。如果pf+qf≥3且如果2/（p+q）≤ν<（pf+qf）/（p+q），那么要么存在一些i，使得约束w>ui−b=η处于活动状态，要么存在一些j，使得ξj=0且约束−w>vj+b=η处于活动状态。

证据。（1）我们可以假设ks=1/（p+q）。我们自相矛盾。因此，我们假设，对于all=0，那么约束w>ui−b≥η是不活动的，即w>ui−b>η，对于所有j∈1，…，q，如果ξj=0，那么约束−w>vj+b≥η是不活动的，即−w>vj+b>η。

设，并设pf=i和qf=j（当然，η>0）。

假设pf+qf≥3。由于互补松弛性，所有约束i∈i和j∈j都是主动的，因此我们的假设是

对于任何θ>0，这样

，

我们可以写信

目标函数的初始值是

，

新的价值是

因为根据假设pf+qf≥3，如果

，

那么涉及θ的项是负的，所以

ω（θ）<ω（0），

通过选择θ，我们得到了一个可行的解，与解的最优性（对于向量）相矛盾。

，与ξ−θ类似。

请注意，如果pf+qf=p+q且ν<min 2p/（p+q），2q/（p+q）≤1，则命题54.5产生矛盾。因此，pf+qf<p+q，即至少一些ui或一些vj是

分类正确

注：如果集合ui和vj是线性可分的，那么从定理49.12我们可以知道，一些ui在蓝边上，一些vj在红边上。

我们也有下面的命题，它给出了一个充分的条件，暗示η和b可以从对偶的最优解（λ，μ）中找到。

提案54.3.是w=06且η>0的问题（SVMS20）的最优解，如果2/（p+q）≤ν<4/（p+q）和pf，qf≥2，则始终可以从对偶的最优解（λ，μ）中确定η和b。

证据。由于pf+qf≥4，根据命题54.5，要么有一些i0，例如=0，约束w>ui0−b=η处于活动状态，要么有一些j0，例如ξj0=0，约束−w>vj0+b=η处于活动状态，正如我们已经解释的那样，问题（svms20）满足具有零dua的条件。间隙。因此，对于最优解，我们有

，

也就是说

，

从那以后

，

我们得到

.（）

设j=j∈1，…，qξj>0。假设i≥2和j≥2。我们知道，所有i∈i的λi=1/（p+q），所有j∈j的λj=1/（p+q），因此以下方程是有效的：

i∈i j∈j。

但是（）可以写为

，（）

从那以后

通过代入方程（），我们得到

我们还知道w>ui0−b=η或−w>vj0+b=η。在第一种情况下，b=−η+w>ui0，通过在上述方程中代入b，我们得到一个形式的方程。

，

也就是说，

在第二种情况下b=η+w>vj0，我们得到一个形式的方程

，

也就是说，

我们需要选择，使2 i/（p+q）−ν=06和2 j/（p+q）−ν=06。由于i≥2和j≥2，因此，如果v<4/（p+q），则会出现这种情况。如果满足这个条件，我们可以求出η，然后我们从b=−η+w>ui0或b=η+w>vj0中找到b。

注：如果集合ui和vj是线性可分的，那么从定理49.12我们可以知道，一些ui在蓝边上，一些vj在红边上，因此可以确定b和δ。虽然我们可以确保某些UI被正确分类或某些VJ被正确分类，但似乎不可能证明相应的约束在没有附加假设（如pf+qf≥3）的情况下是活动的。

支持向量机的优点之一是有助于在vc维（vapnik和chernovenkis发明的概念）方面找到有趣的统计界限。我们不会在这里讨论这个问题，而是将读者引向Vapnik[176]（尤其是第4章和第9-13章）。

问题（SVMS20）的“kernelized”版本如下：

软边缘内核SVM（SVMS20）：

最小化

通过对双程序的推导，我们得到

最小化

其中k是第54.1节的核矩阵。

如第54.2节所述，我们获得

，

所以

，

以及分类功能

f（x）=sgn（hw，（x）i-b）

由给出

54.4软保证金SVM；（SVMS3）

在这一部分中，我们考虑问题（SVMS20）的版本，在该版本中，我们不使用函数作为正则化函数，而是使用二次函数

软利润SVM（SVMS3）：

最小化

式中，ν和k是两个给定的正常数。如前所述，选择k=1/（p+q）比较方便。

这个问题公式的新扭曲是，如果为0，则相应的不等式意味着通过将i设置为零而减少的值得到的不等式w>ui−b≥η，同样，如果ξj<0，则相应的不等式−w>vj+b≥η−ξj意味着in等式−w>vj+b≥η，通过将ξj设置为零，同时减小kξk2的值得到。因此，如果（w，b，，ξ）是问题（svms3）的最优解，则无需将松弛变量限制为非负变量，这就简化了一些问题。

这种方法的一个优点是由λ确定，ξ由μ确定。我们也可以省略约束η≥0，因为对于最优解，可以用对偶性表示η≥0。

拉格朗日由

为了找到关于w、ξ、b和η的双函数g（λ、μ、γ），我们将其最小化。因为拉格朗日是凸的（

开集，根据定理39.11，拉格朗日在（=0，

54.4。软保证金SVM；（SVMS3）

所以我们计算。梯度由下式给出

通过设置=0，我们得到方程

（W）

和

最后两个方程与问题（SVMS20）中得到的最后两个方程相同。我们可以用其他方程得到双函数g（λ，μ，γ）的下列表达式。

因此，双程序相当于最小化程序。

最小化

上述程序与为问题（SVMS20）而得到的程序相似，但矩阵x>x被矩阵x>x+（1/2k）ip+q所代替，该矩阵自k>0起为正定，且不再存在λi≤k和μj≤k的不等式。然而，这些限制意味着存在一些i0，例如λi0>0，而一些j0，例如μj0>0。

通过使用基于梯度下降的数值程序（例如第51.6节中的ADMM）来求解双程序。如果原始问题是可解的，则会得到λ和μ的解。我们从问题（SVMS20）中的λ和μ以及γ中获得w；即，

p q w=xλiui−xμjvj。

I=1 J=1

由于变量i和μj不被限制为非负，我们不再有涉及它们的互补松弛条件，但我们知道

也因为约束

和

意味着存在一些i0，例如λi0>0和一些j0，例如，μj0>0，我们有且ξj0>0，这意味着至少两个点被错误分类，因此问题（svms3）只应在集ui和vj不可线性分离时使用。我们可以使用与任何i0对应的主动约束来解b和η，从而使λi0>0和任何j0，从而使μj0>0，我们得到

我们也可以利用最优性间隙为0的事实求出η。我们有

，

从那以后

我们得到

上述结果证实，在最优性条件下，我们得到η≥0。

问题（SVMS3）的“kernelized”版本如下：

软边缘内核SVM（SVMS3）：

最小化

通过对对偶程序的推导，我们得到

最小化

其中k是第54.1节的核矩阵。然后，w、b和f（x）的计算与第54.3节中的计算完全相同。

54.5软边界支持向量机；（SVMS4）

在本节中，我们通过在目标函数中添加术语（1/2）b2来考虑问题（SVMS20）的变化。结果表明，在将拉格朗日最小化的情况下，不仅可以求出双函数G，而且还可以求出B。我们还抑制了约束η≥0，这是多余的。

软利润SVM（SVMS4）：

最小化

为了简化演示，我们假设k=1，并将k写为1/（p+q）。

拉格朗日）的

为了找到关于的双函数g（λ，μ，α，β），我们将其最小化。由于拉格朗日是凸的（，一个凸的开集），根据定理39.11，拉格朗日在（w，，ξ，b，η）iff=0中有一个最小值，因此我们计算了它相对于w，，ξ，b，η的梯度，得到

通过设置=0，我们得到方程

（W）

和

.（b）

第二和第三个方程等价于箱约束

0≤λi，μj≤ks，i=1，…，p，j=1，…，q.

因为我们假设原始问题有一个w=06的最优解，我们有

把w从（w）和b从（b）插回拉格朗日，我们得到

因此，双函数独立于α，β，并由

双程序由

最大化受试者

十倍

λi+μj=νi=1 j=1 0≤λi≤ks，i=1，…，p

0≤μj≤ks，j=1，…，q.

最后，双程序相当于以下最小化程序：

最小化

如前所述，定理49.16（2）的假设成立，所以如果原始问题（SVMS4）有一个w=06的最优解，那么对偶问题也有一个解，对偶间隙为零。因此，对于最优解，我们有

，

也就是说

从那以后

，

我们得到

自从

是正半定的，因此我们确定η≥0。

因为ks=1/（p+q），为了满足约束条件

并且0≤λi，μj≤1/（p+q）要满足要求，我们必须

ν≤1.

方程式

十倍

λi+μj=νi=1 j=1

也意味着要么存在一些i0，使得λi0>0，要么存在一些j0，使得μj0>0。

在（svms4）的标准裕度假设下，要么存在一些i0，例如0<λi0<ks，要么存在一些j0，例如0<μj0<ks，并且通过互补松弛条件=0，因此我们得出

w>ui0−b=η，或−w>vj0+b=η，

我们可以求出η。

方程（†）和盒子不等式

0≤λi≤ks，0≤μj≤ks

也意味着以下事实：

提案54.4.如果问题（SVMS4）的最优解w=06且η>0，则以下事实成立：

(1) 在最大的ν（p+q）点，ui和vj未能达到边缘η。

(2) Ui和Vj上至少有ν（p+q）点的边缘至多为η。

证据。（1）回想一下，对于w=06且η>0的最优解，我们得到了方程

如果ui未能达到裕度η，则为0，并通过补充松弛度λi=ks=1/（p+q）。同样，如果VJ未能达到边缘，则ξj>0，并通过补充松弛度μj=ks=1/（p+q）。假设pf点ui不符合边际，qf点vj不符合边际。然后

，

所以pf+qf≤ν（p+q）。

（2）一点ui的裕度最大为ηiffλi>0，一点vj的裕度最大为ηiffμj>0。如果

im=i∈1，…，pλi>0和pm=im|

和

jm=j∈1，…，qμj>0和qm=jm|

然后

，

由于λi，μj≤ks=1/（p+q），我们得到

，

得出pm+qm≥ν（p+q）。

请注意，如果选择了ν，则使之等于ν<1/（p+q），则表示没有一个数据点被错误分类；换句话说，uis和vjs是线性可分离的。因此，我们发现，如果uis和vjs不是线性可分离的，我们必须选择v，这样1/（p+q）≤v≤1，方法才能成功。

下面的命题阐明了常数v在建立保证金宽度和保证金误差点数量之间的权衡中的作用。特别地，它表明，如果问题（SVMS4）有一个w=06且η>0的最优解，并且如果ν<1，那么至少一些ui或一些vj被正确分类。显然我们有1/（p+q）≤1。

提案54.5。假设是问题（SVMS4）的最优解，其中w=06，η>0，设pf为误分类的点Ui个数（qf为误分类的点Vj个数（ξj>0）。如果pf+qf≥2且如果1/（p+q）≤ν<（pf+qf）/（p+q），那么要么存在一些i，使得约束w>ui−b=η处于活动状态，要么存在一些j，使得ξj=0且约束−w>vj+b=η处于活动状态。

设，并设pf=i和qf=j（当然，η>0）。

假设pf+qf≥2。由于互补松弛性，所有约束i∈i和j∈j都是主动的，因此我们的假设是

对于任何θ>0，这样

，

我们可以写信

目标函数的初始值是

，

新的价值是

因为根据假设pf+qf≥2，如果

，

那么涉及θ的项是负的，所以

ω（θ）<ω（0），

通过选择θ，我们得到了一个可行的解，与解的最优性（对于向量）相矛盾。

，与ξ−θ类似。

请注意，如果pf+qf=p+q且ν<1，则54.5命题产生矛盾。因此，pf+qf<p+q，即至少某些ui或某些vj被正确分类。

注：如果集合ui和vj是线性可分的，那么从定理49.12我们可以知道，一些ui在蓝边上，一些vj在红边上。

我们也有下面的命题，它给出了一个充分的条件，即η可以从对偶的最优解（λ，μ）中找到。

提案54.6.如果是w=06且η>0的问题（SVMS4）的最优解，如果1/（p+q）≤ν<2/（p+q）且pf+qf≥2，则始终可以从对偶的最优解（λ，μ）中确定η。

证据。正如我们已经解释过的，问题（SVMS4）满足具有零对偶间隙的条件。因此，对于最优解，我们有

，

也就是说

那么，让我们

假设i+j≥2。那么我们知道，所有i∈i的λi=1/（p+q），所有j∈j的λj=1/（p+q），因此以下方程是有效的：

i∈i j∈j。

但是（）可以写为

从那以后

通过代入方程（），我们得到

我们可以解出我们需要选择+j≥2，这将是这样的情况，如果_使（i 1+/（pj+）/q（）p≤+ν<q）−2/（_p=06+q）。如果这个条件满足，我们假设η。

注：49.12如果setsui在蓝边上，有些ui和vj是线性可分的，那么我们从定理mvj知道它在红边上，所以b和δ可以确定。虽然我们可以确保某些UI被正确分类或某些VJ被正确分类，但似乎不可能证明相应的约束在没有附加假设的情况下是活动的（例如pf+qf≥2）。

问题（SVMS4）的“kernelized”版本如下：

软边缘内核SVM（SVMS4）：

最小化

54.6。软保证金SVM；（SVMS5）

通过对双程序的推导，我们得到

最小化

十倍

λi+μj=νi=1 j=1

0≤λi≤ks，i=1，…，p

0≤μj≤ks，j=1，…，q，

其中k是第54.1节的核矩阵。

我们得到

分类功能

f（x）=sgn（hw，（x）i-b）

由给出

54.6软保证金SVM；（SVMS5）

在本节中，我们考虑问题（SVMS3）的版本，在该版本中，我们将术语（1/2）b2添加到目标函数中。我们还降低了约束η≥0，这是多余的。

软利润SVM（SVMS5）：

最小化

式中，ν和k是两个给定的正常数。如前所述，选择k=1/（p+q）比较方便。

拉格朗日由

为了找到关于和η的双函数g（λ，μ），我们将其最小化。由于拉格朗日是凸的（，一个凸的开集，根据定理39.11，拉格朗日在（=0）中有一个最小值，所以我们计算。梯度由下式给出

通过设置=0，我们得到方程

（W）

和

最后两个方程与问题（SVMS4）中得到的最后两个方程相同。我们可以用其他方程得到双函数g（λ，μ，γ）的下列表达式。

54.6。软保证金SVM；（SVMS5）

因此，双程序相当于最小化程序

通过使用基于梯度下降的数值程序（例如第51.6节中的ADMM）来求解双程序。如果原始问题是可解的，则会得到λ和μ的解。

约束意味着要么存在一些i0，使得λi0>0，要么存在一些j0，使得μj0>0。我们从λ和μ中得到w和b，如问题（svms4）；即，

由于变量i和μj不被限制为非负，我们不再有涉及它们的互补松弛条件，但我们知道

也因为约束

十倍

λi+μj=νi=1 j=1

意味着要么存在一些i0，比如λi0>0，要么存在一些j0，比如μj0>0，我们有0，这意味着至少有一个点被错误分类，所以只有当集合ui和vj不可线性分离时，才应使用问题（svms5）。我们可以使用与任何i0对应的主动约束来求解η，这样λi0>0或任何j0，这样μj0>0。

我们也可以利用最优性间隙为0的事实求出η。我们有

，所以我们得到

上述结果证实，在最优性条件下，我们得到η≥0。

问题（SVMS5）的“kernelized”版本如下：

软边缘内核SVM（SVMS5）：

最小化

通过对双程序的推导，我们得到

最小化

其中k是第54.1节的核矩阵。然后，w、b和f（x）的计算与第54.5节中的计算完全相同。

54.7支持向量机方法总结与比较

在本章中，我们考虑了六个变量来解决两组点的软边界二值分类问题，并使用支持向量分类方法。目的是找到方程w>x-b=0的分离超平面hw，b。我们还试图找到两个“边缘超平面”hw，方程w>x−b−δ=0和hw，方程w>x−b+δ=0的b−δ，这样δ尽可能大，但错误分类点的数量是最小化的，这是通过允许每个点ui的误差0来实现的，在这个意义上，tHE约束

在约束条件下，每个点vj的误差ξj≥0

−w>vj+b≥δ−ξj

应该保持。

目的是设计一个目标函数，使δ最小化和ξ最大化。对于W和B，优化问题也应该解决，因此必须在W上施加一些约束。另一个目标是尝试使用双程序来解决优化问题，因为解决方案涉及内部产品，因此该问题可以用kern进行泛化。EL功能。

第一次尝试，即使用目标函数

而约束w>w≤1并不能很好地发挥作用，因为这个约束需要用拉格朗日乘子γ≥0来保护，因此，将拉格朗日L最小化以找到对偶函数g，给出了求解形式w的方程。

，

但如果集合不可线性分离，则γ=0可能出现最优解，在这种情况下，无法确定w。这是第54.1节中考虑的问题（SVMS1）。

软利润SVM（SVMS1）：

最小化

习惯上写`=p+q。

如第54.1节所示，双程序相当于以下最小化程序：

最小化

注意，约束意味着必须选择k，以便

如果最佳值为0，则γ=0和=0，因此在这种情况下不可能确定w。但是，如果最佳值大于0，则一旦获得λ和μ的解，我们就可以

所以我们得到

，

如果下面的温和假设成立，则可以找到b和δ。

（SVMS1）的标准裕度假设。有一些指数i0，如0<λi0<k，有一些指数j0，如0<μj0<k。这意味着一些ui0被正确分类，在蓝边上，一些vj0被正确分类，在红边上。

如果（svms1）的标准裕度假设成立，那么=0和祆j0=0，那么我们就有了活动方程。

w>ui0−b=δ和−w>vj0+b=δ，

我们得到b和δ的值

第二个更成功的方法是将术语（1/2）w>w添加到目标函数中，并删除约束w>w≤1。然后，根据涉及（线性或二次）的正则化项的选择、边界是如何用delt（隐式地用项1或显式地用项η）进行delt的、以及项（1/2）b2是否添加到目标函数中，该方法有几个变体。

这些方法都具有这样的性质：如果原问题有一个w=06的最优解，那么对偶问题总是确定w，然后在我们称之为标准裕度假设的温和条件下，可以确定b和η。然后可以使用活动的约束来确定。当（1/2）b2添加到目标函数中时，b由方程式确定

所有这些问题都是凸的，且约束是合格的，所以对偶间隙为零，如果初等有一个w=06的最优解，则得出η≥0。

我们现在更详细地考虑五种变体。

（1）基本软利润支持向量机：（支持向量机2）。

这是一个优化问题，其中正则化项是线性的，裕度δ由δ=1/kwk给出：

最小化

这个问题是所有机器学习或模式分析书籍中讨论的经典问题，例如Vapnik[176]、Bishop[23]和Shawe–Taylor和Christianini[154]。如第54.2节所示，双程序

最小化

我们可以用对偶程序来求解初等问题。一旦发现λ≥0，μ≥0，w由下式得出：

，

但是b不是由二元决定的。

互补松弛条件意味着，如果0，则λi=k，如果ξj>0，则μj=k。因此，如果λi<k，则=0和ui被正确分类，同样，如果μj<k，则ξj=0和vj被正确分类。

先验没有什么能阻止所有非零λi的λi=k或所有非零μj的μj=k的情况。如果发生这种情况，我们可以用更大的k值重新运行优化方法。如果下面的温和假设成立，则可以找到b。

（SVMS2）的标准裕度假设。有一些指数i0，如0<λi0<k，有一些指数j0，如0<μj0<k。这意味着一些ui0被正确分类，在蓝边上，一些vj0被正确分类，在红边上。

如果（svms2）的标准裕度假设成立，那么=0和礹j0=0，那么我们就得到了活动方程。

w>ui0−b=1和−w>vj0+b=1，

我们得到

（2）基本软边挓-SVM问题（SVMS20）。

这个问题的推广（svms2）对于来自问题（svmh2）的软边界svm的一个版本，通过增加额外的自由度得到，也就是说，我们使用边界δ=η/kwk，其中，η是我们希望最大化的一些正常数。为此，我们在目标函数中添加一个术语−kmη。我们有以下优化问题：

最小化

其中，km>0和ks>0是固定常数，可调整以确定η和正则化项的影响。

SVM问题的这一版本首先在scho–lkopf、smola、williamson和bartlett[143]中以ν-svc的名义进行了讨论，也用于sch–olkopf、platt、shawe–taylor和smola[142]。

为了解决这个问题，我们必须选择km和ks，以便

km≤最小2pks，2qks。

如第54.3节所示，双程序

最小化

如果原问题有一个w=06的最优解，那么利用对偶间隙为零的事实，我们可以证明η≥0。因此，可以省略约束η≥0。

与前一种情况一样，w由

，

但b和η不是由对偶决定的。

如果我们降低约束η≥0，那么不等式

替换为公式

十倍

λi+μj=公里。I=1 J=1

方便地定义v>0，以便

km=（p+q）ksν，

那就是

，

因此，目标函数）由

，

k=（p+q）ks，所以km=kν，ks=k/（p+q）。

观察条件km≤min 2pks，2qks等于

由于我们通过用一个公共的正因子重新标定来获得一个等价的问题，因此可以方便地将ks归一化为

，

在这种情况下，km=ν。这种方法被称为nv-支持向量机。

在（svms20）的标准裕度假设下，存在一些i0，例如0<λi0<ks，一些j0，例如0<μj0<ks，并且由互补松弛条件=0和ξj0=0，因此我们有两个主动约束。

w>ui0−b=η，−w>vj0+b=η，

我们可以解b和η，得到

η=w>ui0−w>vj0。二

命题54.1给出了积分Ui的个数和未能达到边缘且最大有边缘的积分Vj的个数的上界。因此，如果uis和vjs不是线性可分离的，我们必须选择v，使2/（p+q）≤v≤min 2p/（p+q），2q/（p+q）方法成功。

我们还研究了确保某个点ui被正确分类或某个点vi被正确分类的条件，并且相应的约束是活动的（因此ui在边缘，resp）。VJ在边缘）。如果存在pf误分类点ui和qf误分类点vj，那么如果pf+qf≥3和2/（p+q）<（pf+qf）/（p+q），则上述属性保持不变；见54.2号提案。我们还表明，如果pf，qf≥2，如果2/（p+q）<4/（p+q），那么b和η可以在不参考标准裕度假设的情况下找到；见命题54.3。

（3）基本二次型软边-SVM问题（SVMS3）。这是问题（SVMS20）的版本，其中我们使用二次函数代替线性函数作为正则函数。优化问题是

最小化

式中，ν和k是两个给定的正常数。如前所述，选择k=1/（p+q）比较方便。

在这种方法中，不再需要0，因为最优解满足这些条件。我们也可以省略约束η≥0，因为对于最优解，可以用对偶性表示η≥0。如第54.4节所示，对偶函数由下式给出：

最小化

上述程序与为问题（SVMS20）而得到的程序相似，但矩阵x>x被矩阵x>x+（1/2k）ip+q所代替，该矩阵自k>0起为正定，且不再存在λi≤k和μj≤k的不等式。然而，这些限制意味着存在一些i0，例如λi0>0，而一些j0，例如μj0>0。如果约束η≥0下降，则不等式

替换为公式

我们从问题（SVMS20）中的λ和μ以及γ中获得w；即，

，

但对偶不确定b和η。然而，决定于

也因为约束

和

意味着存在一些i0，使得λi0>0，而一些j0，使得μj0>0，我们有

0和ξj0>0，这意味着至少两个点被错误分类，因此问题（SVMS3）只能在集合ui和vj不可线性分离时使用。我们可以使用与任何i0对应的主动约束来求解b和η，从而使λi0>0和任何j0，从而使μj0>0。这种方法不需要标准边际假设。

（4）软边ν-SVM问题（SVMS4）。这是通过在目标函数中添加术语（1/2）b2而得到的问题（SVMS20）的变化。结果表明，在将拉格朗日最小化的情况下，不仅可以求出双函数G，而且还可以求出B。我们还抑制了约束η≥0，这是多余的。优化问题是

最小化

Ks=1/（P+Q）。

在第54.5节中显示，双变量由下式给出：

最小化

一旦得到λ和μ的溶液，我们就得到

但η不是由对偶决定的。注意约束

出现在程序对偶（SVMS20）中的已被交易为方程

确定b。这似乎是问题的优势（svms4）。

结果还表明，如果原始问题（SVMS4）有一个W=06的最优解，则η≥0。为了让原始人有一个解决方案，我们必须

ν≤1.

在（svms4）的标准裕度假设下，要么存在一些i0，例如0<λi0<ks，要么存在一些j0，例如0<μj0<ks，并且通过互补松弛条件=0，因此我们得出

w>ui0−b=η，或−w>vj0+b=η，

我们可以求出η。

命题54.4给出了积分Ui的个数和未能达到边缘且最大有边缘的积分Vj的个数的上界。因此，如果uis和vjs不是线性可分离的，我们必须选择v，这样1/（p+q）≤v≤1，方法才能成功。

我们还研究了确保某个点ui被正确分类或某个点vi被正确分类的条件，并且相应的约束是活动的（因此ui在边缘，resp）。VJ在边缘）。如果存在pf错误分类点ui和qf错误分类点vj，则如果pf+qf≥2和1/（p+q）<（pf+qf）/（p+q），则上述属性保持不变。见54.5号提案；这比54.2号提案稍有改进。我们还表明，如果pf+qf≥2，并且如果1/（p+q）<3/（p+q），则无需标准裕度假设即可得出η；见命题54.6。这也比提议稍有改进

54.3。

（5）二次侧软边Ⅴ-SVM问题（SVMS5）。这是问题（SVMS3）的变体，其中我们将术语（1/2）b2添加到目标函数中。我们还降低了约束η≥0，这是多余的。我们有以下优化问题：

最小化

式中，ν和k是两个给定的正常数。如前所述，选择k=1/（p+q）比较方便。

在第54.6节中，程序对偶（SVMS5）由以下公式给出：

最小化

这一次，我们从λ和礹中得到和ξ：

约束条件

十倍

λi=μj i=1 j=1

程序对偶（svms3）中出现的问题已被转换为方程。

确定B。这似乎是问题的优势（SVMS5）。约束条件

十倍

λi+μj=νi=1 j=1

意味着要么存在一些i0，比如λi0>0，要么存在一些j0，比如μj0>0，我们有0，这意味着至少有一个点被错误分类，所以只有当集合ui和vj不可线性分离时，才应使用问题（svms5）。我们可以使用与任何i0对应的主动约束来求解η，这样λi0>0或任何j0，这样μj0>0。利用对偶性可以证明，如果初等有一个w=06的最优解，则η≥0。

这些方法都有一个内核化的版本。

总之，从理论上看，问题（SVMS4）和（SVMS5）似乎比其他问题具有更多的优势，因为它们至少确定了w和b，但这有待于实验验证。