本文目录一览：
如何用python实现smo算法
在ml中常见的优化算法基本都是： sgd 这种对每个单变量进行同步更新 als(交替最小二乘）/smo(序列最小优化）这种交替（固定一个单变量，优化另一个单变量）思路。如果你熟悉smo，那么als就也可以理解了。 其它（希望更多的人补充）
如何利用 Python 实现 SVM 模型
我先直观地阐述我对SVM的理解，这其中不会涉及数学公式，然后给出Python代码。
SVM是一种二分类模型，处理的数据可以分为三类：
线性可分，通过硬间隔最大化，学习线性分类器
近似线性可分，通过软间隔最大化，学习线性分类器
线性不可分，通过核函数以及软间隔最大化，学习非线性分类器
线性分类器，在平面上对应直线；非线性分类器，在平面上对应曲线。
硬间隔对应于线性可分数据集，可以将所有样本正确分类，也正因为如此，受噪声样本影响很大，不推荐。
软间隔对应于通常情况下的数据集（近似线性可分或线性不可分），允许一些超平面附近的样本被错误分类，从而提升了泛化性能。
如下图：
实线是由硬间隔最大化得到的，预测能力显然不及由软间隔最大化得到的虚线。
对于线性不可分的数据集，如下图：
我们直观上觉得这时线性分类器，也就是直线，不能很好的分开红点和蓝点。
但是可以用一个介于红点与蓝点之间的类似圆的曲线将二者分开，如下图：
我们假设这个黄色的曲线就是圆，不妨设其方程为x^2+y^2=1，那么核函数是干什么的呢？
我们将x^2映射为X，y^2映射为Y，那么超平面变成了X+Y=1。
那么原空间的线性不可分问题，就变成了新空间的（近似）线性可分问题。
此时就可以运用处理（近似）线性可分问题的方法去解决线性不可分数据集的分类问题。
---------------------------------------------------------------------------------------------------------------------------
以上我用最简单的语言粗略地解释了SVM，没有用到任何数学知识。但是没有数学，就体会不到SVM的精髓。因此接下来我会用尽量简洁的语言叙述SVM的数学思想，如果没有看过SVM推导过程的朋友完全可以跳过下面这段。
对于求解（近似）线性可分问题：
由最大间隔法，得到凸二次规划问题，这类问题是有最优解的（理论上可以直接调用二次规划计算包，得出最优解）
我们得到以上凸优化问题的对偶问题，一是因为对偶问题更容易求解，二是引入核函数，推广到非线性问题。
求解对偶问题得到原始问题的解，进而确定分离超平面和分类决策函数。由于对偶问题里目标函数和分类决策函数只涉及实例与实例之间的内积，即xi,xj。我们引入核函数的概念。
拓展到求解线性不可分问题：
如之前的例子，对于线性不可分的数据集的任意两个实例：xi,xj。当我们取某个特定映射f之后，f(xi)与f(xj)在高维空间中线性可分，运用上述的求解（近似）线性可分问题的方法，我们看到目标函数和分类决策函数只涉及内积f(xi),f(xj)。由于高维空间中的内积计算非常复杂，我们可以引入核函数K(xi,xj)=f(xi),f(xj)，因此内积问题变成了求函数值问题。最有趣的是，我们根本不需要知道映射f。精彩！
我不准备在这里放推导过程，因为已经有很多非常好的学习资料，如果有兴趣，可以看：CS229 Lecture notes
最后就是SMO算法求解SVM问题，有兴趣的话直接看作者论文：Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines
我直接给出代码：SMO+SVM
在线性可分数据集上运行结果：
图中标出了支持向量这个非常完美，支持向量都在超平面附近。
在线性不可分数据集上运行结果（200个样本）：
核函数用了高斯核，取了不同的sigma
sigma=1，有189个支持向量，相当于用整个数据集进行分类。
sigma=10，有20个支持向量，边界曲线能较好的拟合数据集特点。
我们可以看到，当支持向量太少，可能会得到很差的决策边界。如果支持向量太多，就相当于每次都利用整个数据集进行分类，类似KNN。
如何用Python实现支持向量机
终于到SVM的实现部分了。那么神奇和有效的东西还得回归到实现才可以展示其强大的功力。SVM有效而且存在很高效的训练算法，这也是工业界非常青睐SVM的原因。
前面讲到，SVM的学习问题可以转化为下面的对偶问题：
需要满足的KKT条件：
也就是说找到一组αi可以满足上面的这些条件的就是该目标的一个最优解。所以我们的优化目标是找到一组最优的αi*。一旦求出这些αi*，就很容易计算出权重向量w*和b，并得到分隔超平面了。
这是个凸二次规划问题，它具有全局最优解，一般可以通过现有的工具来优化。但当训练样本非常多的时候，这些优化算法往往非常耗时低效，以致无法使用。从SVM提出到现在，也出现了很多优化训练的方法。其中，非常出名的一个是1982年由Microsoft Research的John C. Platt在论文《Sequential Minimal Optimization: A Fast Algorithm for TrainingSupport Vector Machines》中提出的Sequential Minimal Optimization序列最小化优化算法，简称SMO算法。SMO算法的思想很简单，它将大优化的问题分解成多个小优化的问题。这些小问题往往比较容易求解，并且对他们进行顺序求解的结果与将他们作为整体来求解的结果完全一致。在结果完全一致的同时，SMO的求解时间短很多。在深入SMO算法之前，我们先来了解下坐标下降这个算法，SMO其实基于这种简单的思想的。
8.1、坐标下降（上升）法
假设要求解下面的优化问题：
在这里，我们需要求解m个变量αi，一般来说是通过梯度下降（这里是求最大值，所以应该叫上升）等算法每一次迭代对所有m个变量αi也就是α向量进行一次性优化。通过误差每次迭代调整α向量中每个元素的值。而坐标上升法（坐标上升与坐标下降可以看做是一对，坐标上升是用来求解max最优化问题，坐标下降用于求min最优化问题）的思想是每次迭代只调整一个变量αi的值，其他变量的值在这次迭代中固定不变。
最里面语句的意思是固定除αi之外的所有αj(i不等于j)，这时W可看作只是关于αi的函数，那么直接对αi求导优化即可。这里我们进行最大化求导的顺序i是从1到m，可以通过更改优化顺序来使W能够更快地增加并收敛。如果W在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。
用个二维的例子来说明下坐标下降法：我们需要寻找f(x,y)=x2+xy+y2的最小值处的(x*, y*)，也就是下图的F*点的地方。
假设我们初始的点是A（图是函数投影到xoy平面的等高线图，颜色越深值越小），我们需要达到F*的地方。那最快的方法就是图中黄色线的路径，一次性就到达了，其实这个是牛顿优化法，但如果是高维的话，这个方法就不太高效了（因为需要求解矩阵的逆，这个不在这里讨论）。我们也可以按照红色所指示的路径来走。从A开始，先固定x，沿着y轴往让f(x, y)值减小的方向走到B点，然后固定y，沿着x轴往让f(x, y)值减小的方向走到C点，不断循环，直到到达F*。反正每次只要我们都往让f(x, y)值小的地方走就行了，这样脚踏实地，一步步走，每一步都使f(x, y)慢慢变小，总有一天，皇天不负有心人的。到达F*也是时间问题。到这里你可能会说，这红色线比黄色线贫富差距也太严重了吧。因为这里是二维的简单的情况嘛。如果是高维的情况，而且目标函数很复杂的话，再加上样本集很多，那么在梯度下降中，目标函数对所有αi求梯度或者在牛顿法中对矩阵求逆，都是很耗时的。这时候，如果W只对单个αi优化很快的时候，坐标下降法可能会更加高效。
8.2、SMO算法
SMO算法的思想和坐标下降法的思想差不多。唯一不同的是，SMO是一次迭代优化两个α而不是一个。为什么要优化两个呢？
我们回到这个优化问题。我们可以看到这个优化问题存在着一个约束，也就是
假设我们首先固定除α1以外的所有参数，然后在α1上求极值。但需要注意的是，因为如果固定α1以外的所有参数，由上面这个约束条件可以知道，α1将不再是变量（可以由其他值推出），因为问题中规定了：
因此，我们需要一次选取两个参数做优化，比如αi和αj，此时αi可以由αj和其他参数表示出来。这样回代入W中，W就只是关于αj的函数了，这时候就可以只对αj进行优化了。在这里就是对αj进行求导，令导数为0就可以解出这个时候最优的αj了。然后也可以得到αi。这就是一次的迭代过程，一次迭代只调整两个拉格朗日乘子αi和αj。SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效（对一个参数的优化可以通过解析求解，而不是迭代。虽然对一个参数的一次最小优化不可能保证其结果就是所优化的拉格朗日乘子的最终结果，但会使目标函数向极小值迈进一步，这样对所有的乘子做最小优化，直到所有满足KKT条件时，目标函数达到最小）。
总结下来是：
重复下面过程直到收敛{
（1）选择两个拉格朗日乘子αi和αj；
（2）固定其他拉格朗日乘子αk(k不等于i和j)，只对αi和αj优化w(α);
（3）根据优化后的αi和αj，更新截距b的值；
}
支持向量机—从推导到python手写
笔者比较懒能截图的地方都截图了。
支持向量机分为三类：
（1）线性可分支持向量机，样本线性可分，可通过硬间隔最大化训练一个分类器。
（2）线性支持向量机，样本基本线性可分，可通过软间隔最大化训练一个分类器。
（3）非线性支持向量机，样本线性不可分，可通过核函数和软间隔最大化训练一个分类器。
上面最不好理解的恐怕就是硬间隔和软间隔了，
说白了硬间隔就是说存在这么一个平面，可以把样本完全正确无误的分开，当然这是一种极理想的情况，现实中不存在，所以就有了软间隔。
软间隔说的是，不存在一个平面可以把样本完全正确无误的分开，因此呢允许一些样本被分错，怎么做呢就是加入松弛变量，因为希望分错的样本越小越好，因此松弛变量也有约束条件。加入松弛变量后，问题就变为线性可分了，因为是每一个样本都线性可分，因此松弛变量是针对样本的，每一个样本都对应一个不同的松弛变量。
其实感知机说白了就是找到一条直线把样本点分开，就是上方都是一类，下方是另一类。当然完全分开是好事，往往是不能完全分开的，因此就存在一个损失函数，就是误分类点到这个平面的距离最短：
这里啰嗦一句，误分类点y*(wx+b)0，所以加个负号在前边。
一般情况下||w||都是可以缩放，那么我们把它缩放到1，最后的目标函数就变成了
间隔就是距离，我们假设分离超平面为 ，那么样本点到这个平面的距离可以记为 。我们都知道通过感知机划分的点，超平面上方的点 ，下方的点 ，然后通过判断 的值与y的符号是否一致来判断分类是否正确。根据这个思路函数间隔定义为：
支持向量的定义来源于几何间隔，几何间隔最直接的解释是离分隔超平面最近点的距离，其他任何点到平面的距离都大于这个值，所以几何间隔就是支持向量。然后呢同样道理，w和b是可以缩放的，所以定义支持向量满足如下条件：
再通俗一点说，支持向量是一些点，这些点到分隔平面的距离最近，为了便于表示，把他们进行一下缩放计算，让他们满足了wx+b=+-1.
核函数是支持向量机的核心概念之一，它存在的目的就是将维度转换之后的计算简化，达到减少计算量的目的。我们都知道支持向量机求的是间距最大化，通常情况下我们求得的alpha都等于0，因此支持向量决定了间距最大化程度。
核函数的形式是这样的
其中x(i)和x(j)都是向量，他们两个相乘就是向量内积，相乘得到一个数。刚才说了目标函数一般只和支持向量有关，因此在做核函数计算之前，实际就是选择的支持向量进行计算。
这个写完下面得再补充
我们知道了支持向量的概念，那么支持向量机的目标函数是要使这两个支持向量之间的距离尽可能的远，因为这样才能更好地把样本点分开，当然支持向量也要满足最基本的约束条件，那就是分类正确，还有就是其他点到分隔平面的距离要大于等于支持向量到分隔平面的距离。
这种凸优化问题都可以通过拉格朗日算子进行优化，就是把约束条件通过拉格朗日系数放到目标函数上。这部分基础知识，就是拉格朗日算法可以将等式约束和不等式约束都加到目标函数上，完成求解问题的转换，但是要满足一些约束条件，也就是我们后边要说的kkt条件。
这里有个细节就是转换时候的加减号问题，这个和目标函数还有约束的正负号有关。一般这么理解，就是求最小化问题时候，如果约束是大于0的，那么拉个朗日算子可以减到这一部分，这样一来目标函数只能越来越小，最优解就是约束为0的时候，这个时候和没有约束的等价，再求最小就是原问题了。
这里是最小化问题，直接减掉这部分约束，然后后半部分永远大于等于0所以这个式子的值是要小于原来目标函数值的。我们知道当x满足原问题的约束条件的时候，最大化L就等于那个原目标函数。所以我们可以把这个问题转化为：
把它带回去原来的目标函数中，整理一下。
这个时候只要求最优的α，就可以求出w和b了。我们上边做了那么一堆转换，这个过程要满足一个叫做kkt条件的东西，其实这个东西就是把一堆约束条件整理到一起。
（1）原有问题的可行性，即h(x )=0,g(x )0
放到这里就是：
SMO算法的核心思想是求出最优化的α，然后根据之前推导得到的w,b,α之间的关系计算得到w和b，最后的计算公式是：
现在的问题就是怎么求α了。
SMO算法总共分两部分，一部分是求解两个α的二次规划算法，另一部分是选择两个α的启发式算法。
先说这个选择α的启发式算法部分：大神可以证明优先优化违反kkt条件的α可以最快获得最优解，至于咋证明的，就先不看了。
在讲支持向量机的求解算法时候，直接给出了核函数K，那么怎么去理解核函数呢。核函数的作用是解决样本点在高维空间的内积运算问题，怎么理解呢，通常的分类问题都是有很多个特征的，然后为了达到现线性可分，又会从低维映射到高维，样本量再一多计算量非常大，因此先通过函数进行一个转换，减少乘法的计算量。
要理解核函数，先理解内积运算，内积运算实际是两个向量，对应位置相乘加和，比如我有x1 = [v1,v2], x2=[w1,w2]，那么x1和x2的内积计算方法就是：v1w1+v2w2。
如果上面那种情况线性不可分，需要到高维进行映射，让数据变得线性可分，然后数据变为五维的，即v1 2+v2 2+v1+v2+v1v2，然后再进行一次内积计算，数据变为 。
稍作变换，可以变为 ，形式展开和上边那个长式子差不多，然后其实可以映射内积相乘的情况，所以可以进行核函数的变化。
问题在于，当你需要显式的写出来映射形式的时候，在维度很高的时候，需要计算的量太大，比如x1有三个维度，再进行映射就有19维度了，计算很复杂。如果用核函数，还是在原来低维度进行运算，既有相似的效果（映射到高维），又低运算量，这就是核函数的作用了。
核函数的种类：
这部分的核心在于SMO算法的编写。有待补充。
