大数据十大经典算法SVM讲解.ppt

通俗的说：找到一个最宽的直线，将类别分开，超平面为直线的中心线。 类间间隔最大 - 结构风险最小 - 泛化能力强 解释 支持向量所在平面方程 为什么为+1，-1. ai有许多为0 到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。 到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。 通过给每一个约束条件加上一个 Lagrange multiplier(拉格朗日乘值)，即引入拉格朗日对偶变量α，如此我们便可以通过拉格朗日函数将约束条件融和到目标函数里去 到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。 到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。 当某个约束条件不满足时，例如?yi(wTxi+b)1，那么我们显然有?θ(w)=∞（只要令?αi=∞?即可）。而当所有约束条件都满足时，则有?θ(w)=12∥w∥2?，亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化?1/2 *∥w∥^? 实际上等价于直接最小化?θ(w)??? ? 原问题 -》 二次凸优化问题（已有很好的体系来解决此类问题） -》 对偶问题（将约束条件加入到目标函数内） -》 SMO优化问题（可以省略） 具体细节见 参考资料 内积 ，为核函数引入奠定基础。 R5空间无法显示，动态图为映射到R3空间的效果。 总结： 1、核函数的价值在于将特征进行从低维到高维的转换，但核函数事先在低维上进行计算，而将实质上的分类效果表现在了高维上，避免了直接在高维空间中的复杂计算。 2、核函数：找到某种方法，它不需要显式的将输入空间中的样本映射到新的空间中，而能够在输入空间中直接计算高维空间内积 。它其实是对输入空间向高维空间的一种隐式映射，它不需要显式的给出那个映射，在输入空间就可以计算 ，这就是传说中的核函数方法。 具体细节见 参考资料 具体细节见 参考资料 线性分类 1 线性分类 最优标准：分类间隔 对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点（xi,yi）的函数间隔为 对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点（xi,yi）的几何间隔为 ||w||叫做向量w的范数,WX的p范数为 ||w||p=(X1^p+X2^p+...+Xn^p）^(1/p) 函数间隔和几何间隔的关系? = ? / ||w|| （1） 最优标准：分类间隔 H2与H之间的间隔便是几何间隔。其中H1：wx+b = 1；H2：wx+b = -1； 定义超平面（w,b）关于训练数据集T的函数间隔为超平面（w,b）关于T中所有样本点（xi,yi）的函数间隔之最小值，即 同理 最终问题转化成为求最大?值。（ps:我的理 解 在找到几何间隔?后，就要使H1和H2尽可能 的离H远，这样分类就更有说服力） 在H1和H2上的点就叫做支持向量 H1和H2之间的距离称为间隔，间隔依赖于法向量w,等于2/||w||,H1和H2称为间隔边界 由等式（1），可将问题写为 求最大的? 由于函数间隔?不影响最优化问题的解，这样可以取?=1，由于最大化1/||w||和最小化 1/2* ||w||* ||w||问题是等价的 于是问题便转化成了求 很容易看出当||w||=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带 解决方法：加一个约束条件 求最大的? 我们把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，于是不难得到有不等式：yi[w,xi+b]≥1 (i=1,2,…,l)总成立。 于是上面的问题便转化成了求条件最优化问题： 约束条件 这是一个凸二次规划问题，所以一定会存在全局的最优解，但实际求解较为麻烦。 实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的问题。 （2）