TL;DR
This paper introduces a novel method for compressing large neural networks by replacing entire layers with sparse oblique decision forests. This approach significantly reduces inference time and parameter count while maintaining or even improving accuracy, offering a compelling alternative to traditional compression techniques.
What Problem Does This Paper Address?
Deploying large, computationally intensive neural networks on resource-constrained devices (like mobile phones or edge devices) is a major challenge. While existing methods like pruning, quantization, and low-rank factorization can reduce model size and computation, they often involve complex training procedures or can lead to accuracy degradation. This paper tackles the problem of accelerating neural network inference and reducing model complexity by exploring a new compression paradigm: replacing substantial parts of a neural network with specialized decision forests.
Methods
The core of this work lies in using sparse oblique decision trees trained with the Tree Alternating Optimization (TAO) algorithm within a teacher-student framework.
- Sparse Oblique Decision Trees: Unlike traditional decision trees that use axis-aligned splits (e.g., "if feature X > threshold"), oblique trees use hyperplane splits (e.g., "if aX1 + bX2 > c"). This allows for more complex decision boundaries. The "sparse" aspect comes from an L1 regularization term during training, which encourages many weights in the decision nodes to become zero, effectively pruning them and simplifying the tree.
- Tree Alternating Optimization (TAO): This algorithm optimizes the tree's parameters (hyperplanes and leaf predictions) iteratively, similar to how neural networks are trained, rather than the greedy top-down growth of traditional decision trees. It optimizes a regularized empirical risk function.
- Teacher-Student Approach: The "teacher" is a portion of the original neural network (typically the later layers), and the "student" is the decision forest. The forest is trained to mimic the output of the teacher network, effectively learning to perform the same task. This allows the forest to leverage the rich features learned by the preceding layers of the neural network.
The authors also explore ensembling these sparse oblique trees using bagging and boosting to form decision forests, further enhancing performance.
Datasets
The experiments were conducted on standard image classification datasets:
- CIFAR10
- CIFAR100
- MNIST
The paper uses these datasets to train and evaluate various neural network architectures (LeNet5, VGG16, ResNet56) and their compressed counterparts.
Key Insights and Ideas
- Decision Forests as Layer Replacements: The most significant insight is that decision forests, specifically sparse oblique ones, can effectively replace entire layers (including convolutional and fully-connected layers) of deep neural networks without sacrificing accuracy, and often with substantial improvements in inference speed.
- Oblique Trees Outperform Axis-Aligned: The paper demonstrates that sparse oblique forests achieve a much better accuracy-compression tradeoff compared to traditional axis-aligned forests (like Random Forests or XGBoost), even when those are optimized with specialized compilers like TreeLite.
- TAO's Efficiency: The TAO algorithm, combined with L1 regularization, is shown to be effective in learning sparse oblique trees that are both accurate and computationally efficient. The training process for these forests is also noted to be significantly faster and more parallelizable than training neural networks.
- Orthogonality to Other Methods: The proposed forest-based compression is orthogonal to other techniques like pruning and quantization, meaning it can be combined with them for even greater compression.
Key Results
The paper reports impressive compression ratios and speedups:
- VGG16 (CIFAR10): Replacing the last 7 layers of VGG16 with a single sparse oblique tree reduced FLOPs by 7440x with a marginal increase in test error. A boosted ensemble of nine trees matched the network's performance while reducing FLOPs by 6289x.
- LeNet5 (MNIST): A bagged forest of 11 trees achieved a test accuracy of 0.57% (slightly better than the reference 0.55%) with a 69x reduction in FLOPs and a 3.41x reduction in parameters, running ~4x faster. A boosted ensemble of 5 trees achieved an even better test error of 0.52% with a 21x FLOP reduction and 4x parameter reduction, running ~4x faster.
- VGG16 (CIFAR10): Replacing the last 7 layers with a bagged ensemble of 9 trees achieved the same test error as the reference network but with a 9.6x parameter reduction, 516x FLOP reduction, and 28x inference speedup. A boosted ensemble of 9 trees achieved the same error with a 6289x FLOP reduction and 86x inference speedup.
- General Observation: Sparse oblique forests consistently offered orders of magnitude faster inference times compared to regular and even TreeLite-optimized XGBoost and Random Forests, while achieving better or comparable test errors.
Limitations and Future Work
- Hardware/Software Dependence: The authors acknowledge that inference times can vary depending on hardware and software implementations. They believe their sparse oblique trees have significant room for further optimization, potentially widening the performance gap.
- End-to-End Training: Currently, the approach involves training the forest separately from the preceding neural network layers. The authors express interest in developing methods for end-to-end training of such hybrid architectures.
- Arbitrary Layer Replacement: While they demonstrate replacing later layers, future work could explore replacing arbitrary portions of a neural network.
- Other Tree Types/Ensembles: Investigating other types of decision trees or ensembling mechanisms is also suggested.
- CPU/GPU Implementation: Efficient implementation of sparse oblique trees and forests on CPUs and GPUs is a promising direction.
Summary updated