《机器学习-核函数基本概念》由会员分享，可在线阅读，更多相关《机器学习-核函数基本概念（13页珍藏版）》请在金锄头文库上搜索。
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 考虑由式（1.5）定义的从到多项式空间的映射
3、，则在空间上的内积可表为 (1.9)其中 (1.10) 证明：直接计算可得 (1.11) 上述定理表明，我们并不需要在高维的多项式空间中直接做内积运算， 而利用式（1.10)给出的输入空间上的二元函数来计算高维多项式空间中的内积。 2. 有序多项式空间在式（1.5）定义的映射中，多项式空间的分量由所有的阶有序单项式组成。如果把该多项式空间的分量扩充为所有不超过阶的有序单项式，便得到从到有序多项式空间的映射(1.12)对于这个映射，我们有如下的定理：定理1.2 考虑有式（1.12）定义的从到多项式空间的映射，则空间上的内积可表为空间上的内积的函数，即若定义两个变量和的函数 (1.13)则有 (1
4、.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
5、.13）和（1.20）分别为阶多项式核函数和阶齐次多项式核函数。比较式（1.4）定义的变换和式（1.17）定义的可以发现，它们所映射到的多项式空间是不同的。前者是一个4维多项式空间，后者为一个3维多项式空间。但是内积是相同的，它们都可以表示为内积的函数。这说明：多项式空间不是由核函数唯一确定的。2 Mercer 核1.半正定矩阵的特征展开给定向量集合，其中 。设是上的对称函数，我们定义 (1.21)则称是关于的Gram矩阵。我们首先要研究的问题是：当Gram矩阵满足什么条件时，函数是一个核函数。定义 1.2 （矩阵算子）定义在上的矩阵算子：对，的分量由下式确定 (1.22)定义1.3 （特征值
6、和特征向量）考虑定义1.2给出的矩阵算子。称为它的特征值，并称为相应的特征向量，如果 且 (1.23)定义 1.4（半正定性） 考虑定义1.2给出的矩阵算子。称它是半正定的，如果对，有 (1.24)引理 1.1 若定义1.2给出的矩阵算子是半正定的，则存在着个非负特征值和互相正交的单位特征向量，使得 , (1.25)证明： 由于是对称的，所以存在着正交矩阵和对角矩阵，使得 (1.26)这里是矩阵的第t个特征向量，它对应的特征值是。因为是半正定的，所以所有特征值均为非负数。于是由（1.26）推知 (1.27) 引理 1.2 若引理1.1的结论成立，则存在着从到的映射，使得 (1.28)其中是特征
7、空间的内积。因而是一个核函数。 证明： 定义映射 (1.29)直接验证可知引理1.2成立。 引理 1.3 若引理1.2的结论成立，则矩阵是半正定的。 证明： 设不是半正定的，则一定存在着与一个负特征值相对应的单位特征向量。定义中的向量z (1.30)则有 (1.31)显然，这与是负特征值相矛盾。因此K必须是半正定的。 定理 1.3 设是有限集合，是定义在上的对称函数。则由定义1.2给出的矩阵算子半正定，等价于可表示为 (1.32)其中是矩阵 (1.33)的特征值，为对应于的特征向量，也等价于是一个核函数，即，其中映射由式（1.29）定义。2. 半正定积分算子的特征展开设输入集合为中的紧集，并设
8、是的连续对称函数。我们要研究的问题是，当满足什么条件时，它是一个核函数。 定义 1.5 （积分算子） 定义积分算子为按下式确定的在上的积分算子 (1.34) 定义 1.6 （特征值和特征函数） 考虑定义1.5给出的积分算子，称为它的特征值，为相应的特征函数，如果 (1.35) 定义 1.7 （半正定性）考虑定义1.5给出的积分算子。称它是半正定的，如果对，有 (1.36) 引理 1.4 若定义1.5给出的积分算子是半正定的，则存在着可数个非负特征值和相应的互相正交的单位特征函数，使得可表示为上的一致收敛的级数 (1.37)引理 1.5 若引理1.4的结论成立，则存在着到Hilbert空间的映射
9、，使得 ， (1.38)其中是上的内积。因而是一个核函数。证明： 定义映射 (1.39)则可验证引理1.5成立。引理 1.6 若引理1.5的结论成立则积分算子是半正定的。定理 1.4（Mercer 定理） 令是上的一个紧集，是上的连续实值对称函数。则由定义1.5给出的积分算子半正定 ， (1.40)等价于可表示为的一致收敛序列 (1.41)其中是的特征值，是对应的特征函数。它也等价于是一个核函数 (1.42)其中映射由式（1.39）定义，而是Hilbert空间上的内积。定义 1.8 （Mercer 核） 称函数为Mercer 核，如果是定义在上的连续对称函数，其中是的紧集，且由定义1.5给出的
10、积分算子是半正定的。定理 1.5 设为上的紧集，是上的连续对称函数，则积分算子半正定的充要条件是关于任意的的Gram矩阵半正定。3 正定核定理 1.6 设是的子集。若是定义在上的正定核，则对，函数关于的Gram矩阵都是半正定的。证明： 是定义在上的正定核，因此存在着从X到Hilbert空间H的映射，使得 (1.43)任取，构造关于的Gram矩阵。显然，根据由式（1.43）可以断言，对,我们有 (1.44)这表明关于的Gram矩阵是半正定的。引理 1.7 若集合S由所有的下列元素组成 (1.45)其中为任意的正整数，,则S为一个向量空间。 证明： 由于集合S中的元素对于加法和数乘封闭，所以S构成一个向量空间。 引理 1.8 若对S中的两元素 和 (1.46)定义运算 (1.47)并由此定义在上的函数，则该函数关于的Gram矩阵都是半正定的。 证明： 由知：若任意选取，记函数相应的Gram矩阵为。显然它是对称矩阵。由（1.47）可知对有： (1.48)这表明Gram矩阵是半正定的。 引理 1.9 在引理1.8中定义的运算具有如下性质：对于，有 (1.49) 证明： 任取,则关于的Gram矩阵为 (1.50)因为，所以由引理1.8可知：矩阵（1.50）是半正定的，其行列式非负。由此可知
