Kernel-Based and Bayesian Methods for Numerical Integration
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering |
Doctoral thesis (article-based)
| Defence date: 2019-11-08
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2019
Major/Subject
Mcode
Degree programme
Language
en
Pages
90 + app. 98
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 160/2019
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.Description
Supervising professor
Särkkä, Simo, Prof., Aalto University, Department of Electrical Engineering and Automation, FinlandThesis advisor
Särkkä, Simo, Prof., Aalto University, Department of Electrical Engineering and Automation, FinlandKeywords
numerical integration, reproducing kernel Hilbert spaces, Gaussian processes, probabilistic numerics, numeerinen integrointi, reproduktiivisen ytimen Hilbertin avaruudet, gaussiset prosessit, probabilistinen numeriikka
Other note
Parts
-
[Publication 1]: Toni Karvonen, Simo Särkkä. Fully symmetric kernel quadrature. SIAM Journal on Scientific Computing, 40(2):A697–A720, 2018.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201806183337DOI: 10.1137/17M1121779 View at publisher
-
[Publication 2]: Toni Karvonen, Simo Särkkä, Chris J. Oates. Symmetry exploits for Bayesian cubature methods. Accepted for publication in Statistics and Computing, 2019.
DOI: 10.1007/s11222-019-09896-8 View at publisher
-
[Publication 3]: Toni Karvonen, Simo Särkkä. Gaussian kernel quadrature at scaled Gauss–Hermite nodes. BIT Numerical Mathematics, 2019.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201908154801DOI: 10.1007/s10543-019-00758-3 View at publisher
- [Publication 4]: Toni Karvonen, Chris J. Oates, Simo Särkkä. A Bayes–Sard cubature method. In Advances in Neural Information Processing Systems 31 (NeurIPS 2018), pp. 5882–5893.
-
[Publication 5]: Toni Karvonen, Simo Särkkä. Classical quadrature rules via Gaussian processes. In 27th IEEE International Conference on Machine Learning for Signal Processing, Tokyo, Japan, 2017.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201803161723DOI: 10.1109/MLSP.2017.8168195 View at publisher