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

第9章模式识别中的核方法第9章模式识别中的核方法19模式识别中的核方法9.1核方法概述9.2核方法基础9.3凸优化与SVM9模式识别中的核方法9.1核方法概述29.1核方法概述模式识别的核方法：首先把数据嵌入到合适的特征空间然后采用基于线性代数、几何、统计学算法，发现嵌入数据的模式9.1核方法概述模式识别的核方法：39.1核方法概述核方法的4个关键：数据嵌入特征空间在特征空间中寻找线性模式在嵌入空间中，不需要计算点的坐标，只用两两内积利用核函数，可以直接从初始数据高效地计算内积。从基于线性函数类的模式中抽取出来的模式函数数据核函数核矩阵PA算法模式函数9.1核方法概述核方法的4个关键：从基于线性函数类的模式中抽49.1核方法概述——线性回归给定n维空间中训练集合，寻找齐次线性函数使其为S的最优插值通过给定的n维点，拟合一个超平面如果可逆令9.1核方法概述——线性回归给定n维空间中训练集合59.1核方法概述——线性回归给定n维空间中训练集合，寻找齐次线性函数使其为S的最优插值如果可逆训练点的线性组合如果不可逆：伪逆——岭回归9.1核方法概述——线性回归给定n维空间中训练集合69.1核方法概述——岭回归如果不可逆：数据不够，或存在噪声——没有足够信息，精确指明解法（不适定ill-posed）添加某种条件（或偏置），限制函数的选择（正则化）选择范数较小的w范数与损失之间的相对权衡In是一个n阶单位阵，时总可逆9.1核方法概述——岭回归如果不可逆：数据79.1核方法概述——对偶岭回归训练点的线性组合称为Gram矩阵：对偶变量G:训练点对间的内积k：训练点和测试点之间的内积9.1核方法概述——对偶岭回归训练点的线性组合称为Gram8直接法：N很大时，解N×N的方程组代价过大9.1核方法概述——核函数考虑一个嵌入映射将上的非线性关系转化为高维空间上的线性关系对偶法：需要的所有信息为特征空间F中的内积跳过显式计算直接计算——核函数：核（kernel）是一个函数，对于所有满足：其中是从X到（内积）特征空间F的一个映射：指数维，甚至无限维特征空间。直接法：N很大时，9那么，F中的线性函数为：9.1核方法概述——核函数举例考虑一个二维输入空间同时考虑特征映射：将特征空间中的线性关系与输入空间中的二次关系相对应：直接计算特征空间中的内积不用显式计算特征空间中的坐标也可计算如下映射空间的内积特征空间并不由核函数唯一确定那么，F中的线性函数为：9.1核方法概述——核函数举例考虑一109.1核方法概述——核函数举例考虑一个n维输入空间，那么函数是一个核函数，对应的特征映射为：因为：9.1核方法概述——核函数举例考虑一个n维输入空间119模式识别中的核方法9.1核方法概述9.2核方法基础9.3凸优化与SVM9模式识别中的核方法9.1核方法概述12核矩阵

考虑l个训练样本在N维特征空间中映射，记为l×N矩阵称与之相关的L×LGram矩阵为核矩阵，其元素为核矩阵可写作：核矩阵考虑l个训练样本在N维特征空间中映射，记为13基本运算如果是核，B是一个半正定矩阵，p(x)是一个正系数多项式，那么下面都是核:高斯核基本运算如果是核，B是一个半正定矩阵，p(14均值和距离特征向量的范数:特征向量的规范化:均值和距离特征向量的范数:特征向量的规范化:15均值和距离特征向量线性组合的范数:均值和距离特征向量线性组合的范数:16均值和距离特征向量之间的距离:均值和距离特征向量之间的距离:17均值和距离质心的范数质心的范数的平方=核矩阵元素的平均值均值和距离质心的范数质心的范数的平方=核矩阵元素的平均值18均值和距离点到质心的距离均值和距离点到质心的距离19均值和距离方差核矩阵对角线元素平均值-全体元素平均值均值和距离方差核矩阵对角线元素平均值-全体元素平均值20中心化数据把原点移到质心——平均特征值最小化移动后，新的核函数为中心化数据把原点移到质心——平均特征值最小化移动后，新的核函21可以证明对于有：中心化的稳定性从训练样本估计质心的可靠性：样本中心多大程度上接近真实期望？可以证明对于22在概率下：新颖检测举例对于一个新的随机点满足概率的界：模式函数的期望在概率下的界为：把满足的项视为新颖项，把正常项误判为正常项的概率最大为在概率下：新颖检测举例对于一个新的随机23二分类举例将训练集S划分为两个正例、负例子集：S_，

S+利用新颖检测，计算测试点x到两子集质心的距离：

分类规则为：b+b-二分类举例将训练集S划分为两个正例、负例子集：S_，S24数据分散度——标准化数据两均值为0的随机变量x,y的协方差：两变量乘积的期望不同原始特征，难以直接比较，需要在比较前进行标准化：两变量的相关性：以下三条件等价：比较两变量的标准化结果，可衡量两变量的线性相关性用于检测是否存在模式：数据分散度——标准化数据两均值为0的随机变量x,y的25数据分散度——协方差矩阵

考虑l个训练样本在N维特征空间中映射，记为l×N矩阵N×N协方差矩阵C元素为:数据分散度——协方差矩阵考虑l个训练样本在N维特征26数据分散度——投影的方差设v为特征空间的单位向量，在v方向上投影的范数为投影范数的中心为：投影范数的方差为：如何用内积计算？将v表示成训练点的线性组合数据分散度——投影的方差设v为特征空间的单位向量，27数据分散度——投影的方差投影范数的方差为：将v表示成训练点的线性组合数据分散度——投影的方差投影范数的方差为：将v表示成训练点的289模式识别中的核方法9.1核方法概述9.2核方法基础9.3凸优化与SVM9模式识别中的核方法9.1核方法概述29凸优化与SVM超球体在嵌入空间中，寻找包含训练数据集的最小超球体。并构建检测新颖（反常）数据的算法。最大间隔超平面在嵌入空间中，寻找能将两类样本分开的最大间隔超平面，构建分类算法凸二次规划问题凸优化与SVM超球体凸二次规划问题30训练集嵌入到特征空间F中包含点集合的最小超球体寻找一个包含所有特征点的最小超球体中心是点的线性组合，且点数据点的跨度之内——对偶训练集31包含点集合的最小超球体对偶lagrange函数包含点集合的最小超球体对偶lagrange函数32最大化：约束：凸二次规划：KT条件：=0包含点集合的最小超球体最大化：约束：凸二次规划：KT条件：=0包含点集合的最小超球33基于最小超球体的新颖检测仅对支持向量有仅需要计算#SV个内积基于最小超球体的新颖检测仅对支持向量有仅需要计算#SV个内积34新颖检测稳定性那么至少在的概率下，在大小为的样本上有：令：=0，对于训练样本在的概率下，来自训练分布D的点落在以c为中心，为半径的球的外部的概率小于。新颖检测稳定性那么至少在的概率下，在大35不一味追求包含所有点——避免个别噪声影响。包含大部分点的软超球体遗漏点的损失半径过大的损失VS

松弛变量：两种损失的权衡不一味追求包含所有点——避免个别噪声影响。包含大部分点的36包含大部分点的软超球体包含大部分点的软超球体37包含大部分点的软超球体最大化：约束：凸二次规划：包含大部分点的软超球体最大化：约束：凸二次规划：38包含大部分点的软超球体选取某i，使则KT条件：=0此时根据KT条件：包含大部分点的软超球体选取某i，使39基于软超球体的新颖检测在的概率下，来自训练分布D的点被判为新颖点的概率最大为：基于软超球体的新颖检测在的概率下40v-软最小超球体软最小超球体v-软最小超球体超球体外的点有最多有个点在球外超球体内的有至少有个点不在球内v-软最小超球体软最小超球体v-软最小超球体超球体外的点有最41v-软最小超球体在的概率下，来自训练分布D的点被判为新颖点的概率最大为：测试超球体半径平方为：v-软最小超球体的优化目标为即取时，测试超球体体积最小希望p

为定值，将概率的界固定v-软最小超球体在的概率下，来自42超球体的讨论“硬”最小包含球。扩大半径，保证更大的概率下包含正常点对于个别点敏感，不健壮软最小包含球不要求包含所有点，考虑半径大小与遗漏点的折中有可能将任意点排斥在外。v-软最小包含球给出包含于球内的点的界。V与误差率的联系。超球体的讨论“硬”最小包含球。433对L求导，代回Lagrange函数，转化为基于和核的对偶，凸优化——二次规划求解基于核的凸优化方法1在高维特征空间中,在样本集上构造优化问题最小化目标约束条件2构造Lagrange函数4根据K_T条件，得到基于核的模式函数3对L求导，代回Lagrange函数，转化为基于和核44最优分类界面样本集与分类界面之间的间隔定义为样本与分类界面之间几何间隔的最小值。最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。最优分类界面样本集与分类界面之间的间隔定义为样本与分类45最大间隔分类器线性函数：训练样本：最大间隔分类器线性函数：训练样本：46最大间隔分类器最大间隔分类器47最大间隔分类器最大化：约束：凸二次规划：选择由KT条件：最大间隔分类器最大化：约束：凸二次规划：选择由KT条件：48最大间隔分类器模式函数：在的概率下泛化误差的界：硬间隔：必须用在可分离情况，对噪声敏感——不健壮软间隔：容忍部分分错，对噪声不敏感——健壮最大间隔分类器模式函数：在的概率下泛化49软间隔分类器软间隔分类器50软间隔分类器软间隔分类器51软间隔分类器与最大间隔的结果相同，仅约束条件不同：软间隔分类器与最大间隔的结果相同，仅约束条件不同：52软间隔分类器最大化：约束：凸二次规划：软间隔分类器最大化：约束：凸二次规划：53软间隔分类器选择使在的概率下泛化误差的界：软间隔分类器选择使在的概率下泛化误差的54第9章模式识别中的核方法第9章模式识别中的核方法559模式识别中的核方法9.1核方法概述9.2核方法基础9.3凸优化与SVM9模式识别中的核方法9.1核方法概述569.1核方法概述模式识别的核方法：首先把数据嵌入到合适的特征空间然后采用基于线性代数、几何、统计学算法，发现嵌入数据的模式9.1核方法概述模式识别的核方法：579.1核方法概述核方法的4个关键：数据嵌入特征空间在特征空间中寻找线性模式在嵌入空间中，不需要计算点的坐标，只用两两内积利用核函数，可以直接从初始数据高效地计算内积。从基于线性函数类的模式中抽取出来的模式函数数据核函数核矩阵PA算法模式函数9.1核方法概述核方法的4个关键：从基于线性函数类的模式中抽589.1核方法概述——线性回归给定n维空间中训练集合，寻找齐次线性函数使其为S的最优插值通过给定的n维点，拟合一个超平面如果可逆令9.1核方法概述——线性回归给定n维空间中训练集合599.1核方法概述——线性回归给定n维空间中训练集合，寻找齐次线性函数使其为S的最优插值如果可逆训练点的线性组合如果不可逆：伪逆——岭回归9.1核方法概述——线性回归给定n维空间中训练集合609.1核方法概述——岭回归如果不可逆：数据不够，或存在噪声——没有足够信息，精确指明解法（不适定ill-posed）添加某种条件（或偏置），限制函数的选择（正则化）选择范数较小的w范数与损失之间的相对权衡In是一个n阶单位阵，时总可逆9.1核方法概述——岭回归如果不可逆：数据619.1核方法概述——对偶岭回归训练点的线性组合称为Gram矩阵：对偶变量G:训练点对间的内积k：训练点和测试点之间的内积9.1核方法概述——对偶岭回归训练点的线性组合称为Gram62直接法：N很大时，解N×N的方程组代价过大9.1核方法概述——核函数考虑一个嵌入映射将上的非线性关系转化为高维空间上的线性关系对偶法：需要的所有信息为特征空间F中的内积跳过显式计算直接计算——核函数：核（kernel）是一个函数，对于所有满足：其中是从X到（内积）特征空间F的一个映射：指数维，甚至无限维特征空间。直接法：N很大时，63那么，F中的线性函数为：9.1核方法概述——核函数举例考虑一个二维输入空间同时考虑特征映射：将特征空间中的线性关系与输入空间中的二次关系相对应：直接计算特征空间中的内积不用显式计算特征空间中的坐标也可计算如下映射空间的内积特征空间并不由核函数唯一确定那么，F中的线性函数为：9.1核方法概述——核函数举例考虑一649.1核方法概述——核函数举例考虑一个n维输入空间，那么函数是一个核函数，对应的特征映射为：因为：9.1核方法概述——核函数举例考虑一个n维输入空间659模式识别中的核方法9.1核方法概述9.2核方法基础9.3凸优化与SVM9模式识别中的核方法9.1核方法概述66核矩阵

考虑l个训练样本在N维特征空间中映射，记为l×N矩阵称与之相关的L×LGram矩阵为核矩阵，其元素为核矩阵可写作：核矩阵考虑l个训练样本在N维特征空间中映射，记为67基本运算如果是核，B是一个半正定矩阵，p(x)是一个正系数多项式，那么下面都是核:高斯核基本运算如果是核，B是一个半正定矩阵，p(68均值和距离特征向量的范数:特征向量的规范化:均值和距离特征向量的范数:特征向量的规范化:69均值和距离特征向量线性组合的范数:均值和距离特征向量线性组合的范数:70均值和距离特征向量之间的距离:均值和距离特征向量之间的距离:71均值和距离质心的范数质心的范数的平方=核矩阵元素的平均值均值和距离质心的范数质心的范数的平方=核矩阵元素的平均值72均值和距离点到质心的距离均值和距离点到质心的距离73均值和距离方差核矩阵对角线元素平均值-全体元素平均值均值和距离方差核矩阵对角线元素平均值-全体元素平均值74中心化数据把原点移到质心——平均特征值最小化移动后，新的核函数为中心化数据把原点移到质心——平均特征值最小化移动后，新的核函75可以证明对于有：中心化的稳定性从训练样本估计质心的可靠性：样本中心多大程度上接近真实期望？可以证明对于76在概率下：新颖检测举例对于一个新的随机点满足概率的界：模式函数的期望在概率下的界为：把满足的项视为新颖项，把正常项误判为正常项的概率最大为在概率下：新颖检测举例对于一个新的随机77二分类举例将训练集S划分为两个正例、负例子集：S_，

S+利用新颖检测，计算测试点x到两子集质心的距离：

分类规则为：b+b-二分类举例将训练集S划分为两个正例、负例子集：S_，S78数据分散度——标准化数据两均值为0的随机变量x,y的协方差：两变量乘积的期望不同原始特征，难以直接比较，需要在比较前进行标准化：两变量的相关性：以下三条件等价：比较两变量的标准化结果，可衡量两变量的线性相关性用于检测是否存在模式：数据分散度——标准化数据两均值为0的随机变量x,y的79数据分散度——协方差矩阵

考虑l个训练样本在N维特征空间中映射，记为l×N矩阵N×N协方差矩阵C元素为:数据分散度——协方差矩阵考虑l个训练样本在N维特征80数据分散度——投影的方差设v为特征空间的单位向量，在v方向上投影的范数为投影范数的中心为：投影范数的方差为：如何用内积计算？将v表示成训练点的线性组合数据分散度——投影的方差设v为特征空间的单位向量，81数据分散度——投影的方差投影范数的方差为：将v表示成训练点的线性组合数据分散度——投影的方差投影范数的方差为：将v表示成训练点的829模式识别中的核方法9.1核方法概述9.2核方法基础9.3凸优化与SVM9模式识别中的核方法9.1核方法概述83凸优化与SVM超球体在嵌入空间中，寻找包含训练数据集的最小超球体。并构建检测新颖（反常）数据的算法。最大间隔超平面在嵌入空间中，寻找能将两类样本分开的最大间隔超平面，构建分类算法凸二次规划问题凸优化与SVM超球体凸二次规划问题84训练集嵌入到特征空间F中包含点集合的最小超球体寻找一个包含所有特征点的最小超球体中心是点的线性组合，且点数据点的跨度之内——对偶训练集85包含点集合的最小超球体对偶lagrange函数包含点集合的最小超球体对偶lagrange函数86最大化：约束：凸二次规划：KT条件：=0包含点集合的最小超球体最大化：约束：凸二次规划：KT条件：=0包含点集合的最小超球87基于最小超球体的新颖检测仅对支持向量有仅需要计算#SV个内积基于最小超球体的新颖检测仅对支持向量有仅需要计算#SV个内积88新颖检测稳定性那么至少在的概率下，在大小为的样本上有：令：=0，对于训练样本在的概率下，来自训练分布D的点落在以c为中心，为半径的球的外部的概率小于。新颖检测稳定性那么至少在的概率下，在大89不一味追求包含所有点——避免个别噪声影响。包含大部分点的软超球体遗漏点的损失半径过大的损失VS

松弛变量：两种损失的权衡不一味追求包含所有点——避免个别噪声影响。包含大部分点的90包含大部分点的软超球体包含大部分点的软超球体91包含大部分点的软超球体最大化：约束：凸二次规划：包含大部分点的软超球体最大化：约束：凸二次规划：92包含大部分点的软超球体选取某i，使则KT条件：=0此时根据KT条件：包含大部分点的软超球体选取某i，使93基于软超球体的新颖检测在的概率下，来自训练分布D的点被判为新颖点的概率最大为：基于软超球体的新颖检测在的概率下94v-软最小超球体软最小超球体v-软最小超球体超球体外的点有最多有个点在球外超球体内的有至少有个点不在球内v-软最小超球体软最小超球体v-软