支持向量机(SVM)原理及应用概述.doc

东北大学东北大学 研究生考试试卷研究生考试试卷 评分 考试科目 信号处理的统计分析方法 课程编号 09601513 阅 卷 人 刘 晓 志 考试日期 2012 年 11 月 07 日 姓 名 赵 亚 楠 学 号 1001236 注 意 事 项 1 考前研究生将上述项目填写清楚 2 字迹要清楚 保持卷面清洁 3 交卷时请将本试卷和题签一起上交 4 课程考试后二周内授课教师完成评卷工作 公共课成绩单与试卷交研究生院培养办公室 专业课成绩单与试卷交各学院 各学院把成绩单交研究生院培养办公室 东北大学研究生院培养办公室 支持向量机 支持向量机 SVM 原理及应用 原理及应用 目录目录 一 SVM 的产生与发展 3 二 支持向量机相关理论 4 一 统计学习理论基础 4 二 SVM原理 4 1 最优分类面和广义最优分类面 5 2 SVM的非线性映射 7 3 核函数 8 三 支持向量机的应用研究现状 9 一 人脸检测 验证和识别 10 二 说话人 语音识别 10 三 文字 手写体识别 11 四 图像处理 11 五 其他应用研究 12 四 结论和讨论 12 支持向量机 支持向量机 SVM 原理及应用原理及应用 一 一 SVM 的产生与发展的产生与发展 自1995年Vapnik在统计学习理论的基础上提出SVM作为模式识别的新方法之后 SVM一直 倍受关注 同年 Vapnik和Cortes提出软间隔 soft margin SVM 通过引进松弛变量度量 i 数据的误分类 分类出现错误时大于0 同时在目标函数中增加一个分量用来惩罚非零 i x i 松弛变量 即代价函数 SVM的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程 1996年 Vapnik等人又提出支持向量回归 Support Vector Regression SVR 的方法用于 解决拟合问题 SVR同SVM的出发点都是寻找最优超平面 但SVR的目的不是找到两种数据的 分割平面 而是找到能准确预测数据分布的平面 两者最终都转换为最优化问题的求解 1998年 Weston等人根据SVM原理提出了用于解决多类分类的SVM方法 Multi Class Support Vector Machines Multi SVM 通过将多类分类转化成二类分类 将SVM应用于多分类问题 的判断 此外 在SVM算法的基本框架下 研究者针对不同的方面提出了很多相关的改进算 法 例如 Suykens提出的最小二乘支持向量机 Least Square Support Vector Machine LS SVM 算法 Joachims等人提出的SVM 1ight 张学工提出的中心支持向量机 Central Support Vector Machine CSVM Scholkoph和Smola基于二次规划提出的v SVM 等 此后 台湾大学林智仁 Lin Chih Jen 教授等对SVM的典型应用进行总结 并设计开发 出较为完善的SVM工具包 也就是LIBSVM A Library for Support Vector Machines 上述 改进模型中 v SVM是一种软间隔分类器模型 其原理是通过引进参数v 来调整支持向量数 占输入数据比例的下限 以及参数来度量超平面偏差 代替通常依靠经验选取的软间隔分 类惩罚参数 改善分类效果 LS SVM则是用等式约束代替传统SVM中的不等式约束 将求解 QP问题变成解一组等式方程来提高算法效率 LIBSVM是一个通用的SVM软件包 可以解决分 类 回归以及分布估计等问题 它提供常用的几种核函数可由用户选择 并且具有不平衡样 本加权和多类分类等功能 此外 交叉验证 cross validation 方法也是LIBSVM对核函数参 数选取问题所做的一个突出贡献 SVM 1ight的特点则是通过引进缩水 shrinking 逐步简化 QP问题 以及缓存 caching 技术降低迭代运算的计算代价来解决大规模样本条件下SVM学习 的复杂性问题 二 支持向量机相关理论二 支持向量机相关理论 一 统计学习理论基础 一 统计学习理论基础 与传统统计学理论相比 统计学习理论 Statistical learning theory或SLT 是一种专 门研究小样本条件下机器学习规律的理论 该理论是针对小样本统计问题建立起的一套新型 理论体系 在该体系下的统计推理规则不仅考虑了对渐近性能的要求 而且追求在有限信息 条件下得到最优结果 Vapnik等人从上世纪六 七十年代开始致力于该领域研究 直到九十 年代中期 有限样本条件下的机器学习理论才逐渐成熟起来 形成了比较完善的理论体系 统计学习理论 统计学习理论的主要核心内容包括 1 经验风险最小化准则下统计学习一致性条件 2 这些条件下关于统计学习方法推广性的界的结论 3 这些界的基础上建立的小样本归纳 推理准则 4 发现新的准则的实际方法 算法 二 二 SVM 原理原理 SVM方法是20世纪90年代初Vapnik等人根据统计学习理论提出的一种新的机器学习方法 它以结构风险最小化原则为理论基础 通过适当地选择函数子集及该子集中的判别函数 使 学习机器的实际风险达到最小 保证了通过有限训练样本得到的小误差分类器 对独立测试 集的测试误差仍然较小 支持向量机的基本思想是 首先 在线性可分情况下 在原空间寻找两类样本的最优分 类超平面 在线性不可分的情况下 加入了松弛变量进行分析 通过使用非线性映射将低维 输入空间的样本映射到高维属性空间使其变为线性情况 从而使得在高维属性空间采用线性 算法对样本的非线性进行分析成为可能 并在该特征空间中寻找最优分类超平面 其次 它 通过使用结构风险最小化原理在属性空间构建最优分类超平面 使得分类器得到全局最优 并在整个样本空间的期望风险以某个概率满足一定上界 其突出的优点表现在 1 基于统计学习理论中结构风险最小化原则和VC维理论 具有 良好的泛化能力 即由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的 误差 2 支持向量机的求解问题对应的是一个凸优化问题 因此局部最优解一定是全局最 优解 3 核函数的成功应用 将非线性问题转化为线性问题求解 4 分类间隔的最大化 使得支持向量机算法具有较好的鲁棒性 由于SVM自身的突出优势 因此被越来越多的研究 人员作为强有力的学习工具 以解决模式识别 回归估计等领域的难题 1 最优分类面和广义最优分类面 最优分类面和广义最优分类面 SVM是从线性可分情况下的最优分类面发展而来的 基本思想可用图1来说明 对于一维 空间中的点 二维空间中的直线 三维空间中的平面 以及高维空间中的超平面 图中实心 点和空心点代表两类样本 H为它们之间的分类超平面 H1 H2分别为过各类中离分类面最 近的样本且平行于分类面的超平面 它们之间的距离 叫做分类间隔 margin 图1 最优分类面示意图 所谓最优分类面要求分类面不但能将两类正确分开 而且使分类间隔最大 将两类正确 分开是为了保证训练错误率为0 也就是经验风险最小 为O 使分类空隙最大实际上就是使 推广性的界中的置信范围最小 从而使真实风险最小 推广到高维空间 最优分类线就成为 最优分类面 设线性可分样本集为是类别符号 d维空间中线性判 1 1 1 x yRxniy d ii 别函数的一般形式为是类别符号 d维空间中线性判别函数的一般形式为 分bxwxg 类线方程为 将判别函数进行归一化 使两类所有样本都满足 也就是0 bxw1 xg 使离分类面最近的样本的 此时分类间隔等于 因此使间隔最大等价于使1 xg 2w 或 最小 要求分类线对所有样本正确分类 就是要求它满足 w 2 w 1 1 nibxwyi 2 1 01 满足上述条件 1 1 并且使最小的分类面就叫做最优分类面 过两类样本中离分 2 w 类面最近的点且平行于最优分类面的超平面H1 H2上的训练样本点就称作支持向量 support vector 因为它们 支持 了最优分类面 利用Lagrange优化方法可以把上述最优分类面问题转化为如下这种较简单的对偶问题 即 在约束条件 1 0 1 i n i i y 2a 1 2b ni i 2 1 0 下面对求解下列函数的最大值 i 1 n ji jijiji n i xxyy 1 1i 2 1 Q 3 若为最优解 则 1 n i i yw 1 4 即最优分类面的权系数向量是训练样本向量的线性组合 这是一个不等式约束下的二次函数极值问题 存在唯一解 根据k hn Tucker条件 解 中将只有一部分 通常是很少一部分 不为零 这些不为0解所对应的样本就是支持向量 i 求解上述问题后得到的最优分类函数是 1 5 sgn sgn 1 n i iii bxxybxwxf 根据前面的分析 非支持向量对应的均为0 因此上式中的求和实际上只对支持向量 i 进行 是分类阈值 可以由任意一个支持向量通过式 1 1 求得 只有支持向量才满足其中 b 的等号条件 或通过两类中任意一对支持向量取中值求得 从前面的分析可以看出 最优分类面是在线性可分的前提下讨论的 在线性不可分的情 况下 就是某些训练样本不能满足式 1 1 的条件 因此可以在条件中增加一个松弛项参数 变成 0 i 1 6 nibxwy iii 2 1 01 对于足够小的s 0 只要使 1 7 n i i F 1 最小就可以使错分样本数最小 对应线性可分情况下的使分类间隔最大 在线性不可分 情况下可引入约束 1 k c 2 w 8 在约束条件 1 6 幂1 1 8 下对式 1 7 求极小 就得到了线性不可分情况下的最优分类 面 称作广义最优分类面 为方便计算 取s 1 为使计算进一步简化 广义最优分类面问题可以迸一步演化成在条件 1 6 的约束条件 下求下列函数的极小值 1 9 2 1 1 n i i Cwww 其中C为某个指定的常数 它实际上起控制对锩分样本惩罚的程度的作用 实现在错分 样本的比例与算法复杂度之间的折衷 求解这一优化问题的方法与求解最优分类面时的方法相同 都是转化为一个二次函数极值问题 其 结果与可分情况下得到的 1 2 到 1 5 几乎完全相同 但是条件 1 2b 变为 1 10 niC 1 0 i 2 SVM 的非线性映射的非线性映射 对于非线性问题 可以通过非线性交换转化为某个高维空间中的线性问题 在变换空间 求最优分类超平面 这种变换可能比较复杂 因此这种思路在一般情况下不易实现 但是我 们可以看到 在上面对偶问题中 不论是寻优目标函数 1 3 还是分类函数 1 5 都只涉及 训练样本之间的内积运算 设有非线性映射将输入空间的样本映射到高 i xx HR d 维 可能是无穷维 的特征空间H中 当在特征空间H中构造最优超平面时 训练算法仅使用空 间中的点积 即 而没有单独的出现 因此 如果能够找到一个函数K使得 ji xx i x 1 11 jiji xxxxK 这样在高维空间实际上只需进行内积运算 而这种内积运算是可以用原空间中的函数实 现的 我们甚至没有必要知道变换中的形式 根据泛函的有关理论 只要一种核函数 满足Mercer条件 它就对应某一变换空间中的内积 因此 在最优超平面中采用 ji xxK 适当的内积函数就可以实现某一非线性变换后的线性分类 而计算复杂度却没有 ji xxK 增加 此时目标函数 1 3 变为 1 12 n ji jijiji n i i xxKyyQ 11 1 2 1 而相应的分类函数也变为 1 13 sgn 1 n i jiii bxxKyxf 算法的其他条件不变 这就是SVM 概括地说SVM就是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间 在这个特征空间中构造最优分类超平面 在形式上SVM分类函数类似于一个神经网络 输出 是中间节点的线性组合 每个中间节点对应于一个支持向量 如图2所示 图2 SVM示意图 其中 输出 决策规则 权值 为基于 sgn 1 n i iii bxxKyy iii yw i xxK s个支持向量的非线性变换 内积 为输入向量 s xxx 21 21d xxxx 3 核函数 核函数 选择满足Mercer条件的不同内积核丞数 就构造了不同的SVM 这样也就形成了不同的 算法 目前研究最多的核函数主要有三类 1 多顼式核函数 1 14 q ii xxxxK 1 其中q是多项式的阶次 所得到的是q阶多项式分类器 2 径向基函数 RBF 1 15 exp 2 2 i i xx xxK 所得的SVM是一种径向基分类器 它与传统径向基函数方法的基本区别是 这里每一个 基函数的中心对应于一个支持向量 它们以及输出权值都是由算法自动确定的 径向基形式 的内积函数类似人的视觉特性 在实际应用中经常用到 但是需要注意的是 选择不同的S 参数值 相应的分类面会有很大差别 3 S形核函数 1 16 tanh cxxvxxK ii 这时的SVM算法中包含了一个隐层的多层感知器网络 不但网络的权值 而且网络的隐 层结点数也是由算法自动确定的 而不像传统的感知器网络那样由人凭借经验确定 此外 该算法不存在困扰神经网络的局部极小点的问题 在上述几种常用的核函数中 最为常用的是多项式核函数和径向基核函数 除了上面提 到的三种核函数外 还有指数径向基核函数 小波核函数等其它一些核函数 应用相对较少 事实上 需要进行训练的样本集有各式各样 核函数也各有优劣 B Bacsens和S Viaene等 人曾利用LS SVM分类器 采用UCI数据库 对线性核函数 多项式核函数和径向基核函数进 行了实验比较 从实验结果来看 对不同的数据库 不同的核函数各有优劣 而径向基核函 数在多数数据库上得到略为优良的性能 三 支持向量机的应用研究现状三 支持向量机的应用研究现状 SVM方法在理论上具有突出的优势 贝尔实验室率先对美国邮政手写数字库识别研究方 面应用了SVM方法 取得了较大的成功 在随后的近几年内 有关SVM的应用研究得到了很多 领域的学者的重视 在人脸检测 验证和识别 说话人 语音识别 文字 手写体识别 图像 处理 及其他应用研究等方面取得了大量的研究成果 从最初的简单模式输入的直接的SVM 方法研究 进入到多种方法取长补短的联合应用研究 对SVM方法也有了很多改进 一 人脸检测 验证和识别 一 人脸检测 验证和识别 Osuna最早将SVM应用于人脸检测 并取得了较好的效果 其方法是汽接训练非线性SVM 分类器完成人脸与非人脸的分类 由于SVM的训练需要大量的存储空间 并且非线性SVM分类 器需要较多的支持向量 速度很慢 为此 马勇等提出了一种层次型结构的SVM分类器 它 由一个线性SVM组合和一个非线性SVM组成 检测时 由前者快速排除掉图像中绝大部分背景 窗口 而后者只需对少量的候选区域做出确认 训练时 在线性SVM组台的限定下 与 自 举 bootstrapping 方法相结合可收集到训练非线性SVM的更有效的非人脸样本 简化SVM 训练的难度 大量实验结果表明这种方法不仅具有较高的检测率和较低的误检率 而且具有 较快的速度 人脸检测研究中更复杂的情况是姿态的变化 叶航军等提出了利用支持向量机方法进行 人脸姿态的判定 将人脸姿态划分成6个类别 从一个多姿态人脸库中手工标定训练样本集 和测试样本集 训练基于支持向量机姿态分类器 分类错误率降低到1 67 明显优于在传 统方法中效果最好的人工神经元网络方法 在人脸识别中 面部特征的提取和识别可看作是对3D物体的2D投影图像进行匹配的问题 由于许多不确定性因素的影响 特征的选取与识别就成为一个难点 凌旭峰等及张燕昆等分 别提出基于PCA与SVM相结合的人脸识别算法 充分利用了PCA在特征提取方面的有效性以及 SVM在处理小样本问题和泛化能力强等方面的优势 通过SVM与最近邻距离分类器相结合 使 得所提出的算法具有比传统最近邻分类器和BP网络分类器更高的识别率 王宏漫等在PCA基 础上进一步做ICA 提取更加有利于分类的面部特征的主要独立成分 然后采用分阶段淘汰 的支持向量机分类机制进行识别 对两组人脸图像库的测试结果表明 基于SVM的方法在识 别率和识别时间等方面都取得了较好的效果 二 说话人 语音识别 二 说话人 语音识别 说话人识别属于连续输入信号的分类问题 SVM是一个很好的分类器 但不适合处理连 续输入样本 为此 忻栋等引入隐式马尔可夫模型HMM 建立了SVM和HMM的混合模型 HMM适 合处理连续信号 而SVM适台于分类问题 HMM的结果反映了同类样本的相似度 而SVM的输 出结果则体现了异类样本间的差异 为了方便与HMM组成混合模型 首先将SVM的输出形式改 为概率输出 实验中使用YOHO数据库 特征提取采用12阶的线性预测系数分析及其微分 组 成24维的特征向量 实验表明HMM和SVM的结合达到了很好的效果 三 文字 手写体识别 三 文字 手写体识别 贝尔实验室对美国邮政手写数字库进行的实验 人工识别平均错误率是2 5 专门针 对该特定问题设计的5层神经网络错误率为5 1 其中利用了大量先验知识 而用3种SVM方 法 采用3种核函数 得到的错误率分别为4 0 4 1 和4 2 且是直接采用16 16的字符 点阵作为输入 表明了SVM的优越性能 手写体数字O 9的特征可以分为结构特征 统计特征等 柳回春等在 心理测试自动 分析系统中组合SVM和其他方法成功地进行了手写数字的识别实验 另外 在手写汉字识别 方面 高学等提出了一种基于SVM的手写汉字的识别方法 表明了SVM对手写汉字识别的有效 性 四 图像处理 四 图像处理 1 图像过滤 一般的互联网色情网图像过滤软件主要采用网址库的形式来封锁色情网 址或采用入工智能方法对接收到的中 英文信息进行分析甄别 段立娟等提出一种多层次特 定类型图像过滤法 即以综合肤色模型检验 支持向量机分类和最近邻方法校验的多层次图 像处理框架 达到85 以上的准确率 2 视频字幕提取 揽频字幕蕴含了丰富语义 可用于对相应视频流进行高级语义标注 庄越挺等提出并实践了基于SVM的视频字幕自动定位和提取的方法 该方法首先将原始图像 帧分割为N N的子块 提取每个子块的灰度特征 然后使用预先训练好的SVM分类机进行字幕 子块和非字幕子块的分类 最后结合金字塔模型和后期处理过程 实现视频图像字幕区域的 自动定位提取 实验表明该方法取得了良好的效果 3 图像分类和检索 由于计算机自动抽取的图像特征和人所理解的语义间存在巨大的 差距 图像检索结果难以令人满意 近年来出现了相关反馈方法 张磊等以SVM为分类器 在每次反馈中对用户标记的正例和反例样本进行学习 并根据学习所得的模型进行检索 使 用由 幅图像组成的图像库进行实验 结果表明 在有限训练样本情况下具有良好的 泛化能力 目前3D虚拟物体图像应用越来越广泛 肖俊等提出了一种基于SVM对相似3D物体识别与 检索的算法 该算法首先使用细节层次模型对3D物体进行三角面片数量的约减 然后提取3D 物体的特征 由于所提取的特征维数很大 因此先用独立成分分析进行特征约减 然后使用 SVM进行识别与检索 将该算法用于3D丘陵与山地的地形识别中 取得了良好效果 五 其他应用研究 五 其他应用研究 1 由于SVM的优越性 其应用研究目前开展已经相当广泛 陈光英等设计并实现了一种 基于SVM分类机的网络入侵检测系统 它收集并计算除服务器端口之外TCP IP的流量特 征 使用SVM算法进行分类 从而识别出该连接的服务类型 通过与该连接服务器端口所表 明服务类型的比较 检测出异常的TCP连接 实验结果表明 系统能够有效地检测出异常TCP 连接 2 口令认证简便易实现 但容易被盗用 刘学军等提出利用SVM进行键入特性的验真 并通过实验将其与BP RBF PNN和LVQ 4种神经网络模型进行对比 证实了采用SVM进行键入 特性验真的有效性 3 李晓黎等提出了一种将SVM与无监督聚类相结合的新分类算法 并应用于网页分类问 题 该算法首先利用无监督聚类分别对训练集中正例和反例聚类 然后挑选一些例子训练 SVM并获得SVM分类器 任何网页可以通过比较其与聚类中心的距离决定采用无监督聚类方法 或SVM分类器进行分类 该算法充分利用了SVM准确率高与无监督聚类速度快的优点 实验表 明它不仅具有较高的训练效率 而