Persistent homology is a technique of topological data analysis that seeks to understand the shape of data. We study the effectiveness of a single-layer perceptron and gradient boosted classification trees in classifying perhaps the most well-known data set in machine learning, the MNIST-Digits, or MNIST. An alternative representation is constructed, called MNIST-PD. This construction captures the topology of the digits using persistence diagrams, a product of persistent homology. We show that the models are more effective when trained on MNIST compared to MNIST-PD. Promising evidence reveals that the topology is learned by the algorithms. / Thesis / Master of Science (MSc)

This thesis studies problems in computational topology through the lens of semi-algebraic geometry. We first give an algorithm for computing a semi-algebraic basis for the first homology group, H1(S,F), with coefficients in a field F, of any given semi-algebraic set S⊂Rk defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves s polynomials whose degrees are bounded by d, the complexity of the algorithm is bounded by (sd)^kO⁽¹⁾.This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. We then turn our attention to the Reeb graph, a tool from Morse theory which has recently found use in applied topology due to its ability to track the changes in connectivity of level sets of a function. The roadmap of a set, a construction that arises in semi-algebraic geometry, is a one-dimensional set that encodes information about the connected components of a set. In this thesis, we show that the Reeb graph and, more generally, the Reeb space, of a semi-algebraic set is homeomorphic to a semi-algebraic set, which opens up the algorithmic problem of computing a semi-algebraic description of the Reeb graph. We present an algorithm with singly-exponential complexity that realizes the Reeb graph of a function f:X→Y as a semi-algebraic quotient using the roadmap of X with respect to f.

Stable rank has recently been proposed as an invariant to encode the result of persistent homology, a method used in topological data analysis. In this thesis we develop methods for statistical analysis as well as machine learning methods based on stable rank. As stable rank may be viewed as a mapping to a Hilbert space, a kernel can be constructed from the inner product in this space. First, we investigate this kernel in the context of kernel learning methods such as support-vector machines. Next, using the theory of kernel embedding of probability distributions, we give a statistical treatment of the kernel by showing some of its properties and develop a two-sample hypothesis test based on the kernel. As an alternative approach, a mapping to a Euclidean space with learnable parameters can be conceived, serving as an input layer to a neural network. The developed methods are first evaluated on synthetic data. Then the two-sample hypothesis test is applied on the OASIS open access brain imaging dataset. Finally a graph classification task is performed on a dataset collected from Reddit. / Stable rank har föreslagits som en sammanfattning på datanivå av resultatet av persistent homology, en metod inom topologisk dataanalys. I detta examensarbete utvecklar vi metoder inom statistisk analys och maskininlärning baserade på stable rank. Eftersom stable rank kan ses som en avbildning i ett Hilbertrum kan en kärna konstrueras från inre produkten i detta rum. Först undersöker vi denna kärnas egenskaper när den används inom ramen för maskininlärningsmetoder som stödvektormaskin (SVM). Därefter, med grund i teorin för inbäddning av sannolikhetsfördelningar i reproducing kernel Hilbertrum, undersöker vi hur kärnan kan användas för att utveckla ett test för statistisk hypotesprövning. Slutligen, som ett alternativ till metoder baserade på kärnor, utvecklas en avbildning i ett euklidiskt rum med optimerbara parametrar, som kan användas som ett ingångslager i ett neuralt nätverk. Metoderna utvärderas först på syntetisk data. Vidare utförs ett statistiskt test på OASIS, ett öppet dataset inom neuroradiologi. Slutligen utvärderas metoderna på klassificering av grafer, baserat på ett dataset insamlat från Reddit. / <p>QC 20200523</p>