机器学习：SVM（一）——线性可分支持向量机原理与公式推导
原理
- SVM基本模型是定义在特征空间上的二分类线性分类器（可推广为多分类），学习策略为间隔最大化，可形式化为一个求解凸二次规划问题，也等价于正则化的合页损失函数的最小化问题。求解算法为序列最小最优化算法（SMO）
- 当数据集线性可分时，通过硬间隔最大化，学习一个线性分类器；数据集近似线性可分时，即存在一小部分outlier，除这些点外，其他的样本线性可分，此时通过软间隔最大化，学习一个线性分类器；当数据集线性不可分时，将输入映射到高维空间使得线性可分，利用原本空间中的核函数表示特征向量映射到高维空间之后的内积，这种方法称为核技巧，此时学习到非线性支持向量机。
- 函数间隔与几何间隔
一个点距离超平面远近可以表示分类预测的确信程度，在超平面\(w \cdot x + b = 0\;({w^T}x + b = 0)\)确定的情况下，\(|{w^T}x + b|\)能够相对表示距离超平面的远近，取正例\(y=+1\)，负例\(y=-1\),则\(y({w^T}x + b)\)可以表示分类正确性以及确信度。大小表示远近，正负表示分类正确与否。
超平面关于某个样本点\((x_i,y_i)\)的函数间隔为\[{\hat \gamma _i} = {y_i}(w \cdot {x_i} + b)\]超平面关于训练集的函数间隔为\[\hat \gamma = \mathop {\min {{\hat \gamma }_i}}\limits_{i = 1,2,...,N} \]
在成比例改变\(w,b\)时，函数间隔会变大，但此时超平面并没有改变。因此需对法向量施加约束，从而有了几何间隔。
超平面关于某个样本点\((x_i,y_i)\)的几何间隔为\[{\gamma _i} = {y_i}(\frac{{w \cdot x_i + b}}{{||w||}})\]超平面关于训练集的几何间隔为\[ {\gamma } = \mathop {\min {\gamma _i}}\limits_{i = 1,2,..,N} \] - 线性可分支持向量机选择一个超平面将空间分成两部分，一部分全部为正例，一部分全部为负例，要求几何间隔最大。感知机的策略是误分类数最小，因此满足条件的超平面不唯一，有无穷多。而线性可分支持向量机基于几何间隔最大的超平面唯一。
- 算法描述
输入：线性可分训练集\(T = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\} ,{y_i} \in \{ + 1, - 1\} ,i = 1,2,..,N\)
输出：分离超平面和分类决策函数
(1).构造并求解约束最优化问题\[\begin{array}{l} \mathop {\min }\limits_\alpha \;\;\;\;\;\frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i} \cdot {x_j}) - \sum\limits_{i = 1}^N {{\alpha _i}} } } \\ s.t.\;\;\;\;\;\;\;\sum\limits_{i = 1}^N {{\alpha _i}{y_i}} = 0\\ \;\;\;\;\;\;\;\;\;\;\;{\alpha _i} \ge \;0\;\;\;\;\;\;i = 1,2,...,N \end{array}\]求得最优解\({\alpha ^*} = {(\alpha _1^*,\alpha _2^*,...,\alpha _N^*)^T}\)
(2).计算\[{w^*} = \sum\limits_{i = 1}^N {\alpha _i^*{y_i}} {x_i}\]并选择一个\(\alpha _j^* > 0\)，计算\[{b^*} = {y_j} - \sum\limits_{i = 1}^N {\alpha _i^*{y_i}({x_i}} \cdot {x_j})\]
(3).求得分离超平面\[{w^*} \cdot x + {b^*} = 0\]分类决策函数：\[f(x) = sign({w^*} \cdot x + {b^*})\]
公式推导
预备知识
- 拉格朗日函数与求解约束最优化问题。假设\(f(x),c_i(x),h_j(x)\)是定义在\(R^n\)上的连续可微函数，对于约束最优化问题\[\begin{array}{l} \mathop {\min }\limits_x f(x)\\ s.t.\;\;{c_i}(x) \le 0,\;\;i = 1,2,...,k\\ \;\;\;\;\;\;{h_j}(x) = 0,\;\;j = 1,2,...l \end{array}\]首先引入拉格朗日函数\[L(x,\alpha ,\beta ) = f(x) + \sum\limits_{i = 1}^k {{\alpha _i}} {c_i}(x) + \sum\limits_{j = 1}^l {{\beta _j}} {h_j}(x),\;\;\;\;\;{\alpha _i} \ge 0\]则在\(x\)满足约束条件下\[\mathop {\min }\limits_x f(x) = \mathop {\min }\limits_x \;\mathop {\max }\limits_{\alpha ,\beta } L(x,\alpha ,\beta ),\;\;\;\;{\alpha _i} \ge 0\]这样一来，就把原始问题表示为广义拉格朗日函数的极小极大问题。
- 对偶问题。记极小极大问题为原始问题，则其对偶问题为\(\mathop {\max }\limits_{\alpha ,\beta } \;\mathop {\min }\limits_x L(x,\alpha ,\beta )\)，称为广义拉格朗日函数的极大极小问题。假设原始问题与极大极小问题函数都有最优值，两者关系为前者最优值大于等于后者最优值。对应于最优值，存在可行解。当最优值相等时，两个问题的可行解即为两个问题的最优解。
- KKT条件。由上我们可以得出思路，当原始问题与对偶问题的最优值相等时，可行解为最优解，可用解对偶问题替代解原始问题。假设\(f(x),c_i(x)\)为凸函数，\(h_j(x)\)为仿射函数，并且不等式约束是严格可行的，则此时\(x^*\)和\({\alpha ^*},{\beta ^{^*}}\)分别是原始问题和最偶问题的充要条件是满足KKT条件：\[\begin{array}{l} {\nabla _x}L({x^*},{\alpha ^*},{\beta ^*}) = 0\\ {\nabla _\alpha }L({x^*},{\alpha ^*},{\beta ^*}) = 0\\ {\nabla _\beta }L({x^*},{\alpha ^*},{\beta ^*}) = 0\\ {\alpha _i} \ge 0\\ {c_i}({x^*}) \le 0\\ {\alpha _i}{c_i}({x^*}) = 0\;\;\;\;\;\;\;i = 1,2,...,k\\ {h_j}({x^*}) = 0\;\;\;\;\;\;\;\;j = 1,2,...,l \end{array}\]第五式为对偶互补条件！其中一个因子必为0。以线性可分支持向量机来看，第一个因子为零，样本不会在求和中出现。第二个因子为零，样本在间隔边界上，此时为支持向量。同时保证了二式。
具体推导
在上面算法描述中我们知道，要求出超平面只需要解决算法描述中的(1)，后面超平面问题即可迎刃而解。关键是（1）怎么得到的，下面推导为过程，其中用到了预备知识。
- 基于最大几何间隔分离超平面可表示为\[\begin{array}{l} \mathop {\max }\limits_{w,b} \gamma \\ s.t.\;\;\;{y_i}(\frac{{w \cdot x + b}}{{\left\| w \right\|}}) \ge \gamma ,\;\;\;i = 1,2,..,N \end{array}\]
- 考虑到几何间隔与函数间隔的关系，可将问题改写为\[\begin{array}{l} \mathop {\max }\limits_{w,b} \frac{{\hat \gamma }}{{\left\| w \right\|}}\\ s.t.\;\;\;{y_i}(w \cdot x + b) \ge \hat \gamma ,\;\;\;i = 1,2,..,N \end{array}\]
- 函数间隔取值对最优化问题求解不影响，因此可取1，颠倒分子分母后，最大化与最小化等价，于是得到如下最优化问题\[\begin{array}{l} \mathop {\min }\limits_{w,b} \;\;\frac{1}{2}{\left\| w \right\|^2}\\ s.t.\;\;\;{y_i}(w \cdot x + b) - 1 \ge 0,\;\;\;i = 1,2,..,N \end{array}\]
- 构造拉格朗日函数\[L(w,b,\alpha ) = \frac{1}{2}{\left\| w \right\|^2} + \sum\limits_{i = 1}^N {{\alpha _i}} [1 - {y_i}(w \cdot {x_i} + b)] = \frac{1}{2}{\left\| w \right\|^2} - \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}(w \cdot {x_i} + b) + \sum\limits_{i = 1}^N {{\alpha _i}}，{\alpha _i} \ge 0 \]此时，在约束条件下\[\mathop {\min }\limits_{w,b} \;\;\frac{1}{2}{\left\| w \right\|^2} = \mathop {\min }\limits_{w,b} \;\mathop {\max }\limits_\alpha L(w,b,\alpha ),{\alpha _i} \ge 0\]，为极小极大问题。
- 对偶问题为极大极小问题 \(\mathop {\max }\limits_\alpha \mathop {\min }\limits_{w,b} L(w,b,\alpha ),{\alpha _i} \ge 0\),我们知道普通条件下原问题是不能利用对偶条件来求解的，需要某些条件进行限定，即\(KKT\)条件。因此我们给出限定约束如下：\[\begin{array}{l} {\nabla _w}L = 0\\ {\nabla _b}L = 0\\ {\alpha _i} \ge 0\\ {y_i}(w \cdot {x_i} + b) - 1 \ge 0\\ {\alpha _i}{y_i}(w \cdot {x_i} + b) = 0 \end{array}\]
- 此时我们只需求解对偶问题\[\mathop {\max }\limits_\alpha \mathop {\min }\limits_{w,b} L(w,b,\alpha ),{\alpha _i} \ge 0\]即可。我们需要先求极小，将解带入得到极小的函数值，再求极大。
1.将拉格朗日求偏导并令其等于0\[\begin{array}{l} {\nabla _w}L = w - \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}{x_i} = 0\\ {\nabla _b}L = \sum\limits_{i = 1}^N {{\alpha _i}{y_i} = } 0\\ \\ w = \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}{x_i}\\ \sum\limits_{i = 1}^N {{\alpha _i}{y_i} = } 0 \end{array}\]
2.带入拉格朗日函数，可得\[\begin{array}{l} L = \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) - \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}[(\sum\limits_{j = 1}^N {{\alpha _j}} {y_j}{x_j}) \cdot {x_i} + b] + \sum\limits_{i = 1}^N {{\alpha _i}} \\ \;\;\; = - \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) + \sum\limits_{i = 1}^N {{\alpha _i}} \end{array}\]，即\[\;\;\min L\; = - \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) + \sum\limits_{i = 1}^N {{\alpha _i}} \]
3.对上式求极大，相当于加符号求极小，从而得到最终形式\[\begin{array}{l} \mathop {\min }\limits_\alpha \;\;\;\;\; \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) - \sum\limits_{i = 1}^N {{\alpha _i}} \\ s.t.\;\;\;\;\;\;\sum\limits_{i = 1}^N {{\alpha _i}{y_i} = } 0\\ \;\;\;\;\;\;\;\;\;\;{\alpha _i} \ge 0,\;\;\;\;\;i = 1,2,...,N \end{array}\]
因此我们只需考虑求解上面的最终形式，从而进一步求得\(w,b\)即可得线性可分支持向量机。这也是一个约束最优化问题，利用序列最小最优化算法（SMO）即可求解。
总结
- 求解线性可分支持向量机，即利用SMO求解最终形式最优化问题，得到\(\alpha\),进一步求得\(w,b\)，从而得到分离超平面和分类决策函数。其中的推导过程需要理解明白，单纯记住一个最终模型没有意义。
1、Linux C语言中gotoxy函数
2、DRF之注册器响应器分页器
3、Swift—泛型（上）
4、k 动画脚本很有算法 同时可以借鉴这里的画圆
5、第一坑