原文：
http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982684.html http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988415.html http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
- 1 简介
- 2 重新审视logistic回归
- 3 形式化表示
- 4 函数间隔（functional margin）和几何间隔（geometric margin）
- 5 最优间隔分类器（optimal margin classifier）
- 6 拉格朗日对偶（Larrange duality）
- 7 最优间隔分类器（optional margin classifier）
- 8 核函数
- 9 核函数有效性判定
- 10 规则化和不可分情况处理（Regularization and the non-separable case）
- 11 坐标上升法
- 12 SMO优化算法（Sequential minimal optimization）
- 13 SMO中拉格朗日乘子的启发式选择方法
- 14 总结
1 简介
支持向量机基本上是最好的有监督学习算法了。从logistic回归出发，引出了SVM，既揭示了模型间的联系，也让人觉得过渡更自然。
2 重新审视logistic回归
Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。
结论：我们更应该关心靠近中间分割线的点，让他们尽可能地远离中间线，而不是在所有点上达到最优。因为那样的话，要使得一部分点靠近中间线来换取另外一部分点更加远离中间线。
支持向量机的思路和logistic回归的不同点，一个考虑局部（不关心已经确定远离的点），一个考虑全局（已经远离的点可能通过调整中间线使其能够更加远离）。
3 形式化表示
4 函数间隔（functional margin）和几何间隔（geometric margin）
函数间隔代表了我们认为特征是正例还是反例的确信度。
函数间隔归一化结果就是几何间隔。
5 最优间隔分类器（optimal margin classifier）
目标：寻找一个超平面，使得离超平面比较近的点能有更大的间距。
我们不考虑所有的点都必须远离超平面，我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。
6 拉格朗日对偶（Larrange duality）
KKT的总体思想是将极值会在可行域边界上取得，也就是不等式为0或等式约束里取得，而最优下降方向一般是这些等式的线性组合，其中每个元素要么是不等式为0的约束，要么是等式约束。对于在可行域边界内的点，对最优解不起作用，因此前面的系数为0。
7 最优间隔分类器（optional margin classifier）
只需求新来的样本和支持向量的内积，然后运算即可。
8 核函数
如果原始特征内积是<x, z>，映射后为<f(x), f(z)>，那么定义核函数（Kernel）为K(x, z) = f(x)Tf(z)。
高斯核函数：如果x和z很相近，那么核函数值为1，如果x和z相差很大，那么核函数约为0。函数类似于高斯分布，也叫径向基函数（Radial Basis Function，简称RBF）。它能够把原始特征映射到无穷维。高斯核函数能够比较x和z的相似度，并映射到0到1.
9 核函数有效性判定
核函数的充分必要条件：
K是有效的和函数 <==> 核函数矩阵K是对称半正定的。
10 规则化和不可分情况处理（Regularization and the non-separable case）
我们之前讨论的情况都是建立在样例线性可分的假设上，当样例线性不可分时，我们可以尝试使用核函数来将特征映射到高维，这样很可能就可分了。然而，映射后我们也不能100%保证可分。那怎么办呢，我们需要将模型进行调整，以保证在不可分的情况下，也能够尽可能地找出分隔超平面。
一个离群点（可能是噪声）可以造成超平面的移动，间隔缩小，可见以前的模型对噪声非常敏感。再有甚者，如果离群点在另外一个类中，那么这时候就是线性不可分了。
这时候我们应该允许一些点游离并在在模型中违背限制条件（函数间隔大于1）。
我们需要重新调整目标函数，以对离群点进行处罚，离群点越多，目标函数值越大，而我们要求的是尽可能小的目标函数值。这里的C是离群点的权重，C越大表明离群点对目标函数影响越大，也就是越不希望看到离群点。我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。
11 坐标上升法
回归中几种求最优解的方法：
- 梯度下降法
- 牛顿法
- 坐标上升法
12 SMO优化算法（Sequential minimal optimization）
SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。
SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效。
13 SMO中拉格朗日乘子的启发式选择方法
14 总结
SVM的思想：在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。
在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。