  In this paper, we propose a Shapley value based method to evaluate operation
contribution (Shapley-NAS) for neural architecture search. Differentiable
architecture search (DARTS) acquires the optimal architectures by optimizing
the architecture parameters with gradient descent, which significantly reduces
the search cost. However, the magnitude of architecture parameters updated by
gradient descent fails to reveal the actual operation importance to the task
performance and therefore harms the effectiveness of obtained architectures. By
contrast, we propose to evaluate the direct influence of operations on
validation accuracy. To deal with the complex relationships between supernet
components, we leverage Shapley value to quantify their marginal contributions
by considering all possible combinations. Specifically, we iteratively optimize
the supernet weights and update the architecture parameters by evaluating
operation contributions via Shapley value, so that the optimal architectures
are derived by selecting the operations that contribute significantly to the
tasks. Since the exact computation of Shapley value is NP-hard, the Monte-Carlo
sampling based algorithm with early truncation is employed for efficient
approximation, and the momentum update mechanism is adopted to alleviate
fluctuation of the sampling process. Extensive experiments on various datasets
and various search spaces show that our Shapley-NAS outperforms the
state-of-the-art methods by a considerable margin with light search cost. The
code is available at https://github.com/Euphoria16/Shapley-NAS.git
