笔者比较懒能截图的地方都截图了。

1 支持向量机分类

支持向量机分为三类：
（1）线性可分支持向量机，样本线性可分，可通过硬间隔最大化训练一个分类器。
（2）线性支持向量机，样本基本线性可分，可通过软间隔最大化训练一个分类器。
（3）非线性支持向量机，样本线性不可分，可通过核函数和软间隔最大化训练一个分类器。
上面最不好理解的恐怕就是硬间隔和软间隔了，
说白了硬间隔就是说存在这么一个平面，可以把样本完全正确无误的分开，当然这是一种极理想的情况，现实中不存在，所以就有了软间隔。
软间隔说的是，不存在一个平面可以把样本完全正确无误的分开，因此呢允许一些样本被分错，怎么做呢就是加入松弛变量，因为希望分错的样本越小越好，因此松弛变量也有约束条件。加入松弛变量后，问题就变为线性可分了，因为是每一个样本都线性可分，因此松弛变量是针对样本的，每一个样本都对应一个不同的松弛变量。

2 支持向量机的几个概念

2.1 感知机

其实感知机说白了就是找到一条直线把样本点分开，就是上方都是一类，下方是另一类。当然完全分开是好事，往往是不能完全分开的，因此就存在一个损失函数，就是误分类点到这个平面的距离最短：

目标函数-1

这里啰嗦一句，误分类点y*(wx+b)<0，所以加个负号在前边。
一般情况下||w||都是可以缩放，那么我们把它缩放到1，最后的目标函数就变成了

目标函数-2

2.2 函数间隔与几何间隔

间隔就是距离，我们假设分离超平面为，那么样本点到这个平面的距离可以记为。我们都知道通过感知机划分的点，超平面上方的点，下方的点，然后通过判断的值与y的符号是否一致来判断分类是否正确。根据这个思路函数间隔定义为：

函数间隔
函数间隔的问题就在于w和b是可以成倍增加的，这样的话函数间隔是有问题的，并不能代表点到平面的真实距离，因此我们参考点到平面的距离公式，给它加一个限制，最后变成：
几何间隔
当然了最后的函数间隔和几何间隔都要取所有点中的最小值。
image.png
image.png

2.3 支持向量

支持向量的定义来源于几何间隔，几何间隔最直接的解释是离分隔超平面最近点的距离，其他任何点到平面的距离都大于这个值，所以几何间隔就是支持向量。然后呢同样道理，w和b是可以缩放的，所以定义支持向量满足如下条件：

image.png
image.png

再通俗一点说，支持向量是一些点，这些点到分隔平面的距离最近，为了便于表示，把他们进行一下缩放计算，让他们满足了wx+b=+-1.

2.4 核函数

核函数是支持向量机的核心概念之一，它存在的目的就是将维度转换之后的计算简化，达到减少计算量的目的。我们都知道支持向量机求的是间距最大化，通常情况下我们求得的alpha都等于0，因此支持向量决定了间距最大化程度。
核函数的形式是这样的

image.png

其中x(i)和x(j)都是向量，他们两个相乘就是向量内积，相乘得到一个数。刚才说了目标函数一般只和支持向量有关，因此在做核函数计算之前，实际就是选择的支持向量进行计算。

2.4 硬间隔最优化和软间隔最优化

这个写完下面得再补充

3 支持向量机的推导

3.1 原问题目标函数和约束条件

我们知道了支持向量的概念，那么支持向量机的目标函数是要使这两个支持向量之间的距离尽可能的远，因为这样才能更好地把样本点分开，当然支持向量也要满足最基本的约束条件，那就是分类正确，还有就是其他点到分隔平面的距离要大于等于支持向量到分隔平面的距离。

原问题形式
为了便于计算，几何间隔可以取,关于这个还有一种说法就是说取几并没有关系，因为我们主要要优化的是w和b。现在目标函数又变成：
简化后的原问题
为了方便求导计算等，我们再对这个公式做个转化，就是最小化和最大化是一样的，再转换一下：
image.png
写到这了，有点数学基础的都发现这是一个凸优化的问题，没有数学基础也没关系，凸优化就是目标函数是二次的，约束条件是线性的，其实这时可以用任何一种优化软件求解了，但是比较麻烦，所以有人又开始对这个问题做转换了。

3.2 拉格朗日算子转化问题

这种凸优化问题都可以通过拉格朗日算子进行优化，就是把约束条件通过拉格朗日系数放到目标函数上。这部分基础知识，就是拉格朗日算法可以将等式约束和不等式约束都加到目标函数上，完成求解问题的转换，但是要满足一些约束条件，也就是我们后边要说的kkt条件。
这里有个细节就是转换时候的加减号问题，这个和目标函数还有约束的正负号有关。一般这么理解，就是求最小化问题时候，如果约束是大于0的，那么拉个朗日算子可以减到这一部分，这样一来目标函数只能越来越小，最优解就是约束为0的时候，这个时候和没有约束的等价，再求最小就是原问题了。

image.png

这里是最小化问题，直接减掉这部分约束，然后后半部分永远大于等于0所以这个式子的值是要小于原来目标函数值的。我们知道当x满足原问题的约束条件的时候，最大化L就等于那个原目标函数。所以我们可以把这个问题转化为：

image.png
根据拉格朗日对偶性，极小极大问题可以转化为极大极小问题
image.png
这样把有约束问题，转化为无约束问题了，现在求minL，就是求偏导的事了：
image.png

把它带回去原来的目标函数中，整理一下。

image.png
于是原来的问题可以转化为下面这个形式了：
image.png
我们还有一个求极大值的过程：
image.png
但是这个有约束的，就是我们上面求的 image.png
最后我们要解决的问题是这个，取负号后最大化的问题就变为最小化问题了：
image.png

3.3 SMO算法求解

3.3.1 kkt条件

这个时候只要求最优的α，就可以求出w和b了。我们上边做了那么一堆转换，这个过程要满足一个叫做kkt条件的东西，其实这个东西就是把一堆约束条件整理到一起。
（1）原有问题的可行性，即h(x)=0,g(x)<0
放到这里就是：

image.png
（2）拉格朗日性，
image.png
这个式子不太好理解，可以拆开来看，
image.png
就是说在无约束的最优化问题下，取得最优值得时候，对所有参数求偏导等于0。
（3）目标函数成立性，就是不等式的拉格朗日算子要大于等于0，但在最优值处一定要满足原目标函数取得最大，所以他和不等式相乘要等于0，就是要消除约束条件的影响，这个比较好理解。
image.png
来对SVM的kkt条件做一个总结：
svm的kkt条件
知道了这些，我们来看smo算法。

3.3.2 SMO算法

SMO算法的核心思想是求出最优化的α，然后根据之前推导得到的w,b,α之间的关系计算得到w和b，最后的计算公式是：

image.png
image.png

现在的问题就是怎么求α了。
SMO算法总共分两部分，一部分是求解两个α的二次规划算法，另一部分是选择两个α的启发式算法。
先说这个选择α的启发式算法部分：大神可以证明优先优化违反kkt条件的α可以最快获得最优解，至于咋证明的，就先不看了。

• 启发式算法的步骤：
  1）外层循环，就是选第一个待优化的α，遍历一遍数据，选出0<α<C的点，判断是否违反kkt条件，也就是说yif(xi)远大于1或者远小于1。这个时候的KKT条件是下面的这个图这样的，违反严重就是说和后边的计算结果相去甚远，当然是选择yf(x)绝对值最大的值作为第一个优化的alpha。

  
  KKT条件
  

  这里还要说下C是什么，C是我们人为加的一个α上限。
  2）内层循环，就是选择第二个待优化的α，这时候的标准是让|E2-E1|足够大，从而达到加速计算的过程。
  其实最重要的就是第一个alpha的选择，确定一个alpha后需要一直遍历样本点，找出yif(xi)最大的那个alpha。

• 二次规划算法的步骤
  1）选出来待优化的两个alpha,固定其他alpha,改变目标函数形式：

  
  image.png
  

  这个K是两个x相乘的简写，也可以理解为核函数，实质上为简化计算就是用了核函数。
  满足的约束条件是：

  
  image.png
  2）alpha取值范围的问题
  接下来看看两个待优化的alpha取值有什么约束。
  image.png
  

  首先是α都是大于等于0小于等于C的，因此在矩形框内。
  

  其次两个alpha取值还满足kkt条件 image.png
  ，因此还要在那条直线上。
  这个图标记的很清楚，各种情况下，α的取值范围，如果各位看官有疑问，可以自己去百度一下。有了这个图，各个端点的坐标就可以求出来了。
  y1和y2不相等的时候，满足下面：
  image.png
  y1和y2相等的时候，满足下面：
  image.png
  3）α更新方法
  现在需要优化的变量只有α1和α2，我们知道g(x)=wx+b，根据KKT条件有：
  image.png
  现在计算一下预测值和真实值之间的差，记为E
  image.png
  

  现在我们有了alpha的更新公式了：

  
  image.png
  注意，这个公式就是编程时候要用的，至于怎么推导的，大概说一下，其实记住这个就行了。
  先人为定义一个v：
  image.png
  把目标函数改一下：
  image.png
  然后表示一下α1，就是根据它的一些性质，直接截图了：
  image.png
  带入目标函数，求导数：
  image.png
  求最优解就是让他等于0，然后整理一波：
  image.png
  好了 最重要的一步来了，我们说了上边alpha2的取值是有约束的，最后更新alpha2需要这么来：
  image.png
  然后计算alpha1要这么来：
  image.png
  4）更新b和E
  参数更新后，b和E也变了，怎么计算直接给出方法：

• alpha在0和C之间

  
  image.png
  image.png
  image.png
• alpha等于0或者C
  b取b1和b2的均值
  最后，概述一下SMO算法的流程：
• 初始化alpha全部为0
• 根据启发式算法选择优化的α1和α2，其他保持固定
• 根据二次规划算法更新α1和α2
• 遍历所有样本是否完全满足kkt条件，若是输出参数值，否则重复2-3步
  原理部分基本就这么多，当然很多细节笔者也有不懂的地方，但是大概可以理顺这个算法了。

3.4 核函数的解释

在讲支持向量机的求解算法时候，直接给出了核函数K，那么怎么去理解核函数呢。核函数的作用是解决样本点在高维空间的内积运算问题，怎么理解呢，通常的分类问题都是有很多个特征的，然后为了达到现线性可分，又会从低维映射到高维，样本量再一多计算量非常大，因此先通过函数进行一个转换，减少乘法的计算量。
要理解核函数，先理解内积运算，内积运算实际是两个向量，对应位置相乘加和，比如我有x1 = [v1,v2], x2=[w1,w2]，那么x1和x2的内积计算方法就是：v1w1+v2w2。
如果上面那种情况线性不可分，需要到高维进行映射，让数据变得线性可分，然后数据变为五维的，即v1^2+v22+v1+v2+v1v2，然后再进行一次内积计算，数据变为。
稍作变换，可以变为，形式展开和上边那个长式子差不多，然后其实可以映射内积相乘的情况，所以可以进行核函数的变化。
问题在于，当你需要显式的写出来映射形式的时候，在维度很高的时候，需要计算的量太大，比如x1有三个维度，再进行映射就有19维度了，计算很复杂。如果用核函数，还是在原来低维度进行运算，既有相似的效果（映射到高维），又低运算量，这就是核函数的作用了。
核函数的种类：

• 线性核
  其实就是适用于线性可分的情况，样本的维度并没有变化。这个就是为了形式上的统一，没有什么具体的含义。

• 多项式核

  
  image.png
  

  可以将低维数据映射到高维，d越高维度越多越复杂。

• 径向基核函数

  
  image.png
  

  也可以将数据映射到高维，跟距离有关，距离函数可用的在此都可用。

• sigmoid核函数

  
  image.png
  

  来源于神经网络，应用的不多，其实采用这个核函数就是实现多层感知机。
  核函数怎么选择呢：
  原则就是先试试线性核函数效果怎么样，如果不好再换其他的，可以参照下面的方法：
  （1）特征很多，样本比较少，选择线性核函数
  （2）特征少，样本居中，选择径向基核函数
  （3）特征少，样本很大，选择多项式核函数
  当然这只是一般原则，如果实际要选择的话，还是结合实际特点来。

3.5 软间隔的解释

• 基本理念
  软间隔实际是将硬间隔的条件放宽了，本来要求点到支持向量的距离一定是大于等于1的，现在加入软间隔就是增加了一点缓冲，允许一些错误点的出现。
  软件的做法是引入松弛变量，将约束条件变为：

  
  带软间隔的约束条件
  

  进一步将支持向量机的目标函数进行改写：

  
  带软间隔支持向量机的形式
  这里有一个关键的参数C，他是误分类的损失函数，越大代表对误分类的容忍度越低，是支持向量机调参过程中的一个重要参数。

• 函数优化方法
  优化思路和普通SVM差不多吧，也是拉格朗日加对偶形式解决的，最后得到的形式是：

  
  带软间隔支持向量机最后形式
  

  实际上就是多了一个惩罚项C，其实支持向量机代码编写都是考虑软间隔的。

3.6 python实现SVM

这部分的核心在于SMO算法的编写。有待补充。