【摘 要】 协方差函数是高斯过程方法的核心,本文给出了关于协方差函数的概述。
【原 文】 Rasmussen, C.E. and Williams, C.K. (2006), Chapter 4 of Gaussian processes for machine learning. Cambridge, Mass: MIT press Cambridge, MA (3).
第 4 章 协方差函数
我们已经看到,协方差函数是高斯过程预测器中的关键成分,因为它编码了我们对所希望学习的函数的假设。从稍微不同的角度来看,很明显在监督学习中数据点之间的相似性概念是至关重要的;一个基本假设是输入 x \mathbf{x} x 接近的点可能具有相似的目标值 y y y ,因此靠近测试点的训练点应该提供有关该点预测的信息。在高斯过程视图下,协方差函数定义了接近度或相似度。
输入对 x \mathbf{x} x 和 x ′ \mathbf{x}' x ′ 的任意函数通常不会是有效的协方差函数。本章的目的是给出一些常用协方差函数的示例并检查它们的性质。
第 4.1 节定义了一些与协方差函数相关的基本术语。
第 4.2 节给出了平稳、点积和其他非平稳协方差函数的示例,还给出了一些从旧函数创建新函数的方法。
第 4.3 节介绍了协方差函数的特征函数分析这一重要主题,并陈述了 Mercer 定理,该定理允许我们根据其特征函数和特征值来表达协方差函数(在特定条件下)。当输入域 X \mathcal{X} X 是 R D \mathbb{R}^D R D 的子集时,第 4.2 节给出的协方差函数有效。
第 4.4 节描述了当输入域位于结构化对象(例如字符串和树)上时定义协方差函数的方法。
4.1 预备知识
4.1.1 基本概念
(1) 平稳协方差函数
平稳协方差函数是 x − x ′ \mathbf{x} − \mathbf{x}' x − x ′ 的函数。因此它对于输入空间具有平移不变性。例如,式 2.16
中给出的平方指数协方差函数是平稳的。如果进一步,协方差函数仅是 ∣ x − x ′ ∣ |\mathbf{x − x'}| ∣ x − x ′ ∣ 的函数,则称为各向同性;因此它对所有刚性运动都是不变的。例如,式(2.16)
中给出的平方指数协方差函数是各向同性的。由于 k k k 现在只是 r = ∣ x − x ′ ∣ r = |\mathbf{x − x'}| r = ∣ x − x ′ ∣ 的函数,这些也称为 径向基函数 (RBF) 。
(2)点积协方差函数
如果协方差函数仅通过点积 x ⋅ x ′ \mathbf{x \cdot x'} x ⋅ x ′ 依赖于 x \mathbf{x} x 和 x ′ \mathbf{x'} x ′ ,则我们称其为 点积协方差函数 。一个简单例子是协方差函数 k ( x , x ′ ) = σ 0 2 + x ⋅ x ′ k(\mathbf{\mathbf{x,x'}}) = \sigma^2_0 + \mathbf{x \cdot x'} k ( x , x ′ ) = σ 0 2 + x ⋅ x ′ ,它可以通过将 N ( 0 , 1 ) \mathcal{N}(0, 1) N ( 0 , 1 ) 放在 D D D 个 x d x_d x d 上和将 N ( 0 , σ 0 2 ) \mathcal{N}(0, \sigma^2_0) N ( 0 , σ 0 2 ) 放在偏置(或常量函数)1 上的形成,参见 式(2.15)
。另一个重要例子是非齐次多项式核 k ( x , x ′ ) = ( σ 0 2 + x ⋅ x ′ ) p k(\mathbf{\mathbf{x,x'}}) = (\sigma^2_0 + \mathbf{x \cdot x'})^p k ( x , x ′ ) = ( σ 0 2 + x ⋅ x ′ ) p 其中 p p p 是一个正整数。点积协方差函数对于坐标围绕原点的旋转具有不变性,但对平移不行。
(3)核函数的定义
将一对输入 x , x ′ ∈ X \mathbf{x} , \mathbf{x}' \in \mathcal{X} x , x ′ ∈ X 映射到 R \mathbb{R} R 的函数 k k k ,被统称为 核或核函数 。
核这个术语源自积分运算理论,某个积分运算 T k T_k T k 可以被定义为
( T k f ) ( x ) = ∫ X k ( x , x ′ ) f ( x ′ ) d μ ( x ′ ) (4.1) (T_kf )(\mathbf{x}) = \int_\mathcal{X} k(\mathbf{\mathbf{x,x'}}) f(\mathbf{x}') dμ(\mathbf{x}') \tag{4.1}
( T k f ) ( x ) = ∫ X k ( x , x ′ ) f ( x ′ ) d μ ( x ′ ) ( 4.1 )
其中 μ μ μ 表示某种测度;有关这一点的进一步解释,请参阅 第 A.7 节
。
A.7-测度与积分 A.7 测度与积分
在这里,我们勾勒出关于测度和积分的定义,更两者更全面的介绍,可以参考 Doob [1994] 和 Bartle [1995] 。
【测度】
令 Ω Ω Ω 为某个实验的所有可能输出构成的集合,例如,对于一个 D D D 维实值变量而言,Ω = R D Ω = \mathbb{R}^D Ω = R D 。令 F \mathcal{F} F 为 Ω Ω Ω 的某些子集的 σ σ σ -域,其中包含了我们可能感兴趣的所有事件。当 μ \mu μ 为非负实数时,如果对于所有互不相交的集合 A 1 , A 2 , … ∈ F A_1,A_2,\ldots \in \mathcal{F} A 1 , A 2 , … ∈ F ,μ μ μ 均能满足下式,则称 μ μ μ 是可数的加性测度。
μ ( ⋃ i = 1 ∞ A i ) = ∑ i = 1 ∞ μ ( A i ) (A.26) μ \left( \bigcup^{\infty}_{i=1} A_i \right)= \sum^{\infty}_{i=1} μ(A_i) \tag{A.26}
μ ( i = 1 ⋃ ∞ A i ) = i = 1 ∑ ∞ μ ( A i ) ( A.26 )
有限测度 :如果 μ ( Ω ) < ∞ μ(Ω) < \infty μ ( Ω ) < ∞ ,则 μ μ μ 被称为 有限测度 ;
概率测度 :如果 μ ( Ω ) = 1 μ(Ω) = 1 μ ( Ω ) = 1 ,则称为 概率测度 ;
Lebesgue 测度 :Lebesgue 测度定义了对欧几里得空间子集的统一测度。这里适当的 σ σ σ -代数是 Borel σ σ σ -代数 B D \mathcal{B}^D B D ,其中 B \mathcal{B} B 是由 R \mathbb{R} R 的开放子集生成的 σ σ σ -代数。例如在直线 R R R 上,区间 ( a , b ) (a, b) ( a , b ) 的勒贝格测度是 b − a b − a b − a 。
【积分】
我们现在将 Ω Ω Ω 限制为 R D \mathbb{R}^D R D ,并希望赋予函数 f : R D → R f:\mathbb{R}^D \rightarrow \mathbb{R} f : R D → R 关于测度 μ μ μ 的积分意义:
∫ f ( x ) d μ ( x ) (A.27) \int f(\mathbf{x}) dμ(\mathbf{x}) \tag{A.27}
∫ f ( x ) d μ ( x ) ( A.27 )
假设 f f f 是可测的,也就是说,对于任何 Borel-可测集合 A ∈ R A \in \mathbb{R} A ∈ R ,有 f − 1 ( A ) ∈ B D f^{−1}(A) \in \mathcal{B}^D f − 1 ( A ) ∈ B D 。通常有两种情况会让我们感兴趣:
(i)当 μ μ μ 是勒贝格测度时;
(ii)当 μ μ μ 是概率测度时。
对于第一种情况,式 (A.27)
简化为普通的积分符号 ∫ f ( x ) d x \int f(\mathbf{x})d \mathbf{x} ∫ f ( x ) d x 。
对于 x \mathbf{x} x 上的概率测度 μ μ μ ,非负函数 p ( x ) p(\mathbf{x}) p ( x ) 称为测度的密度,如果对于所有 A ∈ B D A \in \mathcal{B}^D A ∈ B D ,我们有
μ ( A ) = ∫ A p ( x ) d x (A.28) μ(A) = \int A p(\mathbf{x}) d \mathbf{x} \tag{A.28}
μ ( A ) = ∫ A p ( x ) d x ( A.28 )
如果存在这样的密度,则它几乎在任何地方都是唯一确定的,即测度为零的集合除外。并非所有概率测度都具有密度,只有将零概率分配给 x \mathbf{x} x 空间中的各个点的分布才能具有密度。如果 p ( x ) p(\mathbf{x}) p ( x ) 存在,则我们有
∫ f ( x ) d μ ( x ) = ∫ f ( x ) p ( x ) d x (A.29) \int f(\mathbf{x}) d μ(\mathbf{x}) = \int f(\mathbf{x}) p(\mathbf{x}) d \mathbf{x} \tag{A.29}
∫ f ( x ) d μ ( x ) = ∫ f ( x ) p ( x ) d x ( A.29 )
如果 μ μ μ 没有密度表达式,式 (A.27)
在勒贝格积分的标准构造下仍然有意义。
对于 Ω = R D Ω = \mathbb{R}^D Ω = R D ,概率测度 μ μ μ 可以与分布函数 F : R D → [ 0 , 1 ] F:\mathbb{R}^D \rightarrow [0, 1] F : R D → [ 0 , 1 ] 相关,该函数定义为 F ( z ) = μ ( x 1 ≤ z 1 , … x D ≤ z D ) F(\mathbf{z}) = μ(x_1 \leq z_1, \ldots x_D \leq z_D) F ( z ) = μ ( x 1 ≤ z 1 , … x D ≤ z D ) 。分布函数比密度更通用,因为它总是为给定的概率测度定义的。具有分布函数但没有密度的随机变量的一个简单示例可通过以下构造获得:抛硬币,正面朝上的概率为 p p p ;如果正面朝上 x x x 是从 U ( 0 , 1 ) U (0, 1) U ( 0 , 1 ) 中选择的([ 0 , 1 ] [0, 1] [ 0 , 1 ] 上的均匀分布),否则x x x 设置为 1 / 2 1/2 1/2 (概率为 1 − p 1 − p 1 − p )。该分布在 x = 1 / 2 x = 1/2 x = 1/2 处有一个 “质点”(或原子)。
如果 k ( x , x ′ ) = k ( x ′ , x ) k(\mathbf{\mathbf{x,x'}}) = k(\mathbf{x', x}) k ( x , x ′ ) = k ( x ′ , x ) 成立,则称核是对称的;显然,协方差函数必须是对称定义的。
给定一组输入 { x i ∣ i = 1 , … , n } \{\mathbf{x}_i | i = 1,\ldots, n\} { x i ∣ i = 1 , … , n } , 我们可以计算出元素值 K i j = k ( x i , x j ) K_{ij} = k(\mathbf{x}_i,\mathbf{x}_j) K ij = k ( x i , x j ) 的 Gram 矩阵 K K K 。当核 k k k 是一个协方差函数时,其对应的 Gram 矩阵 K K K 即为协方差矩阵。
注:
(1)任意能够实现 式(4.1)
积分的函数,都可以被成为核函数;因此核的内涵要大于协方差函数。参见 《核的性质》 ;
(2)从数学性质上:普通核函数对应的 Gram 矩阵不一定是半正定的,但协方差函数对应的 Gram 矩阵必须是半正定的;
(3)在实际使用中,协方差函数通常主要是人们感兴趣的几种半正定类型;
(4)平稳协方差函数是最常用的类型,它将两点之间的核函数具体化为两者之间某种(欧式)距离的函数。
(5)点积协方差函数与核方法具有紧密联系。
(4)协方差函数与核函数的重要区别:半正定性
如果对于任意向量 v ∈ R n \mathbf{v} \in \mathbb{R}^n v ∈ R n ,n × n n \times n n × n 的实值矩阵 K K K 都能满足条件 Q ( v ) = v ⊤ K v ≥ 0 Q(\mathbf{v}) = \mathbf{v}^{\top} K \mathbf{v} \geq 0 Q ( v ) = v ⊤ K v ≥ 0 ,则称 K K K 为半正定矩阵 (PSD)。如果仅当 v = 0 \mathbf{v = 0} v = 0 时 Q ( v ) = 0 Q(\mathbf{v}) = 0 Q ( v ) = 0 ,则矩阵是正定的。此时的 Q ( v ) Q(\mathbf{v}) Q ( v ) 称为二次型。一个对称矩阵是半正定的当且仅当该矩阵的所有特征值都非负。
普通核函数对应的 Gram 矩阵不一定是半正定的,但协方差函数对应的 Gram 矩阵必须是半正定的。
一个核函数被称为半正定,如果满足:
∫ k ( x , x ′ ) f ( x ) f ( x ′ ) d μ ( x ) d μ ( x ′ ) ≥ 0 (4.2) \int k(\mathbf{x,x'}) f(\mathbf{x}) f(\mathbf{x'}) dμ(\mathbf{x}) dμ(\mathbf{x'}) \geq 0 \tag{4.2}
∫ k ( x , x ′ ) f ( x ) f ( x ′ ) d μ ( x ) d μ ( x ′ ) ≥ 0 ( 4.2 )
上式中所有 f ∈ L 2 ( X , μ ) f \in L_2(\mathcal{X}, μ) f ∈ L 2 ( X , μ ) 。
等效地,对于 n ∈ N n \in \mathbb{N} n ∈ N 和任意 D \mathcal{D} D ,能够产生半正定 Gram 矩阵的核函数也是正半定的。
为了看到这一点,令 f f f 为每个 x i \mathbf{x}_i x i 处的 delta 函数的加权和。由于此类函数是 L 2 ( X , μ ) L_2(\mathcal{X},\mu) L 2 ( X , μ ) 中函数的极限, 式(4.2)
暗示任意 D \mathcal{D} D 对应的 Gram 矩阵是半正定的。
我们现在描述随机过程的均方连续性和可微性,依据 Adler [1981,sec. 2.2]。
4.1.2 函数的均方连续性
令 x 1 , x 2 , … \mathbf{x_1, x_2,\ldots} x 1 , x 2 , … 是一个点序列,x ∗ \mathbf{x}_* x ∗ 是 R D \mathbb{R}^D R D 中的一个不动点,且当 k → ∞ k \rightarrow \infty k → ∞ 时,有 ∣ x k − x ∗ ∣ → 0 |\mathbf{x}_k − \mathbf{x}_*| \rightarrow 0 ∣ x k − x ∗ ∣ → 0 。如果当 k → ∞ k \rightarrow \infty k → ∞ 时,同时有 E [ ∣ f ( x k ) − f ( x ∗ ) ∣ 2 ] → 0 \mathbb{E}[|f(\mathbf{x}_k) − f(\mathbf{x}_*)|^2] \rightarrow 0 E [ ∣ f ( x k ) − f ( x ∗ ) ∣ 2 ] → 0 ,则称过程 f ( x ) f(\mathbf{x}) f ( x ) 在 x ∗ \mathbf{x}_* x ∗ 处均方连续。
其有以下性质:
域的均方连续性 :如果上述性质对所有 x ∗ ∈ A \mathbf{x}_* \in A x ∗ ∈ A 都成立(A A A 是 R D \mathbb{R}^D R D 的子集),则称过程 f ( x ) f(\mathbf{x}) f ( x ) 在域 A A A 上均方连续。
均方连续的充分必要条件 :随机场在 x ∗ \mathbf{x}_* x ∗ 处均方连续的充分必要条件是,其协方差函数 k ( x , x ′ ) k(\mathbf{x,x'}) k ( x , x ′ ) 在点 x = x ′ = x ∗ \mathbf{x = x' = x_*} x = x ′ = x ∗ 处连续。
根据上述性质,平稳协方差函数只需检查 k ( 0 ) k(\mathbf{0}) k ( 0 ) 处的连续性即可。
请注意:均方连续性并不一定意味着函数样本的连续性 ;有关函数样本连续性和可微性的讨论,参见 Adler [1981, ch. 3]。
4.1.3 函数的均方可微性
当如下极限存在时,f ( x ) f(\mathbf{x}) f ( x ) 被称为在第 i i i 个方向上是均方可导的:
∂ f ( x ) ∂ x i = l.i.m h → 0 f ( x + h e i ) − f ( x ) h (4.4) \frac{∂f(\mathbf{x})}{∂x_i} = \operatorname{l.i.m}_{h \rightarrow 0} \frac{f(\mathbf{x} + h \mathbf{e}_i) − f(\mathbf{x})}{h} \tag{4.4}
∂ x i ∂ f ( x ) = l.i.m h → 0 h f ( x + h e i ) − f ( x ) ( 4.4 )
其中 l.i.m \operatorname{l.i.m} l.i.m 表示均方极限,e i \mathbf{e}_i e i 是第 i i i 个方向上的单位向量。
其有如下性质:
均方导数 ∂ f ( x ) / ∂ x i ∂f(\mathbf{x})/∂x_i ∂ f ( x ) / ∂ x i 的协方差函数,可以由 f f f 的协方差函数的导数 ∂ 2 k ( x , x ′ ) / ∂ x i ∂ x i ′ ∂^2 k(\mathbf{x,x'})/∂x_i∂x'_i ∂ 2 k ( x , x ′ ) / ∂ x i ∂ x i ′ 给出。
上一条性质可以进一步扩展到高阶导数。
利用上述性质可知:对于平稳随机过程,如果 2 k 2k 2 k 阶偏导数 ∂ 2 k k ( x ) / ∂ 2 x i 1 … ∂ 2 x i k ∂^{2k}k(\mathbf{x})/∂^2x_{i_1} \ldots ∂^2x_{ik} ∂ 2 k k ( x ) / ∂ 2 x i 1 … ∂ 2 x ik 存在,并且在 x = 0 \mathbf{x = 0} x = 0 时有限,则对于所有 x ∈ R D \mathbf{x} \in \mathbb{R}^D x ∈ R D ,随机过程的 k k k 阶偏导数 ∂ k f ( x ) / ∂ x i 1 … x i k ∂^k f(\mathbf{x})/∂x_{i_1} \ldots x_{ik} ∂ k f ( x ) / ∂ x i 1 … x ik (作为均方极限)存在。
请注意: 核 k k k 在 0 0 0 附近的特性决定了平稳过程的平滑特性(均方可微性) 。
4.2 常见协方差函数
在本节中,我们考虑协方差函数,其中输入域 X \mathcal{X} X 是向量空间 R D \mathbb{R}^D R D 的子集(注:第 4.4 节
会考虑更一般的输入空间)。
第 4.2.1 节
介绍最常用的平稳协方差函数
第 4.2.2 节
介绍点积协方差函数
第 4.2.3 节
介绍部分非平稳的协方差函数
第 4.2.4 节
中描述从旧核构建新核的一般性方法。
表 4.1
中汇总了一些常用协方差函数。此外,关于协方差函数还有几个很好的综述,参见例如 Abrahamsen [1997]。
4.2.1 平稳协方差函数
4.2.1.1 平稳协方差函数的性质
(1)平稳协方差函数的谱密度
在本节(和第 4.3 节
)中,将核理解为从 x , x ′ ∈ X \mathbf{x},\mathbf{x'} \in \mathcal{X} x , x ′ ∈ X 到复数空间 C \mathbb{C} C (而不是实数空间 R \mathbb{R} R )的映射会更方便我们理解。如果零均值过程 f f f 是复值的,则协方差函数可以被定义为复数形式: k ( x , x ′ ) = E [ f ( x ) f ∗ ( x ′ ) ] k(\mathbf{x,x'}) = \mathbb{E}[f(\mathbf{x}) f^*(\mathbf{x'})] k ( x , x ′ ) = E [ f ( x ) f ∗ ( x ′ )] ,其中 ∗ * ∗ 表示复共轭。
平稳协方差函数是关于 τ = x − x ′ \boldsymbol{τ} = \mathbf{x − x'} τ = x − x ′ 的函数。因此,我们有时会将平稳协方差函数 k k k 写成单参数形式,即 k ( τ ) k(\boldsymbol{τ}) k ( τ ) 。一个平稳协方差函数可以被表示为 有限正值测度的傅里叶变换 ,即如下 Bochner 定理。
【定理 4.1(Bochner 定理)】 一个在 R D \mathbb{R}^D R D 上定义的(复值)函数 k k k 是一个(弱平稳均方连续复值随机过程的)核函数,当且仅当 k k k 可以被表示为:
k ( τ ) = ∫ R D e 2 π i s ⋅ τ d μ ( s ) (4.5) k(τ) = \int_{\mathbb{R}^D} e^{2πi \mathbf{s} \cdot \boldsymbol{τ}} dμ(\mathbf{s}) \tag{4.5}
k ( τ ) = ∫ R D e 2 πi s ⋅ τ d μ ( s ) ( 4.5 )
其中 μ μ μ 是有限正值测度。 Bochner 定理引自 Stein [1999, p. 24];可以在 Gihman 和 Skorohod [1974] 中找到证明。
如果测度 μ μ μ 自身具有某种概率密度 S ( s ) S(\mathbf{s}) S ( s ) ,则 S S S 被称为对应于 k k k 的 谱密度 或 功率谱 。 式(4.5)
给出的构造,将非负功率值置入每个频率分量 s \mathbf{s} s ;这等价于 式(2.4)
中对协方差矩阵 Σ p \Sigma_p Σ p 的非负定要求。
在谱密度 S ( s ) S(\mathbf{s}) S ( s ) 存在的情况下,协方差函数和谱密度是彼此的傅立叶对偶,如 式(4.6)
所示;这也被称为 维纳-辛钦( Wiener-Khintchine )定理 ,参见 Chatfield [1989]
k ( τ ) = ∫ S ( s ) e 2 π i s ⋅ τ d s S ( s ) = ∫ k ( τ ) e − 2 π i s ⋅ τ d τ (4.6) \begin{align*}
&k(\boldsymbol{τ}) = \int S(\mathbf{s}) e^{2πi \mathbf{s} \cdot \boldsymbol{τ}} d \mathbf{s}\\
&S(\mathbf{s}) = \int k(\boldsymbol{τ})e^{−2πi \mathbf{s} \cdot \boldsymbol{τ}}d \boldsymbol{τ}
\end{align*} \tag{4.6}
k ( τ ) = ∫ S ( s ) e 2 πi s ⋅ τ d s S ( s ) = ∫ k ( τ ) e − 2 πi s ⋅ τ d τ ( 4.6 )
请注意: 过程的方差为 k ( 0 ) = ∫ S ( s ) d s k(\mathbf{0}) = \int S(\mathbf{s}) d \mathbf{s} k ( 0 ) = ∫ S ( s ) d s , 也就是说,功率谱必须满足可积条件才能定义有效的高斯过程 。
要获得对 式(4.6)
中功率谱的一些直觉,一定要意识到: 复指数 e 2 π i s ⋅ x e^{2πi \mathbf{s \cdot x}} e 2 πi s ⋅ x 是某个平稳核的(关于 Lebesgue 测度的)特征函数 (详细信息参见 第 4.3 节
)。而 S ( s ) S(\mathbf{s}) S ( s ) 可以被视为分配给特征函数 e 2 π i s ⋅ x e^{2πi \mathbf{s \cdot x}} e 2 πi s ⋅ x (其频率为 s \mathbf{s} s )的功率量。还要意识到,当频率 ∣ s ∣ → ∞ |\mathbf{s}| \rightarrow \infty ∣ s ∣ → ∞ 时,S ( s ) S(\mathbf{s}) S ( s ) 必须衰减得足够快,否则无法满足可积条件。与此同时,功率谱的衰减率也可以提供关于随机过程平滑度的重要信息。例如:它可以确定过程的均方可微性(详细信息参见第 4.3 节
)。
Bochner 定理定义了函数的谱分解,但其中隐含了一个简单的正定性判决方法:一个函数是正定的当且仅当其傅里叶变换为正 。
核函数正定的定义为:对于函数 k ( τ ) k(\tau) k ( τ ) 和 ∀ n , ∀ t 1 , t 2 , … , t n \forall n,\forall t_1,t_2,\ldots,t_n ∀ n , ∀ t 1 , t 2 , … , t n ,由 k ( t i − t j ) k(t_i - t_j) k ( t i − t j ) 组成的矩阵是正定的。其中 k ( t i − t j ) k(t_i - t_j) k ( t i − t j ) 为矩阵第 i i i 行第 j j j 列的元素。
矩阵正定的定义:对于一个 n × n n \times n n × n 的实对称矩阵 K \mathbf{K} K ,对于任意一个长度为 n n n 的非 0 0 0 向量 α \boldsymbol{\alpha} α ,都有 α T K α ≥ 0 \boldsymbol{\alpha}^T \mathbf{K} \boldsymbol{\alpha} \geq 0 α T K α ≥ 0 (注:还有其他等价表现),则 K \mathbf{K} K 称为半正定矩阵。
如果仅依据函数正定的定义,我们需要根据根据核矩阵的正定性来判断核函数的正定型,也就是说我们很难直接判断一个核函数是否正定。而 Bochner 定理的一个推论表明: 一个函数如果是正定的那么其傅里叶变换一定是正的 。这让人们对函数正定有了更加直观的了解。用数学语言描述如下:
k ( τ ) 是正定的 ⇔ ∫ − ∞ + ∞ k ( τ ) e − j ω t d τ = S ( ω ) ⩾ 0 k(\tau) \text{ 是正定的 } \Leftrightarrow \int_{-\infty }^{+\infty} k(\tau) e^{-j\omega t}d \tau = S(\omega )\geqslant 0
k ( τ ) 是正定的 ⇔ ∫ − ∞ + ∞ k ( τ ) e − jω t d τ = S ( ω ) ⩾ 0
(2)各向同性平稳协方差函数的谱密度
如果协方差函数是各向同性的(因此是标量 r r r 的函数,其中 r = ∣ τ ∣ r = |\boldsymbol{τ}| r = ∣ τ ∣ ),则可以证明 S ( s ) S(\mathbf{s}) S ( s ) 也对应于一个标量 s ≜ ∣ s ∣ s \triangleq |\mathbf{s}| s ≜ ∣ s ∣ 的函数 [Adler,1981 年,定理 2.5.2]。此时,式 (4.6)
中的对偶关系可以改写为球面极坐标形式,在积分掉角度变量后(因为各向同性),可以简化为(参见例如 Bracewell, 1986, ch. 12):
k ( r ) = 2 π r D / 2 − 1 ∫ 0 ∞ S ( s ) J D / 2 − 1 ( 2 π r s ) s D / 2 d s (4.7) k(r) = \frac{2π}{r^{D/2−1}} \int^\infty_0 S(s) J_{D/2−1}(2π rs) s^{D/2} ds \tag{4.7}
k ( r ) = r D /2 − 1 2 π ∫ 0 ∞ S ( s ) J D /2 − 1 ( 2 π rs ) s D /2 d s ( 4.7 )
S ( s ) = 2 π s D / 2 − 1 ∫ 0 ∞ k ( r ) J D / 2 − 1 ( 2 π r s ) r D / 2 d r (4.8) S(s) = \frac{2π }{s^{D/2−1}} \int^\infty_0 k(r)J_{D/2−1}(2π rs)r^{D/2} dr \tag{4.8}
S ( s ) = s D /2 − 1 2 π ∫ 0 ∞ k ( r ) J D /2 − 1 ( 2 π rs ) r D /2 d r ( 4.8 )
式中,J ν ( z ) J_ν(z) J ν ( z ) 是第一类贝塞尔函数。
请注意, 式(4.7)
中对维数 D D D 的依赖性意味着: 同一各向同性的谱密度函数形式,在不同维数 D D D 下会产生不同的各向同性协方差函数 。反之亦然,如果我们从一个特定的各向同性协方差函数 k ( r ) k(r) k ( r ) 出发,则其对应的谱密度形式也取决于 D D D (例如 式(4.15)
中给出的 Matern 族谱密度),事实上 k ( r ) k(r) k ( r ) 有可能无法适用于所有维数 D D D 。谱密度存在的一个必要条件是 ∫ r D − 1 ∣ k ( r ) ∣ d r < ∞ \int r^{D−1} | k(r)| dr < \infty ∫ r D − 1 ∣ k ( r ) ∣ d r < ∞ ;参见 Stein [1999, sec. 2.10]。
我们现在给出一些常用的各向同性协方差函数的例子。这些协方差函数以标准化形式给出,其中 k ( 0 ) = 1 k(0) = 1 k ( 0 ) = 1 ;我们可以将 k k k 乘以一个(正)常数 σ f 2 σ^2_f σ f 2 以获得任何所需的过程方差。
4.2.1.2 平方指数函数
(1)函数形式
平方指数 (SE) 协方差函数已在第 2 章 式(2.16)
中有过介绍。形式为:
k S E ( r ) = exp ( − r 2 2 ℓ 2 ) (4.9) k_{SE}(r) = \exp \left( − \frac{r^2}{2\ell^2} \right) \tag{4.9}
k SE ( r ) = exp ( − 2 ℓ 2 r 2 ) ( 4.9 )
参数 ℓ \ell ℓ 定义特征长度尺度。使用 式(4.3)
我们看到 1d 中平方指数过程的零级上交叉平均数是 ( 2 π ℓ ) − 1 (2π \ell)^{−1} ( 2 π ℓ ) − 1 ,这证实了 ℓ \ell ℓ 作为长度尺度的角色。这个协方差函数是无限可微的,这意味着具有这个协方差函数的高斯过程具有所有阶的均方导数,因此非常平滑。
(2)谱密度
平方指数协方差函数的谱密度为
S ( s ) = ( 2 π ℓ 2 ) D / 2 exp ( − 2 π 2 ℓ 2 s 2 ) S(\mathbf{s}) = (2π \ell^2)^{D/2} \exp(−2π^2 \ell^2 s^2)
S ( s ) = ( 2 π ℓ 2 ) D /2 exp ( − 2 π 2 ℓ 2 s 2 )
Stein [1999] 认为这种强平滑假设对于模拟许多物理过程不现实,并推荐使用 Matern 族协方差函数(见下文)。不过,平方指数可能是核机器领域中使用最广泛的核。
平方指数核是无限可分的,因为对于所有 t > 0 t > 0 t > 0 , ( k ( r ) ) t (k(r))^t ( k ( r ) ) t 都是有效核;将 k k k 提高到 t t t 次方的效果只是重新缩放 ℓ \ell ℓ 。
(3)与无限宽神经网络的关系 关于平方指数协方差函数有一个非常著名的论断: 单隐层的无限宽神经网络等效于一个协方差函数为平方指数的高斯过程 。
下面做一简要证明。
将输入 x \mathbf{x} x 通过高斯形基函数扩展到特征空间(可以视为神经网络的隐藏层),同样可以获得平方指数协方差函数。为了简化证明,我们考虑具有标量输入的如下基函数:
ϕ c ( x ) = exp ( − ( x − c ) 2 2 ℓ 2 ) (4.10) \phi_c(\mathbf{x}) = \exp(− \frac{(x − c)^2}{2 \ell^2} ) \tag{4.10}
ϕ c ( x ) = exp ( − 2 ℓ 2 ( x − c ) 2 ) ( 4.10 )
其中 c c c 表示基函数的中心。回顾 第 2.1 节
和 第 2.2 节
,在权重参数上设置高斯先验 w ∼ N ( 0 , σ p 2 I ) \mathbf{w} \sim \mathcal{N}(\mathbf{0}, \sigma^2_p \mathbf{I}) w ∼ N ( 0 , σ p 2 I ) ,等价于设置了一个具有如下协方差函数的高斯过程。
k ( x p , x q ) = σ p 2 ∑ c = 1 N ϕ c ( x p ) ϕ c ( x q ) (4.11) k(x_p, x_q) = \sigma^2_p \sum^{N}_{c=1} \phi_c(x_p)\phi_c(x_q) \tag{4.11}
k ( x p , x q ) = σ p 2 c = 1 ∑ N ϕ c ( x p ) ϕ c ( x q ) ( 4.11 )
现在,假设允许无限数量的基函数(按照某个间距以任意位置为中心),并且随着基函数数量的增加,相应地减小权重先验的方差。则我们可以得到极限
lim N → ∞ σ p 2 N ∑ c = 1 N ϕ c ( x p ) ϕ c ( x q ) = σ p 2 ∫ c m i n c m a x ϕ c ( x p ) ϕ c ( x q ) d c (4.12) \lim_{N \rightarrow \infty} \frac{\sigma^2_p}{N} \sum^{N}_{c=1} \phi_c(x_p)\phi_c(x_q) = \sigma^2_p \int^{c_{max}}_{c_{min}} \phi_c(x_p) \phi_c(x_q) dc \tag{4.12}
N → ∞ lim N σ p 2 c = 1 ∑ N ϕ c ( x p ) ϕ c ( x q ) = σ p 2 ∫ c min c ma x ϕ c ( x p ) ϕ c ( x q ) d c ( 4.12 )
代入 式 (4.10)
的高斯形基函数并且让积分的极限趋于无穷大,有:
k ( x p , x q ) = σ p 2 ∫ − ∞ ∞ exp ( − ( x p − c ) 2 2 ℓ 2 ) exp ( − ( x q − c ) 2 2 ℓ 2 ) d c = π ℓ σ p 2 exp ( − ( x p − x q ) 2 2 ( 2 ℓ ) 2 ) (4.13) k(x_p, x_q) = \sigma^2_p \int^{\infty}_{−\infty} \exp(−\frac{(x_p − c)^2}{2 \ell^2}) \exp(− \frac{(x_q − c)^2 }{2 \ell^2}) dc = \sqrt{π} \ell \sigma^2_p \exp(− \frac{(x_p − x_q)^2}{2 (\sqrt{2} \ell)^2}) \tag{4.13}
k ( x p , x q ) = σ p 2 ∫ − ∞ ∞ exp ( − 2 ℓ 2 ( x p − c ) 2 ) exp ( − 2 ℓ 2 ( x q − c ) 2 ) d c = π ℓ σ p 2 exp ( − 2 ( 2 ℓ ) 2 ( x p − x q ) 2 ) ( 4.13 )
可以看出,这是一个长度尺度为 2 \sqrt{2} 2 的平方指数协方差函数。此推导改编自 MacKay [1998]。将此构造推广到多元 x \mathbf{x} x 也很简单。在 式(4.30)
中也存在类似构造,不过在该式中基函数的中心是从高斯分布中采样得到的;当高斯分布的方差趋于无穷大时,这些构造是等价的。
4.2.1.3 Matern 族函数
(1)函数形式
协方差函数的 Matern 族由下式给出
k M a t e r n ( r ) = 2 1 − ν Γ ( ν ) ( 2 ν r ℓ ) ν K ν ( 2 ν r ℓ ) (4.14) k_{Matern}(r) = \frac{2^{1−ν}}{Γ(ν)} \left(\frac{\sqrt{2ν} r}{\ell} \right)^ν K_ν \left(\frac{\sqrt{2ν} r}{\ell} \right) \tag{4.14}
k M a t er n ( r ) = Γ ( ν ) 2 1 − ν ( ℓ 2 ν r ) ν K ν ( ℓ 2 ν r ) ( 4.14 )
(2)谱密度
具有正参数 ν ν ν 和 ℓ \ell ℓ ,其中 K ν K_ν K ν 是修正贝塞尔函数 [Abramowitz and Stegun, 1965, sec. 9.6]。该协方差函数在不同维度 D D D 上具有不同谱密度
S ( s ) = 2 D π D / 2 Γ ( ν + D / 2 ) ( 2 ν ) ν Γ ( ν ) ℓ 2 ν ( 2 ν ℓ 2 + 4 π 2 s 2 ) − ( ν + D / 2 ) (4.15) S(\mathbf{s}) = \frac{2^D π^{D/2} Γ(ν + D/2)(2ν)^ν }{Γ(ν) \ell^2ν} \left(\frac{2ν}{\ell^2} + 4 π^2s^2 \right)^{−(ν + D/2)} \tag{4.15}
S ( s ) = Γ ( ν ) ℓ 2 ν 2 D π D /2 Γ ( ν + D /2 ) ( 2 ν ) ν ( ℓ 2 2 ν + 4 π 2 s 2 ) − ( ν + D /2 ) ( 4.15 )
(3)函数特性
请注意,选择缩放比例是为了让 ν → ∞ ν \rightarrow \infty ν → ∞ 我们获得平方指数协方差函数 e − r 2 / 2 ℓ 2 e^{−r2/2 \ell^2} e − r 2/2 ℓ 2 ,参见 式(A.25)
。 Stein [1999] 根据 Matern [1960] 的工作将其命名为 Matern 族。对于 Matern 族,当且仅当 ν > k ν > k ν > k 时,过程 f ( x ) f(\mathbf{x}) f ( x ) 是 k k k 次均方可微分的。
当 ν ν ν 是半整数时,Matern 协方差函数变得特别简单:ν = p + 1 / 2 ν = p + 1/2 ν = p + 1/2 ,其中 p p p 是一个非负整数。在这种情况下,协方差函数是指数和 p p p 阶多项式的乘积,通用表达式可以从 [Abramowitz and Stegun, 1965, eq. 10.2.15] 给出:
k ν = p + 1 / 2 ( r ) = exp ( − 2 ν r ℓ ) Γ ( p + 1 ) Γ ( 2 p + 1 ) ∑ i = 0 p ( p + i ) ! i ! ( p − i ) ! ( 8 ν r ℓ ) p − i (4.16) k_{ν=p+1/2}(r) = \exp \left(−\frac{\sqrt{2ν} r}{\ell} \right) \frac{ Γ(p + 1) }{Γ(2p + 1) } \sum^{p}_{i=0} \frac{(p + i)!}{i!(p − i)!} \left(\frac{\sqrt{8ν} r}{\ell} \right)^{p−i} \tag{4.16}
k ν = p + 1/2 ( r ) = exp ( − ℓ 2 ν r ) Γ ( 2 p + 1 ) Γ ( p + 1 ) i = 0 ∑ p i ! ( p − i )! ( p + i )! ( ℓ 8 ν r ) p − i ( 4.16 )
机器学习领域最感兴趣的情况可能是 ν = 3 / 2 ν = 3/2 ν = 3/2 和 ν = 5 / 2 ν = 5/2 ν = 5/2 ,其中
k ν = 3 / 2 ( r ) = ( 1 + 3 r ℓ ) exp ( − 3 r ℓ ) (4.17a) k_{ν=3/2}(r) = \left( 1+ \frac{\sqrt{3} r}{\ell} \right) \exp \left(−\frac{\sqrt{3} r}{\ell} \right) \tag{4.17a}
k ν = 3/2 ( r ) = ( 1 + ℓ 3 r ) exp ( − ℓ 3 r ) ( 4.17a )
k ν = 5 / 2 ( r ) = ( 1 + 5 r ℓ + 5 r 2 3 ℓ 2 ) exp ( − 5 r ℓ ) (4.17b) k_{ν=5/2}(r) = \left( 1+ \frac{\sqrt{5} r}{\ell} + \frac{5r^2}{3 \ell^2} \right) \exp \left(− \frac{\sqrt{5} r}{\ell}\right) \tag{4.17b}
k ν = 5/2 ( r ) = ( 1 + ℓ 5 r + 3 ℓ 2 5 r 2 ) exp ( − ℓ 5 r ) ( 4.17b )
因为对于 ν = 1 / 2 ν = 1/2 ν = 1/2 ,过程变得非常粗糙,而对于 ν ≥ 7 / 2 ν \geq 7/2 ν ≥ 7/2 ,在没有关于高阶导数存在的明确先验知识的情况下,从有限噪声训练样本中很难区分 ν ≥ 7 / 2 ν \geq 7/2 ν ≥ 7/2 的值(或者甚至区分 ν ν ν 的有限值和 ν → ∞ ν \rightarrow \infty ν → ∞ ,在这种情况下是平滑的平方指数)。例如,[Cornford et al., 2002] 中使用了 ν = 5 / 2 ν = 5/2 ν = 5/2 的值。
图 4.1: (a) Matern 族协方差函数,和 (b)从高斯过程中抽取的随机函数,具有式 (4.14) 的 Matern 协方差函数,采用了不同 ν ν ν 值,其中 ℓ = 1 \ell = 1 ℓ = 1 。右侧的示例函数是使用 2000 个等距点的 x x x 轴离散化获得的。
4.2.1.4 Ornstein-Uhlenbeck 过程和指数协方差函数
在 Matern 族中通过设置 ν = 1 / 2 ν = 1/2 ν = 1/2 获得的特例给出了指数协方差函数 k ( r ) = exp ( − r / ℓ ) k(r) = \exp(−r/\ell) k ( r ) = exp ( − r / ℓ ) 。相应的过程是均方连续的,但不是均方可微的。在 D = 1 D = 1 D = 1 时,这对应于 Ornstein-Uhlenbeck (OU) 过程
的协方差函数。 OU 过程 [Uhlenbeck 和 Ornstein,1930 年] 是作为布朗运动的粒子速度的数学模型引入的。更一般地,在 D = 1 D = 1 D = 1 中,对于整数 p p p 设置 ν + 1 / 2 = p ν + 1/2 = p ν + 1/2 = p , 会产生特定形式的连续时间 A R ( p ) AR(p) A R ( p ) 高斯过程;有关详细信息,请参阅 第 B.2.1 节
。 Matern 协方差函数的形式和从中提取的 ν = 1 / 2 ν = 1/2 ν = 1/2 、ν = 2 ν = 2 ν = 2 和 ν → ∞ ν \rightarrow \infty ν → ∞ 的样本如图 4.1
所示。
4.2.1.5 γ 指数协方差函数
略。
4.2.1.6 有理二次协方差函数
略。
4.2.1.7 具有紧支撑的分段多项式协方差函数
一系列具有紧凑支撑的分段多项式函数提供了另一类有趣的协方差函数。
紧凑支撑意味着当点之间的距离超过某个阈值时,点之间的协方差正好变为零 。这意味着协方差矩阵将通过构造变得稀疏,从而可能带来计算优势。设计这些函数的挑战在于如何保证其正定性。 Wendland [2005, ch. 9] 讨论了用于导出此类协方差函数的多种算法。这些函数通常不是对所有输入维度都是正定的,其有效性通常被限制在某个最大维数 D D D 。
下面给出在维数 R D \mathbb{R}^D R D 下,正定协方差函数 k p p D , q ( r ) k_{pp D,q}(r) k pp D , q ( r ) 的一些例子:
k p p D , 0 ( r ) = ( 1 − r ) + j k p p D , 1 ( r ) = ( 1 − r ) + j + 1 ( ( j + 1 ) r + 1 ) k p p D , 2 ( r ) = ( 1 − r ) + j + 2 ( ( j 2 + 4 j + 3 ) r 2 + ( 3 j + 6 ) r + 3 ) / 3 k p p D , 3 ( r ) = ( 1 − r ) + j + 3 ( ( j 3 + 9 j 2 + 23 j + 15 ) r 3 + ( 6 j 2 + 36 j + 45 ) r 2 + ( 15 j + 45 ) r + 15 ) / 15 where j = ⌊ D 2 + q + 1 ⌋ (4.21) \begin{align*}
&k_{ppD,0}(r) = (1 − r)^{j}_+\\
&k_{ppD,1}(r) = (1 − r)^{j+1}_+ ((j + 1)r + 1)\\
&k_{ppD,2}(r) = (1 − r)^{j+2}_+ ((j^2 + 4j + 3)r^2 + (3j + 6)r + 3)/3\\
&k_{pp D,3}(r) = (1 − r)^{j+3}_+ ((j^3 + 9j^2 + 23j + 15)r^3 + (6j^2 + 36j + 45)r^2 + (15j + 45)r + 15)/15\\
& \text{ where } j = \lfloor \frac{D}{2} + q + 1 \rfloor
\end{align*} \tag{4.21}
k pp D , 0 ( r ) = ( 1 − r ) + j k pp D , 1 ( r ) = ( 1 − r ) + j + 1 (( j + 1 ) r + 1 ) k pp D , 2 ( r ) = ( 1 − r ) + j + 2 (( j 2 + 4 j + 3 ) r 2 + ( 3 j + 6 ) r + 3 ) /3 k pp D , 3 ( r ) = ( 1 − r ) + j + 3 (( j 3 + 9 j 2 + 23 j + 15 ) r 3 + ( 6 j 2 + 36 j + 45 ) r 2 + ( 15 j + 45 ) r + 15 ) /15 where j = ⌊ 2 D + q + 1 ⌋ ( 4.21 )
图 4.4
说明了其中三个协方差函数的性质。这些协方差函数是 2 q 2q 2 q 次连续可微的,因此相应的过程是 q q q 次均方可微的。
我们往往感兴趣的是:在获得类似推论同时,能够在多大程度上使用上述紧凑支撑的协方差函数来代替其他协方差函数?
紧凑支撑的优点是能够产生可利用的稀疏 Gram 矩阵 ,例如,当使用迭代方式求解高斯过程回归问题时,参见第 8.3.6 节
。
图 4.4: (a) 紧凑支撑的协方差函数, (b) 从具有 Matern 协方差函数的高斯过程中提取的随机函数,对于不同的 ν ν ν 值,其中 ℓ = 1 \ell = 1 ℓ = 1 。右侧示例函数是使用 2000 2000 2000 个等距点的 x x x 轴离散化获得的。
4.2.1.8 其他重要的平稳协方差函数形式
(1)振荡型协方差函数
上面给出的协方差函数随 r r r 单调衰减并且总是正的。不过,这并不是协方差函数的必要条件。例如 Yaglom [1987] 表明,当 ν ≥ ( D − 2 ) / 2 ν \geq (D − 2)/2 ν ≥ ( D − 2 ) /2 和 α > 0 α > 0 α > 0 时,k ( r ) = c ( α r ) − ν J ν ( α r ) k(r) = c(αr)^{−ν} J_ν(αr) k ( r ) = c ( α r ) − ν J ν ( α r ) 是有效的协方差函数;并且具有阻尼振荡的特征。
(2)协方差函数的低秩(降维)表示
上述各向同性协方差函数的各向异性版本可以通过设置 r 2 ( x , x ′ ) = ( x − x ′ ) ⊤ M ( x − x ′ ) r^2(\mathbf{x,x'}) = (\mathbf{x-x'})^{\top} M (\mathbf{x-x'}) r 2 ( x , x ′ ) = ( x − x ′ ) ⊤ M ( x − x ′ ) 来创建,其中 M M M 是半正定的。如果 M M M 是对角矩阵,这将实现在不同维度上使用不同的长度尺度,有关自动相关性判决的进一步讨论,请参见第 5.1 节
。一般的 M M M 已经被 Matern [1960, p. 19]、Poggio 和 Girosi [1990] 以及 Vivarelli 和 Williams [1999] 等考虑过;在后一项工作中,低秩 M M M 被用于实现从输入空间到低维特征空间的线性降维步骤。
更一般地,可以采用以下形式
M = Λ Λ ⊤ + Ψ M = \Lambda \Lambda^{\top} + \Psi
M = Λ Λ ⊤ + Ψ
其中 Λ \Lambda Λ 是一个 D × k D \times k D × k 矩阵,其列定义了 k k k 个高度相关的方向,Ψ \Psi Ψ 是一个对角矩阵(具有正值元素),捕获轴对齐的相关性,另请参见 图 5.1
。因此 M M M 有一个因子分析形式。对于 k k k 的某些特定选择,这可能在灵活性和所需参数数量之间表现出一种平衡。
(3)周期性协方差函数
平稳核也可以在周期域上定义,并且可以很容易地从 R \mathbb{R} R 上的平稳核构造。给定平稳核 k ( x ) k(x) k ( x ) ,核 k T ( x ) = ∑ m ∈ Z k ( x + m l ) k_{\mathbb{T}}(x) = \sum_{m \in \mathbb{Z}} k(x + ml) k T ( x ) = ∑ m ∈ Z k ( x + m l ) 是周期性,其周期为 l l l ,参见 B.2.2 节
和 Scholkopf 和 Smola [2002, eq. 4.42]。
4.2.2 点积协方差函数
正如我们上面已经提到的,核 k ( x , x ′ ) = σ 0 2 + x ⋅ x ′ k(\mathbf{x,x'}) = \sigma^2_0 + \mathbf{x · x'} k ( x , x ′ ) = σ 0 2 + x ⋅ x ′ 可以从线性回归中获得。如果 σ 0 2 = 0 \sigma^2_0 = 0 σ 0 2 = 0 ,我们称之为 齐次线性核 ,否则是非齐次的。 当然,这可以通过在 x \mathbf{x} x 的分量上使用通用的协方差矩阵 Σ p \Sigma_p Σ p 来推广到 k ( x , x ′ ) = σ 0 2 + x ⊤ Σ p x ′ k(\mathbf{x,x'}) = \sigma^2_0 + \mathbf{x}^{\top} \Sigma_p \mathbf{x'} k ( x , x ′ ) = σ 0 2 + x ⊤ Σ p x ′ ,如 式(2.4)
中所述。
根据 第 4.2.4 节
所述,给定一个协方差函数,其正整数幂也是一个有效的协方差函数,所以,当 p p p 是正整数时,k ( x , x ′ ) = ( σ 0 2 + x ⊤ Σ p x ′ ) p k(\mathbf{x,x'}) = (\sigma^2_0 + \mathbf{x}^{\top} \Sigma_p \mathbf{x'})^p k ( x , x ′ ) = ( σ 0 2 + x ⊤ Σ p x ′ ) p 也是有效的协方差函数。
我们通常对于多项式协方差函数的显式特征空间构造很感兴趣。在此重点考虑齐次多项式的情况,因为非齐次的情况可以简单地通过连接一个常数来扩展 x \mathbf{x} x 获得。我们记:
k ( x , x ′ ) = ( x ⋅ x ′ ) p = ( ∑ d = 1 D x d x d ′ ) p = ( ∑ d 1 = 1 D x d 1 x d 1 ′ ) … ( ∑ d p = 1 D x d p x d p ′ ) = ∑ d 1 = 1 D … ∑ d p = 1 D ( x d 1 … x d p ) ( x d 1 ′ … x d p ′ ) ≜ ϕ ( x ) ⋅ ϕ ( x ′ ) (4.23) k(\mathbf{x,x'}) = (\mathbf{x · x'})^p = \left(\sum^{D}_{d=1} x_d x'_d \right)^p = \left(\sum^{D}_{d_1=1} x_{d_1} x'_{d_1} \right) \ldots \left(\sum^{D}_{d_p=1} x_{d_p} x'_{d_p} \right) = \sum^{D}_{d_1=1} \ldots \sum^{D}_{d_p=1} (x_{d_1} \ldots x_{d_p})(x'_{d_1} \ldots x'_{d_p}) \triangleq \boldsymbol{\phi}(\mathbf{x}) · \boldsymbol{\phi}(\mathbf{x'}) \tag{4.23}
k ( x , x ′ ) = ( x ⋅ x ′ ) p = ( d = 1 ∑ D x d x d ′ ) p = ( d 1 = 1 ∑ D x d 1 x d 1 ′ ) … d p = 1 ∑ D x d p x d p ′ = d 1 = 1 ∑ D … d p = 1 ∑ D ( x d 1 … x d p ) ( x d 1 ′ … x d p ′ ) ≜ ϕ ( x ) ⋅ ϕ ( x ′ ) ( 4.23 )
请注意,这个总和显然包含 D p D^p D p 个项,但实际上它小于这个数,因为单项式 x d 1 … x d p x_{d_1} \dots x_{d_p} x d 1 … x d p 中下标索引的顺序并不重要,例如对于 p = 2 p = 2 p = 2 ,x 1 x 2 x_1 x_2 x 1 x 2 和 x 2 x 1 x_2 x_1 x 2 x 1 是同一单项式。我们可以通过定义一个向量 m \mathbf{m} m 来消除冗余,在 ∑ i = 1 D m i = p \sum^{D}_{i=1} m_i = p ∑ i = 1 D m i = p 的约束下,用其元素 m d m_d m d 指定索引 d d d 在单项式中出现的次数。因此与向量 m \mathbf{m} m 对应的特征 ϕ m ( x ) \phi_{\mathbf{m}}(\mathbf{x}) ϕ m ( x ) 正比于单项式 x 1 m 1 … x D m D x^{m_1}_1 \ldots x^{m_D}_D x 1 m 1 … x D m D 。ϕ m ( x ) \phi_{\mathbf{m}}(\mathbf{x}) ϕ m ( x ) 可以退化为 p ! m 1 ! … m D ! \frac{p!}{m_1! \ldots m_D!} m 1 ! … m D ! p ! (像往常一样定义 0 ! = 1 0!= 1 0 ! = 1 ),给出特征映射:
ϕ m ( x ) = p ! m 1 ! … m D ! x 1 m 1 … x D m D (4.24) \phi_{\mathbf{m}}(\mathbf{x}) = \sqrt{\frac{p!}{m_1! \ldots m_D!}}x^{m1}_1 \ldots x^{mD}_D \tag{4.24}
ϕ m ( x ) = m 1 ! … m D ! p ! x 1 m 1 … x D m D ( 4.24 )
例如,对于 D = 2 D = 2 D = 2 时的 p = 2 p = 2 p = 2 ,我们有 ϕ ( x ) = ( x 1 2 , x 2 2 , 2 x 1 x 2 ) ⊤ \boldsymbol{\phi}(\mathbf{x}) = (x^2_1, x^2_2, \sqrt{2}x_1x_2)^{\top} ϕ ( x ) = ( x 1 2 , x 2 2 , 2 x 1 x 2 ) ⊤ 。点积核有时以 式(4.35)
给出的归一化形式使用。
对于回归问题,多项式核是一个相当奇怪的选择,因为对于 ∣ x ∣ > 1 |\mathbf{x}| > 1 ∣ x ∣ > 1 ,先验方差会随 ∣ x ∣ |\mathbf{x}| ∣ x ∣ 快速增长。不过,此类核已证明在高维分类问题(例如,将 x \mathbf{x} x 设为向量化的二值图像)中是有效的,其中输入数据是二值或灰度,在每个维度上归一化为 [ − 1 , 1 ] [−1, 1] [ − 1 , 1 ] [Scholkopf and Smola,2002 年,7.8 节]。
注:
点积协方差函数 与 再生核希尔伯特空间(RKHS) 以及相关的 核方法 有着密切联系,参见 Shawe-Taylor 的经典书籍《模式分析的核方法》第三章:《核的性质》
4.2.3 非平稳协方差函数
上面我们已经看到了非平稳点积核的例子。不过,还有其他有趣的核采用这种形式。
(1)神经网络的协方差函数
在本节中,我们首先描述属于特定类型神经网络的协方差函数;这种构造归功于 Neal [1996]。
考虑一个神经网络,它接受输入 x \mathbf{x} x ,有一个包含 N H N_H N H 个单元的隐藏层,然后将隐藏单元的输出与偏置 b b b 线性组合以获得 f ( x ) f(\mathbf{x}) f ( x ) 。该映射可以写成
f ( x ) = b + ∑ j = 1 N H v j h ( x ; u j ) (4.25) f(\mathbf{x}) = b + \sum^{N_H}_{j=1} v_j h(\mathbf{x; u_j}) \tag{4.25}
f ( x ) = b + j = 1 ∑ N H v j h ( x ; u j ) ( 4.25 )
其中 v j v_j v j 是隐藏单元到输出的权重,h ( x ; u ) h(\mathbf{x; u}) h ( x ; u ) 是隐藏单元的传递函数(假设其有界),依赖于输入到隐藏单元的权重 u \mathbf{u} u 。 例如,我们可以选择 h ( x ; u ) = tanh ( x ⋅ u ) h(\mathbf{x; u}) = \tanh( \mathbf{x · u}) h ( x ; u ) = tanh ( x ⋅ u ) 。
这种架构很重要,因为 Hornik [1993] 已经表明,对于广泛的传递函数(不包括多项式),当隐藏单元的数量趋于无穷大时,具有单隐藏层的神经网络是一个通用逼近器。令 b b b 和 v v v 分别服从独立的方差为 σ b 2 \sigma^2_b σ b 2 和 σ v 2 \sigma^2_v σ v 2 的零均值高斯,并令每个隐藏单元的权重 u j \mathbf{u}_j u j 独立同分布。用 w \mathbf{w} w 表示所有权重,我们得到(根据 Neal [1996])
E w [ f ( x ) ] = 0 (4.26) \mathbb{E}_{\mathbf{w}}[f(\mathbf{x})] = 0 \tag{4.26}
E w [ f ( x )] = 0 ( 4.26 )
E w [ f ( x ) f ( x ′ ) ] = σ b 2 + ∑ j σ v 2 E u [ h ( x ; u j ) h ( x ′ ; u j ) ] = σ b 2 + N H σ v 2 E u [ h ( x ; u ) h ( x ′ ; u ) ] \begin{align*}
\mathbb{E}_{\mathbf{w}}[f(\mathbf{x}) f(\mathbf{x'})] &= \sigma^2_b+ \sum_j \sigma^2_v \mathbb{E}_{\mathbf{u}} [h(\mathbf{x; u_j})h(\mathbf{x'; u_j})] \tag{4.27} \\
&= \sigma^2_b + N_H \sigma^2_v \mathbb{E}_{\mathbf{u}}[h( \mathbf{x; u} )h(\mathbf{x';u})] \tag{4.28}
\end{align*}
E w [ f ( x ) f ( x ′ )] = σ b 2 + j ∑ σ v 2 E u [ h ( x ; u j ) h ( x ′ ; u j )] = σ b 2 + N H σ v 2 E u [ h ( x ; u ) h ( x ′ ; u )] ( 4.27 ) ( 4.28 )
其中式 (4.28)
成立,因为所有隐藏单元都是同分布的。通过让 σ v 2 \sigma^2_v σ v 2 缩放为 ω 2 / N H ω^2/N_H ω 2 / N H , 式(4.28)
中的最后一项变为 ω 2 E u [ h ( x ; u ) h ( x ′ ; u ) ] ω^2\mathbb{E}_{\mathbf{u}}[h(\mathbf{x; u})h( \mathbf{ x'; u})] ω 2 E u [ h ( x ; u ) h ( x ′ ; u )] 。
式(4.27)
中的求和,是在 N H N_H N H 个独立分布随机变量上的。由于传递函数有界,所以该分布的所有矩都是有界的,可以应用中心极限定理,表明随机过程将收敛到极限为 N H → ∞ N_H \rightarrow \infty N H → ∞ 的高斯过程。
通过计算 E u [ h ( x ; u ) h ( x ′ ; u ) ] \mathbb{E}_{\mathbf{u}}[h(\mathbf{x; u})h(\mathbf{x'; u})] E u [ h ( x ; u ) h ( x ′ ; u )] ,我们可以获得神经网络的协方差函数。例如,如果选择误差函数 h ( z ) = erf ( z ) = 2 / π ∫ 0 z e − t 2 d t h(z) = \text{erf}(z) = 2/\sqrt{π} \int^z_0 e^{−t^2} d t h ( z ) = erf ( z ) = 2/ π ∫ 0 z e − t 2 d t 作为传递函数,让 h ( x ; u ) = erf ( u 0 + ∑ j = 1 D u j x j ) h(\mathbf{x; u}) = \text{erf}(u_0 + \sum^{D}_{j=1} u_j x_j) h ( x ; u ) = erf ( u 0 + ∑ j = 1 D u j x j ) ,同时选择 u ∼ N ( 0 , Σ ) \mathbf{u} \sim \mathcal{N}(0, \Sigma) u ∼ N ( 0 , Σ ) ,则可以得到如下神经网络的协方差函数 [Williams, 1998]
k N N ( x , x ′ ) = 2 π sin − 1 ( 2 x ~ ⊤ Σ x ~ ′ ( 1 + 2 x ~ ⊤ Σ x ~ ) ( 1 + 2 x ~ ′ ⊤ Σ x ~ ′ ) ) (4.29) k_{NN}(\mathbf{x,x'}) = \frac{2}{π} \sin^{−1} \left( \frac{2 \mathbf{\tilde{x}^{\top} \Sigma \tilde{x}'}}{\sqrt{(1 + 2 \tilde{\mathbf{x}}^{\top} \Sigma \tilde{\mathbf{x}})(1 + 2 \tilde{\mathbf{x}}'^{\top} \Sigma \tilde{\mathbf{x}}'}) }\right) \tag{4.29}
k NN ( x , x ′ ) = π 2 sin − 1 ( ( 1 + 2 x ~ ⊤ Σ x ~ ) ( 1 + 2 x ~ ′ ⊤ Σ x ~ ′ ) 2 x ~ ⊤ Σ x ~ ′ ) ( 4.29 )
其中 x ~ = ( 1 , x 1 , … , x d ) ⊤ \tilde{\mathbf{x}} = (1, x_1,\ldots, x_d)^{\top} x ~ = ( 1 , x 1 , … , x d ) ⊤ 是增广输入向量。这是一个真正的 “神经网络” 协方差函数。有人建议 “sigmoid” 核 k ( x , x ′ ) = tanh ( a + b x ⋅ x ′ ) k(\mathbf{x,x'}) = \tanh(a + b \mathbf{x · x'}) k ( x , x ′ ) = tanh ( a + b x ⋅ x ′ ) ,但实际上该核永远不是正定的,因此不是有效的协方差函数,参见,例如 Scholkopf 和 Smola [2002, p. 113]。
图 4.5
显示了神经网络协方差函数和从高斯过程先验中抽取的函数样本。我们设置了 Σ = diag ( σ 0 2 , σ 2 ) \Sigma = \text{diag}(\sigma^2_0, σ^2) Σ = diag ( σ 0 2 , σ 2 ) 。来自具有此协方差函数的高斯过程样本可以被视为函数 erf ( u 0 + u x ) \text{erf}(u_0 +ux) erf ( u 0 + ux ) 的叠加,其中 σ 0 2 \sigma^2_0 σ 0 2 控制 u 0 u_0 u 0 的方差(以及这些函数与原点的偏移量),而 σ 2 σ^2 σ 2 控制 u u u 从而在 x \mathbf{x} x 轴上进行缩放。在 图 4.5(b)
中,我们观察到 σ σ σ 越大的函数样本变化越快。请注意,样本显示了协方差函数的非平稳性,因为对于 + x +x + x 或 − x −x − x 的大值,它们应该趋向于恒定值,与 “sigmoid” 函数叠加的构造保持一致。
图 4.5: (a):σ 0 = 10 σ_0 = 10 σ 0 = 10 、σ = 10 σ = 10 σ = 10 的 k N N ( x , x ′ ) k_{NN}(\mathbf{x, x'}) k NN ( x , x ′ ) 协方差函数图 (b):从神经网络协方差函数中抽取的样本,σ 0 = 2 σ_0 = 2 σ 0 = 2 ,σ σ σ 在图例中显示。使用 500 500 500 个 x x x 轴的离散化等距点获得样本
(2)基于高斯基函数的协方差函数
另一个有趣的构造是设置 h ( x ; u ) = exp ( − ∣ x − u ∣ 2 / 2 σ g 2 ) h(\mathbf{x; u}) = \exp(−|\mathbf{x − u}|^2/2 σ^2_g) h ( x ; u ) = exp ( − ∣ x − u ∣ 2 /2 σ g 2 ) ,其中 σ g σ_g σ g 指定了此高斯基函数的尺度。当 u ∼ N ( 0 , σ u 2 I ) \mathbf{u} \sim \mathcal{N}(\mathbf{0}, σ^2_u \mathbf{I}) u ∼ N ( 0 , σ u 2 I ) 时,我们有:
k G ( x , x ′ ) = 1 ( 2 π σ u 2 ) d / 2 ∫ exp ( − ∣ x − u ∣ 2 2 σ g 2 − ∣ x ′ − u ∣ 2 2 σ g 2 − u ⊤ u 2 σ u 2 ) d u = ( σ e σ u ) d exp ( − x ⊤ x 2 σ m 2 ) exp ( − ∣ x − x ′ ∣ 2 2 σ s 2 ) exp ( − x ′ ⊤ x ′ 2 σ m 2 ) (4.30) \begin{align*}
k_{G}(\mathbf{x,x'}) &= \frac{1}{(2π \sigma^2_u)^{d/2}} \int \exp \left(− \frac{|\mathbf{x − u}|^2}{2 \sigma^2_g} − \frac{ |\mathbf{x' − u}|^2}{2 \sigma^2_g} − \frac{\mathbf{u^{\top} u}}{2 \sigma^2_u} \right) d \mathbf{u} \\
&= ( \frac{σ_e}{σ_u})^d \exp \left( − \frac{\mathbf{x^{\top} x}}{2\sigma^2_m} \right) \exp \left( −\frac{|\mathbf{x-x'}|^2}{2 \sigma^2_s} \right) \exp \left( − \frac{ \mathbf{x'^{\top} x'}}{2 \sigma^2_m } \right)
\end{align*} \tag{4.30}
k G ( x , x ′ ) = ( 2 π σ u 2 ) d /2 1 ∫ exp ( − 2 σ g 2 ∣ x − u ∣ 2 − 2 σ g 2 ∣ x ′ − u ∣ 2 − 2 σ u 2 u ⊤ u ) d u = ( σ u σ e ) d exp ( − 2 σ m 2 x ⊤ x ) exp ( − 2 σ s 2 ∣ x − x ′ ∣ 2 ) exp ( − 2 σ m 2 x ′ ⊤ x ′ ) ( 4.30 )
其中 1 / σ e 2 = 2 / σ g 2 + 1 / σ u 2 1/\sigma^2_e = 2/\sigma^2_g + 1/\sigma^2_u 1/ σ e 2 = 2/ σ g 2 + 1/ σ u 2 、σ s 2 = 2 σ g 2 + σ g 4 / σ u 2 \sigma^2_s = 2\sigma^2_g + \sigma^4_g / \sigma^2_u σ s 2 = 2 σ g 2 + σ g 4 / σ u 2 、 σ m 2 = 2 σ u 2 + σ g 2 \sigma^2_m = 2\sigma^2_u + \sigma^2_g σ m 2 = 2 σ u 2 + σ g 2 。这通常是一个非平稳协方差函数,但如果 σ u 2 → ∞ \sigma^2_u \rightarrow \infty σ u 2 → ∞ (同时适当缩放 ω 2 ω^2 ω 2 ),我们可以恢复平方指数 k G ( x , x ′ ) ∝ exp ( − ∣ x − x ′ ∣ 2 / 4 σ g 2 ) k_{G}(\mathbf{x,x'}) \propto \exp(−|\mathbf{x-x'}|^2/4\sigma^2_g) k G ( x , x ′ ) ∝ exp ( − ∣ x − x ′ ∣ 2 /4 σ g 2 ) 。对于 σ u 2 \sigma^2_u σ u 2 的有限值,k G ( x , x ′ ) k_{G}(\mathbf{x,x'}) k G ( x , x ′ ) 包含由高斯衰减包络函数 exp ( − x ⊤ x / 2 σ m 2 ) exp ( − x ′ ⊤ x ′ / 2 σ m 2 ) \exp(−\mathbf{x^{\top} x}/2\sigma^2_m) \exp(−\mathbf{x'^{\top} x'}/2\sigma^2_m) exp ( − x ⊤ x /2 σ m 2 ) exp ( − x ′ ⊤ x ′ /2 σ m 2 ) 调制的平方指数协方差函数,类似于第 4.2.4 节
中描述的垂直缩放结构。
(3)非线性空间中的平稳协方差函数
引入非平稳性的一种方法是引入输入 x \mathbf{x} x 的任意非线性映射(或扭曲)u ( x ) \mathbf{u}(\mathbf{x}) u ( x ) ,然后在 u \mathbf{u} u 空间中使用平稳协方差函数。请注意,x \mathbf{x} x 和 u \mathbf{u} u 不需要彼此具有相同的维度。 Sampson 和 Guttorp [1992] 采用这种方法,利用高斯过程对不列颠哥伦比亚省西南部的太阳辐射模式进行建模。
MacKay [1998] 给出了这种扭曲构造的另一个有趣示例,其中一维输入变量 x \mathbf{x} x 映射到二维 u ( x ) = ( cos ( x ) , sin ( x ) ) \mathbf{u}(\mathbf{x}) = (\cos(\mathbf{x}), \sin(\mathbf{x})) u ( x ) = ( cos ( x ) , sin ( x )) 以产生 x \mathbf{x} x 的周期性随机函数。如果我们在 u \mathbf{u} u 空间中使用平方指数核,那么
k ( x , x ′ ) = exp ( − 2 sin 2 ( x − x ′ 2 ) ℓ 2 ) (4.31) k(\mathbf{x,x'}) = \exp \left( − \frac{2 \sin^2(\frac{\mathbf{ x−x'}}{2})}{\ell^2} \right) \tag{4.31}
k ( x , x ′ ) = exp ( − ℓ 2 2 sin 2 ( 2 x − x ′ ) ) ( 4.31 )
其中 ( cos ( x ) − cos ( x ′ ) ) 2 + ( sin ( x ) − sin ( x ′ ) ) 2 = 4 sin 2 ( x − x ′ 2 ) (\cos(\mathbf{x}) − \cos(\mathbf{x'}))^2 + (\sin(\mathbf{x}) − \sin(\mathbf{x'}))^2 = 4 \sin^2(\frac{x−x'}{2}) ( cos ( x ) − cos ( x ′ ) ) 2 + ( sin ( x ) − sin ( x ′ ) ) 2 = 4 sin 2 ( 2 x − x ′ ) 。
(4)可变长度尺度的非平稳方案
上面我们已经描述了如何通过不同地缩放不同维度来制作各向异性协方差函数。然而,我们不能随意使这些长度尺度成为 x \mathbf{x} x 的函数,因为这通常不会产生有效的协方差函数。 Gibbs [1997] 导出协方差函数
k ( x , x ′ ) = ∏ d = 1 D ( 2 ℓ d ( x ) ℓ d ( x ′ ) ℓ d 2 ( x ) + ℓ d 2 ( x ′ ) ) 1 / 2 exp ( − ∑ d = 1 D ( x d − x d ′ ) 2 ℓ d 2 ( x ) + ℓ d 2 ( x ′ ) ) (4.32) k(\mathbf{x,x'}) = \prod^{D}_{d=1} \left(\frac{2 \ell_d(\mathbf{x}) \ell_d(\mathbf{x'})}{\ell^2_d(\mathbf{x}) + \ell^2_d(\mathbf{x'})} \right)^{1/2} \exp \left( − \sum^{D}_{d=1} \frac{(x_d − x'_d)^2}{\ell^2_d(\mathbf{x}) + \ell^2_d(\mathbf{x'})} \right) \tag{4.32}
k ( x , x ′ ) = d = 1 ∏ D ( ℓ d 2 ( x ) + ℓ d 2 ( x ′ ) 2 ℓ d ( x ) ℓ d ( x ′ ) ) 1/2 exp ( − d = 1 ∑ D ℓ d 2 ( x ) + ℓ d 2 ( x ′ ) ( x d − x d ′ ) 2 ) ( 4.32 )
其中每个 ℓ i ( x ) \ell_i(\mathbf{x}) ℓ i ( x ) 是 x \mathbf{x} x 的任意正函数。请注意,对于所有 x \mathbf{x} x ,k ( x , x ) = 1 k(\mathbf{x, x}) = 1 k ( x , x ) = 1 。该协方差函数是通过考虑中心为 c j \mathbf{c}_j c j 的 N N N 个高斯基函数的网格和输入维度 d d d 上的相应长度尺度(其随正函数 ℓ d ( c j ) \ell_d(\mathbf{c}_j) ℓ d ( c j ) 变化)而获得的。以 N → ∞ N \rightarrow \infty N → ∞ 为极限,总和变成积分并经过一些代数计算, 得到 式 (4.32)
。
一个可变长度尺度函数的例子和来自对应于 式(4.32)
的先验样本。如 图 4.6
所示。请注意,随着长度尺度变短,样本函数的变化会如人们预期的那样更快。短尺度区域两侧的大尺度区域可能具有很强的相关性。如果通过创建一个长度尺度函数 ℓ ( x ) \ell(\mathbf{x}) ℓ ( x ) 来尝试相反的实验,它在两个较短的区域之间有一个较长的长度尺度区域,那么行为可能并不完全符合预期;在最初过渡到长尺度区域时,协方差在稳定到较慢的变化之前,会由于 式(4.32)
中的预分解而急剧下降。见 Gibbs [1997, sec. 3.10.3]了解更多详情。
图 4.6: (a) 显示了选定的长度尺度函数 ℓ ( x ) \ell(x) ℓ ( x ) 。 (b) 显示了使用吉布斯协方差函数 式(4.32)
之前来自 GP 的三个样本。该图基于 Gibbs [1997] 中的图 3.9。
Paciorek 和 Schervish [2004] 推广了 Gibbs 构造以获得任意各向同性协方差函数的非平稳版本。令 k S k_S k S 是在每个欧几里德空间 R D , D = 1 , 2 , … \mathbb{R}^D, D = 1, 2,\ldots R D , D = 1 , 2 , … 中都有效的平稳、各向同性协方差函数。令 Σ ( x ) \Sigma(\mathbf{x}) Σ ( x ) 为对所有 x \mathbf{x} x 均正定的矩阵值(输出为 D × D D \times D D × D 的矩阵)函数,令 Σ i ≜ Σ ( x i ) \Sigma_i \triangleq \Sigma(\mathbf{x}_i) Σ i ≜ Σ ( x i ) 。 (Gibbs 的 ℓ i ( x ) \ell_i(\mathbf{x}) ℓ i ( x ) 函数集定义了对角矩阵 Σ ( x ) \Sigma(\mathbf{x}) Σ ( x ) )然后定义二次形:
Q i j = ( x i − x j ) ⊤ ( ( Σ i + Σ j ) / 2 ) − 1 ( x i − x j ) (4.33) Q_{ij} = (\mathbf{x_i − x_j})^{\top} ((\Sigma_i + \Sigma_j)/2)^{−1}(\mathbf{x_i − x_j}) \tag{4.33}
Q ij = ( x i − x j ) ⊤ (( Σ i + Σ j ) /2 ) − 1 ( x i − x j ) ( 4.33 )
Paciorek 和 Schervish [2004] 表明
k N S ( x i , x j ) = 2 D / 2 ∣ Σ i ∣ 1 / 4 ∣ Σ j ∣ 1 / 4 ∣ Σ i + Σ j ∣ − 1 / 2 k S ( Q i j ) (4.34) k_{NS}(\mathbf{x}_i,\mathbf{x}_j) = 2^{D/2} |\Sigma_i|^{1/4} |\Sigma_j|^{1/4} |\Sigma_i + \Sigma_j |^{−1/2} k_S(\sqrt{Q_{ij}} ) \tag{4.34}
k NS ( x i , x j ) = 2 D /2 ∣ Σ i ∣ 1/4 ∣ Σ j ∣ 1/4 ∣ Σ i + Σ j ∣ − 1/2 k S ( Q ij ) ( 4.34 )
是有效的非平稳协方差函数。
在第 2 章
中我们描述了特征空间 f ( x ) = ϕ ( x ) ⊤ w f(\mathbf{x}) = \boldsymbol{\phi}(\mathbf{x})^{\top} \mathbf{w} f ( x ) = ϕ ( x ) ⊤ w 中的线性回归模型。 O’Hagan [1978] 建议使 w \mathbf{w} w 成为 x \mathbf{x} x 的函数,以允许不同的 w \mathbf{w} w 值适用于不同的区域。因此,对于某些正定矩阵 W 0 W_0 W 0 ,他在 w \mathbf{w} w 上放置了一个形式为 cov ( w ( x ) , w ( x ′ ) ) = W 0 k w ( x , x ′ ) \operatorname{cov}(\mathbf{w(x), w(x')}) = W_0 k_w(\mathbf{x,x'}) cov ( w ( x ) , w ( x ′ ) ) = W 0 k w ( x , x ′ ) 的先验高斯过程,从而产生了 f ( x ) f(\mathbf{x}) f ( x ) 上的先验协方差 k f ( x , x ′ ) = ϕ ( x ) ⊤ W 0 ϕ ( x ′ ) k w ( x , x ′ ) k_f(\mathbf{x,x'}) = \boldsymbol{\phi}(\mathbf{x})^{\top} W_0 \boldsymbol{\phi}(\mathbf{x'}) k_w(\mathbf{x,x'}) k f ( x , x ′ ) = ϕ ( x ) ⊤ W 0 ϕ ( x ′ ) k w ( x , x ′ ) 。
最后,我们注意到具有协方差函数 k ( x , x ′ ) = min ( x , x ′ ) k(\mathbf{x,x'}) = \min(\mathbf{x,x'}) k ( x , x ′ ) = min ( x , x ′ ) 的维纳过程是一个基础的非平稳过程。参见 B.2.1 节和 Grimmett 和 Stirzaker [1992, ch. 13] 了解更多详情。
表 4.1:几种常用协方差函数的汇总。协方差可以写成 x \mathbf{x} x 和 x ′ \mathbf{x'} x ′ 的函数,或者写成 r = ∣ x − x ′ ∣ r = |\mathbf{x − x'}| r = ∣ x − x ′ ∣ 的函数。标记为 “S” 和 “ND” 的两列分别表示协方差函数是否平稳和非退化。退化协方差函数具有有限秩,有关此问题的更多讨论,请参见第 4.3 节。
4.2.4 从旧核生成新核
在前面的部分中,我们开发了许多协方差函数,其中一些总结在 表 4.1
中。在本节,我们将展示如何组合或修改现有协方差函数来生成新的协方差函数。
(1)两个核之和也是一个核。
证明:考虑随机过程 f ( x ) = f 1 ( x ) + f 2 ( x ) f(\mathbf{x}) = f_1(\mathbf{x}) + f_2(\mathbf{x}) f ( x ) = f 1 ( x ) + f 2 ( x ) ,其中 f 1 ( x ) f_1(\mathbf{x}) f 1 ( x ) 和 f 2 ( x ) f_2(\mathbf{x}) f 2 ( x ) 是独立的。那么 k ( x , x ′ ) = k 1 ( x , x ′ ) + k 2 ( x , x ′ ) k(\mathbf{x,x'}) = k_1(\mathbf{x,x'}) + k_2(\mathbf{x,x'}) k ( x , x ′ ) = k 1 ( x , x ′ ) + k 2 ( x , x ′ ) 。这种结构可以用于(例如)将具有不同长度尺度的核加在一起。
(2)两个核的乘积是一个核。
证明:考虑随机过程 f ( x ) = f 1 ( x ) f 2 ( x ) f(\mathbf{x}) = f_1(\mathbf{x})f_2(\mathbf{x}) f ( x ) = f 1 ( x ) f 2 ( x ) ,其中 f 1 ( x ) f_1(\mathbf{x}) f 1 ( x ) 和 f 2 ( x ) f_2(\mathbf{x}) f 2 ( x ) 是独立的。那么 k ( x , x ′ ) = k 1 ( x , x ′ ) k 2 ( x , x ′ ) k(\mathbf{x,x'}) = k_1(\mathbf{x,x'})k_2(\mathbf{x,x'}) k ( x , x ′ ) = k 1 ( x , x ′ ) k 2 ( x , x ′ ) 。这个论证的简单扩展意味着 k p ( x , x ′ ) k^p(\mathbf{x,x'}) k p ( x , x ′ ) 是 p ∈ N p \in \mathbb{N} p ∈ N 的有效协方差函数。
设 a ( x ) a(\mathbf{x}) a ( x ) 为给定的确定性函数,并考虑 g ( x ) = a ( x ) f ( x ) g(\mathbf{x}) = a(\mathbf{x})f(\mathbf{x}) g ( x ) = a ( x ) f ( x ) ,其中 f ( x ) f(\mathbf{x}) f ( x ) 是随机过程。那么 cov ( g ( x ) , g ( x ′ ) ) = a ( x ) k ( x , x ′ ) a ( x ′ ) \operatorname{cov}(g(\mathbf{x}), g(\mathbf{x'})) = a(\mathbf{x})k(\mathbf{x,x'})a(\mathbf{x'}) cov ( g ( x ) , g ( x ′ )) = a ( x ) k ( x , x ′ ) a ( x ′ ) 。这样的构造可用于通过选择 a ( x ) = k − 1 / 2 ( x , x ) a(\mathbf{x}) = k^{−1/2}(\mathbf{x, x}) a ( x ) = k − 1/2 ( x , x ) (假设 k ( x , x ) > 0 ∀ x k(\mathbf{x, x}) > 0 \forall \mathbf{x} k ( x , x ) > 0∀ x )来归一化核,因此:
k ~ ( x , x ′ ) = k ( x , x ′ ) k ( x , x ) k ( x ′ , x ′ ) (4.35) \tilde{k}(\mathbf{x,x'}) = \frac{k(\mathbf{x,x'})}{\sqrt{k(\mathbf{x, x})} \sqrt{k(\mathbf{x', x'})}} \tag{4.35}
k ~ ( x , x ′ ) = k ( x , x ) k ( x ′ , x ′ ) k ( x , x ′ ) ( 4.35 )
这确保了对于所有 x \mathbf{x} x ,有 k ( x , x ) = 1 k(\mathbf{x, x}) = 1 k ( x , x ) = 1 。
我们也可以通过卷积(或模糊)得到一个新过程。考虑任意平稳核 h ( x , z ) h(\mathbf{x, z}) h ( x , z ) 和映射 g ( x ) = ∫ h ( x , z ) f ( z ) d z g(\mathbf{x}) = \int h(\mathbf{x, z})f(\mathbf{z}) d \mathbf{z} g ( x ) = ∫ h ( x , z ) f ( z ) d z 。那么卷积显然是 cov ( g ( x ) , g ( x ′ ) ) = ∫ h ( x , z ) k ( z , z ′ ) h ( x ′ , z ′ ) d z d z ′ \operatorname{cov}(g(\mathbf{x}), g(\mathbf{x'})) = \int h(\mathbf{x, z})k(\mathbf{z, z'})h(\mathbf{x', z'}) d \mathbf{z} d \mathbf{z'} cov ( g ( x ) , g ( x ′ )) = ∫ h ( x , z ) k ( z , z ′ ) h ( x ′ , z ′ ) d z d z ′ 。
如果 k ( x 1 , x ′ 1 ) k(\mathbf{x}_1, \mathbf{x'}_1) k ( x 1 , x ′ 1 ) 和 k ( x 2 , x ′ 2 ) k(\mathbf{x}_2, \mathbf{x'}_2) k ( x 2 , x ′ 2 ) 是不同空间 X 1 \mathcal{X}_1 X 1 和 X 2 \mathcal{X}_2 X 2 上的协方差函数,则通过求和构造与求积构造,有 直和 k ( x , x ′ ) = k 1 ( x 1 , x ′ 1 ) + k 2 ( x 2 , x ′ 2 ) k(\mathbf{x,x'}) = k_1(\mathbf{x}_1, \mathbf{x'}_1) + k_2(\mathbf{x}_2, \mathbf{x'}_2) k ( x , x ′ ) = k 1 ( x 1 , x ′ 1 ) + k 2 ( x 2 , x ′ 2 ) 和 张量积 k ( x , x ′ ) = k 1 ( x 1 , x ′ 1 ) k 2 ( x 2 , x ′ 2 ) k(\mathbf{x,x'}) = k_1(\mathbf{x}_1, \mathbf{x'}_1) k_2(\mathbf{x}_2, \mathbf{x'}_2) k ( x , x ′ ) = k 1 ( x 1 , x ′ 1 ) k 2 ( x 2 , x ′ 2 ) 也是协方差函数(定义在乘积空间 X 1 × X 2 \mathcal{X}_1 \times \mathcal{X}_2 X 1 × X 2 上)。
可以进一步推广 直和 构造。考虑一个函数 f ( x ) f(\mathbf{x}) f ( x ) ,其中 x \mathbf{x} x 是 D D D 维的。加性模型 [Hastie and Tibshirani, 1990] 的形式为 f ( x ) = c + ∑ i = 1 D f i ( x i ) f(\mathbf{x}) = c + \sum^{D}_{i=1} f_i(x_i) f ( x ) = c + ∑ i = 1 D f i ( x i ) ,即单变量函数的线性组合。如果将单个 f i f_i f i 视为独立的随机过程,则 f f f 的协方差函数将具有直和的形式。如果我们现在承认两个变量的相互作用,那么 f ( x ) = c + ∑ i = 1 D f i ( x i ) + ∑ i j , j < i f i j ( x i , x j ) f(\mathbf{x}) = c + \sum^{D}_{i=1} f_i(x_i) + \sum_{ij,j < i} f_{ij}(x_i, x_j) f ( x ) = c + ∑ i = 1 D f i ( x i ) + ∑ ij , j < i f ij ( x i , x j ) 并且各种 f i f_i f i 和 f i j f_{ij} f ij 是独立的随机过程,那么协方差函数的形式为 k ( x , x ′ ) = ∑ i = 1 D k i ( x i , x i ′ ) + ∑ i = 2 D ∑ j = 1 i − 1 k i j ( x i , x j ; x i ′ , x j ′ ) k(\mathbf{x,x'}) = \sum^{D}_{i=1} k_i(x_i, x'_i) + \sum^{D}_{i=2} \sum^{i−1}_{j=1} k_{ij} (x_i, x_j ; x'_i , x'_j) k ( x , x ′ ) = ∑ i = 1 D k i ( x i , x i ′ ) + ∑ i = 2 D ∑ j = 1 i − 1 k ij ( x i , x j ; x i ′ , x j ′ ) 。事实上,这个过程可以进一步扩展以提供功能 ANOVA 的分解,范围从简单的加法模型到所有 D D D 输入变量的完全交互。 (求和也可以在某个阶段被截断。)Wahba [1990, ch. 10] 和 Stitson 等 [1999] 建议对具有交互作用的核使用张量积,以便在上面的示例中 k i j ( x i , x j ; x ′ i , x ′ j ) k_{ij}(x_i, x_j; \mathbf{x'}_i, \mathbf{x'}_j) k ij ( x i , x j ; x ′ i , x ′ j ) 的形式为 k i ( x i ; x ′ i ) k j ( x j ; x ′ j ) k_i(x_i; \mathbf{x'}_i) k_j(x_j; \mathbf{x'}_j) k i ( x i ; x ′ i ) k j ( x j ; x ′ j ) 。请注意,如果 D D D 很大,那么大量的成对(或高阶)项可能会有问题; Plate [1999] 研究了使用加性高斯过程模型和允许完全交互的一般协方差函数的组合。
4.3 核的特征函数分析
本节首先定义特征值和特征函数,并讨论 Mercer 定理,在特定条件下,该定理允许我们根据特征值和特征函数来表示核。
4.3.1 节
给出了平方指数核在高斯测度下特征值问题的解析形式解。
4.3.2 节
讨论了在精确解未知的情况下,如何实现近似特征函数的数值计算。
如 第 2 章
所述,高斯过程回归可以被视为含有无限个基函数的贝叶斯线性回归。其中一种可能的基函数集合是 协方差函数的特征函数 。
4.3.1 核的特征函数
(1)核的特征函数与特征值
我们称一个服从如下积分式的函数 ϕ ( ⋅ ) \phi(·) ϕ ( ⋅ ) 为核 k k k 关于测度 μ μ μ 的特征函数,λ λ λ 是其对应的特征值。
∫ k ( x , x ′ ) ⏟ K e r n e l F u n c t i o n ϕ ( x ) ⏟ E i g e n f u n c t i o n d μ ( x ) ⏟ M e a s u r e = λ ⏟ E i g e n V a l u e ϕ ( x ′ ) (4.36) \int \underbrace{k(\mathbf{x,x'})}_{KernelFunction} \underbrace{\phi(\mathbf{x})}_{Eigenfunction} d \underbrace{μ(\mathbf{x})}_{Measure} = \underbrace{λ}_{EigenValue} \phi(\mathbf{x'}) \tag{4.36}
∫ Ker n e lF u n c t i o n k ( x , x ′ ) E i g e n f u n c t i o n ϕ ( x ) d M e a s u re μ ( x ) = E i g e nVa l u e λ ϕ ( x ′ ) ( 4.36 )
我们特别感兴趣的测度主要有两种:
一是在 R D \mathbb{R}^D R D 的紧凑子集 C \mathcal{C} C 上的 Lebesgue 测度;
二是能够将 d μ ( x ) d μ(\mathbf{x}) d μ ( x ) 改写成 p ( x ) d x p(\mathbf{x}) d \mathbf{x} p ( x ) d x 的密度函数 p ( x ) p(\mathbf{x}) p ( x ) 。
勒贝格测度 :在测度论中,勒贝格测度(Lebesgue measure)是欧几里得空间上的标准测度。对维数为 1,2,3 的情况,勒贝格测度就是通常的长度、面积、体积。它广泛应用于实分析,特别是用于定义勒贝格积分。可以赋予勒贝格测度的集合称为勒贝格可测集;勒贝格可测集 A A A 的测度记作 λ ( A ) λ (A) λ ( A ) 。一般来说,我们允许一个集合的勒贝格测度为 ∞ \infty ∞ ,但是即使如此,在假设选择公理成立时,R n \mathbb{R}^n R n 仍有勒贝格不可测的子集。
概率测度 :概率测度是概率空间中定义在一个事件集合上的、满足测度性质(例如可列可加性)的实值函数。概率测度与一般意义上的测度(包括类似面积或体积等概念)的区别在于,概率测度之于整个概率空间的值必须等于 1。 从直觉上来看,概率测度的可加性意味着两个不相交事件的并集的概率测度值,应该等于两个事件各自概率测度值之和,例如 “掷骰子得到 1 或 2” 这一事件的测度值应等于 “掷骰子得到 1” 的测度值与 “掷骰子得到 2” 的测度值之和。
通常特征函数可以有无限多个,我们将其标记为 ϕ 1 ( x ) , ϕ 2 ( x ) , … \phi_1(\mathbf{x}), \phi_2(\mathbf{x}),\ldots ϕ 1 ( x ) , ϕ 2 ( x ) , … ,并假设按照特征值从大到小( λ 1 ≥ λ 2 ≥ … λ_1 \geq λ_2 \geq \ldots λ 1 ≥ λ 2 ≥ … )排序。特征函数之间关于测度 μ μ μ 是正交的,并且可以进行归一化,使得 ∫ ϕ i ( x ) ϕ j ( x ) d μ ( x ) = δ i j \int \phi_i(\mathbf{x})\phi_j(\mathbf{x}) d μ(\mathbf{x}) = δ_{ij} ∫ ϕ i ( x ) ϕ j ( x ) d μ ( x ) = δ ij 其中 δ i j δ_{ij} δ ij 是 Kronecker delta。
(2)Mercer 定理
Mercer 定理(参见 Konig,1986)允许我们用特征值和特征函数来表示核函数,或者反之,将一个核函数表示成特征值核特征函数的线性组合。
【定理 4.2(Mercer 定理)】 。设 ( X , μ ) (\mathcal{X},\mu) ( X , μ ) 是一个有限测度空间,k ∈ L ∞ ( X 2 , μ 2 ) k \in L_{\infty}(\mathcal{X}^2, μ^2) k ∈ L ∞ ( X 2 , μ 2 ) 是一个核,使得 T k : L 2 ( X , μ ) → L 2 ( X , μ ) T_k : L_2(\mathcal{X},\mu) \rightarrow L_2(\mathcal{X},\mu) T k : L 2 ( X , μ ) → L 2 ( X , μ ) 是正定的,见 式(4.2)
。令 ϕ i ∈ L 2 ( X , μ ) \phi_i \in L_2(\mathcal{X},\mu) ϕ i ∈ L 2 ( X , μ ) 为 T k T_k T k 的归一化特征函数(对应于特征值 λ i > 0 λ_i > 0 λ i > 0 )。则:
(1)特征值 { λ i } i = 1 ∞ \{λ_i\}^{\infty}_{i=1} { λ i } i = 1 ∞ 是绝对可求和的;
(2)如下核函数形式
k ( x , x ′ ) = ∑ i = 1 ∞ λ i ϕ i ( x ) ϕ i ∗ ( x ′ ) (4.37) k(\mathbf{x,x'}) = \sum^{\infty }_{i=1} λ_i \phi_i(\mathbf{x}) \phi^*_i (\mathbf{x'}) \tag{4.37}
k ( x , x ′ ) = i = 1 ∑ ∞ λ i ϕ i ( x ) ϕ i ∗ ( x ′ ) ( 4.37 )
关于测度 μ 2 μ^2 μ 2 处处都成立,并且序列关于测度 μ 2 μ^2 μ 2 处处绝对和一致收敛。
上述分解是 Hermitian 矩阵对角化的无限维模拟。请注意,式中的求和可能终止于某个 N ∈ N N \in \mathbb{N} N ∈ N (即超出 N N N 时的特征值为零),也可能是无限的。
(3)退化核
我们有以下定义 [Press et al., 1992, p. [794]
【定义 4.1】 退化核(Degenerate Kernel)只有有限数量的非零特征值。
退化核具有有限的秩 。如果核不是退化的,则称其为非退化的(Nondegenerate)。例如,特征空间中的一个 N N N 维的线性回归模型(参见 式(2.10)
)可以产生具有最多 N N N 个非零特征值的退化核。 (如果测度仅对 x \mathbf{x} x 空间中的 n n n 个有限点施加权重,那么特征分解就是 n × n n \times n n × n 矩阵的简单特征分解,即便核是非退化的。)
上述 Mercer 定理涉及有限测度 μ μ μ 。如果测度 μ μ μ 采用 Lebesgue 测度,并考虑平稳协方差函数,那么直接从 式 (4.5)
的 Bochner 定理可以得到:
k ( x − x ′ ) = ∫ R D e 2 π i s ⋅ ( x − x ′ ) d μ ( s ) = ∫ R D e 2 π i s ⋅ x ( e 2 π i s ⋅ x ′ ) ∗ d μ ( s ) (4.38) k(\mathbf{x-x'}) = \int_{\mathbb{R}^D} e^{2πi \mathbf{s·(x−x')}} d μ(\mathbf{s}) = \int_{\mathbb{R}^D} e^{2πi \mathbf{s·x}} \left( e^{2πi \mathbf{s·x'}} \right)^* d μ(\mathbf{s}) \tag{4.38}
k ( x − x ′ ) = ∫ R D e 2 πi s ⋅ ( x − x ′ ) d μ ( s ) = ∫ R D e 2 πi s ⋅ x ( e 2 πi s ⋅ x ′ ) ∗ d μ ( s ) ( 4.38 )
也就是说,复指数函数 e 2 π i s ⋅ x e^{2πi \mathbf{s·x}} e 2 πi s ⋅ x 可以被视为平稳核关于 Lebesgue 测度的特征函数。注意其与 式(4.37)
的相似性,除了求和被积分代替。
(4)特征值的渐近性质
特征值的衰减率提供了有关核平滑度的重要信息 。例如 Ritter 等 [1995] 表明,在一维空间中,如果 μ μ μ 在 [ 0 , 1 ] [0, 1] [ 0 , 1 ] 上均匀分布,则 r r r 次均方可微的高斯过程具有渐近的特征值 λ i ∝ i − ( 2 r + 2 ) λ_i \propto i^{−(2r+2)} λ i ∝ i − ( 2 r + 2 ) 。这是有道理的,因为 “更粗糙” 的高斯过程在高频下具有更大的功率,因此它们的特征值谱衰减得更慢。同样的现象可以从 式(4.15)
中给出的 Matern 族的功率谱中解读出来。
Hawkins [1989] 给出了 [ 0 , 1 ] [0, 1] [ 0 , 1 ] 上 Ornstein-Uhlenbeck 过程的精确特征值谱。Widom [1963; 1964] 考虑到密度 d μ ( x ) = p ( x ) d x d μ(\mathbf{x}) = p(\mathbf{x})d \mathbf{x} d μ ( x ) = p ( x ) d x 的影响,对平稳核的特征值进行渐近分析; Bach 和 Jordan [2002,表 3] 使用这些结果来显示不同 p ( x ) p(\mathbf{x}) p ( x ) 对平方指数核的影响。
下一节将给出高斯密度下平方指数核的精确特征分析。
4.3.2 一个解析的案例
考虑 p ( x ) p(x) p ( x ) 是高斯分布且具有平方指数核 k ( x , x ′ ) = exp ( − ( x − x ′ ) 2 / 2 ℓ 2 ) k(x,x') = \exp(−(x−x')^2/2\ell^2) k ( x , x ′ ) = exp ( − ( x − x ′ ) 2 /2 ℓ 2 ) 的情况,Zhu 等 [1998 年,第 4 节] 给出其特征值和特征函数的解析结果。设 p ( x ) = N ( x ∣ 0 , σ 2 ) p(x) = \mathcal{N}(x|0, σ^2) p ( x ) = N ( x ∣0 , σ 2 ) ,特征值 λ k λ_k λ k 和特征函数 ϕ k \phi_k ϕ k 可以由下式给出(为方便起见,令 k = 0 , 1 , … k = 0, 1,\ldots k = 0 , 1 , … ):
λ k = 2 a A B k (4.39) \lambda_k = \sqrt{\frac{2a}{A}} B^k \tag{4.39}
λ k = A 2 a B k ( 4.39 )
ϕ k ( x ) = exp ( − ( c − a ) x 2 ) H k ( 2 c x ) (4.40) \phi_k(x) = \exp(− (c − a)x^2) H_k(\sqrt{2c} x) \tag{4.40}
ϕ k ( x ) = exp ( − ( c − a ) x 2 ) H k ( 2 c x ) ( 4.40 )
其中 H k ( x ) = ( − 1 ) k exp ( x 2 ) d k d x k exp ( − x 2 ) H_k(x) = (−1)^k \exp(x^2) \frac{d^k}{dx^k} \exp(−x^2) H k ( x ) = ( − 1 ) k exp ( x 2 ) d x k d k exp ( − x 2 ) 是第 k k k 阶 Hermite 多项式(参见 Gradshteyn 和 Ryzhik [1980, sec. 8.95]),a − 1 = 4 σ 2 a^{−1} = 4σ^2 a − 1 = 4 σ 2 , b − 1 = 2 ℓ 2 b^{-1} = 2 \ell^2 b − 1 = 2 ℓ 2 ,并且:
c = a 2 + 2 a b , A = a + b + c , B = b / A (4.41) c=\sqrt{a^2+2ab},\qquad A=a+b+c,\quad B=b/A \tag{4.41}
c = a 2 + 2 ab , A = a + b + c , B = b / A ( 4.41 )
图 4.7
显示了 a = 1 a = 1 a = 1 和 b = 3 b = 3 b = 3 的前三个特征函数图。
图 4.7:关于高斯密度的平方指数核的前 3 3 3 个特征函数。 k = 0 , 1 , 2 k = 0, 1, 2 k = 0 , 1 , 2 的值等于函数的过零次数。虚线与密度 p ( x ) p(x) p ( x ) 成正比。
当核和高斯密度是单变量表达式的乘积时,上述特征值和特征函数的结果很容易被推广到多元情况,因为特征函数和特征值也是乘积。对于 a a a 和 b b b 在所有 D D D 个维度上都相等的情况,特征值 ( 2 a A ) D / 2 B k (\frac{2a}{A})^{D/2} B^k ( A 2 a ) D /2 B k 的退化为( k + D − 1 D − 1 ) \binom{k+D−1}{D−1} ( D − 1 k + D − 1 ) ,即 O ( k D − 1 ) \mathcal{O}(k^{D−1}) O ( k D − 1 ) 。由于 ∑ j = 0 k ( j + D − 1 D − 1 ) = ( k + D D ) \sum^{k}_{j=0} \binom{j+D−1}{D−1} = \binom{k+D}{D} ∑ j = 0 k ( D − 1 j + D − 1 ) = ( D k + D ) ,我们看到第 ( k + D D ) \binom{k+D}{D} ( D k + D ) 个特征值的值由 ( 2 a A ) D / 2 B k (\frac{2a}{A})^{D/2} B^k ( A 2 a ) D /2 B k 给出,这可以用于确定谱的衰减率。
4.3.3 特征值与特征函数的数值逼近
(1)特征值的数值逼近
近似 式(4.36)
中特征函数和特征值的标准数值方法,是使用一个数值例程来近似积分(例如参见 Baker [1977, ch. 3])。例如让 式(4.36)
中的 d μ ( x ) = p ( x ) d x d μ(\mathbf{x}) = p(\mathbf{x})d \mathbf{x} d μ ( x ) = p ( x ) d x 。 则此时可以使用近似
λ i ϕ i ( x ′ ) = ∫ k ( x , x ′ ) p ( x ) ϕ i ( x ) d x ≃ 1 n ∑ l = 1 n k ( x l , x ′ ) ϕ i ( x l ) (4.42) λ_i \phi_i(\mathbf{x'}) = \int k(\mathbf{x,x'}) p(\mathbf{x}) \phi_i(\mathbf{x}) d \mathbf{x} \simeq \frac{1}{n} \sum^{n}_{l=1} k(\mathbf{x}_l, \mathbf{x'}) \phi_i(\mathbf{x}_l) \tag{4.42}
λ i ϕ i ( x ′ ) = ∫ k ( x , x ′ ) p ( x ) ϕ i ( x ) d x ≃ n 1 l = 1 ∑ n k ( x l , x ′ ) ϕ i ( x l ) ( 4.42 )
其中 x l \mathbf{x}_l x l 是来自 p ( x ) p(\mathbf{x}) p ( x ) 的样本。对于 l = 1 , … , n l = 1,\ldots, n l = 1 , … , n ,将 x ′ = x l \mathbf{x' = x}_l x ′ = x l 代入 式(4.42)
,得到矩阵特征问题:
K u i = λ i m a t u i (4.43) K \mathbf{u}_i = λ^{mat}_i \mathbf{u}_i \tag{4.43}
K u i = λ i ma t u i ( 4.43 )
其中 K K K 是元素为 K i j = k ( x i , x j ) K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j) K ij = k ( x i , x j ) 的 n × n n \times n n × n Gram 矩阵,λ i m a t λ^{mat}_i λ i ma t 是矩阵的第 i i i 个特征值,u i \mathbf{u}_i u i 是对应的特征向量(归一化,u i ⊤ u i = 1 \mathbf{u}^{\top}_i \mathbf{u}_i = 1 u i ⊤ u i = 1 )。我们有 ϕ i ( x j ) ∼ n ( u i ) j \phi_i(\mathbf{x}_j) \sim \sqrt{n}(\mathbf{u}_i)_j ϕ i ( x j ) ∼ n ( u i ) j ,其中 n \sqrt{n} n 因子来自特征向量和特征函数的不同归一化。因此 1 n λ i m a t \frac{1}{n} \lambda^{mat}_i n 1 λ i ma t 是 λ i λ_i λ i 的显著估计( i = 1 , … , n i = 1,\ldots , n i = 1 , … , n )。对于固定的 n n n ,人们会期望较大的特征值比较小的特征值估计地更好。
特征值问题的数值解法表明:对于固定的 i i i ,1 n λ i m a t \frac{1}{n} \lambda^{mat}_i n 1 λ i ma t 将在 n → ∞ n \rightarrow \infty n → ∞ 的极限下收敛到 λ i λ_i λ i [Baker,1977,定理 3.4]。也可以进一步研究收敛性;例如,在特征空间中使用主成分分析 (PCA) 的性质很容易证明,对于任何 l , 1 ≤ l ≤ n l,1 \leq l \leq n l , 1 ≤ l ≤ n ,E n [ 1 n ∑ i = 1 l λ i m a t ] ≥ ∑ i = 1 l λ i \mathbb{E}_n[\frac{1}{n} \sum^{l}_{i=1} \lambda^{mat}_i ] \geq \sum^{l}_{i=1} λ_i E n [ n 1 ∑ i = 1 l λ i ma t ] ≥ ∑ i = 1 l λ i 和 E n [ 1 n ∑ i = l + 1 n λ i m a t ] ≤ ∑ i = l + 1 N λ i \mathbb{E}_n[\frac{1}{n} \sum^{n}_{i=l+1} \lambda^{mat}_i] \leq \sum^{N}_{i=l+1} λ_i E n [ n 1 ∑ i = l + 1 n λ i ma t ] ≤ ∑ i = l + 1 N λ i ,其中 E n \mathbb{E}_n E n 表示对从 p ( x ) p(\mathbf{x}) p ( x ) 中抽取的大小为 n n n 的样本的期望。有关详细信息,请参阅 Shawe-Taylor 和 Williams [2003]。
(2)特征函数的数值逼近
用于逼近第 i i i 个特征函数的 Nystrom 方法(参见 Baker [1977] 和 Press 等 [1992,第 18.1 节])由下式给出:
ϕ i ( x ′ ) ≃ n λ i m a t k ( x ′ ) ⊤ u i (4.44) \phi_i(\mathbf{x'}) \simeq \frac{\sqrt{n}}{\lambda^{mat}_i} \mathbf{k}(\mathbf{x'})^{\top} \mathbf{u}_i \tag{4.44}
ϕ i ( x ′ ) ≃ λ i ma t n k ( x ′ ) ⊤ u i ( 4.44 )
其中 k ( x ′ ) ⊤ = ( k ( x 1 , x ′ ) , … , k ( x n , x ′ ) ) \mathbf{k}(\mathbf{x'})^{\top} = (k(\mathbf{x_1, x'}), \ldots , k(\mathbf{x_n, x'})) k ( x ′ ) ⊤ = ( k ( x 1 , x ′ ) , … , k ( x n , x ′ )) ,这是从式(4.42)
的两边除以 λ i λ_i λ i 获得的。 式(4.44)
将近似 ϕ i ( x j ) ≃ n ( u i ) j \phi_i(\mathbf{x}_j) \simeq \sqrt{n}(\mathbf{u}_i)_j ϕ i ( x j ) ≃ n ( u i ) j 从有限的样本点 x 1 , … , x n \mathbf{x_1,\ldots, x_n} x 1 , … , x n 扩展到了所有 x \mathbf{x} x 。
Scholkopf 等 [1998] 的核 PCA 方法和上面讨论的特征函数展开之间存在有趣的关系。特征函数展开具有(至少可能)无限数量的非零特征值。相反,核 PCA 算法对 n × n n \times n n × n 矩阵 K K K 进行运算并产生 n n n 个特征值和特征向量。式 (4.42)
阐明了两者之间的关系。但请注意 式 (4.44)
与 Scholkopf 等 [1998 年,式 4.1] 相同,描述了新点 x ′ \mathbf{x}' x ′ 到核 PCA 特征空间中第 i i i 个特征向量的投影。
4.4 非向量输入的核
到目前为止,我们均假设输入 x \mathbf{x} x 是一个用于测量多个属性值的向量。然而,对于某些学习问题,输入并不是向量,而是一些结构化的对象(如字符串、树、图等)。举几个例子:
我们可能有一个生物学问题,需要对蛋白质(表示为氨基酸的符号串)进行分类。
我们的输入可能是来自语言分析的解析树。
我们可能希望将化合物表示为带标签的图,顶点表示原子,边表示键。
为了使用判别式方法,我们需要从输入对象中提取一些特征并使用这些特征构建预测器。(对于分类问题,还存在另外一种生成式方法,可以基于对象构建类条件模型)。下面我们将描述两种用于特征提取问题的方法,以及从中有效计算核的方法:
在 第 4.4.1 节
中,我们介绍了字符串核
在 第 4.4.2 节
中,我们描述了 Fisher 核。当然,还存在为字符串构建核的其他建议,例如 Watkins [2000] 描述了使用承兑隐马尔可夫模型。
4.4.1 字符串核
我们首先为字符串定义一些符号。设 A \mathcal{A} A 是一个有限的字符字母表。字符串 x x x 和 y y y 的串联写为 x y xy x y 和 ∣ x ∣ |x| ∣ x ∣ 表示字符串 x x x 的长度。如果某些(可能为空的)u u u 、s s s 和 v v v 能够编写为 x = u s v x = usv x = u s v ,则字符串 s s s 是 x x x 的子字符串。
令 ϕ s ( x ) \phi_s(x) ϕ s ( x ) 表示子字符串 s s s 在字符串 x x x 中出现的次数。然后我们将两个字符串 x x x 和 x ′ x' x ′ 之间的核定义为
k ( x , x ′ ) = ∑ s ∈ A ∗ w s ϕ s ( x ) ϕ s ( x ′ ) (4.45) k(x,x') = \sum_{s \in \mathcal{A}^∗} w_s \phi_s(x) \phi_s(x') \tag{4.45}
k ( x , x ′ ) = s ∈ A ∗ ∑ w s ϕ s ( x ) ϕ s ( x ′ ) ( 4.45 )
其中 w s w_s w s 是子串 s s s 的非负权重。例如,我们可以设置 w s = λ ∣ s ∣ w_s = λ^{|s|} w s = λ ∣ s ∣ ,其中 0 < λ < 1 0 < λ < 1 0 < λ < 1 ,这样较短的子串比较长的子串获得更多的权重。
定义 4.45 中包含许多有趣的特例:
对于 ∣ s ∣ > 1 |s| > 1 ∣ s ∣ > 1 ,设置 w s = 0 w_s = 0 w s = 0 给出 “字符-袋” 核。这将字符串 x x x 的特征向量作为 A \mathcal{A} A 中每个字符在 x x x 中出现的次数。
在文本分析中,我们可能希望考虑单词出现的频率。如果我们要求 s s s 以空格为边界,则获得 “词袋” 表示。虽然这是一个非常简单的文本模型(忽略词序),但它对于文档分类和检索任务非常有效,参见例如 Hand 等 [2001 年, 14.3 节]。可以为不同的词设置不同权重,例如使用在信息检索领域开发的 “词频逆文档频率”(TF-IDF)加权方案[Salton and Buckley, 1988]。
如果只考虑长度为 k k k 的子串,那么我们将获得 k k k -谱核[Leslie et al., 2003]。
重要的是,有一些使用后缀树的有效方法,可以在 ∣ x ∣ + ∣ x ′ ∣ |x| + |x'| ∣ x ∣ + ∣ x ′ ∣ 的线性时间计算字符串核 k ( x , x ′ ) k(x,x') k ( x , x ′ ) (对权重 {w_s} 有一些限制)[Leslie et al., 2003, Vishwanathan and Smola, 2003]。
字符串核的工作是由 Watkins [1999] 和 Haussler [1999] 开始的。我们上面描述的方法有许多进一步的发展;例如 Lodhi 等 [2001] 超越子串来考虑 x x x 的子序列,这些子序列不一定是连续的,Leslie 等 [2003] 描述了不匹配字符串核,如果它们之间最多有 m m m 个不匹配,则允许 x x x 和 x ′ x' x ′ 的子串 s s s 和 s ′ s' s ′ 分别匹配。我们期待这一领域的进一步发展,定制(或工程化)字符串核以具有在特定领域有意义的性质。
我们考虑子字符串匹配的字符串核的想法可以很容易地扩展到树,例如通过查看子树的匹配 [Collins and Duffy, 2002]。
Leslie 等 [2003] 已将字符串核应用于将蛋白质域分类为 SCOP12 超家族。获得的结果明显优于基于 PSI-BLAST13 搜索或生成隐马尔可夫模型分类器的方法。 Jaakkola 等[2000] 使用 Fisher 核(在下一节中描述)获得了类似的结果。Saunders 等 [2003] 还描述了使用字符串核将 Reuters-2157814 数据库中的自然语言新闻专线故事分为十类的问题。
4.4.2 Fisher 核
如上所述,我们的问题是输入 x x x 是任意大小的结构化对象,例如一个字符串,我们希望从中提取特征。 Fisher 核(由 Jaakkola 等于 2000 年引入)通过采用生成模型 p ( x ∣ θ ) p(x|\boldsymbol{\theta}) p ( x ∣ θ ) 来实现这一点,其中 θ \boldsymbol{\theta} θ 是参数向量,并计算特征向量 ϕ θ ( x ) = ∇ θ log p ( x ∣ θ ) \phi_{\boldsymbol{\theta}}(x) = \nabla_{\boldsymbol{\theta}} \log p(x | \boldsymbol{\theta}) ϕ θ ( x ) = ∇ θ log p ( x ∣ θ ) 。 ϕ θ ( x ) \phi_{\boldsymbol{\theta}}(x) ϕ θ ( x ) 有时称为 分值向量 。
以字符串的马尔可夫模型为例。令 x k x_k x k 为字符串 x x x 中的第 k k k 个符号。然后马尔可夫模型给出 p ( x ∣ θ ) = p ( x 1 ∣ π ) ∏ i = 1 ∣ x ∣ − 1 p ( x i + 1 ∣ x i , A ) p(x|\boldsymbol{\theta}) = p(x_1 | \boldsymbol{\pi}) \prod^{|x|−1}_{i=1} p(x_{i+1} | x_i, A) p ( x ∣ θ ) = p ( x 1 ∣ π ) ∏ i = 1 ∣ x ∣ − 1 p ( x i + 1 ∣ x i , A ) ,其中 θ = ( π , A ) \boldsymbol{\theta} = (\boldsymbol{\pi}, A) θ = ( π , A ) 。这里 ( π ) j (\boldsymbol{\pi})_j ( π ) j 给出了 x 1 x_1 x 1 是字母表 A A A 中第 j j j 个符号的概率,并且 A A A 是一个 ∣ A ∣ × ∣ A ∣ |A| \times |A| ∣ A ∣ × ∣ A ∣ 随机矩阵,其中 a j k a_{jk} a jk 给出 p ( x i + 1 = k ∣ x i = j ) p(x_{i+1} = k | x_i = j) p ( x i + 1 = k ∣ x i = j ) 的概率。给定这样的模型,可以直接计算给定 x x x 的分值向量。
也可以考虑其他生成模型 p ( x ∣ θ ) p(x|\boldsymbol{\theta}) p ( x ∣ θ ) 。例如,我们可以尝试 k k k 阶马尔可夫模型,其中 x i x_i x i 由前面的 k k k 个符号预测。见 Leslie 等 [2003] 和 Saunders 等 [2003] 对 k k k 谱核中使用的特征与从 k − 1 k − 1 k − 1 阶马尔可夫模型派生的分值向量的相似性进行了有趣的讨论。正如 Jaakkola 等 [2000] 所讨论的,另一个有趣的选择是使用隐马尔可夫模型 (HMM) 作为生成模型。 了解从 x ∈ R D \mathbf{x} \in \mathbb{R}^D x ∈ R D 的各向同性高斯模型推导出的线性核。
我们根据 x x x 和 x ′ x' x ′ 的分值向量定义核 k ( x , x ′ ) k(x,x') k ( x , x ′ ) 。一个简单的选择是设置
k ( x , x ′ ) = π θ ( x ) M − 1 ϕ θ ( x ′ ) (4.46) k(x, x') = \boldsymbol{\pi}_{\boldsymbol{\theta}}(x)M^{−1} \boldsymbol{\phi}_{\boldsymbol{\theta}}(x') \tag{4.46}
k ( x , x ′ ) = π θ ( x ) M − 1 ϕ θ ( x ′ ) ( 4.46 )
其中 M M M 是严格正定矩阵。或者,对于某些 α > 0 α > 0 α > 0 ,我们可以使用平方指数核 k ( x , x ′ ) = exp ( − α ∣ ϕ θ ( x ) − ϕ θ ( x ′ ) ∣ 2 ) k(x,x') = \exp(−α |\boldsymbol{\phi}_{\boldsymbol{\theta}}(x)−\boldsymbol{\phi}_{\boldsymbol{\theta}}(x')|^2) k ( x , x ′ ) = exp ( − α ∣ ϕ θ ( x ) − ϕ θ ( x ′ ) ∣ 2 )
随着 θ \boldsymbol{\theta} θ 的变化,p ( x ∣ θ ) p(x|\boldsymbol{\theta}) p ( x ∣ θ ) 的结构在信息几何中得到了广泛的研究(例如,参见 Amari,1985)。可以证明 log p ( x ∣ θ ) \log p(x|\boldsymbol{\theta}) log p ( x ∣ θ ) 的流形是黎曼流形,其度量张量是 Fisher 信息矩阵 F F F 的逆矩阵,其中
F = E x [ ϕ θ ( x ) ϕ θ ⊤ ( x ) ] (4.47) F = \mathbb{E}_x[\boldsymbol{\phi}_{\boldsymbol{\theta}}(x) \boldsymbol{\phi}^{\top}_{\boldsymbol{\theta}}(x)] \tag{4.47}
F = E x [ ϕ θ ( x ) ϕ θ ⊤ ( x )] ( 4.47 )
在 式(4.46)
中设置 M = F M = F M = F 给出 Fisher 核 。如果 F F F 难以计算,则可以求助于设置 M = I M = I M = I 。使用 Fisher 信息矩阵的优点是它使流形上的弧长对于 θ \boldsymbol{\theta} θ 的重新参数化不变。
Fisher 核使用类无关模型 p ( x ∣ θ ) p(x|\boldsymbol{\theta}) p ( x ∣ θ ) 。Tsuda 等 [2002] 开发了基于 ∇ θ ( log p ( y = + 1 ∣ x , θ ) − log p ( y = − 1 ∣ x , θ ) ) \nabla_{\boldsymbol{\theta}}(\log p(y = +1|x, \boldsymbol{\theta}) − \log p(y = −1|x, \boldsymbol{\theta})) ∇ θ ( log p ( y = + 1∣ x , θ ) − log p ( y = − 1∣ x , θ )) 的后验概率正切 (TOP) 核,它利用了 C + C_+ C + 和 C − C_− C − 类的类条件分布。