Hyperbolic machine learning is an emerging field aimed at representing data with a hierarchical structure. However, there is a lack of tools for evaluation and analysis of the resulting hyperbolic data representations. To this end, we propose Hyperbolic Delaunay Geometric Alignment (HyperDGA) - a similarity score for comparing datasets in a hyperbolic space. The core idea is counting the edges of the hyperbolic Delaunay graph connecting datapoints across the given sets. We provide an empirical investigation on synthetic and real-life biological data and demonstrate that HyperDGA outperforms the hyperbolic version of classical distances between sets. Furthermore, we showcase the potential of HyperDGA for evaluating latent representations inferred by a Hyperbolic Variational Auto-Encoder.

We introduce a non-parametric density estimator deemed Radial Voronoi Density Estimator (RVDE). RVDE is grounded in the geometry of Voronoi tessellations and as such benefits from local geometric adaptiveness and broad convergence properties. Due to its radial definition RVDE is continuous and computable in linear time with respect to the dataset size. This amends for the main shortcomings of previously studied VDEs, which are highly discontinuous and computationally expensive. We provide a theoretical study of the modes of RVDE as well as an empirical investigation of its performance on high-dimensional data. Results show that RVDE outperforms other non-parametric density estimators, including recently introduced VDEs.

Variational auto-encoders (VAEs) are deep generative models used for unsupervised learning, however their standard version is not topology-aware in practice since the data topology may not be taken into consideration. In this paper, we propose two different approaches with the aim to preserve the topological structure between the input space and the latent representation of a VAE. Firstly, we introduce InvMap-VAE as a way to turn any dimensionality reduction technique, given an embedding it produces, into a generative model within a VAE framework providing an inverse mapping into original space. Secondly, we propose the Witness Simplicial VAE as an extension of the simplicial auto-encoder to the variational setup using a witness complex for computing the simplicial regularization, and we motivate this method theoretically using tools from algebraic topology. The Witness Simplicial VAE is independent of any dimensionality reduction technique and together with its extension, Isolandmarks Witness Simplicial VAE, preserves the persistent Betti numbers of a dataset better than a standard VAE.

We introduce an algorithm for active function approximation based on nearest neighbor regression. Our Active Nearest Neighbor Regressor (ANNR) relies on the Voronoi-Delaunay framework from computational geometry to subdivide the space into cells with constant estimated function value and select novel query points in a way that takes the geometry of the function graph into account. We consider the recent state-of-the-art active function approximator called DEFER, which is based on incremental rectangular partitioning of the space, as the main baseline. The ANNR addresses a number of limitations that arise from the space subdivision strategy used in DEFER. We provide a computationally efficient implementation of our method, as well as theoretical halting guarantees. Empirical results show that ANNR outperforms the baseline for both closed-form functions and real-world examples, such as gravitational wave parameter inference and exploration of the latent space of a generative model.

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.

Med hänsyn till omfattningen av området artificiell intelligens kan indelningen av de underliggande metoderna ofta begränsas till antingen en probabilistisk eller en geometrisk synvinkel. En sådan uppdelning är särskilt utbredd inom mer klassisk maskininlärning, "före-neurala-nätverk", om man jämför Bayesiansk modellering med mer deterministiska modeller som k-närmste grannar.

Den forskning som bedrivs i avhandlingen bygger på studier och utveckling av geometriskt grundade metoder, hämtade från områdena beräkningstopologi och geometri, som tillämpas på maskininlärningsuppgifter. Arbetet knyts samman med analysen av naturliga grannskapspartitioner i datarummet som kallas Voronoi-tessellationer, liksom deras dubbla Delaunay-tessellationer. Ett grundläggande problem som uppstår när man arbetar med dessa konstruktioner är deras överväldigande höga geometriska komplexitet i höga dimensioner som är väldigt vanliga i moderna maskininlärningsuppgifter. Vi presenterar en grupp liknande tekniker som är utformade för att lindra dessa begränsningar och göra det möjligt att arbeta med Voronoi-tessellationer implicit i godtyckliga dimensioner utan att de konstrueras explicit. Teknikerna är baserade på ett strålkastningsförfarande, en utbredd metodik som har fått fäste inom områden som stokastisk geometri och datorgrafik. Vi presenterar tillämpningar av sådana dekompositioner på vanliga maskininlärningsproblem, t.ex. klassificering, täthetsuppskattning och aktiv interpolering. Vi går även igenom metoderna för approximation av Delaunay-grafer och för en mer allmän diskussion om ämnet högdimensionell geometrisk analys.

Advanced representation learning techniques require reliable and general evaluation methods. Recently, several algorithms based on the common idea of geometric and topological analysis of a manifold approximated from the learned data representations have been proposed. In this work, we introduce Delaunay Component Analysis (DCA) - an evaluation algorithm which approximates the data manifold using a more suitable neighbourhood graph called Delaunay graph. This provides a reliable manifold estimation even for challenging geometric arrangements of representations such as clusters with varying shape and density as well as outliers, which is where existing methods often fail. Furthermore, we exploit the nature of Delaunay graphs and introduce a framework for assessing the quality of individual novel data representations. We experimentally validate the proposed DCA method on representations obtained from neural networks trained with contrastive objective, supervised and generative models, and demonstrate various use cases of our extended single point evaluation framework.

The Voronoi Density Estimator (VDE) is an established density estimation technique that adapts to the local geometry of data. However, its applicability has been so far limited to problems in two and three dimensions. This is because Voronoi cells rapidly increase in complexity as dimensions grow, making the necessary explicit computations infeasible. We define a variant of the VDE deemed Compactified Voronoi Density Estimator (CVDE), suitable for higher dimensions. We propose computationally efficient algorithms for numerical approximation of the CVDE and formally prove convergence of the estimated density to the original one. We implement and empirically validate the CVDE through a comparison with the Kernel Density Estimator (KDE). Our results indicate that the CVDE outperforms the KDE on sound and image data.

Voronoi diagrams and their dual, the Delaunay complex, are two fundamental geometric concepts that lie at the foundation of many machine learning algorithms and play a role in particular in classical piecewise linear interpolation and regression methods. More recently, they are also crucial for the construction of a common class of simplicial complexes such as Alpha and Delaunay-\vC ech complexes in topological data analysis. We propose a randomized approximation approach that mitigates the prohibitive cost of exact computation of Voronoi diagrams in high dimensions for machine learning applications. In experiments with data in up to 50 dimensions, we show that this allows us to significantly extend the use of Voronoi-based simplicial complexes in Topological Data Analysis (TDA) to higher dimensions. We confirm prior TDA results on image patches that previously had to rely on sub-sampled data with increased resolution and demonstrate the scalability of our approach by performing a TDA analysis on synthetic data as well as on filters of a ResNet neural network architecture. Secondly, we propose an application of our approach to piecewise linear interpolation of high dimensional data that avoids explicit complete computation of an associated Delaunay triangulation. 

Voronoi cell decompositions provide a classical avenue to classification. Typical approaches however only utilize point-wise cell-membership information by means of nearest neighbor queries and do not utilize further geometric information about Voronoi cells since the computation of Voronoi diagrams is prohibitively expensive in high dimensions. We propose a Monte-Carlo integration based approach that instead computes a weighted integral over the boundaries of Voronoi cells, thus incorporating additional information about the Voronoi cell structure. We demonstrate the scalability of our approach in up to 3072 dimensional spaces and analyze convergence based on the number of Monte Carlo samples and choice of weight functions. Experiments comparing our approach to Nearest Neighbors, SVM and Random Forests indicate that while our approach performs similarly to Random Forests for large data sizes, the algorithm exhibits non-trivial data-dependent performance characteristics for smaller datasets and can be analyzed in terms of a geometric confidence measure, thus adding to the repertoire of geometric approaches to classification while having the benefit of not requiring any model changes or retraining as new training samples or classes arc added.