Shapley Value as Principled Metric for Structured Network Pruning

Markus Gross, Marco Ancona, Cengiz Öztireli, Markus Gross 0001arXiv 2020 · arXiv

Abstract

Deep Neural Networks (DNNs) are notoriously overparameterized. Structured pruning—removing entire neurons or filters—is essential for hardware acceleration but relies on accurate importance metrics. We demonstrate that common heuristics fail in data-scarce environments where fine-tuning cannot recover performance. By applying Shapley values from cooperative game theory, we introduce a principled method to rank neurons based on their marginal contributions. Our results show that Shapley-based pruning significantly outperforms traditional heuristics in robustness and accuracy, particularly in low-data regimes.

Introduction

The overparameterization of Deep Neural Networks (DNNs) allows for significant compression via pruning. Structured pruning is preferred for real-world speedups but requires identifying which units are redundant. Traditional importance scores, such as weight magnitudes or Taylor expansions, are often sub-optimal heuristics. While some argue that fine-tuning makes the choice of pruning metric irrelevant, we show that this choice is critical when data or compute resources are limited.

Methodology

We treat neurons within a network layer as players in a cooperative game. The Shapley value of a neuron is its average marginal contribution across all possible subsets of other neurons.

Theoretical Properties

Shapley values are the unique attribution method satisfying four fundamental axioms:

  • Null Player: Neurons with no impact receive a zero score.
  • Symmetry: Identical neurons receive identical scores.
  • Linearity: Scores are consistent across task combinations.
  • Efficiency: The sum of all scores equals the total performance gain.

Computational Feasibility

Calculating exact Shapley values is NP-hard ($2^n$). We utilize a sampling-based approximation that allows for practical computation on modern GPUs within seconds or minutes. Unlike magnitude-based metrics, Shapley values can be negative, identifying "harmful" neurons that actively degrade network performance.

Comparison of attribution methods on a toy network. Shapley values (SV) correctly identify neuron contributions where heuristics like weight norms or Taylor expansions fail.

Experimental Evaluation

We evaluated our approach on MNIST, CIFAR-10, and ImageNet, as well as the CUB-200 dataset to simulate low-data transfer learning scenarios.

Key Insights

  1. Heuristic Fragility: Standard metrics can be "fooled" by redundant or symmetric neurons, whereas Shapley values remain robust.
  2. Harmful Neurons: Pruning units with negative Shapley values can improve the accuracy of randomly initialized networks without any training.
  3. Low-Data Robustness: In transfer learning tasks (e.g., CUB-200), Shapley-based pruning prevents the model collapse observed with random or heuristic-based pruning.

Results

Shapley values consistently outperformed APoZ, weight norms, and sensitivity metrics in layer-wise pruning tests. On the CUB-200 dataset, Shapley-based pruning maintained significantly higher stability at high pruning ratios.

Test accuracy vs. pruned layers for CIFAR-10 and CUB-200. Shapley values (SV) consistently maintain higher accuracy, especially in the low-data CUB-200 regime.

Quantitatively, Shapley values achieved an Area Under the Curve (AUC) for loss of 0.11 on Fashion-MNIST, nearly doubling the performance of the next best heuristic (0.19).

Conclusion

Shapley values provide a mathematically principled framework for network pruning. While computationally more demanding than simple heuristics, the "measure twice, cut once" philosophy is essential for deploying models in data-constrained environments. Future work will focus on more efficient approximation algorithms to further integrate this method into standard deep learning workflows.

Summary updated

BibTeX
@misc{gross2020shapley,
  author = {Markus Gross and Marco Ancona and Cengiz Öztireli and Markus Gross},
  title = {{Shapley Value as Principled Metric for Structured Network Pruning}},
  year = {2020},
  eprint = {2006.01795},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.01795},
}
Figure