A Semi-Supervised Assessor of Neural Architectures

Introduction

The impressive successes in computer vision tasks, such as image classification , detection and segmentation , heavily depends on an effective design the backbone deep neural networks, which are usually over-parameterized for the sake of effectiveness. Instead of resorting to human expert experience, Neural Architecture Search (NAS) framework focuses on an automatic way to select hyper-parameters and design appropriate network architectures.

There have been a large body of works on NAS, and they can be roughly divided into two categories. Combinatorial optimization methods search architectures in a discrete space by generating, evaluating and selecting different architectures, e.g. Evolutionary Algorithm (EA) based methods and Reinforcement Learning (RL) based methods . The other kind of NAS methods are continuous optimization based, which relax the original search space to a continuous space and gradient-based optimization is usually applied . In NAS, to get the exact performance of an architecture, it often takes hours or even days for a sufficient training process. Reducing the number of training epochs or introducing the weight sharing mechanism could alleviate prohibitive computational cost, but it would result in inaccurate performance estimation for the architectures. Recently, there are studies to collect many network architectures with known real performance on the specific tasks and train a performance predictor . This one-off training of the predictor can then be applied to evaluate the performance of intermediate searched architectures in NAS, and the overall evaluation cost of an individual architecture can be reduced from hours to milliseconds.

A major bottleneck in obtaining a satisfactory architecture performance predictor could be the collection of a large annotated training set. Given the expensive cost on annotating a neural architecture with its real performance, the training set for the performance predictor is often small, which would lead to an undesirable over-fitting result. Existing methods insist on the fully supervised way to train the performance predictor, but neglect the significance of those neural architectures without annotations. In the search space of NAS, a number of valid neural architectures can be sampled with ease. Though the real performance could be unknown, their architecture similarity with those annotated architectures would convey invaluable information to optimize the performance predictor.

In this paper, we propose to assess neural architectures in a semi-supervised way for training the architecture predictor using the well-trained networks as fewer as possible. Specifically, a very small proportion of architectures are randomly selected and trained on the target dataset to obtain the ground-truth labels. With the help of massive unlabeled architectures, an auto-encoder is used to discover meaningful representations. Then we construct a relation graph involving both labeled and unlabeled architectures to capture intrinsic similarities between architectures. The GCN assessor takes the learned representations of all these architectures and the relation graph as input to predict the performance of unlabeled architectures. The entire system containing the auto-encoder and GCN assessor can be trained in an end-to-end manner. Extensive experiments results on the NAS-bench-101 dataset demonstrate the superiority of the proposed semi-supervised assessor for searching efficient neural architectures.

This paper is organized as follows: in Sec. 2 we briefly review several performance predictors and analyze pros and cons of them, and give an introduction of NAS, GCN and auto-encoder. Sec. 3 gives a detailed implementation of the proposed method. Several experiments conducted on NASBench dataset and the results are shown in Sec. 4. Finally, Sec. 5 summarizes the conclusions.

Related Works

In this section, we first review current methods of NAS and performance predictor, and then introduce the classical GCN and auto-encoder.

Current NAS framework for obtaining desired DNNs can be divided into two sub-problems, i.e., search space and search method.

A well-defined search space is extremely important for NAS, and there are mainly three kinds of search spaces in the state-of-the-art NAS methods. The first is cell based search space . Once a cell structure is searched, it is used in all the layers across the network by stacking multiple cells. Each cell contains several blocks, and each of the block contains two branches, with each branch applying an operation to the output of one of the former blocks. The outputs of the two branches are added to get the final output of the block. The second is Direct Acyclic Graph (DAG) based search space . The difference between cell based and DAG based search space is that the latter does not restrict the number of branches. The input and output number of a node in the cell is not limited. The third is factorized hierarchical search space , which allows different layer architectures in different blocks.

Besides search space, most of the NAS research focus on developing efficient search methods, which can be divided into combinatorial optimization methods and continuous optimization methods. Combinatorial optimization methods include Evolutionary Algorithm (EA) based methods and Reinforcement Learning (RL) based methods . Continuous optimization methods include DARTS , which makes the search space continuous by relaxing the categorical choice of a particular operation to a softmax over all possible operations, and several one-shot methods that solve the problem in a one-shot procedure . Recently, architecture datasets with substantial full-trained neural architectures are also proposed to compare different NAS methods conveniently and fairly .

2 NAS Predictor

There are limited works focusing on predicting the network performance. Some of the previous works were designed on hyper-parameter optimization with Gaussian Process , which focus on developing optimization functions to better evaluate the hyper-parameter. Other methods directly predict the performance of a given network architecture. The first way is to predict the final accuracy by using part of the learning curves with a mixture of parametric functions , Bayesian Neural Network or $v$-SVR . The second way is to predict the performance of a network with a predictor. Deng et al. extract the feature of a given network architecture layer by layer, and the features with flexible length are sent to LSTM to predict the final accuracy. Istrate et al. use a similar manner to predict the accuracy with random forest, believing that few training data are required by using random forest. Luo et al. propose an end-to-end manner by using an encoder to extract features of the networks. The learned features are optimized with gradient descent and then decoded into new architectures with an decoder. The architecture derived in this way is regarded as the optimal architecture with a high performance.

3 Graph Convolutional Network (GCN)

GCN is a prevalent technique tackling data generated from non-Euclidean domains and represented as graphs with complex relation. Sperduti et al. first tackle DAGs with neural networks and recently GCNs achieve the-state-of-art performance in multiple tasks, such as citation networks , social networks and point clouds data analyses . Both graph-level task and node level tasks can be tackled with GCNs. For a graph-level task, each graph is seen as an individual and the GCN is to predict the labels of those graphs. As for node-level tasks, the examples are seen as vertices of a graph which reflects the relation between them, and the labels of examples are predicted by the GCN with the help of graph. Beyond the features of examples, the graph also provides extra valuable information and improves prediction accuracy.

Approach

Consider the search space $X=X^{l}\bigcup X^{u}$ with $N=N_{l}+N_{u}$ architectures, where $X^{l}=\{{\bm{x}}^{l}_{1},{\bm{x}}^{l}_{2},\cdots,{\bm{x}}^{l}_{N_{l}}\}$ are annotated architectures with the corresponding ground-truth performance ${\bm{y}}^{l}=\{y^{l}_{1},y^{l}_{2},\cdots,y^{l}_{N_{l}}\}$, and $X^{u}=\{{\bm{x}}^{u}_{1},{\bm{x}}^{u}_{2},\cdots,{\bm{x}}^{u}_{N_{u}}\}$ are the remaining massive unlabeled architectures. The assessor $\mathcal{P}$ is to take the architecture $x_{i}\in X$ as the input and output the estimated performance $\hat{y}_{i}=\mathcal{P}(W_{p},{\bm{x}}_{i})$, where $W_{p}$ is the trainable parameters of the assessor $\mathcal{P}$. Given a sufficiently large labeled architecture set as the training data, the assessor $\mathcal{P}$ can be trained in a supervised manner to fit the ground truth performance , i.e.,

Before sending neural architectures to the performance predictor, we need an encoder $\mathcal{E}$ is to get the appropriate embedding of architectures. There are already some common hand-crafted representations of architectures for specific search spaces. For example, Ying et al. represent the architectures in a Directed Acyclic Graph (DAG) based search space with adjacency matrices, where 0 represents no connection between two nodes and the non-zero integers denote the operation types. Though these hand-crafted representations can describe different architectures, they are usually redundant and noisy to express the intrinsic property of architectures. In contrast with this manual approach, we aim to discover more effective representations of neural architectures with an auto-encoder.

A classical auto-encoder contains two modules: the encoder $\mathcal{E}$ and decoder $\mathcal{D}$. $\mathcal{E}$ takes the hand-crafted representations of both labeled architectures ${\bm{x}}^{l}\in X^{l}$ and unlabeled architectures ${\bm{x}}^{u}\in X^{u}$ as input and maps them to a low-dimension space. Then the learn compact representation are sent to the decoder $\mathcal{D}$ to reconstruct the original input. The auto-encoder is trained as:

where $W_{e}$ and $W_{d}$ are the trainable parameters of the encoder $\mathcal{E}$ and decoder $\mathcal{D}$, respectively${\bm{x}}_{i}^{l}$ and ${\bm{x}}_{i}^{u}$ in Eq. (2) also denote the hand-crafted representations of the architectures without ambiguity.. The feature $\mathcal{E}({\bm{x}}_{i})$ for architectures ${\bm{x}}_{i}\in X$ learned by the auto-encoder can be more compact representations of architectures. Most importantly, the auto-encoder can be optimized together with the predictor $\mathcal{P}$ in an end-to-end manner, which enables feature $\mathcal{E}({\bm{x}}_{i})$ to be more compatible with $\mathcal{P}$ to predict the performance of architectures.

2 Semi-supervised Architecture Assessor

The architectures in a search space are not independent and there are some intrinsic relation between architectures. For example, an architecture can always be obtained by slightly modifying a very ‘similar’ architecture, such as replacing an operation type, adding/removing an edge, changing the width/depth and so on. Most importantly, beyond the limited labeled architectures, the massive unlabeled architectures in search space would also be helpful for the training of assessor $\mathcal{P}$, because of their underlying connections with those labeled architectures. Though obtaining the real performance of all architectures is impossible, exploiting the large volume of unlabeled architectures and exploring intrinsic constraints underlying different architectures will make up the insufficiency of labeled architectures.

Based on the learned representation $\mathcal{E}({\bm{x}}_{i})$ of architectures, we adopt the common Radial Basis Function (RBF) to define the similarity measure $s({\bm{x}}_{i},{\bm{x}}_{j})$ between architectures ${\bm{x}}_{i}\in X$ and ${\bm{x}}_{j}\in X$ , i.e.,

where $d(\cdot,\cdot)$ denotes the distance measure (e.g., Euclidean distance) and $\sigma$ is a scale factor. $s({\bm{x}}_{i},{\bm{x}}_{j})$ ranges in and $s({\bm{x}}_{i},{\bm{x}}_{i})=1$. When the distance between representation $\mathcal{E}({\bm{x}}_{i})$ and $\mathcal{E}({\bm{x}}_{j})$ becomes larger, the similarity $s({\bm{x}}_{i},{\bm{x}}_{j})$ decreases rapidly.

To utilize both limited labeled architectures and massive unlabeled architectures with their similarity modeled by the graph $G$, we construct the assessor $\mathcal{P}$ by stacking multiple graph convolutional layers, which takes the learned representations of both labeled and unlabeled architectures as inputs. The graph $G$ is also embedded into each layer and guides the information propagation between the features of different architectures. Taking all these architectures as a whole and utilizing the relation between architectures, the assessor $\mathcal{P}$ outputs their estimated performance. A assessor $\mathcal{P}$ composing of two graph convolutional layers is:

where $\mathcal{E}([X^{l},X^{u}])$ denotes the learned representations of both labeled and unlabeled architectures, and $\hat{\bm{y}}^{l}=\{\hat{y}^{l}_{1},\hat{y}^{l}_{2},\cdots,\hat{y}^{l}_{N_{l}}\}$ and $\hat{\bm{y}}^{u}=\{\hat{y}^{u}_{1},\hat{y}^{u}_{2},\cdots,\hat{y}^{u}_{N_{u}}\}$ are their estimated performance, respectively. $D$ is a diagonal matrix where $D_{ii}=\sum_{j}{A}_{ij}$, and $\hat{A}=D^{-\frac{1}{2}}{A}D^{-\frac{1}{2}}$. $W^{(0)}_{p}$, $W^{(1)}_{p}$ are the weight matrices.

As shown in Eq. (4), the output of the assessor $\mathcal{P}$ depends on not only their input representation but also the neighboring architectures in the graph $G$ due to adjacency matrix $A$, and thus the performance prediction processes of labeled and unlabeled architectures interact with each other. In fact, GCN can be considered as a Laplacian smoothing operator and intuitively, two connected nodes on the graph tend to have similar features and produce similar outputs. As both labeled and unlabeled architectures are sent to the predictor simultaneously, their intermediate features interrelate with each other.

The assessor $\mathcal{P}$ is trained to fit the ground-truth performance of labeled architectures based as both the architectures themselves and the relation between them, i.e.,

where $W_{p}$ is the trainable parameter of assessor $\mathcal{P}$. Though the supervised loss is only applied on labeled architectures, the unlabeled architectures also participate in the performance prediction of the labeled architectures via the relation graph $G$, and thus the supervision information from those limited performance labels can guide the feature generation process of those unlabeled architectures. Intuitively, the labels can propagate along the edge in the relation graph $G$, considering the length of paths and the weights of edges. What’s more, the training process helps the predictor learn to predict the performance of a given architecture with the assistance of its neighbors in the graph $G$, which makes the prediction more robust and improve the prediction accuracy.

3 Optimization

The auto-encoder and assessor can constitute an end-to-end system, which learns the representations of architectures and predict performance simultaneously. As shown in Figure 1, the hand-crafted representations of both labeled architectures $X^{l}$ and unlabeled architectures $X^{u}$ are first delivered into the encoder $\mathcal{E}$ to produce learned representations $\mathcal{E}([X^{l},X^{u}])$, and then the relation graph $G$ is constructed based on the representation $\mathcal{E}([X^{l},X^{u}])$ via Eq. (3). Both the representation $\mathcal{E}([X^{l},X^{u}])$ and relation graph $G$ are sent to the GCN assessor $\mathcal{P}$ to get the estimated performance $\hat{\bm{y}}$. In the training phase, the learned representations $\mathcal{E}([X^{l},X^{u}])$ are also sent to the decoder $\mathcal{D}$ to reconstruct the original input. Combining the regression loss $\mathcal{L}_{rg}$ that fits the ground-truth performance and the reconstruction loss $\mathcal{L}_{rc}$ , the entire system is trained as:

where $\lambda\in$ is the hyper-parameter that balances the two types of loss functions. In the end to end system, the learning of architecture representations and performance prediction are promoted mutually. The regression loss $\mathcal{L}_{rg}$ focuses on fitting the ground-truth performance of labeled architectures and propagating labels to the unlabeled architectures, which also makes the learned representations $\mathcal{E}([X^{l},X^{u}])$ have stronger relativity to the ground-truth performance. The reconstruction loss $\mathcal{L}_{rc}$ refines information from the massive unlabeled architectures to supply the limited labeled examples and makes the training process more robust. Note that for both regression loss $\mathcal{L}_{rg}$ and reconstruction loss $\mathcal{L}_{rc}$, the unlabeled architectures participate in their optimization process and play an important role.

When implementing the proposed semi-supervised assessor to a large search space containing massive architectures, it is inefficient to construct a large graph containing all the $N$ architectures. Constructing the graph needs to calculate the similarity of arbitrary two architectures which is time-consuming, and storing such a graph also needs a large memory. Mini-batch is a common strategy to tackle big data in deep learning , and we propose to construct the graph and train the entire system with mini-batch. For each mini-batch, labeled and unlabeled architectures are randomly sampled from $X^{l}$ and $X^{u}$, and the graph is constructed with those examples. Thus the entire system can be trained efficiently with random gradient descent on memory-limited GPUs. The mini-batch training algorithm is presented in Algorithm 1.

Experiments

In this section, we conduct extensive experiments to validate the effectiveness of the proposed semi-supervised assessor. Firstly, the performance prediction accuracies of our method are compared with several state-of-the-art methods. Then we embed the proposed assessor and peer competitors to the combinatorial searching algorithm (such as evolutionary algorithm) to identify architectures with good performance. Ablation studies are also conducted to further analyze the proposed method.

Dataset. Nas-Bench-101 is the largest public architecture dataset for NAS research proposed recently, containing 423K unique CNN architectures trained on CIFAR-10 for image classification, and the best architecture achieves a test accuracy of 94.23%. The search space for Nas-Bench-101 is a feed-forward structure stacked by blocks and each block is constructed by stacking the same cell 3 times. As all the network architectures in the search space are trained completely to get their ground-truth performance, it is fair and convenient to compare different performance prediction methods comprehensively on Nas-Bench-101. A more detailed description of the dataset can be referred to . Besides Nas-Bench-101, we also construct a small architecture dataset on CIFAR-100 to verify the effectiveness of the methods on different datasets.

Implementation details. The encoder $\mathcal{E}$ is constructed by stacking two convolutional layers followed by a full-connected layer and the decoder $\mathcal{D}$ is the reverse. The inputs of $\mathcal{E}$ are the matrix representations of architectures following . The assessor $\mathcal{P}$ consists of two graph convolutional layers and outputs the predicted performance. The scale factor $\sigma$ and threshold $\tau$ for constructing graph are set to 0.01 and $10^{-5}$, and $\lambda$ in Eq. (6) is set to 0.5 empirically. The entire system is trained end-to-end with Adam optimizer without weight decay for 200 epochsThe auto-encoder is first pre-trained as initialization for optimization stabilization.. The batch size and initial learning rate are set to 1024 and 0.001, respectively. All the experiments are conducted with Pytorch library on NVIDIA V100 GPUs.

We compare the proposed method with the state-of-the-art predictors based methods Peephole and E2EPP . Since the main function of the performance predictors is to identify better architectures in a search space, accurate performance ranking of architectures is more important than their absolute values. KTau $\in$ is a common indicator measuring the correlation between the ranking of prediction values and the actual labels, and higher values mean more accurate prediction. Two other common criteria mean square error (MSE) and correlation coefficient (r) are also compared for completeness. MSE measures the deviation of predictions from the ground truth directly, and r $\in$ measures the correlation degree between prediction values and true labels.

The experimental results are shown in Table 1. We randomly sample $N_{l}$ architectures from the search space (including 423k architectures) as labeled examples, and varies $N_{l}$ from {1k, 10k, 100k}. All possible architectures are available once the search space has been given, and thus the remaining architectures are used as unlabeled architectures, i.e., $N^{u}=N-N^{l}$. As shown in Table 1, the proposed semi-supervised assessor surpasses the state-of-the-art methods on three criteria with different number of labeled examples. For example, with 1k labeled architectures, KTau of our method can achieve 0.6541, which is 0.2168 higher than Peephole (0.4373) and 0.0836 higher than E2EPP (0.5705), meaning more accurate predicted ranking. The correlation coefficient $r$ is also improved by 0.1227 and 0.0773, indicating higher correction between predicted values and ground-truth labels using our method. The improved performance comes from more thorough exploitation of the information in the search space, which makes up the insufficiency of labeled data. Note that increasing $N_{l}$ improves the performance of all these methods, but the computational cost of training these architectures is also increased. Thus, the balance between the performance of the predictors and the computation cost of getting labeled examples needs to be considered in practice.

The qualitative results are shown in Figure (2). For clarity, 5k architectures are randomly sampled and shown in the scatter diagrams. The $x$-axis of each point (architecture) is its ground truth ranking and the $y$-axis is predicted ranking. For our method the points are much closer to the diagonal line, implying stronger consistency between the predicted ranking and ground truth ranking. Both the numerical criteria and intuitive diagrams show that our method surpasses the state-of-the-art methods.

2 Searching Results on NAS-Bench-101

The performance predictors can be embedded to various architecture search algorithms such as random search, Reinforcement learning (RL) based methods and Evolutionary Algorithm (EA) based methods . Taking EA based methods as an example, the performance predicted by the predictors can be used as fitness, and other progresses including population generation, cross-over and mutation are not changed. Since we focus on the design of performance predictors, we embed different prediction methods into EA to find the architectures with high performance. Concretely, we compare the best performance among the top-10 architectures selected by different methods, and all the methods are repeated 20 times with different random seeds.

The performance of the best architecture selected by different methods is shown in Table 2. The second column is the accuracies of architectures on CIFAR-10 dataset and the third column is their real performance rankings in all the architectures of Nas-Bench-101. The best network identified by the proposed semi-supervised assessor achieves performance 94.01%, outperforming the compared methods (93.41% for Peephole and 93.77%) by a large margin, since the proposed method can make a more accurate estimation of performance and further identify those architectures with better performance. Though only 1k architectures are sampled to train the predictor, it can still find the architectures whose real performance is in the top 0.01% of the search space. Compared to the global best architecture with performance 94.23%, which is obtained by exhaustively enumerating all the possible architectures in the search space, the performance 94.01% obtained by our method with only 1k labeled architectures is comparable.

We further show the intuitive representation of the best architectures identified by different methods in Figure 3. There are some common characteristics for these architectures with good performance, e.g., both existing a very short path (e.g., path length 1) and a long path from the first node to the last. The long path consisting of multiple operations ensures the representation ability of the networks, and the short path makes gradient propagate easily to the shallow layers. The architecture identified by our method (Figure 3(c)) also contains a max pooling layer in the longest path to enlarge the receptive field, which may be a reason for the better performance.

3 Experiments on CIFAR-100 Dataset

To verify the effectiveness of the proposed semi-supervised assessor in different datasets, we further conduct experiments on the common object classification dataset CIFAR-100. Since there is no architecture dataset with ground-truth performance based on CIFAR-100, we randomly sample 1k architectures from the search space of NAS-bench-101 and train them completely from scratch using the same training hyper-parameters in . With the 1k labeled architectures, different performance prediction methods are embedded into the EA to find the best performance. As CIFAR-100 contains 100 categories, we both compare the top-1 and top-5 accuracies. The best performance among the top-10 architectures are compared and all the methods are repeated for 20 times with different random seeds.

The accuracies and diagrams of different architectures are shown in Table 3 and Figure 4, respectively. The best architecture identified by our method achieves much higher performance (78.64% for top-1 and 94.23% for top-5) compared with the state-of-the-art methods (e.g., 75.86% for top-1 and 93.11% for top-5 in E2EPP). It implies that exploring the relation between architectures and utilizing the massive unlabeled examples in the proposed method works well in different datasets.

4 Ablation study

The impact of scale factor $\sigma$. The hyper-parameter $\sigma$ impacts the similarity measurement in Eq. (3) and thereby impacts the construct of the graph. With a fixed threshold $\tau$, a denser graph $G$ is constructed with a bigger $\sigma$, and more interaction between different architectures is applied when predicting performance with the GCN assessor. The prediction results with different scale factor $\sigma$ are shown in Figure 5(a), which verifies the effectiveness of utilizing unlabeled architectures with a relation graph to train a more accurate performance predictor. An excessive $\sigma$ also incurs the drop of accuracies in Figure 5(a), as putting too much attention on other architectures also disturb the supervision training process.

The impact of weight $\lambda$. The weight $\lambda$ balances the regression loss $\mathcal{L}_{rg}$ and the reconstruction loss $\mathcal{L}_{rc}$. When the reconstruction loss do not participate in the training process ($\lambda=0$), prediction accuracies (Ktau and $r$) are lower than those with reconstruction loss as shown in Figure 5(b), since the information in massive unlabeled architectures is not well preserved when constructing the learned architecture representation.

The number of unlabeled architectures $N^{u}$. The unlabeled architectures can provide extra information to assist the training of the architecture assessor to make an accurate prediction. As shown in Figure 5, with the increasing of unlabeled architectures, both the two criteria KTau and $r$ are increased correspondingly, indicating more accurate performance prediction. The improvement of accuracies comes from that more information is provided by the unlabeled architectures. When the number of unlabeled architectures is enough to reflect the property of the search space (e.g., $N^{u}=50k$), adding extra unlabeled architectures only brings limited accuracy improvement.

The effect of auto-encoder. To show the superiority of the learned representations compared with the hand-craft representations, the prediction results with or without the auto-encoder are shown in Table 4. The prediction accuracies (Ktau) are improved obviously by the deep auto-encoder (e.g., 0.6541 v.s. 0.5302 with 1k labeled architectures), which indicates the learned representations can reflect the intrinsic characteristics and more compatible to measure architecture similarity and used as the inputs of performance predictor.

Conclusion

The paper proposes a semi-supervised assessor to evaluate the network architectures by predicting their performance directly. Different from the conventional performance predictors trained in a fully supervised way, the proposed semi-supervised assessor takes advantage of the massive unlabeled architectures in the search space by exploring the intrinsic similarity between architectures. Meaningful representations of architectures are discovered by an auto-encoder and a relation graph involving both labeled and unlabeled architectures is constructed based on the learned representations. The GCN assessor takes both the representations and relation graph to predict the performance. With only 1k architectures randomly sampled from the large NAS-Benchmark-101 dataset , the architecture with $94.01\%$ accuracy (top $0.01\%$ of the entire search space) can be found with the proposed method. We plan to investigate the sampling strategy to construct more representative training sets for the assessor and identify better architectures with fewer labeled architectures in the future.

Acknowledgment

This work is supported by National Natural Science Foundation of China under Grant No. 61876007, 61872012, National Key R&D Program of China (2019YFF0302902), Australian Research Council under Project DE-180101438, and Beijing Academy of Artificial Intelligence (BAAI).

References