《斯坦福大学公开课 ：机器学习课程note3翻译.docx》由会员分享，可在线阅读，更多相关《斯坦福大学公开课 ：机器学习课程note3翻译.docx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Part VSupport Vector Machines这篇讲义讲的是支持向量机（SVM）学习算法。SVMs是最好的“非专门设计的”监督学习算法。为了讲SVM的故事，我们需要先讲一下分散数据的边际概念。接下来我们会说一下最优边际分类，虽然会有一点离题去讲拉格朗日对偶。我们也会说一下这个核心，给出一种支撑SVMs很有效的适用于高纬度的特征空间，最后我们会以能够很好实现SVMs算法的SMO结束这个故事。1 Margins: Intuition我们会以考虑边际开始我们的故事。本节会给出边际判断和预测的“自信力”；这些东西会正式的讲解在第三节。 考虑一下逻辑回归，概率p(y=1|x; )由h（x）=
2、g（Tx）给出。我们然后会预测“1”通过输入到x当且仅当，或者是当且仅当。有一个正数训练样本（y=1）。越大，就越大，因此我们的预测标签是1的“自信度”也就越高。因此，正式的我们能认为我们的预测作为一个自信的模型如果。同样的，我们认为逻辑回归做出一个非常自信的预测对于y=0，如果。给定一组训练集，如果我们能找到一个使的对于所有的x有当对于任意y有y=1并且对于任意的x有成立当对于所有的y=0，因此这个能反映一个非常正确的分类集对于所有的训练样本。这看起来是一个好的目标去实现，并且我们很快会把这个想法实现出来用函数边际的概念。 对于一个不同的类型关于判断事实，考虑下列图形，x代表正的训练样本，0
3、代表负的训练样本，一个决策边界（图中给定的这条线由给出的，被叫做分类超平面）在图中给出，并且有三个点被标出为A，B和C 注意这个点A离我们的决策边界很远。如果我们被要求去预测一个值y就在A点，看起来我们应该很自信的说y=1.相反的是，C点离这个决策边界很近，并且他也是在我们预测的y=1的一边，看起来如果有一点点的改变的话这个预测值就会改变为y=0.因此，我们相对于C点来说对我们在A点的预测更为自信。点B是介于这两种情况之间，更广泛的说，我们可以看到当一个点远离分类特征时候，我们会更加自信对于我们的预测值。再一次，我们认为他会更好，给定一个训练集，我们想要去找到一个决策边界能够使我们去对所有的数
4、据做正确的和自信的预测。我们会讲到这个在之后使用几何边际的概念。 2 Notation 符号为了使我们对SVMs的讨论更加简单，我们首先需要介绍一下讨论新的算法需要用的符号。我们考虑一个线性分类器对于一个二值分类问题使用标签为y和特征为x。现在开始，我们使用y-1，1（包括0，1）表示分类标签。同样的，我们会使用参数w，b来表示我们的分类器而不是使用向量，接下来可以写出来我们的分类函数：这里g（z）=1如果z=0；其他情况下g(z)=-1。参数“w，b”可以使我们明确的把偏置项b和其他的参数分开。（我们舍弃了以前使用的令x0=1作为偏置项的决定）因此，b现在扮演的角色就是以前的0，w就是以前的
5、1,2,nT。 注意，使用我们上面对g的规定，我们的分类器预测出来的值是-1和1，省去了需要对y进行大约估计的中间步骤。（那是在逻辑回归中做的事情。）3 Functional and geometric margins（函数和几何间接）我们把功能和几何间隔形式化。给定一个训练集（xi，yi），我们定义（w，b）相对于训练集的函数间隔：注意，如果yi=1，这个函数间隔会变大（例如：对于我们的预测会更加自信和正确。）然后我们需要是一个很大的正数。相反的，如果yi=-1，那么这个函数间隔也会变大，那么我们需要是一个很大的负数。此外，如果，那么我们对于这个训练样本的预测是正确的。（自己证明）。因此，一
6、个大的函数间隔代表一个自信的和正确的预测。 对于一个已经给定了上述g的线性分类器，然而，有一个关于函数间隔的性质使的他不能作为判断是否分类完好的标准。选定函数g，我们注意到如果我们使用2w替换w，2b替换b，然后，这个并不会改变最终的输出结果。也就是g和仅仅依赖于正负而不是大小。然而，用（2w,2b）替换（w，b）也使我们的函数间隔增加了2倍。因此，看起来我们按规定的比例值增大w,b，而且这也是我们的函数间隔变大但是这个改变是没有什么意义的。更直观的说，可能那样会有意义就是增加一些标准性的条件，比如像|w|2=1；也就是说，我们可能会使用（）替换（w,b），并且考虑这时候的函数间隔。之后我们会
7、再回来讨论这个问题。 给定一个训练集S=（xi，yi）；i=1，,m,我们同样定义关于(w,b)的函数间隔关于S作为最小的关于给定训练样本的函数间隔。一样可以写出：接下来,我们讨论几何间隔。考虑一下下面这张图：这个和(w,b)相一致的决策边界如图所示，伴随着向量V。注意w是和分离超平面垂直的。考虑这个点A，代表输入的训练样本xi的标签yi=1.他到决策边界的距离是线段AB。 我们怎么样才能找到的值？是单位向量的长度方向和w一样。因为A代表xi，因此我们发现B由给出。但是这个点在决策边界上，并且所有在决策边界上的点x都满足。因此：解出： 这个对于算出对于一个在图中A点的正的训练集，在决策边界的正
8、方向一侧是好的。更一般的，我们定义（w，b）得到几何间隔使用训练集（xi，yi）注意，如果|w|=1，这个函数间隔等于几何间隔-因此这给出了一种关于两种不一样的表示之间的联系。并且，重新调节参数几何间隔是不变的，也就是说，如果我们用（2w，2b）替换（w，b）这个几何间隔是不变的。这个迟早会用到的。特别的，因为这个不变性，当试图去找到合适的w和 b去训练数据时候，我们可以假设改变任意大小对w而不改变其他重要的东西；例如，我们可以要求|w|=1或者|w1|=5或者|w1+b|+|w2|=2，这些都能适应简单的改变w和b。 最后给定一个训练集S=（xi，yi）；i=1，,m，我们定义关于S的（w，
9、b）的几何间隔是最小的在所有的几何间隔中。4 The optimal margin classifier 最佳间隔分类器 给定一个训练集，看起来像从我们以前讨论的里面拿来的一个必需品去试图找到一个决策边界最大化这个间隔，因此这个会反映一个非常明确的对训练集的预测和适合的参数。特别的，这会导致分开正的训练样本和负的训练样本用一个间隔。 现在开始，我们假设我们给定一个训练集是可线性分隔的。也就是说那是可能的分开正的和负的训练样本使用分类超平面。我们怎么才能找到这个分类超平面使的这个几何间隔最大化？我们能提出下面的最佳化问题：也就是说，我们想要最大化，对于每一个训练样本都使用的最小的。此外条件|w|
10、=1约束使的几何间隔等于函数间隔，因此我们能保证对于所有的几何间隔都有最小的。因此，解决这个问题会归结于求（w，b）使的几何间隔最大化在训练集中。 如果我们想解决上面这个优化问题，我们已经做了的。但是条件“|w|=1”是向下的（非凸的），并且这个问题不能以任何形式用标准优化软件去解决。因此试着去改变这个问题成为一个好一点的。考虑下面这个式子：这里，我们想要最大化，受制于函数间隔的所有条件都是在最小化。因此，这个几何和函数间隔是通过联系，这会给我们一个我们想要的答案。此外，我们还摆脱了|w|=1的约束。负面的影响是我们现在有一个非凸的目标函数：，并且我们仍旧没有得到任何的现成的软件可以去解决这类
11、优化问题。 继续。重新回到我们以前的讨论我们能加上一个任意的缩放约束对于w和b而不改变其他东西。这是我们现在要用的主要思想。我们接下来会介绍这个对w，b的缩放约束对于函数间隔在训练集必须是1的条件下： 因此，使w和b乘上一些约束结果导致这个函数间隔同样乘以相同的常熟，这的确是一种缩放约束并且能被适用通过改变w和b。把这些加到我们上面的问题中，并且注意最大化 =是同样的事情和最小化。我们现在有下面的优化问题：我们现在已经改变这个问题到另一个形式能够被有效解决的形式。上面的是一个优化问题带有凸二次方程和仅仅是线性缩放的。他的解决给了我们一个最优间隔分类器。这个最优问题能够被解决使用商业的二次规划代
12、码。 然而现在我们说的问题已经被解决了，我们接下来要做的就是离题讨论一下对偶。这个会引导我们的最优问题到对偶形式，这将会扮演一个重要角色在允许我们使用k均值去得到最优间隔分类器去有效的解决问题在更高维的空间中。这个对偶形式也会允许我们导出一个有效的算法对于解决最优问题能够比商业二次规划代码解决的更好。5 Lagrange duality拉格朗日对偶 让我们先临时的把SVMs和最大化间隔分类器放一边，先考虑一下解决最优选择问题。 考虑如下形式的问题：你们又会说拉格朗日乘数的方法怎么能用来解决这类问题。（不要着急如果以前你没有见到过的话。）在这种方法中，我们定义这个拉格朗日函数为：这里，叫做拉格朗
13、日乘数。我们之后会是他的偏导数等于0：并求出w和。在本节中，我们会归纳这个为最优选择问题我们把不平等的最优当作平等的。由于时间限制，我们本节不会真的去讲拉格朗日对偶的理论推导，但是我们会给出这个主要的定义的结论，我们之后会应用到我们的最优选择问题中。 考虑下面这个问题，我们叫做原始最优问题：为了解决他，我们开始定义一般化的拉格朗日函数：这里，和都是拉格朗日乘数，考虑下面这个等式：这里“p”代表“一般化”。先给定一些w。如果w违反了任何的一般化限制（例如：如果对于任何的gi(w)0或者hi(w)!=0对于i）然后你要能证明：相反的，如果限制条件非常适合一个特别的w，有。因此： 和我们问题中的适合
14、一般化模型的所有的w的值相同，并且是正的如果限制条件被违反了，因此，如果我们考虑这个最小化问题：我们看到这是同一个问题，一般化问题。对于之后的使用，我们也定义这个类的最优值为，我们交这个值为一般化问题的最优值。现在，我们考虑这个有一点点不一样的问题.我们定义：这个“D”代表“对偶”。注意我们定义最优化这个值使用和，这里最优化是依赖于w。我们现在提出对对偶最优化问题的讨论：这个整好和我们上面说的一般化问题一样，出来这个求最值问题换了一下。一个是求最大一个是求最小。我们定义对偶问题的最优值为这个一般化问题和对偶问题有什么联系呢？他可以简单的用下面公式表示：然而，在确定的情况下，我们有，因此我们能解
15、决对偶问题代替原始的问题。我们看一下这些条件. 假设f和gis都是给定的，并且his是仿射变换。进一步假设假设条件gi是可行的；这意味着存在w使得gi(w)0对于所有的i都成立。在我们上面的假设中条件下，必定存在以便于是原是问题的最优解，是对偶问题的最优解，并且。更进一步，适用于KKT条件，如下所示：更进一步说，如果使用于KKT条件，那也就是一种解决原始化和对偶问题的解。 我们看一下等式（5），等式（5）被叫做KKT对偶互补条件。特别的是他反映的是如果那么。（例如：“”条件是激活的，意味着他支持这个等式而不是不等式。）然后，这个会是这个关键对于表示SVM仅仅有一小部分对于“支持向量”成立；这个
16、KKT对偶互补条件也会给我们测试当我们讨论SMO算法时候。6 Optimal margin classifiers最有间隔分类之前，我们给出了下列优化问题去寻找这个最有间隔分类器：我们有一个约束对于每一个训练样本。注意在KKT对偶互补条件中，我们有仅仅对训练样本哪些有函数建个整好对应这个。（例如：这些相对应的约束条件支持等式）。考虑下面的图像，最大间隔分割平面是这个实线。这些最小间隔的点整好是哪些靠近决策边界的那些；这里有是那个点（一个正的和两个负的样本）整好落在和决策边界平行的虚线上。因此，只有三个s-也就是说这三个点相对应的训练样本-将不会等于0在最优化解决中对于我们的最优化问题。这三个点
17、叫做支持向量在这个问题中。这个事实是这个支持向量的数量可以比着训练集小很多。 继续，朝前看，我们提升这个问题为对偶形式，一个主要的注意就是关注我们试图写我们的算法用内积的形式在两个输入特征空间中间。这个事实我们能表示出我们的算法用内积形式将会是我们应用于标志性内核的主要。 当我们重构拉格朗日函数对于我们的最优化问题，我们有：注意这里仅仅只有i而没有i作为拉格朗日乘数，因为这个问题只有不等式限制。 我们找到这个问题的对偶形式。为了这样做，我们需要收线最小化L（w，b，）用w和b，得到，我们将会设置L对w和b的偏导数等于0。这表明：对b求偏导得到：如果我们对照等式（9）的定义并且带回到拉格朗日函数
18、中并且化简我们得到：但是根据公式（10），最后一项必须为0，因此重新说我们得到上面这个等式通过最小化L使用w和b。把这些放在一起和还有公式（10），我们得到下面的对偶优化问题： 你同样需要证明这个条件对于p*=d*和KKT条件支持这个最适合的在我们的优化问题中。因此我们可以解决对偶代替解决原始化问题。特别的是，在上面对偶问题中，我们有一个最大化问题参数是s。我们之后会使用这个特别的算法我们将会用来去解决对偶问题，但是如果我们能够解决它，然后我们能使用等式（9）去带回并且找到这个最优的ws最为s的函数。找到w*之后，通过考虑最优化问题，可以直接计算出最优值对于偏置项b在进一步讨论之前，我们先详细
19、的看一下等式（9），给出了w的最优值使用。假设我们找到适合我们的模型参数对于一个训练样本，并且现在想要去做一个预测对于一个新的输入x。我们将会计算并且假设y=1有且仅有这个值比大。但是使用（9），这个值能写成：因此，吐过我们已经找到了s，为了做一个预测，我们必须要计算一个值仅仅依赖与内积在x和训练集中的点。更进一步，我们可以看到s将会是0除了支持向量外。因此，在和中的大部分的项都会是0，并且我们真切的想要找到这个内积在x和支持向量之间在我们的计算（13）中并且做出我们的预测。 通过测设最有问题的对偶形式，我们得到重要的在洞察在这个问题结构中，并且能够写出整个算法用内积的形式在输入特征向量之间；
20、在下一节中，我们会探索这个性能去适应于内核对于我们的分类问题。这个结果算法，支持向量机将会是有效的学习在更高维度的空间。7 Kernels内核回到之前我们对于线性回归的讨论，我们有一个问题关于输入x即房子的面积，并且我们考虑表现回归使用特征x，x2和x3去得到一个三次函数。为了区分这两个变量集，我们叫“原始”的输入值作为问题的输入属性（在这个问题中为x，房子的面积）。当映射到一些新的数量级输入到学习算法中，我们将会叫那些新的数量为输入特征。（不幸的是，不同的作者使用不同的形式去描述这两件事情，但是我们会试着使用一贯的术语在本讲义中）我们也会使用表示特征图，那些表示特征属性的图集。例如：在我们的
21、例子中，我们有：相比较适用于SVMs使用原始输入属性x，我们更倾向于使用特征(x)去学习。为了这样做，我们仅仅需要转变我们之前的算法就好，并且替换每一个x使用(x)。由于这个算法能够被完整的用内积表示，这就意味着我们可以替换所有的内积用.特别的是，给定一个特征图，我们定义这个相应的内核为：之后，在我们的算法中碰到的没一个我们都能够简单的替换使用K(x,z)，并且我们的算法现在学习使用特征。现在，给定，我们能够简单计算出K(x,z)通过找到(x) 和(z)并且做他们的内积。但是更有意思的是通常情况下K(x,z)都是很容易计算的，即使(x)他本身可能是很难计算的（可能因为他是特别高维的向量）在一些
22、设置中，通过使用我们的算法作为一个有效的方法去计算K(x,z)，我们能得到SVMs去学习在高维的特征空间中使用给给定的，但是除了已经明确的知道或者代表向量(x)。我们看一个例子。假设x，zRn，并且我们也能写为：因此，我们看，这个特征映射已经给定通过注意当计算高维的(x)需要O（n2）时间，找到K(x,z)仅仅需要O(n)的时间-线性的在输入属性的纬度。对于一个相关内核，同样考虑：这个相对应的特征映射为：参数c控制这个相关系数xi和xixj之间。更宽泛的说，内核相对于到 空间的特征映射，对应于每一个xi1，xi2.xik适用于顺序d。然而，尽管在维空间中计算K(x,z)所用时间仍然仅仅是O(n
23、)，并且因此我们从不需要去明确的表示特征向量在非常高维的特征空间中。 现在，讨论一个稍微不同的观点对于内核。直观上（有一些东西是错误的在直觉上，但是不要介意），如果(x)和(z)挨的特别紧，我们可能会期望非常大。相反的如果(x)和(z)离得比较远-也就是说二者差不多正交-那么将会非常小。因此，我们可以认为K(x; z)作为(x)和(z)之间距离的一种测量，或者说x和z有多相似。 给出这个直观的判断，假定对于一些学习算法你正在研究的，你已经提出一些函数K(x; z)你认为可能是一个可行的测量关于x和z有多相似。例如：假设你选择这是一个公平的测量方法关于x和z有多相似，并且接近于1当x和z接近时，
24、接近于0当x和z离得非常远的时候。我们是否能使用这个K的定义作为内核在SVM中?在这个特别的例子中,答案当然是yes.(这个内核叫做高斯内核,并且接近于无穷纬度的特征映射)但是更一般的说，给定一些函数K，我们怎么样才能识别他是否是一个有效的内核；例如，我们怎么才能知道是否存在特征映射使得对于所有的x和z？ 假设现在K是一个有效的内核非常接近于一些特征映射。现在，考虑一些有限的m个点的集合x1，x2.xm并且组成一个矩形，m*m的矩阵K被定义以便于使他的(I,j)输入被给出由。这个矩阵被叫做内核矩阵。注意我们已经介绍过这些符号并且使用K去代表这个内核函数K(x，z)和内核矩阵K，由于他们明显接近
25、的关系。 注意，如果K是一个有效的内核，那么 并且因此K必须是对称的。更多的，用k(x)代表第K个相同的向量(x)，我们发现对于任意的向量z，我们有：倒数第二步使用相同的诀窍想你在问题集1Q1中看到的那样。由于z是任意的，这表明K是正的（K=0）至此，我们已经证明K是否是一个有效的内核（例如：如果他接近于一些特征映射），之后这个接近的内核矩阵KRm*m是对称的正的。更一般的说，不重要的但是有效的的条件对于说明K是一个有效的内核。下面的结果是由于Mercer。Mercer定理：令K：已经给定。然后为了使K是一个有效的内核，那是重要的也是有效的对于所有的x1,x2xm（m无穷），这个相对应的内核矩
26、阵是对称半正定的。 给定一个函数K，除了试图找一个特征映射接近他的，这个定理因此给出了另一种方法用来测试是否他是一个有效的内核。你将会更多的机会接触这些在问题集2。 课堂上，我们简明的讨论关于几个其他关于内核的例子。例如：考虑这个数字识别问题，给定一副手写体数字（0-9）的图像（16*16像素），我们必须辨识出是那一个数字。使用任何一个简单的多项式内核K（x，z）=（xTz）d或者高斯内核，SVMs能够得到相当好的表现对于这个问题。这个是非常惊奇的由于这个输入属性x是一个256维的向量关于图像的像素值，并且这个系统没有对于视觉的只是，乃至于那些像素在其他的前面。另一个例子我们简单说一下在课堂上
27、是如果类x我们试图去分类的是字符串（也即是说，x是一列氨基酸，仅仅的和蛋白质在一起），然后他看起来很难去建模一个有效的“小的”数据集关于特征对于大多数的学习算法，特别是如果不同的串有不同的长度。然而，考虑使(x)为一个特征向量包含没一个在x中出现的。如果我们考虑用英文，那么就有26个这样的串。因此（x）是一个26维的向量；甚至对于K，这可能太大了对于我们高效的工作。然而，使用串匹配算法，他是有可能的去高效的计算因此我们可以暗中的计算在26维的特征空间中，但是不明显的在这个空间中计算特征向量。这个关于内核的应用对于支持向量机应该已经很明白并且因此我们不会过多的讨论他在这里。记住这个内核的注意有更
28、重要和广泛的应用比着SVMs。特别的，如果你有任何学习算法你能够写出呢个内积的形式表示K是一个内核，你可以“魔法的”允许你的算法去高效的工作在更高纬度的特征空间中接近于K。例如：内核映射能够适用于这个感知机去得到一个内核感知机算法。大多数我们之后会看到的算法都经得起检验对于这种方法，这个算法已经广泛传播为“内核追踪”。8 Regularization and the non-separable case规则化和不可分的情况 SVM的推导已经至今已经提出的是假设这个数据是线性可分的。当数据映射到一个高纬度的特征空间通过做一般的增长这个似然函数使这个数据可分，我们不能保证这种方法总是能够成功。因此
29、，在一些情况下他不是明显的能找到一个分割平面我们正好想要的，由于对一些超过边界的点比较敏感。例如，下面左边的图表明一种优化矩阵分类器，并且当一个单一异常值增加进来之后在这个左上角，他使得这个决策边界做了一个大幅度的转动，并且这个结果分类器有一个更小的边距。为了使这个算法适用于非线性可分的数据集并且对这个异常值不是特别的敏感，我们形式化我们的优化项（使用l1正则化）如下：因此，例子现在允许有函数间隔小于1并且如果一个样本的函数间隔是，我们会给出一个损失项为。这个参数C控制这个相关权重在成对的目标之间使的最大（我们能看到的是使这个间隔最小）并且确保这个大部分的样本的函数间隔至少是1。 像以前一样，
30、我们能定义这个极大似然函数：这里，和是我们的拉格朗日乘数（都大于等于0）我们不再计算这个导数，但是之后设定这个函数对w和b的导数为0，把他们代回到前面，并且化简，我们得到下面的式子：像之前一样，我们同样有w能够被表达使用的形式如在式子9中给出的那样，因此在解决这个对偶问题之后，我们能够继续使用式子13去做我们的预测。注意，意外的是，在增加L1正则化项之后，这个对偶问题仅有的变化是最初的约束条件i0现在变为0iC。对b*的计算也相应的改变（式子11不再适用。）；看下面一节的评论。同样的，KKT对偶互补条件是：现在，所有的剩下的就是得到一个算法对于实际解决这个对偶问题，也即是我们下一节所要做的事情
31、。9 The SMO algorithm序列最小优化算法序列最小优化算法，被John Platt提出的，给出了一种效率的方法去解决对偶问题。一部分程度上为了刺激SMO算法，一部分因为他非常有趣在他自己的权力，我们离题讨论一下相关的算法。9.1 Coordinate ascent 并列上升考虑试着去解决无约束的优化问题，这里我们认为W是关于参数的函数，并且现在忽略任何的联系在这个问题和SVMs之间。我们已经看过两个优化算法，梯度上升和牛顿法。新的算法我们将要在这里讨论的被叫做并列上升：因此，在这个循环的最里层，我们会保持所有的参数出来i不变，并且重复优化W仅仅使用i。这里提出来的方法，这个循环的
32、最里面一层重复优化这个函数使用i当这个函数W能够被求出最大值在这个循环的最里层，这个并列上升算法能被是为一种非常有效率的算法。下面这张图说明了这个算法是怎么工作的：这个图中的椭圆是这些二次函数我们想要去优化得到的。并列上升初始化为（2，-2），在图中描绘出来他的行进路线到全局最大值。注意在每一步中，并列上升行走一部他的路线都平行与一个核心值，因此每一步只有一个参数被优化。9.2 SMO我们结束对Svms的讨论用SMo算法。一些细节将会被留做家庭作业，其他的你们可以参考这个论文课外找到的。下面就是这个优化问题我们想要去解决的：我们有is适用于等式（18-19）。现在假设我们2. m是固定的，并且
33、对问题做并列上升和迭代优化这个目标用1。我们能有任何进步吗？答案当然是否定的。因为等式19确保：或者，通过对等式化简使用y1我们可以得到：（这一步使用这个结论y1-1，1，因此（y1）2=1）因此，1是确定的参数可以通过其他的参数表示出来，并且如果我们想要保持2m固定，我们也不能对1做任何的改变出来违反等式19在这个优化问题中。因此如果我们想要更新一些i我们必须更新至少他们中的两项以便于保证能服从这个约束条件。这便催生出来SMO算法，如下所示：为了测试这个算法的收敛性，我们可以检测是否KKT条件（14-16）是否适用在使用tol。这里，tol是这个收敛容差参数，并且通常被设置在0.01到0.0
34、01之间。这个关键的原因说SMO是一个有效率的算法是这个更新对i和j能够被很有效率的计算出来。我们接下来简单的描述一下这个算法的效率更新。我们说我们当前的一些设置对于is都能适用于这个约束条件（等式18-19），并且假设我们保持3m是固定的，并且想要去优化W使用1和2。从等式19中，我们要求由于这个等式的右边是固定的，我们可以使他被定义为固定参数：我们能够画出下面的约束条件对于1和2从等式18中我们知道1和2必须在0，C*0，C之间。画出这条1和2必须符合的直线。注意，从这些约束条件中，我们知道L2H；另一方面，（1，2）不能同时的适用于这个盒子和这个直线约束。这个例子中，L=0。但是取决于这
35、个直线，这个通常不是这个问题的重点，但是更一般地说，会有一些下界L和上界H在许可的值对于2会确保1和2刚好在这个约束条件中。使用等式20，我们也能写出1为2的函数：（自己检查这个推论，我们会再一次使用这个定理y1-1，1因此（y1）2=1）因此这个目标函数W（）能够被写为：把3m固定，你能够证明这个仅仅是一个关于2的二次函数。例如：这个能够被表示为如下形式对于大多数的适当的a，b，c。如果我们忽略这个等式18的约束条件，那么我们能简单的最大化这个二次函数通过设置他的导数为0并且解出来。我们会使表示这个结果值对于2。你同样可以信服你自己如果我们代替我们想要最大化W使用2但是受限制于这个约束条件，之后我们能够妨碍西安这个结果值简单优化通过使用并且可以转化到下面的约束条件中最后，找到这个，我们能够使用等式20去代会到前面并且找到这个最优值对于。这里还有更过的细节我们能够很简单的证明但是我们会留给你自己去读在Platt论文：One is the choice of the heuristics used to select the next i, j to update；另一个是怎么更新b随着SMO算法运行。