支持向量机 c++代码_支持向量机：白板推导 + 代码实现-白红宇

支持向量机 c++代码_支持向量机：白板推导 + 代码实现

阅读量：5940 次

发布时间：2019-06-19

本文共 2756 字，大约阅读时间需要 9 分钟。

为了能够介绍清楚支持向量机，首先需要理解下面的一些数学基础。

支持向量机的数学基础

点到直线/超平面的距离

首先推导

$equation?tex=%5Cmathbb%7BR%7D%5ED$ 空间中点到超平面的距离。

图 1. 欧氏空间中点到直线的距离公式推导

带约束的优化问题

优化问题 1：带有等式约束的优化问题

图 2. 等式约束的优化问题求解方法（拉格朗日乘子法）

通过上面的推导，带有等式约束的优化问题可以转化为等价的拉格朗日函数在

$equation?tex=%5Cmathbb%7BR%7D%5E%7BD%2B1%7D$ 空间中关于

$equation?tex=%5Cmathbf%7Bx%7D$ 和

$equation?tex=%5Clambda+$ 的优化问题。

优化问题 2：带有不等式的约束优化问题

图 3. 不等式约束优化问题的等价转换（KKT 条件）

优化问题 3：等式和不等式约束同时存在的优化问题

图 4. 同时带有等式与不等式约束的优化问题等价转换

主问题转换为对偶问题

图 5. 主问题与对偶问题的关系推导

为什么要转换原问题到对偶问题？

1. 主问题的目标函数或者可行域不一定是凸的（Convex），但是对偶问题中，目标函数是变量的线性组合，同时可行域是超立方体，所以必然是凸的。

2. 即使主问题是凸的，其可行域是被超平面截出来的一些不规则区域，不利于求解。但是对偶问题的可行域是规则的超立方体，利于模型的求解。

3. 对于满足如下 Slater 条件的带约束优化问题，对偶问题和原问题的解是一样的。可通过求解对偶问题得到原问题的解。

图 6. 主问题与原问题的关系

支持向量机可以通过两种观点进行推导，下面先介绍几何的观点。

支持向量机：几何的观点

基本型（硬间隔支持向量机）

图 7. 支持向量机的基本想法

主要想法

1. 超平面：在空间中找到完全将两类样本点分开的超平面。

2. 分类原则：如果分类函数取正值，则将样本点分为正样本，否则为负样本。

3. 稳健原则（MaxMin 准则）：所选的分类超平面满足，离超平面最近点的距离最大化。

主问题

从图 1 可以得到下面 P0 中目标函数的点到直线距离公式，

图 8. 支持向量机主优化问题的等价转换

上图的一些注记：

1. P0 到 P1的等价转换关系成立，主要通过限定每个超平面对应的

$equation?tex=%5Cmin_%7Bx_i%7D%7Cw%5ETx_%7Bi%7D%2Bb%7C%3D1$ 来实现。

2. 上图中的优化问题

$equation?tex=P0+%3C%3D%3EP1%3C%3D%3EP2%3C%3D%3EP3$ .

对偶问题

图 9. 主问题转换为对偶问题

KKT 条件与模型参数求解

图 10. KKT 条件与通过对偶问题求解判别函数参数

支持向量：通过求解对偶问题 D0，所有非零的

$equation?tex=%5Chat%7B%5Calpha%7D_i$ 对应的样本

$equation?tex=x_i$ 使得

$equation?tex=y_i%28%5Chat%7Bw%7D%5E%7BT%7Dx_%7Bi%7D-b%29%3D1$ 满足

$equation?tex=%5Cmin_%7Bx_i%7D%7Cw%5ETx_i%2Bb%7C%3D1$ 。所以，这些样本都是到分类超平面距离最近的点，又被称为支持向量。

分类超平面的参数：从图 10 可以看出，分类超平面的参数

$equation?tex=%5Chat%7Bw%7D$ 与

$equation?tex=b$ 仅由支持向量构成。所以支持向量机的模型复杂度由支持向量决定。大部分的训练样本都不参与模型的推断，所以模型做预测的计算复杂度非常的低。

线性可分/线性不可分

线性可分：假定样本所在的空间中存在一个超平面能够将正样本与负样本划分平面的两侧。

基本类型的支持向量机基于线性可分的假设，利用训练样本来构造最优（稳健）的超平面。

示例

图 11. (a) 线性可分示例；（b）线性不可分示例

拓展类型（软间隔（soft-margin）的支持向量机）

为了使得模型能够处理线性不可分的分类问题，可以通过容许支持向量机在某些样本上判别错误。

软间隔的引入

软间隔：不满足优化问题 P3 中约束条件的样本点，即

$equation?tex=y_%7Bi%7D%28w%5ETx_%7Bi%7D%2Bb%29%3C1$ 。

松弛变量的引入

松弛变量：

$equation?tex=%5Cxi_i%5Cgeq0$ , 且

$equation?tex=y_i%28w%5ETx_i%2Bb%29%5Cgeq1-%5Cxi_i$ 。

目标函数拓展

优化问题 P3 中的目标函数为

$equation?tex=%5Cfrac%7B1%7D%7B2%7D%5C%7Cw%5C%7C_2%5E2$ 。此时对于松弛变量而言，还需要引入另一个目标，即引入的松弛变量之和越小越好。将优化问题 P3 的优化目标与松弛变量的目标综合起来，得到间隔支持向量机的目标函数，

$equation?tex=%5Cfrac%7B1%7D%7B2%7D%5C%7Cw%5C%7C_2%5E2%2BC%5Csum_%7Bi%3D1%7D%5E%7Bm%7D%5Cxi_i$ ，其中非负数

$equation?tex=C$ 是惩罚系数，用来平衡原始目标与松弛变量目标的相对重要程度。

主问题与对偶问题

图 12. 软间隔支持向量机的主问题与对偶问题

KKT 条件

图 13. 软间隔的 KKT 条件以及不同类型的点

解对偶问题 D1，得到最优解

$equation?tex=%5Chat%7B%5Calpha%7D%3D%28%5Chat%7B%5Calpha%7D_1%2C%5Chat%7B%5Calpha%7D_2%2C%5Cdots%2C%5Chat%7B%5Calpha%7D_m%29%5ET$ ，通过下面的对应关系，可以得到主问题 P4 的解，

$equation?tex=%5Chat%7Bw%7D%2C%5Chat%7Bb%7D%2C%5Chat%7B%5Cxi%7D_i$ 。

图 14. 对偶问题 D1 的解与主问题 P4 的解之间的对应关系

（1）如果

$equation?tex=0%3C%5Chat%7B%5Calpha%7D_i%3CC$ , 则

$equation?tex=%5Chat%7B%5Cxi%7D_%7Bi%7D%3D0$ , 即第

$equation?tex=i$ 个样本点刚好落在最大间隔的边界上面。

（2）

$equation?tex=%5Chat%7B%5Calpha%7D_i%3DC$ ，

（2.1）如果

$equation?tex=%5Chat%7B%5Calpha%7D_i%3DC$ 且

$equation?tex=%5Chat%7B%5Cxi%7D_%7Bi%7D%5Cleq1$ , 则分类边界将第

$equation?tex=i+$ 个样本点正确分类，且该点处于由两侧最大间隔构成的带状区域内。

（2.2）如果

$equation?tex=%5Chat%7B%5Calpha%7D_i%3DC$ 且

$equation?tex=%5Chat%7B%5Cxi%7D_%7Bi%7D%3E1$ , 则分类边界将第

$equation?tex=i+$ 个样本点错误分类。

（3）如果

$equation?tex=%5Chat%7B%5Calpha%7D_i%3D0$ ，则分类边界将第

$equation?tex=i$ 个样本点正确分类，且该点处于由两侧最大间隔构成的带状区域外。

损失函数

通过如下 P4 到 P6 的等价转化，可以将软间隔的支持向量机问题转化为经验 Hinge 损失 +

正则项这种一般形式。

图 15. 软间隔支持向量机转化为损失函数+正则项的过程

图 16. 常见的损失函数及其图像

相较于指数损失与 logistic 损失函数，使用 hinge 损失函数得到的解具有稀疏性。相较于支持向量机，使用 logistic 回归做预测需要更大的时间与存储开销。

一般形式

图 17. 一般形式：最小化经验风险 + 结构风险

经验风险：描述所选模型

$equation?tex=f%28x%29$ 与样本的接近程度。

结构风险: 又称作正则化项，描述模型的某方面性质，比如模型的复杂度。

$equation?tex=L_p$ 范数通常被用来做为正则化项，比如

$equation?tex=%5C%7Cw%5C%7C_0%2C+%5C%7Cw%5C%7C_1$ 倾向于选择稀疏的模型，

$equation?tex=%5C%7Cw%5C%7C_2$ 倾向于选择各个分量都比较均衡的模型。

正则化常数：协调模型选择过程中，经验风险和结构风险之间的偏好。