从零开始SVM算法(2)-SVM方程推导
上一章我们介绍了SVM算法的意义，SVM是large-margin算法，旨在找到一条能够完全区分训练集而且拥有最大margin值的直线。在这一章节里，我们将推导margin的计算方式和SVM最终要解决的问题的方程表达式。
任意点到决策边界距离（1） － 初步表达式
上章节我们提到，margin值就是所有数据点到决策边界的距离里面的最小值，所以首先我们要计算平面内任意一点到决策边界的距离。为了使得表述和理解更简单，在下面的所有推导中，我们都采用二维平面内的数据作为例子去做解释。二维平面得到的结论可以推广到任意维度的空间当中。
上图是一个在上一章节用过的二维数据集例子。在图中，红色的数据点是需要计算到决策边界距离的点，我们标注其为X。X1为决策边界上的点。注意，这里的X1跟坐标轴上的x1不一样，这里的X1是一个点，也是一个拥有两个维度的向量。坐标轴上的x1是两个维度对应的值的大小，是标量。图中的distance是我们需要计算的距离，该线段与决策边界垂直且与点X相交。
现在，假定图中的决策边界是由特征权重向量W和偏差值b决定的，既对于任意数据点，h(X) = sign(WTX + b)，该分类器是一个线性分类器(linear classifier)。对于任意数据X，当WTX + b > 0的时候预测该点为正类，当WTX + b < 0的时候预测该点为负类。当WTX + b = 0的时候，该点正好落在决策边缘上，此时分类器将其预测为正类来打破平衡(tie-break)。因此，我们很容易得到决策边界的方程为WTX + b = 0。
为了计算点X到决策边界的距离，我们做了一条辅助线，这条辅助线穿过点X和决策边界上的一点X1。根据高中几何知识我们知道X到决策边缘的距离D，是向量X X1长度在垂直于决策边界方向上的投影，既Distance = ||X - X1||cos(a)，a为向量XX1与垂直于决策边界方向的夹角。
此时，要计算Distance大小我们有两个方法，第一个方法是计算角度a以及||X - X1||的大小，第二个方法是找到一个垂直于决策边界的向量，假设是P。则距离
对于以上的公式推导，我们将会在下面演示。
根据经验而言，求法向量P往往比求角度a要简单一些，所以我们在这里采用第二种方法。由于我们最终需要用权重向量W和偏差b来表示距离大小，所以上面公式的是距离的初步表达式，我们还需要进行进一步推算。
任意点到决策边界距离（2） － 初步表达式的证明
刚刚我们提到了第二种计算距离的方法，并给出了计算公式，现在我们要证明计算公式的正确性。
首先根据向量相乘公式我们知道，两个向量相乘等于向量长度的乘积再与向量夹角余弦值的乘积。既
上面的式子说的是向量P和向量||X - X1||的乘积，因为P是垂直于决策边界，所以P与X - X1向量的夹角就是第一个坐标图中的角a。之前我们提到过，所求距离Distance = ||X - X1|| cos(a)。因此根据上面的得到的公式我们可以推出：
任意点到决策边界距离（3） － 找到跟决策边界垂直的向量P
在前面我们介绍并推导了任意点到决策边界距离的初步表达式。现在，我们要找到公式当中的向量P，一个垂直于决策边界的向量。
现在我们再定义另一个落在决策边界上的点X2。
X1和X2都落在决策边界上，因此对于点X1和X2，满足决策边界方程
我们把方程组中的上下两式相减得到 WT (X1 - X2) = 0。向量相乘等于零说明向量方向互相垂直。因此我们可以得到WT ⊥ (X1 - X2)。由于X1和X2都落在决策边界上，所以，(X1 - X2)的方向就是决策边界的方向。因此WT就是我们要找的垂直于决策边界的向量P。
任意点到决策边界距离（4）－ 最终表达式
上面我们得到了垂直于决策边界的向量 WT，现在我们把WT代入到前面的得到的距离初步表达式当中，
我们把WT放到后面的括号里面：
因为X1是决策边界上的一点，所以有
把上式代入Distance公式当中得到
为了让式子看着更简单，我们把||WT||换成||W||，因为
W的长度与其转置的长度一样。
这个距离公式还存在一个问题，就是WTX + b的值有可能为负，这样算出来的距离就会为负值，这不符合我们常规当中对距离大小的认识，我们常识当中总认为距离是非负的。因此我们在WTX + b外面加上一个绝对值符号，确保其非负。下面就是任意点X到决策边界的距离最终表达式：
Margin表达式的推导
前面我们推导了任意点到决策平面的距离表达式，下面我们要把问题回归到SVM，推导Margin值的表达式。
在上一章节我们提到，SVM的前提是要把训练集无错误地分开，也就是说，对于所有训练数据X, WTX + b 于这个点的分类值yn必须是同号，即yn (WTX + b) > 0。
因为yn只有两个值，+1和-1, 我们可以把距离公式当中的绝对值符号去掉，但是要添加一个条件：
s.t. 后面的是等式成立的条件，这也是SVM的前提。
我们已经知道，Margin值就是所有点Distance的最小值，因此我们得到Margin的表达式：
Margin表达式的简化
上面我们得到了Margin的表达式，然而要得到上面表达式的最大值仍然有点复杂，不便于计算，因此我们还需要对表达式进行进一步的简化，以方便计算。
通过观察上面的表达式，我们可以把1 / ||W||提到min函数的前面去，因为1 / ||W||跟n并无关系，margin公式转换成了：
现在再次观察新的margin表达式，容易看出我们或许可以尝试对公式当中min后面的式子进行简化。假若我们能够把后面的min值简化成一个常数，甚至让后面的min值简化成1，那么margin表达式就会剩下一个 1 / ||W||，计算量将会大大减少。
事实上，我们确实可以把表达式当中的min值简化成1。在说明白这个道理之前，先看一个例子。
对于平面内任意决策边界，WTX + b ＝ 0。现在让其W和b同时放大三倍，既 3WTX + 3b ＝ 0。可以很容易知道，放大三倍之后的决策边界跟放大之前的决策边界是同一条边界，因此我们可以知道，对W和b同时进行缩放，不会影响决策边界的位置。
现在我们回到刚刚的margin表达式，我们可以对决策边界参数做一个特殊的缩放，假设缩放倍数为n，使得其永远满足以下条件：
刚刚提到，对决策边界参数同时做相同倍数的缩放不影响决策边界的位置，因此，WTX + b ＝ 0 与 nWTX + nb ＝ 0是同一条直线。所以可以得到相同的结论：
因此我们可以对margin表达式再次简化为：
注意，s.t.条件当中原来有的 yn (WTX + b) > 0 这个条件在这里我们省略不写，原因是只要满足了yn (WTX + b)的最小值为1的话，必然满足原来大于0的条件，所以为了简化，我们省略原来的条件不写。
把最小化条件放松
上面我们得到了简化的margin表达式及其成立条件，表达式只是剩下一个1 / ||W||，已经足够简单。然而，在让表达式简单的同时，我们却把s.t.后面的条件变得更复杂了：
原来的条件是一个不等式，现在变成了一个最小化问题，问题变得更加复杂了，所以现在我们要做的就是把最小化条件放松，使条件再次变成一个不等式。关于为什么不等式条件会比最小化条件容易解决，我们会在以后的章节有所解释。现在我们暂且认同这一点。
现在我们尝试把原来的最小化条件放松成以下条件：
这个条件是原来最小化条件的必要条件，即满足原来条件，必定满足新的条件，即若满足yn (WTX + b)的最小值为1必定满足对于所有的n，yn (WTX + b) >= 1。
但是对于新条件是否是原来条件的充分条件，我们还需证明。
现在用反证法证明新条件是旧条件的充分条件
假设一个最大的margin值对应的最优解为(W, b)，假设这个最优解满足 ：
此时这个最优解满足新的不等式条件，但是不满足旧的最小化条件。
此时可以把不等式两边同时除以1.1，使其与原来的不等式条件一致：
这时的最优解就变成了(W / 1.1, b / 1.1)。
把新的参数代入margin：
我们发现，当W变成W / 1.1的时候，||W||的值会变小，margin的值就会更大，解比原来的W更优。因此这与原来假设的(W, b)是最优解相互矛盾。
所以，我们可以下结论，当(W, b)为最优解时，最小化条件和不等式条件是互为充要条件，可以作出最小化条件放松的操作。
现在，我们得到了更简单的margin计算方程，这里把最小化条件去掉了：
margin最大化问题
上面我们得到了margin的计算表达式，现在可以得到我们需要优化的模型：
总结
在这一章节里，主要讲解了如何计算平面内任意一点到决策边界的距离，之后还推导了margin最大化问题的模型。在后面的章节里，将会继续介绍如何解决这一章得到的最大化问题，从而得到最优解。
引用
本章节某些内容引用了台湾大学林轩田老师Standard_Large-Margin_Problem一章节课件内容
