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

机器学习-核函数基本概念§1多项式空间和多项式核函数定义1.1(核或正定核)设X是nR中的一个子集，称定义在XX上的函数),(zx是核函数，如果存在一个从X到Hilbert空间H的映射Hxx)(:(1.1)使得对任意的Xzx,，))()((),(zxzx(1.2)都成立。其中)(表示Hilbert空间H中的内积。定义1.2（d阶多项式）设nTnRxxxx)][,,][,]([21，则称乘积djjjxxx][][][21为x的一个d阶多项式，其中},,2,1{,,,21njjjd。1.有序齐次多项式空间考虑2维空间中（nRx）的模式Txxx)][,]([21，其所有的2阶单项式为21][x，22][x，21][][xx，12][][xx(1.3)注意，在表达式(1.3)中，我们把21][][xx和12][][xx看成两个不同的单项式，所以称式（1.3）中的单项式为有序单项式。这4个有序单项式张成的是一个4维特征空间，称为2阶有序齐次多项式空间，记为H。相应地可建立从原空间2R到多项式空间H的非线性映射HxxxxxxxCxxxCTT)][][,][][,][,]([)()][,]([:122122212212(1.4)同理，从nR到d阶有序齐次多项式空间H的映射可表示为HnjjjxxxxCxxxxCTdjjjdTndd}),,2,1{,,,|][][]([)()][,,][,]([:212121(1.5)这样的有序单项式djjjxxx][][][21的个数为dn，即多项式空间H的维数dHnn。如果在H中进行内积运算)()(zCxCdd，当n和d都不太小时，多项式空间H的维数dHnn会相当大。如当200n，5d时，维数可达到上亿维。显然，在多项式空间H中直接进行内积运算将会引起“维数灾难”问题，那么，如何处理这个问题呢？我们先来考查2dn的情况，计算多项式空间H中两个向量的内积2121221212222212122)(][][][][][][][][][][][][))()((zxzzxxzzxxzxzxzCxC(1.6)若定义函数2)(),(zxzx(1.7)则有),())()((22zxzCxC(1.8)即4维多项式空间H上的向量内积可以转化为原始2维空间上的向量内积的平方。对于一般的从nR到d阶有序多项式空间H的映射（1.5）也有类似的结论。定理1.1考虑由式（1.5）定义的从nR到多项式空间H的映射)(xCd，则在空间H上的内积))()((zCxCdd可表为),())()((zxzCxCdd(1.9)其中dzxzx)(),((1.10)证明：直接计算可得njnjjjjjdddddzzxxzCxC11111][][][][))()((njnjjjjjdddzxzx11111][][][][ddnjjjzxzx)()][][(1(1.11)上述定理表明，我们并不需要在高维的多项式空间H中直接做内积运算))()((zCxCdd，而利用式（1.10)给出的输入空间nR上的二元函数),(zx来计算高维多项式空间中的内积。2.有序多项式空间在式（1.5）定义的映射中，多项式空间H的分量由所有的d阶有序单项式组成。如果把该多项式空间的分量扩充为所有不超过d阶的有序单项式，便得到从nR到有序多项式空间的映射~dCTdnjjjjdTndnjjjxdxdxxdxxxCxxxxCdd}),,2,1{,,,|1,][,,][,,][][,][]([)()][,,][,]([:211~21~11(1.12)对于这个映射，我们有如下的定理：定理1.2考虑有式（1.12）定义的从nR到多项式空间H的映射~dC，则空间H上的内积))()((~~zCxCdd可表为空间nR上的内积)(zx的函数dzx)1)((，即若定义两个变量x和z的函数dzxzx)1)((),((1.13)则有),())()((~~zxzCxCdd(1.14)上述有序多项式空间的一个简单的例子是TxxxC)][,]([:21~2TxxxxxxxxxC)1,][2,][2,][][,][][,][,]([)(2112212221~2(1.15)3.无序多项式空间如果我们把式（1.4）中的21][][xx和12][][xx看作相同的单项式，那么我们就可以把从2R到4维多项式空间H的映射（1.4）简化为从2R到3维多项式空间的映射TTxxxxxx)][][,][,]([)][]([21222121(1.16)将映射（1.16）调整为)][][2,][,]([)][,]([)(2122212122xxxxxxx(1.17)则相应的多项式空间称为2阶无序多项式空间，并且有222)())()((zxzx(1.18)对式（1.5）所示的变换)(xCd按下述方式操作：把)(xCd中次序不同但因子相同的各分量合并为一个分量，并在该分量前增加一个系数，这个系数取为相应次序不同但因子相同的分量在)(xCd中出现次数的平方根。这样得到的从nR到d阶无序多项式空间的变换)(xd仍满足关系式),())()((zxzxdd(1.19)其中dzxzx)(),((1.20)根据定义1.1，我们称（1.13）和（1.20）分别为d阶多项式核函数和d阶齐次多项式核函数。比较式（1.4）定义的变换)(2xC和式（1.17）定义的)(2x可以发现，它们所映射到的多项式空间是不同的。前者是一个4维多项式空间，后者为一个3维多项式空间。但是内积是相同的，它们都可以表示为内积的函数2)(),(zxzx。这说明：多项式空间不是由核函数唯一确定的。§2Mercer核1.半正定矩阵的特征展开给定向量集合},,,{21lxxxX，其中liRxni,,2,1,。设),(zx是XX上的对称函数，我们定义ljixxKGjiij,,2,1,),,((1.21)则称)(ijGG是),(zx关于X的Gram矩阵。我们首先要研究的问题是：当Gram矩阵G满足什么条件时，函数),(K是一个核函数。定义1.2（矩阵算子）定义在lR上的矩阵算子G：对lTlRuuuu),,,(21，Gu的分量由下式确定liuxxKGujljjii,,2,1,),(][1(1.22)定义1.3（特征值和特征向量）考虑定义1.2给出的矩阵算子G。称R为它的特征值，并称v为相应的特征向量，如果vGv且v0(1.23)定义1.4（半正定性）考虑定义1.2给出的矩阵算子G。称它是半正定的，如果对lTlRuuuu),,,(21，有0),(1,jiljijiTuuxxKGuu(1.24)引理1.1若定义1.2给出的矩阵算子G是半正定的，则存在着l个非负特征值t和互相正交的单位特征向量tv，使得lttjtitjivvxxK1),(,,1,2,,ijm(1.25)证明：由于G是对称的，所以存在着正交矩阵),,,(21lvvvV和对角矩阵),,,(21ldiag，使得TVVG(1.26)这里Ttltttvvvv),,,(21是矩阵G的第t个特征向量，它对应的特征值是t。因为G是半正定的，所以所有特征值均为非负数。于是由（1.26）推知lttjtitlttjttijivvvvxxK11),((1.27)引理1.2若引理1.1的结论成立，则存在着从X到lR的映射，使得ljixxxxKjiji,,2,1,)),()((),((1.28)其中()是特征空间lR的内积。因而),(K是一个核函数。证明：定义映射lTliliiiiRvvvxx),,,()(:2211(1.29)直接验证可知引理1.2成立。引理1.3若引理1.2的结论成立，则矩阵G是半正定的。证明：设G不是半正定的，则一定存在着与一个负特征值s相对应的单位特征向量sv。定义lR中的向量zslvxxxz)](,),(),([21(1.30)则有SSSSTSSlTlTSvKvvvxxxxvz2112)](,),([)](,),([0(1.31)显然，这与s是负特征值相矛盾。因此K必须是半正定的。定理1.3设X是有限集合},,,{21lxxxX，),(zxK是定义在XX上的对称函数。则由定义1.2给出的矩阵算子G半正定，等价于),(K可表示为lttjtitjivvxxK1),((1.32)其中0t是矩阵ljijixxKG1,)),(((1.33)的特征值，Ttltttvvvv),,,(21为对应于t的特征向量，也等价于),(zxK是一个核函数，即))()((),(jijixxxxK，其中映射由式（1.29）定义。2.半正定积分算子的特征展开设输入集合为nR中的紧集X，并设),(zxK是XX的连续对称函数。我们要研究的问题是，当),(zxK满足什么条件时，它是一个核函数。定义1.5（积分算子KT）定义积分算子KT为按下式确定的在)(2xL上的积分算子)(,)(),()(2xLfdzzfzfTfTXKK(1.34)定义1.6（特征值和特征函数）考虑定义1.5给出的积分算子KT，称为它的特征值，为相应的特征函数，如果KT(1.35)定义1.7（半正定性）考虑定义1.5给出的积分算子KT。称它是半正定的，如果对)(2xLf，有0)()(),(dxdzzfxfzxKXX(1.36)引理1.4若定义1.5给出的积分算子KT是半正定的，则存在着可数个非负特征值t和相应的互相正交的单位特征函数)(xt，使得),(K可表示为XX上的一致收敛的级数1)()(),(ttttzxzxK(1.37)引理1.5若引理1.4的结论成立，则存在着nRX到Hilbert空间2l的映射，使得))()((),(zxzxK，Xzx,(1.38)其中()是2l上的内积。因而),(K是一个核函数。证明：定义映射Txxxx)),(),(()(2211：(1.39)则可验证引理1.5成立。引理1.6若引理1.5的结论成立则积分算子kT是半正定的。定理1.4（Mercer定理）令X是nR上的一个紧集，),(zxK是XX上的连续实值对称函数。则由定义1.5给出的积分算子kT半正定0)()(),(dxdzzfxfzxKXX，)(2xLf(1.40)等价于),(K可表示为XX的一致收敛序列1)()(),(itttzxzxK(1.41)其中0t是kT的特征值，)(2xLt是对应t的特征函数。它也等价于),(zxK是一个核函数))()((),(zxzxK(1.42)其中映射由式（1.39）定义，而()是Hilbert空间2l上的内积。定义1.8（Mercer核）称函数),(zxK为Mercer核，如果),(zxK是定义在XX上的连续对称函数，其中X是nR的紧集，且由定义1.5给出的积分算子是半正定的。定理1.5设X为nR上的紧集，),(zx是XX上的连续对称函数，则积分算子KT半正定的充要条件是),(zx关于任意的Xxxxl,,,21的Gram矩阵半正定。§3正定核定理1.6设X是nR的子集。若),(zx是定义在XX上的正定核，则对Xxxxl,,,21，函数),(zx关于lxxx,,,21的Gram矩阵都是半正定的。证明：),(zx是定义在XX上的正定核，因此存在着从X到Hilbert空间H的映射，使得))()((),(zxzxK(1.43)任取Xxxxl,,,21，构造),(关于l