SVM 白板推导| 由最大间隔化目标演化的损失函数推导过程
SVM 英文名为 Support Vector Machine，叫支持向量机，SVM 是一个二分类模型。算法
感知机学习算法会由于初始值不一样而获得不一样的超平面，而 SVM 试图寻找一个最佳超平面，来划分数据，怎么才算最佳呢？咱们天然能想到，距离样本点距离尽量的远，模型的泛化性能和鲁棒性更强为最好，并且能够找到一条惟一的超平面。函数
以下图能够看出，感知机的超平面能够有无数条，SVM只要找到一条距离样本点最大间隔的超平面便可。性能
SVM 目标
咱们知道，感知机是一个如今网上已经有不少最初被提出是为了解决二分类问题，假设以下有正负样本。学习
由此，咱们知道，SVM 的目标就是要找到一条间隔最大化的超平面，使得样本点距离超平面尽量的远，那么，咱们如何找到间隔最大的超平面呢？优化
首先，咱们要先想到，间隔最大，便是求样本点到超平面的距离。spa
而如今，咱们有 N 个样本点，则咱们可能有 N 个距离，那咱们最终想要的就是，离超平面距离最小的样本点的最大值。rem
既然是最大间隔分类器，咱们拆开来解释：it
最大：找到距离样本点最大的间隔class
间隔：N 个样本点距离超平面的最小值变量
分类器：既然是二分类问题，那么咱们的超平面就是要将样本分开，对于超平面 $y=w^Tx+b$ 而言，咱们能够假设有两条超平面，一条是 $w^Tx+b>0$ 和 $w^Tx+b<0$，咱们能够引入函数 $yi=\{_{-1}^{+1}$，将两个超平面用一个函数表示，如图。
如今就须要咱们想办法计算样本点到超平面的距离，以下图，表示点 $(x_i,y_i)$ 到超平面 $y=w^Tx+b$ 的距离的计算，最终将目标转化为找到 N 个样本点距离超平面的最小距离。
将 $min-distance(w,b,x)$ 代入 $max-margin(w,b)$，条件是 $y_i=w^Tx_i+b>0$，而且是恒大于0，由此，咱们能够将下图的式子转换一下，将模去掉。
而且咱们还能看出，$\frac{1}{||w||}$ 与 $x_i$ 无关，咱们能够将它提到前面去。
这样一来，咱们的问题就转化成求解一个带约束的优化问题。对于条件 $y_i(w^Tx_i+b)>0$ 而言，必定存在一个 γ，使得 $min(y_i(w^Tx_i+b)>0)=γ$，为了简化计算，咱们能够令 $y_i(w^Tx_i+b)=γ$。
假设令 γ=1，则咱们能够获得最终的式子只与 W 有关，咱们要求损失函数，则将其转化成最小化问题。
可能有的人会疑惑，为何 γ=1可行，咱们知道，$y=w^Tx+b$ 和$ y=2w^Tx+2b$ 表示的是同一个超平面，咱们若是将 2-范数 固定下来，这样去指定 $y=w^Tx+b$ 的值是能够肯定下来，不然有无穷多个，由于能够随机缩放，由于 γ > 0，因此不管 γ 等于多少，均可以任意比例缩放成 1，对整个等式无影响。
咱们能够看到，目标函数是二次的，约束条件是线性的，因此它是一个带约束的凸二次规划问题，这个问题能够用现成的 QP 优化包进行求解，一言以蔽之：在必定约束下，目标最优，损失最小。
引入拉格朗日乘子
经过拉格朗日乘子，咱们已经将带约束的原问题转化成了无约束的问题。
那么什么是拉格朗日对偶性呢？简单来说，经过给每一个约束条件加上拉格朗日乘子 λ，定义拉格朗日函数 (经过拉格朗日函数将约束条件融合到目标函数中，从而只用一个函数表达式便能清楚的表达出咱们的问题)。
咱们能够看到，原式子是一个关于 w 的凸二次函数，约束条件是 N 个关于 x 的不等式。经过引入拉格朗日乘子以后，咱们能够将有约束问题转化为一个无约束的，只与 λ 有关的式子。
咱们能够简单的理解一下，为何能够这样定义，假设以下是关于 w,b 的集合，咱们能够将其表示为两个部分，一部分是 △>0，一部分是 △<=0。
当 △>0 时，即 $1-y_i(w^Tx_i+b)>0$，显然 $maxL(w,b,λ)=\frac{1}{2}w^Tw+∞=∞$，此时，对于咱们求解无心义，咱们也得不到最小化的值。
当 △<=0 时，即 $1-y_i(w^Tx_i+b)<=0$，显然 $maxL(w,b,λ)=\frac{1}{2}w^Tw+0=\frac{1}{2}w^Tw$，咱们能够看到，与原问题相符。
因此，当咱们谈到知足最优化的条件时，一般状况都是 △<=0 的状况。
此外，因为这个问题的特殊结构，还能够经过拉格朗日对偶性变换到对偶变量的优化问题，即经过求解与原问题等价的对偶问题获得原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样作的优势在于：一是对偶问题每每更容易求解，二是能够天然的引入核函数进而推广到非线性分类问题。
对偶问题与原问题
这里用 $p^*$ 表示原问题的最优解，且和最初的问题是等价的。若是直接求解，那么一上来便得面对 $w,b$ 两个参数，而 λ 又是不等式约束，这个求解过程很差作。不放把最小和最大的位置交换下。
交换之后的新问题是原问题的对偶问题，对偶问题的最优解用 $d^*$ 来表示，并且有 $d^* <= P^*$ ，在知足某些条件的状况下，这二者相等，这个时候，口能够经过求解对偶问题来间接求解原问题。
换言之，之因此从 $min$ $max$ 原始问题 $p^*$ 转化为 $max$ $min$ 的对偶问题 $d^*$，一者是由于 $d^*$ 是 $p^*$ 是近似解，两者，转化成对偶问题更容易求解。
下面能够先求 $L$ 对 $w,b$ 的极小，再求 $L$ 对 λ 的极大。
KKT
上面提到 $d^* <= P^*$ 在知足某些条件的状况下，二者相等，某些条件就是 KKT 条件。
对偶问题求解的 3 个步骤
1，固定 λ，让 $L$ 关于 $w,b$ 最小化，对 $w,b$ 求偏导，令 $\frac{δL}{δw}=0$ 和 $\frac{δL}{δb}=0$。
将以上结果代入 L，最终结果咱们能够看到，最终的结果只与 x 有关。
如何理解这一结果呢？咱们能够看看 KKT 条件中的其中一个。
当 λ=0 时，此时的 L 只与 w 有关，对超平面无限制。
当 λ>0 时，此时 $1-y_i(w^Tx_i+b)=0$，由于 $yi=\{_{-1}^{+1}$，此时，L 与在边界上的点有关，即只与支持向量有关。
2, 对 λ 求极大，便是关于对偶问题的最优化问题，通过上面的第一个步骤的求 w 和 b，获得拉格朗日函数式子已经没有了变量 w，b，只有 λ。
而且咱们也在以前求导过程当中求出了 w。
将上述式子代入 L 中，能够求出 w 和 b
最终，咱们能够获得新的分类决策函数。
3, 在求得 $L(w,b,λ)$ 关于 $w$ 和 $b$ 最小化，以及对 $λ$ 极大以后，最后一步即是利用 SMO 算法求解对偶问题中的拉格朗日乘子 λ。
咱们的拉格朗日函数中，在 $λ_i={λ_1,λ_2,...,λ_n}$ 上求上述目标函数的最小值，为了求解这些乘子，每次从中任意抽取两个乘子 $λ_1,λ_2$，而后固定 $λ_1,λ_2$ 之外的乘子 $λ_i={λ_3,λ_4,...,λ_n}$，使得目标函数只关于 $λ_1,λ_2$ 的函数，这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求乘子问题，最终达到求解原问题的目的。
若是您以为文章对你有帮助，欢迎点赞转发关注。