(斯坦福大学公开课机器学习课程note3翻译.docxVIP

Part VSupport Vector Machines这篇讲义讲的是支持向量机（SVM）学习算法。SVMs是最好的“非专门设计的”监督学习算法。为了讲SVM的故事，我们需要先讲一下分散数据的边际概念。接下来我们会说一下最优边际分类，虽然会有一点离题去讲拉格朗日对偶。我们也会说一下这个核心，给出一种支撑SVMs很有效的适用于高纬度的特征空间，最后我们会以能够很好实现SVMs算法的SMO结束这个故事。1 Margins: Intuition我们会以考虑边际开始我们的故事。本节会给出边际判断和预测的“自信力”；这些东西会正式的讲解在第三节。 考虑一下逻辑回归，概率p(y=1|x; θ)由hθ（x）=g（θTx）给出。我们然后会预测“1”通过输入到x当且仅当，或者是当且仅当。有一个正数训练样本（y=1）。越大，就越大，因此我们的预测标签是1的“自信度”也就越高。因此，正式的我们能认为我们的预测作为一个自信的模型如果。同样的，我们认为逻辑回归做出一个非常自信的预测对于y=0，如果。给定一组训练集，如果我们能找到一个θ使的对于所有的x有当对于任意y有y=1并且对于任意的x有成立当对于所有的y=0，因此这个能反映一个非常正确的分类集对于所有的训练样本。这看起来是一个好的目标去实现，并且我们很快会把这个想法实现出来用函数边际的概念。 对于一个不同的类型关于判断事实，考虑下列图形，x代表正的训练样本，0代表负的训练样本，一个决策边界（图中给定的这条线由给出的，被叫做分类超平面）在图中给出，并且有三个点被标出为A，B和C 注意这个点A离我们的决策边界很远。如果我们被要求去预测一个值y就在A点，看起来我们应该很自信的说y=1.相反的是，C点离这个决策边界很近，并且他也是在我们预测的y=1的一边，看起来如果有一点点的改变的话这个预测值就会改变为y=0.因此，我们相对于C点来说对我们在A点的预测更为自信。点B是介于这两种情况之间，更广泛的说，我们可以看到当一个点远离分类特征时候，我们会更加自信对于我们的预测值。再一次，我们认为他会更好，给定一个训练集，我们想要去找到一个决策边界能够使我们去对所有的数据做正确的和自信的预测。我们会讲到这个在之后使用几何边际的概念。 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就是以前的[θ1,θ2,…,θn]T。 注意，使用我们上面对g的规定，我们的分类器预测出来的值是-1和1，省去了需要对y进行大约估计的中间步骤。（那是在逻辑回归中做的事情。）3 Functional and geometric margins（函数和几何间接）我们把功能和几何间隔形式化。给定一个训练集（xi，yi），我们定义（w，b）相对于训练集的函数间隔：注意，如果yi=1，这个函数间隔会变大（例如：对于我们的预测会更加自信和正确。）然后我们需要是一个很大的正数。相反的，如果yi=-1，那么这个函数间隔也会变大，那么我们需要是一个很大的负数。此外，如果，那么我们对于这个训练样本的预测是正确的。（自己证明）。因此，一个大的函数间隔代表一个自信的和正确的预测。 对于一个已经给定了上述g的线性分类器，然而，有一个关于函数间隔的性质使的他不能作为判断是否分类完好的标准。选定函数g，我们注意到如果我们使用2w替换w，2b替换b，然后，这个并不会改变最终的输出结果。也就是g和仅仅依赖于正负而不是大小。然而，用（2w,2b）替换（w，b）也使我们的函数间隔增加了2倍。因此，看起来我们按规定的比例值增大w,b，而且这也是我们的函数间隔变大但是这个改变是没有什么意义的。更直观的说，可能那样会有意义就是增加一些标准性的条件，比如像||w||2=1；也就是说，我们可能会使用（）替换（w,b），并且考虑这时候的函数间隔。之后我们会再回来讨论这个问题。 给定一个训练集S=｛（xi，yi）；i=1，…,m｝,我们同样定义关于(w,b)的函数间隔关于S作为最小的关于给定训练样本的函数间隔。一样可以写出：接下来,我们讨论几何间隔。考虑一下下面这张图：这个和(w,b)相一致的决策边界如图所示，伴随着向量V。注意w是和分离超平面垂直的。考虑这个点A，代表输入的训练样本xi的标签yi=1.他到决策