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.
Since calculating exact Shapley values is NP-hard, the authors use two approximation techniques:
- Monte-Carlo Sampling: Estimating the value by sampling a small number of random permutations of operations.
- 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.
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