Skip to main content
To KTH's start page To KTH's start page

Breaking the Dimensionality Curse of Voronoi Tessellations

Time: Mon 2022-11-07 15.00

Location: F3 Lindstedtsvagen 26

Video link:

Language: English

Subject area: Computer Science

Doctoral student: Vladislav Polianskii , Robotik, perception och lärande, RPL

Opponent: Professor Michael Bronstein, University of Oxford, Oxford, United Kingdom

Supervisor: Florian T. Pokorny, Robotik, perception och lärande, RPL

Export to calendar

QC 20221017


Considering the broadness of the area of artificial intelligence, interpretations of the underlying methodologies can be commonly narrowed down to either a probabilistic or a geometric point of view. Such separation is especially prevalent in more classical "pre-neural-network" machine learning if one compares Bayesian modelling with more deterministic models like nearest neighbors.

The research conducted in the dissertation is based on the study and development of geometrically-founded methodologies, carried from the areas of computational topology and geometry, applied to machine learning tasks. The work is tied together with the analysis of natural data space neighborhood partitions known as Voronoi tessellations, as well as their dual Delaunay tessellations. One of the fundamental issues that arise when working with these constructs is their overwhelmingly high geometric complexity in high dimensions so abundant in modern machine learning tasks. We present a class of techniques designed to alleviate these constraints and allow us to work with Voronoi tessellations implicitly in arbitrary dimensions without their explicit construction. The techniques are based on a ray casting procedure, a widespread methodology taking root in areas of stochastic geometry and computer graphics. We present applications of such decompositions to common machine learning problems, such as classification, density estimation and active interpolation, review the methods of Delaunay graph approximation and include a more general discussion on the topic of the high-dimensional geometric analysis.