模式识别-第9章--核方法概要课件.ppt
第9章 模式识别中的核方法,9 模式识别中的核方法,9.1核方法概述9.2核方法基础9.3凸优化与SVM,9.1核方法概述,模式识别的核方法：首先把数据嵌入到合适的特征空间然后采用基于线性代数、几何、统计学算法，发现嵌入数据的模式,9.1核方法概述,核方法的4个关键：数据嵌入特征空间在特征空间中寻找线性模式在嵌入空间中，不需要计算点的坐标，只用两两内积利用核函数，可以直接从初始数据高效地计算内积。,从基于线性函数类的模式中抽取出来的模式函数,数据 核函数 核矩阵 PA算法 模式函数,9.1核方法概述线性回归,给定n维空间中训练集合，寻找齐次线性函数 使其为 S 的最优插值,通过给定的n维点，拟合一个超平面,如果 可逆,令,9.1核方法概述线性回归,给定n维空间中训练集合，寻找齐次线性函数 使其为 S 的最优插值,如果 可逆,训练点的线性组合,如果 不可逆：伪逆岭回归,9.1核方法概述岭回归,如果 不可逆：数据不够，或存在噪声,没有足够信息，精确指明解法（不适定ill-posed）,添加某种条件（或偏置），限制函数的选择（正则化）,选择范数较小的w,范数与损失之间的相对权衡,In 是一个 n 阶单位阵，时总可逆,9.1核方法概述对偶岭回归,训练点的线性组合,称,为Gram 矩阵,：对偶变量,G:训练点对间的内积,k：训练点和测试点之间的内积,直接法：N 很大时，解N N 的方程组代价过大,9.1核方法概述核函数,考虑一个嵌入映射,将 上的非线性关系转化为 高维空间上的线性关系,对偶法：需要的所有信息为特征空间 F 中的内积,跳过显式计算 直接计算,核函数：,核（kernel）是一个函数，对于所有 满足：,其中 是从 X 到（内积）特征空间 F 的一个映射：,指数维，甚至无限维特征空间。,那么，F中的线性函数为：,9.1核方法概述核函数举例,考虑一个二维输入空间 同时考虑特征映射：,将特征空间中的线性关系与输入空间中的二次关系相对应：,直接计算特征空间中的内积,不用显式计算特征空间中的坐标,也可计算如下映射空间的内积,特征空间并不由核函数唯一确定,9.1核方法概述核函数举例,考虑一个 n 维输入空间，那么函数是一个核函数，对应的特征映射为：,因为：,9 模式识别中的核方法,9.1核方法概述9.2核方法基础9.3凸优化与SVM,核矩阵,考虑 l 个训练样本在 N 维特征空间中映射，记为 l N 矩阵,称与之相关的L L Gram矩阵为核矩阵，其元素为,核矩阵可写作：,基本运算,如果 是核，B是一个半正定矩阵，p(x)是一个正系数多项式，那么下面都是核:,高斯核,均值和距离,特征向量的范数:,特征向量的规范化:,均值和距离,特征向量线性组合的范数:,均值和距离,特征向量之间的距离:,均值和距离,质心的范数,质心的范数的平方=核矩阵元素的平均值,均值和距离,点到质心的距离,均值和距离,方差,核矩阵对角线元素平均值-全体元素平均值,中心化数据,把原点移到质心平均特征值最小化,移动后，新的核函数为,可以证明对于 有：,中心化的稳定性,从训练样本估计质心的可靠性：样本中心多大程度上接近真实期望？,在概率 下：,新颖检测举例,对于一个新的随机点 满足,概率的界：,模式函数的期望在概率 下的界为：,把满足 的项视为新颖项，把正常项误判为正常项的概率最大为,二分类举例,将训练集S 划分为两个正例、负例子集：S_，S+,利用新颖检测，计算测试点 x 到两子集质心的距离：,分类规则为：,b+,b-,数据分散度标准化数据,两均值为0的随机变量 x,y 的协方差：两变量乘积的期望,不同原始特征，难以直接比较，需要在比较前进行标准化：,两变量的相关性：,以下三条件等价：,比较两变量的标准化结果，可衡量两变量的线性相关性,用于检测是否存在模式：,数据分散度协方差矩阵,考虑 l 个训练样本在 N 维特征空间中映射，记为 l N 矩阵,N N 协方差矩阵 C 元素为:,数据分散度投影的方差,设 v为 特征空间的单位向量，在v方向上投影的范数为,投影范数的中心为：,投影范数的方差为：,如何用内积计算？,将v表示成训练点的线性组合,数据分散度投影的方差,投影范数的方差为：,将v表示成训练点的线性组合,9 模式识别中的核方法,9.1核方法概述9.2核方法基础9.3凸优化与SVM,凸优化与SVM,超球体在嵌入空间中，寻找包含训练数据集的最小超球体。并构建检测新颖（反常）数据的算法。最大间隔超平面在嵌入空间中，寻找能将两类样本分开的最大间隔超平面，构建分类算法,凸二次规划问题,训练集 嵌入到特征空间 F 中,包含点集合的最小超球体,寻找一个包含所有特征点的最小超球体,中心是点的线性组合，且点数据点的跨度之内对偶,包含点集合的最小超球体,对偶lagrange 函数,最大化：,约束：,凸二次规划：,KT条件：=0,包含点集合的最小超球体,基于最小超球体的新颖检测,仅对支持向量有,仅需要计算#SV个内积,新颖检测稳定性,那么至少在 的概率下，在大小为 的样本上有：,令：,=0，对于训练样本,在 的概率下，来自训练分布D的点落在以c为中心，为半径的球的外部的概率小于。,不一味追求包含所有点避免个别噪声影响。,包含大部分点的软超球体,遗漏点的损失,半径过大的损失,VS,松弛变量：,两种损失的权衡,包含大部分点的软超球体,包含大部分点的软超球体,最大化：,约束：,凸二次规划：,包含大部分点的软超球体,选取某 i，使 则,KT条件：=0,此时根据KT条件：,基于软超球体的新颖检测,在 的概率下，来自训练分布D的点被 判为新颖点的概率最大为：,v-软最小超球体,软最小超球体,v-软最小超球体,超球体外的点有,最多有 个点在球外,超球体内的有,至少有 个点不在球内,v-软最小超球体,在 的概率下，来自训练分布D的点被 判为新颖点的概率最大为：,测试超球体半径平方为：,v-软最小超球体的优化目标为,即取 时，测试超球体体积最小,希望 p 为定值，将概率的界固定,超球体的讨论,“硬”最小包含球。扩大半径，保证更大的概率下包含正常点对于个别点敏感，不健壮软最小包含球不要求包含所有点，考虑半径大小与遗漏点的折中有可能将任意点排斥在外。v-软最小包含球给出包含于球内的点的界。V与误差率的联系。,3对L求导，代回Lagrange函数，转化为基于 和核的对偶，凸优化二次规划 求解,基于核的凸优化方法,1在高维特征空间中,在样本集 上构造优化问题最小化目标约束条件,2构造Lagrange函数,4根据K_T条件，得到基于核的模式函数,最优分类界面,样本集与分类界面之间的间隔 定义为样本与分类界面之间几何间隔的最小值。最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。,最大间隔分类器,线性函数：,训练样本：,最大间隔分类器,最大间隔分类器,最大化：,约束：,凸二次规划：,选择,由KT条件：,最大间隔分类器,模式函数：,在 的概率下泛化误差的界：,硬间隔：必须用在可分离情况，对噪声敏感不健壮,软间隔：容忍部分分错，对噪声不敏感健壮,软间隔分类器,软间隔分类器,软间隔分类器,与最大间隔的结果相同，仅约束条件不同：,软间隔分类器,最大化：,约束：,凸二次规划：,软间隔分类器,选择,使,在 的概率下泛化误差的界：,
