# Masked Diffusion with Task-awareness for Procedure Planning
in Instructional Videos

Fen Fang1, Yun Liu1, Ali Koksal1, Qianli Xu1, Joo-Hwee Lim1,2

###### Abstract

A key challenge with procedure planning in instructional videos lies in how to
handle a large decision space consisting of a multitude of action types that
belong to various tasks. To understand real-world video content, an AI agent
must proficiently discern these action types (e.g., _pour milk_ , _pour water_
, _open lid_ , _close lid_ , etc.) based on brief visual observation.
Moreover, it must adeptly capture the intricate semantic relation of the
action types and task goals, along with the variable action sequences.
Recently, notable progress has been made via the integration of diffusion
models and visual representation learning to address the challenge. However,
existing models employ rudimentary mechanisms to utilize task information to
manage the decision space. To overcome this limitation, we introduce a simple
yet effective enhancement - a masked diffusion model. The introduced mask acts
akin to a task-oriented attention filter, enabling the diffusion/denoising
process to concentrate on a subset of action types. Furthermore, to bolster
the accuracy of task classification, we harness more potent visual
representation learning techniques. In particular, we learn a joint visual-
text embedding, where a text embedding is generated by prompting a pre-trained
vision-language model to focus on human actions. We evaluate the method on
three public datasets and achieve state-of-the-art performance on multiple
metrics. Code is available at https://github.com/ffzzy840304/Masked-PDPP.

Figure 1: Searching and sorting action sequences from a large set of action
types is challenging. Projected diffusion (top left) uses task class as a
condition that does not restrict the decision space effectively. We propose
masked diffusion (top right) to explicitly manage the decision space.
Additionally, text embedding is used to enhance task classification and
subsequent action sequence generation.

## Introduction

Learning procedural knowledge from instructional videos - a natural ability of
humans - presents a tough challenge to artificial intelligence (AI). It
requires multiple aspects of cognitive and reasoning abilities such as scene
understanding, event segmentation and discovery, action recognition and
prediction, and causal reasoning (Zhou, Xu, and Corso 2018; Zhou et al. 2023).
Building an AI agent with these capabilities is a pressing task for the AI
community and has broad implications for real-world applications, e.g., to
monitor human behaviors or to assist humans in collaborative tasks. In this
paper, we focus on a sub-field of instructional video understanding, namely
learning goal-directed actions from real-world videos, and subsequently
generate feasible plans. In particular, we follow the work of (Chang et al.
2020) and cast the problem as procedure planning in instructional videos,
which requires a model to generate action plans given the visual observations
of a start state and a goal state (an example of _making jello_ is illustrated
in Figure 1 \- bottom). Moreover, we adopt the challenging problem setting of
learning with weak supervision, i.e., to learn procedure knowledge without
requiring intermediate visual observations (Zhao et al. 2022). Instead, only
action labels are provided, which alleviates the costly annotation of the
start and end times of each intermediate step.

A key challenge with procedure planning in instructional videos lies in how to
handle a large decision space consisting of a multitude of action types that
belong to many tasks. For example, there are 778 action types from 180 task
classes in the COIN dataset (Tang et al. 2019). Since the datasets are
collected from real-world videos at scale, the distribution of actions is
largely unknown. In the current problem setting, the visual observations are
essentially a pair of images (start and goal states) that are stochastically
drawn from a video, and hence it is extremely difficult to recognize them from
visual observations. Moreover, planning a sequence of actions from a large
pool of actions is even more challenging considering the complicated semantic
relationships between action types and task goals. This is exacerbated by the
existence of multiple viable action plans to accomplish a specific task goal
(Bi, Luo, and Xu 2021).

Early works on procedure planning have employed a two-branch autoregressive
approach while adopting different network architectures to model the
probabilistic process. These include the dual dynamics networks (DDN) (Chang
et al. 2020), Bayesian Inference using exterior generative adversarial
imitation learning (Ext-GAIL) (Bi, Luo, and Xu 2021), and Transformers (Sun et
al. 2021). One limitation of these methods is related to the autoregressive
process, which is slow and subject to error propagation. Moreover, they
require the costly observation of intermediate states as supervisory signals.
In contrast, a single-branch non-autoregressive model is proposed that not
only simultaneously predicts all intermediate steps, but more importantly
alleviates the need for intermediate visual observations (Zhao et al. 2022).
However, this method involves a complicated training process on multiple loss
functions to manage a large design space. Recently, a diffusion-based
probabilistic model is proposed to generate procedure plans non-
autoregressively (Wang et al. 2023a). It adopts a two-stage process, namely
task classification and action sequence generation. The former aims to capture
contextual information and used it as a conditional constraint in the latter
step. However, as illustrated in Figure 1 and shown by our results, using the
task class as the condition has a limited effect on reducing the design space,
i.e., decisions are still made with respect to a large pool of action types.

In this study, we propose a masked diffusion model to use task knowledge as
context constraints. Instead of using task labels as a soft condition as in
(Wang et al. 2023a), we propose to generate a task-oriented mask to directly
restrict the search space of action prediction. As shown in Figure 1, action
plans are generated on a greatly reduced subset of action types, owning to the
task-guided mask. It helps to reduce the dimensionality of the decision space
and enforces stronger hierarchical reasoning. Considering the possible adverse
effect of inaccurate task classification, we further enhance visual
representation learning via action-aware visual captioning based on pre-
trained vision-language models (VLMs). In particular, a text embedding is
obtained by prompting a frozen VLM (e.g., LLaVA) (Liu et al. 2023) to focus on
the human actions in the current visual scene. We use text-enhanced multimodal
embedding to both improve task classification and enhance action planning on
the masked diffusion model.

Contributions: (1) We propose a novel masked diffusion model to harness task
information and enforce hierarchical procedure planning. Multiple strategies
of masking operation are designed and evaluated to show the effectiveness of
masking. (2) We enhance visual representation learning with an action-aware
text embedding generated from a VLM in a zero-shot manner. We achieve state-
of-the-art performance on multiple datasets under different testing
conditions. These show the effectiveness of masked diffusion in planning under
uncertainty and the potential of text-enhanced representation learning in
procedure planning.

## Related Work

#### Action sequence modeling

To handle complexities related to a large decision space, early works in
procedure planning resort to solutions in probabilistic reasoning for goal-
directed planning, such as universal planning networks (Srinivas et al. 2018),
uncertainty-aware action anticipation (Abu Farha and Gall 2019), and causal
InfoGAN (Kurutach et al. 2018). However, these models have limited capacity in
handling complexities in the scenes of instructional videos. The DDN model
(Chang et al. 2020) learns the latent space via the interplay of a transition
model and conjugate model, but suffers from compounding error. An Ext-GAIL
model is proposed to separately handle time-invariant context knowledge and
the casual relationship among actions, where a stochastic model is used to
explicitly capture the distribution of plan variants during training (Bi, Luo,
and Xu 2021). The PlaTe model adopts transformer-based visual grounding and
planning (Sun et al. 2021), but has limited capacity to handle uncertainty.
The above approaches suffer from slow convergence and error propagation owing
to the auto-regressive reasoning process.

Recently, a memory-enhanced probabilistic procedure planning framework is
proposed, which adopts weak and adversarial supervision (Zhao et al. 2022).
The method handles uncertainty by combining a pre-trained global memory unit,
an adversarial generative model, and a Viterbi post-processing method.
However, it involves a complicated training scheme and tedious inference
process owing to the computation of multiple loss functions and the
brittleness of training GANs. It is also restricted by the limited capability
of a small-sized global memory with a fixed structure. The closest work to
ours is the projected diffusion procedure planning (PDPP) model (Wang et al.
2023a), which leverages the power of diffusion models to tackle complexity.
However, task information is used as a “soft” condition in the representation,
resulting in weak guidance to action planning. Moreover, task classification
is performed using a simple multilayer perceptron (MLP) on standard visual
embedding, which may not fully capture the value of the task context. We
anticipate that context/task knowledge is crucial in effective and efficient
procedure planning as is shown by numerous empirical evidences in hierarchical
procedure planning (Ashutosh et al. 2023; Nair and Finn 2019; Liu et al. 2022;
Pertsch et al. 2020).

#### Visual representation learning

Visual reasoning can be enhanced by stronger visual representation learning.
In the current problem formulation, the AI agent needs to infer the task type
and generate action sequences based solely on two “peeks” into the start and
goal states. Recently, notable progress has been made to train and fine-tune
large VLMs (Zhao et al. 2023; Xu et al. 2021; Lin et al. 2022; Liu et al.
2023), which is partially driven by the availability of large-scale
instructional video datasets (Zhukov et al. 2019; Tang et al. 2019; Damen et
al. 2020; Miech et al. 2019; Grauman et al. 2022). The latest models usually
use knowledge from the language domain (e.g., wikiHow) as distant supervision
signals (Zhong et al. 2023; Zhou et al. 2023; Lin et al. 2022). However, the
computational cost of training/fine-tuning large VLMs is usually prohibitively
high. Alternatively, efforts have also been made to use pre-trained large
language models (LLMs) as a visual planner (Patel et al. 2023; Wang et al.
2023b), leveraging the zero-shot reasoning ability of powerful foundation
models (Ge et al. 2023; Kim et al. 2022; OpenAI 2023; Touvron et al. 2023).
However, there is still a notable performance gap due to the lack of domain
knowledge. Another stream of research resorts to graph-based representation to
capture visual semantics of procedures, ranging from conventional neural task
graph (Huang et al. 2019) to sophisticated transformer-based models (Rampášek
et al. 2022; Mao et al. 2023; Zhou et al. 2023). One drawback of these models
is that they are usually complex with an additional medium of graph
representation.

Figure 2: Overview of our masked diffusion model with task-awareness. A frozen
Visual-language model (VLM) generates text embedding of the start and goal
states based on action-oriented prompts. An action mask is generated based on
task class to restrict the action types.

## Method

### Problem Formulation

Given the visual observations of a start state ($o_{s}$) and a goal state
($o_{g}$), the procedure planning task is to produce a plan in the form of a
sequence of actions $a_{1:T}$ that, when executed, will enable the transition
from $o_{s}$ to $o_{g}$ in $T$ steps, where $T$ is called the horizon of
planning. Similar to (Wang et al. 2023a), we decompose the task into two
steps: (1) predicting the task category (e.g., make sandwich, assemble bed),
and (2) generating action sequences conditioned on the predicted task
category. The decision process can be formulated as

$p(a_{1:T}|o_{s},o_{g})=\int p(a_{1:T}|o_{s},o_{g},c)p(c|o_{s},o_{g})dc.$ (1)

The system architecture is shown in Figure 2. As mentioned earlier, using task
information as a condition does not exert sufficient modulation power on
search space reduction. To address this issue, we propose a new strategy to
make use of the task information, namely to generate a mask to restrict the
decision space to a subset of “promising” actions. Notably, such a masking
approach is different from masked diffusion transformers (Zheng et al. 2023;
Gao et al. 2023). The latter aim to strengthen the model’s ability to learn
context information for image generation, whereas we use masks to restrict the
decision space.

### Action-aware Visual Representation Learning

In (Wang et al. 2023a), the task classifier is a simple MLP that takes the
concatenated visual embedding of the start and goal state as input. In our
model, task class plays an important role in the diffusion process by
generating a mask to constrain the design space. Therefore, it is important to
improve the accuracy of task classification. We propose two techniques to
address this issue. First, we employ a Transformer model (e.g., ViT) (to
replace the original MLP) that takes $o_{s}$ and $o_{g}$ (based on joint
vision-text embedding) to predict the task class ($c$). Second, we enhance the
visual representation by affixing an action-aware text embedding to the visual
embedding. It is observed that prevalent image encoders are pre-trained on
generic instructional videos, such as Howto100M (Miech et al. 2019), which
does not possess sufficient ability to discriminate refined human actions.
Fine-tuning such models is both costly and may jeopardize their
generalisability. Meanwhile, numerous VLMs have been developed that show
impressive descriptive power and flexibility. We adopt LLaVA (Liu et al. 2023)
with frozen network weights111Other VLM models can be used to achieve similar
outcome. and prompt it to concentrate on the human actions in the visual
input, e.g., “ _Please briefly describe_ [Image] _focusing on the human
actions_ ”. A list of candidate prompts is included in the supplementary
material. Despite the explicit request for brevity, the generated description
may still be verbose and not suitable for subsequent reasoning. Therefore, we
design a simple routine to extract the key words in the form of
$verb+noun(s)+[optional]adverb(s)$. For example, in Figure 2, the raw
description of the start state can be “ _In the image, a person is pouring
water into an electric kettle from a faucet._ ”. The routine can extract the
key information, such as “ _pour water into an electric kettle_ ”. Textual
descriptions of $o_{s}$ and $o_{g}$ are fed into a pre-trained text encoder to
generate the text embedding of the two states. Finally, the text embedding is
concatenated with the visual embedding, resulting in the text-enhanced
representation $(o^{VT}_{s},o^{VT}_{g})$.

### Masked Diffusion Model

In a standard diffusion model (Ho, Jain, and Abbeel 2020), a forward diffusion
process involves incremental addition of Gaussian noise
$\epsilon\sim\mathcal{N}(0,\,\mathbf{I})$ to the input data ($x_{0}$, i.e.,
the true signal) until it degrades to a random Gaussian distribution $x_{t}$.
The process is parameterized via a Stochastic Differential Equation (SDE):

$\displaystyle
q(x_{n},x_{0})=\sqrt{\overline{\alpha}_{n}}x_{0}+\epsilon\sqrt{1-\overline{\alpha}_{n}},$
(2) $\displaystyle
q(x_{n}|x_{n-1})=\mathcal{N}(x_{n};\sqrt{1-\beta_{n}}x_{n-1},\beta_{n}\mathbf{I}),$

where $\overline{\alpha}_{n}=\prod_{s=1}^{n}(1-\beta_{s})$ denotes the noise
magnitude, and $\beta_{s}\in(0,1)_{s=1}^{t}$ specifies the ratio of Gaussian
noise added to the signal in each step.

Similarly, the reverse denoising process gradually maps a Gaussian noise into
the sample via a discrete SDE:

$p_{\theta}(x_{n-1}|x_{n})=\mathcal{N}(x_{n-1};\mu_{\theta}(x_{n},n),\textstyle{\sum_{\theta}}(x_{n},n)).$
(3)

The network is trained by optimizing the variational lower-bound of
$p_{\theta}(x_{0})$, based on which $\sum_{\theta}(x_{n},n)$ can be obtained.
Meanwhile, $\mu_{\theta}(x_{n},n)$ is reparameterized as a noise prediction
network $\epsilon_{\theta}(x_{n},n)$, which is trained with a simple mean-
squared error loss $L=||\epsilon-\epsilon_{\theta}(x_{n},n)||^{2}$. After
training, the model can recover the signal $x_{0}$ from random Gaussian noise.

We construct the input signal by concatenating three elements, namely (1) the
text-enhanced visual observations of the start and goal states
$(o^{VT}_{s},o^{VT}_{g})$, (2) the predicted task class ($c$), and (3) a
sequence of candidate actions $(a_{1:T})$, i.e.
$x=[(o^{VT}_{s},o^{VT}_{g}),c,a_{1:T}]$. Different from (Wang et al. 2023a),
the candidate action sequence is affixed with a binary mask (e.g., ‘1’ for
active actions in the predicted task class, ‘0’ for other actions) that is
specified by the task class. In practice, the loss function is computed on $x$
with respect to the unmasked actions, $x^{m}$. The task-specific mask is
derived from the mapping relationship between a task class and the action
types, which can be obtained from ground truth during training. In essence,
despite the fact that an individual action planning instance does not have the
complete list of action types with respect to the task, one can simply include
all action types for a specific task from many instances and remove the
duplicates.

We adopt a similar condition project scheme on the task class and observations
as in (Wang et al. 2023a). Consistent with the premise that the initial and
terminal actions are more important due to their primacy and recency effects,
additional weights are assigned to these specific actions. The projection
operation $Proj()$ in our model is defined as

$\begin{matrix}\begin{bmatrix}\hat{c}_{1}&\hat{c}_{2}&&\hat{c}_{T}\\\
w\hat{a}_{1}^{m}&\hat{a}_{2}^{m}&...&w\hat{a}_{T}^{m}\\\
\hat{o}_{1}&\hat{o}_{2}&&\hat{o}_{T}\end{bmatrix}&\rightarrow&\begin{bmatrix}c&c&&c\\\
w\hat{a}_{1}^{m}&\hat{a}_{2}^{m}&...&w\hat{a}_{T}^{m}\\\
o_{s}^{VT}&0&&o_{g}^{VT}\end{bmatrix}\\\ x^{m}&&Proj(x^{m})\end{matrix},$ (4)

where $\hat{c}_{i}$, $\hat{o}_{i}$ and $\hat{a}_{i}^{m}$ refer to the $i^{th}$
horizon task class, observation dimensions and predicted masked action logits
in masked representation $x^{m}$, respectively. $c$, $o_{s}^{VT}$,
$o_{g}^{VT}$ represent the specified conditions.

The projection operation in Eq. 4 indicates that the guidance is not changed
during training. More importantly, after projecting task classification and
observations to their original values, the loss on $x^{m}$ is exclusively
attributed to $a^{m}$. Thus, the training loss can be computed as follows:

$\mathcal{L}_{diff}^{m}=\sum_{n=1}^{N}(\epsilon_{\theta}(a_{n}^{m},n)-a_{0}^{m})^{2}.$
(5)

By employing a binary mask on the action dimensions, Gaussian noise is
exclusively introduced to unmasked active actions. As a result, the search
space for optimal actions is confined to the task-defined subset, rather than
encompassing the entire action space of the dataset. This operation
considerably reduces the learning load of the model during loss minimization,
which in turn leads to a streamlined convergence process and enhanced accuracy
in the denoising phase. This benefit becomes even more pronounced as the
action space becomes larger.

### Training

Our training program consists of two main stages: (1) training of a task class
prediction model to extract conditional guidance from start to goal
observation as well as action masks; (2) leveraging the masked diffusion model
to effectively fit the target action sequence distribution.

As mentioned earlier, a binary mask is applied to the action dimensions,
directing the denoising model to focus on active actions. In the action
sequence distribution fitting stage, we adopt the U-Net architecture
(Ronneberger, Fischer, and Brox 2015) to learn the noise prediction model
$\epsilon_{\theta}(x_{n},n)$ on the masked action distribution, as it
resembles the stacked denoising autoencoders. By minimizing
$\mathcal{L}_{diff}^{m}$, the model effectively mitigates the impact of
randomly introduced noise on $x_{n}^{m}$. The detailed denoising model
training process is shown in Algorithm 1.

Algorithm 1 Training Process

Input: Initial input $x_{0}$, Gt task class $c$, the condition project
function $Proj()$, total diffusion steps $N$, diffusion model
$\epsilon_{\theta}$, $\\{\overline{\alpha}_{n}\\}_{n=1}^{N}$

1: apply a binary mask to action dimension in $x_{0}$ given $c$

2: $a_{0}^{m}=a_{0}[0,1,0...1,0]$($a$ in $c$ value is ‘1’, otherwise ‘0’)

3: repeat

4: $n\sim\\{1,N\\}$

5: $\epsilon\sim\mathcal{N}(0,\,\mathbf{I})$

6:
$x_{n}^{m}$=$\sqrt{\overline{\alpha}_{n}}x_{0}^{m}+\epsilon\sqrt{1-\overline{\alpha}_{n}}$

7: $\hat{x}_{0}^{m}=\epsilon_{\theta}(Proj(x_{n}^{m}),n)$

8: Take gradient descent step on

9: $\bigtriangledown_{\theta}\parallel
x_{0}^{m}-Proj(\hat{x}_{0}^{m})\parallel^{2}$

10: until converged

### Inference

During the inference stage, only the initial observation $o_{s}$ and the
target observation $o_{g}$ are given. The task class is generated through the
trained task classifier, eliminating the need for the ground truth task class
as in the training phase. Subsequently, Gaussian noise is introduced to the
conditions of the observations and masked action dimensions, resulting in the
creation of $x_{n}^{m}$. The acquired denoise model is then employed to
conduct denoising $N$ times for sampling an optimal action sequence. The
detailed procedure in the inference stage is shown in Algorithm 2.

Algorithm 2 Inference Process

Input: Total diffusion steps $N$, task class prediction $c$, model
$\epsilon_{\theta}$, $\\{\overline{\alpha}_{n}\\}_{n=1}^{N}$,
$\\{\beta_{n}\\}_{n=1}^{N}$

1: apply a binary mask to action dimension in $\hat{x}_{N}$ given $c$

2: $\hat{a}_{N}^{m}=\hat{a}_{N}[0,1,0...1,0]$($a$ in $c$ value is ‘1’,
otherwise ‘0’)

3: for $n=N$,…,1 do

4: $\hat{x}_{0}^{m}=\epsilon_{\theta}(Proj(x_{n}^{m}),n)$

5: if $n>1$ then

6:
$\hat{\mu}_{n}=\frac{\sqrt{\overline{\alpha}_{n-1}}\beta_{n}}{1-\overline{\alpha}_{n}}\hat{x}_{0}^{m}+\frac{\sqrt{\alpha_{n}}(1-\overline{\alpha}_{n-1})}{1-\overline{\alpha}_{n}}\hat{x}_{n}^{m}$

7:
$\hat{\sum}_{n}=\frac{1-\overline{\alpha}_{n-1}}{1-\overline{\alpha}_{n}}\cdot\beta_{n}$

8:
$\hat{x}_{n-1}^{m}\sim\mathcal{N}(\hat{x}_{n-1}^{m};\hat{\mu}_{n},\hat{\sum}_{n}\mathbf{I})$

9: end if

10: end for

11: return $\hat{x}_{0}^{m}$

### Implementation Details

The perceptual input to our model is a 1536-dimensional vector that represents
the visual features extracted from HowTo100M (Miech et al. 2019). For the text
representation input, we utilize LLaVA’s (Liu et al. 2023) prompt-extracted
text, which is subsequently encoded into a 578-dimensional vector using a
DistilBERT (Sanh et al. 2019) base model. All models are trained using a
linear warm-up scheme. Throughout our experiments, the training batch size
remains constant at 256. All the experiments are conducted using the ADAM
optimizer (Kingma and Ba 2014) on a setup consisting of 4 NVIDIA RTX A5000
GPUs. Refer to supplement for more detailed information, such as learning rate
and training epochs on different datasets.

## Experiments

### Evaluation Protocol

#### Datasets

We conduct evaluations of our model on three instructional video datasets:
CrossTask (Zhukov et al. 2019), NIV (Alayrac et al. 2016), and COIN (Tang et
al. 2019). The CrossTask dataset comprises 2,750 videos spanning 18 different
tasks, with an average of 7.6 actions per video. The NIV dataset consists of
150 videos depicting 5 daily tasks, with an average of 9.5 actions per video.
The COIN dataset contains 11,827 videos involving 180 different tasks, with an
average of 3.6 actions per video. We adopt the standard approach by randomly
splitting the data, using 70% for training and 30% for testing (Zhao et al.
2022; Sun et al. 2021; Wang et al. 2023a). We adhere to the data pre-
processing methodology (Wang et al. 2023a) to generate action sequences and
select {start, goal} observations.

#### Metrics

In accordance with prior studies (Zhao et al. 2022; Sun et al. 2021; Wang et
al. 2023a), we employ three metrics to assess the performance of our approach:
(1) _Success Rate (SR)_ : A plan is considered correct only if all actions in
the predicted sequence exactly match the corresponding actions in the ground
truth. (2) _Mean Accuracy (mAcc)_ : It is the accuracy of actions at each
individual time step. An action is considered correct if it precisely matches
the action in the ground truth at the same time step. (3) _Mean Intersection
over Union (mIoU)_ : It quantifies the overlap between predicted actions and
the ground truth by computing the action IoU. Note that _mIoU_ does not
consider the order of actions and solely indicates whether the model
effectively captures the correct set of steps required to complete the
procedure plan. Following (Wang et al. 2023a), we calculate the _mIoU_ metric
on each individual sequence, instead of computing it on every mini-batch, as
done in prior studies (Zhao et al. 2022; Sun et al. 2021). This is a more
stringent condition and allows us to assess the accuracy of predicted actions
for each specific sequence independently.

In addition, we conduct a comprehensive evaluation of the stochastic nature of
our model by employing various probabilistic metrics: (1) _Kullback–Leibler
divergence (KL-Div)_ and _Negative Log Likelihood (NLL)_ between the
probability distributions of the predicted plans and the corresponding ground
truth; (2) _Mode Recall (ModeRec)_ to assess the coverage of ground truth
modes in the results, and (3) _Mode Precision (ModePrec)_ to indicate the
frequency with which our predicted plans align with the true modes of the
data.

#### Baselines

We include recent procedure planning approaches based on instructional videos
as baselines (Chang et al. 2020; Sun et al. 2021; Bi, Luo, and Xu 2021; Zhao
et al. 2022; Wang et al. 2023a).

### Task Classification Results

We intend to improve the task prediction accuracy by employing a combination
of visual and text representations along with a transformer model. The results
of task prediction performance are shown in Table 1, where different
configurations are examined. Our model achieves an improvement of
approximately 3% in task classification accuracy on the COIN dataset (with the
largest task space). It achieves a slight improvement on CrossTask; and
maintains perfect accuracy (100%) on NIV as in other configurations.

To verify the influence of task classification on the ultimate accuracy of
action planning, we compare the outcomes achieved through the utilization of
the MLP as detailed in (Wang et al. 2023a) with the results obtained by
incorporating Transformer classifiers as inputs for both PDPP and our model.
We observe a positive effect of Transformer, as shown by the results in
supplementary section D.

### Comparison with Prior Approaches

#### Crosstask (short horizon)

We show the main performance results on CrossTask in Table 2. Our model
consistently outperforms other approaches in terms of both _SR_ and _mAcc_.
Across sequence lengths $T=3$ and $4$, our model exhibits a notable _SR_
increase of approximately 2% (absolute change) compared to the previous state-
of-the-art (SotA). In terms of _mAcc_ , our model showcases significant
enhancements, achieving more than 11% improvement at $T=3$ and around 2.3% at
$T=4$. Regarding _mIoU_ , as aforementioned, we follow PDPP (Wang et al.
2023a) to compute it by calculating the mean of every IoU for a single action
sequence rather than a mini-batch adopted by (Sun et al. 2021; Zhao et al.
2022). Hence, a direct comparison with (Sun et al. 2021; Zhao et al. 2022) is
not relevant. Compared to PDPP, our model achieves about $1.5\%$ improvement
in _mIoU_.

#### CrossTask (long horizon)

Following (Zhao et al. 2022; Wang et al. 2023b), we evaluate the performance
on predicting plans for longer time horizons, $T={3,4,5,6}$. The results are
shown in Table 3. Our model consistently achieves substantial enhancements
across all planning horizons, surpassing the performance of previous models.

#### NIV and COIN

Results on the NIV and COIN datasets are presented in Table 4. It is shown
that our method demonstrates superior performance on both datasets, surpassing
other approaches in terms of _SR_ and _mAcc_ metrics. In particular, on the
relatively smaller NIV dataset, our model achieves 1% ($T=3$) and 2% ($T=4$)
increases respectively in _SR_ , along with improvements of 0.6% ($T=3$) and
1.3% ($T=4$) in _mAcc_. On the COIN dataset, which poses the highest level of
difficulty, our method achieves a remarkable absolute improvement of 8.1%
($T=3$) and 6.9% ($T=4$) on _SR_ , and 4% ($T=3$) and 2.7% ($T=4$) on _mAcc_
metrics, respectively. These represent a substantial margin over previous
SotA, i.e., PDPP. Such a performance boost is also illustrated in Figure 3,
which shows the training process on COIN dataset. Our approach features a
large margin on SR and a faster learning speed, especially during the initial
stage of training.

Figure 3: Success rate during training on COIN dataset.

### Evaluating Probabilistic Modeling

To assess the effectiveness of our method on probabilistic modeling, we
conduct a comparison between the plan distributions generated by our model and
the ground truth distribution of viable plans, following the protocol proposed
in (Zhao et al. 2022; Wang et al. 2023a). The evaluation is done on CrossTask
dataset which is most suitable for this purpose with its higher variations in
feasible plans. Results on NIV and COIN datasets are included in the
supplementary material. We compare our model with three baselines: (1) a
Deterministic baseline established by setting the initial distribution
$\hat{x}_{N}=0$, (2) a Noise baseline achieved by directly sampling from a
random distribution using the provided observations and task class condition
in a single step, and (3) the original PDPP approach (Wang et al. 2023a).

The outcomes are presented in Table 5. Our model consistently produces the
lowest _NLL_ and _KL-Div_ values across all horizons in comparison with the
other three models. The results underscore the enhanced proficiency of our
model in managing uncertainty. Furthermore, our model exhibits a remarkable
capability to generate plans that are both diverse and logical, consistently
outperforming the other models in terms of _SR_ , _ModePrec_ , and _ModeRec_
across all horizons.

Table 1: Task classification results. VM: visual representation + MLP
classifier; VTM: visual-text representation + MLP classifier; VTT: visual-text
representation + Transformer classifier.

CrossTask COIN NIV T=3 T=4 T=5 T=6 T=3 T=4 T=3 T=4 VM 92.4 93.0 93.4 93.2 79.4
78.9 100 100 VTM 92.7 93.2 93.5 93.6 81.0 80.2 100 100 VTT 92.9 93.3 93.8 93.7
82.6 81.9 100 100

Table 2: Performance of benchmarks with planning horizons T$\in${3, 4} on
CrossTask. The ‘Supervision’ column indicates the type of supervision during
training. ‘V’: intermediate visual states; ‘L’: language features; ‘C’: task
class. Notably, to get _mIoU_ , we compute the average IoU for each individual
action sequence, rather than across a mini-batch (in grey font).

Models Supervision T=3 T=4 SR $\uparrow$ mAcc $\uparrow$ mIoU $\uparrow$ SR
$\uparrow$ mAcc $\uparrow$ mIoU $\uparrow$ DDN (Chang et al. 2020) V 12.18
31.29 47.48 5.97 27.10 48.46 PlaTe (Sun et al. 2021) L 16.00 36.17 65.91 14.00
35.29 44.36 Ext-GAIL (Bi, Luo, and Xu 2021) V 21.27 49.46 61.70 16.41 43.05
60.93 P3IV (Zhao et al. 2022) L 23.34 49.46 73.89 13.40 44.16 70.01 PDPP (Wang
et al. 2023a) C 37.20 55.35 66.57 21.48 57.82 65.13 Ours C 39.17 66.66 68.31
23.47 60.16 66.75

Table 3: Results of success rate for longer planning horizons on CrossTask.

Models T=3 T=4 T=5 T=6 SR$\uparrow$ SR$\uparrow$ SR$\uparrow$ SR$\uparrow$ DDN
(Chang et al. 2020) 12.18 5.97 3.10 1.20 PlaTe (Sun et al. 2021) 18.50 14.00
10.00 7.50 P3IV (Zhao et al. 2022) 23.34 13.40 7.21 4.40 PPDP (Wang et al.
2023a) 37.20 21.48 13.58 8.47 Ours 39.17 23.47 15.25 10.10

Table 4: Results for prediction horizons T$\in${3, 4} on NIV and COIN
datasets. ‘Sup.’ means the type of supervision during training.

Hor. Models Sup. NIV COIN SR $\uparrow$ mAcc $\uparrow$ mIoU $\uparrow$ SR
$\uparrow$ mAcc $\uparrow$ mIoU $\uparrow$ T=3 DDN V 18.41 32.54 56.56 13.9
20.19 64.78 Ext-GAIL V 22.11 42.20 65.93 - - - P3IV L 24.68 49.01 74.29 15.4
21.67 76.31 PDPP C 31.25 49.26 57.92 21.33 45.62 51.82 Ours C 32.35 49.89
58.90 29.43 49.50 52.20 T=4 DDN V 15.97 27.09 53.84 11.13 17.71 68.06 Ext-GAIL
V 19.91 36.31 53.84 - - - P3IV L 20.14 38.36 67.29 11.32 18.85 70.53 PDPP C
26.72 48.92 59.04 14.41 44.10 51.39 Ours C 28.88 50.20 59.75 21.30 46.84 52.45

Table 5: Uncertainty and diversity evaluation on CrossTask.

Hori. Model NLL$\downarrow$ KL-Div$\downarrow$ SR$\uparrow$ ModePrec$\uparrow$
ModeRec$\uparrow$ T=3 Deterministic 3.57 2.99 39.03 55.60 34.13 Noise 3.58
3.00 34.92 51.04 39.42 PDPP 3.61 3.03 37.20 53.14 36.49 Ours 3.10 2.52 39.17
56.03 44.52 T=4 Deterministic 4.29 3.40 21.17 45.65 18.35 Noise 4.04 3.15
18.99 43.90 25.56 PDPP 3.85 2.96 21.28 44.55 31.10 Ours 3.41 2.52 23.47 47.33
34.60 T=5 Deterministic 4.70 3.54 12.59 35.47 11.20 Noise 4.45 3.30 12.04
34.35 15.67 PDPP 3.77 2.62 13.58 36.30 29.45 Ours 3.61 2.46 15.25 36.56 30.12
T=6 Deterministic 5.12 3.82 7.47 25.24 6.75 Noise 4.97 3.49 7.82 24.51 11.04
PDPP 4.06 2.76 8.47 25.61 22.68 Ours 3.67 2.37 10.10 25.90 28.69

### Ablation Studies

#### Effect of text-enhanced representation learning

To validate the efficacy of text-enhanced representation learning within our
model, we compare the performance of three setups: (1) the original PDPP model
that utilizes only visual representation, (2) a truncated model that uses only
text-based representation, and (3) a model that employs joint vision-text
representations. The results are listed in Table 6. Apparently, the text-only
modality is inferior to the visual-only modality and the vision-text
multimodality in representation learning. Importantly, the additional action-
aware text embedding does have a positive effect on planning efficacy as
indicated by the higher performance of vision-text joint representation than
visual-only. This outcome is consistent with the information in Table 1,
wherein higher accuracy of task classification is achieved when vision-text
joint representation is used.

Table 6: Ablation study on the role of text-enhanced representation learning.

Models CrossTask NIV COIN T=3 T=4 T=5 T=6 T=3 T=4 T=3 T=4 PDPP(V) 37.20 21.48
13.58 8.47 31.25 26.72 21.33 14.41 PDPP(T) 32.18 18.86 11.47 8.15 28.33 24.87
17.63 11.35 PDPP(V+T) 37.72 22.07 14.03 9.04 31.73 27.41 24.46 16.02

#### Effect of masked diffusion

We conduct an ablation study to investigate the impact of different masking
techniques on performance. In our method, we apply a binary mask to the action
dimensions (called hard mask). Gaussian noise is exclusively generated within
the unmasked regions, corresponding to the actions relevant to the active
task. However, a possible adverse effect is that if the task classification is
incorrect, there is a substantial likelihood that the action plans are wrong.
Hence, we use the confidence score of task prediction to dictate the
likelihood of a set of actions being retained, enabling the creation of a
“soft” mask that is applied to the action dimensions. We also include a
condition where no masking is applied to the action dimensions (w/o mask),
resulting in a diffusion model identical to that of PDPP.

The _SR_ results are outlined in Table 7 \- detailed data for _SR_ , _mAcc_ ,
and _mIoU_ can be found in supplementary materials. It is shown that hard
masking results in the highest _SR_. In fact, even without applying masking to
action dimensions, the “w/o mask” configuration outperforms PDPP, possibly due
to improved task class prediction facilitated by text-enhanced representation.
Interestingly, soft masking leads to the lowest _SR_ , performing worse than
both PDPP and the non-masked approach. The possible reason is that with hard
masking, action planning is confined within the boundaries of a task. This
restriction significantly reduces the action space, allowing for a thorough
exploration of the action sequencing within the unmasked subset of actions.
With soft masking, the confidence scores of task classification could be ill-
calibrated (Guo et al. 2017), which leads to wrong allocation to task-guided
action types.

Table 7: Ablation study on the role of the masking type.

CrossTask NIV COIN T=3 T=4 T=5 T=6 T=3 T=4 T=3 T=4 PDPP 37.20 21.48 13.58 8.47
31.25 26.72 21.33 14.41 w/o mask 37.72 22.07 14.03 9.04 31.73 27.41 24.46
16.02 Soft mask 34.37 18.44 12.04 7.73 30.44 26.07 18.76 12.57 Hard mask 39.17
23.47 15.25 10.10 32.35 28.88 27.85 20.24

## Conclusion

In this paper, we have introduced a masked diffusion model to deal with the
large design space that challenges procedure planning in instructional videos.
A simple yet effective masking mechanism is designed in a projected diffusion
model to restrict the scope of planning to a subset of actions, as is guided
by the task class information. We show that such a binary mask leads to
significant improvements in procedure planning with respect to multiple
metrics. It also engenders a positive effect on probabilistic modeling to
reflect the inherent data distribution. Furthermore, we show the preferable
effect of text-enhanced representation learning, which leverages the power of
large VLMs and generates action-aware text description simply via prompting,
without the need for computationally intensive training or fine-tuning. A
direction of future work is to develop a more sophisticated masking scheme
based on a well-calibrated task prediction model, so as to allow for a well-
balanced compromise between the reduction in dimensions induced by masking and
the retention of context relevant to the task.

## References

  * Abu Farha and Gall (2019) Abu Farha, Y.; and Gall, J. 2019.  Uncertainty-Aware Anticipation of Activities.  In _IEEE/CVF International Conference on Computer Vision Workshops_ , 1197–1204.
  * Alayrac et al. (2016) Alayrac, J.-B.; Bojanowski, P.; Agrawal, N.; Sivic, J.; Laptev, I.; and Lacoste-Julien, S. 2016.  Unsupervised Learning from Narrated Instruction Videos.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 4575–4583.
  * Ashutosh et al. (2023) Ashutosh, K.; Girdhar, R.; Torresani, L.; and Grauman, K. 2023.  HierVL: Learning Hierarchical Video-Language Embeddings.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 23066–23078.
  * Bi, Luo, and Xu (2021) Bi, J.; Luo, J.; and Xu, C. 2021.  Procedure Planning in Instructional Videos via Contextual Modeling and Model-based Policy Learning.  In _IEEE/CVF International Conference on Computer Vision_ , 15591–15600.
  * Chang et al. (2020) Chang, C.-Y.; Huang, D.-A.; Xu, D.; Adeli, E.; Fei-Fei, L.; and Niebles, J. C. 2020\.  Procedure planning in instructional videos.  In _European Conference on Computer Vision_ , 334–350.
  * Damen et al. (2020) Damen, D.; Doughty, H.; Farinella, G. M.; Furnari, A.; Kazakos, E.; Ma, J.; Moltisanti, D.; Munro, J.; Perrett, T.; Price, W.; and Wray, M. 2020.  Rescaling Egocentric Vision: Collection, Pipeline and Challenges for EPIC-KITCHENS-100.  _International Journal of Computer Vision_ , 130: 33–55.
  * Gao et al. (2023) Gao, S.; Zhou, P.; Cheng, M.-M.; and Yan, S. 2023.  Masked Diffusion Transformer is a Strong Image Synthesizer.  _ArXiv_ , abs/2303.14389.
  * Ge et al. (2023) Ge, J.; Luo, H.; Qian, S.; Gan, Y.; Fu, J.; and Zhang, S. 2023.  Chain of Thought Prompt Tuning in Vision Language Models.  _ArXiv_ , abs/2304.07919.
  * Grauman et al. (2022) Grauman, K.; Westbury, A.; Byrne, E.; and et al. 2022.  Ego4D: Around the World in 3,000 Hours of Egocentric Video.  _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 18973–18990.
  * Guo et al. (2017) Guo, C.; Pleiss, G.; Sun, Y.; and Weinberger, K. Q. 2017.  On Calibration of Modern Neural Networks.  In _International Conference on Machine Learning_.
  * Ho, Jain, and Abbeel (2020) Ho, J.; Jain, A.; and Abbeel, P. 2020.  Denoising Diffusion Probabilistic Models.  In _Advances in Neural Information Processing Systems_ , 6840–6851.
  * Huang et al. (2019) Huang, D.-A.; Nair, S.; Xu, D.; Zhu, Y.; Garg, A.; Fei-Fei, L.; Savarese, S.; and Niebles, J. C. 2019.  Neural Task Graphs: Generalizing to Unseen Tasks From a Single Video Demonstration.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 8557–8566.
  * Kim et al. (2022) Kim, J.; Nguyen, D.; Min, S.; Cho, S.; Lee, M.; Lee, H.; and Hong, S. 2022.  Pure Transformers are Powerful Graph Learners.  In _Advances in Neural Information Processing Systems_ , 14582–14595.
  * Kingma and Ba (2014) Kingma, D.; and Ba, J. 2014.  Adam: A Method for Stochastic Optimization.  _International Conference on Learning Representations_.
  * Kurutach et al. (2018) Kurutach, T.; Tamar, A.; Yang, G.; Russell, S. J.; and Abbeel, P. 2018.  Learning Plannable Representations with Causal InfoGAN.  In _Advances in Neural Information Processing Systems_ , 8747–8758.
  * Lin et al. (2022) Lin, X.; Petroni, F.; Bertasius, G.; Rohrbach, M.; Chang, S.-F.; and Torresani, L. 2022.  Learning To Recognize Procedural Activities with Distant Supervision.  _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 13843–13853.
  * Liu et al. (2022) Liu, A.; Sohn, S.; Qazwini, M.; and Lee, H. 2022.  Learning Parameterized Task Structure for Generalization to Unseen Entities.  In _AAAI Conference on Artificial Intelligence_ , 7534–7541.
  * Liu et al. (2023) Liu, H.; Li, C.; Wu, Q.; and Lee, Y. J. 2023.  Visual Instruction Tuning.  _ArXiv_ , abs/2304.08485.
  * Mao et al. (2023) Mao, W.; Desai, R.; Iuzzolino, M. L.; and Kamra, N. 2023.  Action Dynamics Task Graphs for Learning Plannable Representations of Procedural Tasks.  _ArXiv_ , abs/2302.05330.
  * Miech et al. (2019) Miech, A.; Zhukov, D.; Alayrac, J.-B.; Tapaswi, M.; Laptev, I.; and Sivic, J. 2019\.  HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips.  In _IEEE/CVF International Conference on Computer Vision_ , 2630–2640.
  * Nair and Finn (2019) Nair, S.; and Finn, C. 2019.  Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generation.  _ArXiv_ , abs/1909.05829.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  _ArXiv_ , abs/2303.08774.
  * Patel et al. (2023) Patel, D.; Eghbalzadeh, H.; Kamra, N.; Iuzzolino, M. L.; Jain, U.; and Desai, R. 2023.  Pretrained Language Models as Visual Planners for Human Assistance.  _ArXiv_ , abs/2304.09179.
  * Pertsch et al. (2020) Pertsch, K.; Rybkin, O.; Ebert, F.; Zhou, S.; Jayaraman, D.; Finn, C.; and Levine, S. 2020.  Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors.  In _Advances in Neural Information Processing Systems_ , 17321–17333.
  * Rampášek et al. (2022) Rampášek, L.; Galkin, M.; Dwivedi, V. P.; Luu, A. T.; Wolf, G.; and Beaini, D. 2022.  Recipe for a General, Powerful, Scalable Graph Transformer.  In _Advances in Neural Information Processing Systems_ , 14501–14515.
  * Ronneberger, Fischer, and Brox (2015) Ronneberger, O.; Fischer, P.; and Brox, T. 2015.  U-Net: Convolutional Networks for Biomedical Image Segmentation.  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 234–241.
  * Sanh et al. (2019) Sanh, V.; Debut, L.; Chaumond, J.; and Wolf, T. 2019.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  _ArXiv_ , abs/1910.01108.
  * Srinivas et al. (2018) Srinivas, A.; Jabri, A.; Abbeel, P.; Levine, S.; and Finn, C. 2018.  Universal Planning Networks: Learning Generalizable Representations for Visuomotor Control.  In _International Conference on Machine Learning_ , 4732–4741.
  * Sun et al. (2021) Sun, J.; Huang, D.-A.; Lu, B.; Liu, Y.; Zhou, B.; and Garg, A. 2021.  PlaTe: Visually-Grounded Planning With Transformers in Procedural Tasks.  _IEEE Robotics and Automation Letters_ , 7: 4924–4930.
  * Tang et al. (2019) Tang, Y.; Ding, D.; Rao, Y.; Zheng, Y.; Zhang, D.; Zhao, L.; Lu, J.; and Zhou, J. 2019.  COIN: A Large-Scale Dataset for Comprehensive Instructional Video Analysis.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 1207–1216.
  * Touvron et al. (2023) Touvron, H.; Lavril, T.; Izacard, G.; Martinet, X.; Lachaux, M.-A.; Lacroix, T.; Rozière, B.; Goyal, N.; Hambro, E.; Azhar, F.; Rodriguez, A.; Joulin, A.; Grave, E.; and Lample, G. 2023.  LLaMA: Open and Efficient Foundation Language Models.  _ArXiv_ , abs/2302.13971.
  * Wang et al. (2023a) Wang, H.; Wu, Y.; Guo, S.; and Wang, L. 2023a.  PDPP: Projected Diffusion for Procedure Planning in Instructional Videos.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 14836–14845.
  * Wang et al. (2023b) Wang, Q.; Li, M.; Chan, H. P.; Huang, L.; Hockenmaier, J.; Chowdhary, G. V.; and Ji, H. 2023b.  Multimedia Generative Script Learning for Task Planning.  In _Annual Meeting of the Association for Computational Linguistics_ , 986–1008.
  * Xu et al. (2021) Xu, H.; Ghosh, G.; Huang, P.-Y. B.; Okhonko, D.; Aghajanyan, A.; and Feichtenhofer, F. M. L. Z. C. 2021.  VideoCLIP: Contrastive Pre-training for Zero-shot Video-Text Understanding.  In _Conference on Empirical Methods in Natural Language Processing_ , 6787–6800.
  * Zhao et al. (2022) Zhao, H.; Hadji, I.; Dvornik, N.; Derpanis, K. G.; Wildes, R. P.; and Jepson, A. D. 2022.  P3IV: Probabilistic Procedure Planning from Instructional Videos with Weak Supervision.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2928–2938.
  * Zhao et al. (2023) Zhao, Y.; Misra, I.; Krähenbühl, P.; and Girdhar, R. 2023.  Learning Video Representations from Large Language Models.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 6586–6597.
  * Zheng et al. (2023) Zheng, H.; Nie, W.; Vahdat, A.; and Anandkumar, A. 2023.  Fast Training of Diffusion Models with Masked Transformers.  _ArXiv_ , abs/2306.09305.
  * Zhong et al. (2023) Zhong, Y.; Yu, L.; Bai, Y.; Li, S.; Yan, X.; and Li, Y. 2023.  Learning Procedure-aware Video Representation from Instructional Videos and Their Narrations.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 14825–14835.
  * Zhou et al. (2023) Zhou, H.; Martín-Martín, R.; Kapadia, M.; Savarese, S.; and Niebles, J. C. 2023.  Procedure-Aware Pretraining for Instructional Video Understanding.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 10727–10738.
  * Zhou, Xu, and Corso (2018) Zhou, L.; Xu, C.; and Corso, J. 2018.  Towards Automatic Learning of Procedures from Web Instructional Videos.  In _AAAI Conference on Artificial Intelligence_ , 7590–7598.
  * Zhukov et al. (2019) Zhukov, D.; Alayrac, J.-B.; Cinbis, R. G.; Fouhey, D.; Laptev, I.; and Sivic, J. 2019.  Cross-task Weakly Supervised Learning from Instructional Videos.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 3537–3545.


# Trainless Model Performance Estimation Based on Random Weights
Initialisations for Neural Architecture Search

Ekaterina Gracheva<EMAIL_ADDRESS>International Center for
Materials Nanoarchitectonics, National Institute for Materials Science, 1-1
Namiki, Tsukuba, Ibaraki, 305-0044 Japan  University of Tsukuba, 1-1-1
Tennodai, Tsukuba, Ibaraki, 305-8577 Japan

###### Abstract

Neural architecture search has become an indispensable part of the deep
learning field. Modern methods allow to find one of the best performing
architectures, or to build one from scratch, but they typically make decisions
based on the trained accuracy information. In the present article we explore
instead how the architectural component of a neural network affects its
prediction power. We focus on relationships between the trained accuracy of an
architecture and its accuracy prior to training, by considering statistics
over multiple initialisations. We observe that minimising the coefficient of
variation of the untrained accuracy, $CV_{U}$, consistently leads to better
performing architectures. We test the $CV_{U}$ as a neural architecture search
scoring metric using the NAS-Bench-201 database of trained neural
architectures. The architectures with the lowest $CV_{U}$ value have on
average an accuracy of $91.90\pm 2.27$, $64.08\pm 5.63$ and $38.76\pm 6.62$
for CIFAR-10, CIFAR-100 and a downscaled version of ImageNet, respectively.
Since these values are statistically above the random baseline, we make a
conclusion that a good architecture should be stable against weights
initialisations. It takes about $190$ s for CIFAR-10 and CIFAR-100 and $133.9$
s for ImageNet16-120 to process 100 architectures, on a batch of $256$ images,
with $100$ initialisations.

###### keywords:

Neural architecture search , Trainless architecture search , Deep learning ,
Machine learning

##  1 Introduction

Since the beginning of the boom in the field of artificial intelligence, there
has been continuous increase in data complexity and quantity, neural
architecture designs, as well as yet increasing choice of powerful hardware.
These factors render neural architecture building process complex. Given an
extremely large number of parameters to be tuned, it can be extremely slow,
when the decisions are made on a trial and error basis. Neural architecture
search (NAS) is a way to automatise and accelerate the decision taking,
shifting the task from humans to machines. It comes as no surprise, that
recently NAS has become one of the most popular topics among the deep learning
community.

The first attempts to find the most suitable network structure were done
through evolutionary algorithms [1, 2, 3, 4]. There, several architectures are
mutated in various ways (e.g. adding or removing a layer, changing activation
function, etc.), and the resulting offsprings are evaluated through training.
The best performing of the offsprings are added to the population for the next
step, and the procedure is repeated for a given number of steps. This method
has been used since back in the 1990’s [5] and shows one of the best
performances until now [6].

Similarly, Bayesian optimisation [7] is used to predict the best performing
architecture out of many by training a subset of architectures [8]. This
method has shown a few state-of-the-art performances in the period between
2013 and 2020 [9, 10, 11, 12].

In 2016 Zoch et al. [13] proposed to use the reinforcement learning to build
neural architectures from scratch. There, a so-called controller neural
network is trained to build a child-network — the network to be used for the
final training and prediction. The original method demands tremendous amount
of child-model training and is extremely lengthy. Several related works show
significant acceleration of the process by reducing the search space [14] or
introducing weight sharing [15]. An extensive overview of the NAS methods has
been recently done by Thomas Elsken et al. [16].

The common point of all the above mentioned NAS algorithms is that at some
point they all require model training. Not only that means longer search
times, but also a higher uncertainty, since model training brings extra
parameters to be tuned (_e.g._ , batch size or learning rate).

As a step towards trainless NAS, in 2018 Istrate et al. [17] have introduced a
small LSTM-based model, that allows to predict architecture’s performance
without training it on the data of interest. This model predicts an
architecture’s potential for a given data complexity. This data is taken from
a so-called lifelong database of experiments. The straightaway restriction of
this method is that there should already exist some data of a similar
complexity within the database, and the available networks are limited to
already existing ones (focused on image classification). Moreover, with time
the overall procedure might lead to a bias, i.e., a most often predicted
architecture in the beginning will have yet more chance to be output in
future, thus ”locking” it at the top position.

A similar approach is proposed by Deng et al. [18]. They encode the layers
composing the network into vectors, and bring them together with a predictive
LSTM layer to build numerical representation of a network. A multilayer
perceptron model is trained to predict the architecture with the highest
prediction accuracy. Therefore, in order to use this method one needs to first
train a set of architectures to acquire their trained accuracies, and then to
train the predictive model on top. Since the final decision is made by a
neural model, this method does not provide a reason why a given architecture
has been chosen.

The first work that investigates fundamental architectural properties of
neural networks in order to attain fully trainless NAS is proposed by Mellor
et al. [19] in 2020. The authors assess the neural architecture’s potential by
passing a single minibatch of the data through a network forwards and
backwards — one single time. Based on the results of the backpropagation, they
measure the correlation between calculated gradients associated with the input
layer. Using the NAS-Bench-201 benchmark database [20], the authors show that
their metric is able to distinguish one of the best neural architectures among
many with consistent success. To the best of our knowledge, this is the only
approach that aims to give an explanation of neural network’s performance
based on its structure.

On another end, there are a few papers, indicating that the best trained
neural architecture often shows a better untrained accuracy. For example, the
work of the UBER team [21] mentions that the best final architecture shows
nearly $40\%$ accuracy on MNIST dataset [22] at initialisation. David Ha and
Adam Gaier [23] have presented a NAS algorithm which builds an architecture
based on the untrained score. Their score is taking into account both the
number of parameters contained within a model, which they seek to minimise,
and the mean accuracy, which is being maximised. The mean accuracy is computed
over several initialisations of the child model using a set of constant
weights (single value for all the weights). They report that the resulting
model achieves $82.0\%\pm 18.7\%$ on MNIST data with random weights at
initialisation, and over $90\%$ when the weights are fixed to the best
performing constant ones.

These findings imply that neural networks might have an intrinsic property,
which defines their prediction performance prior to training. Such property
should not depend on the values of trainable parameters (weights), but only on
network’s topology. In order to cancel out the influence of the weights and to
bring out the architectural component, we perform multiple random weights
initialisations to assess averaged networks’ performances. We compute several
untrained statistics and explore their relationships with the trained
accuracy. Based on the results of these tests, we deduce a trainless NAS
scoring metric.

Our work can be divided into two parts. First, we have conducted an extensive
MNIST study to explore dependencies between various untrained statistics and
the trained accuracy. For this, we train a range of fully-connected neural
networks on a reduced MNIST data, with multiple seeds and learning
rates.111Fully reproducible code with data is available on GitHub at
https://github.com/egracheva/TrainlessNAS_MNIST Then, the most promising
statistical property, the coefficient of variation $CV$, is tested on larger
datasets and more complex neural geometries, to confirm its generality as a
scoring metric for NAS.

The paper is structured as follows: Section 2 details the search spaces,
datasets and training schemes used for the scoring metric search (2.1) and
application (2.2). We present and discuss the results in Section 3. Subsection
3.1 presents the selected scoring metric, while in Subsection 3.2 we provide
the results of the experiments with CIFAR-10, CIFAR-100 [24] and
ImageNet16-120 [25]. Conclusions and future improvements are proposed in
Section 4.

##  2 Materials and methods

###  2.1 MNIST dataset processing and training

####  2.1.1 Dataset

First, we explore correlations between some of the untrained performance
statistics and the resulting trained accuracy evaluated on the test set. For
this purpose we use a reduced version of MNIST [22] dataset, containing images
of handwritten digits from 0 to 9. We reduce the size of the training set,
leaving $20$ data points per class ($200$ data point in total). This is done
to accelerate the training process and to train more models for better
statistics. Besides, reduced training set makes the prediction task harder,
which allows to distinguish the difference between architectures clearer. Note
that both the validation and test sets are entirely preserved, containing
$5000$ data points each. No data augmentation is applied.

####  2.1.2 Search space

In order to reduce the uncertainty brought by complex neural structures
(effects of initialisation, activation, etc.), the search region is limited to
fully connected neural networks consisting of $2$ hidden layers. The number of
units in each hidden layer is set to be one of the $12$ values in
$[8,16,24,32,56,64,96,128,$ $256,512,1024,2048]$, making a total of $144$ of
possible architectures.

####  2.1.3 Training scheme

Every neural network is initialised and trained with $100$ different seeds
between $0$ and $99$, and $6$ learning rates
$[0.0001,0.0003,0.001,0.003,0.01,0.03]$ ($600$ trainings per architecture,
$86400$ trainings overall). The batch size $N_{BS}$ is fixed to $50$, which we
found showing the best results for a wide range of architectures within the
search space. The models are built with Keras [26] and Tensorflow [27] and
trained for $200$ epochs using $3$ NVIDIA Titan V GPUs. Weights are
initialised using the He uniform initialiser [28], which is used together with
ReLU activation function [29] for hidden layers and Adam optimiser [30] with
default decay rates ($0.9$ and $0.99$ for the first and second moments,
respectively).

The final weights are based on the epoch with the best validation accuracy
after a burn-in period of $50$ epochs. Ignoring the first quarter of the
training process is based on experience, since the validation loss of small
noisy data tends to demonstrate random behaviour in the beginning of the
training, leading to faulty results.

The pseudocode for the MNIST [22] training process is given in Algorithm 1.

Algorithm 1 MNIST training pseudocode

Load the data

Split data on train/val/test sets

for cat in categories do $\triangleright$ creating reduced train set

Randomly pick $20$ points from the original train set

end for

for nunits_layer_1 in $[8,16,\dots,2048]$ do

for nunits_layer_2 in $[8,16,\dots,2048]$ do

for lr in $[0.0001,0.0003,0.001,0.003,0.01,0.03]$ do

for seed in range($N_{init}$) do

Build initial model

Assess the untrained accuracy $U_{i}$ $\triangleright$ untrained accuracy

Train the model

Select the final weights based on the best validation accuracy

Compute test set accuracy $T_{i}$ $\triangleright$ trained accuracy

end for

Compute means and standard deviations
$\displaystyle\mu_{T}=\frac{1}{N}\sum\limits_{i=1}^{N_{init}}T_{i},\quad\sigma_{T}=\sqrt{\frac{\sum\limits_{i=1}^{N_{init}}(T_{i}-\mu_{T})^{2}}{N_{init}}}$
$\displaystyle\mu_{U}=\frac{1}{N}\sum\limits_{i=1}^{N_{init}}U_{i},\quad\sigma_{U}=\sqrt{\frac{\sum\limits_{i=1}^{N_{init}}(U_{i}-\mu_{U})^{2}}{N_{init}}}$

end for

Select the best performing learning rate based on $max(\mu_{T})$

$\triangleright$ one set of [$\mu_{T}$, $\sigma_{T}$, $\mu_{U}$, $\sigma_{U}$]
per architecture

end for

end for

Once the training is complete, only the learning rate showing the highest
average training accuracy is selected for each architecture. This is done to
insure that neural architectures are compared in a fair way, each showing its
best performance. Afterwards, mean untrained error $\mu_{U}$, mean trained
error $\mu_{T}$, together with their respective standard deviations
($\sigma_{U}$, $\sigma_{T}$) are calculated.

###  2.2 CIFAR-10, CIFAR-100 and ImageNet

####  2.2.1 Search space: NAS-Bench-201

To test more complex geometries on challenging datasets, we used a modified
version of the code used by Mellor et al. [19], published together with their
paper222The code can be found on GitHub at https://github.com/BayesWatch/nas-
without-training. To check the validity of their NAS search metric, the
authors use the NAS-Bench-201 search space [20]. It is a set of architectures
with a fixed skeleton, consisting of convolution layer and three stacks of
cells, connected by a residual block. Each cell is a densely-connected
directed acyclic graph with $4$ nodes, $5$ possible operations and no limits
on the number of edges, providing a total of $15,625$ possible architectures.

####  2.2.2 Datasets

Each of the architectures from NAS-Bench-201 [20] is trained on three major
datasets: CIFAR-10, CIFAR-100 [24] and ImageNet [25]. Since the original CIFAR
datasets do not contain a validation set, the NAS-Bench-201 authors created
one by splitting the original data. In case of CIFAR-10, the training set is
split into halves to form the validation set, leaving the test set unchanged;
for CIFAR-100, the test set is split in halves to form the validation set and
the new test set. For the sake of computational tractability, a simplified
version of ImageNet is used [25]. All the images are down-scaled to 16x16
pixels, with 120 classes kept, forming a new ImageNet16-120 dataset. Data
augmentation is used for all datasets; augmentation schemes differ slightly
between CIFAR [24] and ImageNet [25] due to the difference between input image
sizes.

An overview on all the data used in the present work is given in Table 1.

Table 1: A summary over the datasets used in this paper: number of classes, image resolution and splitting schemes (in thousands) for reduced MNIST [22], CIFAR-10, CIFAR-100 [24] and ImageNet16-120 [25]. Dataset | Classes | Resolution | Train/val/test (K)
---|---|---|---
Reduced MNIST | 10 | 28x28 | 0.2/5/5
CIFAR-10 | 10 | 32x32x3 | 25/25/10
CIFAR-100 | 100 | 32x32x3 | 50/5/5
ImageNet16-120 | 120 | 16x16x3 | 151.7/3/3

####  2.2.3 Training

The training is done using up to $3$ different seeds, and with the same fixed
set of hyperparameters for each dataset. The authors use stochastic gradient
descent with Nesterov momentum, batch size $N_{BS}=256$, learning rate between
$0.1$ and $0$ with cosine annealing and weight decay of $5\times 10^{-4}$.
Architectures are trained for $200$ epochs.

####  2.2.4 Experimental scheme

The goal of this part of the study is to determine how efficiently does a
given scoring metric select a good architecture among many random ones. In
order to obtain statistically significant information, selection process is
run $N_{runs}=500$ times, each time choosing $N_{a}$ architectures at random
(among $15,625$ available). Each architecture is initialised $N_{init}$ times,
in order to access the mean $\mu_{U}$ and standard deviation $\sigma_{U}$ of
the untrained performance. The batch data used for the accuracy computation is
fixed for every individual run, so that all the architectures are fairly
compared, and there is no uncertainty coming from the data choice. The
pseudocode for this part of the study is given in Algorithm 2. For this, we
use a modified code provided by Mellow et al. together with their paper
[19].333The modified code can be found on GitHub at
https://github.com/egracheva/TrainlessNAS_NAS201Bench

Algorithm 2 $CV_{U}$ tests on NAS-Bench-201

for run in range($N_{runs}$) do

Randomly select $N_{BS}$ images from the training dataset

Randomly select $N_{a}$ architectures from the whole space $\triangleright$
arches

for arch in arches do

for seed in range($N_{init}$) do

Initialise the arch with the seed

Forward propagate selected $N_{BS}$ images

Compute untrained accuracy $U_{i}$

end for

Compute mean $\mu_{U}$, standard deviation $\sigma_{U}$ for untrained
accuracies over initialisations
$\displaystyle\mu_{U}=\frac{1}{N}\sum\limits_{i=1}^{N_{init}}U_{i},\quad\sigma_{U}=\sqrt{\frac{\sum\limits_{i=1}^{N_{init}}(U_{i}-\mu_{U})^{2}}{N_{init}}}$

Compute the score  $CV_{U}=\frac{\sigma_{U}}{\mu_{U}}$ (1)

end for

Select the architecture with the minimum score value ($CV_{U}>0$)

Retrieve trained accuracy $T$ for the selected architecture from the database

end for

Average trained accuracies of selected architectures over $N_{runs}$
$\mu_{T}=\sum\limits_{j=1}^{N_{runs}}T_{j}$ (2)

Filtering out the scores equal to zero is necessary for the random
architectures containing no meaningful layers (for example, architectures
consisting of skip-connection layers only). These architectures, naturally,
show random accuracy with no deviation ($\sigma_{U}=0$).

##  3 Results and discussion

###  3.1 Scoring metric search with MNIST

The aim of the experiments related to MNIST [22] is to explore dependencies
between various untrained statistics and the trained accuracy. The existing
machine learning literature suggests that the best trained architecture may
also show high untrained performance [23, 21]. We expect, thus, to see some
tendency between mean accuracies prior to and after the training. We denote
these accuracies as $\mu_{U}$ and $\mu_{T}$, respectively. Against our
expectations, there is no clear correlation between these two metrics, as
shown in Figure 1(a). Instead, surprisingly, the mean trained accuracy
$\mu_{T}$ seems to be related to the untrained standard deviation
$\sigma_{U}$: even though there is no linear correlation, the lowest
$\sigma_{U}$ values belong to architectures from the top performance range
(Figure 1(b)).

(a)

(b)

Figure 1: (a) Mean untrained accuracy $\mu_{U}$ (a) and standard deviation of
untrained accuracy $\sigma_{U}$ (b) against mean trained accuracy $\mu_{T}$,
all three computed over $N_{init}=100$ initialisations. One point stands for
one architecture. The colours represent the logarithm of the number of
parameters for a given architecture.

We have also observed that lower means $\mu_{U}$ corresponds to lower standard
deviations $\sigma_{U}$ (Figure 3). Indeed, lower accuracy values lead to
proportionally lower mean and standard deviation. Therefore, minimising
standard deviation alone may bias towards the networks that show overall low
untrained accuracies $U_{i}$. To compensate for this effect, we normalise the
standard deviation $\sigma_{U}$ by the mean $\mu_{U}$:

$\displaystyle CV_{U}=\frac{\sigma_{U}}{\mu_{U}}.$

Figure 2: Mean untrained accuracy $\mu_{U}$ against standard deviation of
untrained accuracy $\sigma_{U}$, computed over $N_{init}=100$ initialisations.
One point stands for one architecture. The colours represent the logarithm of
the number of parameters for a given architecture.

Figure 3: Coefficient of variation of the untrained accuracy $CV_{U}$
($\rm\%$) against mean trained accuracy $\mu_{T}$, both computed over
$N_{init}=100$ initialisations. One point stands for one architecture. The
colours represent the number of parameters contained within an architecture.

The resulting parameter $CV_{U}$ is known in statistics as the coefficient of
variation, or relative standard deviation. When plotting the coefficient of
variation $CV_{U}$ against the trained accuracy $\mu_{T}$ in Figure 3,
tendency becomes yet more clear: selecting the architectures with low $CV_{U}$
leads to high trained accuracy $\mu_{T}$.

When choosing a NAS scoring metric, one has to consider how it correlates with
the number of parameters contained within the network. It has been shown
earlier that bigger does not necessarily mean better [31, 32]. Even though
there is a higher chance for a bigger network to contain a subnetwork, capable
of successfully fitting the data [33], there is also an increasing risk of
overfitting, and increasing training time. We can confirm the effect of the
performance saturation with our toy MNIST model both for the totality of
parameters, and for the parameters in a single layer, as demonstrated in
Figure 4.

(a)

(b)

Figure 4: Number of parameters against the architectures mean trained
performance $\mu_{T}$, computed over $N_{init}=100$ initialisations. One point
represents one architecture. The colours represent the number of units in the
first layer (a) and the second layer (b). Figure 5: The number of parameters
against the scoring metric $CV_{U}$ ($\rm\%$), or the coefficient of variation
of the untrained performance, computed over $N_{init}=100$ initialisations.
One point stands for one architecture.

Therefore, in order to find optimal architecture regardless the number of
parameters, one should use a scoring metric uncorrelated with them. Figure 5
shows that there is no significant correlation between $CV_{U}$ and the number
of parameters.

Taking all the above into consideration, we conclude that $CV_{U}$ is a
suitable scoring metric for NAS.

###  3.2 Testing the scoring metric $CV_{U}$

The results of the $CV_{U}$ performance with CIFAR-10, CIFAR-100 [24] and
ImageNet16-120 [25] are given in Table 2. We present our results based on
$100$ initialisations ($N_{init}=100$), for $N_{BS}=256$, both used by Mellor
et al. [19] and during the NAS-Bench-201 training. We also provide the two
sample t-test p-values for the statistical significance of differences between
our results and those of Mellor et al. [19], as well as for the random
baseline (p-value $<0.05$ means that the results are statistically different,
otherwise, they are considered similar). Comparisons are made both with the
best performing $N_{a}$ and with $N_{a}$ fixed to $100$ architectures. The
results show that the performance of the $CV_{U}$ scoring metric is clearly
above random for all three datasets.

Method | Time(s) | CIFAR-10 |  | CIFAR-100 |  | ImageNet16-120
---|---|---|---|---|---|---
validation | test | validation | test | validation | test
State-of-the-art
REA | $12000$ | $91.19\pm 0.31$ | $93.92\pm 0.3$ |  | $71.81\pm 1.12$ | $71.84\pm 0.99$ |  | $45.15\pm 0.89$ | $45.54\pm 1.03$
Random Search | $12000$ | $90.93\pm 0.36$ | $93.92\pm 0.31$ |  | $70.93\pm 1.09$ | $71.04\pm 1.07$ |  | $44.45\pm 1.1$ | $44.57\pm 1.25$
REINFORCE | $12000$ | $91.09\pm 0.37$ | $93.92\pm 0.32$ |  | $71.61\pm 1.12$ | $71.71\pm 1.09$ |  | $45.05\pm 1.02$ | $45.24\pm 1.18$
BOHB | $12000$ | $90.82\pm 0.53$ | $93.92\pm 0.33$ |  | $70.74\pm 1.29$ | $70.85\pm 1.28$ |  | $44.26\pm 1.36$ | $44.42\pm 1.49$
Baselines
Optimal ($N_{a}=10$) | N/A | $89.92\pm 0.75$ | $93.06\pm 0.59$ |  | $69.61\pm 1.21$ | $69.76\pm 1.25$ |  | $43.11\pm 1.85$ | $43.30\pm 1.87$
Optimal ($N_{a}=100$) | N/A | $91.05\pm 0.28$ | $93.84\pm 0.23$ |  | $71.45\pm 0.79$ | $71.56\pm 0.78$ |  | $45.37\pm 0.61$ | $45.67\pm 0.64$
Random | N/A | $83.20\pm 13.28$ | $86.61\pm 13.46$ |  | $60.70\pm 12.55$ | $60.83\pm 12.58$ |  | $33.34\pm 9.39$ | $33.13\pm 9.66$
Trainless
Mellor et al. ($N_{a}=10$) | $1.7$ | $88.47\pm 1.3$ | $91.53\pm 1.62$ |  | $66.49\pm 3.08$ | $66.63\pm 3.14$ |  | $38.33\pm 4.98$ | $38.33\pm 5.22$
Mellor et al. ($N_{a}=25$) | $4.8$ | $88.46\pm 1.42$ | $91.78\pm 1.45$ |  | $66.87\pm 2.84$ | $67.05\pm 2.89$ |  | $37.18\pm 6.11$ | $37.07\pm 6.39$
Mellor et al. ($N_{a}=100$) | $17.4$ | $88.45\pm 1.46$ | $91.61\pm 1.71$ |  | $66.42\pm 3.27$ | $66.56\pm 3.28$ |  | $36.56\pm 6.7$ | $36.37\pm 6.97$
$CV_{U}$ ($N_{a}=10$) | $19.6/19.5/14.9$ | $85.01\pm 6.08$ | $91.03\pm 2.77$ |  | $63.73\pm 5.62$ | $63.83\pm 5.65$ |  | $37.74\pm 6.89$ | $37.70\pm 7.13$
$CV_{U}$ ($N_{a}=25$) | $47.7/47.5/34.0$ | $84.91\pm 5.98$ | $91.46\pm 2.39$ |  | $63.83\pm 5.50$ | $63.92\pm 5.57$ |  | $38.42\pm 6.30$ | $38.42\pm 6.51$
$CV_{U}$ ($N_{a}=100$) | $190.0/190.4/133.9$ | $84.89\pm 6.39$ | $91.90\pm 2.27$ |  | $63.99\pm 5.61$ | $64.08\pm 5.63$ |  | $38.68\pm 6.34$ | $38.76\pm 6.62$
p-values (best $N_{a}$) |  |  | $0.319$ |  |  | $3.7\mathrm{e}{-24}$ |  |  | $0.254$
p-values ($N_{a}=100)$ |  |  | $0.023$ |  |  | $8\mathrm{e}{-17}$ |  |  | $3\mathrm{e}{-8}$
p-values (random baseline) |  |  | $5\mathrm{e}{-11}$ |  |  | $2\mathrm{e}{-7}$ |  |  | $2\mathrm{e}{-25}$

Table 2: Comparison of the trainless $CV_{U}$ metric performance against
existing NAS algorithms on CIFAR-10, CIFAR-100 [24] and ImageNet16-120 [25]
datasets. On the top, we list the best performing methods that require
training (REA [6], random search, REINFORCE [34], BOHB [35]). As a low limit
reference, the random and optimal values for $N_{a}\in\\{10,100\\}$ are given.
Then, the results from Mellor et al. [19] and our results are reported for
$N_{a}\in\\{10,25,100\\}$ with $N_{BS}=256$. Our training elapsed times are
reported in CIFAR-10/CIFAR-100/ImageNet16-120 format. Finally, the two sample
t-test p-values are provided for two cases: when comparing best performing
$N_{a}$ (bold), and with a fixed $N_{a}$=100.

The effects of number of iterations and number of selected architectures are
shown in Figures 6 and 7, respectively, on an example of CIFAR-10 [24]. The
number of picked architectures considerably increases the overall performance,
since there is more chance to involve a good architecture. The number of
iterations improves the precision of the method. Similar plots for CIFAR-100
[24] and ImageNet16-120 [25] can be found in Appendix (Figures 8, 9, 10, 11).
Table 3 shows results of our metric performance with various batch sizes,
$N_{init}$ and $N_{a}$ combinations.

(a) $N_{a}=10$

(b) $N_{a}=100$

(c) $N_{a}=25$

(d) $N_{a}=1000$

(e) $N_{a}=50$

(f) $N_{a}=5000$

Figure 6: Comparison of the coefficient of variation $CV_{U}$ performance
against mean trained accuracy $\mu_{T}$ for CIFAR-10 [24] dataset for
different number of selected architectures $N_{a}\in[10,25,50,100,1000,5000]$.
Statistics are computed over $N_{init}=100$ initialisations. One point stands
for one architecture. The colours represent the logarithm of the total number
of trainable parameters.

(a) $N_{init}=3$

(b) $N_{init}=25$

(c) $N_{init}=5$

(d) $N_{init}=50$

(e) $N_{init}=10$

(f) $N_{init}=100$

Figure 7: Comparison of the coefficient of variation $CV_{U}$ performance
against mean trained accuracy $\mu_{T}$ for CIFAR-10 [24] dataset. Statistics
are computed over varying number of initialisations
$N_{init}\in[3,5,10,25,50,100]$. Number of architectures $N_{a}=1000$. One
point stands for one architecture. Colours represent the logarithm of the
total number of trainable parameters.

We compare our results against the results presented by Mellor et al., since
in their work they also aim to discover a direct architectural property. We do
not make comparison with other trainless NAS methods, since they rely on a
supplementary model responsible for the architecture choice. In Table 2,
similar overall performances are observed. Methods are also similar in the
sense that they filter out bad architectures, rather than choose the best one.

Mellor et al. focus on correlations between linear maps (Jacobians) of input
entries. Jacobian of a given input expresses how much local perturbations
within this input impact the corresponding output. Their metric minimises the
correlation between Jacobians within a minibatch using the eigenvalues of the
correlation matrix:

$\displaystyle
S=-\sum\limits_{i=1}^{n}[\log(\sigma_{J,i}+k)+(\sigma_{J,i}+k)^{-1}],$

where $\sigma_{J,i}$ are the eigenvalues of $\Sigma$, and k is a small
constant added for numerical stability ($k=1\mathrm{e}{-5}$). It’s worth
noting that the choice of the final score’s shape is not clearly explained in
[19].

The success of the $S$ metric means, that when inputs affect the output in an
uncorrelated way, the neural network has a higher chance to distinguish
between them, and therefore to have a better trainability. Their method,
however, depends slightly on the values of the initial weights.

Our approach, on the other hand, focuses on how much variation in weights
affects the outputs. $CV_{U}$ quantifies the stability of the network against
initialisations for the same fixed data minibatch. Intuitively, if a network
is stable against random weights, it will also be less affected by weights
fluctuations during the training. It might suggest that the function
representing a stable network is relatively smooth, which allows for more
efficient training and lower overfitting risks.

As it was mentioned above, our algorithm involves two extra hyperparameters,
which may be considered as a disadvantage. The first one is the batch size:
there are significant deviations on the prediction power (with different
optimal $N_{BS}$ for each dataset, see Table 3). The second is the number of
initialisations. Besides, the fact that our method requires multiple
initialisations leads to a significantly slower performance compared to Mellor
et al. (running time grows linearly with the number of initialisations). Yet,
comparing to the methods that require training, the absolute performance speed
remains high (tens to hundreds of seconds).

Prediction accuracy improves with the number of sampled architectures (for any
batch size). This is a natural consequence of the fact that the chance of
having a well performing architecture among many architectures is higher than
among few (which is confirmed by random selection tests, see Table 2). Note
that in the work of Mellor et al. [19] increasing the number of sampled
architectures does not improve the result, which is counterintuitive. While
this could be a statistical artefact for CIFAR [24] data, for ImageNet [25]
the difference between $N_{a}=10$ and $N_{a}=100$ is statistically significant
(p-value of $5.8\mathrm{e}{-7}$).

Nevertheless, the $CV_{U}$ metric alone is not sufficient for successful NAS.
It can be partly justified by the fact that all the architectures within the
NAS-201-Benchmark are trained with the same fixed set of hyperparameters. For
some of the networks contained within the benchmark these set may not be
optimal. There is a possibility that the architectures selected by our metric
could have achieved better accuracies. We plan to investigate it in future
work, as well as to try to combine our metric with other NAS methods (for
example, the one from Mellor et al. [19]).

##  4 Conclusions

In this work we explore relashionship between the prediction performance of an
architecture and its accuracy prior to training. The principal objective is to
better understand how the neural network’s geometry affects its prediction
power. For this, we evaluate untrained accuracy over multiple random weights
initialisations. We observe that the architectures with low coefficient of
variation of untrained accuracy $CV_{U}=\sigma_{U}/\mu_{U}$ show overall
better performance. We use this observation to develop an entirely trainless
NAS technique. Our metric achieves the accuracies of $91.90\pm 2.27$,
$64.08\pm 5.63$ and $38.76\pm 6.62$ for CIFAR-10, CIFAR- [24] and a downscaled
version of ImageNet [25], respectively (when choosing among $100$
architectures, with $100$ random initialisations and evaluating accuracies on
a minibatch of $256$ data points). These accuracies are statistically above
the random baseline, which leads to the conclusion that the stability of a
network against initialisations is an indicator of its trainability. However,
since this metric does not guarantee the best architecture at all times, we
consider that the stability is not the only property that influences the
neural architecture’s performance. Combining our method with others (for
example, the one from Mellor et al. [19]), might lead to more stable results.
We plan to explore various combinations of the $CV_{U}$ metric with other
methods in future work.

##  5 Acknowledgement

We would like to express our deepest gratitude to Dr. Ayako Nakata and Dr.
Guillaume Lambard for their continuous support and valuable discussions.

## References

  * [1] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. Le, A. Kurakin, Large-scale evolution of image classifiers, arXiv preprint arXiv:1703.01041 (2017).
  * [2] H. Liu, K. Simonyan, O. Vinyals, C. Fernando, K. Kavukcuoglu, Hierarchical representations for efficient architecture search, arXiv preprint arXiv:1711.00436 (2017).
  * [3] M. Suganuma, S. Shirakawa, T. Nagao, A genetic programming approach to designing convolutional neural network architectures, in: Proceedings of the genetic and evolutionary computation conference, 2017, pp. 497–504.
  * [4] T. Elsken, J. H. Metzen, F. Hutter, Efficient multi-objective neural architecture search via lamarckian evolution, arXiv preprint arXiv:1804.09081 (2018).
  * [5] P. J. Angeline, G. M. Saunders, J. B. Pollack, An evolutionary algorithm that constructs recurrent neural networks, IEEE Transactions on Neural Networks 5 (1) (1994) 54–65.
  * [6] E. Real, A. Aggarwal, Y. Huang, Q. V. Le, Regularized evolution for image classifier architecture search, in: Proceedings of the aaai conference on artificial intelligence, Vol. 33, 2019, pp. 4780–4789.
  * [7] P. I. Frazier, A tutorial on bayesian optimization, arXiv preprint arXiv:1807.02811 (2018).
  * [8] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, N. De Freitas, Taking the human out of the loop: A review of bayesian optimization, Proceedings of the IEEE 104 (1) (2015) 148–175.
  * [9] J. Bergstra, D. Yamins, D. D. Cox, Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures, in: Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28, ICML’13, JMLR.org, 2013, p. I–115–I–123.
  * [10] T. Domhan, J. T. Springenberg, F. Hutter, Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves, in: Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, AAAI Press, 2015, p. 3460–3468.
  * [11] H. Mendoza, A. Klein, M. Feurer, J. T. Springenberg, F. Hutter, Towards automatically-tuned neural networks, in: Workshop on Automatic Machine Learning, 2016, pp. 58–65.
  * [12] G. Lambard, E. Gracheva, SMILES-x: autonomous molecular compounds characterization for small datasets without descriptors, Machine Learning: Science and Technology 1 (2) (2020) 025004.  doi:10.1088/2632-2153/ab57f3.
URL https://doi.org/10.1088/2632-2153/ab57f3

  * [13] B. Zoph, Q. V. Le, Neural architecture search with reinforcement learning, arXiv preprint arXiv:1611.01578 (2016).
  * [14] B. Zoph, V. Vasudevan, J. Shlens, Q. V. Le, Learning transferable architectures for scalable image recognition, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 8697–8710.
  * [15] H. Pham, M. Y. Guan, B. Zoph, Q. V. Le, J. Dean, Efficient neural architecture search via parameter sharing, arXiv preprint arXiv:1802.03268 (2018).
  * [16] T. Elsken, J. Metzen, F. Hutter, Neural architecture search: A survey. arxiv 2018, arXiv preprint arXiv:1808.05377 (2018).
  * [17] R. Istrate, F. Scheidegger, G. Mariani, D. Nikolopoulos, C. Bekas, A. C. I. Malossi, Tapas: Train-less accuracy predictor for architecture search, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 2019, pp. 3927–3934.
  * [18] B. Deng, J. Yan, D. Lin, Peephole: Predicting network performance before training, arXiv preprint arXiv:1712.03351 (2017).
  * [19] J. Mellor, J. Turner, A. Storkey, E. J. Crowley, Neural architecture search without training, arXiv preprint arXiv:2006.04647v1 (2020).
  * [20] X. Dong, Y. Yang, Nas-bench-102: Extending the scope of reproducible neural architecture search, arXiv preprint arXiv:2001.00326 (2020).
  * [21] H. Zhou, J. Lan, R. Liu, J. Yosinski, Deconstructing lottery tickets: Zeros, signs, and the supermask, in: Advances in Neural Information Processing Systems, 2019, pp. 3597–3607.
  * [22] Y. LeCun, C. Cortes, C. Burges, Mnist handwritten digit database, ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist 2 (2010).
  * [23] A. Gaier, D. Ha, Weight agnostic neural networks, in: Advances in Neural Information Processing Systems, 2019, pp. 5364–5378.
  * [24] A. Krizhevsky, G. Hinton, et al., Learning multiple layers of features from tiny images, Master’s thesis, Department of Computer Science, University of Toronto (2009).
  * [25] P. Chrabaszcz, I. Loshchilov, F. Hutter, A downsampled variant of imagenet as an alternative to the cifar datasets, arXiv preprint arXiv:1707.08819 (2017).
  * [26] F. Chollet, et al., Keras, https://keras.io (2015).
  * [27] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, X. Zheng, Tensorflow: Large-scale machine learning on heterogeneous systems, software available from tensorflow.org (2015).
URL http://tensorflow.org/

  * [28] K. He, X. Zhang, S. Ren, J. Sun, Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, in: Proceedings of the IEEE international conference on computer vision, 2015, pp. 1026–1034.
  * [29] V. Nair, G. E. Hinton, Rectified linear units improve restricted boltzmann machines, in: ICML, 2010, pp. 807–814.
  * [30] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, in: Y. Bengio, Y. LeCun (Eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
URL http://arxiv.org/abs/1412.6980

  * [31] Y. N. Dauphin, Y. Bengio, Big neural networks waste capacity, arXiv preprint arXiv:1301.3583 (2013).
  * [32] Y. LeCun, J. S. Denker, S. A. Solla, Optimal brain damage, in: Advances in neural information processing systems, 1990, pp. 598–605.
  * [33] J. Frankle, M. Carbin, The lottery ticket hypothesis: Finding sparse, trainable neural networks, arXiv preprint arXiv:1803.03635 (2018).
  * [34] R. J. Williams, Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine learning 8 (3-4) (1992) 229–256.
  * [35] S. Falkner, A. Klein, F. Hutter, Bohb: Robust and efficient hyperparameter optimization at scale, arXiv preprint arXiv:1807.01774 (2018).

##  Appendix A Appendix

Table 3:

CIFAR-100
---
Batch size
| 2 | 4 | 8 | 16 | 32
$N_{a}$ | $N_{init}$ | Validation | Test | Validation | Test | Validation | Test | Validation | Test | Validation | Test
10 | $10$ | $59.44\pm 12.50$ | $59.54\pm 12.51$ | $65.71\pm 6.03$ | $65.86\pm 6.02$ | $62.71\pm 8.44$ | $62.84\pm 8.44$ | $62.00\pm 8.75$ | $62.09\pm 8.82$ | $62.46\pm 8.16$ | $62.58\pm 8.19$
$100$ | $62.30\pm 9.05$ | $62.44\pm 9.07$ | $62.62\pm 7.28$ | $62.71\pm 7.27$ | $62.33\pm 7.58$ | $62.44\pm 7.57$ | $63.65\pm 6.93$ | $63.71\pm 6.99$ | $59.60\pm 8.95$ | $59.71\pm 9.04$
25 | $10$ | $58.00\pm 13.99$ | $58.11\pm 13.95$ | $66.33\pm 4.84$ | $66.48\pm 4.84$ | $65.67\pm 5.22$ | $65.79\pm 5.22$ | $64.60\pm 5.23$ | $64.67\pm 5.30$ | $60.45\pm 9.01$ | $60.52\pm 9.08$
$100$ | $60.14\pm 10.26$ | $60.23\pm 10.24$ | $62.38\pm 7.46$ | $62.48\pm 7.49$ | $62.47\pm 5.97$ | $62.57\pm 6.00$ | $63.76\pm 6.84$ | $63.84\pm 6.91$ | $58.77\pm 9.31$ | $58.86\pm 9.37$
100 | $10$ | $58.06\pm 13.65$ | $58.19\pm 13.64$ | $66.64\pm 3.24$ | $66.74\pm 3.27$ | $66.20\pm 4.02$ | $66.27\pm 4.05$ | $64.80\pm 4.85$ | $64.94\pm 4.94$ | $59.60\pm 8.95$ | $59.71\pm 9.04$
$100$ | $60.42\pm 8.19$ | $60.49\pm 8.18$ | $63.30\pm 6.11$ | $63.38\pm 6.09$ | $61.87\pm 5.83$ | $61.98\pm 5.87$ | $65.78\pm 5.29$ | $65.88\pm 5.32$ | $60.08\pm 8.62$ | $60.15\pm 8.71$
Batch size
| 64 | 128 | 256 | 512 |  |
$N_{a}$ | $N_{init}$ | Validation | Test | Validation | Test | Validation | Test | Validation | Test |  |
10 | $10$ | $62.20\pm 7.88$ | $62.33\pm 7.89$ | $63.21\pm 7.11$ | $63.31\pm 7.19$ | $62.96\pm 7.68$ | $63.05\pm 7.67$ | $62.20\pm 7.97$ | $62.32\pm 8.00$ |  |
$100$ | $59.77\pm 10.35$ | $59.88\pm 10.38$ | $60.46\pm 8.83$ | $60.59\pm 8.86$ | $63.73\pm 5.62$ | $63.83\pm 5.65$ | $64.28\pm 5.45$ | $64.38\pm 5.49$ |  |
25 | $10$ | $62.49\pm 7.37$ | $62.61\pm 7.40$ | $63.42\pm 7.02$ | $63.53\pm 7.08$ | $61.91\pm 8.13$ | $62.05\pm 8.14$ | $61.51\pm 8.48$ | $61.63\pm 8.51$ |  |
$100$ | $60.03\pm 9.68$ | $60.15\pm 9.68$ | $60.34\pm 7.97$ | $60.45\pm 8.00$ | $63.83\pm 5.50$ | $63.92\pm 5.57$ | $64.15\pm 5.11$ | $64.23\pm 5.19$ |  |
100 | $10$ | $63.10\pm 6.03$ | $63.21\pm 6.01$ | $63.74\pm 5.93$ | $63.89\pm 5.97$ | $61.98\pm 7.44$ | $62.09\pm 7.45$ | $60.82\pm 8.81$ | $60.96\pm 8.82$ |  |
$100$ | $60.54\pm 8.54$ | $60.64\pm 8.56$ | $60.91\pm 7.84$ | $61.01\pm 7.87$ | $63.99\pm 5.61$ | $64.08\pm 5.63$ | $64.01\pm 5.06$ | $64.10\pm 5.10$ |  |
CIFAR-10
Batch size
| 2 | 4 | 8 | 16 | 32
$N_{a}$ | $N_{init}$ | Validation | Test | Validation | Test | Validation | Test | Validation | Test | Validation | Test
10 | $10$ | $84.02\pm 7.41$ | $88.45\pm 5.70$ | $85.90\pm 4.04$ | $89.03\pm 4.75$ | $85.28\pm 5.78$ | $90.79\pm 3.21$ | $86.62\pm 4.00$ | $88.67\pm 7.46$ | $83.20\pm 7.18$ | $87.52\pm 8.04$
$100$ | $83.94\pm 6.10$ | $90.68\pm 2.94$ | $85.79\pm 5.33$ | $91.50\pm 2.71$ | $83.32\pm 8.00$ | $91.46\pm 2.42$ | $85.01\pm 6.08$ | $90.96\pm 3.07$ | $85.63\pm 5.05$ | $90.55\pm 3.24$
25 | $10$ | $84.14\pm 6.68$ | $88.42\pm 4.93$ | $85.98\pm 4.11$ | $89.37\pm 4.16$ | $85.42\pm 6.16$ | $91.08\pm 3.38$ | $86.49\pm 4.15$ | $89.89\pm 5.49$ | $83.04\pm 6.37$ | $87.62\pm 7.68$
$100$ | $88.42\pm 4.93$ | $90.79\pm 3.51$ | $89.37\pm 4.16$ | $91.82\pm 2.55$ | $91.08\pm 3.38$ | $91.56\pm 1.74$ | $89.89\pm 5.49$ | $90.89\pm 2.96$ | $87.62\pm 7.68$ | $91.15\pm 2.29$
100 | $10$ | $84.80\pm 4.52$ | $87.99\pm 5.02$ | $85.51\pm 3.72$ | $89.85\pm 3.55$ | $86.23\pm 5.05$ | $91.57\pm 1.77$ | $86.37\pm 3.59$ | $90.49\pm 4.09$ | $82.02\pm 6.49$ | $87.99\pm 8.17$
$100$ | $83.81\pm 5.20$ | $91.04\pm 2.50$ | $87.04\pm 3.99$ | $92.37\pm 1.85$ | $82.68\pm 7.62$ | $91.57\pm 1.65$ | $84.89\pm 6.39$ | $91.43\pm 1.64$ | $86.23\pm 4.13$ | $91.36\pm 1.96$
Batch size
| 64 | 128 | 256 | 512 |  |
$N_{a}$ | $N_{init}$ | Validation | Test | Validation | Test | Validation | Test | Validation | Test |  |
10 | $10$ | $84.65\pm 6.66$ | $87.31\pm 7.86$ | $85.31\pm 5.42$ | $88.65\pm 7.35$ | $85.60\pm 5.02$ | $89.97\pm 3.89$ | $86.35\pm 4.25$ | $91.15\pm 2.48$ |  |
$100$ | $86.19\pm 4.94$ | $91.19\pm 2.71$ | $87.59\pm 2.55$ | $90.49\pm 3.67$ | $87.98\pm 1.95$ | $91.03\pm 2.77$ | $88.29\pm 1.64$ | $91.48\pm 1.82$ |  |
25 | $10$ | $83.82\pm 6.81$ | $87.31\pm 7.54$ | $85.71\pm 4.72$ | $87.98\pm 8.87$ | $85.48\pm 5.36$ | $90.13\pm 3.59$ | $86.68\pm 2.95$ | $91.34\pm 1.93$ |  |
$100$ | $86.29\pm 3.60$ | $91.75\pm 2.17$ | $87.63\pm 2.21$ | $91.14\pm 3.22$ | $88.03\pm 1.74$ | $91.46\pm 2.39$ | $88.27\pm 1.48$ | $91.51\pm 1.75$ |  |
100 | $10$ | $83.80\pm 6.39$ | $88.18\pm 7.12$ | $86.27\pm 3.97$ | $88.88\pm 7.90$ | $86.05\pm 4.56$ | $90.33\pm 3.86$ | $86.44\pm 2.57$ | $91.25\pm 2.23$ |  |
$100$ | $86.39\pm 3.31$ | $92.50\pm 1.59$ | $87.49\pm 2.46$ | $92.32\pm 2.16$ | $88.18\pm 1.66$ | $91.90\pm 2.27$ | $88.39\pm 1.37$ | $91.52\pm 1.87$ |  |
ImageNet16-120
Batch size
| 2 | 4 | 8 | 16 | 32
$N_{a}$ | $N_{init}$ | Validation | Test | Validation | Test | Validation | Test | Validation | Test | Validation | Test
10 | $10$ | $31.40\pm 8.43$ | $30.96\pm 8.66$ | $33.02\pm 7.71$ | $31.85\pm 8.62$ | $33.73\pm 7.58$ | $33.39\pm 7.83$ | $34.29\pm 6.87$ | $34.04\pm 7.15$ | $32.78\pm 7.51$ | $32.37\pm 7.83$
$100$ | $31.97\pm 7.78$ | $31.49\pm 8.02$ | $37.46\pm 6.53$ | $37.39\pm 6.78$ | $37.96\pm 6.08$ | $37.91\pm 6.33$ | $37.74\pm 6.89$ | $37.70\pm 7.13$ | $35.72\pm 9.34$ | $35.59\pm 9.69$
25 | $10$ | $32.09\pm 8.11$ | $31.66\pm 8.39$ | $32.31\pm 8.36$ | $31.93\pm 8.66$ | $34.95\pm 6.78$ | $34.71\pm 7.03$ | $34.11\pm 6.50$ | $33.84\pm 6.78$ | $32.93\pm 6.95$ | $32.53\pm 7.23$
$100$ | $36.67\pm 6.63$ | $36.59\pm 6.93$ | $37.86\pm 5.93$ | $37.82\pm 6.21$ | $38.44\pm 5.90$ | $38.47\pm 6.19$ | $38.42\pm 6.30$ | $38.42\pm 6.51$ | $36.44\pm 9.49$ | $36.37\pm 9.84$
100 | $10$ | $31.97\pm 7.78$ | $31.49\pm 8.02$ | $32.66\pm 8.48$ | $32.36\pm 8.75$ | $34.13\pm 6.89$ | $33.81\pm 7.11$ | $34.99\pm 5.39$ | $34.69\pm 5.66$ | $32.97\pm 5.94$ | $32.46\pm 6.19$
$100$ | $36.93\pm 6.38$ | $36.89\pm 6.64$ | $38.78\pm 5.60$ | $38.72\pm 5.85$ | $39.11\pm 5.03$ | $39.17\pm 5.23$ | $38.68\pm 6.34$ | $38.76\pm 6.62$ | $36.73\pm 9.92$ | $36.73\pm 10.23$
Batch size
| 64 | 128 | 256 | 512 |  |
$N_{a}$ | $N_{init}$ | Validation | Test | Validation | Test | Validation | Test | Validation | Test |  |
10 | $10$ | $33.33\pm 7.40$ | $33.02\pm 7.71$ | $32.54\pm 8.11$ | $32.85\pm 7.78$ | $34.02\pm 7.91$ | $33.72\pm 8.30$ | $33.42\pm 7.61$ | $33.11\pm 7.94$ |  |
$100$ | $36.55\pm 8.16$ | $36.47\pm 8.49$ | $36.21\pm 8.12$ | $36.09\pm 8.43$ | $35.64\pm 8.42$ | $35.50\pm 8.77$ | $35.04\pm 8.40$ | $34.90\pm 8.72$ |  |
25 | $10$ | $33.39\pm 6.87$ | $33.02\pm 7.11$ | $32.32\pm 7.95$ | $32.66\pm 7.65$ | $33.90\pm 7.74$ | $33.58\pm 8.08$ | $33.37\pm 7.65$ | $33.06\pm 7.99$ |  |
$100$ | $37.77\pm 7.76$ | $37.75\pm 8.03$ | $35.64\pm 8.82$ | $35.51\pm 9.13$ | $36.75\pm 7.84$ | $36.71\pm 8.14$ | $34.92\pm 8.18$ | $34.74\pm 8.45$ |  |
100 | $10$ | $34.02\pm 6.41$ | $33.64\pm 6.64$ | $32.69\pm 7.06$ | $33.06\pm 6.81$ | $34.08\pm 7.39$ | $33.79\pm 7.73$ | $34.04\pm 7.12$ | $33.79\pm 7.49$ |  |
$100$ | $37.48\pm 8.54$ | $37.49\pm 8.83$ | $37.35\pm 7.69$ | $37.27\pm 8.05$ | $38.11\pm 6.75$ | $38.11\pm 7.06$ | $35.61\pm 7.81$ | $35.46\pm 8.08$ |  |

(a) $N_{a}=10$

(b) $N_{a}=100$

(c) $N_{a}=25$

(d) $N_{a}=1000$

(e) $N_{a}=50$

(f) $N_{a}=5000$

Figure 8: Comparison of the relative standard deviation $CV_{U}$ ($\rm\%$)
performance against mean trained accuracy $\mu_{T}$ for CIFAR-100 [24] dataset
for different number of selected architectures
$N_{a}\in[10,25,50,100,1000,5000]$. Statistics are computed over
$N_{init}=100$ initialisations. One point represents one architecture. The
colours represent the logarithm of the total number of trained parameters.

(a) $N_{init}=3$

(b) $N_{init}=25$

(c) $N_{init}=5$

(d) $N_{init}=50$

(e) $N_{init}=10$

(f) $N_{init}=100$

Figure 9: Comparison of the relative standard deviation $CV_{U}$ ($\rm\%$)
performance against mean trained accuracy $\mu_{T}$ for CIFAR-100 [24]
dataset. Statistics are computed over varying number of initialisations
$N_{init}\in[3,5,10,25,50,100]$. One point stands for one architecture. The
colours represent the logarithm of the total number of trained parameters.

(a) $N_{a}=10$

(b) $N_{a}=100$

(c) $N_{a}=25$

(d) $N_{a}=1000$

(e) $N_{a}=50$

(f) $N_{a}=5000$

Figure 10: Comparison of the relative standard deviation $CV_{U}$ ($\rm\%$)
performance against mean trained accuracy $\mu_{T}$ for ImageNet16-120 dataset
[25] for different number of selected architectures
$N_{a}\in[10,25,50,100,1000,5000]$. Statistics are computed over
$N_{init}=100$ initialisations. One point represents one architecture. The
colours represent the logarithm of the total number of trained parameters.

(a) $N_{init}=3$

(b) $N_{init}=25$

(c) $N_{init}=5$

(d) $N_{init}=50$

(e) $N_{init}=10$

(f) $N_{init}=100$

Figure 11: Comparison of the relative standard deviation $CV_{U}$ ($\rm\%$)
performance against mean trained accuracy $\mu_{T}$ for ImageNet16-120 dataset
[25]. Statistics are computed over varying number of initialisations
$N_{init}\in[3,5,10,25,50,100]$. One point stands for one architecture. The
colours represent the logarithm of the total number of trained parameters.