Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper Complexity Measure for Classification
This work addresses the need for a proper complexity measure in classification to improve generalization and robustness, offering a foundational approach with potential broad impact in machine learning.
The paper tackles the problem of measuring classifier complexity by proposing to directly count the number of boundary pieces in ReLU neural networks, developing a novel method using tropical geometry to achieve exact counts and finding that this measure is largely independent of other complexity metrics and negatively correlated with robustness.
Classic learning theory suggests that proper regularization is the key to good generalization and robustness. In classification, current training schemes only target the complexity of the classifier itself, which can be misleading and ineffective. Instead, we advocate directly measuring the complexity of the decision boundary. Existing literature is limited in this area with few well-established definitions of boundary complexity. As a proof of concept, we start by analyzing ReLU neural networks, whose boundary complexity can be conveniently characterized by the number of affine pieces. With the help of tropical geometry, we develop a novel method that can explicitly count the exact number of boundary pieces, and as a by-product, the exact number of total affine pieces. Numerical experiments are conducted and distinctive properties of our boundary complexity are uncovered. First, the boundary piece count appears largely independent of other measures, e.g., total piece count, and $l_2$ norm of weights, during the training process. Second, the boundary piece count is negatively correlated with robustness, where popular robust training techniques, e.g., adversarial training or random noise injection, are found to reduce the number of boundary pieces.