核函数特征空间0610

CH.3核函数特征空间《导论》pp.24-46需要学习的目标函数的复杂度取决于它的表示（自变元个数、定义域、函数关系式、……），学习任务的难易程度随之而变化。线性学习器计算能力有限核表示方法的特点使用线性学习器分二类问题

分二类问题

寻找一个实值函数（决策函数）f：XR，

当f(x)0

时，输入赋给正类；当

f(x)0

时，输入赋给负类。线性学习器

使用线性假设

确定最优超平面，其控制参数为而决策规则由

给出。线性学习器计算能力有限目标概念（函数）通常不能由给定属性的简单线性函数组合产生导致使用多层阈值线性函数（如：多层神经网络、BP算法等）对目标概念的更为简洁的直接描述涉及比给定数据更为广泛的抽象特征导致核表示方法核表示方法的特点将给定数据映射到高维空间，变线性不可分情形为线性可分，来增加线性学习器的计算能力用于学习的算法和理论可以在很大程度上同应用领域的特性分开，而这些特性将在设计合适的核函数时考虑Ch.3主要内容1、特征空间和特征选择问题2、使用线性学习器学习一个非线性关系3、关于核函数的讨论4、特征空间中的计算5、核与高斯过程

使用不同技术的困难所在1、特征空间和特征选择问题

1）一个合理的思路2）定义和概念3）特征映射可能产生的困难4）特征选择面临的重要任务1）一个合理的思路需要增加一个预处理步骤，将给定数据的表达形式转换成一个与特定的学习问题（如P.25,例3.1万有引力，x→lnx)所需要的表示相匹配的一种形式。P.25“万有引力定理”，使用映射：x→lnx2）定义和概念属性：原始的数据量(或输入量)，空间X是输入空间（低维）。特征：经变化后，用于描述数据的量新空间是特征空间（高维）特征选择（特征映射）：选择最适合学习问题的数据表达方式的任务

P.26图3.1经过特征映射，使得所得数据可以线性分开P.26图3.1特征映射：二维输入空间→二维特征空间

数据线性分开：不能→能3）特征映射可能产生的困难考虑二维输入空间的情形假定关于问题的先验知识提示：相关信息已编码到自由度为2的单项式的形式，则一个可能使用的映射是：（4维）对于n维输入空间，自由度取为d的单项式形式，特征映射：若还要用到交错项的信息表示，则其特征空间的维数将很快变得不可计算。4）特征选择面临的重要任务

降低和排除维数灾难，提高计算性能和泛化性能检测出无关特征并将其去除特别是那些与目标值输出无关的特征例：万有引力计算中，物体的颜色、温度等维数约简：寻找包含原始属性中必要信息的最小特征集（d尽可能小于n)关于万有引力的例子作为学习过程的一个重要部分，如何实现自动化及避免选择的任意性。（主成分分析，…）P.26,例3.2关于万有引力定理的进一步例子：2、使用线性学习器学习一个非线性

关系1）考虑问题的思路2）到特征空间的隐式映射3）核函数方法1）考虑问题的思路应用一个固定的非线性映射Φ，将原始数据（属性）从输入空间Χ映射到特征空间F，在特征空间F中使用线性学习器，提高计算能力。所考虑的假设集是形为f(x)的函数：

（非线性特征映射）即用二步法建立一个非线性学习器。2）到特征空间的隐式映射线性学习器的一个重要性质是可以表述为对偶形式（对偶变量）针对上述变换后的假设如果能找到一种方式，避开对特征映射Φ的显式运算，而在特征空间F中直接计算内积，则可得到假设函数在对偶空间上的表示：原问题化为对偶空间（）上的一个线性学习问题，而特征空间F本身的维数N

和特征映射的显式表示不再影响计算。3）核函数方法

核的使用，避免了特征向量的显式表示，而用原始数据隐式表达了特征空间，并在对偶空间上直接训练线性学习器。关于训练样例的唯一信息是它们在特征空间上的Gram矩阵,称为核矩阵()，用粗体表示ii）核的几个简单例子（pp.28-29）iii）核函数方法的特点内积特征空间ii)核的几个简单例子特征：自由度为d

的多项式返回3.4节iii）核函数方法的特点直观想法：①创建一个复杂的特征空间②寻找该特征空间上适当的内积③寻找一种直接的方法，用原始输入计算该值实际做法：①直接定义一个核函数②通过它隐式地定义了特征空间（因此，在计算内积时，在学习器的设计中，都避开了具体的特征空间）3、关于核函数的讨论1）核函数的性质和Mercer定理2）再生核希尔伯特空间（RKHS）

(ReproducingKernelHilbertSpace)3）从核函数出发构造核函数4）从特征出发构造核函数1）核函数的性质和Mercer定理i）对称性：

ii）Cauchy-Schward不等式：

iii）非负定性——Mercer定理

a）是有限个输入组成的空间，是上对称函数

b)更一般情形iii）非负定性——Mercer定理a）是有限个输入组成的空间，是上对称函数：是核函数矩阵是半正定的（非负定）（证明：p.30命题3.5）实际对应特征映射

其中λt是K的第t个特征值，vt是λt对应的特征向量。有限维输入下，Mercer定理的证明（命题3.5）命题3.5证明（续）iii）非负定性——Mercer定理（续）b)一般情形（输入的个数可能无限）①Mercer定理：设输入空间是紧子集，假设K是连续对称函数。任意对称，非负定函数可以看作平方可积函数空间上的一个内积。①Mercer定理的说明假设K是连续对称函数b)一般情形的说明（续）决策函数在原输入空间上的表示决策函数在对偶空间上的表示2）再生核希尔伯特空间（RKHS）

(ReproducingKernelHilbertSpace)函数空间H

的引进及其产生的问题核K对于H中函数的再生性

iii）RKHS及其作用i）函数空间H的引进及其产生的问题

函数空间H

的引进：(假设空间的转换）引进一个函数空间H，H是特征空间F在映射T下的映像

由定义在输入空间X上的函数组成i）问题的产生（续）在无穷维F的情况下：H可能不包括所有可能的假设函数（它们可能是在F中没有有限范数的点的映像）H可能包括过多的函数（不利于计算、以及泛化性）提出RKHS,就是为了保证H确切地包含假设集，且有一定的附加性质。ii）核K对于H中函数的再生性ii)核K对于H中函数的再生性（续）iii)再生核希尔伯特空间（RKHS）及其作用iii)再生核希尔波特空间(RKHS)及其作用(续)③④iii）Mercer核和

再生核希尔伯特空间（RKHS）结论:(th.3.10,p.37）对定义在域上的每一个Mercer核存在一个由定义在X上的函数所组成的RKHS.H,其逆定理也成立：对线性有界函数的任意Hilbert空间，存在再生核函数。且此再生核是Mercer核。关于RKHS作用的一个例子（p.37,例3.11）＝t(xi)=yi与αi无关3）从核函数出发构造核函数确认一个对称函数是核函数的关键：函数在任意有限点集上定义的Gram矩阵是半正定的可以从简单的核出发，构造复杂的核:(p.38,命题3.12)4）从特征出发构造核函数直接通过内积的计算，从而不需要验证半正定性例如：前述的多项式核（pp.28-29）特殊：例3.15（字符串子序列核）（p.40）在非欧氏空间(离散空间)中核方法的应用潜力在非欧氏空间(离散空间)中核方法的应用潜力_2在非欧氏空间(离散空间)中核方法的应用潜力_34、特征空间中的计算1）核的使用，避免了显式计算特征向量

特征映射：得到的内嵌是非线性的，它定义了特征空间的n维子流形；此时，特征空间F中可以用对偶形式表示的点，即：映像的线性组合通常不对应任意输入点的映像（即，不一定找得到其在X中的关于的原像点），但仍然可以计算这些点之间的距离和内积。2）具体计算方法2）