支持向量分类机原理入门.ppt

实现非线性分划的思想 决策函数 其中 核函数(核或正定核)定义 设 是 中的一个子集。称定义在 上的函数 是核函数(正定核或核)，如果存在着从 到某一个 空间 的映射 使得 其中 表示 中的内积 核函数的选择 多项式内核 径向基函数内核RBF Sigmoind内核 目前研究最多的核函数主要有三类： 得到q 阶多项式分类器 每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定 包含一个隐层的多层感知器，隐层节点数是由算法自动确定 提纲 SVM有关概念介绍 SVM分类问题的数学表示和推导 简单的最优分类面 广义最优分类面 非线性最优分类面 SVM分解算法 － Edgar Osuna(Cambridge,MA)等人在IEEE NNSP’97发表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。 传统的利用二次型优化技术解决对偶问题时： 需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存； SVM在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。 SVM分解算法 考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。 例如：基于这种思路的 算法。 根据子问题的划分和迭代策略的不同，大致分为： 块算法(Chunking Algorithm)： SVM分解算法 将工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程选择一种合适的换入换出策略，将剩余样本中的一部分与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量中的一部分进行优化。 例如: 算法 根据子问题的划分和迭代策略的不同，大致分为： 2. 固定工作样本集 (Osuna et al.)： SVM分解算法 K-类模式识别问题是为样本集 多类问题中的SVM 构造一个决策函数。由于SVM是解决两类分类问题的有效方法，因此用SVM解多类问题的思路通常是将其转化为两类问题，然后对结果进行处理。常用方法有： One-against-the-rest方法：在第k类和其他第k-1类之间构造超平面。 One-against-one方法：为任意两个类构建超平面，共需K(K+1)/2个SVM K-class SVM：同时为所有类构造一个分类超平面 Thank you! * COLT(Computational Learning Theory) * Support Vector Classification Doctoral Seminar 数据挖掘中的新方法－支持向量分类机原理 中科院计算所智能开放室 曾立 zengl@ics.ict.ac.cn 提纲 SVM有关概念介绍 SVM分类问题的数学表示和推导 简单的最优分类面 广义最优分类面 非线性最优分类面 SVM分解算法 History SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，从此迅速发展起来，目前已经在许多智能信息获取与处理领域都取得了成功的应用。 关于SVM 思想： 通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。 途径： 构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrained quadratic programing),求解该问题，构造分类超平面，从而得到决策函数。 提纲 SVM有关概念介绍 SVM分类问题的数学表示和推导 简单的最优分类面 广义最优分类面 非线性最优分类面 SVM分解算法 a yest denotes +1 denotes -1 f x f(x) = sgn(w. x + b) Copyright ? 2001, 2003, Andrew W. Moore How would you classify