课件线性分类器.ppt

三．MSE准则函数的梯度下降法 在伪逆解 中，需要计算Y+ 。 这时要求 存在 的计算量大，而且可能引入更大的计算误差。 最小平方误差判别 因此实际操作中往往不用求Y+解析解的方法，而是用梯度下降法等最优化技术。 ∵ 梯度 ∴ 梯度下降法可写为： 最小平方误差判别 如果选 是一个正常数， 则上述迭代公式得到的权向量序列收敛于 使 的权向量a*。 即MSE准则的解。 最小平方误差判别 上述的梯度下降法不论YTY可逆与否，总能产生一个有用的权a*。而且计算 的计算 量比计算 的计算量小。 为了进一步减小计算量和存储，可采用单样本修正法，即把样本作为一个不断重复出现的序列来处理。 最小平方误差判别 单样本修正法的迭代公式为： 最小平方误差判别 准确地说，单样本修正法不是梯度下降法。两者不同，所得结果也不同。 上述算法是对MSE准则函数采用梯度下降法的一个修正算法，称为Widrow-Hoff算法或最小均方根算法(Least-mean square, LMS)。 最小平方误差判别 提纲 * 西安电子科技大学计算机学院 * 线性判别函数 Fisher线性判别分析 感知器 最小平方误差判别 线性支持向量机 多类线性分类器 支持向量机(SVM) 哪一个线性分类器好？如何评价哪一个好？ 间隔（margin） 模式到判决面最小距离称为分类间隔（margin） 一般认为，分类间隔越大的判决面越好 要找到离判决面最近的样本点：支持向量 支持向量机(SVM) 间隔的计算 函数间隔：样本xi到分类界面g(x)=0的函数间隔 定义为： 几何间隔： 支持向量机(SVM) 样本集与分类界面之间的间隔γ定义为样本与分类界面之间几何间隔的最小值。 最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。 支持向量机(SVM) 支持矢量：距离最优分类界面最近的这些训练样本称为支持矢量； 训练一个支持向量机的目标是找到一个具有最大间隔的分类平面；如果间隔越大，得到的分类器也越好。 最优分类界面完全由支持矢量决定，然而支持矢量的寻找比较困难。 支持向量机(SVM) 给定两类线性可分问题的样本集合： {(x1, y1), …, (xN, yN)} 其中y为样本的类别标号。 线性判决函数为： 类别标签：yk=1 表示xk属于第一类，yk=-1 表示xk属于第二类 设边缘阈量为1，则： 支持向量机(SVM) 优化目标： 最大化： 即，最小化 约束条件： 支持向量机(SVM) SVM可转化为如下的优化问题： s.t. 支持向量机(SVM) 构造Lagrange函数 分别对参数w和b求导： 支持向量机(SVM) SVM的优化问题可转化为一个二次规划问题: s.t. 支持向量机(SVM) 原问题的解: 满足条件 的样本点为支持向量。 最优分类界面为： 支持向量机(SVM) SVM方法的优点：分类器的复杂度取决于支持向量的个数，而不是变换空间的维数。因此SVM不容易发生过拟合的现象。（参考书目：Vladimir N. Vapnik 著, 张学工译. 统计学习理论的本质.北京.清华大学出版社, 2000年） 当原训练样本线性不可分时，可利用某个非线性变换将原数据空间中的样本点映射到更高维空间中，使得在此高维空间中的映射点线性可分。 核技巧（kernel trick）……（参考书目：徐勇, 杨健. 模式识别中的核方法及其应用. 国防工业出版社. 2010年） 支持向量机(SVM) 模式识别是一种基于数据的机器学习，学习的目的不仅是要对训练样本能够正确分类，而是要能够对所有可能的样本正确分类，这种能力叫做推广能力。 期望风险：所有可能出现的样本的错误率或风险 经验风险：所有训练样本的分类决策损失： 大间隔与推广能力 统计学习理论的关键结论：也就是经验风险与期望风险的关系， 其中右边第二项是置信范围，它与样本数成反比，而与VC维 成正比。 需要强调的是VC维反映了所设计的学习机器的复杂性。 大间隔与推广能力 线性不可分的情况： 对 不等式 不可能同时满足。 每一个样本引入一个非负的松弛变量 支持向量机(SVM) 广义最优分类面： s.t. 上述的问题可转化为拉