SVM理解..docx

1. SVM是要解决什么问题？之前，冲上来就看SVM的应用，简介，最优化计算方法等。从没认真想过SVM要解决什么问题。下面一幅是常用的图，来解释SVM的需求。SVM最基本的应用是分类。求解最优的分类面，然后用于分类。最优分类面的定义：?对于SVM，存在一个分类面，两个点集到此平面的最小距离最大，两个点集中的边缘点到此平面的距离最大。从直观上来看，下图左边的，肯定不是最优分类面；而右边的能让人感觉到其距离更大，使用的支撑点更多，至少使用了三个分类面，应该是最优分类面。那么，是不是一个最优分类面需要两个或三个以上的点才能确定那？这个要依据实际情况而定。如下图，左图是由三个点，来确定的一个最优分类面，不同类别的两个点确定一个中心点，而同类的两个点可以确定方向向量。这个最优分类面，需要三个点。但对于右图，直接获取不同类别的两个点的垂面，即是最优分类面。这个分类面，则需要两个点。以上，情况的分析，使得求解最优分类面的思路，模式比较复杂。若采用穷举法，至少需要以下过程。先取不同类别的两个点，求解中心连线的垂面。如以上右图模式然后判断其他点到此垂面的距离，若有更小的距离（或负值，即分类错误），则选取以上左图模式。穷举所有点。采用最直接的方式处理，则其运算复杂度为 m*n*n，若n m.这个还没有用到高维映射哪，如果再加上高维映射的处理，算法恐怕就更复杂了。所以，穷举法是不太现实的。2. 从直观到数学推论由直观到拟合：直观上，存在一个最优的超平面。那么，我们就假设这个最优面的公式是：W * X + b = 0，那么对于所有的点集x，都存在平行于最优超平面，的点集的边界面W * xi + b = 1 或 W * xi + b = -1, 这里yi可以归一化为1，-1最大化这两个平行超平面的距离。即max ?2 / ||w||或者说是最小化w，即 min ||w||另外一个条件是?W * xi + b = 1 或 W * xi + b = -1。这个有点超出平时用的计算方法了（如果没学过最优化理论），因既有求极值，又有不等式存在。这个是典型的QP（quandratic programming）二次规划问题。高数里面有有关求极值的理论，采用的是拉格朗日乘子法，但其条件是等式。所以，需要将不等式，转化为等式的形式。方法就引入变量。给每个点配上一个系数α，若是边界点，那么α就为大于0，否则就为0.则?αi * yi * (W * xi + b) = 0.从另一方面来讲，αi也可以看做是拉格朗日系数，采用拉格朗日乘子法，求极值。由于αi也是未知的。所以，又需要求出αi。即 min ( max?L?)， max?L?是因为后面的超平面公式经过减号后变成了 = 形式，其求和的最大值为0。先对min求极值, 对w，和b进行微分。推导出以下关系（blog没公式编辑器，想偷懒只要剪贴了）终于推出简单点的公式了。由min 到 max 也是一个对偶转换的过程，又称dual求max极值，并且，只有一个等式约束条件，缺点就是未知变量也增加了。接下来，就是用最优化的方法，求取极值了。对未知变量，取一个初始值，然后用点集中的点，一个接一个的进行训练。直至未知变量收敛。3. SMO 解法SVM 从简单边界分类思路，到复杂的拉格朗日求解。其实，对于二次规划问题，有经典的最速下降法，牛顿法等最优化求解方法。而SMO是一个SVM的优化算法，避开了经典的二次规划问题。消除w，转换为?αi的求解。这是一个更加有效的求解方法利用KKT条件，再加上一堆的推论，终于有以下公式：还是这么多公式和术语，真是令我头疼。只能先记着，后面慢慢消化。原理理解：?αi *??αj ?* ... 其实仍然是一个多元规划问题，所以，先多做几个假设：1. 假设除?α1 之外，其他都是定值，那么据∑ni=1αiyi=0，??α1可以直接定下来，就无法进行优化了。2. 若有?α1，??α2是变量，其他是常量，?α2可以由?α1来表示，代入到目标函数中，就形成了一个一元二次函数。这样就能轻易地求极值了。其中，还是要考虑约束条件的：αiαi0 = ai = C. 总之，求极值是方便可行多了。采用此方法，选取不同的?αi,??αj求极值。然后选取最大的。SMO就是采用这种原理，只不过它不是依次或随机选取?α，而是采用启发式算法选取最优的两个维度。?John C. Platt 的那篇论文 Fast Training of Support Vector Machines Using Sequential Minimal Optimization，有原理，有伪代码可以参考。/?page_id=683介绍的也是比较深入浅出的。3. SVM种类有哪些，适用场景及优缺点SVM的空间复杂度：SVM 是所占内存，是样本数据量的平方。《A