机器学习-核函数基本概念

机器学习-核函数根本概念§1多项式空间和多项式核函数(核或正定核)设是中的一个子集，称定义在上的函数是核函数，如果存在一个从到Hilbert空间的映射()使得对任意的，()都成立。其中表示Hilbert空间中的内积。定义〔d阶多项式〕设，那么称乘积为的一个d阶多项式，其中。有序齐次多项式空间考虑2维空间中〔〕的模式，其所有的2阶单项式为，，，(1.3)注意，在表达式(1.3)中，我们把和看成两个不同的单项式，所以称式〔1.3〕中的单项式为有序单项式。这4个有序单项式张成的是一个4维特征空间，称为2阶有序齐次多项式空间，记为。相应地可建立从原空间到多项式空间的非线性映射(1.4)同理，从到阶有序齐次多项式空间的映射可表示为(1.5)这样的有序单项式的个数为，即多项式空间的维数。如果在中进行内积运算，当和都不太小时，多项式空间的维数会相当大。如当，时，维数可到达上亿维。显然，在多项式空间中直接进行内积运算将会引起“维数灾难”问题，那么，如何处理这个问题呢？我们先来考查的情况，计算多项式空间中两个向量的内积(1.6)假设定义函数(1.7)那么有(1.8)即4维多项式空间上的向量内积可以转化为原始2维空间上的向量内积的平方。对于一般的从到阶有序多项式空间的映射〔1.5〕也有类似的结论。考虑由式〔1.5〕定义的从到多项式空间的映射，那么在空间上的内积可表为(1.9)其中(1.10)证明：直接计算可得(1.11)上述定理说明，我们并不需要在高维的多项式空间中直接做内积运算，而利用式〔1.10)给出的输入空间上的二元函数来计算高维多项式空间中的内积。2.有序多项式空间在式〔1.5〕定义的映射中，多项式空间的分量由所有的阶有序单项式组成。如果把该多项式空间的分量扩充为所有不超过阶的有序单项式，便得到从到有序多项式空间的映射(1.12)对于这个映射，我们有如下的定理：定理1.2考虑有式〔1.12〕定义的从到多项式空间的映射，那么空间上的内积可表为空间上的内积的函数，即假设定义两个变量和的函数(1.13)那么有(1.14)上述有序多项式空间的一个简单的例子是(1.15)3.无序多项式空间如果我们把式〔1.4〕中的和看作相同的单项式，那么我们就可以把从到4维多项式空间的映射〔1.4〕简化为从到3维多项式空间的映射(1.16)将映射〔1.16〕调整为(1.17)那么相应的多项式空间称为2阶无序多项式空间，并且有(1.18)对式〔1.5〕所示的变换按下述方式操作：把中次序不同但因子相同的各分量合并为一个分量，并在该分量前增加一个系数，这个系数取为相应次序不同但因子相同的分量在中出现次数的平方根。这样得到的从到阶无序多项式空间的变换仍满足关系式(1.19)其中(1.20)根据定义1.1，我们称〔1.13〕和〔1.20〕分别为阶多项式核函数和阶齐次多项式核函数。比拟式〔1.4〕定义的变换和式〔1.17〕定义的可以发现，它们所映射到的多项式空间是不同的。前者是一个4维多项式空间，后者为一个3维多项式空间。但是内积是相同的，它们都可以表示为内积的函数。这说明：多项式空间不是由核函数唯一确定的。§2Mercer核1.半正定矩阵的特征展开给定向量集合，其中。设是上的对称函数，我们定义(1.21)那么称是关于的Gram矩阵。我们首先要研究的问题是：当Gram矩阵满足什么条件时，函数是一个核函数。〔矩阵算子〕定义在上的矩阵算子：对，的分量由下式确定(1.22)定义1.3〔特征值和特征向量〕。称为它的特征值，并称为相应的特征向量，如果且(1.23)定义〔半正定性〕。称它是半正定的，如果对，有(1.24)假设定义是半正定的，那么存在着个非负特征值和互相正交的单位特征向量，使得,5)证明：由于是对称的，所以存在着正交矩阵和对角矩阵，使得6)这里是矩阵的第t个特征向量，它对应的特征值是。因为是半正定的，所以所有特征值均为非负数。于是由〔6〕推知7)引理1.2假设引理1.1的结论成立，那么存在着从到的映射，使得8)其中是特征空间的内积。因而是一个核函数。证明：定义映射(1.29)直接验证可知引理1.2成立。引理1.3假设引理1.2的结论成立，那么矩阵是半正定的。证明：设不是半正定的，那么一定存在着与一个负特征值相对应的单位特征向量。定义中的向量z(1.30)那么有(1.31)显然，这与是负特征值相矛盾。因此K必须是半正定的。设是有限集合，是定义在半正定，等价于可表示为(1.32)其中是矩阵(1.33)的特征值，为对应于的特征向量，也等价于是一个核函数，即，其中映射由式〔1.29〕定义。2.半正定积分算子的特征展开设输入集合为中的紧集，并设是的连续对称函数。我们要研究的问题是，当满足什么条件时，它是一个核函数。〔积分算子〕定义积分算子为按下式确定的在上的积分算子(1.34)〔特征值和特征函数，称为它的特征值，为相应的特征函数，如果(1.35)定义1.7〔半正定性。称它是半正定的，如果对，有(1.36)引理1.4假设定义是半正定的，那么存在着可数个非负特征值和相应的互相正交的单位特征函数，使得可表示为上的一致收敛的级数(1.37)假设引理1.4的结论成立，那么存在着到Hilbert空间的映射，使得，(1.38)其中是上的内积。因而是一个核函数。证明：定义映射(1.39)那么可验证引理1.5成立。引理那么积分算子是半正定的。〔Mercer定理〕令是上的一个紧集，是半正定，(1.40)等价于可表示为的一致收敛序列(1.41)其中是的特征值，是对应的特征函数。它也等价于是一个核函数(1.42)其中映射由式〔〕定义，而是Hilbert空间上的内积。〔Mercer核〕称函数为Mercer核，如果是定义在上的连续对称函数，其中是的紧集，且由定义1.5给出的积分算子是半正定的。设为上的紧集，是上的连续对称函数，那么积分算子半正定的充要条件是关于任意的的Gram矩阵半正定。§3正定核定理1.6设是的子集。假设是定义在上的正定核，那么对，函数关于的Gram矩阵都是半正定的。证明：是定义在上的正定核，因此存在着从X到Hilbert空间H的映射，使得(1.43)任取，构造关于的Gram矩阵。显然，根据由式〔1.43〕可以断言，对,我们有(1.44)这说明关于的Gram矩阵是半正定的。假设集合S由所有的以下元素组成(1.45)其中为任意的正整数，,,那么S为一个向量空间。证明：由于集合S中的元素对于加法和数乘封闭，所以S构成一个向量空间。假设对S中的两元素和(1.46)定义运算(1.47)并由此定义在上的函数，那么该函数关于的Gram矩阵都是半正定的。证明：由知：假设任意选取，记函数相应的Gram矩阵为。显然它是对称矩阵。由〔1.47〕可知对有：(1.48)这说明Gram矩阵是半正定的。具有如下性质：对于，有(1.49)证明：任取,那么关于的Gram矩阵为(1.50)因为可知：0〕是半正定的，其行列式非负。由此可知(1.51)引理1.10是S上的内积运算，因而可记为(1.52)证明：直接验证可知该运算具有内积运算应满足的如下性质：对和有(1.53)(1.54)(1.55)(1.56)只需证明：假设，那么有。事实上，假设(1.57)那么按运算规那么〔1.47〕知，对，有(1.58)由于(1.59)所以(1.60)此式意味着当时，对，都有，即为零元素。假设H是引理1.7中的集合S在引理1.8中定义的内积运算意义下的闭包，那么H是一个Hilbert空间。定理1.7设是定义在上的对称函数。假设对，函数关于的Gram矩阵都是半正定的，那么是一个正定核。证明：定义映射(1.61)由引理1.7和1.11知，该映射是从X到某一Hilbert空间的映射。由式〔1.58〕可得到(1.62)是内积运算。利用式〔1.61〕可得到(1.63)是正定核。〔正定核的等价定义〕设是的子集。称定义在上的对称函数为一个正定核，如果对，相对于的Gram矩阵都是半正定的。〔再生核的Hilbert空间〕令是一个非空的集合，是一个由函数组成的，内积由式〔1.47〕定义以及范数由定义的Hilbert空间。称是一个再生核Hilbert空间〔简称RKHS〕,如果存在满足如下性质具有再生性，即对，有(1.64)特别地(1.65)张成空间，即(1.66)其中表示集合A的闭包。假设函数是Mercer核，那么对，有因此，一定是一个正定核。因为Mercer是正定的，所以它是再生核。§4核函数的构造根据正定核的等价定义，我们可以从简单的核来构造复杂的核。定理1.8设是上的核。假设是从到的映射，那么是上的核。特别地，假设矩阵B是半正定的，那么是的核。证明：任取，那么相应的Gram矩阵为(1.67)记，，那么有(1.68)由是上的正定核可知：上式右端矩阵是半正定的。从而左端矩阵半正定。所以是正定核。当B为半正定矩阵时，它可分解为(1.69)定义上的核，令，那么有(1.70)从而是正定核。定理1.9假设是定义在上的实值函数，那么是正定核。证明：只需把双线性形式重写如下1)0设和是上的核，。设常数，那么下面的函数均是核：〔1〕2)〔2〕3)〔3〕4)证明:对给定的一个有限集合，令和分别是和相对于这个集合的Gram矩阵。对,有5)所以是半正定的，因而是核函数。〔2〕是核函数。〔3〕设为对应于的Gram矩阵，那么的元素是和对应元素的乘积6)现证明是半正定矩阵。令,，那么7)1设是上的核。又设是系数全为正数的多项式。那么下面的函数均是核。〔1〕8)〔2〕