Probabilistic numerics
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Probabilistic numerics is an active field of study at the intersection of applied mathematics, statistics, and machine learning centering on the concept of uncertainty in computation. In probabilistic numerics, tasks in numerical analysis such as finding numerical solutions for integration, linear algebra, optimization and simulation and differential equations are seen as problems of statistical, probabilistic, or Bayesian inference.
Probabilistic numerics is an active field of study at the intersection of applied mathematics, statistics, and machine learning centering on the concept of uncertainty in computation. In probabilistic numerics, tasks in numerical analysis such as finding numerical solutions for integration, linear algebra, optimization and simulation and differential equations are seen as problems of statistical, probabilistic, or Bayesian inference.
In this setting, the optimization objective is often an empirical risk of the form \textstyle L(\theta) = \frac{1}{N}\sum_{n=1}^N \ell(y_n, f_{\theta}(x_n)) defined by a dataset \textstyle \mathcal{D}=\{(x_n, y_n)\}_{n=1}^N , and a loss \ell(y, f_{\theta}(x)) that quantifies how well a predictive model f_{\theta}(x) parameterized by \theta performs on predicting the target y from its corresponding input x .
Epistemic uncertainty arises when the dataset size N is large and cannot be processed at once meaning that local quantities (given some \theta ) such as the loss function L(\theta) itself or its gradient \nabla L(\theta) cannot be computed in reasonable time. Hence, generally mini-batching is used to construct estimators of these quantities on a random subset of the data.
Probabilistic numerical methods model this uncertainty explicitly and allow for automated decisions and parameter tuning. have primarily focused on solving systems of linear equations of the form Ax=b and the computation of determinants |A| . A large class of methods are iterative in nature and collect information about the linear system to be solved via repeated matrix-vector multiplication v \mapsto Av with the system matrix A with different vectors v .
Such methods can be roughly split into a solution- and a matrix-based perspective, depending on whether belief is expressed over the solution x of the linear system or the (pseudo-)inverse of the matrix H=A^{\dagger} . The belief update uses that the inferred object is linked to matrix multiplications y= Av or z=A^\intercal v via b^\intercal z = x^\intercal v and v = A^{-1} y . Methods typically assume a Gaussian distribution, due to its closedness under linear observations of the problem.
While conceptually different, these two views are computationally equivalent and inherently connected via the right-hand-side through x = A^{-1}b . Probabilistic numerical linear algebra routines have been successfully applied to scale Gaussian processes to large datasets. In particular, they enable exact propagation of the approximation error to a combined Gaussian process posterior, which quantifies the uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
Probabilistic numerical methods for ordinary differential equations \dot{y}(t) = f(t, y(t)) , have been developed for initial and boundary value problems. Many different probabilistic numerical methods designed for ordinary differential equations have been proposed, and these can broadly be grouped into the two following categories: Randomisation-based methods are defined through random perturbations of standard deterministic numerical methods for ordinary differential equations.
For example, this has been achieved by adding Gaussian perturbations on the solution of one-step integrators or by perturbing randomly their time-step. This defines a probability measure on the solution of the differential equation that can be sampled. Gaussian process regression methods are based on posing the problem of solving the differential equation at hand as a Gaussian process regression problem, interpreting evaluations of the right-hand side as data on the derivative.
These techniques resemble to Bayesian cubature, but employ different and often non-linear observation models. In its infancy, this class of methods was based on naive Gaussian process regression. This was later improved (in terms of efficient computation) in favor of Gauss Markov priors modeled by the stochastic differential equation \mathrm{d}x(t) = A x(t) \, \mathrm{d} t + B \, \mathrm{d}v(t) , where x(t) is a \nu -dimensional vector modeling the first \nu derivatives of y(t) , and where v(t) is a \nu -dimensional Brownian motion.
Inference can thus be implemented efficiently with Kalman filtering based methods. These methods are known as ODE filters. The boundary between these two categories is not sharp, indeed a Gaussian process regression approach based on randomised data was developed as well. These methods have been applied to problems in computational Riemannian geometry, inverse problems, latent force models, and to differential equations with a geometric structure such as symplecticity.
In modern terminology, Poincaré considered a Gaussian prior distribution on a function f \colon \mathbb{R} \to \mathbb{R} , expressed as a formal power series with random coefficients, and asked for "probable values" of f(x) given this prior and n \in \mathbb{N} observations f(a_{i}) = B_{i} for i = 1, \dots, n . A later seminal contribution to the interplay of numerical analysis and probability was provided by Albert Suldin in the context of univariate quadrature.
The statistical problem considered by Suldin was the approximation of the definite integral \textstyle \int u(t) \, \mathrm{d} t of a function u \colon [a, b] \to \mathbb{R} , under a Brownian motion prior on u , given access to pointwise evaluation of u at nodes t_{1}, \dots, t_{n} \in [a, b] . Suldin showed that, for given quadrature nodes, the quadrature rule with minimal mean squared error is the trapezoidal rule; furthermore, this minimal error is proportional to the sum of cubes of the inter-node spacings.
As a result, one can see the trapezoidal rule with equally-spaced nodes as statistically optimal in some sense — an early example of the average-case analysis of a numerical method. Suldin's point of view was later extended by Mike Larkin. Note that Suldin's Brownian motion prior on the integrand u is a Gaussian measure and that the operations of integration and of point wise evaluation of u are both linear maps. Thus, the definite integral \textstyle \int u(t) \, \mathrm{d} t is a real-valued Gaussian random variable.
In particular, after conditioning on the observed pointwise values of u , it follows a normal distribution with mean equal to the trapezoidal rule and variance equal to \textstyle \frac{1}{12} \sum_{i = 2}^{n} (t_{i} - t_{i - 1})^{3} . This viewpoint is very close to that of Bayesian quadrature, seeing the output of a quadrature method not just as a point estimate but as a probability distribution in its own right.
As noted by Houman Owhadi and collaborators, interplays between numerical approximation and statistical inference can also be traced back to Palasti and Renyi, Sard, Kimeldorf and Wahba (on the correspondence between Bayesian estimation and spline smoothing/interpolation) and Larkin (on the correspondence between Gaussian process regression and numerical approximation).
Although the approach of modelling a perfectly known function as a sample from a random process may seem counterintuitive, a natural framework for understanding it can be found in information-based complexity (IBC), the branch of computational complexity founded on the observation that numerical implementation requires computation with partial information and limited resources.
In IBC, the performance of an algorithm operating on incomplete information can be analyzed in the worst-case or the average-case (randomized) setting with respect to the missing information. Moreover, as Packel observed, the average case setting could be interpreted as a mixed strategy in an adversarial game obtained by lifting a (worst-case) minmax problem to a minmax problem over mixed (randomized) strategies.
This observation leads to a natural connection between numerical approximation and Wald's decision theory, evidently influenced by von Neumann's theory of games. To describe this connection consider the optimal recovery setting of Micchelli and Rivlin in which one tries to approximate an unknown function from a finite number of linear measurements on that function.
Interpreting this optimal recovery problem as a zero-sum game where Player I selects the unknown function and Player II selects its approximation, and using relative errors in a quadratic norm to define losses, Gaussian priors emerge as optimal mixed strategies for such games, and the covariance operator of the optimal Gaussian prior is determined by the quadratic norm used to define the relative error of the recovery.
See also
Average-case analysis Information-based complexity Uncertainty quantification
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369996234 under CC BY-SA 4.0; modifications have been made.