机器学习（九）：CS229ML课程笔记（5）——支持向量机（SVM），最优间隔分类，拉格朗日对偶性，坐标上升法，SMO
Part 5：Support Vector Machines SVM
这一节将描述的是支持向量机学习算法，是一种非线性分类方法（non-linear classifiers）。
要学习SVM，首先我们要认识一下“margins”和 the idea of separating data with a large“gap.”之后还需要了解 “optimal margin classifier”最优间隔分类器，和能够使SVM有效的应用高维度特征空间的"kernels"，最后我们会学习能高效完成SVM的SMO算法。现在看不懂上面的描述没有关系，看到最后你就懂了。
5.1 对边界的感性认识Margins: Intuition
5.1.1逻辑回归回顾
同时可以看到当z在0附近时，输出概率在0.5附件徘徊，而且比较敏感，但是当z=θTx>>0时它的输出很接近1，当z=θTx<<0时它的输出很接近0。所以如果我们能够让z>>0或者z<<0，我们就会更加确信这个样本被正确分类了。
5.1.2 用简单的线性分类器模型构造更加复杂的非线性分类器
之前介绍的感知器算法，GDA,NB（NB的前置假设是多项式分布模型，也算是逻辑回归模型的一种），最终结果会得到一个直线或者一个超平面，但是数据如果不是线性可分，模型的性能就会很差，所以以上都是属于线性分类器。在这一部分我们要用简单的线性分类器模型构造复杂的非线性分类器。
以逻辑回归为例，他可以表示 成为下图：
其中sigmoid圆圈是计算节点，有参数θ。函数长这样的还记得不：
而神经网络就是将这样的计算单元组合起来：
其中a1-a3都是中间单元输出。上面的这个神经网络有3个中间单元，每个中间单元都有自己独立的参数。所以：
这时的代价函数（cost function）：
然后在用梯度下架方法最小化代价函数求得参数，在神经网络中的梯度下降的专业名称叫做反向传播算法（back propagation）。在上图中与输入直接相连的称为隐藏层（hidden layer），与输出直接相连的叫做输出层（output layer）。神经网络的特点在于不知道隐藏层计算东西的含义，另外一个特点是有较多的局部最优值，不像逻辑回归，神经网络总是会对非凸优化问题作出响应，所以用梯度下降或者牛顿法不会像逻辑回归那样直接得到全局最优，因为他有太多的局部最优。可以通过多次随机设定初始值求解最优。
5.1.3 泛泛的了解：
我们看下面这张图，其中“x”表示“ positive training examples,y=1”，“o”表示“negative training examples,y=0”，下图还有一条直线将两类分开，被叫做“decision boundary”，也被叫做“separating hyperplane”，其中的A点是离这个决策边界较远，所以我们可以很确定的认为y（A）=1。对于C点，离边界较近，可能对决策边界一个小小的改变就能使y（c）=0。因此我们对A预测正确的自信度大于C预测。我们稍后会再次提到这些。以下的讲解是先从线性可分的样本数据入手。
5.2 对符号的简单入门notation：
为了容易理解后面对SVM的讨论，我们引入一种新的符号表示。现在我们讨论的是用标签y（）和特征x表示的线性二分类问题。这次我们不在用vector θ，而是选择的w和b：
此时的b相当于以前的，w相当于以前的
。
也就是：
还要注意的是，根据我们对g的定义，我们的分类器会直接预测0或1（比如感知器算法），而不需要先通过中间步骤来估计y为1的概率（比如逻辑回归，y的取值在0-1之间）。
5.3 函数间隔（Functional margins）
函数间隔的作用有两个：一个是确认样本点有没有被正确分类，另一个是衡量该样本点被正确分类的确信度。
（函数距离是定义的，表示一个由w和b确定的超平面和训练样本对应的函数距离）
5.4 几何间隔（Geometric margins）
我们希望间隔函数很大，也就是即所有样本中最小的函数距离很大。但是前面提到，我们可以成比例地增大w与b，使得距离函数变得无限大。但这没有意义，因为超平面的位置并没有发生改变。
这时候就轮到几何间隔出场了，它是增加了约束的函数间隔，使函数间隔变得唯一，用符号γ表示。
直观上来看几何间隔是样本点到超平面的距离。
此时改变几何间隔就能够移动超平面，同时几何间隔仍然能反映样本被正确分类的确信度，所以对几何间隔的最大化，就是对超平面的最优化。
w的方向垂直于决策边界。
理解①：直线的法向量的单位向量是w/||w||.
理解②：
所以最大间隔分类（max margin classifier）就是去max（r），分类最正确，置信度最高：
。
5.5 最优间隔分类器（The optimal margin classifier）
假设我们现在存在一个线性可分的训练集，也就是可以用一个分离超平面separating hyperplane把它分成两类，那么我们怎么样才能找到最大的几何间隔？
首先，我们需要解决的最优化问题是：
我们想要最大化γ，在每个训练集的函数间隔（functional margin）不小于γ的条件下。||w||=1的限制是为了保证函数间隔和几何间隔相等，所以我们可以同时保证几何间隔（geometric）也不小于γ。但是这个限制是非凸的，不利于优化求解，所以我们进行了转化：
所以下一步就要最大化几何间隔，在每个训练集的函数间隔都不小于
的限制下。因为
，所以目前就不需要
这个限制了。
最终变成凸优化问题，它的解w,b构成我们所需的最优分离超平面，这种求解方法被叫做最优间隔分类器 （the optimal margin classifier）。这个最优化问题可以使用商业二次编程代码来解决（commercial quadratic programming (QP) code）。但在下面我们要寻求一种更好的方法来解决这种问题。
5.6 拉格朗日对偶性（Lagrange duality）
我们暂时先抛开SVM和最优间隔分类器，目前先讨论一下解决约束最优化问题（constrained optimization problems）。
有一些求解类似下面的公式：
也就是求w使f（w）最小化，约束条件是h（w）=0.（其实拉格朗日乘子（Lagrange multipliers）可以很好的解决的这个问题，如果没听过，继续往下看就好）
在这里，我们先定义拉格朗日函数为：
此时的βi 就被叫做拉格朗日乘子（Lagrange multipliers）。
我们现在让L的偏导数为0，解出w和β:
上面涉及到的是等式约束条件（equality constraints），下面来看看非等式约束（inequality constraints）的例子。
example：原始优化问题（primal optimization problem）：
首先我们定义一个广义拉格朗日函数：
这里的αi和βi是拉格朗日乘子。
我们现在定义：
这里的下标表示的是“primal”。如果w给定，而且不满足原始约束条件（primal constraint），比如对于某些i使
，则：
也就是当w不满足原本的约束条件，总会找到一个情况使θp为正无穷的大。相反的，若w满足所有的约束条件：
综合来说，即：
如果我们把问题看成最小化问题：
（1）
目标函数的最优值为：
我们把上面的叫做原始问题的价值（ the value of the primal problem.）
example：对偶优化问题（dual optimization problem）：
下面再看一个有点点不同的问题，我们定义：
其中下标表示的是“dual”，值得注意的是，在解决原始优化问题即优化
时是关于α和β的优化，在这里解决对偶优化问题即最小化L是关于w的优化。
定义对偶优化问题为：
发现这和上面的（1）公式很相近，我们在这里也定义目标函数的最优值为：
易证：
到这里我们可以看到原始优化问题和对偶优化问题的相通性。
（如果f函数有Hessian矩阵，当且仅当hessian矩阵是半正定的（positive semidefinite），则f是凸函数。比如就是凸函数，相似的，所有的线性和仿射函数也是convex的。一个凸函数也可以是不可微的
affine仿射和线性一样，但是仿射允许截距b 的存在）
为了让d*=p*，即可以通过求对偶问题来解决原始优化问题，需要满足以下假设：
假设f函数和gi函数是凸函数（convex）而hi函数是仿射affine的，进一步假设对于存在一些w使所有的i。
在以上假设的前提下则必然存在使
是the primal problem的解，
是 the dual problem的解，而且
。另外
就满足Karush-Kuhn-Tucker (KKT) conditions：
其中αi*gi(w)=0被称为KKT dual complementarity condition。它暗示了只有当gi(w)=0时才有可能有αi>0，这是SVM只有很少数support vectors的原因；在之后的SMO算法的收敛验证中也会用到这个条件。
5.7 最优间隔分类Optimal margin classifiers
我们再次回到最优间隔分类：
我们把约束条件换一种写法：
在上一部分我们提到了KKT dual complementarity condition，只有当ai>0的时候gi才=0，此时函数间隔functional margin为1，我们看下面这张图：
上图中的实线就是最大间隔分离超平面（maximum margin separating hyperplane），此时满足gi(w)=0对应着距离分隔超平面最近的点（回顾推导最大间隔分类器最优化公式的过程），即上图中虚线穿过的三个点。这三个点被叫做支持向量support vectors。而且支持向量的数量相对于整个训练集的数量越小效果会越好。
将目前的最优化问题构造为拉格朗日的形式： （1）
在式子（1）中只有α没有β，这里只存在非等式约束（inequality constraints）。
接下来求解对偶问题，通过使偏导数为0，求在固定α，不固定w与b的条件下求最小化的L(w, b, α)，即θD：
将（2）与（3）带入（1）中，可得：
最终，SVM对应的最优化问题为：
我们可以通过解求问题最大化的的方法求解出α，我们将α带入公式（2）就可解出w，然后再根据之前解求原始问题的方法求b：
所以最终的解为：
（4）
在次看看这张图
式（4）中，−表示，过分类为-1的支持向量的超平面的截距，对应图中过圈圈的下面那条虚线的截距；−
表示，过分类为1的支持向量的超平面的截距，对应图中过叉叉的上面那条虚线的截距。
实线即超平面的截距是这两个截距的和的一半。
也可以直接用α求得模型的线性组合结果（消除w）：
（5）
内积（inner product）：也就是
。
那么问题来了，为什么我们要这么“折腾”地用拉格朗日对偶性把原本清晰的最大间隔分类的优化问题转化成SVM的内积的形式？其中一个很大原因就是接下来要说的核函数。
5.8 Kernels
5.8.1核函数感性认识：
核函数的作用：把原坐标系里线性不可分的数据投影到另一个空间，尽量使得数据在新的空间里线性可分。
低维空间（这里是二维）里有红色与蓝色两种不同的分类点，可以看到在这里它们线性不可分：
5.8.2 核函数的理性认识：
输入属性（input attributes）:原始的输入值，比如之前线性回归里面的x房屋面积；
输入特征（input features）：被映射的变量，之后会传递到学习算法中。
我们现在用φ表示特征映射（feature mapping），也就是把属性映射为特征。有时我们希望将低维的向量特征映射到高维以增加分类的准确性，比如添加二次、三次项到模型中：
可以将之前算法的所有x替换成上面的φ（x）以相同的算法求解。
将数据映射到高维空间，在高维空间中去寻找线性超平面的这个方式固然好，但是却引来了新的问题。
ϕ(x)ϕ(x)是映射后的数据，一般比原数据更高维，而真正使用的时候，还是在计算它的内积ϕ(x)Tϕ(z)ϕ(x)Tϕ(z)，这样的计算代价太高昂了。
核函数的一个巧妙之处在于，可以通过计算低维向量内积的平方，得到高维向量的内积。
因为算法可以被完全地表达为特征向量内积的形式<x, z>，所以只要将映射后的内积<Φ(x), Φ(z)>替换掉原本的内积即可。给定一个特征映射规则Φ，我们将kernel定义为：
现在，当给定φ，我们能够很容易的根据φ（x）和φ（z）来计算内积K（x，z）。即使在φ（x）自身的计算量很大的时候我们发现K（x，z）的计算量不大。当输入空间的维度非常高时（甚至是无限维度），我们可以核函数来大大缩减计算量。
example 1 ：
假设，
此时的φ（这是在n=3的情况下）：
由此我们可以看到计算<Φ(x), Φ(z)>需要O(n2)的时长，而直接计算K(x,z)只需要O(n)的时长，当维度极高时，这个优势将极为明显。
具体事例：
example 2 ：一个类似的kernels：
此时的φ（在n=3的情况下）：
参数c控制xi（一级）和xixj（二阶）项之间的相对权重。（the parameter c controls the relative weighting between the xi (first order) and the xixj (second order) terms.）
还有它的一般形式：。
该函数对应的映射函数φ（x）为一个大小的向量。向量中的每个元素为最高d阶的变量的组合。
如果直接计算φ内积的结果的复杂度是，但是如果直接计算核函数的复杂度是
，所以在高维度的时候为了减少计算量，可以直接用核函数而不用直观的用映射函数φ。
example 3： Gaussian kernel
下面说说对核的另外一个意义。如果φ（x）和φ（z）离得很近，则会很大，如果它们离得很远，比如接近正交直线，则
会很小，所以我们也可以把核函数当做评判φ（x）和φ（z）的相似程度，也是x和z 的相似程度。
我们再看另外一个很函数：
这也是评估x和z相似度的可行方法。当x，z很相似核函数会接近1，反之会接近0。这个核函数被叫做高斯核函数，它能将原始特征映射到无穷维度。
核函数的有效性：
5.9 软间隔分类器：正则化和不可分离的情况（Regularization and the non-separable case）
迄今为止所提出的SVM的推导假定数据是线性可分类似下图（1）。
（1） （2）
虽然通过一般的方式将数据映射到高维的特征空间会增加数据可分离的可能性，但我们不能保证它总是这样的。在某些情况下，我们不能确定找到的超平面是否正是我们想要的，因为它可能会受到异常值的影响。比如上图（2）当一个单独的异常值出现，它会导致决策边界产生一个戏剧性的摆动，而且使产生的分类器的几何间隔要小很多。
为了使我们的算法适用于非线性可分数据集而且对异常值不敏感，我们允许某些数据点拥有比1小的几何间隔，当ξ>1时，即可允许分类是错误的，然后我们将ξ作为惩罚添加到目标函数中。同时加入一个预设的惩罚系数C，就得到了下面的软间隔分类器：
然后引入拉格朗日乘子α和r（它们的限制是≥1）：
进行对偶问题的第一步求解，即minL(w,b,α)，同样地，我们分别对w,b,ξi求偏导，令其偏导数结果为0之后，再把它们代回上式，简化形式。这里不进行具体求解，最后得到：
到目前为止，我们根据上面的（2）即，可以用α来表示w，然后在用上面的（5）也就是
来进行我们的预测。在这里需要注意，在我们加了L1正则化，对于对偶问题位移的变化就是之前的限制条件变成了
，ξi已经不见了踪影。还有
的计算方法和KKT条件也发生了改变，这里不做详述。
KKT dual-complementarity conditions将变为：
5.10 SMO (sequential minimal optimization)算法：
5.10.1 坐标上升法（Coordinate ascent）:
坐标上升法与SMO算法的思想是一致的，但是更简单。
对于寻找函数最优值，除了梯度下降（上升），以及牛顿法之外，还有很多方法。下面介绍的坐标上升法也是其中的一种。
首先我们要解决的无约束优化问题是：
在这里我们把W当做一个关于参数α的函数。具体过程如下：
最内层循环的意思是固定除αi之外的所有αj(j≠i)，W只有一个αi的参数，直接对αi求导优化。这里我们进行最大化求导的顺序i是从1到m，可以更改优化顺序，使W能够更快地增加并收敛。它需要迭代的次数很多，但是每一次迭代的代价都很小，所以实际上它的速度还是比较快的。
我们来看看图解示范：
图中的椭圆表示我们想优化的二次函数的等高线。起始坐标是（2,-2），其核心思想是一次只在一个维度上使得函数最大化。
5.10.2 SMO(sequential minimal optimization)
我们目前要解决的对偶优化问题如下：
假设我们现在已经有了满足限制条件的αi，然后按照坐标上升法逐个选择一个α为变量求偏导优化，但是我们发现没有任何效果，因为第二个限制条件可以写成：
在进一步：因为，
，所以左右同时乘以
就可以得到：
αi相对于其他α不是独立的，如果其他α固定，αi一定固定，所以我们不能直接使用坐标上升法。
所以SMO算法是每次选择两个参数进行优化：
判断循环收敛的标准是检验某些tol是否满足KKT条件，tol是收敛容忍参数，一般在0.01-0.001之间。
循环过程：
假设我们已经有了满足限制条件的αi们，限制我们将α3至αm固定，也就是选择α1和α2为参数对w进行优化。根据之前的第二个限制条件 可以得到：
因为等式的右边是固定的，所以我们可以用个固定值来表示，也就是写成：
我们用图解表示上面的式子：
我们现在在看第一个限制条件，也就是α1和α2都在0-C之间，
我们可以用α2来表示α1（，
）;
我们可以得到：W是关于α2的一个二次函数。而二次函数求导获得最大值是很简单的，再考虑上边界的限制后，α2的新值为：
而α1的最优值可以由α2计算获得。
具体的求解过程和小结参照参考博客①最后。
5.11 最后的最后
引用①的小结：
参考博客：
①：https://blog.****.net/sinat_37965706/article/details/70666682
②：https://blog.****.net/poorfriend/article/details/51711425
③：https://blog.****.net/stdcoutzyx/article/details/9722701
④：https://blog.****.net/stdcoutzyx/article/details/9774135（和视频内容很吻合）
⑤：https://blog.****.net/stdcoutzyx/article/details/9798843