Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search

Han Xiao, Ziwei Wang, Jiwen Lu, Jie Zhou

Introduction

Neural Architecture Search (NAS) aims to automate the design of deep learning models. A popular approach, Differentiable Architecture Search (DARTS), makes this efficient by using gradient descent to learn "mixing weights" ($\alpha$) for different operations. However, DARTS has a fundamental flaw: the magnitude of these weights does not necessarily reflect the actual importance of an operation. An operation might have a large weight but contribute very little to the final validation accuracy, or vice versa. Furthermore, operations in a neural network are not independent; they interact in complex ways. Simply looking at one weight at a time ignores these "synergies," often leading to suboptimal architectures.

Methodology: Shapley-NAS

The authors propose Shapley-NAS, which frames architecture search as a cooperative game. Every candidate operation on every edge of the neural "supernet" is treated as a player, and the "value" of a group of operations is the validation accuracy of the sub-network they form.

To find the true contribution of an operation, the authors calculate its Shapley value—a concept from game theory that determines a "fair" reward for a player by averaging its marginal contribution across all possible combinations of other players.

Overview of the Shapley-NAS framework compared to traditional Differentiable NAS.

Since calculating exact Shapley values is NP-hard, the authors use two approximation techniques:

  1. Monte-Carlo Sampling: Estimating the value by sampling a small number of random permutations of operations.
  2. Early Truncation: If a sub-network's performance drops below a threshold $\eta$, evaluation stops early to save computation.

A momentum mechanism is used to update architecture parameters based on these estimated Shapley values over multiple training steps, ensuring search stability.

Key Insights

Synergy and Correlation

The paper demonstrates that operations are interdependent. Removing two operations together often results in a performance drop different from the sum of individual removals. Shapley-NAS captures these interactions. More importantly, the correlation between the search metric and final performance is significantly improved. While DARTS often shows near-zero correlation, Shapley-NAS achieves a Kendall Tau coefficient of ~0.4 to 0.5, indicating it accurately identifies high-performing components.

Efficiency vs. Accuracy

A key finding is that a perfect Shapley calculation isn't necessary. Using just 10 Monte-Carlo samples per step allows the algorithm to outperform traditional DARTS while maintaining low search costs.

Impact of the number of samples $M$ and truncation threshold $\eta$ on test error and search cost.

Experimental Results

Shapley-NAS was evaluated on several benchmarks:

  • CIFAR-10: Achieved a top-tier error rate of 2.43% with a search cost of only 0.3 GPU days.
  • ImageNet: Searching directly on ImageNet yielded a 23.9% top-1 error, outperforming light-weight methods like PC-DARTS.
  • NAS-Bench-201: The method successfully identified global optimal architectures on both CIFAR-10 and CIFAR-100.

Conclusion

Shapley-NAS addresses the reliability issues of gradient-based NAS by leveraging game theory. By accurately measuring marginal contributions, it discovers superior architectures with high stability and efficiency. While it introduces some computational overhead compared to simple gradient steps, the significant gains in architecture quality and search reliability make it a compelling alternative for automated model design.

Summary updated

Abstract

In this paper, we propose a Shapley value based operation contribution evaluation method (Shapley-NAS) for neural architecture search. Differentiable architecture search (DARTS) acquires the expected architectures by optimizing the architecture parameters with gradient descent, which benefits from the high efficiency due to the significantly reduced search cost. However, DARTS leverages the learnable architecture parameters of the supernet to represent the operation importance during the search process, which fails to reveal the actual impacts of operations on the task performance and therefore harms the effectiveness of obtained architectures. On the contrary, we evaluate the direct influence of operations on accuracy via Shapley value for supernet optimization and architecture discretization, so that the optimal architectures are acquired by selecting the operations that contribute significantly to the tasks. Specifically, we iteratively employ Monte-Carlo sampling based algorithm with early truncation to efficiently approximate the Shapley value of operations, and update weights of the supernet whose architecture parameters are assigned with the operation contribution evaluated by Shapley value. At the end of the search process, operations with the largest Shapley value are preserved to form the final architecture. Extensive experiments on CIFAR-10 and ImageNet for image classification and on NAS-Bench-201 for optimal architecture search show that our Shapley-NAS outperforms the state-of-the-art methods by a sizable margin with light search cost.
BibTeX
@inproceedings{xiao2022shapley,
  author = {Han Xiao and Ziwei Wang and Jiwen Lu and Jie Zhou},
  title = {{Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2022},
  url = {https://openreview.net/forum?id=KM7MS0jATR},
}
Figure