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

机器学习-核函数基本概念
§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阶有序齐次多项式空间，记为。相应地可建立从原空间到多项式空间的非线性映射
(1.4)
同理，从到阶有序齐次多项式空间的映射可表示为
(1.5)
这样的有序单项式的个数为，即多项式空间的维数。如果在中进行内积运算，当和都不太小时，多项式空间的维数会相当大。如当，时，维数可达到上亿维。显然，在多项式空间中直接进行内积运算将会引起“维数灾难”问题，那么，如何处理这个问题呢？
我们先来考查的情况，计算多项式空间中两个向量的内积
(1.6)
若定义函数
(1.7)
则有
(1.8)
即4维多项式空间上的向量内积可以转化为原始2维空间上的向量内积的平方。对于一般的从到阶有序多项式空间的映射（1.5）也有类似的结论。
定理1.1 考虑由式（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维多项式空间。但是内积是相同的，它们都可以表示为内积的函数。这说明：多项式空间不是由核函数唯一确定的。
§2 Mercer 核
1.半正定矩阵的特征展开
给定向量集合，其中 。设是上的对称函数，我们定义
(1.21)
则称是关于的Gram矩阵。我们首先要研究的问题是：当Gram矩阵满足什么条件时，函数是一个核函数。
定义 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个特征向量，它对应的特征值是。因为是半正定的，所以所有特征值均为非负数。于是由（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)
的特征值，为对应于的特征向量，也等价于是一个核函数，即，其中映射由式（1.29）定义。
2. 半正定积分算子的特征展开
设输入集合为中的紧集，并设是的连续对称函数。我们要研究的问题是，当满足什么条件时，它是一个核函数。
定义 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空间的映射，使得
， (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给出的积分算子是半正定的。
定理 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）是半正定的，其行列式非负。由此可知
(1.51)
引理 1.10 引理1.8中定义的运算是S上的内积运算，因而可记为
(1.52)
证明： 直接验证可知该运算具有内积运算应满足的如下性质：对和有
(1.53)
(1.54)
(1.55)
(1.56)
只需证明：若，则有。事实上，若
(1.57)
则按运算规则（1.47）知，对，有
(1.58)
由于
(1.59)
所以
(1.60)
此式意味着当时，对，都有，即为零元素。
引理 1.11 若H是引理1.7中的集合S在引理1.8中定义的内积运算意义下的闭包，则H是一个Hilbert空间。
定理 1.7 设是定义在上的对称函数。若对，函数关于的Gram矩阵都是半正定的，则是一个正定核。
证明： 定义映射
(1.61)
由引理1.7和1.11知，该映射是从X到某一Hilbert空间的映射。由式（1.58）可得到
(1.62)
由引理1.10知引理1.8中定义的运算是内积运算。利用式（1.61）可得到
(1.63)
由定义1.1知是正定核。
定义 1.12 （正定核的等价定义） 设是的子集。称定义在上的对称函数为一个正定核，如果对，相对于的Gram矩阵都是半正定的。
定义 1.13 （再生核的Hilbert空间） 令是一个非空的集合，是一个由函数组成的，内积由式（1.47）定义以及范数由定义的Hilbert空间。称是一个再生核Hilbert空间（简称RKHS）,如果存在满足如下性质
（1） 具有再生性，即对，有
(1.64)
特别地
(1.65)
（2） 张成空间，即
(1.66)
其中表示集合A的闭包。
若函数是Mercer核，则对，有

因此，一定是一个正定核。因为Mercer是正定的，所以它是再生核。

§4 核函数的构造
根据正定核的等价定义，我们可以从简单的核来构造复杂的核。
定理 1.8 设是上的核。若是从到的映射，则是上的核。特别地，若矩阵B是半正定的，则是的核。
证明： 任取，则相应的Gram矩阵为
(1.67)
记，，则有
(1.68)
由是上的正定核可知：上式右端矩阵是半正定的。从而左端矩阵半正定。所以是正定核。
当B为半正定矩阵时，它可分解为
(1.69)
定义上的核，令，则有
(1.70)
从而是正定核。
定理 1.9 若是定义在上的实值函数，则是正定核。
证明： 只需把双线性形式重写如下

(1.71)
定理 1.10 设和是上的核，。设常数，则下面的函数均是核：
（1） (1.72)
（2） (1.73)
（3） (1.74)
证明: 对给定的一个有限集合，令和分别是和相对于这个集合的Gram矩阵。
（1） 对,有
(1.75)
所以是半正定的，因而是核函数。
（2）是核函数。
（3） 设为对应于的Gram矩阵，则的元素是和对应元素的乘积
(1.76)
现证明是半正定矩阵。令,，则

(1.77)
定理 1.11 设是上的核。又设是系数全为正数的多项式。则下面的函数均是核。
（1） (1.78)
（2） (1.79)
（3） (1.80)
证明： （1）记系数全为正数的阶多项式为，则有
(1.81)
由定理1.10知结论成立。
（2）由于指数函数可以用多项式无限逼近，所以是核函数的极限。再注意到核函数是闭集，便知结论成立。
（3） 由于
(1.82)
由定理1.9知，上式右端前两个因子构成一个正定核。由定理1.8知，是一个正定核。从结论（2）可知：第三个因子也是一个正定核。由定理1.10的结论（3），便知结论成立。