支持向量机毕业外文翻译

支持向量机1.1引言第8章的结果表明：对于已定和欠定的系统，内核岭回归量(KRR)提供了一个统一的处理。另外一种方式实现统一这些两种线性系统的方法是被Vapnik提出的通过支持向量机(SVM)学习模式。支持向量机学习的关键组成部分是确认一组具有代表性的被认为最有助于形成(线性或非线性)决策边界的训练向量。这些训练向量被称为“支持向量”，其余的训练向量被称为非支持向量。要注意的是只有支持向量才可以直接参与进支持向量机的决策边界特性化。支持向量机已成功地应用于一个非常广泛的应用范围域，包括信号处理和分类，图像检索，多媒体，故障检测，通信，计算机视觉，安全/认证，时间序列预测，生物医学预测，生物信息学。本章将讨论以下课题：1.2节推导线性支持向量机（SVM）的二元分类。主要目标是再次创建一个最大的极限来区分对立的两类——正如以前在欠定系统中使用的公式一样。支持向量机学习的关键组成部分是确认一组具有代表性的被认为最有助于形成(线性或非线性)决策边界的训练向量。这些训练向量被称为“支持向量”，并且，对于支持向量机来说，只有支持向量需要处于正确的边际超平面。1.3节将基本的支持向量机算法推广到模糊分离的数据集分类。1.4节将线性支持向量机推广到它的非线性变量。通过强加额外的约束给拉格朗日乘子，被惩罚因子参数化，从相同的优化公式中得到稳健的非线性支持向量机。在1.5节中，给出了一些关于多类支持向量机的应用研究。对训练和预测精度进行了比较。此外，探究了预测精度和训练数据集的大小之间的关系。1.6节探讨通过削减支持向量来减少实验间隙维数的可能性。提议通过支持向量机削减算法的目的是最终只保留一小部分的训练向量，还产生高性能的决策规则。这可能进一步降低分类的复杂性。1.2线性支持向量机给一个二元分类训练数据集，一个基本的SVM学习模式是找到两平行的边际超平面分离的正面和负面的训练矢量。理想的情况是，两平行超平面应区分两类，正向量落在第一平面的一侧，而负向量落在第二平面的另一边。在图1.1中，以两条虚线表示边际超平面，而实线用来强调线性分类器的决策边界，两个平面之间的地区则是安全带。由区域创建的安全边际可以被一个边际超平面（两条虚线中的一条）和决策边界（实线）之间的距离D测量出来。可完美线性分离的支持向量机回忆一下，前面介绍的线性学习模式的目的是找到一个决策向量W以产生一个没有误差的可以满足被公式（8.37）严格规定的等式的解决方案。在这方面，支持向量机公式有着不一样的目的：将严格的等式转化为不等式。对于所有的积极训练向量：（1.1）图1.1 SVM中相应边际超平面的图解。虚线表示边际超平面，而实线用来表示决策超平面。同时：对于所有的积极训练向量：（1.2）这两个不等式可以通过一个简单的限制从而更简洁的表达： 在松弛条件下，支持向量机提供了一个可以适用于已定（M≥N）和欠定（N＞M）场景的统一的学习模式。1.2.1原始向量空间中的优化公式就像在以前的学习模式中，误差项可对应一个训练向量，叫做，表示为：，被公式（1.3）限制后，变为：，培训的目标是通过最小化w来最大限度地分离边缘约束下2/w。这将导致以下优化公式：受约束后：（1.4）由于SVM方法采用比LSE较少限制的约束，其解决方案熊w值低于规定的LSE学习模型实现参照公式（8.32）。注意,小w的值更广泛的分离的安全裕度。1.2.2经验空间中的沃尔夫对偶优化等式（1.4）表示的式子是一个通过使用标准的凸优化方法可解的二次规划优化问题。更具体地说，可以从中推导出拉格朗日的相关结论。（1.5）拉格朗日乘子必须是非负的，即：（1.6）以确保通过聚焦的一阶梯度对w,我们可以建立太阳能发电:（1.7）对于SVM，这已对LSP验证的标准方法。这应该是显而易见的，在公式的优化配方，由定理1.1符合规定的条件，从而提供一个独立的LSP的验证。此外，通过相对于B的归零阶指令，我们得到如下的正交平面性（OHP）条件：（1.8）将式（1.7）和式（1.8）带入式（1.5），并化简，得：（1.9）沃尔夫对偶优化让我们来表示，fori=1,...,N，然后，支持向量机的目标函数可以改写如下：其中，K是内核矩阵，并且是经验空间里的决策向量。注意,约束控制方程（1.8）可以被一个新的形成条件取代,即：这导致了下面的沃尔夫双优化公式的实证决策向量：服从OPM的条件后：受符号约束后：（1.9）注意，由于式（1.6）符号的约束，是必要的。然而，如果我们暂时忽略符号上的约束，那么我们只需要考虑控制约束。对于控制约束，采用拉格朗日乘子B，我们将获得一个新的拉格朗日公式。以F（a，b）一阶梯度相对于和B和均衡到零，我们得到：这说明了一个事实，如果它忽略符号限制，分析解决方案将是可行的。让我们用一个算例表明如果只有符号约束可以忽略这个问题可以大大简化。示例1.1(SVM分类器的三个三维(2D)训练向量)如图1.2（a）所示，为三个训练向量根据式（1.9），目标函数是：（1.11）受和，对于等式限制，拉格朗日乘子B,可以导致了一种新的拉格朗日函数： 以就和B和均衡他们零阶梯度，我们得到：图1.2 一个简单的支持向量机分类：（a）数据集。(b)支持向量机分类的决策边界。在这种情况下，所有三个训练数据都是支持向量。这个收益率，和阈值b=−1。如图1.2（b）虚线所示，决策边界是： 在一般情况下，通过求解方程（1.11）是不能直接得到支持向量机的解决方案。根据KKT条件，式（1.11）仅部分有效。更准确地说,它适用于支持向量相关的行,但不适用于非支持向量相关的行。上述数值示例中，所有三个培训向量恰好是支持向量。因此，自动满足限制，通过切结一组线性方程提供一个分析的解决方案。一般来说，执行符号限制尝尝带来繁琐的数值程序，没有封闭的解。这样一个过程是在识别SVM中的支持向量和非支持向量时时必要的。1.2.3卡罗需-库恩-塔克（KKT）条件在SVM学习模型中,等式(1.11)只适用于选择性的子集训练向量。与这相关的训练向量子集将被命名为支持向量,而其余培训向量将称为非支持向量。更确切地说,积极的训练向量可以再细分如下:(1)支持向量必须满足等式: (1.12)并且（2）支持向量满足不等式： 同样,训练向量可以类似地细分:(1)支持向量满足等式： （1.13）并且（2）支持向量满足不等式： 目前，将变得明确，与支持向量相关联是，而非支持向量是。因此，因此,只有支持向量定义判别函数有一个积极的作用,，见表（1.19）。为方便起见，支持向量的指标表示，其中S表示支持向量的个数。支持向量最优子集的识别在支持向量机学习模型中起着关键性的作用。换句话说，如果这样的子集是已知的，解决方案会通过简单地解决下列等式得：1.2.4支持向量约束是与是与知名的卡罗需-库恩-塔克（KKT）条件密切相关。更准确地说,根据KKT条件、最优的解决方案必须满足下列等式:（1.14）对于所有的训练向量。这有效的将约束分为两类。支持向量。满足（即）的向量被称为支持向量。当时，相应的培训向量必须满足： （1.15） 因此，支持向量处于正确的边际超平面：。这也被成为支持超平面。同样，利用式（1.7）的LSP，我们得到： （1.16） 总之，只有当时，第k个训练向量是一个支持向量。非支持向量。如果那么KKT条件(式(1.14)总是会被遇到不管或者。因此，第k个训练向量没有必要满足零点误差条件：。这进一步意味着第k个训练向量不会直接参与塑造决策边界。为此，第k个训练向量应标记为非支持向量。在给出的式（1.10）中，求解沃尔夫对偶优化的困难点在于正确识别一组适当的支持向量。决策边界一旦乘数已经确定,可以由式（1.17）获得决策向量w: （1.17）阈值b可以被求出： （1.18）是任一个处于正面无误差平面上的支持向量。它遵循的判别函数可以表示为： （1.19）并且决策边界的特征可以用f(x)=0来描述。现在让我们来探讨一个数值例子来帮助说明KKT条件所发挥的关键作用。示例1.2（带有四个二维训练向量的SVM分类器）如图1.3所示的数据集,有四个训练向量：数据矩阵为：对应的线性核矩阵为：图1.3 比较两个分离率表明SVM分类器的产量比LSE分类器较大幅度。（一）LSE的分类器，正面和负面的利润率显示为实线。决策边界是由所有四个训练向量共同决定的，正（负）的安全边际是由正（或负）的训练模式，这是最接近的决策边界。（二）支持向量机分类器的决策边界是由三个支持向量决定的。对于支持向量机，正面和负面的利润率（如虚线）是相同的。由此推导出下列的拉格朗日公式：（1.20）通过调整相对于和B的拉格朗日一阶导数，我们得到： 方程组的线性系统不存在可行解。然而，随着一个训练向量,可能是一个非支持向量，然后通过KKT条件的美德，其相应的乘数为零，即。更重要的是，根据KKT条件，相对于必须是零，因此由上面第一个方程的约束可以被忽略。通过求解余下的四个方程，我们可以得到一个可行的解.和b=-1；它遵循决策向量w:最后，如图1.3（b）所示，决策边界是1.2.5LSE和SVM分离率的比较从理论上讲，支持向量机产生一个最佳的分离裕度之间的类。特别是，它应该有一个比LSE对应更好的边缘。这个结果可以通过比较得到的分类器验证通过LSE（例8.1）和支持向量机（例1.2）。对于数据集（四个二维向量），SVM对LSE的微弱优势。这两个分类的决策边界和分离的利润率显示在图1.3。下面的例子提供了更详细的比较。示例1.3（LSE和SVM分类器的比较）对于给出的示例1.2中数据集（四个二维训练向量），我们有以下意见：对于LSE分类器，决策边界被规定为：正面和负面的安全边际是图1.3（1）的2条短的实心线所示。正类的安全边际是由最近的正训练模式的决策边界。负边缘被定义为类似的方式。例如，两者的利润率分别为0.382和0.318。平均等于0.35。对于SVM分类器，决策边界被规定为：图1.3（二）的虚线表示，正、负利润率均为相同值：注意：0.354＞0.35，因此SVM对LSE在平均利润率方面稍占优势。让我们举个例子来说明比较LDA，RR，SVM的数值：示例1.4（案例研究：比较LDA，RR，SVM）考虑到同一个数据集作为例8.6。其中有四个训练向量：同时，以及SVM的决策边界是，与第一特征主导的决策规则。另一方面，LSE或FDA的决策边界是，作为唯一的决策特征。对于RR，两特征之间的平衡取决于所选择的价值ρ。当0≤ρ＜32，相比SVM，RR更强调第二特征。当ρ=32，RR和SVM具有完全相同的解决方案。当32＜ρ，相比SVM，RR解决方案更强调第一特征。通过定义，训练向量沿决策向量投影之后，支持向量机提供了最广泛的（任一）正面和（任一）负面分离之间的差距。在这种情况下，最宽的宽度是：没有其他的分类可以产生一个更广泛的正面和负面分离的投影。记得，当ρ→∞，RR的解决方案产生了最广泛的后投影分离阳性和阴性的质心之间的宽度：见式（8.61）1.3模糊分离的支持向量机：松弛变量的作用在现实世界中的应用程序，训练向量是不太可能清楚地分离。然而，基于最大可分性相同的配方是可行的只要一些选择性的训练矢量的豁免，即允许违反最低保证金规则。显然，该豁免向量宽间隔的数量越多。这是由图1.4所示。首先，我们注意到，有一个明确的保证金（薄的固体线），其特征是由三个原始的支持向量。然而，一个相当大的分离区（虚线之间）可以通过人为免六违反了培训载体。尽管如此，一个良好的训练向量的大部分仍然是清楚的可分离的，这些载体被保持在禁区外。这些向量将被视为不支持向量的模糊支持向量机分类。图1.4 这一图解说明了如何通过允许一些违规行为创建一个更广泛的分离裕度。1.3.1优化原有空间在模糊支持向量中，一组正松弛变量，是用来放松规定的约束式（1.4）。与松弛变量，我们得到以下的软约束：，∀i=1,...,N,(1.21)当为了防止过度放松惩罚项，其中C是一个预选的惩罚因子，将被添加到原来的损失函数（方程（1.4）），导致：受一系列软限制：同时，并且（1.22）注意，式（1.22）满足定理1.1规定的条件下，进一步保证了学习子空间的性质（LSP）。LSP可以通过如下一个标准的优化分析进行阐述。1.3.2学习子空间特性和优化经验空间将式（1.22）与拉格朗日公式相照应，得到：（1.23）这应用了两种拉格朗日乘子（1）时，（2），时。对偶优化问题可以用以下最小-最大公式来表示： 通过对照于W调整L（W，B，α，β，ξ）的一阶梯度，我们得到了LSP的条件：（1.24）通过对照于b调整L（W，B，α，β，ξ）的指令，我们得到了：（1.25）通过对照于ξ调整L（W，B，α，β，ξ）的指令，我们得到了： （1.26）将式（1.24）-式（1.26）带入到式（1.23），我们得到一种改良的沃尔夫双优化公式：（1.27）受和的限制（注意由于公式（1.25）和（1.26）的限制）。一旦已从式（1.27）获得，向量W和阈值可以通过式（1.24）获得。阈值b可从下式获得：(1.28)对于任意整数k，（在这种情况下，是一个支持向量，正是在于对（正或负）无误差平面。然后，可以得出决策边界,如下：（1.29）让经验决策向量a变为中的向量。那么成本函数可用a和来表达:（1.30）且，i=1,…,N分离裕度向量C分离裕度即，可以通过改变惩罚因子C，其边缘效应（模糊）的分离是由图1.5注意较大值C产生一个窄的模糊分离区为例，区内含有更少的SVS。相比之下，C产生一个更广泛的范围内，可以找到更多的SVS。最合适的C在数据分布上，往往是通过试验和误差得到的。在确定学习支持向量机模型的鲁棒性中，惩罚因子也起着重要的作用。当C是足够小的，它会创建一个体面的大池的支持向量，它们都参与决策。这意味着，由此产生的决策边界成为一个更大的子集的训练向量的一致性。人们普遍认为，包括更多的支持向量的方法。图1.5 线性支持向量机的决策边界（实心线）和边际边界（虚线）的20个数据点。（一）C=10时的线性支持向量机。（乙）C=0.1时的线性支持向量机。这两种情况下的决策边界几乎是相同的。两条虚线之间的区域被认为是“模糊区域”，一个小的区域创建一个更大的模糊区域。数据集来源于A.Schwaighofer。该分类器具有更强的预测能力。在实际应用中，请参见图1.11中C的作用。示例1.5（模糊可分数据集。）在这个例子中，一个线性的支持向量机被施加到的非线性可分20个数据点。图1.5描述了两个（略有不同）的决策边界（显示为实心线）和两个（非常不同）的分离边界（有界的两个虚线）为10和0.1。值得注意的是，大多数（但不是全部）支持向量在平面之间的边际。很明显，当C是小的，分离裕度更宽，允许更多的支持向量。1.3.3支持向量的研究和WEC分析对于明确分离的况下，有一个非常简单的特征支持向量。众所周知，第K个训练向量是一个支持向量，当时，。KKT条件和支持向量在明确可分或模糊可分的情况下，支持向量可以被简单描述为有且只有时，由第i个训练向量是一个支持向量。注意表示式中的KKT条件（1.14），即：，fori=1,2,...,N,(1.31)或者：fori=1,2,...,N,(1.32)这仅适用于明确可分离的情况。对于模糊可分的情况下，KKT条件需要修改为：，∀i=1,...,N.(1.33)这将导致一个更复杂的支持和非支持向量的特性。支持向量的特性如果乘子，然后训练矢量将支持向量必须严格遵守： 对比于方程不等式（1.21）。图1.5（b）中，点1，2，4，9，和10是负数据集的支持向量，而分11，12，15，19，和20是正数据集的支持向量。严格来说,当为支持向量时，条件只是一个必要条件(但不是充分条件)。一般说来,另一方面,当为非支持向量时，条件是必要充分条件。非支持向量的特性如果乘子,这意味着。在这种情况下，相应的训练向量将是一个非支持向量，并将保持在禁区外。图1.5（b），点3，5，6，7，和8为负数据集的支持向量，而分13，14，16，17，和18是正数据集的支持向量。严格来说,当为非支持向量时，条件只是一个必要条件(但不是充分条件)。一般说来,另一方面,当为非支持向量时，条件是必要充分条件。总之,如图1.6所示,所有的支持向量是由两个边际超平面有界,一个由f(x)=1(等价于)正训练样本和一个f(x)=−1(等价于)负训练样本。这形成了的支持向量机的WEC，如图1.6所示。对于正训练数据集,根据KKT条件是一个支持向量(SV)只有在时,这也进一步表明。然而,几乎是一个充分条件为作为支持向量,是减轻(罕见)数据分布,如重复或共面训练向量。因此,它也是一般化的充分条件。(参数为负的数据集是相似的。)图1.6 为一个支持向量的条件的必要（且充分）条件是。 这是通过SVM转化为WEC的帮助。（一）负向量的WEC。因为，决策边界是f(x)=0时，这对应于点。（b）正向量的WEC。现在，，决定点对应于。这两个WECS都表明了，几乎所有的支持向量具有恒定的值，唯一的例外是那些相应的EI=0。这（开放）分离区也可称为恒α区。1.4内核支持向量机要达成一个可变的决策边界，求助于一个支持向量机的非线性核函数是可取的。一个非正式的推导是可以通过非线性核函数代替线性内积得到，即。根据式（1.27），这直接产生以下的一个非线性模糊支持向量机的优化公式：且，又1.4.1内核空间的初始算法对于一个正式的推导，首先让我们来表示的内在空间的判别函数：其误差为：接下来在以式（1.4）的刚性限制同样的理论是为了获得一个清晰可分的模糊支持向量机,另一方面,引入一组松弛变量的为了放松这样的刚性约束。更确切的说,放松约束变为：∀i=1,...,N.(1.34)为了防止过度的违规操作，惩罚项被再次纳入目标函数。现在的模糊支持向量机学习模型在本质空间中有以下的优化公式：受以下公式限制：同时又,∀i=1,...,N.(1.35)注意，该公式满足定理1.1中规定的条件，从而进一步保证了学习内在空间中子空间的性质（LSP）。在随后的讨论中，LSP将再一次地独立确认通过标准的优化分析。1.4.2经验空间中的双重优化器与式（1.35）相对应的拉格朗日公式：（1.36）在拉格朗日乘子确保，而提供类似的目的确保。对偶优化问题可以表示为以下公式：在相同的数学操作下进行式（1.27）的推导，为线性的情况下，我们就得到下面的沃尔夫对偶公式： （1.37）且又用取代，我们有一个关于a的等价优化公式： （1.38）就像在式（1.28），可以再次得到阈值b： （1.39）对于任何的整数k，都有这将推导出以下支持向量机学习算法。算法1.1（支持向量机学习模型）给出了核矩阵K和引导向量y，支持向量机学习量为乘子系数决策向量： 且又(1.40)或者，等价地，通过解决实证决策向量a： 且又（1.41）LSP明确对于支持向量机，我们有： 因此判别函数是： （1.42）a可以从方程（1.41）和式（1.39）中得出。最后，可以用作结果。再一次，让我们用OCR数据作为优化公式的例子。示例1.6（OXR数据的非线性支持向量机）OXR数据是线性不可分的；有必要采用非线性核函数。非线性支持向量机的分类可以通过最大化得到：其限制条件为，且其中的惩罚因子被设置为C=1。优化解