SVM理论与算法分析

硬间隔线性支撑向量机 假设给定一个特征空间上的训练数据集 1 1 2 2 其中 为第 i 个特征向量或实例 为 的类标记 当 时 称 为 1 1 1 2 1 正例 当 时 称 为负例 为样本点 1 假设训练数据集是线性可分的 存在硬间隔 那么学习的目标是在特征空间找到一个分离超平面 能将实 例分到不同的类 分离超平面方程 它由法向量 w 和截距 b 决定 可用 表示 分离超平面 0 将特征空间分为两部分 一部分是正类 一部分是负类 法向量指向的一侧为正类 另一侧是负类 一般地 当训练数据集线性可分时 存在无穷个分离超平面可将两类数据正确分开 感知机利用误分类最小 的策略 求得分离超平面 不过这是的解有无穷多 线性可分支撑向量机利用间隔最大化求最优分离超平面 解唯一 一 模型推导 1 函数间隔 一般来说 一个点距离分离超平面的远近可以表示分类预测的确信程度 在超平面 确定的情况下 能够相对地表示 注意 真实距离为 点 距离超平面的远近 0 而 的符号与类标记 的符号是否一致能够表示分类是否正确 所以可用标量 来表示分类的 正确性及确信度 值为正表示分类正确 值为负表示分类错误 超平面 关于样本点 的函数间隔为 超平面 关于训练数据集 T 的函数间隔 min 1 2 min 1 2 2 几何间隔 函数间隔可以表示分类预测的正确性及确信度 但是选择分离超平面时 只有函数间隔还不够 因为只要成比例地改变 w 和 b 虽然超平面并没有改变 但函数间隔 它是 的线性函数 却依原比例同 等改变 为了将 表示的超平面的唯一化 即每个超平面对应 中的唯一向量 可以对法向量 w 1 加以规范化约束 这时函数间隔称为几何间隔 1 超平面 关于样本点 的几何间隔为 超平面 关于训练数据集 T 的几何间隔为 min 1 2 min 1 2 3 间隔最大化 支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面 对于线性可分 的训练数据集而言 线性可分分离超平面有无穷多个 每一个都是一个感知机 但是几何间隔最大的分离超 平面时唯一的 间隔最大化的直观解释是 对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进 行分类 也就是说 不仅将正负实例点要分开 而且对最难分的实例点 离超平面最近的点 也有足够多大 的确信度将它们分开 因此所要优化的问题 表示为 max 1 2 改写为 max 1 2 的取值不影响最优化问题的解 如果 是最优解 那么 也是最优解 因此 是变动的可以取到 任意值 如果固定 也就变得唯一了 令 等价变换为 1 max 1 1 1 2 目标函数是支撑间隔 约束是样本点在间隔边界或外侧 目标是寻找支撑向量使得间隔最大化 等价变换 为 标准无等式约束的凸二次规划 这是为了运算方便 min 12 2 1 0 1 2 凸二次规划问题存在全局最优解 4 分离超平面与分类决策函数 分离超平面 0 分类决策函数 5 支撑向量与间隔边界 在线性可分情况下 训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量 支撑向量 是使约束条件等号成立的点 即 对于正例点 支撑向量在超平面 上 对于1 0 1 负例点 支撑向量在超平面 上 没有实例点落在这两个平行的超平面 间隔边界 之间 这两 1 个超平面之间的距离称为间隔 它依赖于分离超平面的法向量 w 等于 2 在决定分离超平面时只有支持向量起作用 而其他实例点并不起作用 如果移动支持向量将改变所求的解 但是如果在间隔边界以外移动其他实例点 甚至去掉这些点 则解是不会改变的 显然支撑向量是训练集中 重要的样本 二 模型求解 将原始问题转化为 Lagrange 对偶问题 通过求解对偶问题来获得原始问题的最优解 对每个不等式约束引 入 Lagrange 乘子 1 Lagrange 对偶函数 12 2 1 1 其中 为拉格朗日乘子向量 1 2 0 1 2 2 对偶问题 max min 1 求 min 1 0 1 0 得出 1 1 0 带入拉格朗日函数 得出 min 12 1 1 1 1 1 12 1 1 1 2 求 max min max 12 1 1 1 1 0 0 1 2 转换为求极小 min 12 1 1 1 1 0 0 1 2 根据对偶理论 对上述对偶优化存在 使 是原始问题的解 是对偶问题的解 因此求解原始问题 可以转化为求解对偶问题 3 最优解 根据 KKT 条件 a 1 0 b 1 0 c 1 0 1 2 d 1 0 1 2 e 0 1 2 由 a 求得 1 其中至少有一个 如果 那么 无解 显然它不是原始最优化问题的解 结合 KKT 0 0 0 条件 c 得出 1 0 将 带入 KKT 条件 得出 1 1 两边同时乘以 由于 2 1 1 1 1 因此分类决策函数为 1 从 中可以看出它们仅仅依赖于 的特征点 即支撑向量 因为 0 所有 在分隔边界上 1 0 1 软间隔线性支撑向量机 一 模型推导 如果样本集中存在特异点使得样本集线性不可分 即不能满足函数间隔大于等于 1 不等式约束条件 为了解 决这个问题 可以对每个样本点 引入一个松弛变量 使函数间隔加上松弛变量大于等于 1 这样 0 约束条件变为 1 同时对每个松弛变量 支付一个代价 目标函数变成 min 12 2 1 这里 称为惩罚参数 一般由应用问题决定 C 值大时对误分类的惩罚增大 C 值小时对误分类的惩罚 0 减小 最小化上述目标函数有两层含义 要使的 尽量小即间隔尽量大 同时使的误分类的点的个数尽 12 2 量小 C 是调和二者的系数 这时的间隔称为软间隔 因为间隔内含义特异点 原始优化问题 min 12 2 1 1 0 1 2 0 1 2 这仍是一个二次凸优化 存在全局最优解 w 的解是唯一的 但 b 的解不唯一 b 的解存在于一个区间 二 模型求解 仍使用 Lagrange 对偶方法求解 1 Lagrange 函数 12 2 1 1 1 1 其中 0 0 2 对偶问题 max min 1 求 min 1 0 1 0 1 0 得出 1 1 0 0 带入拉格朗日函数 得出 min 12 1 1 1 注意它与 无关 2 求 max min max 12 1 1 1 1 0 0 1 2 0 1 2 0 1 2 消去 转换为求极小 min 12 1 1 1 1 0 0 1 2 0 3 最优解 根据 KKT 条件 a 1 0 b 1 0 c 1 0 d 1 0 1 2 e 0 1 2 f 0 1 2 g 1 0 1 2 h 0 1 2 i 0 1 2 由 a 求得 1 由 c e i 得出 0 0 再结合 f 得出 如果 那么 如果 j 0 1 0 0 1 由 j k 得出 如果 那么 因此 0 0 1 0 1 1 由 j g 得出 如果 那么 这说明 0 0 1 位于 间 隔 边 界上或以外 由 j k 得出 如果 那么 1 0 此种情况下 进一步讨论 如果 那么 在间隔边界上 0 如果 那么 分类正确 在间隔边界与分离超平面之间 0 1 因此可以看出 软间隔的支撑向量 或者在间隔边界上 或者在间隔边界与分离超平面之间 或 0 者在分离超平面误分一侧 3 支撑向量的另一种解释 最小化以下目标函数 1 1 2 第一项是经验损失或经验风险 函数称为合页损失函数 下标 表 1 示以下取正值得函数 0 0 0 也就是说 当样本点被正确分类且函数间隔大于 1 时 损失函数为 0 否则 为支撑向量时 损失函数是 第二项是系数为 的 w 的 范数 是正则化项 这两种优化是等价的 通过变量替换方法 1 L2 非线性支撑向量机 对于分类问题是非线性的 线性模型无法将正负实例正确分开 可以利用核技巧 进行一个非线性变换 将非线性问题变换为线性问题 通过解变换后的线性问题的方法求解原来的非线性问题 用线性分类方法求解非线性分类问题问题分两步 首先使用一个变换将原空间的数据映射到新空间 然后再 新空间里用线性分类学习方法从训练数据中学习分类模型 核技巧应用到支持向量机 其基本思想 通过一个非线性变换将输入空间 欧氏空间 或离散集合 对应于一个特征空间 希尔伯特空间 H 使得在输入空间 中的超曲面模型对应于特征空间 H 中的超平面模型 支撑向量机 这样分类问题的学习 任务通过在特征空间中求解线性支撑向量机就可以完成 一 非线性支撑向量机 在线性支撑向量机的对偶问题中 无论是目标函数还是决策函数 分离超平面 都只涉及输入实例与实 例之间的內积 如果把这个內积 看作是希尔伯特空间中的两个特征的內积 其中 那么对于在低维线性不可分的样本集 如果通过映射 变换到高 1 2 维希尔伯特空间 变得线性可分 假设能找到这样的合适的映射 那么就可以使用核函数 1 2 代替计算 这里 未知 但 已知 使用核函数后的对偶问题的目标函数成为 12 1 1 1 最优解成为 1 1 分类决策函数成为 1 在实际应用中 往往依赖领域知识直接选择核函数 核函数选择的有效性需要通过实验验证 二 核函数方法 核函数 设 X 是输入空间 欧氏空间 的子集或离散集合 H 为特征空间 希尔伯特空间 如果存在一 个从 X 到 H 的映射 使得对所有 函数 满足条件 则称 为核函数 为映射函数 为 和 內积 希尔伯特空间是完备化的內积空间 其中的每个元素是一个向量 可以无穷维 向量之间定义有內积运 算 且空间关于內积诱导出的范数是完备的 核技巧的想法是 在学习与预测中只定义核函数 而不显示地定义映射函数 因为通常直接计算 比较容易 而通过 和 计算 并不容易 注意 是输入空间 到特征空间 H 的映射 特 征空间 H 一般是高维的 甚至是无穷维的 我们需要的是特征空间中两个特征的內积结果 而不是特征的表 示 如果我们能通过简单的函数 得到 的內积 那就简化了问题 不用考虑 的形式 这正是 核函数的妙用之处 对于给定的核函数 特征空间 H 希尔伯特子空间 和映射函数 的取法不唯一 因为核函数给出 的是映射后的內积结果 所选取的映射过程可能是不同的 核函数判定定理 设 是对称函数 则 为正定核函数的充要条件是对任意 对应的 Gram 矩阵 是半正定的 1 2 对于一个具体函数 来说 检验它是否为正定核函数并不容易 因为要去对任意有限输入集验证 K 对应 的 Gram 矩阵是否为半正定 在实际问题中往往应用已有的核函数 常用核函数 1 多项式核函数 对应的支撑向量机是一个 p 次多项式分类器 1 2 高斯核函数 对应的支撑向量机是高斯径向基函数分类器 22 2 3 字符串核函数 1 基本定义 有限字符表 字符串 s 字符串 s 的长度 空字符串长度为 0 1 2 字符串连接 s 和 t 分别是字符串 长度为 n 的字符串集合 所有字符串的集合 0 s 的子串 u 给定一个指标序列 其长度 1 2 1 1 2 2 映射定义 假设 S 是长度大于或等于 n 字符串的集合 s 是 S 的元素 建立字符串集合 S 到特征空间 的映射 表示定义在 上的实数空间 其每一维对应一个字符串 映射 将字符串 s 对应于空间 中 的一个向量 其在 u 维上的取值为 这里 是一个衰减参数 表示字符串 i 的长度 求和在 s 中所有与 u 相同的子串上进行 0 2 2 由 得出 1 1 2 2 1 1 2 2 1 1 1 2 2 1 1 1 2 2 1 1 1 2 2 2 2 变量的 启发式 选择方法 SMO 算法在每个子问题中选择两个变量优化 其中至少一个变量是违反 KKT 条件的 1 第一个变量的选择 SMO 称选择第 1 个变量的过程为外层循环 外层循环在训练样本中选取违反 KKT 条件最严重的样本点 并 将其对应的变量作为第 1 个变量 具体地 检验训练样本点 是否满足 KKT 条件 即 具体推导见软 间隔 SVM 文章 如果 那么 0 0 1 如果 那么 因此 0 0 1 0 1 如果 那么 1 0 0 1 1 0 1 1 1 1 该检验是在 范围内进行的 在检验过程中 外层循环首先遍历所有满足条件 的样本点 即在间隔 0 边界上的支撑向量点 检验它们是否满足 KKT 条件 如果这些样本点都满足 KKT 条件 那么遍历整个训练集 检验它们是否满足 KKT 条件 2 第二个变量的选择 SMO 称选择第 2 个变量的过程为内层循环 假设在外层循环中已经找到第 1 个变量 现在要在内层循环中 1 找第 2 个变量 第 2 个变量的选择的标准是希望能使 有足够大的变化 这样新的 也会有足够大的变化 2 2 1 从而尽快趋向满足 KKT 条件的值 从上面的推导中可以发现 依赖于 为了加快计算速度 一种简单的做法是选择 使其对应 2 1 2 2 的 最大 因为 已定 也是确定的 如果 是正 那么选择最小的 作为 如果如果 是负 1 2 1 1 1 2 1 那么选择最大的 作为 为了节省时间 将所有的 值保存在一个列表中 2 在特殊情况下 如果内层循环通过以上方法选择的 不能使目标函数有足够的下降 那么采用以下启发式规 2 则继续选择 遍历在间隔边界上的支撑向量点 依次将其对应的变量作为 试用 直到目标函数有足够的 2 2 下降 若找不到合适的 那么遍历训练数据集 若仍找不到合适的 则放弃第 1 个 再通过外层循环 2 2 1 寻求另外的 1 3 计算阈值 b 和差值 每次完成两个变量的优化后 都要重新计算阈值 b 和 使用迭代的方法更新 b 根据定义预测误差 展开得 1 1 1 1 1 3 1 1 1 1 11 2 2 21 f 1 1 3 1 1 1 11 2 2 21 下面讨论如何迭代更新 b 即获得 显然每次更新完 后 的选择应该使得 KKT 条件成立 1 2 a 如果 时 由 KKT 条件可知 0 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 11 2 2 21 1 3 1 1 1 1 11 2 2 21 带入 f 得出 1 1 1 1 11 2 2 21 1 1 11 2 2 21 g 1 1 1 11 1 1 2 21 2 2 同样 如果 那么0 2 h 2 2 1 12 1 1 2 22 2 2 b 如果 时 由 KKT 条件可知 1 0 1 1 1 1 1 3 1 1 1 11 2 2 21 1 带入 f 得出 1 1 1 1 1 11 2 2 21 1 1 11 2 2 21 1 1 1 1 1 11 1 1 2 21 2 2 1 1 1 1 1 11 1 1 2 21 2 2 同样 如果 时 那么 2 0 2 2 2 1 12 1 1 2 22 2 2 C 如果 时 由 KKT 条件可知 1 1 1 1 1 1 3 1 1 1 11 2 2 21 1 带入 f 得出 1 1 1 1 1 11 2 2 21 1 1 11 2 2 21 1 1 1 1 1 11 1 1 2 21 2 2 1 1 1 1 1 11 1 1 2 21 2 2 同样 如果 时 那么 2 2 2 2 1 12 1 1 2 22 2 2 综上可以得出结论 如果 那么取 可以证明两者相等 0 1 或 0 2 1或 2 否则如果 那么 这种情况应该排除 1 2 0或 1 2 0或 因此 如果 中一个是 0 另一个是 C 那么 和 以及它们之间的数都是符合 KKT 1 2 1 2 1 2 条件的阈值 这时选择它们的中点作为 在每次完成两个变量的优化后 还必须更新对应的 值 并将它们保存在列表中 值得更新要用到 值 以及所有支撑向量对应的 其中 S 是所有支撑向量 的集合 由于非支撑向量对用的 因此在 S 上求和与在整个样本集上是一致 0 的 序列最小最优化 SMO 算法实现 输入 训练数据集 其中 1 1 2 2 精度 C 1 1 1 2 输出 近似解 1 取初值 令 0 0 0 2 选取优化变量 1 1 1 2 1 选择第 1 个变量 在 范围内在训练样本中选取违反 KKT 条件最严重的样本点 首先遍历满足 1 1 条件 的所有样本点 如果它们都满足 KKT 条件 那么遍历整个训练集 0 a 0 1 1 b 0 1 1 c 1 1 2 选择第二个变量 如果 是正 那么选择最小的 作为 如果如果 是负 那么选择最大 1 2 1 2 1 的 作为 在特殊情况下 如果以上方法选择的 不能使目标函数有足够的下降 那么遍历在间隔边 2 2 界上的支撑向量点 依次将其对应的变量作为 试用 直到目标函数有足够的下降 若找不到合适的 2 2 那么遍历训练数据集 若仍找不到合适的 则放弃第 1 个 返回 1 重新选择 2 1 1 3 计算阈值 b 和差值 1 的计算 1 1 1 11 1 1 2 21 2 2 2 2 1 12 1 1 2 22 2 2 如果 那么 0 1 或 0 2 2 2 1 1 1 2 2 2 其中 如果 那么 如果 2 1 0 1 2 2 1 2 那么 2 1 0 2 1 2 1 2 3 更新 为 1 5 若在精度 范围内满足下列停机条件 则转 6 否则令 转 2 1 1 1 0 2 0 1 2 3 其中 1 1 1 0 0 1 6 取 1