模式识别第9章核方法概要课件.ppt

1、第9章 模式识别中的核方法9 模式识别中的核方法 9.1核方法概述核方法概述 9.2核方法基础 9.3凸优化与SVM9.1核方法概述 模式识别的核方法：首先把数据嵌入到合适的特征空间 然后采用基于线性代数、几何、统计学算法，发现嵌入数据的模式9.1核方法概述 核方法的4个关键：数据嵌入特征空间 在特征空间中寻找线性模式 在嵌入空间中，不需要计算点的坐标，只用两两内积 利用核函数，可以直接从初始数据高效地计算内积。从基于线性函数类的模式中抽取出来的模式函数数据 核函数 核矩阵 PA算法 模式函数9.1核方法概述线性回归 给定n维空间中训练集合 ，寻找齐次线性函数 使其为 S 的最优插值11(,)

2、,(,)Syyxx1(),ntiiigw xxw xw xiyixi(),gyxw x通过给定的n维点，拟合一个超平面yXw22(,)()()tLSwyXwyXw(,)220ttLS wX yX XwwttX XwX y如果 可逆tX X1()ttwX XX y令 11(,),(,)tttllyyXxxy9.1核方法概述线性回归 给定n维空间中训练集合 ，寻找齐次线性函数 使其为 S 的最优插值11(,),(,)S x yx y1(),ntiiigw xxw xw xiyixi如果 可逆tX X1()ttwX XX y2()()ttttwX X X XX yX1=iiix训练点的线性组合如果

3、不可逆：伪逆岭回归tX X9.1核方法概述岭回归如果 不可逆：数据不够，或存在噪声tX X没有足够信息，精确指明解法（不适定ill-posed）添加某种条件（或偏置），限制函数的选择（正则化）222(,)LSww选择范数较小的w范数与损失之间的相对权衡(,)2220ttLS wX yX XwwwttnX XIwX yIn 是一个 n 阶单位阵，时总可逆01ttnwX XIX y1(),ttngxw xy X X XIx9.1核方法概述对偶岭回归(,)2220ttLS wX yX Xwww1()twX yXwt X 训练点的线性组合1()yXw()yXw()tyXX 1()tXXIy,ti ji

4、jGXX Gx x称为Gram 矩阵1(),iiigxw xx x1(),tgx kyGIk11,iiiiiikx x：对偶变量,iik x xG:训练点对间的内积k：训练点和测试点之间的内积直接法：N 很大时，解N N 的方程组代价过大9.1核方法概述核函数:()nNFxx 考虑一个嵌入映射将 上的非线性关系转化为 高维空间上的线性关系nx(,)()(),fyygyw xxxN1()ttwX XX y对偶法：需要的所有信息为特征空间 F 中的内积,(),()i jijGxx(),()iikxx跳过显式计算 直接计算()ix(),()ixx核函数：(,)(),()x zxz核（kernel）是

5、一个函数 ，对于所有 满足：(,),Xx z其中 是从 X 到（内积）特征空间 F 的一个映射：:()Fxx指数维，甚至无限维特征空间。那么，F中的线性函数为：9.1核方法概述核函数举例223121212:(,)()(,2)x xxxx xFxx考虑一个二维输入空间 同时考虑特征映射：2X 2211 122 11212()2gw xw xwx xx将特征空间中的线性关系与输入空间中的二次关系相对应：22221212121 2(,)(),()(,2),(,2)xxx xzzz zx zxz222222112112 1 21 1222,x zx zx x z zx zx zx z直接计算特征空间中

6、的内积不用显式计算特征空间中的坐标2241212122 1:(,)()(,)x xxxx x x xFxx2(,),x zx z也可计算如下映射空间的内积特征空间并不由核函数唯一确定9.1核方法概述核函数举例312,1:(,)()()niji jx xx xFxx考虑一个 n 维输入空间 ，那么函数是一个核函数，对应的特征映射为：nX,1,1(),()(),()nniji jiji jzx xz zx2(,),x zx z2,111,nnnijijiijji jijx x z zx zx zx z因为：9 模式识别中的核方法 9.1核方法概述 9.2核方法基础核方法基础 9.3凸优化与SVM核

7、矩阵 考虑 l 个训练样本在 N 维特征空间中映射，记为 l N 矩阵1(),()tlXxx称与之相关的L L Gram矩阵为核矩阵，其元素为tKXX(),()(,)ijijijKxxx x核矩阵可写作：基本运算 如果 是核，B是一个半正定矩阵，p(x)是一个正系数多项式，那么下面都是核:12,12112(,)(,)(,)(,)(,)(,)(,)(,)(,)tBx zx zx zx zx zx zx zx zx zxx1122(,)(,)(,)exp(,)(,)exp,2px zx zx zx zx zx z高斯核均值和距离特征向量的范数:2()(),()(,)xxxx x特征向量的规范化:(

8、)()()xxx()()(,)(),(),()()xzx zxzxz(),()(,)()()(,)(,)xzx zxzx xz z均值和距离特征向量线性组合的范数:2111()(),()iiiijjiij xxx11(),()ijijij xx,1(,)ijiji j x x均值和距离特征向量之间的距离:2()()()(),()()xzxzxz(),()2(),()(),()xxxzzz(,)2(,)(,)x xx zz z均值和距离质心的范数11()siix21111(),()sijijxx22,1,111(),()(,)ijiji ji jxxx x质心的范数的平方=核矩阵元素的平均值均值

9、和距离点到质心的距离11()siix2()(),(),2(),ssss xxxx2,1112(,)(,)(,)ijji jix xx xx x均值和距离方差221,1,1112(,)(,)(,)kkijikki ji kx xx xx x211()isix21,111(,)(,)kkijki jx xx x核矩阵对角线元素平均值-全体元素平均值中心化数据把原点移到质心平均特征值最小化211,1111(,)(,)(,)(,)ijijiji jx zx xx zx x移动后，新的核函数为1111(,)(),()()(),()()iiiix zxzxxzx11()()()()siixxxx可以证明对

10、于 有：中心化的稳定性 从训练样本估计质心的可靠性：样本中心多大程度上接近真实期望？()()()XdPExxxx()()sg SExx221()2lnRg S11()iisx在概率 下：新颖检测举例11()()maxidEdxxx1x对于一个新的随机点 满足 11)()SSEdxxxmaxid(1)s21()212lnSRx1x概率的界：11max1iP ddl2121()()max()2lnSiSiRfH xxx()1(1)E fxx模式函数的期望在概率 下的界为：(1)把满足 的项视为新颖项，把正常项误判为正常项的概率最大为()1fx1(1)二分类举例将训练集S 划分为两个正例、负例子集：

11、S_，S+利用新颖检测，计算测试点 x 到两子集质心的距离：()()Sdxx()()Sdxx分类规则为：22()sgn()()SShxxx2,1112sgn(,)(,)(,)ijii jix xx xx x2,1112(,)(,)(,)ijii jix xx xx x1111sgn(,)(,)iiiibx xx xb+b-数据分散度标准化数据两均值为0的随机变量 x,y 的协方差：两变量乘积的期望cov(,)xyx yExy不同原始特征，难以直接比较，需要在比较前进行标准化：xxxx两变量的相关性：corr(,)xyxyx yExyxyxyxyxyE 以下三条件等价：1xyxyywxb比较两变

12、量的标准化结果，可衡量两变量的线性相关性1xyywxb用于检测是否存在模式：(,)g x yywxb数据分散度协方差矩阵 考虑 l 个训练样本在 N 维特征空间中映射，记为 l N 矩阵11()()stisitiCxx1(),()tlXxxN N 协方差矩阵 C 元素为:111()()ttiististxxX X数据分散度投影的方差设 v为 特征空间的单位向量，在v方向上投影的范数为方向上投影的范数为()xv()x()tvx投影范数的中心为：投影范数的中心为：11()tiivx投影范数的方差为：投影范数的方差为：11()()ttiiivxxv211ttttv X Xvv X j2222()()

13、ttiiEEvvvvxvx21ttv X j11()tiivx()tviEvx1ttv X j如何用内积计算？如何用内积计算？将将v表示成训练点的表示成训练点的线性组合线性组合数据分散度投影的方差1()tiiivxX 投影范数的方差为：投影范数的方差为：2211ttttvv X Xvv X j将将v表示成训练点的线性组合表示成训练点的线性组合211ttttt XX XX XX j211tt KK Kj9 模式识别中的核方法 9.1核方法概述 9.2核方法基础 9.3凸优化与凸优化与SVM凸优化与凸优化与SVM 超球体 在嵌入空间中，寻找包含训练数据集的最小超球体。并构建检测新颖（反常）数据的算

14、法。最大间隔超平面 在嵌入空间中，寻找能将两类样本分开的最大间隔超平面，构建分类算法凸二次规划问题训练集 嵌入到特征空间 F 中 包含点集合的最小超球体1,S xx寻找一个包含所有特征点的最小超球体 rc2,min c rr22.()0istrxc2221(,)()iiiLrrrcxc1(,)2()0iiiLr cxcc1(,)220iiLrrrrc11ii1()iiicx中心是点的线性组合，且点数据点的跨度之内对偶 包含点集合的最小超球体2221(,)()iiiLrrrcxc111()(),()()iiiiiiiiiixxxx1,11(,)(,)2(,)iiikjjkjijik jj x x

15、x xx x11ii1()iiicx1,1,1(,)(,)2(,)iiikjjkijijik ji j x xx xx x1,1(,)(,)iiikjjkik j x xx x对偶对偶lagrange 函数函数ttiik K1,1()(,)(,)iiikjjkik jW x xx x最大化：约束：11,0iii*argmax()W2(*)rW2221(*)()iiiWrrxc凸二次规划：KT条件：=0rc1()iii cx包含点集合的最小超球体2(*)rW22212()()()iiifHrr cxxxxrc1()iii cx21,1(,)2(,)(,)iiijijii jHr x xx xx

16、x基于最小超球体的新颖检测D仅对支持向量有0sv(,)2(,)iii SVHD x xx x仅需要计算#SV个内积22220 ,()()(),()+1 ,elsergrrrxcxxcxcrc新颖检测稳定性那么至少在 的概率下，在大小为 的样本上有：R令：2116ln(2)()()32DiiREggxx1=0，对于训练样本在 的概率下，来自训练分布D的点落在以c为中心，为半径的球的外部的概率小于 。1*r(,)e(,)e不一味追求包含所有点避免个别噪声影响。包含大部分点的软超球体遗漏点的损失 rc半径过大的损失VS 松弛变量：i20,()()()iiiirrrxcxcxc，2,min c rr2

17、2.()istrxc1iiC,0ii 两种损失的权衡2222111(,)()iiiii iiiiLrrCrc xc包含大部分点的软超球体2222111(,)()iiiii iiiiLrrCrc xc12()0iiiL xcc1210iiLrr0iiiLCiC11ii1()iiixc21(,)()iiiLrc xc1,1(,)(,)iiikjjkik j x xx x包含大部分点的软超球体1,1()(,)(,)iiikjjkik jW x xx x最大化：约束：11,0,iiiC*argmax()W2222111(*)()iiiiiiiiiWrCr xc凸二次规划：1()iii cxrci0ii

18、C包含大部分点的软超球体21(*)iiWrC2222111(*)()iiiiiiiiiWrCr xc1()iii cx选取某 i，使 则0,iCKT条件：=00iiC()irxc0iiC此时根据KT条件：121,1(,)2(,)(,)iikkijkjkkj kx xx xx x22122()()iiifHrr xxcxx21,1(,)2(,)(,)iiijijii jHr x xx xx x基于软超球体的新颖检测D1(,)2(,)iiiHD x xx x在 的概率下，来自训练分布D的点被 判为新颖点的概率最大为：1()fx2116ln(2)32iiR1C v-软最小超球体软最小超球体2,1mi

19、n c riirCv-软最小超球体2,11min c riir1C1C 010iiC11ii超球体外的点有2222111(*)()iiiiiiiiiWrCr xc0i1iC最多有 个点在球外超球体内的有0i至少有 个点不在球内1C0iiCv-软最小超球体在 的概率下，来自训练分布D的点被 判为新颖点的概率最大为：1()fx2116ln(2)32iiR2116iiRp测试超球体半径平方为：2*2*2116iiRrrppp v-软最小超球体的优化目标为2,11min c riir即取 时，测试超球体体积最小p希望 p 为定值，将概率的界固定超球体的讨论“硬”最小包含球。扩大半径，保证更大的概率下包

20、含正常点 对于个别点敏感，不健壮 软最小包含球 不要求包含所有点，考虑半径大小与遗漏点的折中 有可能将任意点排斥在外。v-软最小包含球 给出包含于球内的点的界。V与误差率的联系。3对L求导，代回Lagrange函数，转化为基于 和核的对偶，凸优化二次规划 求解 基于核的凸优化方法 1在高维特征空间中,在样本集 上构造优化问题 最小化目标 约束条件()()Lrfg bw()0,()0fg bw 2构造Lagrange函数(,)rbw1(),()tlXxx(,),W 4根据K_T条件，得到基于核的模式函数 最优分类界面 样本集与分类界面之间的间隔 定义为样本与分类界面之间几何间隔的最小值。最优分类

21、界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。最大间隔分类器,min bw线性函数：11(,),(,)Syyxx训练样本：2(),(),1igbxwxw2.y,(),1iistbwxw21y,()1iiiiLb wxw1y()20iiiiL xww110iiL 10iiiLyb 11ii10iiiy11y()2iiiiwx最大间隔分类器21y,()1iiiiLb wxw21y,()iiii wxw11ii10iiiy11y()2iiiiwx,111y y(),()24ijijjii j xx,11y y(,)4ijijiji j x x12,1y y(,)ijijiji j x x

22、12,11y y(,)2ijijiji jx x最大间隔分类器11,0iii10iiiy,1()y y(,)ijijiji jW x x最大化：约束：*argmax()W凸二次规划：()W选择0i由KT条件：21y()y(,)ijjijjbx x1()sgn(,)iiiifybxx21y,()1iiiiLb wxw0最大间隔分类器1()sgn(,)iiiifybxx x*4ln(2)tr()32K模式函数：在 的概率下泛化误差的界：1硬间隔：必须用在可分离情况，对噪声敏感不健壮软间隔：容忍部分分错，对噪声不敏感健壮软间隔分类器,min bw2.1,y,()iistbwwx1iiC,()iiiy

23、 gx,0ii 1121y,()+1iiiiiiiiiiLCb wxw软间隔分类器11y,()+iiiiiiiLCb wx12()0iiiiLywxw0iiiLC10iiiLyb110iiL 211iiiw软间隔分类器11y,()+iiiiiiiLCb wx12,1()y y(,)ijijiji jL x x12,11y y(,)2ijijiji jx x211iiiw与最大间隔的结果相同，仅约束条件不同：0iiCiC软间隔分类器111,0,0iiiiiiyC,1()y y(,)ijijiji jW x x最大化：约束：*argmax()W凸二次规划：12,11y y(,)2ijijiji jx x软间隔分类器选择(,)i j使*110.5y(,)y(,)kkikkkkjkkb x xx x*y0yiijjCC1*12y(,)kkjkkbx x*1()sgn(,)iiiifybxx x*-W()14ln(2)tr()32CCK在 的概率下泛化误差的界：1