哈工大模式识别——核方法概要.ppt

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