Thread by @maosbot

What is Probabilistic Numerics (PN)? To illustrate, take one core use case of PN— computing integrals. Most integrals are intractable (life is hard), so we must often integrate numerically. Sadly, numerical integrators are unreliable & computationally expensive.

PN can help! 🧵

Consider

F = ∫_{-3}^{3} f(x) dx
f(x) = exp(-(sin 3x)^2 - x^2)

The integrand f(x) here is simple—~20 characters, only atomic functions, can be evaluated in nanoseconds. However—the integral F is intractable! Let's try to calculate F numerically using PN.

The central idea of Probabilistic Numerics is to treat a numerical method as a *learning machine*. What about when the numerical method is an integrator? Well, a learning machine

• receives data,

• predicts and then

• takes actions.

QUIZ: in numerical integration,

• data = ?

• quantity of interest (the thing we want to predict) = ?

• actions = ?

Answers in two tweets' time!

No peeking!

ANSWERS:

Probabilistic Numerics views integration as:

• data = evaluations (also known as samples), f(x_i)

• quantity of interest = integral, F

• actions = choices of evaluation locations, x_i.

What does the learning machine use to turn data into predictions & actions? A model! A Probabilistic Numerical Method is (partly) defined by the choice of that model. The PN approach to integration is known as Bayesian quadrature, and often uses a Gaussian process (GP) model.

Why a GP?

1. We must choose evaluation locations, x_i. A GP, p(f(x)), gives trustworthy uncertainty (error-bars) for f(x_i)—we can trust the GP on which x_i to evaluate so as to best reduce uncertainty. Such evaluations are informative—giving high efficiency, low compute cost.

Why a GP?

2. A GP on the integrand, p(f(x)), leads to a neat one-d Gaussian, p(F), for the integral, F, 😎. p(F) gives not just an estimate, hat{F}, for F—it also tells us if/how that estimate is *trustworthy*. We get reliable error-bars for the integral!

Why a GP?

3. There exist other stochastic processes that might give trustworthy p(f(x)) and p(F)—at the cost of introducing additional, hard, numerical integration problems (a chicken/egg situation)! In contrast, a GP implementation requires (principally) only linear algebra.

But which GP? The beating heart of a GP is its covariance, k—different k's give different GPs, and hence different Bayesian quadrature (BQ) methods. PN is cool because it gives all the tools of Bayes (i.e. model selection) to help pick the k, and hence to pick the best BQ method.

Let's try one particular covariance, k = min(x, x') - χ. This k gives a GP model for f whose 'best guess', the expected value E[(f(x)], linearly interpolates between evaluations.

Does linear interpolation for numerical integration seem familiar? Well—do you remember the trapezoid rule? Used in ancient Babylon?

The trapezoid rule is just BQ with k=min(x,x')-χ!

The code for BQ with k=min(x,x')-χ IS IDENTICAL to the code for the trapezoid rule! 🎉

But we can do A LOT better than the trapezoid rule—by choosing a k that better fits f(x), e.g. a k that correctly assumes that f(x) is smooth. BQ with such a k (e.g. a k that reproduces Gauss-Legendre integration) is MUCH faster—with error that converges superpolynomially.

Notice that Monte Carlo integration… didn't do so well? Guess what: Monte Carlo is ALSO BQ, with a k that assumes that f(x) is constant plus noise. This assumption is false for our smooth f(x)—and so Monte Carlo converges slowly. Assuming that f(x) is noise is fairly odd!

Many different k's are possible! Almost anything that is known about the integrand can be baked into a k—the more we correctly assume, the faster our method. And it is possible to know a lot about the integrand: we usually have full access to the integrand's source code.

So, PN (in the form of BQ) can give integrators that are more

* Reliable—BQ gives error bars on F, quantifying reliability.
* Computationally cheap—via allowing better models, and via allowing efficient selection of evaluations, BQ can give very fast convergence.

Thanks for reading! This thread was drawn from our new book, #PNbook (with @PhilippHennig5 and @HansKersting)—check it out at the links below.

• retail: amazon.de/dp/1107163447
• CUP: cambridge.org/9781107163447
• free pdf: probabilistic-numerics.org/textbooks

Please share the word on PN 🚀

https://twitter.com/maosbot/status/1542574786273955840