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

第9章 模式识别中的核方法 9 模式识别中的核方法 9.1核方法概述 9.2核方法基础 9.3凸优化与SVM 9.1核方法概述 模式识别的核方法： 首先把数据嵌入到合适的特征空间 然后采用基于线性代数、几何、统计学算法，发现嵌入数据的模式 9.1核方法概述 核方法的4个关键： 数据嵌入特征空间 在特征空间中寻找线性模式 在嵌入空间中，不需要计算点的坐标，只用两两内积 利用核函数，可以直接从初始数据高效地计算内积。 9.1核方法概述——线性回归 给定n维空间中训练集合 ，寻找齐次线性函数 使其为 S 的最优插值 9.1核方法概述——线性回归 给定n维空间中训练集合 ，寻找齐次线性函数 使其为 S 的最优插值 9.1核方法概述——岭回归 9.1核方法概述——对偶岭回归 9.1核方法概述——核函数 9.1核方法概述——核函数举例 9.1核方法概述——核函数举例 9 模式识别中的核方法 9.1核方法概述 9.2核方法基础 9.3凸优化与SVM 核矩阵 基本运算 如果 是核，B是一个半正定矩阵，p( x )是一个正系数多项式，那么下面都是核: 均值和距离 特征向量的范数: 均值和距离 特征向量线性组合的范数: 均值和距离 特征向量之间的距离: 均值和距离 均值和距离 均值和距离 中心化数据 中心化的稳定性 新颖检测举例 二分类举例 数据分散度——标准化数据 数据分散度——协方差矩阵 数据分散度——投影的方差 数据分散度——投影的方差 9 模式识别中的核方法 9.1核方法概述 9.2核方法基础 9.3凸优化与SVM 凸优化与SVM 超球体 在嵌入空间中，寻找包含训练数据集的最小超球体。并构建检测新颖（反常）数据的算法。 最大间隔超平面 在嵌入空间中，寻找能将两类样本分开的最大间隔超平面，构建分类算法 包含点集合的最小超球体 包含点集合的最小超球体 基于最小超球体的新颖检测 新颖检测稳定性 包含大部分点的软超球体 包含大部分点的软超球体 包含大部分点的软超球体 包含大部分点的软超球体 基于软超球体的新颖检测 v-软最小超球体 软最小超球体 v-软最小超球体 超球体的讨论 “硬”最小包含球。 扩大半径，保证更大的概率下包含正常点 对于个别点敏感，不健壮 软最小包含球 不要求包含所有点，考虑半径大小与遗漏点的折中 有可能将任意点排斥在外。 v-软最小包含球 给出包含于球内的点的界。 V与误差率的联系。 基于核的凸优化方法 1在高维特征空间中,在样本集 上构造优化问题 最小化目标 约束条件 最优分类界面 样本集与分类界面之间的间隔 定义为样本与分类界面之间几何间隔的最小值。 最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。 最大间隔分类器 最大间隔分类器 最大间隔分类器 最大间隔分类器 软间隔分类器 软间隔分类器 软间隔分类器 软间隔分类器 软间隔分类器 对偶lagrange 函数 最大化： 约束： 凸二次规划： KT条件：=0 包含点集合的最小超球体 仅对支持向量有 仅需要计算#SV个内积 那么至少在 的概率下，在大小为 的样本上有： 令： =0，对于训练样本 在 的概率下，来自训练分布D的点落在以c为中心， 为半径的球的外部的概率小于 。 不一味追求包含所有点——避免个别噪声影响。 遗漏点的损失 半径过大的损失 VS 松弛变量： 两种损失的权衡 最大化： 约束： 凸二次规划： 选取某 i，使 则 KT条件：=0 此时根据KT条件： 在 的概率下，来自训练分布D的点被 判为新颖点的概率最大为： v-软最小超球体 超球体外的点有 最多有 个点在球外 超球体内的有 至少有 个点不在球内 在 的概率下，来自训练分布D的点被 判为新颖点的概率最大为： 测试超球体半径平方为： v-软最小超球体的优化目标为 即取 时，测试超球体体积最小 希望 p 为定值，将概率的界固定 3