Petros Maragos

Uploaded by AUTH

Tropical (a.k.a. max-plus) algebra has been developed in the 1980’s and has been applied successfully in nonlinear image processing, control and optimization. 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 in the form of max/min-plus semiring arithmetic used in finite automata, nonlinear image processing, convex analysis, nonlinear control, and idempotent mathematics. Tropical algebra and geometry have 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, and (5) Nonlinear regression with PWL functions.  This tutorial will cover the following topics:

• Elements from Tropical Geometry and Max-Plus Algebra (Brief synopsis).
• Neural Networks with Piecewise-linear Activations, including DNNs with ReLU activations and max-out units. We will study their representation power under the lens of tropical geometry.
• Morphological Neural Networks: Recently there has been a resurgence of networks whose layers operate with max-plus arithmetic. Such networks enjoy faster training and capability of being pruned to a large degree without severe degradation of their performance.
• Neural Network Minimization. We will present several methods, based on approximation of the NN tropical polynomials and their Newton polytopes, to minimize networks trained for multiclass classification problems together with experimental evaluations on known datasets.
• Approximation Using Tropical Mappings. Tropical Mappings, defined as vectors of tropical polynomials, can express several interesting approximation problems in ML, including: (a) tropical inversion; (b) tropical regression; and (c) tropical compression. Potential applications include data compression, data visualization, recommendation systems, and reinforcement learning. We will unify these problems via tropical matrix factorization and present solution algorithms.
• Piecewise-linear (PWL) Regression. Fitting PWL functions to data is a fundamental regression problem in multidimensional signal modeling and machine learning. It has been 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 max of affine functions (e.g. lines, planes). This yields polygonal or polyhedral shape approximations. For this convex PWL regression problem we present optimal solutions and efficient algorithms.

More information and related papers can be found in http://robotics.ntua.gr.