机器学习——支持向量机（SVM）（1）

目录

一、认识SVM

1. 基本介绍

2. 支持向量机分类器目标

二、线性SVM分类原理（求解损失）

三、重要参数

1. kernel（核函数）

2 .C（硬间隔与软间隔）

四、sklearn中的支持向量机（自查）

1. 种类

2. 参数列表（SVC）

3. 属性列表（SVC）

4. 接口列表（SVC）

---

一、认识SVM

1. 基本介绍

        支持向量机（Support Vector Machine，SVM）属于有监督学习模型，主要 用于解决 数据分类问题。SVM 将 每个样本数据 表示为 空间中的点，使 不同类别的样本点尽可能 明显地区分开。通过将样本的 向量映射到高维空间中，寻找 最优区分 两类数据的超平面，使 各分类到 超平面的距离最大化，距离越大 表示 SVM 的分类 误差越小。

        通常 SVM 用于 二元分类问题，对于 多元分类可将 其分解为 多个 二元分类问题，再进行分类，主要的应用场景有 图像分类、文本分类、面部识别、垃圾邮件检测等领域。

2. 支持向量机分类器目标

        支持向量机的 分类方法，是在 样本分布中找出一个 超平面作为 决策边界，使模型在数据上的分类误差 尽量接近于小，尤其是 在未知数据集上的 分类误差（泛化误差）尽量小。

超平面

        

        在几何中，超平面是一个 空间的 子空间，它是 维度比所在 空间小一维的 空间。在 二分类问题中，如果 一个超平面能够 将数据划分为 两个集合，其中 每个集合中包含 单独的一个类别，我们就说 这个超平面 是数据的 “决策边界”。

        对于一个数据集来说，让 训练误差为 0 的决策边界 可以有 无数条。但这 无法保证 这条决策边界 在未知数据集（测试集）上的 表现 也会优秀。

        对于现有的数据集来说，有 B1 和 B2 两条可能的决策边界。可以把决策边界 B1 向 两边平移，直到 碰到离这条决策边界 最近的方块 和 圆圈后停下，形成两个新的超平面，分别是 b11 和 b12，并且将原始的决策边界移动到 b11 和 b12 的中间，确保 B1 到 b11 和 b12 的距离 相等。在 b11 和 b12 中间的距离，叫做 B1 这条决策边界的 边际 (margin），通常记作 d。

        我们引入 和 原本的数据集 相同分布的 测试样本（红色所示）。可得，拥有 更大边际的 决策边界在 分类中的 泛化误差更小。如果边际很小，则 任何轻微扰动 都会 对决策边界的 分类产生很大的 影响。

        边际很小 的情况，是一种 模型在训练集上 表现很好，却在 测试集上表现糟糕的 情况，所以会 “过拟合”。所以我们 在找寻 决策边界的时候，希望 边际越大越好。支持向量机，就是通过找出边际最大的决策边界，来对数据进行分类的分类器。

二、线性SVM分类原理（求解损失）

        假设数据 中总计有 N 个训练样本，每个 训练样本 i 可以被表示为（xi，yi）（ i=1,2，.… N ），其中 xi 是（ x1i，x2i … xni ）T 这样的一个特征向量，每个 样本总 共含有 n 个特征。二分类标签 yi 的取值是｛-1，1｝。如果 n 等于 2，则有 i =（x1i，x2i，yi）T，分别 由特征向量 和 标签组成。此时 可以在 二维平面上，以 x2 为 横坐标，x1 为纵坐标，y 为颜色，来 可视化所有的 N 个 样本。（ 紫色点的标签为 1，红色点的 标签为 -1）

        在 二维平面上，决策边界（超平面）就是 一条直线。二维平面上的 任意一条线 可以被表示为：

        变换可得：

        其中［a，-1］就是参数向量 w，x 就是 特征向量，b 是 截距。

        在一组数据下，给定固定的 w 和 b，这个式子 就可以是 一条固定直线，在 w 和 b 不确定的状况下，这个表达式 wT x+b=0 就可以 代表平面上的 任意一条直线。如果在 w 和 b 固定时，给定一个唯一的 x 的取值，这个 表达式就 可以表示固定的 一个点。在 SVM 中，就 使用这个表达式 来表示 决策边界。

         我们 目标是求解能够让边际最大化的 决策边界，所以要求解参数向量 w 和 截距 b。

        如果在决策边界上 任意取两个点 xa、xb，并带入决策边界的表达式，则有：

        两式相减得：

        两个向量的点击为 0 表示 两个向量的方向 式互相垂直的。xa-xb 的方向是 平行于他们 所在的直线（决策边界）。而 w 与 xa-xb 相互垂直，所以 参数向量 w 的方向必然是 垂直于决策边界。

        这样任意一个紫色的点 xp，就可以被表示为：

        紫色点所代表的标签 y 是 1，所以规定 p > 0。同样 对于 任意一个 红色的点 xr 而言，可以 将它表示为：

        红色点所表示的标签 y 是 -1，所以规定 r < 0。由此，如果 有新的测试数据 xt，则的 xt 标签就可以 根据以下式子 来判定：

        补充：

        决策边界的 两边要有 两个超平面，这 两个超平面在 二维空间中 就是 两条平行线（虚线超平面），而他们之间的距离就是 边际 d。而 决策边界位于这 两条线的中间，所以 这两条平行线 必然是 对称的。我们另这两条平行线 被表示为：

        变化得：

        这就是 平行于决策边界的 两条线的 表达式，表达式两边 的 1 和 -1 分别 表示了 两条 平行于决策边界 的虚线 到决策边界 的 相对距离。此时，可以 让这 两条线 分别过 两类数据中 距离我们的 决策边界 最近的点，这些点就被称为 “支持向量”，而 决策边界 永远在这 两条线的中间，所以可以 被调整。令紫色类的点为 xt，红色类的点为 xr，则可以得到：

        变化得：

        如下图所示，（xp - xr）可表示为 两点之间的 连线，而边际 d 是 平行于 w 的，所以现在，相当于是 得到了 三角型中的 斜边，并且 知道一条直角边的 方向。

        在线性代数中，可以得到：

        补充：

         要最大化 d，就求解 w 的 最小值。极值问题 可以相互转化，可以把求解 w 的最小值 转化为求解 以下函数的最小值：

         对于任意样本 i，可以把 决策函数 写做：

        整理得：

        将函数间隔作为条件附加到 f（w）上，就得到了 SVM 的损失函数 最初形态：

        这个损失函数分为 两部分：需要最小化的函数，以及 参数求解后 必须满足的 约束条件。这是一个最优化问题。

        损失函数是 二次的（quadratic），并且 损失函数中的 约束条件在参数 w 和 b 下是 线性的，求解这样的 损失函数被称为 “凸优化问题”（comvex optimiztion problem）。拉格明日乘数法正好可以用来 解决凸优化问题，解决 带 约束条件，尤其是带有 不等式的 约束条件的函数的 数学方法。

         首先需要使用 拉格朗日乘数来将损失函数 改写为 考虑了约束条件的 形式：

        此时要求解的 就不只有参数向量 w 和 截距 b 了，也 要求解 拉格朗日乘数 a。而 xi 和 yi 都是已知的 特征矩阵 和 标签。

        对参数求导后让一阶导数等于 0 得：

        由于两个求 偏导结果中都带有 未知的拉格朗日乘数 ai，因此 还是无法求解出 w 和 b 。这里 拉格朗日函数 还可以被转换成一种 只带有 ai，而不带有 w 和 b 的形式，这种 形式被称为 拉格朗日对偶函数。在对偶函数下，就可以 求解出拉格朗日乘数 ai，然后 带入到上面 推导出的（1）和（2）式中来求解 w 和 b 。

        对于 任何一个 拉格朗日函数，都存在一个 与它 对应的 对偶函数g（a），只带有拉格朗日乘数a作为唯一的参数。如果L（x，a）的最优解存在并可以表示为 ，并且对偶函数的最优解也存在并可以表示为 ，则我们可以定义对偶差异（dual gap），即拉格朗日函数的最优解与其对偶函数的最优解之间的差值：

        

        如果上式等于 0，则称 L（x，a）与其对偶函数之间 存在强对偶关系（strong duality property），此时 就可以 通过求解 其对偶函数的 最优解 来替代 求解原始函数的 最优解。强对偶关系只在 这个 拉格朗日函数满足 KKT（Karush-Kuhn-Tucker）条件下存在：

        

        当所有限制 都被满足，则 拉格朗日函数 L（x，a）的 最优解与 其对偶函数的 最优解相等，就可以 将原始的 最优化问题转换 成为 对偶函数的 最优化问题。而 不难注意到，对于 损失函数      L（w,b,a）而言，KKT条件 都是 可以操作的。如果能够人为 让 KKT条件 全部成立，就可以 求解出L（w,b,a）的对偶函数来解出 a。

        

        函数 Ld 就是对偶函数。对所有 存在 对偶函数的 拉格朗日函数 有对偶差异 如下表示：

        则对于 L（w，b，a）和 Ld，则有：

        求解 对偶函数的 过程其实是在 求解 L（w,b,a）的最小值，所以 又可以把公式写成：

        如此，只需要 求解 对偶函数的 最大值，就可以求出 a 了。最终 目标函数变化为：

        接下来就需要 使用 梯度下降，SMO 或者 二次规划（QP，quadratic programming）来求解 a，一旦求得了 a 值，就可以使 用求导后 得到的（1）式求解 w，并可以使用（1）式 和 决策边界的表达式 结合 求解出 b。

        当求得特征向量 w 和 b，就得到了 决策边界的表达式，也就 可以利用 决策边界和其 有关的超平面来 进行分类了，决策函数就可以被写作：

        其中 xtest 是任意测试样本，sign（h）是h＞0 时 返回 1，h＜0 时 返回 -1 的符号 函数。

三、重要参数

1. kernel（核函数）

        当数据在原始特征空间中 线性不可分时，就需要 通过某种方式 将数据映射 到一个 更高维的空间中，使得 在这个新空间中数据 变得线性可分。核函数正是 用来实现 这种映射的。它 并不直接对数据 进行映射，而是 定义了 一个计算 两个样本点之间 相似度（或内积）的函数。在 SVM 的训练过程中，核函数被 用来计算 样本点之间的 相似度，从而 在高维空间中 寻找最优的 超平面。选用不同的核函数，就可以解决不同数据分布下的寻找超平面问题。

2 .C（硬间隔与软间隔）

        可以通过调整对决策边界的定义，将 硬间隔时得出的 数学结论 推广到 软间隔的情况上，让决策边界能 够忍受一小部分训练误差。这时候 决策边界就 不是单纯地 寻求 最大边际了，因为 对于软间隔地 数据来说，边际越大 被分错的 样本也 就会越多，因此 需要 找出一个 “最大边际” 与 “被分错的样本数量” 之间的平衡。

        上图原始判别函数为：

        这些超平面现在 无法让数据上的 训练误差 等于 0 了，因为 此时 存在了 一个 混杂在红色点 中的紫色点 xp。于是，需要 放松 原始判别函数中的 不等条件，来 让决策边界 能够 适用于 我们的异常点，于是 引入松弛系数 来帮助我们 优化原始的判别函数：

        损失函数为：

        其中 C 是 用来 控制惩罚项的 惩罚力度的系数。

四、sklearn中的支持向量机（自查）

1. 种类

2. 参数列表（SVC）

3. 属性列表（SVC）

4. 接口列表（SVC）