Tropical Geometry of Deep Neural Networks

Liwen Zhang; Gregory Naitzat; Lek-Heng Lim

Source-linked AI summary

Tropical Geometry of Deep Neural Networks

Liwen Zhang, Gregory Naitzat, Lek-Heng Lim

arXiv:1805.07091v1May 18, 2018cs.LGmath.AGstat.ML

TL;DR

The paper addresses incomplete theoretical understanding of deep neural networks by connecting feedforward ReLU networks with tropical geometry. It characterizes these networks as tropical rational maps and uses tropical tools to analyze decision boundaries, linear regions, and expressiveness.

Problem
Theoretical understanding of why deep neural networks work remains incomplete, motivating connections between ReLU networks and tropical geometry.
Method
The paper models feedforward ReLU neural networks as tropical rational maps and analyzes them using tropical algebraic geometry.
Results
ReLU networks are characterized as tropical rational maps, with decision boundaries and linear regions connected to tropical-geometric objects and deeper networks shown to be exponentially more expressive.
Takeaways & Limitations
Tropical geometry provides useful insights into ReLU network workings by translating neural-network questions into problems involving tropical hypersurfaces, subdivisions, and polytopes.
Takeaways & Limitations
The derived upper bound is more restrictive than prior work because it applies only to neural networks satisfying assumptions (a)–(c) and does not improve the existing bound.

Abstract

from arXiv · show

We establish, for the first time, connections between feedforward neural networks with ReLU activation and tropical geometry --- we show that the family of such neural networks is equivalent to the family of tropical rational maps. Among other things, we deduce that feedforward ReLU neural networks with one hidden layer can be characterized by zonotopes, which serve as building blocks for deeper networks; we relate decision boundaries of such neural networks to tropical hypersurfaces, a major object of study in tropical geometry; and we prove that linear regions of such neural networks correspond to vertices of polytopes associated with tropical rational functions. An insight from our tropical formulation is that a deeper network is exponentially more expressive than a shallow network.

1. Introduction

The paper uses tropical geometry to address the incomplete theoretical understanding of deep neural networks, showing that integer-weight feedforward ReLU networks are exactly tropical rational maps. This connection translates neural-network structure and complexity into tropical-geometric objects and shows that depth yields exponential expressiveness.

The paper aims to connect feedforward ReLU neural networks with tropical geometry to shed light on how deep networks work.
A neural network can therefore be viewed as a tropical ratio of two tropical polynomials, with each output coordinate a tropical rational function.
Feedforward neural networks with ReLU activation and integer weights represent exactly the family of tropical rational maps.
The tropical formulation relates neural-network linear-region boundaries to tropical hypersurfaces and bounds linear-region counts using vertices of associated polytopes.
The analysis proves that deeper neural networks are exponentially more expressive than shallow networks, while emphasizing tropical-geometric insight rather than state-of-the-art performance analysis.

2. Tropical algebra

Tropical algebra replaces ordinary addition and multiplication with maximum and addition, forming a semifield-like framework for tropical polynomials and rational functions. These functions are piecewise linear, and vector-valued tropical rational maps provide the formal language used for neural networks.

Tropical addition is maximum, tropical multiplication is ordinary addition, and tropical quotient is ordinary subtraction.
The tropical structure uses R ∪ {-∞}, with -∞ as additive identity and 0 as multiplicative identity, forming a semiring.
A tropical polynomial is a finite tropical sum of tropical monomials with coefficient and multiindex representations.
A tropical rational function is the ordinary difference, or tropical quotient, of two tropical polynomials.
Tropical polynomials are convex piecewise-linear functions, while tropical rational functions are difference-convex functions and may have nonconvex linear regions.

3. Tropical hypersurfaces

Tropical hypersurfaces identify where tropical polynomials cease to be linear and divide their domains into linear cells. Newton polytopes and their dual subdivisions connect these cells to polyhedral structure, enabling bounds on linear regions through zonotopes and Minkowski sums.

A tropical hypersurface is the set where a tropical polynomial’s value is attained by at least two monomials, equivalently where the function is not linear.
Tropical hypersurfaces divide the domain into convex polyhedral cells on which the tropical polynomial is linear.
The Newton polygon is the convex hull of a tropical polynomial’s exponent vectors, and lifting exponents by coefficients produces its dual subdivision.
Each vertex in the dual polyhedral complex corresponds to a cell where the tropical polynomial is linear, so Newton-polytope vertices upper-bound the number of linear regions.
Tropical powers scale Newton polytopes, while tropical products and sums transform them through Minkowski sums and convex-hull operations.
Zonotope and Minkowski-sum vertex bounds provide tools for bounding linear regions, with equality requiring general-position generating segments and projected vertices.

4. Neural networks

The paper formalizes fully connected feedforward networks as compositions of affine maps and fixed activations, focusing on ReLU networks under integer-weight assumptions. This setting supports the tropical characterization while excluding nonlinear activations such as sigmoid and hyperbolic tangent.

The paper focuses on fully connected feedforward ReLU networks because they are a canonical setting for theoretical insights rather than task-specific efficacy.
An L-layer feedforward network is a composition of affine preactivation maps and fixed activation functions.
Layer width records the number of nodes, with input dimension n0 = d and output dimension nL = p.
The network assumptions use integer-valued weight matrices, real-valued biases, and coordinatewise threshold activations.
Restricting weights to integers is justified by rational approximation, clearing denominators, and the invariance of network behavior under common positive scaling.
The framework includes ReLU, identity, leaky ReLU, and absolute-value activations, but not hyperbolic tangent or sigmoid activations.

5. Tropical algebra of neural networks

The paper represents ReLU feedforward networks as differences of tropical polynomials, yielding a tropical rational-map characterization. Under integer-weight assumptions, this correspondence is exact and also matches continuous piecewise-linear functions with integer coefficients.

Tropical representation: A ReLU layer output is a difference of two tropical polynomials, and deeper networks preserve this form through recursive decomposition.The preactivation and layer outputs are expressed as tropical rational functions using decompositions of weight matrices into nonnegative parts.
Tropical representation: Theorem 5.2 states that feedforward networks under the paper’s assumptions have coordinates that are tropical rational functions, hence form tropical rational maps.The network coordinates are represented using tropical polynomial maps F and G.
Equivalence: With integer weights and linear output, every ReLU feedforward network is a tropical rational function.The integer-weight condition is used to encode weights as exponents of tropical monomials.
Equivalence: Theorem 5.4 establishes an if-and-only-if equivalence between tropical rational functions and feedforward neural networks satisfying the stated assumptions.Together with Proposition 5.5, the result also identifies continuous piecewise-linear functions with integer coefficients as an equivalent class.
Equivalence: A tropical rational function can be represented by an L-layer neural network with L ≤ max{⌈log2 r_f⌉, ⌈log2 r_g⌉} + 2.Here r_f and r_g are the numbers of monomials in the tropical polynomials f and g.
Geometric implications: The resulting characterization connects tropical algebraic geometry with neural-network analysis, including the study of boundaries between linear regions and decision boundaries.The paper uses this algebraic viewpoint to motivate subsequent geometric analysis of neural networks.

6. Tropical geometry of neural networks

The paper uses tropical geometry to analyze ReLU neural networks, connecting decision boundaries, zonotopes, and linear-region complexity to tropical hypersurfaces and polytopes. It shows that depth makes represented functions substantially more complex, while noting that its upper bound is more restrictive and does not improve prior work.

6.1. Decision boundaries of a neural network: Decision boundaries are contained in tropical hypersurfaces associated with tropical polynomials derived from the network and decision threshold.For ν = f/g, the boundary satisfies B ⊆ T(s^-1(c) ⊙ g ⊕ f).
6.1. Decision boundaries of a neural network: The decision boundary partitions the input space into at most N(f) positive regions and at most N(g) negative regions.
6.3. Geometric complexity of deep neural networks: The number of neural-network linear regions can be bounded using vertices in the dual subdivision of a Newton polytope.
6.2. Geometric building blocks: Zonotopes form geometric building blocks for the tropical representation of neural networks, with layer constructions involving weighted Minkowski sums.
6.3. Geometric complexity of deep neural networks: The paper’s upper bound does not improve Raghu et al.’s bound and applies only to networks satisfying assumptions (a)–(c).
6.3. Geometric complexity of deep neural networks: The number of linear regions grows polynomially with width n and exponentially with the number of layers L when hidden-layer widths are comparable.

7. Conclusion

The conclusion presents tropical geometry as a framework for translating neural-network questions into geometric questions. It identifies this work as a first proof of concept and leaves broader implications for future investigation.

Neural networks can be treated, modulo trivialities, as tropical rational maps, allowing their analysis through tropical geometry.
Questions about decision boundaries, linear regions, and depth-dependent expressiveness translate into questions about tropical hypersurfaces, subdivisions, and zonotope-based polytopes.
The paper emphasizes that it examines only a small part of tropical geometry and encourages further investigation from this perspective.

Supplementary Material: Tropical Geometry of Deep Neural Networks

The supplementary material introduces the network notation and tropical-algebraic tools used to relate tropical polynomials and hypersurfaces to polyhedral geometry. It also describes the dual correspondence between tropical hypersurfaces and Newton-polytope subdivisions.

Figure A.1 summarizes the architecture and notation of the ReLU feedforward neural network used in the paper.
Tropical power: For nonnegative powers, tropical powers distribute over tropical sums and products, but this sum identity fails when the exponent is negative.
Tropical hypersurfaces: A bivariate tropical hypersurface is a planar graph dual to the dual subdivision of its Newton polygon.
Tropical hypersurfaces: Two-dimensional faces in the dual subdivision correspond to tropical-hypersurface vertices, while subdivision edges correspond to hypersurface edges.
Dual subdivisions: The dual subdivision is obtained by projecting the upper envelope of an associated polytope onto R^2.

C.2. Polytopes of a two-layer neural network

The two-layer example constructs higher-layer polytopes from first-layer pieces using weighted Minkowski sums, then obtains dual subdivisions by projecting upper faces. The resulting polytope for f(2) combines the polytopes for g(2) and h(2).

The example uses a network with 2 input nodes, 5 first-layer nodes, and 1 output node.
First-layer monomial polytopes are points or line segments in R^3, whose projections yield the corresponding dual subdivisions.
The polytopes P(h(2)) and P(g(2)) are constructed from first-layer pieces as weighted Minkowski sums.
P(f(2)) is the convex hull of P(g(2)) and P(h(2)), while its dual subdivision comes from projecting the upper faces onto the a1,a2-plane.
The construction relies on upper and lower envelope vertices and their projections to relate polytope vertices to the relevant subdivisions.

D.3. Proof of Theorem 5.4

The proof establishes that ReLU networks with integer weights and tropical rational maps represent exactly the same family of functions. It does so by constructing networks for tropical polynomials and rational functions, then proving the converse by decomposing network regions.

Tropical sums of represented functions are implemented by adding one layer beyond the larger constituent depth.
A tropical polynomial formed from r monomials can be represented by a ReLU network with no more than ⌈log2 r⌉ + 1 layers.
Tropical rational functions p − q are represented by combining neural-network representations of the tropical polynomials p and q.
Therefore feedforward ReLU networks with integer weights are exactly the family of tropical rational maps.
Conversely, a piecewise-linear ReLU network is expressed through tropical rational functions on its linear regions and their tropical combinations.

D.6. Proof of Proposition 6.1

The proof identifies neural-network decision boundaries with level sets of tropical rational functions. Under a monomial-separation condition, these level sets lie inside tropical hypersurfaces.

For f − g=c, the level set divides the domain into at most N(f) regions above c and at most N(g) regions below c.
If no monomial of f differs from a monomial of g by c, the level set is contained in a tropical hypersurface.
The containment follows by combining f and g+c tropically, so the level-set value is attained by at least two monomials.
A decision boundary ν(x)=s^-1(c) is a level set of the tropical rational function ν.

D.7. Proof of Theorem 6.3

The proof bounds the complexity of deep tropical rational maps by composing convex-region refinements, while addressing their potentially nonconvex linear regions. Applied recursively to neural-network layers, this yields depth-dependent region bounds.

Convex degree: Tropical rational maps can have nonconvex linear regions, unlike tropical polynomial maps, so the proof introduces convex refinements.
General exponents: A general exponent α can be chosen in N^n so that F^α has the same linear regions as F.
Composition: For H=F∘G, the convex degree satisfies N(H) ≤ Nc(H) ≤ Nc(F|d) · Nc(G).
Neural-network layers: For a neural-network layer, the affine input map has convex degree one, reducing the layer bound to the activation map.
Neural-network layers: The one-layer construction uses a weighted Minkowski sum of line segments, hence a zonotope, to bound its convex degree.
Deep networks: Applying the composition bound recursively gives the stated depth-dependent bound for an L-layer neural network.