哈工大模式识别——核方法概要.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,范数与损失之间的相对权衡,I,n,是一个,n,阶单位阵，时总可逆,7,9.1,核方法概述,对偶岭回归,训练点的线性组合,称,为,Gram,矩阵,：对偶变量,G:,训练点对间的内积,k,：训练点和测试点之间的内积,8,直接法：,N,很大时，解,N,N,的方程组代价过大,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,维特征空间中映射，记为,l,N,矩阵,称与之相关的,L,L Gram,矩阵为核矩阵，其元素为,核矩阵可写作：,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,维特征空间中映射，记为,l,N,矩阵,N,N,协方差矩阵,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,最大间隔分类器,模式函数：,在 的概率下泛化误差的界：,硬间隔：必须用在可分离情况，对噪声敏感,不健壮,软间隔：容忍部分分错，对噪声不敏感,健壮,49,软间隔分类器,50,软间隔分类器,51,软间隔分类器,与最大间隔的结果相同，仅约束条件不同：,52,软间隔分类器,最大化：,约束：,凸二次规划：,53,软间隔分类器,选择,使,在 的概率下泛化误差的界：,54,