暂时先写个SVM的一步步的推导，应用场景，模型参数，优缺点等复习完了再好好总结。

一、支持向量机（SVM）

1.1、大致的思路

1.1.1由逻辑回归，引出SVM。（把逻辑回归的判别模型变化一下，就是SVM的判别模型）

如上图，逻辑回归学到的就是中间的那条线（学习过程就是不断地调整直线的过程），强调所有点尽可能地远离中间那条线。考虑了全局，但是也可能使一部分点靠近中间线来换取另外一部分点更加远离中间线。后果就是对于其中一些分类的点如c点，分类正确的确信度并不高。

由此引出SVM：我只关心局部（不关心已经远离的点 ），也就是，我让距离超平面最近的点的几何间距最大化，就提高了所有点的确信度，我的分类就很可靠了。

1.1.2，对逻辑回归做一下变化，引出函数间隔与几何间隔

逻辑回归的判别模型，取决于θ^Tx（尽管最后是映射到0-1区间），θ^Tx大于零，说明p>0.5，是正例。

用w^Tx+b代替θ^Tx，并对g(z)做一个简化，将其简单映射到类别标签y=1和y=-1上。

于是，暂时可以让w^Tx+b作为SVM分类器的判别模型，w^Tx+b大于零，说明是正例，反之为负例。（后面会 对几何间隔做一个限制，到时就是和1进行比较了。）

这样，y（w^Tx+b）就能代表分类正确情况下，该样例的判定类别的确信度，正负例的情况下都是正数，越大越好。

函数间隔
对于所有的样例来说，自然是确信度，越大越好。但是上面的y（w^Tx+b）可以通过调整参数 w 和 b让其无穷大， 这样不好不好。

几何间隔
我们真正关心的，其实是“几何上”的点到平面的距离，是可以用几何知识推理出来的几何间隔。而不是一开始人们想当然定义的函数间隔。

通过几何与向量的运算，可以得到几何间隔的表示：

几何间隔就是函数间隔除以∥w∥，而函数间隔实际上就是，只是人为定义的一个间隔度量，而几何间隔才是直观上的点到超平面的距离。

1.1.3 最优化 间隔分类器 （就是找到最优的超平面使得几何间隔最大）

我们想要找到最大的几何间隔，并且已经默认的是，所有样例进行y（w^Tx+b）运算得到的距离，都会大于函数间隔（定义），所以，得到目标函数为：

为了计算方便 ，并且使w和b能够有唯一的确定值，去去哦们将全局的函数间隔（分子）定义为1，并且把目标函数转换成二次的凸函数，得到

至此

• 1、已经得到SVM的判别模型：w^Tx_i + b 。参数就是w和b。
  学习完参数以后，新来的样例作为x_i，得到结果大于1，说明在超平面上面，所以是正例。反之亦然。

• 2、SVM的初步目标函数，就是所有样例的几何间隔尽可能的大

• 3、 优化方法勒？
  上面的目标函数并不好求，所以需要引入对偶问题，又因为此目标函数是凸规划问题，所以最优解（w）满足KKT条件 是 强对偶条件的 充分必要条件。

也就是说，求得对偶问题的最优解，也就是原问题的最优解了。

1.1.4 最优解 （也就是找到了最有间隔分类器）

上面引入对偶的优点：

• 1、对偶问题往往更容易求解
• 2、可以自然的引入核函数，进而推广到非线性分类问题。
• 3、 将w的计算提前并消除w，最终使得优化函数变为拉格朗日乘子的单一参数优化问题

---------------------------------------------------------------------------------------------

实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点就是函数间隔是1的点，他们前面的系数α_i>0，这三个点被称作 支持向量。

----------------------------------------------------------------------------------------------

开始求解目标函数（也是一般利用对偶求解目标函数的步骤）

• 1、 先把上面目标函数 构造成拉格朗日函数L
• 2、根据题意，得到原问题的对偶问题d=max min L
• 3、最里面的先求，所以先求L的最小值，此时max中的参数是固定的
  L对w和b求偏导数，解得

此时求得w和b（用α表示），也就是min L的解已经求出，带回对偶形式，接着解max，并且此时只有一个参数α了，解出α，对偶问题就能完美解决了。

即参数w用α表示的形式。b可以先不用管，因为将上式带入max中后 ，利用KKT的第三个条件，即可消去关于b的多项式。

• 4、将上式子带回L中，就得到了min L

由于最后一项是0，因此简化为

• 5、求 max （min L）
  min L已经求得（就是上式），接着就是最大化过程 max （min L）

至此，若是 求出了α，则对偶问题完美解决了，又因为前面的充要条件，也就说明，原问题完美解决了。

• 6、假设α 已经求出。
  其实 α 的求出也有些复杂，所以需要用后面的SMO算法求得，现在为了快速理解 SVM，先假设 α已经求出。

• 7、α已经求出，解用α表示。

假设求得了α_i 就能根据求导得到的结果

求得w，然后就能得到b。

b 就是 距离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。 （其实，由前面的那个x和圈的图，可以认为b就是截距，这个截距b等于上下两条虚线的截距的平均值。）

注意，这里的w，b，alpha都是 向量，都是m维的向量

----------------------------------------------------------------------------------------------

1.1.5 、对‘引入对偶问题的第三个优点的解释’ ： 可以将w的计算提前并消除w

目标函数的解已经求得，最终目标还是判别样例的标签！

由于前面求解中得到

用α_i代替w带入判别模型w^Tx+b，得到：

也就是说，利用判别模型对新来样本进行判别时，要先求得参数 w，b，再做一次线性运算 w^Tx+b，根据结果的正负来判断正负例。

优点一
现在有了alpha，不需要求出w（后面会说，b=w^Tx - y，这几个都是向量）

优点二
另外，那有人会说，与前面所有的样本都做运算是不是太耗时了？其实不然，我们从KKT条件中得到，只有支持向量的α_i>0 （不等于零）其他情况α_i是等于零的。比如，像前面那个x和圈的图，新来的样本只需要和三个支持向量做运算即可。

由此可以看到，求出α_i以后，只需要利用支持向量，就可以来判断新来的样例是正例还是负例了。也许这也是是为什么叫支持向量机吧。

经过上述所有这些东西，便得到了一个maximum margin hyper plane classifier，这就是所谓的支持向量机（Support Vector Machine）。 支持向量机器是最大化间隔超平面分类器。。wx+b

上面这个公式，为下面要提到的核函数（kernel）做了很好的铺垫。

1.2、核函数的登场

1.2.1、核函数总结：

• 1. 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的；
• 2. 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的(甚至会到无穷维，维度爆炸)。

（比如就是将原始空间特征的一阶二阶所有的组合作为新空间的维度，X=(x1,x2)就会变成了 5维，X=(x1,x2x,x3)就会变成19维，当然不是唯一的，可以有很多别的映射函数，比如一阶二阶三阶的，一般多项式的各种映射函数。）

• 3. 此时，核函数就隆重登场了，核函数绝就绝在它在低维上进行计算，但是和 采用第二步（映射到高维以后进行运算）计算得到的结果是相同的，效果也是一样的。
     但是，相比于第二步（映射到高维以后进行运算），核函数的优点就体现出来了：避免了直接在高维空间中的复杂运算，不需要显示的写出映射函数Φ（高维），大大降低了时间复杂度。

1.2.2、核函数的使用：

怎么让SVM利用核函数进行分类呢？

只需要将原来的内积替换成核函数就行了。值的判别也是同1进行比较。

1.2.2、核函数的判定（即怎么判断一个核函数是有效的）：

根据核函数的定义，交换内积前后顺序，可以推出核函数矩阵是半正定的，
又因为，又Mercer定理（矩阵核函数是半正定的，那么K是一个有效核函数。）

1.3 软间隔的提出（从理想到现实）

1.3.1 从理想到现实

至此讨论的都是理想状况：

• 样例线性可分时可以直接使用SVM进行分类
• 当样例线性不可分时（比如同心圆的情况），使用核函数来将特征映射到高维，这样很可能就可分了。

但是也会出现不理想的情况：

• 离群点导致平面受到影响：

• 背叛点导致不可分：

此时就需要调整模型了，让模型能够容忍这些‘不安分’的点，从理想状况接近现实。

1.3.2 调整模型（加入松弛变量）

然后根据引入对偶问题中的做法，得到最终的需要优化的结果，也是最接近现实的目标函数：

最优解必须满足KKT条件，而原问题已经做了调整，所以最优解α 满足的KKT条件也需要进行调整，得到结果如下：

至此，算是得到了软间隔的SVM的目标函数，并且此时的 α 向量满足KKT条件，是对偶问题的最优解，也是原问题的最优解

现在是一步到位，认为α 向量是最优解，所以得到了其相应的KKT条件。但事实是，此时α 向量一定不是最优解，求解目标函数的过程中， 就是调整α 向量中的各个参数，让其满足KKT条件的过程。

1.4 SMO算法

1.4.1 选取 α₁ 和 α₂ 以后，更新这两个参数

• 1、 将拉格朗日公式用α₁ 和 α₂ 表示
• 2、因为此时α₁ 和 α₂增加了一个约束条件，所以需要更新上下界，为后期求出这两个参数以后，做限制准备。
• 3、接着求解，α₁ 用α₂ 表示，得到只含有α₂ 的函数
• 4、 对α₂ 求导，得到α₂ 的解，再根据2所说满足上下界
• 5、 α₁ 的解用α₂的解表示

1.4.2 怎么选取这两个参数？

-------------------------------------------------------------------------------------