TL;DR
"Optimal Brain Damage" (OBD) is a classic paper that introduces a theoretically grounded method for reducing the size of neural networks. By using second-derivative information (the Hessian matrix) to identify which weights actually matter, the authors show you can delete over half the parameters of a network while actually improving its ability to generalize to new data.
The Problem: Finding the Right Network Size
In the late 80s and early 90s, neural networks were getting larger and more structured to handle complex tasks like speech and image recognition. However, researchers faced a "Goldilocks" problem:
- Too many weights: The network "memorizes" the training data (overfitting), leading to poor performance on new examples. It’s also slow and computationally expensive.
- Too few weights: The network isn't powerful enough to learn the underlying patterns (underfitting).
The challenge was finding a principled way to "prune" a network—removing unnecessary connections to find the simplest architecture that still performs well. Before this paper, the standard approach was "weight decay" or simply deleting weights with the smallest magnitudes. The authors argue that a weight's size isn't a reliable indicator of its importance.
Methods: Calculating Saliency
The core innovation is the definition of saliency: the change in the objective function (error) caused by deleting a specific parameter.
To avoid the prohibitively laborious task of deleting every weight one by one to see what happens, the authors use a Taylor series expansion to create a local model of the error function. To make the math tractable for networks with thousands of parameters, they apply three key approximations:
- The Diagonal Approximation: They assume the weights are independent, ignoring the "cross-terms" in the Hessian matrix. This turns a massive matrix calculation into a simple vector operation.
- The Extremal Approximation: They assume pruning happens after the network has converged to a local minimum, meaning the first-order gradient is zero and can be ignored.
- The Quadratic Approximation: They assume the error surface is roughly parabolic, allowing them to ignore third-order derivatives and higher.
The resulting recipe is elegant: train the network, compute the diagonal second derivatives, calculate saliency, delete the low-saliency weights, and retrain.
Datasets
The authors validated OBD using a handwritten digit recognition task.
- Data: Segmented handwritten digits from US Postal Service zip codes and printed digits.
- Scale: Approximately 9,300 training examples and 3,350 test examples.
- Initial Network: A highly constrained, sparsely connected network with 2,578 free parameters and 100,000 connections.
Key Insights
- Magnitude $\neq$ Saliency: A small weight might be crucial for a specific feature, while a large weight might be redundant. OBD identifies "unimportant" weights regardless of their absolute value.
- The "Brain Damage" Paradox: Deleting parts of the network can actually make it smarter. By reducing the information capacity of the model, you force it to capture the essence of the data rather than the noise.
- Interactive Design: The authors found that OBD wasn't just an automatic tool; it was a diagnostic one. It revealed that entire layers of their hand-designed architecture were expendable, leading to a better understanding of how information flows through the network.
- Efficiency: Computing the diagonal Hessian is roughly the same order of complexity as standard back-propagation, making it a practical tool for real-world engineering.
Key Results
- Massive Compression: The authors were able to delete 60% of the parameters (reducing the count from 2,500 to about 1,000) with almost no increase in training error.
- Better Generalization: On the test set, the pruned network actually performed better than the original, as the reduction in parameters helped prevent overfitting.
- Superiority over Magnitude Pruning: Experimental curves showed that OBD-based pruning resulted in significantly lower error rates than deleting weights based on their magnitude.
- Speedup: By reducing the number of parameters by a factor of four, the network's classification speed improved significantly.
Limitations and Future Work
- The Diagonal Assumption: The authors acknowledge that ignoring the off-diagonal terms of the Hessian is a simplification. If weights are highly correlated, the diagonal approximation might misidentify their importance.
- Retraining Requirement: The process is iterative. You can't just delete 60% of the weights in one go; you must delete some, retrain, and repeat to allow the remaining weights to compensate.
- Complexity Measure: While this paper uses the number of non-zero parameters as a proxy for complexity, the authors suggest that second-derivative information could eventually lead to a more sophisticated measure of a network's "information content."
Summary updated