This paper moves beyond simply counting the "complexity" of neural networks to actually looking under the hood at the math they perform on individual data points.
TL;DR
The authors introduce TropEx, an algorithm based on tropical algebra that extracts the specific linear equations a ReLU network applies to data. Their findings reveal a striking reality: almost every data point sits in its own unique "linear region," and Convolutional Neural Networks (CNNs) and Fully-Connected Networks (FCNs) utilize these regions in fundamentally different ways to generalize to new data.
What Problem Does This Paper Address?
Deep neural networks using Rectified Linear Unit (ReLU) activations are technically piecewise linear functions. Imagine the input space (like all possible 32x32 images) partitioned into millions of tiny "rooms" or regions. Inside each room, the network behaves like a simple linear equation ($y = Wx + b$).
Previous research focused on the number of these regions, which is astronomically high—often exceeding $10^{300}$ even for small networks. Since we only have maybe $10^6$ training samples, the vast majority of these regions never see a single piece of data during training. This creates a paradox: If the network is a collection of linear pieces, and almost all those pieces are "empty" during training, how does the network know what to do when a test image falls into one of those empty regions?
Methods
The authors bridge the gap between deep learning and tropical algebra. In tropical geometry, the "sum" of two numbers is their maximum, and the "product" is their standard sum. It turns out that any ReLU network can be represented as a "tropical rational map"—specifically, the difference between two maximums of linear functions.
To make this practical, the authors developed:
- Matrix Representation: A way to represent these complex tropical functions as multi-dimensional arrays that a computer can process efficiently.
- The TropEx Algorithm: A method that starts at the output layer and works backward through the network to extract the specific linear coefficients (the $W$ and $b$) that define the region where a specific data point resides.
- Function Extraction: They created "extracted" versions of networks that only contain the linear terms found at training data points, allowing them to see how much of the network's performance comes from the data it actually saw versus the "empty" space in between.
Key Insights and Ideas
- The "One Point, One Region" Rule: In practice, training and test samples almost never fall into the same linear region. Generalization isn't about the test point landing in a "trained" room; it's about the "untrained" rooms having coefficients that are consistent with the trained ones.
- MNIST is "Solved" by Training Regions Alone: For simple tasks like MNIST, an FCN can achieve ~97% test accuracy using only the linear terms extracted from training data. This suggests the "empty" regions in MNIST networks are mostly redundant.
- CNNs vs. FCNs: There is a fundamental difference in how these architectures store information. FCNs have the "freedom" to tailor coefficients to specific data, leading to highly correlated linear terms across different training runs. CNNs, constrained by weight sharing and filters, produce much more diverse, nearly orthogonal linear terms.
- The Failure of "Empty" Regions in Complex Tasks: On CIFAR10, the "extracted" networks perform poorly compared to the originals. This indicates that for complex data, the network relies heavily on the specific way it interpolates between training points in those "empty" regions.
Key Results
- Accuracy Gap: On CIFAR10, a CNN's accuracy drops from ~71% to ~30% when you only keep the linear terms from training data. In contrast, an FCN on MNIST only drops from ~98% to ~97%.
- Coefficient Orthogonality: Visualizations show that for CNNs, the angles between the linear coefficients of different data points are almost always near 90 degrees ($\pi/2$, orthogonal). For FCNs, these angles are much smaller, indicating the network is reusing similar "logic" across different parts of the input space.
- Training Evolution: As training progresses, FCNs gradually "simplify" their internal representation, while CNNs maintain a high level of diversity in their linear terms from the very first epoch.
Limitations and Future Work
While TropEx provides a powerful lens, it has some constraints:
- Computational Cost: While more efficient than symbolic math, extracting terms for millions of points is still resource-intensive.
- Activation Functions: The current framework is specifically designed for ReLU and Leaky ReLU. Extending this to smoother activations like Sigmoid or Swish would require different mathematical tools.
- Interpretability: While we can now "see" the coefficients, we still don't fully understand why a specific set of $10,000$ coefficients represents a "cat" in a way that generalizes across empty regions. Future work could focus on the "structural" properties of these coefficient matrices.
Summary updated