高斯过程回归稀疏近似方法的统一视角

【摘 要】 我们提供了一个新的统一视角，能够容纳所有现有的高斯过程回归的概率稀疏近似方法。我们的方法依赖于对所采用方法的有效先验（effective prior）的表达。这能够得到对这些方法的新见解，并突出现有方法之间的关系。它还允许对已知近似方法与完整高斯过程之间的接近程度进行理论上的排序。最后，我们直接给出了一种新的更好的稀疏近似设计，该设计在有吸引力的计算约束下结合了现有策略的优点。

【原 文】 Quinonero-Candela, J. and Rasmussen, C.E. (2005) ‘A unifying view of sparse approximate Gaussian process regression’, The Journal of Machine Learning Research, 6, pp. 1939–1959.

基于高斯过程 (GP) 的回归模型易于实现、灵活、完全概率模型，因此是许多应用领域中的强大工具。其主要局限性在于内存需求和计算需求分别随着训练点数量 $n$ 的平方和立方增长，使实施只能限制在最多几千个训练点的问题上。为了克服计算限制，许多作者提出了大量稀疏近似。所有这些近似方案的共同点是：只精确处理隐变量的一个子集（注：此处隐变量指底层不含噪声的高斯过程真实值变量），其余变量则采用计算成本低的近似处理。然而，已发布的算法有着截然不同的动机、重点和阐述，因此很难概括（参见 Rasmussen 和 Williams，2006 年^[8]，第 8 章）它们之间的关联，以及哪些算法可能更优的讨论。

在本文中，我们提供了一种有关高斯过程回归稀疏近似的统一视角,该方法简单但功能强大： 我们分析每种算法的后验，并计算其 有效先验（effective prior）。因此，所有稀疏近似算法都将被重新解释为 “具有近似先验的精确推断”，而不是现在常认为的 “具有精确先验的近似推断”（注： 稀疏近似方法大多采用归纳点来近似真实训练数据，实在实施后验推断之前的工作，因此常被称为属于先验近似方法）。 此方法的优点在于： 可以根据函数的先验假设直接表达近似，从而使得近似结果更容易被理解。我们对近似的看法可能不是唯一的，但它能够将现有各种概率稀疏近似都放在一个框架内，从而能够比较并揭示它们之间的关系。

注： 作者在此处力图建立一种统一的分析视角，将所有稀疏近似方法都视为采用了近似先验后的精确推断和学习。与此相对的，是使用了近似的后验推断方法（如变分、MCMC）。因此，从某种程度上来说，本文最大的亮点在于提出了 “有效先验” 的概念，以及基于该概念形成的一个统一表达框架。此外需要注意的是，先验近似和后验近似并非非此即彼的关系，而是可以进行组合。如： 先验近似 + 精确推断、先验近似 + 变分推断 $\ldots$

本文结构：

• 在 第 1 节 中，我们简要介绍了用于回归的高斯过程模型。
• 在 第 2 节 中，我们展示了统一框架并写出了关键方程。
• 在 第 3 节 中，我们介绍了作为基线之一的数据子集（SoD）方法。
• 在 第 4-7 节 中，对各种稀疏算法提供了统一的分析。
• 在 第 8 节 中，介绍了转导和增广与稀疏框架的关系。
• 在 第 9 节 中，讨论了归纳变量的选择问题。
• 在 第 10 节 中，对一些特殊近似进行评论。
• 在最后得出结论。

1 高斯过程回归

概率回归通常表述如下：给定训练集 $\mathcal{D} = \{(\mathbf{x}_i, y_i), i = 1,\ldots , n\}$ 的 $n$ 对输入 $\mathbf{x}_i$ 和含噪声输出 $y_i$，计算在测试位置 $x_*$ 处的函数值 $f_*$（或含噪声的 $y_*$）的预测分布。在最简单的情况下，我们假设噪声是加性的、独立的、高斯的，则（隐）函数 $f(x)$ 和观测到的噪声目标 $y$ 之间存在如下关系：

$$y_i = f(\mathbf{x}_i) + \varepsilon_i , \text{ 其中 } \varepsilon_i \sim \mathcal{N}(0, \sigma^2_{noise}) \tag{1}$$

式中 $\sigma^2_{noise}$ 是噪声的方差。

【定义 1】 高斯过程 (GP) 是随机变量的集合，其中任意有限数量的随机变量集合都构成一致的联合高斯分布。

高斯过程回归是一种贝叶斯方法，它假设了一个在函数上的高斯过程先验（通常假设均值为 $0$ ），即先验地假设函数值具有如下行为特征：

$$p(\mathbf{f}|\mathbf{x_1}, \mathbf{x_2},\ldots , \mathbf{x}_n) = \mathcal{N}(\mathbf{0, K}) \tag{2}$$

其中 $\mathbf{f} = [ f_1, f_2,\ldots,f_n]^{\top}$ 是隐函数值构成的向量，$f_i = f(\mathbf{x}_i)$；$\mathbf{K}$ 是协方差矩阵，其元素由协方差函数 $K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$ 给出。请注意，高斯过程将隐函数值 $f_i$ 视为被输入索引的随机变量。在下文中，为简单起见，我们将忽略对输入的显式条件依赖关系，但要清楚： 高斯过程模型和所有表达式始终是以相应输入为索引（条件）的。

高斯过程模型并不对输入本身建模，只关心给定输入时输出的条件分布 $p(f_*|\mathbf{x_*}, \mathcal{D})$。

【备注 2】 请注意：为了遵守严格的贝叶斯形式，高斯过程先验的协方差函数应当与数据无关（但可依赖于其他参数）。

正如将在后面看到的，某些近似方案严格等价于高斯过程，而另一些则不行。也就是说，先验可能仍然是多元高斯分布，但训练案例和测试案例的协方差函数可能会有不同。

【定义 3】退化高斯过程：当且仅当一个高斯过程的协方差函数具有有限数量的非零特征值时，我们称之为退化的高斯过程。

退化高斯过程对应于有限的线性（主要指针对参数的线性）模型，典型如具有多项式协方差函数的高斯过程；而非退化高斯过程则不然，典型如具有平方指数或 RBF 核函数的高斯过程。一个有限的 $m$ 维线性模型的先验只能考虑最多 $m$ 个线性独立函数的空间；当 $n \gg m$ 时，这显得过于严格。但请注意，非退化性本身并不能保证对于给定的特定建模任务，存在 “正确类型” 的灵活性。有关高斯过程模型的更详细背景，请参见 Rasmussen 和 Williams (2006 ^[8]) 的示例。

高斯过程模型的推断和预测原理很简单：

注：此处重点建模的是 函数真实值 和 含噪声观测值 之间的关系；虽然在表达式中没有出现 $\mathbf{x}$，但其实隐含了对 $\mathbf{x}$ 的依赖。

推断：在训练隐函数值 $\mathbf{f}$ 和测试隐函数值 $\mathbf{f}_*$ 上放置一个联合的高斯过程先验（注：高斯过程先验是关于隐函数值的先验），然后使用贝叶斯规则将其与似然 $p(\mathbf{y|f})$ 结合，以获得联合后验:

$$p( \mathbf{f}, \mathbf{f}_*| \mathbf{y}) = \frac{p(\mathbf{f}, \mathbf{f}_*)p( \mathbf{y|f})}{p(\mathbf{y})} \tag{3}$$

上式中，高斯过程先验为 $p(\mathbf{f}, \mathbf{f}_*)$， 高斯过程后验为 $p(\mathbf{f}, \mathbf{f}_* | \mathbf{y})$，似然为 $p(\mathbf{y|f})$。

预测：边缘化掉上述 联合后验 中的训练集隐变量，即可产生我们关心的后验预测分布：

$$p(\mathbf{f}_* | \mathbf{y}) = \int p(\mathbf{f}, \mathbf{f}_* | \mathbf{y}) d \mathbf{f} = \frac{1}{p(\mathbf{y})} \int p(\mathbf{y|f}) p(\mathbf{f}, \mathbf{f}_*) d \mathbf{f} \tag{4}$$

或者可以换句话说：预测分布是 “高斯过程先验与似然的乘积，在归一化之后的边缘分布”。根据高斯过程定义，高斯过程先验 $p(\mathbf{f}, \mathbf{f}_*)$ 和似然 $p(\mathbf{y|f})$ 均是高斯的，即：

$$\begin{align*} \text{Prior:} \qquad p(\mathbf{f}, \mathbf{f}_*) &= \mathcal{N} \left( \mathbf{0}, \begin{bmatrix} K_{\mathbf{f,f}} & K_{*,\mathbf{f}}\\ K_{\mathbf{f},*} & K_{*,*} \end{bmatrix} \right ) \\ \text{Likelihood:} \qquad p(\mathbf{y|f}) &= \mathcal{N}(\mathbf{f}, \sigma^2_{noise} \mathbf{I}) \tag{5} \end{align*}$$

其中协方差符号 $K$ 的下标采用参与计算的随机向量表示，其中星号 $*$ 是测试函数值 $\mathbf{f}_*$ 的简写。$\mathbf{I}$ 是单位矩阵。由于 式（4） 中积分内的两个项都是高斯的，因此该积分具有解析形式解，进而有如下解析形式的预测分布（详情见 ^[8] 的第二章）：

$$p(\mathbf{f}_* | \mathbf{y}) = \mathcal{N}(K_{*,\mathbf{f}} (K_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I})^{-1} \mathbf{y}, K_{*,*} − K_{*,\mathbf{f}} (K_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I})^{-1} K_{\mathbf{f},*} ) \tag{6}$$

或写成另外一种等价形式：

$$\begin{align*} \boldsymbol{\mu}_* &= K_{*,\mathbf{f}} (K_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I})^{-1} \mathbf{y}\\ \boldsymbol{\Sigma}_* &= K_{*,*} − K_{*,\mathbf{f}} (K_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I})^{-1} K_{\mathbf{f},*} \end{align*}$$

注： 再次提醒，这里的符号 $\mathbf{f}$、$K$ 都隐式依赖于 $\mathbf{x}$。

上述表达式的问题在于：（1） 预测阶段：均值和方差的计算均需要对大小为 $n \times n$ 的矩阵求逆，这需要 $\mathcal{O}(n^3)$ 次运算，其中 $n$ 是训练案例的数量。（2）学习阶段：在利用训练数据学习核的超参数时，也同样涉及计算协方差矩阵逆和行列式的情况，并且如果采用梯度下降等方法，还会多次计算。因此，精确高斯过程实现通常仅能处理几千个训练案例的情况。

2 新的统一观点

稀疏高斯过程方法寻求通过修改 式(5) 中的（联合）高斯过程先验 $p(\mathbf{f}_*, \mathbf{f})$，来减少 式(6) 中预测的计算要求。

（1）归纳变量与增广分布

首先引入 $m$ 个额外的隐变量 $\mathbf{u} = [u_1,\ldots , u_m]^{\top}$，我们称之为 “归纳变量”。这些隐变量就像 $\mathbf{f}$ 和 $\mathbf{f}_*$ 一样，也是高斯过程值变量，并被 $X_{\mathbf{u}}$ 索引（我们称 $X_{\mathbf{u}}$ 为 “归纳输入”）。 一般来说，在最终的预测分布中，归纳变量 $\mathbf{u}$ 总是会被边缘化掉，不过，归纳输入 $X_{\mathbf{u}}$ 的选择在事实上会给最终的解带来影响，因此是非常重要的一个环节。

归纳变量可以被视为一个泛化概念，因为在其他文献中也有 “支撑点”、“活动集” 或 “伪输入” 等叫法。需要说明的是：特定的稀疏算法会以不同方式选择归纳变量；某些算法从训练集中选择某个子集作为归纳输入，而另一些则选择训练集之外的输入。关于归纳变量选择的问题参见 第 9 节，目前我们可以考虑任意的归纳变量。

由于高斯过程的一致性（或者边缘化性质），因此我们可以将原始的高斯过程先验增广至 $p(\mathbf{f}_*, \mathbf{f,u})$，然后关于 $\mathbf{u}$ 做边缘化后。采用这种方法构造出的先验高斯过程 $p(\mathbf{f}_*, \mathbf{f})$ 是精确的：

$$p(\mathbf{f}_*, \mathbf{f}) =\int p(\mathbf{f}_*, \mathbf{f, u}) d \mathbf{u} =\int p(\mathbf{f}_*, \mathbf{f|u}) p(\mathbf{u}) d \mathbf{u} \tag{7}$$

上式的第二个等号只是简单地应用了概率公式。上式中积分符号内的项均为高斯的（根据归纳变量的定义，$p(\mathbf{u}) = \mathcal{N}(\mathbf{0}, K_{\mathbf{u,u}})$ ），因此最终是一个精确的表达。

下面，让我们开始进入能够产生几乎所有稀疏近似的一个基础框架。

（2）训练条件与测试条件的分离

首先，为了近似联合先验，我们将对 式（7） 右侧进行分解，前提是 假设测试变量集 $\mathbf{f}_*$ 和训练变量集 $\mathbf{f}$ 在给定归纳变量 $\mathbf{u}$ 时条件独立，这也是本文框架必须假设的第一步，见 图 1。基于该独立性假设，式（7） 可以被近似为（此处的近似来自于假设）：

$$p(\mathbf{f}_*, \mathbf{f}) \simeq q(\mathbf{f}_*, \mathbf{f}) =\int q(\mathbf{f}_*|\mathbf{u}) q( \mathbf{f|u}) p(\mathbf{u}) d \mathbf{u} \tag{8}$$

归纳变量的命名动机是： $\mathbf{f}$ 和 $\mathbf{f}_*$ 只能通过 $\mathbf{u}$ 通信，因此 $\mathbf{u}$ 归纳了训练集和测试集之间的依赖关系。

在下文中我们将看到，各种文献中提出的稀疏近似算法，大多数都是对 式(8) 中积分内的两个近似归纳条件 $q(\mathbf{f|u})$ 和 $q(\mathbf{f}_*|\mathbf{u})$ 作出了不同的附加假设。因此，在这里先给出两个条件的精确表达式会对后面的论证非常有用：

$$\begin{align*} &\text{Training Conditional:} \qquad &p(\mathbf{f|u}) = \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}, K_{\mathbf{f,f}} − Q_{\mathbf{f,f}}) \tag{9a}\\ &\text{Test Conditional:} \qquad &p(\mathbf{f}_*|\mathbf{u}) = \mathcal{N}(K_{*,\mathbf{u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}, K_{*,*} − Q_{*,*}) \tag{9b} \end{align*}$$

此处可以直接利用 式（6） 的结论，不过是一种无噪声版本，其中 $\mathbf{u}$ 扮演了无噪声观测的角色。

我们在上式中引入了简写符号 $Q_{\mathbf{a,b}} \triangleq K_{\mathbf{a,u}} K^{-1}_{\mathbf{u,u}} K_{\mathbf{u,b}}$。

请注意：式(9) 中的（半正定）协方差矩阵的形式为 $K − Q$，可以被解释为：先验协方差 $K$ 减去了一个能够量化 $\mathbf{u}$ 提供的有关问题域中变量（$\mathbf{f}$ 或 $\mathbf{f}_*$ ）的信息量的（非负定）矩阵 $Q$。

我们强调，本文中讨论的所有稀疏方法，仅对应于 式(9) 中两种条件分布的不同近似方案，并且我们自始至终都使用如下的精确似然和关于归纳变量的先验：

$$\begin{align*} p(\mathbf{y|f}) &= \mathcal{N}(\mathbf{f}, \sigma^2_{noise}\mathbf{I}) \\ p(\mathbf{u}) &= \mathcal{N}(\mathbf{0}, K_{\mathbf{u,u}}) \tag{10} \end{align*}$$

图 1：归纳变量 $\mathbf{u}$ 与训练隐函数值 $\mathbf{f} = [ f_1, \ldots, f_n]^{\top}$ 和测试隐函数值 $\mathbf{f}_*$。粗水平线表示一组完全连接的节点。观测 $y_1, \ldots , y_n$ 和 $y_*$（未显示）将通过 式 (5) 的精确（因式分解）似然方式独立于相应的隐函数值。左图：全连接图，对应于没有对这些变量的完全联合高斯过程分布进行近似的情况。此时，归纳变量 $\mathbf{u}$ 是多余的，因为所有隐函数值都能与其他隐函数值通信。右图：假设给定 $\mathbf{u}$ 时，训练函数值变量和测试函数值变量之间的条件独立。这导致了 式 (8) 中训练条件和测试条件之间的分离。请注意， 此时训练隐函数值和测试隐函数值之间的通信路径被切断了，来自 $\mathbf{f}$ 的信息只能通过归纳变量 $\mathbf{u}$ 传递到 $\mathbf{f}_*$。

3 数据子集（SoD）近似

为便于后面的讨论，本节先介绍一种可以作为基线方法的简单稀疏近似：数据子集 (SoD) 近似。需要说明的是： 该方法不符合我们的统一框架 。

根据名字就可以知道，SoD 方法是从原始训练集中选择 $m < n$ 个案例，因此其计算复杂度可以降低到 $\mathcal{O}(m^3)$。不过，我们通常不会期望 SoD 能够成为一种有竞争力的方法，因为当只考虑一部分训练数据时，几乎不太可能得到具有准确不确定性的真实结果（即便有足够的冗余数据和好的子集选择方法）。我们在这里主要将其作为对比的一个基线而已。

图 5 左上方的子图是 SoD 的一个示例。可以看到在对随机选择的 $10$ 个案例的子集进行训练时，SoD 方法产生了比较宽泛的预测分布（两条虚线之间的区域）。与其他方法的公平比较将考虑到计算复杂性与 $n$ 无关，而不是其他更高级的方法。这些额外的计算资源可以以多种方式使用，例如较大的 $m$，或主动（而不是随机）选择 $m$ 个点。在本文中，我们将专注于理解各种近似的理论基础，而不是研究将近似方案转化为实际算法所需的必要启发式方法。

4 回归子集 (SoR) 近似或确定性归纳条件（DIC）近似

（1）方法概述

回归子集 (SoR) 算法由 Silverman (1985 ^[11]) 给出，Wahba 等 (1999 ^[17]) 再次提到，然后 Smola 和 Bartlett (2001 ^[12]) 对其进行了改编，提出了对高斯过程回归的稀疏贪心近似。SoR 模型是有限参数线性模型，其权重先验经过特殊设计。对于任何输入 $\mathbf{x}_*$，其对应的函数值 $f_*$ 由以下线性模型给出：

$$\begin{align*} &f_* = K_{*,\mathbf{u}} \mathbf{w_u} \\ &p(\mathbf{w_u}) = \mathcal{N}(\mathbf{0}, K^{-1}_{\mathbf{u,u}}) \tag{11} \end{align*}$$

式中归纳输入集 $X_{\mathbf{u}}$ 中的每个案例都有一个对应的权重。特别是：权重先验的协方差矩阵被设计为归纳变量 $\mathbf{u}$ 的协方差矩阵的逆。利用这种特殊关系，我们能够恢复归纳变量 $\mathbf{u}$ 上的精确高斯过程，其均值为零，协方差为：

$$\mathbf{u} = K_{\mathbf{u,u}} \mathbf{w_u} \quad \Rightarrow \quad \langle \mathbf{u} \mathbf{u}^{\top} \rangle = K_{\mathbf{u,u}} \langle \mathbf{w_u} \mathbf{w_u}^{\top} \rangle K_{\mathbf{u,u}} = K_{\mathbf{u,u}} \tag{12}$$

使用 $\mathbf{u}$ 上的有效先验和 $\mathbf{w_u} = K^{-1}_{\mathbf{u,u}} \mathbf{u}$ 这一事实，我们可以用一种等效的、更直观的方式重新定义 SoR 模型：

$$\begin{align*} &\mathbf{f}_* = K_{*,\mathbf{u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}\\ &\mathbf{u} \sim \mathcal{N}(\mathbf{0}, K_{\mathbf{u,u}}) \tag{13} \end{align*}$$

（2）训练条件与测试条件

推断方面：

鉴于任何 $\mathbf{f}_*$ 和 $\mathbf{u}$ 之间存在确定性关系，式 (8) 中积分的近似条件分布由下式给出：

$$q_{SoR}(\mathbf{f|u}) = \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}, \mathbf{0}) \\ q_{SoR}(\mathbf{f}_*|\mathbf{u}) = \mathcal{N}(K_{*,\mathbf{u}} K^{-1}_{\mathbf{u,u}} \mathbf{u} , \mathbf{0}) \tag{14}$$

与 式(9) 相比，条件的协方差为零。

（3）先验近似

SoR 近似所隐含的先验，可以很容易通过 式(8) 推导得到：

$$q_{SoR}(\mathbf{f}, \mathbf{f}_*) = \mathcal{N} \left( \mathbf{0}, \begin{bmatrix} Q_{\mathbf{f,f}} & Q_{\mathbf{f},*} \\ Q_{*,\mathbf{f}} & Q_{*,*} \end{bmatrix} \right ) \tag{15}$$

回忆一下 $Q$ 的形式：$Q_{\mathbf{a,b}} \triangleq K_{\mathbf{a,u}} K^{-1}_{\mathbf{u,u}} K_{\mathbf{u,b}}$ 。

SoR 方法也被称为 确定性归纳条件 (DIC) 近似。此近似先验是退化的，模型中只有 $m$ 个自由度，这意味着只能从先验中得出 $m$ 个线性独立的函数。第 $m + 1$ 个是前面的线性组合。例如，在非常低的噪声状态下，后验可能会受 $m$ 个训练案例的强约束。

先验的退化导致不合理的预测分布。事实上，该近似先验是如此严格，以至于在给定足够数据的情况下，只有非常有限的函数族在后验函数下是合理的，这会导致过度自信的预测方差。这也是具有少量权重的有限线性模型普遍存在的问题（有关详细信息，请参阅 Rasmussen 和 Quinonero-Candela，2005 年^[7]）。图 5 右上图展示了 SoR 近似的预测不确定性存在一定的不合理性。

（4）预测公式：

预测分布是通过在 式(4) 中使用 SoR 近似先验（式(15)）代替真实先验而获得的。对于所有的近似方法，我们都可以给出两种形式的预测分布（相互等价），一种便于解释和理解，而另一种则计算起来更经济：

$$\begin{align*} q_{SoR}(\mathbf{f}_* | \mathbf{y}) &= \mathcal{N}(Q_{*,\mathbf{f}} (Q_{\mathbf{f,f}} + \sigma^2_{noise} \mathbf{I})^{-1} \mathbf{y}, Q_{*,*} − Q_{*,\mathbf{f}} (Q_{\mathbf{f,f}} + \sigma^2_{noise} \mathbf{I})^{-1}Q_{\mathbf{f},*} ) \tag{16a}\\ &= \mathcal{N}(\sigma^{-2} K_{*,\mathbf{u}} \Sigma K_{\mathbf{u,f}} \mathbf{y}, K_{*,\mathbf{u}} \Sigma K_{\mathbf{u},*} ) \tag{16b} \end{align*}$$

其中 $\Sigma = (\sigma^{-2} K_{\mathbf{u,f}} K_{\mathbf{f,u}} + K_{\mathbf{u,u}})^{-1}$。

式 (16a) 很容易被识别为 式 (6) 的常规预测公式，只是协方差 $K$ 均被 式(15) 中提出的 $Q$ 所取代。这相当于用 $k_{SoR}(\mathbf{x}_i, \mathbf{x}_j) = k(\mathbf{x}_i, u) K^{-1}_{\mathbf{u,u}} k(u, \mathbf{x}_j)$ 替换协方差函数 $k$。新协方差函数的秩（最多）为 $m$。因此我们有：

【备注 4】 SoR 近似等价于具有协方差函数 $k_{SoR}(\mathbf{x}_i, \mathbf{x}_j) = k(\mathbf{x}_i, \mathbf{u}) K^{-1}_{\mathbf{u,u}} k(\mathbf{u}, \mathbf{x}_j)$ 的退化高斯过程中的精确推断。

式(16b) 在计算上更便宜。考虑到 式(11)，$\Sigma$ 是权重 $\mathbf{w_u}$ 后验的协方差。请注意，与数据子集方法相反，所有训练案例都被考虑在内。该方法初始阶段的计算复杂度为 $\mathcal{O}(nm^2)$，每个测试案例的预测均值和预测方差计算复杂度分别为 $\mathcal{O}(m)$ 和 $\mathcal{O}(m^2)$。

5 确定性训练条件 (DTC) 近似

（1）方法概述

借鉴 Csato 和 Opper (2002 ^[2]) 工作中的想法，Seeger 等(2003 ^[10]) 最近提出了另一种被称为 投影隐变量 (Projected Latent Variables，PLV) 高斯过程回归的稀疏近似方法，该方法不受 SoR 近似的不合理预测不确定性影响，但却能够产生完全相同的预测均值。Seeger 等(2003 ^[10]) 表示，该方法依赖于似然近似，基于投影 $\mathbf{f} = K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}$:

$$p(\mathbf{y|f}) \simeq q(\mathbf{y|u}) = \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}, \sigma^2_{noise} \mathbf{I}) \tag{17}$$

（2）训练条件与测试条件

该方法也被 Rasmussen 和 Williams（2006 年^[8]，第 8 章）称为 投影过程近似法 (Projected Process Approximation, PPA)。获得等效模型的一种方法是保留通常的似然，但强加确定性训练条件和 式 (9b) 的精确测试条件。

$$\begin{align*} q_{DTC}(\mathbf{f|u}) &= \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u,0})\\ q_{DTC}(\mathbf{f}_*| \mathbf{u}) &= p(\mathbf{f}_*| \mathbf{u}) \tag{18} \end{align*}$$

这种重新表述的优点是允许我们坚持我们对具有近似先验的精确推断（具有精确似然）的观点。实际上，在该模型下，给定 $\mathbf{u}$ 的 $\mathbf{f}$ 的条件分布与 式(14) 左侧给出的 SoR 的条件分布相同。这种近似的系统名称是 确定性训练条件 (DTC)。

与 SoR 的根本区别在于： DTC 使用 式(9b) 精确测试条件，而不是 SoR 的 $\mathbf{f}_*$ 和 $\mathbf{u}$ 之间的确定性关系。

（3）先验近似

DTC 隐含的联合先验由下式给出：

$$q_{DTC}(\mathbf{f}, \mathbf{f}_*) = \mathcal{N} \left ( \mathbf{0}, \begin{bmatrix} Q_{\mathbf{f,f}} & Q_{\mathbf{f},*} \\ Q_{*,\mathbf{f}} & K_{*,*} \end{bmatrix} \right ) \tag{19}$$

这与 SoR 近似 式(15) 隐含的有效先验惊人地相似。根本区别在于，在 DTC 近似下，$\mathbf{f}_*$ 具有其自身的先验方差，由 $K_{*,*}$ 给出。这种先验方差逆转了预测不确定性的行为，并将它们转变为合理的行为，请参见 图 5 的说明。

（4）预测公式

预测分布现在由下式给出：

$$\begin{align*} q_{DTC}(\mathbf{f}_* | \mathbf{y}) &= \mathcal{N}(Q_{*,\mathbf{f}} (Q_{\mathbf{f,f}} + \sigma^2_{noise} \mathbf{I})^{-1} \mathbf{y}, K_{*,*} − Q_{*,\mathbf{f}} (Q_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I})^{-1} Q_{\mathbf{f},*} \tag{20a}\\ &= \mathcal{N}(\sigma^{-2} K_{*,\mathbf{u}} \Sigma K_{\mathbf{u,f}} \mathbf{y}, K_{*,*} − Q_{*,*} + K_{*,\mathbf{u}} \Sigma K^{\top}_{*,\mathbf{u}} ) \tag{20b} \end{align*}$$

我们再次使用了 式(16) 中定义的 $\Sigma = (\sigma^{-2} K_{\mathbf{u,f}} K_{\mathbf{f,u}} + K_{\mathbf{u,u}})^{-1}$。 DTC 的预测均值与 SoR 方法 （式(16)） 一致，但预测方差将 SoR 中的 $Q_{*,*}$ 替换为 $K_{*,*}$。后者更大，因为 $K_{*,*} − Q_{*,*}$ 是正定的。这个添加的项是 $\mathbf{f}_*$ 后验的预测方差，条件是 $\mathbf{u}$。随着 $\mathbf{x}_*$ 远离 $X_{\mathbf{u}}$ 中的归纳输入，它会增长到先验方差 $K_{*,*}$ 。

【备注 5】 DTC 和 SoR 的预测分布之间的唯一区别是方差。 DTC 的预测方差绝不会小于 SoR。请注意，由于训练案例和测试案例的协方差的计算方式不同，参见 式 (19)

【备注 6】 DTC 近似并不精确对应于一个高斯过程，因为隐值之间的协方差取决于它们是训练案例还是测试案例，这违反了一致性，请参见定义 1。DTC 近似的计算复杂度具有与 SoR 方法相同的阶数。

6 完全独立条件训练 (FITC) 近似

（1）方法概述

最近，Snelson 和 Ghahramani (2006 ^[13]) 提出了另一种似然近似来加速高斯过程回归，他们称之为使用 “伪输入” 的稀疏高斯过程 (SGPP)。DTC 方法基于 式(17) 给出的似然近似，但 SGPP 方法提出了一种更复杂的似然近似，具有更丰富的协方差

$$p(\mathbf{y|f}) \simeq q(\mathbf{y|u}) = \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u ,u}} \mathbf{u}, \text{diag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}}] + \sigma^2_{noise} \mathbf{I}) \tag{21}$$

其中 $\text{diag}[A]$ 是一个对角矩阵，其元素与 $A$ 的对角线匹配。

（2）训练条件与测试条件

正如我们在 式(18) 中为 DTC 所做的那样，我们提供了一个替代的等效公式，称为基于归纳条件的 完全独立训练条件 (FITC)：

$$\begin{align*} q_{FITC}( \mathbf{f|u}) &= \prod^{n}_{i=1} p( f_i| \mathbf{u}) = \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}, \text{diag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}}]) \\ q_{FITC}( \mathbf{f}_*|\mathbf{u}) &= p ( \mathbf{f}_*|\mathbf{u}) \tag{22} \end{align*}$$

我们看到，与 SoR 和 DTC 不同，FITC 并未在 $\mathbf{f}$ 和 $\mathbf{u}$ 之间施加确定性关系。FITC 没有忽略方差，而是提出了给定 $\mathbf{u}$ 的 $\mathbf{f}$ 的训练条件分布的近似值作为进一步的独立性假设。此外，在 式(22) 中使用了 式(9b) 中的精确测试条件，尽管其原因将在本节末尾变得清晰，我们最初只考虑一个测试案例 $\mathbf{f}_*$。图 2 给出了相应的图模型。

（3）先验近似

FITC 隐含的有效先验由下式给出：

$$q_{FITC}(\mathbf{f}, \mathbf{f}_*) = \mathcal{N} \left( \mathbf{0}, \begin{bmatrix} Q_{\mathbf{f,f}} − \text{diag}[Q_{\mathbf{f,f}} − K_{\mathbf{f,f}}] & Q_{\mathbf{f},*} \\ Q_{*,\mathbf{f}} & K_{*,*} \end{bmatrix} \right) \tag{23}$$

图 2：FITC 近似的图形模型。与图 1 中的那些相比，隐函数值之间的所有边缘都已被删除：隐函数值在给定诱导变量 $\mathbf{u}$ 的情况下有条件地完全独立。虽然严格来说 SoR 和 DTC 近似也可以用该图表示，但请注意，两者都进一步假设 $\mathbf{f}$ 和 $\mathbf{u}$ 之间存在确定性关系。

（4）预测公式

请注意，DTC 和 FITC 之间的唯一区别在于先验协方差矩阵的的左上角，FITC 用对角线上的精确协方差替换了 DTC 的近似协方差。预测分布为

$$\begin{align*} q_{FITC}( \mathbf{f}_* | \mathbf{y}) &= \mathcal{N}(Q_{*,\mathbf{f}}(Q_{\mathbf{f,f}} + \Lambda)^{-1} \mathbf{y}, K_{*,*} − Q_{*,\mathbf{f}} (Q_{\mathbf{f,f}} + \Lambda)^{-1} Q_{\mathbf{f},*}) \tag{24a} \\ &= \mathcal{N}(K_{*,\mathbf{u}} \Sigma K_{\mathbf{u,f}} \Lambda^{−1} \mathbf{y}, K_{*,*} − Q_{*,*} + K_{*,\mathbf{u}} \Sigma K_{\mathbf{u},*} ) \tag{24b} \end{align*}$$

其中我们定义了 $\Sigma = (K_{\mathbf{u,u}} + K_{\mathbf{u,f}} \Lambda^{-1}K_{\mathbf{f,u}})^{-1}$ 和 $\Lambda = \text{diag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I}]$。计算复杂度与 SoR 和 DTC 相同。

联合预测问题与完全独立测试条件

到目前为止，我们只考虑了一个测试案例的情况。联合预测有两种选择：

• 1. 使用来自 式(9b) 的完全测试条件；
• 2. 将因子分解假设扩展到测试条件。

尽管 Snelson 和 Ghahramani (2006 ^[13]) 没有明确讨论联合预测，但他们似乎打算采用第二种选择。尽管出于计算原因，测试案例的额外独立性假设并不是真正必要的，但它确实会影响近似的性质。在选项 1) 下，训练和测试协方差的计算方式不同，因此这不符合我们对高斯过程模型的严格定义，但是

【备注 7】 如果将完全独立假设扩展到测试条件，则 FITC 近似等效于具有协方差函数 $k_{FIC}(\mathbf{x}_i, \mathbf{x}_j) = k_{SoR}(\mathbf{x}_i, \mathbf{x}_j) + \delta_{i,j} [k(\mathbf{x}_i, \mathbf{x}_j) − k_{SoR}(\mathbf{x}_i, \mathbf{x}_j)]$ 的非退化高斯过程中的精确推断

其中 $\delta_{i,j}$ 是 Kronecker 的 delta。始终强制条件（训练和测试）完全独立的方法的逻辑名称是完全独立条件 (FIC) 近似。 FIC 隐含的有效先验是：

$$q_{FIC}(\mathbf{f}, \mathbf{f}_*) = \mathcal{N} \left( \mathbf{0}, \begin{bmatrix} Q_{\mathbf{f,f}} − \text{diag}[Q_{\mathbf{f,f}} − K_{\mathbf{f,f}}] & Q_{\mathbf{f},*} \\ Q_{*,\mathbf{f}} & Q_{*,*} − \text{diag}[Q ∗,∗ − K_{*,*}] \end{bmatrix} \right) \tag{25}$$

7 部分独立训练条件 (PITC) 近似

（1）训练条件与测试条件

在上一节中，我们看到了如通过独立分布（即具有对角协方差矩阵的训练条件）来近似训练条件，进而改进了 DTC 近似。在本节中，我们将通过将训练条件扩展为具有块对角线协方差矩阵，来进一步改进近似（同时保持计算上的吸引力）：

$$\begin{align*} q_{PITC}(\mathbf{f|u}) &= \mathcal{N}(K_{\mathbf{f,u}} K^{-1}_{\mathbf{u,u}} \mathbf{u}, \text{blockdiag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}}])\\ q_{PITC}(\mathbf{f}_*|\mathbf{u}) &= p(\mathbf{f}_*|\mathbf{u}) \tag{26} \end{align*}$$

其中 $\text{blockdiag}[A]$ 是块对角矩阵（其中未明确说明块结构）。我们在图 3 中以图方式表示 PITC 近似。

（2）先验近似

将其类似于上一节中的 FITC 近似进行开发，我们得到联合先验

$$q_{PITC}(\mathbf{f}, \mathbf{f}_*) = \mathcal{N} \left( \mathbf{0}, \begin{bmatrix} Q_{\mathbf{f,f}} − \text{blockdiag}[Q_{\mathbf{f,f}} − K_{\mathbf{f,f}}] & Q_{\mathbf{f},*}\\ Q_{*,\mathbf{f}} & K_{*,*} \end{bmatrix} \right) \tag{27}$$

（3）预测公式

并且预测分布与 式(24) 相同，除了 $\Lambda = \text{blockdiag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I} ]$ 的替代定义。 Schwaighofer 和 Tresp（2003 年 ^[9]，第 3 节）从 Tresp（2000 年 ^[15]）最初的贝叶斯委员会机 (BCM) 发展而来，获得了相同的表达式。 Lehel Csato 指出了与 FITC 的关系。 BCM 最初被提议作为转导学习器（即在训练之前必须知道测试输入），并且归纳输入 $X_{\mathbf{u}}$ 被选择为测试输入。我们将在下一节详细讨论转导。

重要的是要认识到 BCM 提出了两个正交思想：

• 首先，部分独立训练条件的块对角线结构；
• 其次，将归纳输入设置为测试输入。

这两个想法可以独立使用，在 第 8 节 中我们建议使用第一个而不使用第二个。

PITC 近似的计算复杂度取决于 式(26) 中强加的分块结构。 Tresp (2000) 也推荐选择 $k = n/m$ 个块，每个块的大小为 $m \times m$。计算复杂度仍然是 $\mathcal{O}(nm^2)$。由于在 PITC 模型中，训练案例和测试案例的协方差计算方式不同，因此：

【备注 8】 PITC 近似并不完全对应于一个高斯过程。

这是因为计算协方差时需要知道点是来自训练集还是测试集，式(27)。通过将部分条件独立假设扩展到测试条件，可以从 PITC 获得高斯过程，就像我们在 【备注 7】 中为 FITC 所做的那样。

图 3：PITC 近似的图形表示。由一组索引 $I_i$ 索引的一组隐函数值 $\mathbf{f}_{I_i}$ 是完全连接的。 PITC 与 FITC（参见图 2 中的图表）的不同之处在于，条件独立性现在位于 $k$ 组训练隐函数值之间。这对应于 式(26) 中给出的真实训练条件的块对角线近似。

8 转导和增广

暂略。

9 关于归纳变量的选择

（1）现状

到目前为止，我们一直假设归纳输入 $X_{\mathbf{u}}$ 是给定的。传统上，稀疏模型通常建立在精心选择的训练输入子集之上。此概念在支持向量机中有着最好的体现（Cortes 和 Vapnik，1995 ^[1]）。在稀疏高斯过程领域，也有人建议从训练输入中选择归纳输入 $X_{\mathbf{u}}$。

考虑到这中间涉及组合优化问题，有人建议采用贪心优化方法来选择归纳变量，其中涉及各种选择准则，如： 在线学习（Csato 和 Opper，2002 年 ^[2]）、贪心后验最大化（Smola 和 Bartlett，2001 年^[12]）、最大信息增益（Seeger 等, 2003 ^[10])、 匹配追踪 (Keerthi and Chu, 2006 ^[3]) 等。如前一节所述，从测试输入中选择归纳输入也已在转导中被考虑。

最近，Snelson 和 Ghahramani (2006 ^[13]) 提出放宽归纳变量必须是训练/测试案例子集的约束，将离散选择问题转变为一个连续优化问题。人们可能希望在连续情况下会比在离散情况下更容易找到一个好的解，尽管在这两种情况下都很难找到全局最优解。也许约束较少的选择可以在稀疏模型中带来更好的性能。

（2）基本方法

到底应该使用哪个最优准则来选择归纳输入呢？

与完全贝叶斯方法不同（其中涉及 $X_{\mathbf{u}}$ 的先验定义），我们可以最大化相对于 $X_{\mathbf{u}}$ 的边缘似然（也称为证据），Snelson 和 Ghahramani（2006 年 ^[13]）采用了此方法。本文提到的每种近似方法都涉及不同的有效先验，因此他们也都有自身特定的有效边缘似然（以归纳输入为条件）：

$$q(\mathbf{y}|X_{\mathbf{u}}) = \int \int p(\mathbf{y|f}) q(\mathbf{f|u}) p(\mathbf{u}|X_{\mathbf{u}})d \mathbf{u} d \mathbf{f} =\int p(\mathbf{y|f}) q(\mathbf{f}|X_{\mathbf{u}}) d \mathbf{f} \tag{29}$$

这与测试条件无关。我们在上面的等式中明确地以归纳输入 $X_{\mathbf{u}}$ 为条件。使用高斯恒等式，通过向 $\mathbf{f}$ 上有效先验的协方差添加岭 $\sigma^2_{noise}\mathbf{I}$（来自似然），可以很容易地获得有效边缘似然。使用 $\Lambda$ 的恰当定义，对数边缘似然变为：

$$\log q(\mathbf{y}|X_{\mathbf{u}}) = − \frac{1}{2} \log |Q_{\mathbf{f,f}} + \Lambda| − \frac{1}{2} \mathbf{y}^{\top} (Q_{\mathbf{f,f}} + \Lambda)^{-1} \mathbf{y} − \frac{n}{2} \log(2π) \tag{30}$$

其中 $\Lambda_{SoR} = \Lambda_{DTC} = \sigma^2_{noise}\mathbf{I}$，$\Lambda_{FITC} = \text{diag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}}] + \sigma^2_{noise}\mathbf{I}$，$\Lambda_{PITC} = \text{blockdiag}[K_{\mathbf{f,f}} − Q_{\mathbf{f,f}}] + \sigma^2_{noise}\mathbf{I}$。

所有方法的边缘似然计算成本都是 $\mathcal{O}(nm^2)$，其梯度相对于 $X_{\mathbf{u}}$ 的单个元素的计算成本是 $\mathcal{O}(nm)$。这当然意味着计算关于 $X_{\mathbf{u}}$ 整体的梯度的复杂性为 $\mathcal{O}(dnm^2)$，其中 $d$ 是输入空间的维度。

有人提议最大化有效后验而不是有效边缘似然（Smola 和 Bartlett，2001 ^[12]）。然而，这有隐含的危险，并可能导致过拟合。相反，最大化整个边缘似然是合理的，并且计算成本相同（有关更深入的分析，请参见 Quinonero-Candela，2004 年 ^[5]，第 3.3.5 节和图 3.2）。

传统上，边缘似然主要用于学习高斯过程的超参数（即对超参数不强求获得分布，是一种非完全贝叶斯的处理，参见 Williams 和 Rasmussen，1996 ^[18]）。因此，对于稀疏近似而言，可以考虑在同一优化过程中同时学习 $X_{\mathbf{u}}$ 和协方差函数的超参数，参见 Seeger 等 (2003 ^[10]) 。

10 其他方法

在本节中，简要提及两个不适合我们统一框架的近似，其中一个不对应于适当的概率模型，另一个则使用了协方差函数的特殊构造。

10.1 Nystrom 近似

用于加速高斯过程回归的 Nystrom 近似最初由 Williams 和 Seeger (2001 ^[20]) 提出，然后受到 Williams 等 (2002 ^[19]) 的质疑。与 SoR 和 DTC 一样，Nystrom 近似将 $\mathbf{f}$ 的先验协方差近似为 $Q_{\mathbf{f,f}}$。然而，与这些方法不同，Nystrom 近似不是基于生成式的概率模型。$f_*$ 和 $\mathbf{f}$ 之间的先验协方差是精确的，这与 $\mathbf{f}$ 上的先验协方差不一致：

$$q(\mathbf{f}, \mathbf{f}_*) = \mathcal{N} \left( \mathbf{0}, \begin{bmatrix} Q_{\mathbf{f,f}} & K_{\mathbf{f},*} \\ K_{*,\mathbf{f}} & K_{*,*} \end{bmatrix} \right) \tag{31}$$

因此，我们无法从统一框架中派生出这种方法，也无法用图模型来表示它。更糟糕的是，生成的先验协方差矩阵甚至不能保证是正定的，因此预测方差有可能为负。请注意，将 式 (31) 中的 $K_{\mathbf{f},*}$ 替换为 $Q_{\mathbf{f},*}$ 足以使先验协方差正定，并获得 DTC 近似。

【备注 14】 Nystrom 近似不对应于形式良好的概率模型。忽略任何关于正定性的争论，Nystrom 近似的预测分布由下式给出：

$$p(f_* | \mathbf{y}) = \mathcal{N}(K^{\top}_{\mathbf{f},*} [Q_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I}]^{−1} \mathbf{y}, K_{*,*} − K^{\top}_{\mathbf{f},*} [Q_{\mathbf{f,f}} + \sigma^2_{noise}\mathbf{I}]^{−1} K_{\mathbf{f},*}) \tag{32}$$

但预测方差不能保证为正。计算成本为 $\mathcal{O}(nm^2)$。

10.2 相关向量机

由 Tipping (2001 ^[14]) 引入的相关向量机是一种有限线性模型，其权重具有独立的高斯先验。对于任何输入 $\mathbf{x}_*$，相应的函数输出由下式给出：

$$\mathbf{f}_* = \phi_* \mathbf{w}, \text{ 其中 } p(\mathbf{w}|A) = \mathcal{N}(0, A) \tag{33}$$

其中 $\phi_* = [\phi_1(\mathbf{x}),\ldots , \phi_m(\mathbf{x})]$ 是 $m$ 个基函数响应的（行）向量，$A = \text{diag}( \boldsymbol{\alpha}_1,\ldots , \boldsymbol{\alpha}_m)$ 是权重的联合先验精度（逆方差）的对角矩阵。 $\boldsymbol{\alpha}_i$ 是通过最大化 RVM 证据来学习的（通过还假设高斯加性 iid. 噪声获得，参见 式（1）），并且对于足够丰富的基函数集的典型情况，许多精度达到无穷大有效地剪掉相应的权重（有关非常有趣的分析，请参见 Wipf 等，2004 年^[21]）。因此，RVM 是一种稀疏方法，幸存的基函数称为相关向量。

请注意，由于 RVM 是一个有限线性模型，其权重具有高斯先验，因此可以将其视为高斯过程：

【备注 15】 RVM 等价于具有如下协方差函数的退化高斯过程

$$k_{RVM}(\mathbf{x}_i, \mathbf{x}_j) = \phi_i A^{−1} \phi_j^{\top} = \sum^{m}_{k=1} \boldsymbol{\alpha}^{−1}_k \phi_k(\mathbf{x}_i) \phi_k(\mathbf{x}_j)$$

表 1：构建近似的方式总结。所有这些方法都在前面的部分中进行了详细介绍。每个测试案例的初始成本以及均值和方差的成本分别为精确 GP 的 $n^2$、$n$ 和 $n^2$，以及所有其他方法的 $nm^2$、$m$ 和 $m^2$。 “GP ?” 列表示近似是否等同于精确高斯过程。对于 FITC，请参阅备注 7。

正如 Tipping (2001 ^[14], 式 (59)) 也指出的那样。到目前为止，我们提出的所有稀疏近似都完全独立于协方差函数的选择，对于 RVM，这种选择仅限于协方差函数，这些协方差函数可以表示为某些基函数的有限展开。作为与 SoR（在第 4 节中介绍）完全相同的方式退化的高斯过程，RVM 也确实存在不合理的预测方差。 Rasmussen 和 Quinonero-Candela (2005 ^[7]) 表明 RVM 的预测分布也可以通过增广来修复，参见第 8 节。一旦学习了 $\boldsymbol{\alpha}_i$，用 $m$ 表示幸存的相关向量的数量，计算RVM 的预测分布对于均值是 $\mathcal{O}(m)$，对于方差是 $\mathcal{O}(m^2)$。

RVM 通常与以训练输入为中心的径向基函数一起使用。 RVM 的一个可能有趣的扩展是学习基函数中心的位置，其方式与 Snelson 和 Ghahramani (2006 ^[13]) 为 FITC 近似提出的相同方式，请参见第 6 节。这是对学习的一种好奇回忆RBF 网络中的中心。

11 结论

我们为高斯回归过程的稀疏近似提供了一个统一框架。我们的方法包括两个步骤， 1) 我们根据对先验的近似重铸近似，2) 我们引入归纳变量 $\mathbf{u}$ 和给定 $\mathbf{u}$ 的条件独立性的想法。我们通过进一步简化训练和测试条件的协方差来恢复所有现有的稀疏方法，见 表 1 的总结。

以前的方法是基于不同的近似范式（例如似然近似、投影方法、矩阵近似、Kullback-Leibler 散度最小化等）提出的，这使得直接比较变得困难。在我们统一的观点下，我们解构方法，明确它们基于哪些构建块。例如，Snelson 和 Ghahramani (2006 ^[13]) 的 SGPP 包含两个想法，1) 似然近似和 2) 连续改变归纳输入的想法；这两个想法可以很容易地独立使用，并结合到其他方法中。类似地，Tresp (2000 ^[15]) 的 BCM 包含两个独立的想法 1) 块对角线假设，以及 2) 选择测试输入作为归纳变量的（转换）想法。最后我们注意到，虽然 1) 转导设置 $\mathbf{u} = \mathbf{f}_*$，2) 增广和 3) $X_{\mathbf{u}}$ 的连续优化的所有三个想法都在非常具体的设置中提出，但实际上它们完全是通用的想法，可以应用于任何所考虑的近似方案。

我们根据它们与相应的完整高斯过程的接近程度对近似进行了排名。然而，实际情况下的性能可能并不总是遵循这个理论排名，因为近似可能表现出可能特别适合特定数据集的属性（不存在于完整的高斯过程中）。这可能会使实证比较的解释具有挑战性。当添加必要的启发式方法以将理论结构转化为实际算法时，会出现更复杂的情况。我们没有在本文中描述完整的算法，但目前正在进行详细的实证研究（准备中，另请参见 Rasmussen 和 Williams，2006 年，第 8 章）。

我们注意到，对于所有考虑的方法，计算复杂度的顺序是相同的，$\mathcal{O}(nm^2)$。这突出表明，使用粗略近似没有计算借口，例如假设确定性关系，特别是在使用 SoR 甚至 DTC 之前可能应该三思而后行。虽然增广具有吸引人的预测特性，但它在计算上是昂贵的。目前尚不清楚增广是否对固定的计算预算有益。

我们在本文中只考虑了更简单的回归情况，但在分类设置中也普遍寻求稀疏性。将诸如期望传播 (EP) 或拉普拉斯方法（有关比较，参见 Kuss 和 Rasmussen，2005 年 ^[4]）等概率近似方法纳入我们的统一框架应该不难。

我们的分析表明，将最佳可能近似 (PITC) 与最强大的归纳输入选择方法相结合会产生一种有趣的新近似。这将对应于 BCM 的非转换版本。我们将避免在进行大量计算之前了解测试集的必要性，并且我们希望能够取代 Snelson 和 Ghahramani（2006 年 ^[13]）针对非常稀疏的近似报告的卓越性能。

参考文献

• [1] Corinna Cortes and Vladimir Vapnik. Support-vector network. Machine Learning, 20(3):273–297, 1995.
• [2] Lehel Csato and Manfred Opper. Sparse online Gaussian processes. Neural Computation, 14(3): 641–669, 2002.
• [3] Sathiya Keerthi and Wei Chu. A Matching Pursuit approach to sparse Gaussian process regression. In Y. Weiss, B. Sch ̈ olkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, Cambridge, Massachussetts, 2006. The MIT Press.
• [4] Malte Kuss and Carl Edward Rasmussen. Assessing approximate inference for binary Gaussian process classification. Journal of Machine Learning Research, pages 1679–1704, 2005.
• [5] Joaquin Quinonero-Candela. Learning with Uncertainty – Gaussian Processes and Relevance Vector Machines. PhD thesis, Technical University of Denmark, Lyngby, Denmark, 2004.
• [6] Carl Edward Rasmussen. Reduced rank Gaussian process learning. Technical report, Gatsby Computational Neuroscience Unit, UCL, 2002.
• [7] Carl Edward Rasmussen and Joaquin Qui ̃ nonero-Candela. Healing the relevance vector machine by augmentation. In International Conference on Machine Learning, 2005.
• [8] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT press, 2006.
• [9] Anton Schwaighofer and Volker Tresp. Transductive and inductive methods for approximate Gaussian process regression. In Suzanna Becker, Sebastian Thrun, and Klaus Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 953–960, Cambridge, Massachussetts, 2003. The MIT Press.
• [10] Matthias Seeger, Christopher K. I. Williams, and Neil Lawrence. Fast forward selection to speed up sparse Gaussian process regression. In Christopher M. Bishop and Brendan J. Frey, editors, Ninth International Workshop on Artificial Intelligence and Statistics. Society for Artificial Intelligence and Statistics, 2003.
• [11] Bernhard W. Silverman. Some aspects of the spline smoothing approach to non-parametric regression curve fitting. J. Roy. Stat. Soc. B, 47(1):1–52, 1985. (with discussion).
• [12] Alexander J. Smola and Peter L. Bartlett. Sparse greedy Gaussian process regression. In Todd K. Leen, Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13, pages 619–625, Cambridge, Massachussetts, 2001. The MIT Press.
• [13] Edward Snelson and Zoubin Ghahramani. Sparse Gaussian processes using pseudo-inputs. In Y. Weiss, B. Sch ̈ olkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, Cambridge, Massachussetts, 2006. The MIT Press.
• [14] Michael E. Tipping. Sparse Bayesian learning and the Relevance Vector Machine. Journal of Machine Learning Research, 1:211–244, 2001.
• [15] Volker Tresp. A Bayesian committee machine. Neural Computation, 12(11):2719–2741, 2000.
• [16] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 1995.
• [17] Grace Wahba, Xiwu Lin, Fangyu Gao, Dong Xiang, Ronald Klein, and Barbara Klein. The biasvariance tradeoff and the randomized GACV. In Michael S. Kerns, Sara A. Solla, and David A. Cohn, editors, Advances in Neural Information Processing Systems 11, pages 620–626, Cambridge, Massachussetts, 1999. The MIT Press.
• [18] Christopher K. I. Williams and Carl Edward Rasmussen. Gaussian processes for regression. In David S. Touretzky, Michael C. Mozer, and Michael E. Hasselmo, editors, Advances in Neural Information Processing Systems 8, pages 514–520, Cambridge, Massachussetts, 1996. The MIT Press.
• [19] Christopher K. I. Williams, Carl Edward Rasmussen, Anton Schwaighofer, and Volker Tresp. Observations of the Nystr ̈ om method for Gaussiam process prediction. Technical report, University of Edinburgh, Edinburgh, Scotland, 2002.
• [20] Christopher K. I. Williams and Mathias Seeger. Using the Nystr ̈ om method to speed up kernel machines. In Todd K. Leen, Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13, pages 682–688, Cambridge, Massachussetts, 2001. The MIT Press.
• [21] David Wipf, Jason Palmer, and Bhaskar Rao. Perspectives on sparse Bayesian learning. In Sebastian Thrun, Lawrence Saul, and Bernhard Sch ̈ olkopf, editors, Advances in Neural Information Processing Systems 16, Cambridge, Massachussetts, 2004. The MIT Press.