NO.25.tip： 诱导点近似

背景

高斯过程的主要缺点是，对 $N\times N$ 核矩阵求逆所需的时间复杂度为 $O(N^3)$，这使得该方法对于大数据集来说太过缓慢。研究学者已经提出了许多不同的近似方案来加速高斯过程。

稀疏近似又称为诱导点近似。加速高斯过程推理的一个简单方法是使用更少的数据。一种更好的方法是尝试将 $N$ 个训练点 $\mathbf{X}$ "汇总"为 $M\ll N$ 个诱导点（inducing point）或伪输入（pseudo input）$\mathbf{Z}$。这允许我们使用 $p(\mathbf{f}\mid {\mathbf{f}}_{\mathbf{X}})$ 来代替 $p(\mathbf{f}\mid {\mathbf{f}}_{\mathbf{Z}})$，其中 ${\mathbf{f}}_{\mathbf{X}}=\{f(\mathbf{x}):\mathbf{x}\in \mathbf{X}\}$ 是在训练点观察到的函数值的向量，${\mathbf{f}}_{\mathbf{Z}}=\{f(\mathbf{x}):\mathbf{x}\in \mathbf{Z}\}$ 是在诱导点估计的函数值。通过优化 $(\mathbf{Z},{\mathbf{f}}_{\mathbf{Z}})$，我们可以学会将训练数据 $(\mathbf{X},{\mathbf{f}}_{\mathbf{X}})$ "压缩"为"瓶颈" $(\mathbf{Z},{\mathbf{f}}_{\mathbf{Z}})$，从而加快计算，将时间复杂度从 $O(N^3)$ 降低到 $O(M^3)$。这被称为稀疏高斯过程（sparse GP）。使用变分推理的框架可以使整个过程变得严谨。

源与流

我们讨论了一种基于诱导点（inducing point）的近似方法，也称为伪输入（pseudoinput），这种方法就像是我们可以条件化地训练数据的学习总结，而不是对全部数据条件化。

设 $\mathbf{X}$ 是观测到的输入，$f_{\mathbf{X}}=f(\mathbf{X})$ 是函数值的未知向量（假设存在噪声观测 $\mathbf{y}$）。设 $f_{\ast }$ 为一个或多个测试点 ${\mathbf{X}}_{\ast }$ 处的未知函数值。最后，假设我们有 $M$ 个额外的输入 $\mathbf{Z}$，其对应的未知函数值为 $f_{\mathbf{Z}}$（通常用 $\mathbf{u}$ 表示）。精确的联合先验具有以下形式：

$$p(f_{\mathbf{X}},f_{\ast })=\int p(f_{\ast },f_{\mathbf{X}},f_{\mathbf{Z}})\mathrm{d}{f}_{\mathbf{Z}}=\int p(f_{\ast },f_{\mathbf{X}}\mid f_{\mathbf{Z}})p(f_{\mathbf{Z}})\mathrm{d}{f}_{\mathbf{Z}}=\mathcal{N}\left(0,\left(\begin{array}{cc}{\mathbf{K}}_{\mathbf{x},\mathbf{x}}& {\mathbf{K}}_{\mathbf{x},\ast }\\ {\mathbf{K}}_{\ast ,\mathbf{x}}& {\mathbf{K}}_{\ast ,\ast }\end{array}\right)\right)\text{\hspace{1em}(1)}$$

（我们记作 $p(f_{\mathbf{X}},f_{\ast })$ 而不是 $p(f_{\mathbf{X}},f_{\ast }\mid \mathbf{X},{\mathbf{X}}_{\ast })$，因为输入可以被认为只是随机函数 $f$ 的索引。）

我们将以这样一种方式选择 $f_{\mathbf{Z}}$，即将该值作为数据的重复统计量，这样我们就可以仅使用 $f_{\mathbf{Z}}$ 而不是 $f_{\mathbf{X}}$ 来预测 $f_{\ast }$，即，我们假设 $f_{\ast }\perp f_{\mathbf{X}}\mid f_{\mathbf{Z}}$。因此，我们将先验近似如下：

$$p(f_{\ast },f_{\mathbf{X}},f_{\mathbf{Z}})=p(f_{\ast }\mid f_{\mathbf{X}},f_{\mathbf{Z}})p(f_{\mathbf{X}}\mid f_{\mathbf{Z}})p(f_{\mathbf{Z}})\approx p(f_{\ast }\mid f_{\mathbf{Z}})p(f_{\mathbf{X}}\mid f_{\mathbf{Z}})p(f_{\mathbf{Z}})\text{\hspace{1em}(2)}$$

注意，这种方法通常被称为稀疏高斯过程，因为该方法使用训练数据的一个子集 $f_{\mathbf{Z}}$，而不是全部数据 $f_{\mathbf{X}}$ 来预测 $f_{\ast }$。

由此，我们可以推导出以下训练和测试条件：

$$p(f_X\mid f_Z)=\mathcal{N}(f_X\mid {\mathbf{K}}_{X,Z}{\mathbf{K}}_{Z,Z}^{-1}{f}_Z,{\mathbf{K}}_{X,X}-{\mathbf{Q}}_{X,X})\text{\hspace{1em}(3)}$$

$$p(f_{\ast }\mid f_Z)=\mathcal{N}(f_{\ast }\mid {\mathbf{K}}_{\ast ,Z}{\mathbf{K}}_{Z,Z}^{-1}{f}_Z,{\mathbf{K}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,\ast })\text{\hspace{1em}(4)}$$

上述公式可以看作是对无噪声观测 $f_Z$ 的精确推理。为了提高计算速度，我们将对 ${\tilde{\mathbf{Q}}}_{X,X}={\mathbf{K}}_{X,X}-{\mathbf{Q}}_{X,X}$ 和 ${\tilde{\mathbf{Q}}}_{\ast ,\ast }={\mathbf{K}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,\ast }$ 做进一步的近似，如下所述。然后，我们可以推导出近似先验 $q(f_X,f_{\ast })=\int q(f_X\mid f_Z)q(f_{\ast }\mid f_Z)p(f_Z)\mathrm{d}{f}_Z$，并以通常的方式将其作为观测的条件。

我们下面讨论的所有近似都会产生 $O(M^3+N{M}^2)$ 的初始训练成本，然后每个测试用例的预测均值都会花费 $O(M)$ 的时间，预测方差会花费 $O(M^2)$ 的时间。（将其与训练时间 $O(N^3)$ 以及测试时间 $O(N)$ 和 $O(N^2)$ 进行比较，以进行精确推断。）

SOR/DIC

假定我们假设 ${\tilde{\mathbf{Q}}}_{X,X}=0$ 和 ${\tilde{\mathbf{Q}}}_{\ast ,\ast }=0$，从而使得条件是确定性的。这被称为确定性诱导条件（Deterministic Inducing Conditional，DIC）近似，或回归子集（Subset Of Regressors，SOR）近似。相应的联合先验具有以下形式：

$$q_{\mathrm{SOR}}(f_X,f_{\ast })=\mathcal{N}\left(0,\left(\begin{array}{cc}{\mathbf{Q}}_{X,X}& {\mathbf{Q}}_{X,\ast }\\ {\mathbf{Q}}_{\ast ,X}& {\mathbf{Q}}_{\ast ,\ast }\end{array}\right)\right)\text{\hspace{1em}(5)}$$

让我们定义 ${\hat{\mathbf{Q}}}_{X,X}={\mathbf{Q}}_{X,X}+{\sigma }^2{\mathbf{I}}_N$，以及 $\mathbf{\Sigma }\triangleq ({\sigma }^{-2}{\mathbf{K}}_{Z,X}{\mathbf{K}}_{X,Z}+{\mathbf{K}}_{Z,Z}{)}^{-1}$，那么预测分布为：

$$q_{\mathrm{SOR}}(f_{\ast }\mid \mathbf{y})=\mathcal{N}(f_{\ast }\mid {\mathbf{Q}}_{\ast ,X}{\hat{\mathbf{Q}}}_{X,X}^{-1}\mathbf{y},{\mathbf{Q}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,X}{\hat{\mathbf{Q}}}_{X,X}^{-1}{\mathbf{Q}}_{X,\ast })\text{\hspace{1em}(6)}$$

$$q_{\mathrm{SOR}}(f_{\ast }\mid \mathbf{y})=\mathcal{N}(f_{\ast }\mid {\sigma }^{-2}{\mathbf{K}}_{\ast ,Z}\mathbf{\Sigma }{\mathbf{K}}_{Z,X}\mathbf{y},{\mathbf{K}}_{\ast ,Z}\mathbf{\Sigma }{\mathbf{K}}_{Z,\ast })\text{\hspace{1em}(7)}$$

这等价于高斯过程的一般情况，除了我们将 ${\mathbf{K}}_{X,X}$ 替换为 ${\mathbf{Q}}_{X,X}$。这相当于使用以下核函数执行高斯过程推理：

$${\mathcal{K}}_{\mathrm{SOR}}({\mathbf{x}}_i,{\mathbf{x}}_j)=\mathcal{K}({\mathbf{x}}_i,\mathbf{Z}){\mathbf{K}}_{Z,Z}^{-1}\mathcal{K}(\mathbf{Z},{\mathbf{x}}_j)\text{\hspace{1em}(8)}$$

核矩阵的秩为 $M$，因此高斯过程是退化的。此外，当 ${\mathbf{x}}_i$ 或 ${\mathbf{x}}_j$ 远离所选点 $\mathbf{Z}$ 之一时，核将接近 $0$，这可能导致预测方差的值被低估。

DTC

克服确定性诱导条件近似过度自信的一种方法是只假设 ${\tilde{\mathbf{Q}}}_{X,X}=0$，并设 ${\tilde{\mathbf{Q}}}_{\ast ,\ast }={\mathbf{K}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,\ast }$ 为精确值。这被称为确定性训练条件（Deterministic Training Conditional，DTC）方法。

相应的联合先验具有以下形式：

$$q_{\mathrm{dtc}}(f_X,f_{\ast })=\mathcal{N}\left(0,\left(\begin{array}{cc}{\mathbf{Q}}_{X,X}& {\mathbf{Q}}_{X,\ast }\\ {\mathbf{Q}}_{\ast ,X}& {\mathbf{K}}_{\ast ,\ast }\end{array}\right)\right)\text{\hspace{1em}(9)}$$

因此，预测分布变成

$$q_{\mathrm{dtc}}(f_{\ast }\mid \mathbf{y})=\mathcal{N}(f_{\ast }\mid {\mathbf{Q}}_{\ast ,X}{\hat{\mathbf{Q}}}_{X,X}^{-1}\mathbf{y},{\mathbf{K}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,X}{\hat{\mathbf{Q}}}_{X,X}^{-1}{\mathbf{Q}}_{X,\ast })\text{\hspace{1em}(10)}$$

$$q_{\mathrm{dtc}}(f_{\ast }\mid \mathbf{y})=\mathcal{N}(f_{\ast }\mid {\sigma }^{-2}{\mathbf{K}}_{\ast ,Z}\mathbf{\Sigma }{\mathbf{K}}_{Z,X}\mathbf{y},{\mathbf{K}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,\ast }+{\mathbf{K}}_{\ast ,Z}\mathbf{\Sigma }{\mathbf{K}}_{Z,\ast })\text{\hspace{1em}(11)}$$

预测均值与回归子集中的相同，但由于给定 $f_Z$ 的 $f_{\ast }$ 的不确定性，方差较大（因为 ${\mathbf{K}}_{\ast ,\ast }-{\mathbf{Q}}_{\ast ,\ast }$ 是正定的）。

FITC

一种广泛使用的近似假设 $q(f_X\mid f_Z)$ 是完全因子化的，即

$$q(f_X\mid f_Z)=\prod _{n=1}^{N}p(f_n\mid f_Z)=\mathcal{N}(f_X\mid {\mathbf{K}}_{X,Z}{\mathbf{K}}_{Z,Z}^{-1}{f}_Z,\mathrm{diag}({\mathbf{K}}_{X,X}-{\mathbf{Q}}_{X,X}))\text{\hspace{1em}(12)}$$

这被称为完全独立的训练条件（Fully Independent Training Conditional，FITC）假设。与回归子集方法和确定性训练条件方法相比，该方法减少了不确定性，因为它没有对 $f_X$ 和 $f_Z$ 之间的关系做出任何确定性假设。

其联合先验具有以下形式：

$$q_{\mathrm{fitc}}(f_X,f_{\ast })=\mathcal{N}\left(0,\left(\begin{array}{cc}{\mathbf{Q}}_{X,X}-\mathrm{diag}({\mathbf{Q}}_{X,X}-{\mathbf{K}}_{X,X})& {\mathbf{Q}}_{X,\ast }\\ {\mathbf{Q}}_{\ast ,X}& {\mathbf{K}}_{\ast ,\ast }\end{array}\right)\right)\text{\hspace{1em}(13)}$$

单个测试用例的预测分布由下式给出：

$$q_{\mathrm{fitc}}(f_{\ast }\mid \mathbf{y})=\mathcal{N}(f_{\ast }\mid {\mathbf{k}}_{\ast ,Z}\mathbf{\Sigma }{\mathbf{K}}_{Z,X}{\mathbf{\Lambda }}^{-1}\mathbf{y},k_{\ast ,\ast }-q_{\ast ,\ast }+{\mathbf{k}}_{\ast ,Z}\mathbf{\Sigma }{\mathbf{k}}_{Z,\ast })\text{\hspace{1em}(14)}$$

其中，$\mathbf{\Lambda }\triangleq \mathrm{diag}({\mathbf{K}}_{X,X}-{\mathbf{Q}}_{X,X}+{\sigma }^2{\mathbf{I}}_N)$，$\mathbf{\Sigma }\triangleq ({\mathbf{K}}_{Z,Z}+{\mathbf{K}}_{Z,X}{\mathbf{\Lambda }}^{-1}{\mathbf{K}}_{X,Z}{)}^{-1}$。如果我们有一批测试用例，那么我们可以假设这些测试用例是条件独立的（一种称为完全独立条件（Fully Independent Conditional，FIC）的方法），并对上述公式进行相乘运算。

计算成本与回归子集以及确定性训练条件方法相同，但由于非退化核，该方法避免了一些弊端。特别地，可以证明完全独立条件方法等价于具有以下非退化核的精确高斯过程推理：

$${\mathcal{K}}_{\mathrm{fitc}}({\mathbf{x}}_i,{\mathbf{x}}_j)=\{\begin{array}{ll}\mathcal{K}({\mathbf{x}}_i,{\mathbf{x}}_j)& \text{如果 }i=j\\ {\mathcal{K}}_{\mathrm{SOR}}({\mathbf{x}}_i,{\mathbf{x}}_j)& \text{如果 }i\ne j\end{array}\text{\hspace{1em}(15)}$$

学习诱导点

到目前为止，我们还没有指定如何选择诱导点或伪输入 $\mathbf{Z}$。我们可以像处理核超参数一样处理这些参数，即选择这些参数以最大化对数边缘似然，如下所示：

$$\log q(\mathbf{y}\mid \mathbf{X},\mathbf{Z})=\log \iint p(\mathbf{y}\mid f_X)q(f_X\mid \mathbf{X},f_Z)p(f_Z\mid \mathbf{Z})\mathrm{d}{f}_Z\mathrm{d}{f}_X\text{\hspace{1em}(16)}$$

$$\log q(\mathbf{y}\mid \mathbf{X},\mathbf{Z})=\log \int p(\mathbf{y}\mid f_X)q(f_X\mid \mathbf{X},\mathbf{Z})\mathrm{d}{f}_X\text{\hspace{1em}(17)}$$

$$\log q(\mathbf{y}\mid \mathbf{X},\mathbf{Z})=-\frac{1}{2}\log |{\mathbf{Q}}_{X,X}+\mathbf{\Lambda }|-\frac{1}{2}{\mathbf{y}}^{\mathsf{T}}({\mathbf{Q}}_{X,X}+\mathbf{\Lambda }{)}^{-1}\mathbf{y}-\frac{n}{2}\log (2\pi )\text{\hspace{1em}(18)}$$

其中，$\mathbf{\Lambda }$ 的定义取决于方法，即 ${\mathbf{\Lambda }}_{\mathrm{SOR}}={\mathbf{\Lambda }}_{\mathrm{dtc}}={\sigma }^2{\mathbf{I}}_N$，${\mathbf{\Lambda }}_{\mathrm{fitc}}=\mathrm{diag}({\mathbf{K}}_{X,X}-{\mathbf{Q}}_{X,X})+{\sigma }^2{\mathbf{I}}_N$。

如果输入域是 ${\mathbb{R}}^d$，我们可以使用梯度方法优化 $\mathbf{Z}\in {\mathbb{R}}^{Md}$。然而，核方法的吸引力之一是这些方法可以处理结构化输入。在这种情况下，我们不能使用梯度方法来选择诱导点。一种简单的方法是从训练集中选择诱导点，或者使用有效选择机制。然而，我们也可以使用离散优化方法。