高斯过程随输入维度D与输出维度M的缩放特性问询

已知单输出、低维输入下，高斯过程（GP）的核心复杂度由数据点数量N主导，为O(N³)（来自Cholesky分解等矩阵操作）。针对输入维度D和输出维度M的缩放规律，具体如下：

输入维度D的缩放特性 #

• 核矩阵计算成本：计算N×N的核矩阵时，每个元素的核函数运算（如RBF核、Matern核）需要遍历D维输入特征，单元素计算复杂度为O(D)，因此核矩阵的构建复杂度为O(N²D)。
• 整体复杂度主导：后续的Cholesky分解、预测等操作仍为O(N³)，因此当N较大时，O(N³)仍是主导复杂度；但D增大时，核矩阵构建的耗时会线性增加，成为次要但不可忽略的成本。
• 高维额外问题：D过大时会出现维数灾难，核函数对数据的拟合能力可能下降，通常需要结合特征选择、稀疏GP等方法缓解，但这属于算法优化范畴，而非基础复杂度缩放。

输出维度M的缩放特性 #

独立多输出GP（最常用场景） #

将M个输出视为独立任务，为每个输出单独训练一个GP，此时：

• 训练复杂度：O(M×N³)，每个输出单独执行一次完整的GP训练流程。
• 核矩阵计算：O(M×N²D)，每个输出需独立构建核矩阵（若输入共享则可复用，此时核矩阵计算成本仍为O(N²D)）。

关联多输出GP（考虑输出间相关性） #

若建模输出间的依赖关系（如使用线性模型核心LMC、卷积多输出GP等结构）：

• 基础复杂度：完整的协方差矩阵维度为MN×MN，因此Cholesky分解复杂度为O((MN)³)，这在M较大时成本极高。
• 优化后复杂度：通过低秩近似、分块矩阵操作等优化，可将复杂度降至O(M²×N³)（如LMC结构），部分高效架构甚至能接近O(M×N³)，具体取决于模型设计。

参考资料 #

• 《Gaussian Processes for Machine Learning》（Rasmussen & Williams）：机器学习领域GP的经典教材，第2章讲解基础GP计算复杂度，第5章深入分析多输出GP的缩放特性。
• 《Multi-Output Gaussian Processes》（Alvarez et al., 2012）：专门聚焦多输出GP的综述论文，详细对比不同架构的复杂度与性能。

内容的提问来源于stack exchange，提问作者uselessrunner