Kernel-Based and Bayesian Methods for Numerical Integration

Abstract

Kernel-based methods provide a flexible toolkit for approximation of linear functionals. Importantly, these methods carry a probabilistic interpretation: a worst-case optimal method in the reproducing kernel Hilbert space induced by the kernel being used can be equivalently formulated as the posterior mean of a Gaussian process (GP) with the same covariance kernel; the worst-case error corresponds to the GP posterior standard deviation. This connection makes it possible to speak of and quantify, in a statistically principled way, uncertainty in the approximation provided by a kernel method. Consequently, these methods can be viewed as probabilistic numerical methods that interpret numerical approximation as a statistical inference problem and attempt to endow the solution of a numerical problem with a full non-degenerate posterior probability distribution. Unfortunately, both the kernel and GP formulations suffer from cubic computational and quadratic memory cost in the number of data points. Furthermore, because standard versions of kernel-based methods do not typically coincide with any ''classical'' method of numerical analysis in a way that would give rise to a corresponding non-degenerate GP posterior (with the exception of spline methods), there has been no straightforward way to interpret classical methods as useful statistical inference procedures within the GP framework. This thesis studies numerical approximation of analytically intractable integrals by the means of kernel and Bayesian cubature rules, the former worst-case optimal cubature methods and the latter posteriors of GPs. The first contribution is the development of algorithms that significantly reduce the computational cost of these cubature methods by employing point sets that can be expressed as unions of fully symmetric sets. The resulting algorithm is non-approximate, computationally competitive and scalable, flexible, and algorithmically simple, enabling application of kernel and Bayesian cubature rules to integration problems involving up to millions of points. Additionally, a closed-form approximation linked to the Gauss–Hermite quadrature is proposed for the special case of one-dimensional integration against the standard Gaussian measure. The second main contribution is the study of different kernels and GP modelling choices that yield Bayesian cubature rules corresponding to classical cubature methods, such as Gaussian cubatures and uniformly weighted Monte Carlo rules. The proposed Bayes–Sard framework is general and capable of probabilistic reproduction of virtually any cubature rule.

Ydinperusteiset menetelmät ovat joustava joukko lineaarifunktioiden approksimointia varten kehitettyjä algoritmeja. Mikä tärkeintä, näillä menetelmillä on todennäköisyysteoreettinen tulkinta: menetelmä, joka on pahimmassa tapauksessa optimaalinen reproduktiivisen ytimen Hilbertin avaruudessa, on mahdollista ilmaista täysin ekvivalentista gaussisen prosessin posteriorikeskiarvona ja sen pahimman tapauksen virhe vastaavana posteriorikeskihajontana. Tämä yhteys mahdollistaa ydinmenetelmän tuottaman approksimaation epävarmuudesta puhumisen ja mallintamisen tilastollisesti merkityksellisesti. Täten ydinmenetelmät voi nähdä probabilistisina numeerisina menetelminä, jotka käsittelevät numeerista approksimaatiota tilastollisena päättelynä ja pyrkivät varustamaan ongelman ratkaisun epädegeneroituneella posterioritodennäköisyysjakaumalla. Sekä ytimiin että gaussisiin prosesseihin perustuvat approksimaatiomenetelmät kärsivät kuutiollisesta aika- ja neliöllisestä tilavaativuudesta. Ydinperusteiset menetelmät eivät myöskään tavanomaisessa muodossaan tyypillisesti samanaikaisesti vastaa ''klassisia'' numeerisen analyysin menetelmiä ja epädegeneroituneita gaussisten prosessien posteriorijakaumia (splinimenetelmiä lukuunottamatta), joten klassisia menetelmiä ei ole ollut mahdollista tulkita hyödyllisinä tilastollisen päättelyn menetelminä gaussisia prosesseja käyttäen. Tämä väitöskirja tutkii suljettua muotoa vailla olevien integraalien approksimointia käyttäen ydinperusteisia ja bayesilaisia kubatuurisääntöjä, joista edelliset ovat pahimmassa tapauksessa optimaalisia ja jälkimmäiset gaussisten prosessien posteriorijakaumia. Väitöskirjan ensimmäinen kontribuutio on laskennallisesti tehokkaiden algoritmien kehittäminen näitä kubatuurimenetelmiä varten käyttäen pistejoukkoja, jotka ovat täysin symmetristen pistejoukkojen yhdisteitä. Näin kehitetty algoritmi ei hyödynnä approksimaatioita, on laskennallisesti kilpailukykyinen, skaalautuva, joustava ja toteutukseltaan yksinkertainen, mahdollistaen ydinperusteisten ja bayesilaisten kubatuurimenetelmien soveltamisen integrointiongelmiin, joissa on käytettävä jopa miljoonia datapisteitä. Lisäki yksiulotteiseen integrointiin gaussisen mitan suhteen kehitetään erilainen suljetussa muodossa ilmaistavissa oleva approksimaatio, joka perustuu Gaussin–Hermiten kvadratuuriin. Väitöskirjan toinen pääkontribuutio liittyy erilaisten ydinten ja gaussisten prosessimallien käyttöön klassisten kubatuurisääntöjen, kuten Gaussin kubatuurien ja Monte Carlo -sääntöjen, tulkitsemisessa bayesilaisina kubatuurisääntöinä. Väitöskirjassa tätä varten kehitetyllä Bayesin–Sardin menetelmällä voi tulkita probabilistisesti lähes minkä tahansa kubatuurisäännön.