06-支持向量机方法解说.ppt

* SVM objective is convex, S3VM objective is non-convex. Finding a solution for semi-supervised SVM is difficult, which has been the focus of S3VM research. Different approaches: SVMlight, rS3VM, continuation S3VM, deterministic annealing, CCCP, Branch and Bound, SDP convex relaxation, etc. The S3VM optimization challenge * Applicable wherever SVMs are applicable, i.e. almost everywhere Clear mathematical framework More modest assumption than generative model or graph-based methods Advantage Disadvantage Optimization difficult Can be trapped in bad local optima Semi-supervised SVM (S3SVM): * 多类问题 * One-vs-all:在第k类和其他k-1类之间构建超平面。在这种方式下，系统仅构建K个svm，每一个svm分别将某一类的数据从其他分类的数据中鉴别出来。在对第i个svm训练时，用第i个类中的训练样本作为正训练样本，而将其他样本作为负类样本。 Pairwise：为任意两个类别构建超平面，共需建立k(k-1)/2个Svm 分类器。在这种方式下，是对k个分类的训练集进行两两区分。测试时，通常采用投票法，得票最多的类别作为最终结果。其缺点是分类器数目随着类别增加而迅速增加。 多类问题 * 多类问题 * One-class svm 若只有一类样本，如何对其进行建模并进行检测？ One-Class SVMs for Document Classification. Journal of Machine Learning Research 2 (2001) 139-154 * Weka, mysvm. etc * * Some conclusions about SVR ? 只有对应 的样本落到函数 f 的ε-不敏感“管道”之外； ? 对任意样本，有 ，即其两个系数不可能同时非零； ? 对于 ，定有 且 ，对应于分类SVM中的支持向量，且可根据这些支持向量求取b： * No-linear SVR 在考虑模式识别问题时，我们将输入向量映射到了高 维空间，在这里，采用同样的做法，可以构造形式为 的最优逼近问题，其中 是标量， ， 是向量, 是满足Mercer条件的一个给定函数。 与模式识别问题中相同，由于SVR最终只涉及向量之间的内积运算，我们选择适当的核函数内积替代之即相当于对向量进行了非线性变换，可得到非线性的SVR。 * No-linear SVR 得回归函数: * No-linear SVR Polynomial of power p: K(xi,xj)= (1+ xi Txj)p Gaussian (radial-basis function network): Sigmoid: K(xi,xj)= tanh(β0xi Txj + β1) * Example 在要求的精度水平下，要逼近在均匀网格 上的值 定义的一维和二维函数。考察逼近精度与支持向量数目之间的关系。 * 逼近一维sinc函数 的例子： 为了构造一维线性样条逼近，采用了核 其中 得到的逼近形式为 其中，系数 是求解二次优化问题的结果。 Example * Example * Example * Example 逼近定义在 上的二维sinc函数： 为了逼近二维sinc函数，采用核 得到的逼近形式为 * Example * 为什么ε值控制支持向量数目？ 假设我们要以精度ε逼近函数 , 即用函数 来描述估计函数，使得函数 处在 的ε-管道内。要构造这样一个函数，我们取一个弹性ε-管道（管道总是趋向于平坦）并把函数 放到这个ε-管道中。 因为弹性管道总趋