机器学习——核函数讲义

《机器学习——核函数讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章核函数§1多项式空间和多项式核函数定义1.1(核或正定核)设是中的一个子集，称定义在上的函数是核函数，如果存在一个从到Hilbert空间的映射(1.1)使得对任意的，(1.2)都成立。其中表示Hilbert空间中的内积。定义1.2（d阶多项式）设，则称乘积为的一个d阶多项式，其中。1.有序齐次多项式空间考虑2维空间中（）的模式，其所有的2阶单项式为，，，(1.3)注意，在表达式(1.3)中，我们把和看成两个不同的单项式，所以称式（1.3）中的单项式为有序单项式。这4个有序单项式张成的是一个4维特征空间，称为2阶有序齐次多项式空间，记为。相应地可建立从

2、原空间到多项式空间的非线性映射(1.4)同理，从到阶有序齐次多项式空间的映射可表示为(1.5)这样的有序单项式的个数为，即多项式空间的维数。如果在中进行内积运算，当和都不太小时，多项式空间的维数会相当大。如当，时，维数可达到上亿维。显然，在多项式空间中直接进行内积运算将会引起“维数灾难”问题，那么，如何处理这个问题呢？我们先来考查的情况，计算多项式空间中两个向量的内积(1.6)若定义函数(1.7)则有(1.8)即4维多项式空间上的向量内积可以转化为原始2维空间上的向量内积的平方。对于一般的从到阶有序多项式空间的映射（1.5）也有类似的结论。定理1.1考虑由

3、式（1.5）定义的从到多项式空间的映射，则在空间上的内积可表为(1.9)其中(1.10)证明：直接计算可得(1.11)上述定理表明，我们并不需要在高维的多项式空间中直接做内积运算，而利用式（1.10)给出的输入空间上的二元函数来计算高维多项式空间中的内积。2.有序多项式空间在式（1.5）定义的映射中，多项式空间的分量由所有的阶有序单项式组成。如果把该多项式空间的分量扩充为所有不超过阶的有序单项式，便得到从到有序多项式空间的映射(1.12)对于这个映射，我们有如下的定理：定理1.2考虑有式（1.12）定义的从到多项式空间的映射，则空间上的内积可表为空间上的内

4、积的函数，即若定义两个变量和的函数(1.13)则有(1.14)上述有序多项式空间的一个简单的例子是(1.15)3.无序多项式空间如果我们把式（1.4）中的和看作相同的单项式，那么我们就可以把从到4维多项式空间的映射（1.4）简化为从到3维多项式空间的映射(1.16)将映射（1.16）调整为(1.17)则相应的多项式空间称为2阶无序多项式空间，并且有(1.18)对式（1.5）所示的变换按下述方式操作：把中次序不同但因子相同的各分量合并为一个分量，并在该分量前增加一个系数，这个系数取为相应次序不同但因子相同的分量在中出现次数的平方根。这样得到的从到阶无序多项式

5、空间的变换仍满足关系式(1.19)其中(1.20)根据定义1.1，我们称（1.13）和（1.20）分别为阶多项式核函数和阶齐次多项式核函数。比较式（1.4）定义的变换和式（1.17）定义的可以发现，它们所映射到的多项式空间是不同的。前者是一个4维多项式空间，后者为一个3维多项式空间。但是内积是相同的，它们都可以表示为内积的函数。这说明：多项式空间不是由核函数唯一确定的。§2Mercer核1.半正定矩阵的特征展开给定向量集合，其中。设是上的对称函数，我们定义(1.21)则称是关于的Gram矩阵。我们首先要研究的问题是：当Gram矩阵满足什么条件时，函数是一个

6、核函数。定义1.2（矩阵算子）定义在上的矩阵算子：对，的分量由下式确定(1.22)定义1.3（特征值和特征向量）考虑定义1.2给出的矩阵算子。称为它的特征值，并称为相应的特征向量，如果且(1.23)定义1.4（半正定性）考虑定义1.2给出的矩阵算子。称它是半正定的，如果对，有(1.24)引理1.1若定义1.2给出的矩阵算子是半正定的，则存在着个非负特征值和互相正交的单位特征向量，使得,(1.25)证明：由于是对称的，所以存在着正交矩阵和对角矩阵，使得(1.26)这里是矩阵的第t个特征向量，它对应的特征值是。因为是半正定的，所以所有特征值均为非负数。于是由（

7、1.26）推知(1.27)引理1.2若引理1.1的结论成立，则存在着从到的映射，使得(1.28)其中是特征空间的内积。因而是一个核函数。证明：定义映射(1.29)直接验证可知引理1.2成立。引理1.3若引理1.2的结论成立，则矩阵是半正定的。证明：设不是半正定的，则一定存在着与一个负特征值相对应的单位特征向量。定义中的向量z(1.30)则有(1.31)显然，这与是负特征值相矛盾。因此K必须是半正定的。定理1.3设是有限集合，是定义在上的对称函数。则由定义1.2给出的矩阵算子半正定，等价于可表示为(1.32)其中是矩阵(1.33)的特征值，为对应于的特征向量

8、，也等价于是一个核函数，即，其中映射由式（1.29）定义。2.半正