仿射追踪:概率线性求解器的新范式
Affine Tracing: A New Paradigm for Probabilistic Linear Solvers
Disha Hegde, Marvin Pförtner, Jon Cockayne
AI 速读 基于摘要
作者提出仿射追踪框架,可从经典仿射迭代法的标准实现自动构造概率迭代方法(PIM),并论证贝叶斯概率线性求解器是仿射PIM的特例。
stat.ML · cs.LG · math.NA
查看原文摘要
Probabilistic linear solvers (PLSs) return probability distributions that quantify uncertainty due to limited computation in the solution of linear systems. The literature has traditionally distinguished between Bayesian PLSs, which condition a prior on information obtained from projections of the linear system, and probabilistic iterative methods (PIMs), which lift classical iterative solvers to probability space. In this work we show this dichotomy to be false: Bayesian PLSs are a special case of non-stationary affine PIMs. In addition, we prove that any realistic affine PIM is calibrated. These results motivate a focus on (non-stationary) affine PIMs, but their practical adoption has been limited by the significant manual effort required to implement them. To address this, we introduce affine tracing, an algorithmic framework that automatically constructs a PIM from a standard implementation of an affine iterative method by passing symbolic tracers through the computation to build an affine computational graph. We show how this graph can be transformed to compute posterior covariances, and how equality saturation can be used to perform algebraic simplifications required for computation under specific prior choices. We demonstrate the framework by automatically generating a probabilistic multigrid solver and evaluate its performance in the context of Gaussian process approximation.