Tropical Geometry for Machine Learning and Optimization
Presenter: PETROS MARAGOS1,2
1School of E.C.E., National Technical University of Athens, Greece.
2Athena Research Center, Robotics Research Unit, Greece.
Web: http://robotics.ntua.gr , www.cvsp.cs.ntua.gr
Presented by: Petros Maragos
Tropical geometry is a relatively recent field in mathematics and computer science combining elements of algebraic geometry and polyhedral geometry. The scalar arithmetic of its analytic part pre-existed (since the 1980s) in the form of max-plus and min-plus semiring arithmetic used in finite automata, nonlinear image processing, convex analysis, nonlinear control, and idempotent mathematics.
Tropical geometry recently emerged successfully in the analysis and extension of several classes of problems and systems in both classical machine learning and deep learning. Such areas include (1) Deep Neural Networks (DNNs) with piecewise-linear (PWL) activation functions, (2) Morphological Neural Networks, (3) Neural Network Minimization, (4) Optimization (e.g. dynamic programming) and Probabilistic Dynamical Systems, and (5) Nonlinear regression with PWL functions. Areas (1), (2) and (3) have many novel elements and have recently been applied to image classification problems. Area (4) offers new perspectives on several areas of optimization. Area (5) is also novel and has many applications.
The tutorial will cover the following topics:
Elements from Tropical Geometry and Max-Plus Algebra (Brief). We will first summarize introductory ideas and objects of tropical geometry, including tropical curves and surfaces and Newton polytopes. We will also provide a brief introduction to the max-plus algebra that underlies tropical geometry. This will involve scalar and vector/signal operations defined over a class of nonlinear spaces and optimal solutions of systems of max-plus equations. Tropical polynomials will be defined and related to classical polynomials through Maslov dequantization. Then, the above introductory concepts and tools will be applied to analyzing and/or providing solutions for problems in the following broad areas of machine learning.
Neural Networks with Piecewise-linear (PWL) Activations. Tropical geometry recently emerged in the study of deep neural networks (DNNs) and variations of the perceptron operating in the max-plus semiring. Standard activation functions employed in DNNs, including the ReLU activation and its “leaky” variants, induce neural network layers which are PWL convex functions of their inputs and create a partition of space well-described by concepts from tropical geometry. We will illustrate a purely geometric approach for studying the representation power of DNNs — measured via the concept of a network’s “linear regions” — under the lens of tropical geometry.
Morphological Neural Networks. Recently there has been a resurgence of networks whose layers operate with max-plus arithmetic (inspired by the fundamental operators of morphological image processing). Such networks enjoy several promising aspects including faster training and capability of being pruned to a large degree without severe degradation of their performance. We will present several aspects from this emerging class of neural networks from some modern perspectives by using ideas from tropical geometry and mathematical morphology. Subtopics include methods for their training and pruning resulting in sparse representations.
Neural Network Minimization. The field of tropical algebra is closely linked with the domain of neural networks with PWL activations, since their output can be described via tropical polynomials in the max-plus semiring. In this tutorial, we will briefly present methods based on approximation of the NN tropical polynomials and their Newton Polytopes via either (i) a form of approximate division of such polynomials, or (ii) the Hausdorff distance of tropical zonotopes, in order to minimize networks trained for multiclass classification problems. We will also present experimental evaluations on known datasets, which demonstrate a significant reduction in network size, while retaining adequate performance.
Approximation Using Tropical Mappings. Tropical Mappings, defined as vectors of tropical polynomials, can be used to express several interesting approximation problems in ML. We will focus on three closely related optimization problems: (a) the tropical inversion problem, where we know the tropical mapping and the output, and search for the input, (b) the tropical regression problem, where we know the input-output pairs and search for the tropical mapping;, and (c) the tropical compression problem, where we know the output, and search for an input and a tropical mapping that represent the data in reduced dimensions. There are several potential applications including data compression, data visualization, recommendation systems, and reinforcement learning. We will present a unified theoretical framework, where tropical matrix factorization has a central role, a complexity analysis, and solution algorithms for this class of problems. Problem (b) will be further detailed under PWL regression (see next).
Piecewise-linear (PWL) Regression. Fitting PWL functions to data is a fundamental regression problem in multidimensional signal modeling and machine learning, since approximations with PWL functions have proven analytically and computationally very useful in many fields of science and engineering. We focus on functions that admit a convex repr¬¬esentation as the maximum of affine functions (e.g. lines, planes), represented with max-plus tropical polynomials. This allows us to use concepts and tools from tropical geometry and max-plus algebra to optimally approximate the shape of curves and surfaces by fitting tropical polynomials to data, possibly in the presence of noise; this yields polygonal or polyhedral shape approximations. For this convex PWL regression problem we present optimal solutions w.r.t. $\ell_p$ error norms and efficient algorithms.
Download slides at: http://robotics.ntua.gr/wp-content/uploads/sites/2/PetrosMaragos_ICASSP2024_Tutorial_TGMLO_20240407.pdf