引言
接下里的一系列有关机器学习的博文，我将具体的介绍常用的算法，并且希望在这个过程中尽可能地结合实际应用更加深入的理解其精髓，希望所付出的努力能得到应有的回报。
接下来的有关机器学习基础博文主要根据机器学习技法课程的学习，围绕特征转换(feature transforms)这个主要工具，从以下三个方向进行探讨：
- 如果现在有很多特征转换可以使用的时候，我们该如何运用这些特征转换，如何控制特征转换中的复杂度的问题，从这个角度刺激了支持向量机(Support Vector Machine)算法的发展。
- 我们该如何将具有预测性质的特征混合起来，让整个模型拥有更好的表现，从这个角度衍生出逐步增强法(Adaptive Boosting,AdaBoost)模型。
- 我们该如何找出数据中的隐藏的特征，或者说机器如何从中学习出来，让机器表现地更好，从这个角度出发，刺激了之前的类神经网络成为近年来的深度学习领域。
这一小节，我们从线性的支持向量机开始，一点一点地延伸到更加复杂的模型。
最大间隔分离超平面(Large-Margin Separating Hyperplane)
就上图给出的分类问题而言，三个图中的分类平面都正确的把训练数据分成两类（训练误差为0），且线性分类模型的复杂度是维度加1(d+1)，那么我们该如何解释最右边图的分离平面要更优呢？
由于高斯噪声的存在，对于左面的图而言，如果在靠近分离平面的点的周围有与该点是同一类别的数据就很容易被判错，故这几幅图的区别在于，其分离平面对于测量误差的容忍度不同，相比较，右侧图对避免测量误差发生的健壮性更好。
所以，实际上，我们希望该分离平面距离训练数据越远越好。
重新叙述一下该问题，我们希望分离平面对数据的泛化能力更好，就希望所有点到线的间隔越大越好。所以我们的目标是，找到最大间隔的分离平面，这个平面要满足两个条件，一是该分离平面能正确分离两类数据(即yn=sign(wTxn)，yn与wTxn同号)，二是该分离间隔取所有点中离平面最近的数据。
标准最大间隔问题(Standard Large-Margin Problem)
上面，我们要求一个最大间隔分离平面，得到了一个待求解的最佳化问题。接下来，我们将要探讨一下在最佳化求解中点到平面的距离要如何计算。
1. Large-Margin Separating Hyperplane
2. Distance to Separating Hyperplane
我们定义向量w=(w1,...,wd)，向量x=(x1,...,xd)，截距b=w0。
我们现在考虑在平面的两个点x'和x"，它们都满足方程wTx'+b=0、wTx"+b=0。
x"-x'表示平面上的一个向量，在这个平面上w是该平面的法向量。
所以点到平面的距离是，该点到平面上任意一点构成的向量对该平面的法向量做投影所得到的距离。
由于我们考虑的分隔平面是将正负例数据都正确分开的平面，所以该公式还需要满足一些性质：
我们要求所计算的分数wTxn+b与yn是同号的，这样就可以将上面的距离公式中的绝对值符号去掉。
所以，我们的目标修正为下面的式子：
3. Margin of Special Separating Hyperplane
到现在，我们还是没法求解这个问题，所以还需要更进一步的简化。
我们观察到wTx+b=0，同时3wTx+3b=0，这种放缩还是表示同一个平面。我们就会想到这些系数似乎是可以放缩的。
对间隔的放缩对最优化问题不等式约束没有影响，对目标函数的优化也没有影响，所以这是一个等价的优化问题。
于是我们的线性可分支持向量机的最优化问题化简为：
4. Standard Large-Margin Hyperplane Problem
最后一步，我们希望找到更好求解的方式。
我们将min yn(wTxn+b)=1这个条件放宽松成yn(wTxn+b)>=1这个条件，且这个条件并没有影响最终的最佳解。
最大化1/||w||和最小化||w||^2/2是等价的，于是得到最终的最优化问题：
最佳化的求解
支持向量
从上图可以看出，我们可以找出距离分隔平面最近的点使得该点距离平面的距离最大，即使将其他不相干的数据点去掉，该结果依然成立。所以说，距离分隔平面最近的点已经唯一确定了这个平面，故这些点叫做支持向量(support vector)。
求解一般的SVM问题
我们回看要求解的最佳化问题，发现其满足两个特点：
- 目标函数是关于(b,w)的凸二次函数
- 不等式约束是关于(b,w)的一次式
这样特性的最佳化问题称作被约束的(凸)二次规划(convex quadratic programming)问题。
二次规划
上面我们将我们待解的问题和二次规划的标准形式作了对比，得到了我们的问题在标准形式中表示方式：
剩下的事情可以用可以解决二次规划的软件工具来求解了。
小结
下面给出了确定二次规划的系数，求解模型参数，并得到svm的模型gSVM的过程。
理论分析
SVM和正则化的解释
SVM和我们直接介绍的正则化是有相似的地方的，不同在于SVM将wTw作为最小化的目标函数，而将Ein=0作为约束条件。
所以SVM就是一种正则化的表现，我们希望有最大的间隔，其实就是希望最终的模型能够对测量误差有更好的健壮性。
从VC理论解释
这里我们不给出具体的证明，只是从定性的角度来解释。
如果我们要给最大的间隔加上一些限制（要求最大的间隔要大于某个常数），这可能使得将数据分开的情形种类减少了，这样使得VC维减小，这使得模型复杂度得到了有效的控制。
接下来
从上面的VC维解释可以得到一个简单的结论，就是SVM对间隔的限制可以有效减低VC维，控制复杂度，得到比较好的泛化能力；还有，如果我们能结合非线性变换，就可以得到复杂的边界。接下来，就会延伸到线性不可分的SVM，通过SVM控制复杂度的方法，更好的使用各式各样不同的特征转换。
转载请注明作者Jason Ding及其出处
Github博客主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)
百度搜索jasonding1354进入我的博客主页
