《SVM支持向量机算法的详细推导(详细到每个步骤,值得推荐).pdf》由会员分享，可在线阅读，更多相关《SVM支持向量机算法的详细推导(详细到每个步骤,值得推荐).pdf（44页珍藏版）》请在金锄头文库上搜索。
1、人工神经网络及应用人工神经网络及应用 主讲 何东健 第八章第八章 支持向量机支持向量机 BP网络及RBF网络解决了模式分类与非线性映射问题 Vapnik提出的支持向世机 Support Vector Machine SVM 同样可以解决模式分类与非线性映射问题 从线性可分模式分类角度看 SVM的主要思想是 建立建立 一个最优决策超平面 一个最优决策超平面 使得该平面两侧距平面最近的两类使得该平面两侧距平面最近的两类 样本之间的距离最大化样本之间的距离最大化 从而对分类问题提供良好的泛化 从而对分类问题提供良好的泛化 能力能力 根据cover定理 将复杂的模式分类问题非线性地 投射到高维特征空间
2、可能是线性可分的 因此只要特征空 间的维数足够高 则原始模式空间能变换为一个新的高维 特征空间 使得在特征空间中模式以较高的概率为线性可 分的 此时 应用支持向量机算法在特征空间建立分类超 平面 即可解决非线性可分的模式识别问题 支持向量机基于统计学习理论的原理性方法 因此需要 较深的数学基础 下面的阐述避免过多抽象的数学概念 推导过程尽量详细 8 1 支持向量机的基本思想 线性可分数据的二值分类机理 系统随机产生一个 超平面并移动它 直到训练集中属于不同类别的样本 点正好位于该超平面的两侧 显然 这种机理能够解 决线性分类问题 但不能够保证产生的超平面是最优超平面是最优 的的 支持向量机建立
3、的分类超平面能够在保证分类精在保证分类精 度的同时 使超平面两侧的空白区域最大化 从而实度的同时 使超平面两侧的空白区域最大化 从而实 现对线性可分问题的最优分类现对线性可分问题的最优分类 什么叫线性可分线性可分 就是可以用一条或几条直线把属 于不同类别的样本点分开 实际上 求解分类问题 实际上 求解分类问题 就是要求出这条或这几条直线 就是要求出这条或这几条直线 问题是 怎么求 进一步理解支持向量机 进一步理解支持向量机 支持向量机 Support Vector Machine SVM 中的 机 机 machine 机器 机器 实际上是一个算法 在机器学习领域 常把一些实际上是一个算法 在机
4、器学习领域 常把一些 算法算法看作是一个机器 又叫看作是一个机器 又叫学习机学习机器 或器 或预测函数预测函数 或或学习函数学习函数 支持向量 支持向量 则是指训练集中的某些训练点则是指训练集中的某些训练点 这些点这些点 最靠近分类决策面 是最难分类的数据点最靠近分类决策面 是最难分类的数据点 SVM 它是一种有监督 有导师 学习方法 即它是一种有监督 有导师 学习方法 即已知已知 训练点的类别训练点的类别 求训练点和类别之间的对应关系求训练点和类别之间的对应关系 以 以 便将训练集按照类别分开 或者是预测新的训练点所便将训练集按照类别分开 或者是预测新的训练点所 对应的类别 对应的类别 SV
5、M主要针对主要针对小样本数据进行学习 分类和预测小样本数据进行学习 分类和预测 有时也叫回归 的一种方法 能解决神经网络不能 有时也叫回归 的一种方法 能解决神经网络不能 解决的解决的过学习问题过学习问题 类似的根据样本进行学习的方法 类似的根据样本进行学习的方法 还有基于案例的推理 还有基于案例的推理 Case Based Reasoning 决策树归纳算法等 决策树归纳算法等 过学习问题 过学习问题 训练误差过小导致推广能力下降 即真 实风险的增加 推广能力 推广能力 generalization ability 也可以说是泛化能泛化能 力力 就是对未知样本进行预测时的精确度 下面讨论线性
6、可分情况下支持向量机的分类原理 8 1 1 最优超平面的概念最优超平面的概念 考虑P个线性可分样本 X1 d1 X2 d2 Xp dp XP dP 对于任一输入样本Xp 期望输出 为dp 1 代表两类类别标识 用于分类 的超平面方程为 WT X b 0 8 1 式中 X为输入向量 W为权值向量 b为偏置偏置 相当 于前述负阈值负阈值 则有 WT XP b 0 dp 1 WT XP b0 以上为不等式约束的二次函数极值问题不等式约束的二次函数极值问题 Quadratic Programming QP 由Kuhn Tucker定理知 式 8 14 的最优解必须满足以下最优化条件 KKT条件 8 1
7、4 上式等号成立的两种情况 一是 p为零 另一种是 WT XP b dp 1 第二种情况仅对应于样本为支持向量对应于样本为支持向量 设Q 的最优解为 01 02 0p 可通过式 8 12 计算最优权值向量 其中多数样本的Lagrange系数为零 因此 即最优超平面的最优超平面的权向量权向量是是训练样本向量的线性组合训练样本向量的线性组合 且 且 只有支持向量影响最终的划分结果只有支持向量影响最终的划分结果 如果去掉其他训练 如果去掉其他训练 样本重新训练 得到分类超平面相同样本重新训练 得到分类超平面相同 但如果一个支持 向量未能包含在训练集内时 最优超平面会被改变 8 16 利用计算出的最优
8、权值向量和一个正的支持向量 可 通过式 8 5 进一步计算出最优偏置计算出最优偏置 b0 1 W0T Xs 8 17 求解线性可分问题得到的最优分类判别函数最优分类判别函数为 在上式中的P个输入向量中 只有若干个支持向量的 Lagrange系数不为零 因此计算复杂度取决于支持向 量的个数 对于线性可分数据 该判别函数对训练样本的分类 误差为零 而对非训练样本具有最佳泛化性能 8 18 8 1 3 非线性可分数据最优超平面的构建 若将上述思想用于非线性可分模式的分类时 会有一 些样本不能满足dp WT XP b 1的约束 而出现分类 误差 因此需要适当放宽该式的约束 将其变为 式中引入了松弛变量
9、松弛变量 p 0 用于度量一个数据点对线度量一个数据点对线 性可分理想条件的偏离程度性可分理想条件的偏离程度 当0 p 1时 数据点数据点 落入分离区域的内部落入分离区域的内部 且在分类超平面的正确一侧且在分类超平面的正确一侧 当 p 1时 数据点进入分类超平面的错误一侧时 数据点进入分类超平面的错误一侧 当 p 0时 相应的数据点即为精确满足式 8 6 的支持向量 Xs 8 19 dp WT XP b 1 建立非线性可分数据的最优超平面非线性可分数据的最优超平面可以采用与线性可 分情况类似的方法 即对于给定的训练样本 X1 d1 X2 d2 Xp dp XP dP 寻找权值W和 阈值B的最优
10、值 使其在式 8 19 的约束下 最小化关 于权值W和松弛变量 p 的代价函数 C是选定的正参数 与前述方法相似 采用Laglange系数方法解决约束最 优问题 需要注意的是 在引入Lagrange函数时 使 式 8 10 中的1被1 p代替 从而使Lagrange函数变为 对式 8 21 采用与前类似推导 得到非线性可分数据非线性可分数据 的对偶问题的对偶问题的表示为 给定训练样本 求解使以下目 标函数 为最大值的Lagrange系数 1 2 p 并满足以 下约束条件 8 21 可以看出在上述目标函数中 松弛变量 p和它们的 Lagrange系数都未出现 因此线性可分的目标函数线性可分的目标
11、函数与 非线性可分非线性可分的目标函数表达式完全相同目标函数表达式完全相同 不同的只是 线性可分情况下的约束条件 p 0 在非线性可分情况 下被替换为约束更强的 0 p C 因此线性可分情况 下的约束条件 p 0可以看作非线性可分情况下的一种 特例 此外 W和b的最优解必须满足的Kuhn Tucker最优 化条件改变为 最终推导得到的W和b的最优解计算式以及最优分类判 别函数与式 8 16 8 17 和 8 18 完全相同 8 2 非线性支持向量机 对非线性可分模式分类 SVM的方法是 将输入向量将输入向量 映射到一个高维特征向量空间映射到一个高维特征向量空间 如果选用的映射函数映射函数 适当
12、适当且特征空间的维数足够高特征空间的维数足够高 则大多数非线性可分非线性可分 模式在特征空间中在特征空间中可以转化为线性可分线性可分模式 因此可 以在该特征空间构造最优超平面构造最优超平面进行模式分类 这个 构造与内积核内积核相关 8 2 1 基于内积核的最优超平面 设X为N维输入空间的向量 令 X 1 X 2 X M X T表示从输入空间到M维特征空间 的非线性变换 称为输入向量输入向量X在特征空间诱导出的在特征空间诱导出的 像 像 照前思路 可在该特征空间构建一个分类超 平面 式中的wj为将特征空间连接到输出空间的权值 b为偏 置或负阈值 令 0 x 1 w0 b 上式可简化为 或 将适合
13、线性可分模式输入空间的式 8 12 用于特征空 间中线性可分的 像像 只需用 X 替换X 得到 8 26 将上式代入式 8 26 可得特征空间的分类超平面为 式中 T XP X 表示第p个输入模式XP在特征空间 的像 XP 与输入向量X在特征空间的像 X 的内积内积 因此在特征空间构造最优超平面时 在特征空间构造最优超平面时 仅使用特征空间仅使用特征空间 中的内积中的内积 若能找到一个函数K 使得 则在特征空间建立超平面时在特征空间建立超平面时无需考虑变换无需考虑变换 的形式的形式 K X XP 称为内积核函数内积核函数 8 28 p 8 29 泛函分析中的Mercer定理给出作为核函数的条件
14、 K X X 表示一个连续的对称核 其中X定义在闭区间 a X b X 类似 核函数K X X 可以展开为级数 式中所有 i 0 保证式 8 30 一致收敛的充要条件充要条件是 对于所有满足 可以看出式 8 29 对于内积核函数K X XP 的展开是 Mercer定理的一种特殊情况 Mercer定理指出如何确 定一个候选核是不是某个空间的内积核 但没有指出 如何构造函数 i X 8 30 对核函数K X XP 的要求是满足Mercer定理 因此其 选择有一定的自由度 下面给出4种常用的核函数 1 线性核函数 K X Xp X Xp 2 多项式核函数 采用该函数的支持向量机是一个q阶多项式分类器
15、 其 中q为由用户决定的参数 3 Gauss核函数 采用该函数的支持向量机是一种径向积函数分类器径向积函数分类器 4 Sigmoid核函数 K X XP tanh k X XP c tanh x ex e x ex e x 双曲正切函数 采用该函数的支持向量机实现的是一个单隐层感知器神经单隐层感知器神经 网络网络 使用内积核在特征空间建立的最优超平面定义为 8 2 2 8 2 2 非线性支持向量机神经网络非线性支持向量机神经网络 支持向量机的思想是 对于非线性可分数据 在进行非 线性变换后的高维特征空间实现线性分类 此时最优分类 判别函数为 令支持向量的数量为Ns 去除系数为零的项 上式可改写
16、 为 从支持向量机分类判别函数的形式上看 它类似于一个类似于一个3 层前馈神经网络层前馈神经网络 其中隐层节点对应于输入样本与一个支隐层节点对应于输入样本与一个支 持向量的内积核函数持向量的内积核函数 而输出节点输出节点对应于隐层输出的线性 组合 图8 2给出支持向量机神经网络的示意图 设计一个支持向量机时 只需选择满足Mercer条件的核 函数而不必了解将输入样本变换到高维特征空间的 的形式 但下面给出的简单的核函数实际上能够构建非线 性映射 支持向量机神经网络 设输入数据为二维平面的向量X x1 x2 T 共有3 个支持向量 因此应将二维输入向量非线性映射为三 维空间的向量 x 1 x 2 x 3 x T 选择K Xi Xj xi T Xj 使映射 从R2 R3满足 对于给定的核函数 映射 和特征空间的维数都不 是唯一的 例如 对于本例的情况可选 X x12 2 x 3 x T 或 X 1 x 2 x 3 x T 8 3 支持向量机的学习算法 在能够选择变换选择变换 取决于设计者在这方面的知识 的情况下 用支持向量机进行求解的学习算法如下 1 通过非线性变换 将输入向量映射到高维特
