Kernel_Method

KernelMethod,PresentedbyLinZheng2July2009,Outline,BasisProblemsSpace&DimensionTwotypesofpatternrecognitionKernelsDualRepresentationsConstructingKernels,空间与维度,何时升维何时降维？升维的目的：使在低维空间线性不可分问题在高维空间变得线性可分。降维的目的：在能够正确表达事物的前提下通过减少特征表达的维数降低计算复杂度、减少冗余信息造成的误差。,空间与维度举例,在一维空间中，没有任何一个线性函数能解决下述划分问题（黑红各代表一类数据），可见线性判别函数有一定的局限性。,空间与维度举例,如果建立一个二次判别函数g(x)=(x-a)(x-b)，则可以很好的解决上述分类问题。决策规则是：如果g(x)=0，则判定x属于C1，如果g(x)0，则判定x属于C2。,空间与维度,二维N维,两类模式识别问题,线性参数模型在这类模型中，训练集要么用于估计参数向量要么用于估计后验概率分布根据输入x和输出y,训练得到一组参数w抛弃训练集，根据训练得到的参数来预测新的输入数据,两类模式识别问题,基于内存的模型对新的输入数据进行预测时需要参照训练集或者训练集的子集，比如分类算法中的“最近邻”方法。这种模型需要一个衡量标准用于计算输入空间中两个向量的相似度。特点：训练很快，预测很慢。,两类模式识别问题KNN,算法原理对于每一个待分类的数据，在训练集中找到k个最相近的邻居，使用这k个邻居的类别作为该数据的候选类别。该数据与邻居间的相似度按类别分别求和，减去一个阈值就得到了该数据的类别测度。训练时间复杂度0分类时间复杂度n,两类模型的转化,很多线性参数模型可以转换成相应的对偶问题(DualRepresentation)，在对偶问题中，预测是基于训练集的核函数(Kernel)的线性组合。什么是核函数？什么是对偶问题？,Kernels,核函数的形式核函数的作用接受两个低维空间里的向量，可以计算出经过某种变换后，在高维空间里的向量内积。,Kernels,核函数导出的多项式特征空间如何在输入空间中计算特征空间中的点积？二维,Kernels,一般化映射Cd把映射到向量Cd(x)，Cd(x)的项是x的项的所有有序d阶乘积。则有：,Kernels,核方法在模型中的角色,Kernels,核函数表达了特定应用下两个变量的相似度,Kernels,对偶问题,什么是对偶问题？任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。,对偶问题,以线性回归模型为例线性回归模型参数是由最小错误平方和公式决定的,对偶问题,公式推导要求得J(w)最小值，则以w为变量对J(w)求导,对偶问题,问题转化成从求向量a，而不需要求参数向量w（对偶表示）,对偶问题,定义Grammatrix以a为变量对J(a)求导=0，得到,对偶问题,我们把之前求得的w和a的表达式代入线性回归模型，可以得到：当对一个新的输入x进行预测时由此可见，对偶表达把最小错误平方和问题转化成核函数问题。对输入x的预测取决于训练集中目标值t的线性组合。,Kernel&Dual小结,对偶表达使得不同的定义可以解决同样的问题。在原始参数空间求w需要处理m*m阶矩阵在对偶问题中求a需要处理n*n阶矩阵虽然n比m大很多，貌似很不利，但是通过直接操作核函数可以避免显示表达特征映射，隐式的操作高维空间。,构造核函数,什么样的函数可以作为核函数呢？Mercer定理：任何半正定对称函数都可以作为核函数。1.对称性：k(x,y)=k(y,x)2.半正定性：若由组成的矩阵A为半正定矩阵，则对任意非零实数向量z有,构造核函数,构造核函数,如何产生新的核函数？借用核函数的性质，以简单的核函数为基础构造新的核函数,构造核函数,高斯核这是一个有效核，因为可以