EF1 – Extracting Dynamical Laws from Complex Data

Project

EF1-3

Approximate Convex Hulls with Bounded Complexity

Project Heads

Michael Joswig, Klaus-Robert Müller

Project Members

Marek Kaluba (TU) 

Project Duration

01.01.2019 – 31.12.2020

Located at

TU Berlin

Description

Finding a meaningful data representation that captures the relevant information for some task or problem lies at the very core of any data-driven discipline such as statistics or machine learning. In contrast to handcrafted data features, representation learning aims to learn such representations from the data itself. Convexity is a very natural and fundamental representation property in machine learning in general. The separation of classes via multiple hyperplanes or half-spaces in supervised classification for instance, such as in Support Vector Machines (SVMs) in the Reproducing Kernel Hilbert Space (RKHS) via the hinge loss or in deep neural networks (DNNs) in the output space via the cross-entropy loss, forms polyhedra that are convex and generally unbounded. Moreover, many well-known unsupervised learning methods make explicit convexity assumptions on the support of the data representation, such as Voronoi cells in k-means clustering or ellipsoids in Gaussian Mixture Models (GMMs). Yet it is worth noting that convexity is also implicit in Gaussian prior assumptions in popular deep generative models such as Variational Autoencoders (VAEs), or Generative Adversarial Networks (GANs). Finally, one-class classification methods for support estimation such as the One-Class SVM or (Deep) Support Vector Data Description (SVDD) also rely on convex assumptions on the data representation via maximum-margin hyperplane and minimum enclosing hypersphere descriptions, respectively.

Although a convex representation of classes and clusters is such a natural and commonly desired property, measuring convexity in a robust and efficient way in high-dimensional spaces is a challenging and fairly non-trivial problem. In this project we propose a scalable and robust method called Random Polytope Descriptor (RPD) for evaluating convexity in representation learning. Our method is based on concepts from convex geometry and constructs a polytope (a piecewise-linear, bounded convex body) around the training data in representation space. Since polytopes by themselves may also suffer from a combinatorial explosion, we construct our descriptor from random convex polytopes instead which also enhances its robustness. Finally, using the proximity to such polytopes allows us to judge the geometric disentanglement of representations, i.e. how well classes and clusters are separated into convex bodies. Our main contributions are the following:

• We propose the Random Polytope Descriptor (RPD) method which is based on the construction of random convex polytopes for evaluating convexity in representation learning and theoretically prove its scalability.
• We demonstrate the usefulness of RPD in experiments on well-known supervised as well as unsupervised deep learning methods for representation learning.
• We find that popular regularization variants of deep autoencoders such as the Variational Autoencoder can destroy crucial geometric information that is relevant for out-of-distribution detection.

The project combines state-of-the-art Machine learning tools with established tools in computational polyhedral geometry using the novel Julia programming language.

Moreover, in the reverse direction, we use reinforced learning (RL) to study the beneath-and-beyond (BB) algorithm with the aim of finding a minimal (in terms of number of top-dimensional simplices) triangulation (the problem is known to be NP-hard). The running time of the algorithm and the size of the resulting triangulation is known to be sensitive to the insertion order. For inferring an optimal ordering we use AlphaZero, a self-play algorithm known to master several board games without former knowledge. The RL task then is then to find an optimal ordering of points minimizing the size of the resulting triangulation. To this aim we reinterpreted the BB iterative process as a single-player game. The game consists of a board (the input set of points), in each turn the player chooses a point by placing a token on an empty place on the board, until the whole board is occupied. After each choice is made, the point is added to the existing triangulation via the BB iterative step. If an optimal game is played, the history of the game defines the optimal ordering of points for the BB algorithm. This is ongoing work in progress;

Project Webpages

Selected Publications

[Kaluba2020] M. Kaluba, B. Lorenz, and S. Timme. Polymake.jl a new interface to `polymake`. Accepted to ICMS, 2020, arXiv:2003.11381.

[Kaluba2020a] M. Kaluba, L. Ruffs, M. Joswig. Geometric Disentanglement by Random Convex Polytopes, arXiv:2009.13987.

Selected Pictures