# Beyond KNN: Deep Neighborhood Learning for WiFi-based Indoor Positioning
Systems

1st Yinhuan Dong, 2nd Francisco Zampella, 3rd Firas Alsehly  Edinburgh
Research Centre
Huawei Technologies Research and Development (UK) Ltd
Edinburgh, UK
{yinhuan.dong1, francisco.zampella<EMAIL_ADDRESS>
###### Abstract

K-Neares Neighbors (KNN) and its variant weighted KNN (WKNN) have been
explored for years in both academy and industry to provide stable and reliable
performance in WiFi-based indoor positioning systems. Such algorithms estimate
the location of a given point based on the locality information from the
selected nearest WiFi neighbors according to some distance metrics calculated
from the combination of WiFi received signal strength (RSS). However, such a
process does not consider the relational information among the given point,
WiFi neighbors, and the WiFi access points (WAPs). Therefore, this study
proposes a novel Deep Neighborhood Learning (DNL). The proposed DNL approach
converts the WiFi neighborhood to heterogeneous graphs, and utilizes deep
graph learning to extract better representation of the WiFi neighborhood to
improve the positioning accuracy. Experiments on 3 real industrial datasets
collected from 3 mega shopping malls on 26 floors have shown that the proposed
approach can reduce the mean absolute positioning error by 10% to 50% in most
of the cases. Specially, the proposed approach sharply reduces the root mean
squared positioning error and 95% percentile positioning error, being more
robust to the outliers than conventional KNN and WKNN.

###### Index Terms:

Indoor positioning, WiFi fingerprinting ,deep learning, graph neural networks,
smartphone.

##  I Introduction

The proliferation of smartphones has provided an excellent tool to keep people
connected, provide them with the latest information, and in general making
life easier for many. These devices and the applications around them provide
services tailored to the user and their context, but they rely on up to date
information about the device. Among the most useful information is the
position of the user, that in outdoor scenarios is typically obtained using
Global Navigation Satellite Systems. In indoor scenarios due to the
attenuation and multipaths of the signals, the accuracy of the positioning is
severely affected [1] and the service needs to rely on other technologies and
techniques to improve it.

In most indoor environments, the devices are able to connect to many wireless
networks that can be used for positioning including cellular, WiFi, Bluetooth,
Ultra Wide Band, among others. The most widely deployed technology is WiFi,
and as an example, in shopping malls it is typically possible to observe
between ten and hundreds of WiFi access points (WAP) at any given point near
shops. The WiFi technology offers several metrics that can be used for
positioning [2], including the angle of Arrival [3, 4], time of arrival [5,
6], time difference of arrival [7] and the received signal strength (RSS) [8,
9]. Among those, the RSS has become one of the most commonly used sources of
information because it does not require extra hardware and it is available in
all devices. In open spaces, it is possible to implement a trilateration from
the position of the WAPs, and estimating the distances to the user with the
RSS measured in dB and a log distance model [10], but even if the positions
were known, that model changes according to the unknown conditions of the
obstructions between the user and the WAPs.

As a way to overcome the non predictable distribution of the RSS values with
position, is it common to measure the RSS values from all observable WAPs in a
grid of samples covering all the areas of interest. These measurements can be
used to estimate more complex models of the RSS-distance models [11], the RSS-
position model [12], as reference points (fingerprints) in a weighted
K-Nearest Neighbors (WKNN) estimation [13, 14, 15, 16], or other machine
learning methods [17, 18, 19, 20]. In most cases it has been observed that the
wide distribution of the data in the RSS-distance and RSS-position modeling
doesn’t allow to have a local model, but in the WKNN estimation, it only use
the locality of the neighbors, but we loose the information from the RSS
values. The authors of this paper propose _Deep Neighborhood Learning_ to
analyse the RSS distribution using a deep graph neural network-based model but
focusing in the local community or neighborhood of similar reference points.

The contributions of this work are summarized as follows:

  * •

We propose a novel Deep Neighborhood Learning approach to extract better
representation of the WiFi neighborhood to improve the positioning accuracy.

  * •

In the proposed approach, we develop a deep graph neural network-based
positioning model to learn the relational information (the topology and the
features) from the WiFi neighborhood.

  * •

Compared to conventional positioning algorithms using the WiFi neighborhood,
the experiments on three real large datasets have shown that the proposed
approach can sharply reduce the positioning error and the influence from the
outliers.

The rest of the paper is distributed as follows: Section II will discuss the
proposed architecture, Section III will describe the experiments, Section IV
will show the results and analyse them, and in Section V we will draw the
general conclusions.

##  II Methodology

As illustrated above, to overcome the challenges of missing RSS features in
conventional KNN and its variant WKNN, we propose a _Deep Neighborhood
Learning_ approach to learn the relation among one given fingerprint (FP) and
its WiFi neighbors, and hence provide better positioning accuracy for WiFi-
based indoor positioning systems.

###  II-A The local community

A local community represents a snapshot of the RSS distributions in the
vicinity of any given FP. Each local community is constructed from a
center/target FP (TFP) and its closest neighbor FPs (NFP), as well as all the
WiFi measurements that can be detected among the FPs in the local community.

To select the NFPs of a certain TFP, we first calculate the distance from the
center/target FP to all the reference FPs. In this work, we use the Manhattan
distance to represent the distance between two FPs in the signal space. The
Manhattan distance has been shown to be effective to represent the similarity
between two WiFi fingerprints, and has been adopted by many WiFi
fingerprinting-based positioning algorithms [14, 15, 16]. Supposing there are
$n$ WAPs in the entire dataset, the RSS values of one FP are converted to a
vector of length $n$, where the non-detected signals are padding with a
default value of 0. So that the Manhattan distance between the two FP vectors
of $FP_{1}=[RSS_{1}^{1},RSS_{2}^{1},...RSS_{n}^{1}]$ and
$FP_{2}=[RSS_{1}^{2},RSS_{2}^{2},...RSS_{n}^{2}]$ can be calculated by:

$|FP_{1}-FP_{2}|=\sum_{i=1}^{n}\left|RSS_{i}^{1}-RSS_{i}^{2}\right|$ (1)

Therefore, for $m$ FPs, we will have $m$ TFPs, and accordingly $m-1$ distances
from a certain TFP to all other reference FPs. We select the top $k$ FPs with
the shortest distance as the NFPs. The local community will consist of the
target FP and the neighbor FPs as:

$C=\\{TFP,NFP_{1},NFP_{2},...,NFP_{k}\\}$ (2)

###  II-B Graph representations of local communities

The local communities represent more than just the fingerprints that are
similar to the TFP, the relationships established by the RSS observed by the
members of that set to the WAPs in the vicinity offer a glimpse of the local
model of RSS in there. The community can be represented as a heterogeneous
graph as described in [21], but focusing only in the area of interest. Given a
training reference set and a test set, 2 types of graphs constructions are
required, the neighbors graphs in the training reference set, where each
reference FP finds neighbors in the rest of the training set, and the
neighbors graphs in the test set, where each test FP finds the neighbors among
the training set. In the training case, the graph shown in Figure 1 can be
created with 3 types of nodes, the neighbor FPs, the target FP and the WAP
nodes. The neighbor FP nodes include information about the position of that
reference point ($F_{W}$), the target FP has a position masked with zeros, and
the WAP node stores the MAC index of the WAP ($F_{A}$). The observations of
each FP ($FP_{i}=\\{MAC_{i_{1}}:RSS_{i_{1}},...,MAC_{i_{n}}:RSS_{i_{n}}\\}$)
are encoded in the edges between FP nodes and WAP nodes ($E_{W\rightarrow A}$
and $E_{A\rightarrow W}$), where the edge from (to) WAP node $i$ to (from) FP
node $j$ has a weight equal to the RSS observed in FP $j$ for WAP $i$. Each
graph of the local community of TFP $i$ in the dataset for training can be
denoted by $g_{train}(i)=\\{F_{W},F_{A},E_{W\rightarrow A},E_{A\rightarrow
W}\\}$. Each graph is associated with a label of the location of the TFP node.

Figure 1: An example of the graph representation of the local community for
training. Figure 2: An example of the graph representation of the local
community for inference/testing.

For inference of the test set, the TFP $j$ has no label, but the same method
to construct a local community is used, selecting the NFPs from the training
dataset, and constructing a similar graph $g_{inf}(j)$ as shown in Figure 2.

###  II-C Positioning with Deep Neighborhood Learning

Figure 3: Structure of the proposed supervised deep graph neural networks-
based positioning model.

The positioning problem is now translated to making inference of the unlabeled
graph $g_{inf}$ by a model trained with labeled graphs
$G_{train}=\\{g_{1},g_{2},...,g_{n}\\}$. The labels are denoted by
$P={p_{1},p_{2},...p_{n}}$, where $p_{i}$ denotes the position of the $i$th
$g_{train}$. To solve such a problem, we propose a supervised model based on
graph neural networks. As the structure of the proposed model is shown in
Figure 3, the model is constructed of multiple modules:

  * •

WiFi FP feature extractor: this module is a 3-layer perceptron with hidden
size of 8 to extract latent features from $F_{W}$.

  * •

WAP feature extractor: this module is constructed of one embedding layer with
hidden size of 8 to extract the embedding of the Mac address indices $F_{A}$.

  * •

Node embedding extractor: this module contains two Graph Isomorphism Network
(GIN) [23] layers. It aggregate the node features from both types of the nodes
through the weighted edges (edges with edge features) and extract the node
embedding.

  * •

Graph embedding extractor: this module takes the sum of the mean readout of
each type of nodes as the graph embedding.

  * •

Position estimator: this module is a 2-layer perceptron with hidden size of 64
to make predictions from the graph embedding.

To train the model, we minimize the loss of mean squared error (MSE) between
the labels $P$ and the predictions $P^{\prime}$. The MSE loss function is
defined as follows:

$\mathrm{MSE}=\frac{1}{b}\sum_{i=1}^{b}\left(P_{i}-{P}^{\prime}\right)^{2}$
(3)

where $b$ denotes the number of training samples in each batch.

##  III Experimental Settings

###  III-A Data

The proposed method was evaluated on three large Huawei WiFi indoor
positioning datasets from: Joycity, Universal Harbor, and Dawan Mall (three
huge shopping malls in Beijing and Shanghai in China). The datasets are
obtained from users submitted data, calibrated using the method described in
[22] and manually map matched to the floor plans.

The details of the datasets are shown in Tables I, II and III.

TABLE I: Details of the Huawei indoor positioning dataset I (Joycity) Floor | -3 | -2 | -1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Total
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Number of FPs | 1188 | 2215 | 3953 | 30386 | 8834 | 3386 | 3132 | 5310 | 6240 | 3354 | 1912 | 1446 | 1827 | 70168
Detected Mac addresses | 1165 | 2112 | 3941 | 5675 | 4381 | 3111 | 2562 | 2440 | 2752 | 2085 | 1445 | 900 | 835 | 8971
TABLE II: Details of the Huawei indoor positioning dataset II (Universal harbor) Floor | -3 | -2 | -1 | 1 | 2 | 3 | 4 | 5 | Total
---|---|---|---|---|---|---|---|---|---
Number of FPs | 1681 | 18484 | 17491 | 38763 | 6044 | 7641 | 8676 | 2136 | 100916
Detected Mac addresses | 1271 | 3196 | 3646 | 5992 | 3834 | 2608 | 2387 | 1891 | 8384
TABLE III: Details of the Huawei indoor positioning dataset III (Dawan mall) Floor | -3 | -2 | -1 | 1 | 2 | Total
---|---|---|---|---|---|---
Number of FPs | 4144 | 41121 | 1640 | 19784 | 7078 | 73767
Detected Mac addresses | 1279 | 2348 | 2766 | 6366 | 3623 | 8728

###  III-B Training settings

Each dataset (per floor) was partitioned into training, validation and test
sets according to the ratio of 6:2:2. In this study, we focus on 2-dimension
positioning problem, and hence we trained floor-based model for each floor in
each building. Each model maintained the same structure.

For better fitting of the model, we supervised the variation of the validation
loss between two epochs and adjust the learning rate dynamically. Initially,
the learning rate was set to 0.01. The learning rate was reduced by a factor
of 0.1 if the validation loss does not decrease in 3 epochs till the learning
rate reaches the minimum of 0.0001.

Besides, we conducted repeated training with different batch size (64, 128,
and 256) of graphs in each training session of 100 epochs. In each training
session, the model with the lowest validation loss was saved for later testing
and evaluations.

###  III-C Evaluation Metrics

To evaluate the positioning accuracy, we calculated the mean absolute error
(MAE) and the root mean squared error (RMSE):

RMSE $\displaystyle=\sqrt{\frac{\sum_{i=1}^{n}e_{i}}{n}}$ (4) MAE
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sqrt{e}_{i}$

where:

$e_{i}=\left(P_{i,x}-{P^{\prime}}_{i,x}\right)^{2}+\left(P_{i,y}-{P^{\prime}}_{i,y}\right)^{2}$
(5)

Also, we compared the cumulative distribution error by sorting the $e_{i}$
from lowest to highest and take the square root of the 68% and 95% point,
respectively.

##  IV Result and Analysis

(a)

(b)

(c)

Figure 4: Comparisons of mean absolute error using different positioning
algorithms on the three buildings: (a) Joycity; (b) Universal Harbor; (c)
Dawan Mall.

(a)

(b)

(c)

Figure 5: Comparisons of root mean squared error using different positioning
algorithms on the three buildings: (a) Joycity; (b) Universal Harbor; (c)
Dawan Mall.

In this section, we analyze the experimental results and evaluate the proposed
model. Specially, We compare the positioning results to an unsupervised
learning algorithm of k-nearest neighbors (KNN) which uses the similar
strategy of WiFi neighbor selection. As illustrated previously, KNN and its
variant Weighted KNN (WKNN) calculate the position of one given test point by
taking the mean or the weighted mean of the selected WiFi neighbors. Such
algorithms narrow down the positioning problem from the entire interested area
(floor, in this study) to a local community constructed by the neighbor WiFi
fingerprints. However, they do not have a learning process to infer the final
location but simply calculate the mean or weighted mean of the neighbors
location, which attributes to low inference ability.

Two standard positioning algorithms of KNN and WKNN were implemented for
comparison in this study:

  * •

KNN: implemented with scikit-learn K Nearest Neighbors Regression [24]; number
of neighbor was set to 10; Manhattan distance was set to the distance metric.

  * •

WKNN: similar to KNN but also set the weight as the inverse the distance in
prediction.

As shown in Figure 4, using the MAE, the proposed model outperform the KNN and
WKNN in 25 and 23 out of 26 cases. In detail, we can see from Table IV that
the proposed model can provide a 10% to 50% reduction of the MAE in 18 (KNN)
and 16 (WKNN) of the cases. Rather than simply taking the mean or the weighted
mean position of the WiFi neighbors, the proposed model can well learn the
WiFi neighborhood through the node features, edge features, and the topology
information to make better predictions of the location.

The proposed model shows even better improvement in RMSE. As we can observe
from the Table IV, the proposed model shows lower RMSE than the other two
algorithms in all 26 cases. Particularly, the reduction of RMSE in most of the
cases (19 cases against KNN; 15 cases against WKNN) is higher than 30%.
Additionally, the proposed model provides much lower RMSE in some specific
cases, particularly when the dataset has a large data volume and a large
amount of detected Mac addresses. For instance, 5992 Mac addresses have been
detected among 38763 FPs on the first floor of Universal harbor. Such large
dataset usually contains more uncertainty and noise; however, the proposed
model is able to provide approximatelly 40% less RMSE than the other two
algorithms. Similar cases can also be found in Joycity and Dawan Mall from
Table V and 5. This illustrates that the proposed model can provide even much
smoother and more accurate predictions than the other two if the data is
noisier.

Last bu not least, the cumulative positioning error of different algorithms
was compared. It can be seen from Table V that the proposed model challenged
KNN and WKNN in half of the cases, when using the 68 percentile of the
positioning accuracy (68% of the CDF). In the remaining cases, it can be
observed that the improvement of the proposed model degrade when the cases
have lower data density. For example, on floor -3 and 5 in Universal Harbor,
the proposed model is 18% and 28% worse than WKNN, respectively. Similar
results can also be found in other floors, particularly some top floors and
underground floors with less data. Nevertheless, the proposed model shows
again superb performance in the 95 percentile positioning accuracy (95% of the
CDF). The model can always provide much lower error than KNN and WKNN, which
suggest that the proposed algorithm is more robust to outliers in large
datasets like the ones observed in the middle floors or in lower density areas
like the top or underground floors.

TABLE IV: Number of cases that the proposed model shows better positioning performance than KNN and WKNN Percentage of improvement | MAE | RMSE | 68%CDF | 95%CDF
---|---|---|---|---
KNN | WKNN | KNN | WKNN | KNN | WKNN | KNN | WKNN
0-10% | 6 | 6 | 2 | 5 | 9 | 9 | 0 | 5
10% - 30% | 9 | 10 | 5 | 6 | 7 | 5 | 9 | 3
30% - 50% | 9 | 6 | 15 | 12 | 0 | 0 | 7 | 8
>50% | 1 | 1 | 4 | 3 | 1 | 1 | 10 | 9
Total | 25 | 23 | 26 | 26 | 17 | 15 | 26 | 25
TABLE V: Comparison of the positioning error using different algorithms Building | Floor | MAE | RMSE | 68%CDF | 95%CDF
---|---|---|---|---|---
KNN | WKNN | DNL | KNN | WKNN | DNL | KNN | WKNN | DNL | KNN | WKNN | DNL
Joycity | -3 | 14.84 | 13.24 | 12.67 | 23.37 | 20.88 | 17.72 | 15.47 | 14.41 | 14.05 | 48.65 | 43.19 | 39.00
| -2 | 11.76 | 11.25 | 7.94 | 20.54 | 19.71 | 10.94 | 8.39 | 8.20 | 8.01 | 47.76 | 45.30 | 22.04
| -1 | 12.33 | 11.96 | 8.76 | 20.23 | 19.65 | 13.76 | 10.59 | 9.95 | 8.44 | 46.93 | 46.22 | 27.00
| 1 | 9.05 | 8.84 | 6.26 | 17.15 | 16.81 | 11.36 | 6.76 | 6.68 | 5.59 | 35.43 | 34.77 | 17.70
| 2 | 13.36 | 13.00 | 7.92 | 25.33 | 24.85 | 12.22 | 8.61 | 8.39 | 7.46 | 62.57 | 60.31 | 24.49
| 3 | 10.91 | 10.67 | 6.90 | 17.24 | 16.91 | 9.36 | 10.00 | 9.78 | 7.32 | 40.60 | 39.99 | 18.50
| 4 | 22.33 | 21.74 | 8.80 | 35.83 | 35.17 | 12.07 | 21.97 | 20.44 | 9.43 | 85.42 | 85.35 | 26.23
| 5 | 11.87 | 11.61 | 8.78 | 19.27 | 18.96 | 13.17 | 10.76 | 10.19 | 9.19 | 43.42 | 42.96 | 22.20
| 6 | 10.55 | 10.27 | 7.30 | 18.12 | 17.74 | 10.41 | 8.07 | 7.78 | 7.48 | 45.08 | 43.90 | 19.62
| 7 | 7.37 | 7.14 | 6.68 | 15.31 | 14.80 | 9.90 | 5.93 | 5.76 | 6.57 | 23.56 | 23.04 | 21.08
| 8 | 6.06 | 5.59 | 6.08 | 12.72 | 11.73 | 11.38 | 4.87 | 4.78 | 5.60 | 20.24 | 16.07 | 17.13
| 9 | 9.35 | 9.04 | 9.28 | 14.85 | 14.22 | 14.00 | 9.02 | 8.82 | 8.79 | 34.09 | 32.95 | 29.69
| 10 | 8.54 | 8.13 | 7.09 | 15.96 | 15.24 | 11.05 | 6.53 | 6.16 | 6.33 | 37.33 | 36.14 | 26.24
Universal Harbor | -3 | 14.86 | 14.09 | 14.84 | 25.20 | 24.08 | 22.14 | 12.70 | 12.26 | 14.87 | 59.26 | 53.66 | 49.46
-2 | 8.83 | 8.59 | 6.84 | 18.55 | 17.93 | 11.06 | 6.23 | 6.13 | 6.54 | 34.90 | 33.02 | 20.22
-1 | 14.76 | 14.22 | 7.60 | 38.86 | 37.69 | 12.65 | 6.73 | 6.61 | 7.11 | 77.68 | 75.46 | 22.59
1 | 13.65 | 13.37 | 10.29 | 29.91 | 29.33 | 17.34 | 9.37 | 9.23 | 9.24 | 56.25 | 54.77 | 32.10
2 | 12.80 | 12.37 | 9.31 | 23.49 | 22.59 | 14.78 | 10.31 | 9.95 | 9.17 | 53.98 | 52.28 | 28.85
3 | 13.26 | 12.86 | 7.88 | 27.14 | 26.41 | 14.23 | 7.54 | 7.38 | 7.22 | 69.00 | 67.91 | 22.98
4 | 8.31 | 8.00 | 6.84 | 16.74 | 16.11 | 11.42 | 6.42 | 6.28 | 6.69 | 30.84 | 27.90 | 17.60
5 | 13.47 | 12.69 | 12.10 | 27.55 | 26.53 | 18.85 | 9.60 | 8.57 | 11.98 | 65.35 | 63.82 | 44.16
Dawan Mall | -3 | 4.95 | 4.73 | 4.64 | 8.44 | 8.09 | 7.49 | 4.42 | 4.35 | 4.44 | 17.05 | 15.12 | 12.54
-2 | 7.62 | 7.56 | 7.14 | 13.17 | 13.10 | 12.65 | 7.09 | 7.03 | 6.69 | 20.87 | 20.51 | 18.48
-1 | 13.04 | 12.75 | 12.02 | 23.89 | 23.39 | 20.61 | 9.24 | 9.04 | 10.70 | 62.01 | 61.03 | 47.32
1 | 17.39 | 17.15 | 10.99 | 32.23 | 31.81 | 19.30 | 12.07 | 11.96 | 9.49 | 78.74 | 78.30 | 37.01
2 | 11.14 | 10.63 | 7.07 | 22.02 | 21.07 | 10.97 | 7.36 | 7.09 | 6.70 | 52.87 | 51.13 | 23.25

##  V Conclusions

In conclusion, we have proposed a Deep Neighborhood Learning approach to
compensate the intrinsic problem of losing relational information among FPs
and WAPs in conventional KNN or WKNN-based WiFi fingerprinting algorithms. For
a given target FP, the proposed approach constructs a heterogeneous graph
based on its local community containing the WiFi neighbor FPs and all the WAPs
that can be detected within the community. A special neural network model has
been designed to learn the topology information and the features from the
neighborhood in the graph, and project the extracted embedding to the location
of the target FP. Compared to KNN and WKNN, experiments on 3 real industrial
datasets collected from 3 shopping malls, covering 26 floors in total, have
shown that the proposed approach can better learn the neighborhood information
and reduce the positioning error (MAE and RMSE) by 10% to 50% in most of the
cases. Particularly, the DNL approach can always provide much lower RMSE and
95% percentile positioning error, being more robust to the outliers caused by
the noise from huge datasets.

Our future work will be conducted from two aspects. On one hand, we will
integrate the WiFi distance learning model proposed in our recent work to
select better WiFi neighbors; On the other hand, we will include more
information to the local community to extract even better representation of
the WiFi fingerprints, such as the measurements and calculations from the
inertial sensors and GNSS data.

## Acknowledgment

This research is from a internship project within Huawei Technologies Research
and Development (UK) Ltd Edinburgh Research Centre. We thank our colleagues
Bertrand Perrat, Ilari Vallivaara, Janis Sokolovskis and Rory Hughes for their
great work on data mining and post-processing.

## References

  * [1] Van Nee, Richard DJ. ”Multipath and multi-transmitter interference in spread spectrum communication and navigation systems.” _Doctoral dissertation_ , Technische Universiteit Delft, Delft, The Netherlands. 1996
  * [2] Liu, F., Liu, J., Yin, Y., Wang, W., Hu, D., Chen, P. and Niu, Q. ”Survey on WiFi-based indoor positioning techniques”. _IET Communications_ , vol 14, no 9: p. 1372-1383, June 2020, doi: 10.1049/iet-com.2019.1059.
  * [3] Gallo, Pierluigi, and Stefano Mangione. ”RSS-eye: Human-assisted indoor localization without radio maps.” _2015 IEEE International Conference on Communications (ICC)_. IEEE, 2015.
  * [4] Wen, Fuxi, and Chen Liang. ”An indoor AOA estimation algorithm for IEEE 802.11 ac Wi-Fi signal using single access point.” _IEEE Communications Letters_ 18.12 (2014): 2197-2200.
  * [5] Golden, Stuart A., and Steve S. Bateman. ”Sensor measurements for Wi-Fi location with emphasis on time-of-arrival ranging.” _IEEE Transactions on Mobile Computing_ 6.10 (2007): 1185-1198.
  * [6] Danjo, Azusa, Yuki Watase, and Shinsuke Hara. ”A theoretical error analysis on indoor TOA localization scheme using unmanned aerial vehicles.” _2015 IEEE 81st Vehicular Technology Conference (VTC Spring)_. IEEE, 2015.
  * [7] Nawaz, Haq, Ayhan Bozkurt, and Ibrahim Tekin. ”A novel power efficient asynchronous time difference of arrival indoor localization system using CC1101 radio transceivers.” _Microwave and Optical Technology Letters_ 59.3 (2017): 550-555.
  * [8] Hernández, Noelia, et al. ”Continuous space estimation: Increasing WiFi-based indoor localization resolution without increasing the site-survey effort.” _Sensors_ 17.1 (2017): 147.
  * [9] Ding, Genming, Jinbao Zhang, and Zhenhui Tan. ”Overview of received signal strength based fingerprinting localization in indoor wireless LAN environments.” _2013 5th IEEE International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless Communications_. IEEE, 2013.
  * [10] M. Hidayab, A. H. Ali and K. B. Abas Azmi, ”Wifi signal propagation at 2.4 GHz,” 2009 Asia Pacific Microwave Conference, 2009, pp. 528-531, doi: 10.1109/APMC.2009.5384182.
  * [11] M. M. Atia, M. Korenberg and A. Noureldin, ”A consistent zero-configuration GPS-Like indoor positioning system based on signal strength in IEEE 802.11 networks,” _Proceedings of the 2012 IEEE/ION Position, Location and Navigation Symposium_ , 2012, pp. 1068-1073, doi: 10.1109/PLANS.2012.6236849.
  * [12] X. Wang, X. Wang, S. Mao, J. Zhang, S. C. G. Periaswamy and J. Patton, ”Indoor Radio Map Construction and Localization With Deep Gaussian Processes,” in _IEEE Internet of Things Journal_ , vol. 7, no. 11, pp. 11238-11249, Nov. 2020, doi: 10.1109/JIOT.2020.2996564.
  * [13] J. Torres-Sospedra, R. Montoliu, S. Trilles, Ó. Belmonte, and J. Huerta, “Comprehensive analysis of distance and similarity measures for wi-fi fingerprinting indoor positioning systems,” _Expert Systems with Applications_ , vol. 42, no. 23, pp. 9263–9278, 2015
  * [14] C. Li, Z. Qiu, and C. Liu, “An improved weighted K-nearest neighbor algorithm for indoor positioning,” _Wireless Pers. Commun._ , vol. 96, no. 2, pp. 2239–2251, Sep. 2017.
  * [15] R. Zhou, Y. Yang, and P. Chen, “An RSS transform—Based WKNN for indoor positioning,” _Sensors_ , vol. 21, no. 17, p. 5685, Aug. 2021, doi: 10.3390/s21175685.
  * [16] Chai ML, Li CG, Huang H. A New Indoor Positioning Algorithm of Cellular and Wi-Fi Networks[J]. _Journal of Navigation_ , 2020, 73(3):1- 21
  * [17] Feng, Y., Minghua, J., Jing, L., Xiao, Q., Ming, H., Tao, P., Xinrong, H.: ”An improved indoor localization of WiFi based on support vector machines”. _International Journal of Future Generation Communication and Networking_ 7.5 (2014): 191-206.
  * [18] Zhang, W., Wang, L., Qin, Z., Zheng, X., Sun, L., Jin, N., Shu, L.: ”INBS: An Improved Naive Bayes Simple learning approach for accurate indoor localization”. In: _2014 IEEE International Conference on Communications (ICC)_ , pp. 148–153 (2014). https://doi.org/10.1109/ICC.2014.6883310
  * [19] Chen, Z., Wang, J.: ”GROF: Indoor localization using a multiplebandwidth general regression neural network and outlier filter”. Sensors 18(11), 3723 (2018). https://doi.org/10.3390/s18113723
  * [20] Shenoy, M.V., Karuppiah, A., Manjarekar, N.: ”A Lightweight ANN based Robust Localization Technique for Rapid Deployment of Autonomous Systems”. _Journal of Ambient Intelligence and Humanized Computing_. 1–16. https://doi.org/10.1007/s12652-019-01331-0 (2019)
  * [21] Zhang, M., Fan, Z., Shibasaki, R., Song, X. Domain Adversarial Graph Convolutional Network Based on RSSI and Crowdsensing for Indoor Localization. arXiv preprint arXiv:2204.05184. 2022
  * [22] Gu, Yang, Caifa Zhou, Andreas Wieser, and Zhimin Zhou. ”Trajectory estimation and crowdsourced radio map establishment from foot-mounted imus, wi-fi fingerprints, and gps positions.” _IEEE sensors journal_ 19, no. 3 (2018): 1104-1113.
  * [23] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks,” in _Proc. ICLR_ , 2019, pp. 1–17.
  * [24] F. Pedregosa et al., “Scikit-learn: Machine learning in Python,” _J. Mach. Learn. Res._ , vol. 12, pp. 2825–2830, Feb. 2011.


:

# Learning by Passing Tests, with Application to Neural Architecture Search

Xuefeng Du<EMAIL_ADDRESS>Pengtao Xie*<EMAIL_ADDRESS>
UC San Diego

###### Abstract

Learning through tests is a broadly used methodology in human learning and
shows great effectiveness in improving learning outcome: a sequence of tests
are made with increasing levels of difficulty; the learner takes these tests
to identify his/her weak points in learning and continuously addresses these
weak points to successfully pass these tests. We are interested in
investigating whether this powerful learning technique can be borrowed from
humans to improve the learning abilities of machines. We propose a novel
learning approach called learning by passing tests (LPT). In our approach, a
tester model creates increasingly more-difficult tests to evaluate a learner
model. The learner tries to continuously improve its learning ability so that
it can successfully pass however difficult tests created by the tester. We
propose a multi-level optimization framework to formulate LPT, where the
tester learns to create difficult and meaningful tests and the learner learns
to pass these tests. We develop an efficient algorithm to solve the LCT
problem. Our method is applied for neural architecture search and achieves
significant improvement over state-of-the-art baselines on CIFAR-100,
CIFAR-10, and ImageNet.

##  1 Introduction

††footnotetext: ∗Corresponding author.

In human learning, an effective and widely used methodology for improving
learning outcome is to let the learner take increasingly more-difficult tests.
To successfully pass a more challenging test, the learner needs to gain better
learning ability. By progressively passing tests that have increasing levels
of difficulty, the learner strengthens his/her learning capability gradually.

Inspired by this test-driven learning technique of humans, we are interested
in investigating whether this methodology is helpful for improving machine
learning as well. We propose a novel learning framework called learning by
passing tests (LPT). In this framework, there is a “learner” model and a
“tester” model. The tester creates a sequence of “tests” with growing levels
of difficulty. The learner tries to learn better so that it can pass these
increasingly more-challenging tests. Given a large collection of data examples
called “test bank”, the tester creates a test $T$ by selecting a subset of
examples from the test bank. The learner applies its intermediately-trained
model $M$ to make predictions on the examples in $T$. The prediction error
rate $R$ reflects how difficult this test is. If the learner can make correct
predictions on $T$, it means that $T$ is not difficult enough. The tester will
create a more challenging test $T^{\prime}$ by selecting a new set of examples
from the test bank in a way that the new error rate $R^{\prime}$ achieved by
$M$ is larger than $R$. Given this more demanding test $T^{\prime}$, the
learner re-learns its model to pass $T^{\prime}$, in a way that the newly-
learned model $M^{\prime}$ achieves a new error rate $R^{\prime\prime}$ on
$T^{\prime}$ where $R^{\prime\prime}$ is smaller than $R^{\prime}$. This
process iterates until convergence.

In our framework, both the learner and tester perform learning. The learner
learns how to best conduct a target task $J_{1}$ and the tester learns how to
create difficult and meaningful tests. To encourage a created test $T$ to be
meaningful, the tester trains a model using $T$ to perform a target task
$J_{2}$. If the model performs well on $J_{2}$, it indicates that $T$ is
meaningful. The learner has two sets of learnable parameters: neural
architecture and network weights. The tester has three learnable modules: data
encoder, test creator, and target-task executor. The learning is organized
into three stages. In the first stage, the learner trains its network weights
on the training set of task $J_{1}$ with the architecture fixed. In the second
stage, the tester trains its data encoder and target-task executor on a
created test to perform the target task $J_{2}$, with the test creator fixed.
In the third stage, the learner updates its model architecture by minimizing
the predictive loss $L$ on the test created by the tester; the tester updates
its test creator by maximizing $L$ and minimizing the loss on the validation
set of $J_{2}$. The three stages are performed jointly end-to-end in a multi-
level optimization framework, where different stages influence each other. We
apply our method for neural architecture search Zoph and Le (2017); Liu et al.
(2019); Real et al. (2019) in image classification tasks on CIFAR-100,
CIFAR-10, and ImageNet (Deng et al., 2009). Our method achieves significant
improvement over state-of-the-art baselines.

The major contributions of this paper are as follows:

  * •

Inspired by the test-driven learning technique of humans, we propose a novel
machine learning approach called learning by passing tests (LPT). In our
approach, a tester model creates increasingly more-difficult tests to evaluate
a learner model. The learner tries to continuously improve its learning
ability so that it can successfully pass however difficult tests created by
the tester.

  * •

We propose a multi-level optimization framework to formulate LPT where the
learner learns to pass tests and the tester learns to create difficult and
meaningful tests.

  * •

We develop an efficient algorithm to solve the LCT problem.

  * •

We apply our approach to neural architecture search and achieve significant
improvement on CIFAR-100, CIFAR-10, and ImageNet.

The rest of the paper is organized as follows. Section 2 reviews related
works. Section 3 and 4 present the method and experiments respectively.
Section 5 concludes the paper.

##  2 Related Works

###  2.1 Neural Architecture Search

Neural architecture search (NAS) has achieved remarkable progress recently,
which aims at searching for the optimal architecture of neural networks to
achieve the best predictive performance. In general, there are three paradigms
of methods in NAS: reinforcement learning (RL) approaches (Zoph and Le, 2017;
Pham et al., 2018; Zoph et al., 2018), evolutionary learning approaches (Liu
et al., 2018b; Real et al., 2019), and differentiable approaches (Cai et al.,
2019; Liu et al., 2019; Xie et al., 2019). In RL-based approaches, a policy is
learned to iteratively generate new architectures by maximizing a reward which
is the accuracy on the validation set. Evolutionary learning approaches
represent the architectures as individuals in a population. Individuals with
high fitness scores (validation accuracy) have the privilege to generate
offspring, which replaces individuals with low fitness scores. Differentiable
approaches adopt a network pruning strategy. On top of an over-parameterized
network, the weights of connections between nodes are learned using gradient
descent. Then weights close to zero are pruned later on. There have been many
efforts devoted to improving differentiable NAS methods. In P-DARTS (Chen et
al., 2019), the depth of searched architectures is allowed to grow
progressively during the training process. Search space approximation and
regularization approaches are developed to reduce computational overheads and
improve search stability. PC-DARTS (Xu et al., 2020) reduces the redundancy in
exploring the search space by sampling a small portion of a super network.
Operation search is performed in a subset of channels with the held-out part
bypassed in a shortcut. Our proposed LCT framework can be applied to any
differentiable NAS methods.

###  2.2 Adversarial Learning

Our formulation involves a min-max optimization problem, which is analogous to
that in adversarial learning. Adversarial learning (Goodfellow et al., 2014a)
has been widely applied to 1) data generation (Goodfellow et al., 2014a; Yu et
al., 2017) where a discriminator tries to distinguish between generated images
and real images and a generator is trained to generate realistic data by
making such a discrimination difficult to achieve; 2) domain adaptation (Ganin
and Lempitsky, 2015) where a discriminator tries to differentiate between
source images and target images while the feature learner learns
representations which make such a discrimination unachievable; 3) adversarial
attack and defence (Goodfellow et al., 2014b) where an attacker adds small
perturbations to the input data to alter the prediction outcome and the
defender trains the model in a way that the prediction outcome remains the
same given perturbed inputs. Different from these existing works, in our work,
a tester aims to create harder tests to “fail” the learner while the learner
learns to “pass” however hard tests created by the tester. Shu et al. (2020)
proposed to use an adversarial examiner to identify the weakness of a trained
model. Our work differs from this one in that we progressively re-train a
learner model based on how it performs on the tests dynamically created by a
tester model while the learner model in (Shu et al., 2020) is fixed and not
affected by the examination results.

##  3 Methods

In this section, we propose a framework to perform learning by passing tests
(LPT) and develop an optimization algorithm for solving the LPT problem.

###  3.1 Learning by Passing Tests

In our framework, there is a learner model and a tester model, where the
learner studies how to perform a target task $J_{1}$ such as classification,
regression, etc. The eventual goal is to make the learner achieve a better
learning outcome with the help of the tester. There is a collection of data
examples called “test bank”. The tester creates a test by selecting a subset
of examples from the test bank. Given a test $T$, the learner applies its
intermediately-trained model $M$ to make predictions on $T$ and measures the
prediction error rate $R$. From the perspective of the tester, $R$ indicates
how difficult the test $T$ is. If $R$ is small, it means that the learner can
easily pass this test. Under such circumstances, the tester will create a more
difficult test $T^{\prime}$ which renders the new error rate $R^{\prime}$
achieved by $M$ on $T^{\prime}$ is larger than $R$. From the learner’s
perspective, $R^{\prime}$ indicates how well the learner performs on the test.
Given this more difficult test $T^{\prime}$, the learner refines its model to
pass this new test. It aims to learn a new model $M^{\prime}$ in a way that
the error rate $R^{\prime\prime}$ achieved by $M^{\prime}$ on $T^{\prime}$ is
smaller than $R^{\prime}$. This process iterates until an equilibrium is
reached. In addition to being difficult, the created test should be meaningful
as well. It is possible that the test bank contains poor-quality examples
where the class labels may be incorrect or the input data instances are
outliers. Using an unmeaningful test containing poor-quality examples to guide
the learning of the learner may render the learner to overfit these bad-
quality examples and generalize poorly on unseen data. To address this
problem, we encourage the tester to generate meaningful tests by leveraging
the generated tests to perform a target task $J_{2}$ (e.g., classification).
Specifically, the tester uses examples in the test to train a model for
performing $J_{2}$. If the performance (e.g., accuracy) $P$ achieved by this
model in conducting $J_{2}$ is high, the test is considered to be meaningful.
The tester aims to create a test that can yield a high $P$.

Figure 1: Illustration of learning by passing tests. The solid arrows denote the process of making predictions and calculating losses. The dotted arrows denote the process of updating learnable parameters by minimizing corresponding losses. Notation | Meaning
---|---
$A$ | Architecture of the learner
$W$ | Network weights of the learner
$E$ | Data encoder of the tester
$C$ | Test creator of the tester
$X$ | Target-task executor of the tester
$D_{ln}^{(\textrm{tr})}$ | Training data of the learner
$D_{tt}^{(\textrm{tr})}$ | Training data of the tester
$D_{tt}^{(\textrm{val})}$ | Validation data of the tester
$D_{b}$ | Test bank
Table 1: Notations in Learning by Passing Tests

In our framework, both the learner and the tester performs learning. The
learner studies how to best fulfill the target task $J_{1}$. The tester
studies how to create tests that are difficult and meaningful. In the learner’
model, there are two sets of learnable parameters: model architecture and
network weights. The architecture and weights are both used to make
predictions in $J_{1}$. The tester’s model performs two tasks simultaneously:
creating tests and performing target-task $J_{1}$. The model has three
learnable modules: data encoder, test creator, and target-task executor, where
the test creator performs the task of generating tests and the target-task
executor conducts $J_{1}$. The test creator and target-task executor share the
same data encoder. The data encoder takes a data example $d$ as input and
generates a latent representation for this example. Then the representation is
fed into the test creator which determines whether $d$ should be selected into
the test. The representation is also fed into the target-task executor which
performs prediction on $d$ during performing the target task $J_{2}$.

In our framework, the learning of the learner and the tester is organized into
three stages. In the first stage, the learner learns its network weights $W$
by minimizing the training loss $L(A,W,D_{ln}^{(\mathrm{tr})})$ defined on the
training data $D_{ln}^{(\mathrm{tr})}$ in the task $J_{1}$. The architecture
$A$ is used to define the training loss, but it is not learned in this stage.
If $A$ is learned by minimizing this training loss, a trivial solution will be
yielded where $A$ is very large and complex that it can perfectly overfit the
training data but will generalize poorly on unseen data. Let $W^{*}(A)$ denote
the optimally learned $W$ in this stage. Note that $W^{*}$ is a function of
$A$ because $W^{*}$ is a function of the training loss and the training loss
is a function of $A$. In the second stage, the tester learns its data encoder
$E$ and target-task executor $X$ by minimizing the training loss
$L(E,X,D_{tt}^{(\mathrm{tr})})+\gamma L(E,X,\sigma(C,E,D_{b}))$ in the task
$J_{2}$. The training loss consists of two parts. The first part
$L(E,X,D_{tt}^{(\mathrm{tr})})$ is defined on the training dataset
$D_{tt}^{\textrm{tr}}$ in $J_{2}$. The second part $L(E,X,\sigma(C,E,D_{b}))$
is defined on the test $\sigma(C,E,D_{b})$ created by the test creator. For
each example $d$ in the test bank $D_{b}$, it is first fed into the encoder
$E$, then the creator $C$, which outputs a binary value indicating whether $d$
should be selected into the test. $\sigma(C,E,D_{b})$ is the collection of
examples whose binary value is equal to 1. $\gamma$ is a tradeoff parameter
between these two parts of losses. The creator $C$ is used to define the
second-part loss, but it is not learned in this stage. Otherwise, a trivial
solution will be yielded where $C$ always sets the binary value to 0 for each
test-bank example so that the second-part loss becomes 0. Let $E^{*}(C)$ and
$X^{*}(C)$ denote the optimally trained $E$ and $X$ in this stage. Note that
they are both functions of $C$ since they are functions of the training loss
and the training loss is a function of $C$. In the third stage, the learner
learns its architecture by trying to pass the test $\sigma(C,E^{*}(C),D_{b})$
created by the tester. Specifically, the learner aims to minimizes the
predictive loss of its model on the test:

$L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))=\sum_{d\in\sigma(C,E^{*}(C),D_{b})}\ell(A,W^{*}(A),d)$
(1)

where $d$ is an example in the test and $\ell(A,W^{*}(A),d)$ is the loss
defined on this example. A smaller $L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))$
indicates that the learner performs well on this test.

Meanwhile, the tester learns its test creator $C$ in a way that $C$ can create
a test with more difficulty and meaningfulness. Difficulty is measured by the
learner’s predictive loss $L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))$ on the
test. Given a model $(A,W^{*}(A))$ of the learner and two tests of the same
size (same number of examples): $\sigma(C_{1},E^{*}(C_{1}),D_{b})$ created by
$C_{1}$ and $\sigma(C_{2},E^{*}(C_{2}),D_{b})$ created by $C_{2}$, if
$L(A,W^{*}(A),\sigma(C_{1},E^{*}(C_{1}),D_{b}))>L(A,W^{*}(A),\sigma(C_{2},E^{*}(C_{2}),D_{b}))$,
it means that $\sigma(C_{1},E^{*}(C_{1}),D_{b})$ is more challenging to pass
than $\sigma(C_{2},E^{*}(C_{2}),D_{b})$. Therefore, the tester can learn to
create a more challenging test by maximizing
$L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))$. A trivial solution of increasing
$L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))$ is to enlarge the size of the test.
But a larger size does not imply more difficulty. To discourage this
degenerated solution from happening, we normalize the loss using the size of
the test:

$\frac{1}{\left|\sigma\left(C,E^{*}(C),D_{b}\right)\right|}L\left(A,W^{*}\left(A\right),\sigma\left(C,E^{*}(C),D_{b}\right)\right)$
(2)

where $|\sigma(C,E^{*}(C),D_{b})|$ is the cardinality of the set
$\sigma(C,E^{*}(C),D_{b})$. To measure the meaningfulness of a test, we check
how well the optimally-trained task executor $E^{*}(C)$ and data encoder
$X^{*}(C)$ of the tester perform on the validation data
$D_{tt}^{\textrm{(val)}}$ in the target task $J_{2}$, and the performance is
measured by the validation loss:
$L(E^{*}(C),X^{*}(C),D_{tt}^{(\mathrm{val})})$. $E^{*}(C)$ and $X^{*}(C)$ are
trained using the test generated by $C$ in the second stage. If the validation
loss is small, it means that the created test is helpful in training the task
executor and therefore is considered as being meaningful. To create a
meaningful test, the tester learns $C$ by minimizing
$L(E^{*}(C),X^{*}(C),D_{tt}^{(\mathrm{val})})$. In sum, $C$ is learned by
maximizing
$L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))/|\sigma(C,E^{*}(C),D_{b})|-\lambda
L(E^{*}(C),X^{*}(C),D_{tt}^{(\mathrm{val})})$, where $\lambda$ is a tradeoff
parameter between these two objectives.

The three stages are mutually dependent: $W^{*}(A)$ learned in the first stage
and $E^{*}(C)$ and $X^{*}(C)$ learned in the second stage are used to define
the objective function in the third stage; the updated $C$ and $A$ in the
third stage in turn change the objective functions in the first and second
stage, which subsequently render $W^{*}(A)$, $E^{*}(C)$, and $X^{*}(C)$ to be
changed. Putting these pieces together, we formulate LPT as the following
multi-level optimization problem.

$\begin{array}[]{l}\max_{C}\min_{A}\;\;\frac{1}{\left|\sigma\left(C,E^{*}(C),D_{b}\right)\right|}L\left(A,W^{*}\left(A\right),\sigma\left(C,E^{*}(C),D_{b}\right)\right)-\lambda
L\left(E^{*}(C),X^{*}(C),D_{tt}^{(\mathrm{val})}\right)\textrm{(III)}\\\
s.t.\;\;E^{*}(C),X^{*}(C)=\min_{E,X}\;\;L\left(E,X,D_{tt}^{(\mathrm{tr})}\right)+\gamma
L\left(E,X,\sigma\left(C,E,D_{b}\right)\right)\textrm{(Stage II)}\\\
\quad\;\;\;W^{*}\left(A\right)=\min_{W}\;\;L\left(A,W,D_{ln}^{(\mathrm{tr})}\right)\textrm{(Stage
I)}\end{array}$ (3)

This formulation nests three optimization problems. On the constraints of the
outer optimization problem are two inner optimization problems corresponding
to the first and second learning stage respectively. The objective function of
the outer optimization problem corresponds to the third learning stage.

As of now, the test $\sigma(C,E,D_{b})$ is represented as a subset, which is
highly discrete and therefore difficult for optimization. To address this
problem, we perform a continuous relaxation of $\sigma(C,E,D_{b})$:

$\sigma(C,E,D_{b})=\\{(d,f(d,C,E))|d\in D_{b}\\}$ (4)

where for each example $d$ in the test bank, the original binary value
indicating whether $d$ should be selected is now relaxed to a continuous
probability $f(d,C,E)$ representing how likely $d$ should be selected. Under
this relaxation, $L(E,X,\sigma(C,E,D_{b}))$ can be computed as follows:

$L(E,X,\sigma(C,E,D_{b}))=\sum_{d\in D_{b}}f(d,C,E)\ell(E,X,d)$ (5)

where we calculate the loss $\ell(E,X,d)$ on each test-bank example and weigh
this loss using $f(d,C,E))$. If $f(d,C,E))$ is small, it means that $d$ is
less likely to be selected into the test and its corresponding loss should be
down-weighted. Similarly, $L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))$ is
calculated as $\sum_{d\in D_{b}}f(d,C,E^{*}(C))\ell(A,W^{*}(A),d)$. And
$|\sigma(C,E^{*}(C),D_{b})|$ can be calculated as

$|\sigma(C,E^{*}(C),D_{b})|=\sum_{d\in D_{b}}f(d,C,E^{*}(C))$ (6)

Similar to (Liu et al., 2019), we represent the architecture $A$ of the
learner in a differentiable way. The search space of $A$ is composed of a
large number of building blocks. The output of each block is associated with a
variable $a$ indicating how important this block is. After learning, blocks
whose $a$ is among the largest are retained to form the final architecture. In
this end, architecture search amounts to optimizing the set of architecture
variables $A=\\{a\\}$.

###  3.2 Optimization Algorithm

In this section, we derive an optimization algorithm to solve the LPT problem
defined in Eq.(3). Inspired by (Liu et al., 2019), we approximate $E^{*}(C)$
and $X^{*}(C)$ using one-step gradient descent update of $E$ and $X$ with
respect to $L(E,X,D_{tt}^{(\mathrm{tr})})+\gamma L(E,X,\sigma(C,E,D_{b}))$ and
approximate $W^{*}(A)$ using one-step gradient descent update of $W$ with
respect to $L(A,W,D_{ln}^{(\mathrm{tr})})$. Then we plug in these
approximations into

$L(A,W^{*}(A),\sigma(C,E^{*}(C),D_{b}))/|\sigma(C,E^{*}(C),D_{b})|-\lambda
L(E^{*}(C),X^{*}(C),D_{tt}^{(\mathrm{val})}),$ (7)

and perform gradient-descent update of $C$ and $A$ with respect to this
approximated objective. In the sequel, we use $\nabla^{2}_{Y,X}f(X,Y)$ to
denote $\frac{\partial f(X,Y)}{\partial X\partial Y}$.

Approximating $W^{*}(A)$ using
$W^{\prime}=W-\xi_{ln}\nabla_{W}L(A,W,D_{ln}^{(\mathrm{tr})})$ where
$\xi_{ln}$ is a learning rate and simplifying the notation of
$\sigma(C,E^{*}(C),D_{b})$ as $\sigma$, we can calculate the approximated
gradient of $L\left(A,W^{*}\left(A\right),\sigma\right)$ w.r.t $A$ as:

$\begin{array}[]{l}\nabla_{A}L\left(A,W^{*}\left(A\right),\sigma\right)\approx\\\
\nabla_{A}L\left(A,W-\xi_{ln}\nabla_{W}L\left(A,W,D_{ln}^{(\mathrm{tr})}\right),\sigma\right)=\\\
\nabla_{A}L\left(A,W^{\prime},\sigma\right)-\xi_{ln}\nabla_{A,W}^{2}L\left(A,W,D_{ln}^{(\mathrm{tr})}\right)\nabla_{W^{\prime}}L\left(A,W^{\prime},\sigma\right),\end{array}$
(8)

The second term in the third line involves expensive matrix-vector product,
whose computational complexity can be reduced by a finite difference
approximation:

$\begin{array}[]{ll}\nabla_{A,W}^{2}L\left(A,W,D_{ln}^{(\mathrm{tr})}\right)\nabla_{W^{\prime}}L\left(A,W^{\prime},\sigma\right)\approx\frac{1}{2\alpha_{ln}}\left(\nabla_{A}L\left(A,W^{+},D_{ln}^{(\mathrm{tr})}\right)-\nabla_{A}L\left(A,W^{-},D_{ln}^{(\mathrm{tr})}\right)\right),\end{array}$
(9)

where
$W^{\pm}=W\pm\alpha_{ln}\nabla_{W^{\prime}}L\left(A,W^{\prime},\sigma\right)$
and $\alpha_{ln}$ is a small scalar that equals
$0.01/\left\|\nabla_{W^{\prime}}L\left(A,W^{\prime},\sigma\right))\right\|_{2}$.
We approximate $E^{*}(C)$ and $X^{*}(C)$ using the following one-step gradient
descent update of $E$ and $C$ respectively:

$\begin{array}[]{l}E^{\prime}=E-\xi_{E}\nabla_{E}[L(E,X,D_{tt}^{(\mathrm{tr})})+\gamma
L(E,X,\sigma(C,E,D_{b}))]\\\
X^{\prime}=X-\xi_{X}\nabla_{X}[L(E,X,D_{tt}^{(\mathrm{tr})})+\gamma
L(E,X,\sigma(C,E,D_{b}))]\end{array}$ (10)

where $\xi_{E}$ and $\xi_{X}$ are learning rates. Plugging in these
approximations into the objective function in Eq.(7), we can learn $C$ by
maximizing the following objective using gradient methods:

$L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))/|\sigma(C,E^{\prime},D_{b})|-\lambda
L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})$ (11)

The derivative of the second term in this objective with respect to $C$ can be
calculated as:

$\begin{array}[]{l}\nabla_{C}L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})=\frac{\partial
E^{\prime}}{\partial
C}\nabla_{E^{\prime}}L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})+\frac{\partial
X^{\prime}}{\partial
C}\nabla_{X^{\prime}}L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})\\\
\end{array}$ (12)

where

$\begin{array}[]{l}\frac{\partial E^{\prime}}{\partial
C}=-\xi_{E}\gamma\nabla^{2}_{C,E}L(E,X,\sigma(C,E,D_{b}))\\\ \frac{\partial
X^{\prime}}{\partial
C}=-\xi_{X}\gamma\nabla^{2}_{C,X}L(E,X,\sigma(C,E,D_{b}))\\\ \end{array}$ (13)

Similar to Eq.(9), using finite difference approximation to calculate
$\nabla^{2}_{C,E}L(E,X,\sigma(C,E,D_{b}))$
$\nabla_{E^{\prime}}L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})$ and
$\nabla^{2}_{C,X}L(E,X,\sigma(C,E,D_{b}))\nabla_{X^{\prime}}L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})$,
we have:

$\begin{array}[]{l}\nabla_{C}L(E^{\prime},X^{\prime},D_{tt}^{(\mathrm{val})})=\\\
-\gamma\xi_{E}\frac{\nabla_{C}L(E^{+},X,\sigma(C,E^{+},D_{b}))-\nabla_{C}L(E^{-},X,\sigma(C,E^{-},D_{b}))}{2\alpha_{E}}-\gamma\xi_{X}\frac{\nabla_{C}L(E,X^{+},\sigma(C,E,D_{b}))-\nabla_{C}L(E,X^{-},\sigma(C,E,D_{b}))}{2\alpha_{X}}\end{array}$
(14)

where
$E^{\pm}=E\pm\alpha_{E}\nabla_{E^{\prime}}L(E^{\prime},X^{\prime},D_{tt}^{\mathrm{(val)}})$
and
$X^{\pm}=X\pm\alpha_{X}\nabla_{X^{\prime}}L(E^{\prime},X^{\prime},D_{tt}^{\mathrm{(val)}})$.
For the first term
$L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))/|\sigma(C,E^{\prime},D_{b})|$ in
the objective, we can use chain rule to calculate its derivative w.r.t $C$,
which involves calculating the derivative of
$L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))$ and
$|\sigma(C,E^{\prime},D_{b})|$ w.r.t to $C$. The derivative of
$L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))$ w.r.t $C$ can be calculated as:

$\begin{array}[]{l}\nabla_{C}L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))=\frac{\partial
E^{\prime}}{\partial
C}\nabla_{E^{\prime}}L(A,W^{\prime},\sigma(C,E^{\prime},D_{b})),\end{array}$
(15)

where $\frac{\partial E^{\prime}}{\partial C}$ is given in Eq.(13) and
$\nabla^{2}_{C,E}L(E,X,\sigma(C,E,D_{b}))$
$\times\nabla_{E^{\prime}}L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))$ can be
approximated with
$\frac{1}{2\alpha_{E}}(\nabla_{C}L(E^{+},X,\sigma(C,E^{+},D_{b}))-\nabla_{C}L(E^{-},X,\sigma(C,E^{-},D_{b})))$,
where $E^{\pm}$ is
$E\pm\alpha_{E}\nabla_{E^{\prime}}L(A,W^{\prime},\sigma(C,E^{\prime},D_{b}))$.
The derivative of $|\sigma(C,E^{\prime},D_{b})|=\sum_{d\in
D_{b}}f(d,C,E^{\prime})$ w.r.t $C$ can be calculated as

$\sum_{d\in D_{b}}\nabla_{C}f(d,C,E^{\prime})+\frac{\partial
E^{\prime}}{\partial C}\nabla_{E^{\prime}}f(d,C,E^{\prime})$ (16)

where $\frac{\partial E^{\prime}}{\partial C}$ is given in Eq.(13). The
algorithm for solving LPT is summarized in Algorithm 1.

while  _not converged_ do

1\. Update the architecture of the learner by descending the gradient
calculated in Eq.(8)
2\. Update the test creator of the tester by ascending the gradient calculated
in Eq.(12-16)
3\. Update the data encoder and target-task executor of the tester using
Eq.(10)
4\. Update the weights of the learner by descending
$\nabla_{W}L(A,W,D_{ln}^{(\mathrm{tr})})$

end while

Algorithm 1 Learning by passing tests

##  4 Experiments

We apply LPT for neural architecture search in image classification tasks.
Following (Liu et al., 2019), we first perform architecture search which finds
out an optimal cell, then perform architecture evaluation which composes
multiple copies of the searched cell into a large network, trains it from
scratch, and evaluates the trained model on the test set. We let the target
task of the learner and that of the tester be the same.

###  4.1 Datasets

We used three datasets in the experiments: CIFAR-10, CIFAR-100, and ImageNet
(Deng et al., 2009). The CIFAR-10 dataset contains 50K training images and 10K
testing images, from 10 classes (the number of images in each class is equal).
Following (Liu et al., 2019), we split the original 50K training set into a
new 25K training set and a 25K validation set. In the sequel, when we mention
“training set”, it always refers to the new 25K training set. During
architecture search, the training set is used as the training data
$D_{ln}^{(\textrm{tr})}$ of the learner and the training data
$D_{tt}^{(\textrm{tr})}$ of the tester. The validation set is used as the test
bank $D_{b}$ and the validation data $D_{tt}^{(\textrm{val})}$ of the tester.
During architecture evaluation, the combination of the training data and
validation data is used to train the large network stacking multiple copies of
the searched cell. The CIFAR-100 dataset contains 50K training images and 10K
testing images, from 100 classes (the number of images in each class is
equal). Similar to CIFAR-100, the 50K training images are split into a 25K
training set and 25K validation set. The usage of the new training set and
validation set is the same as that for CIFAR-10. The ImageNet dataset contains
a training set of 1.2M images and a validation set of 50K images, from 1000
object classes. The validation set is used as a test set for architecture
evaluation. Following (Liu et al., 2019), we evaluate the architectures
searched using CIFAR-10 and CIFAR-100 on ImageNet: given a cell searched using
CIFAR-10 and CIFAR-100, multiple copies of it compose a large network, which
is then trained on the 1.2M training data of ImageNet and evaluated on the 50K
test data.

###  4.2 Experimental Settings

Our framework is a general one that can be used together with any
differentiable search method. Specifically, we apply our framework to the
following NAS methods: 1) DARTS (Liu et al., 2019), 2) P-DARTS (Chen et al.,
2019), 3) DARTS+ (Liang et al., 2019b), 4) DARTS- (Chu et al., 2020a). The
search space in these methods are similar. The candidate operations include:
$3\times 3$ and $5\times 5$ separable convolutions, $3\times 3$ and $5\times
5$ dilated separable convolutions, $3\times 3$ max pooling, $3\times 3$
average pooling, identity, and zero. In LPT, the network of the learner is a
stack of multiple cells, each consisting of 7 nodes. For the data encoder of
the tester, we tried ResNet-18 and ResNet-50 (He et al., 2016b). For the test
creator and target-task executor, they are set to one feed-forward layer.
$\lambda$ and $\gamma$ are both set to 1.

For CIFAR-10 and CIFAR-100, during architecture search, the learner’s network
is a stack of 8 cells, with the initial channel number set to 16. The search
is performed for 50 epochs, with a batch size of 64. The hyperparameters for
the learner’s architecture and weights are set in the same way as DARTS,
P-DARTS, DARTS+, and DARTS-. The data encoder and target-task executor of the
tester are optimized using SGD with a momentum of 0.9 and a weight decay of
3e-4. The initial learning rate is set to 0.025 with a cosine decay scheduler.
The test creator is optimized with the Adam (Kingma and Ba, 2014) optimizer
with a learning rate of 3e-4 and a weight decay of 1e-3. During architecture
evaluation, 20 copies of the searched cell are stacked to form the learner’s
network, with the initial channel number set to 36. The network is trained for
600 epochs with a batch size of 96 (for both CIFAR-10 and CIFAR-100). The
experiments are performed on a single Tesla v100. For ImageNet, following (Liu
et al., 2019), we take the architecture searched on CIFAR-10 and evaluate it
on ImageNet. We stack 14 cells (searched on CIFAR-10) to form a large network
and set the initial channel number as 48. The network is trained for 250
epochs with a batch size of 1024 on 8 Tesla v100s. Each experiment on LPT is
repeated for ten times with the random seed to be from 1 to 10. We report the
mean and standard deviation of results obtained from the 10 runs.

###  4.3 Results

Method | Error(%) | Param(M) | Cost
---|---|---|---
*ResNet (He et al., 2016a) | 22.10 | 1.7 | -
DenseNet (Huang et al., 2017) | 17.18 | 25.6 | -
*PNAS (Liu et al., 2018a) | 19.53 | 3.2 | 150
ENAS (Pham et al., 2018) | 19.43 | 4.6 | 0.5
AmoebaNet (Real et al., 2019) | 18.93 | 3.1 | 3150
*GDAS (Dong and Yang, 2019) | 18.38 | 3.4 | 0.2
R-DARTS (Zela et al., 2020) | 18.01$\pm$0.26 | - | 1.6
DropNAS (Hong et al., 2020) | 16.39 | 4.4 | 0.7
†DARTS-1st (Liu et al., 2019) | 20.52$\pm$0.31 | 1.8 | 0.4
LPT-R18-DARTS-1st (ours) | 19.11$\pm$0.11 | 2.1 | 0.6
*DARTS-2nd (Liu et al., 2019) | 20.58$\pm$0.44 | 1.8 | 1.5
LPT-R18-DARTS-2nd (ours) | 19.47$\pm$0.20 | 2.1 | 1.8
LPT-R50-DARTS-2nd (ours) | 18.40$\pm$0.16 | 2.5 | 2.0
*DARTS- (Chu et al., 2020a) | 17.51$\pm$0.25 | 3.3 | 0.4
†DARTS- (Chu et al., 2020a) | 18.97$\pm$0.16 | 3.1 | 0.4
LPT-R18-DARTS- (ours) | 18.28$\pm$0.14 | 3.4 | 0.6
ΔDARTS+ (Liang et al., 2019a) | 17.11$\pm$0.43 | 3.8 | 0.2
LPT-R18-DARTS+ (ours) | 16.58$\pm$0.19 | 3.7 | 0.3
*P-DARTS (Chen et al., 2019) | 17.49 | 3.6 | 0.3
LPT-R18-P-DARTS (ours) | 16.28$\pm$0.10 | 3.8 | 0.5
Table 2: Results on CIFAR-100, including classification error (%) on the test set, number of parameters (millions) in the searched architecture, and search cost (GPU days). LPT-R18-DARTS-1st denotes that our method LPT is applied to the search space of DARTS. Similar meanings hold for other notations in such a format. R18 and R50 denote that the data encoder of the tester in LPT is set to ResNet-18 and ResNet-50 respectively. DARTS-1st and DARTS-2nd denotes that first order and second order approximation is used in DARTS. * means the results are taken from DARTS- (Chu et al., 2020a). ${\dagger}$ means we re-ran this method for 10 times. $\Delta$ means the algorithm ran for 600 epochs instead of 2000 epochs in the architecture evaluation stage, to ensure a fair comparison with other methods (where the epoch number is 600). The search cost is measured by GPU days on a Tesla v100.  Method | Error(%) | Param(M) | Cost
---|---|---|---
*DenseNet (Huang et al., 2017) | 3.46 | 25.6 | -
*HierEvol (Liu et al., 2018b) | 3.75$\pm$0.12 | 15.7 | 300
NAONet-WS (Luo et al., 2018) | 3.53 | 3.1 | 0.4
PNAS (Liu et al., 2018a) | 3.41$\pm$0.09 | 3.2 | 225
ENAS (Pham et al., 2018) | 2.89 | 4.6 | 0.5
NASNet-A (Zoph et al., 2018) | 2.65 | 3.3 | 1800
AmoebaNet-B (Real et al., 2019) | 2.55$\pm$0.05 | 2.8 | 3150
*R-DARTS (Zela et al., 2020) | 2.95$\pm$0.21 | - | 1.6
GDAS (Dong and Yang, 2019) | 2.93 | 3.4 | 0.2
SNAS (Xie et al., 2019) | 2.85 | 2.8 | 1.5
BayesNAS (Zhou et al., 2019) | 2.81$\pm$0.04 | 3.4 | 0.2
MergeNAS (Wang et al., 2020) | 2.73$\pm$0.02 | 2.9 | 0.2
NoisyDARTS (Chu et al., 2020b) | 2.70$\pm$0.23 | 3.3 | 0.4
ASAP (Noy et al., 2020) | 2.68$\pm$0.11 | 2.5 | 0.2
SDARTS (Chen and Hsieh, 2020) | 2.61$\pm$0.02 | 3.3 | 1.3
DropNAS (Hong et al., 2020) | 2.58$\pm$0.14 | 4.1 | 0.6
PC-DARTS (Xu et al., 2020) | 2.57$\pm$0.07 | 3.6 | 0.1
FairDARTS (Chu et al., 2019) | 2.54 | 3.3 | 0.4
DrNAS (Chen et al., 2020) | 2.54$\pm$0.03 | 4.0 | 0.4
P-DARTS (Chen et al., 2019) | 2.50 | 3.4 | 0.3
*DARTS-1st (Liu et al., 2019) | 3.00$\pm$0.14 | 3.3 | 0.4
LPT-R18-DARTS-1st (ours) | 2.85$\pm$0.09 | 2.7 | 0.6
*DARTS-2nd (Liu et al., 2019) | 2.76$\pm$0.09 | 3.3 | 1.5
LPT-R18-DARTS-2nd (ours) | 2.72$\pm$0.07 | 3.4 | 1.8
LPT-R50-DARTS-2nd (ours) | 2.68$\pm$0.02 | 3.4 | 2.0
*DARTS- (Chu et al., 2020a) | 2.59$\pm$0.08 | 3.5 | 0.4
†DARTS- (Chu et al., 2020a) | 2.97$\pm$0.04 | 3.3 | 0.4
LPT-R18-DARTS- (ours) | 2.74$\pm$0.07 | 3.4 | 0.6
ΔDARTS+ (Liang et al., 2019a) | 2.83$\pm$0.05 | 3.7 | 0.4
LPT-R18-DARTS+ (ours) | 2.69$\pm$0.05 | 3.6 | 0.5
Table 3:  Results on CIFAR-10. * means the results are taken from DARTS- (Chu et al., 2020a), NoisyDARTS (Chu et al., 2020b), and DrNAS (Chen et al., 2020). The rest notations are the same as those in Table 2.  Method | Top-1 | Top-5 | Param | Cost
---|---|---|---|---
Error (%) | Error (%) | (M) | (GPU days)
*Inception-v1 (Szegedy et al., 2015) | 30.2 | 10.1 | 6.6 | -
MobileNet (Howard et al., 2017) | 29.4 | 10.5 | 4.2 | -
ShuffleNet 2$\times$ (v1) (Zhang et al., 2018) | 26.4 | 10.2 | 5.4 | -
ShuffleNet 2$\times$ (v2) (Ma et al., 2018) | 25.1 | 7.6 | 7.4 | -
*NASNet-A (Zoph et al., 2018) | 26.0 | 8.4 | 5.3 | 1800
PNAS (Liu et al., 2018a) | 25.8 | 8.1 | 5.1 | 225
MnasNet-92 (Tan et al., 2019) | 25.2 | 8.0 | 4.4 | 1667
AmoebaNet-C (Real et al., 2019) | 24.3 | 7.6 | 6.4 | 3150
*SNAS (Xie et al., 2019) | 27.3 | 9.2 | 4.3 | 1.5
BayesNAS (Zhou et al., 2019) | 26.5 | 8.9 | 3.9 | 0.2
PARSEC (Casale et al., 2019) | 26.0 | 8.4 | 5.6 | 1.0
GDAS (Dong and Yang, 2019) | 26.0 | 8.5 | 5.3 | 0.2
DSNAS (Hu et al., 2020) | 25.7 | 8.1 | - | -
SDARTS-ADV (Chen and Hsieh, 2020) | 25.2 | 7.8 | 5.4 | 1.3
PC-DARTS (Xu et al., 2020) | 25.1 | 7.8 | 5.3 | 0.1
ProxylessNAS (Cai et al., 2019) | 24.9 | 7.5 | 7.1 | 8.3
FairDARTS (Chu et al., 2019) | 24.9 | 7.5 | 4.8 | 0.4
P-DARTS (CIFAR-100) (Chen et al., 2019) | 24.7 | 7.5 | 5.1 | 0.3
P-DARTS (CIFAR-10) (Chen et al., 2019) | 24.4 | 7.4 | 4.9 | 0.3
FairDARTS (Chu et al., 2019) | 24.4 | 7.4 | 4.3 | 3.0
DrNAS (Chen et al., 2020) | 24.2 | 7.3 | 5.2 | 3.9
PC-DARTS (Xu et al., 2020) | 24.2 | 7.3 | 5.3 | 3.8
DARTS+ (Liang et al., 2019a) | 23.9 | 7.4 | 5.1 | 6.8
DARTS- (Chu et al., 2020a) | 23.8 | 7.0 | 4.9 | 4.5
DARTS+ (CIFAR-100) (Liang et al., 2019a) | 23.7 | 7.2 | 5.1 | 0.2
*DARTS-2nd-CIFAR-10 (Liu et al., 2019) | 26.7 | 8.7 | 4.7 | 4.0
LPT-R18-DARTS-2nd-CIFAR-10 (ours) | 25.3 | 7.9 | 4.7 | 4.0
Table 4: Results on ImageNet, including top-1 and top-5 classification errors
on the test set, number of weight parameters (millions), and search cost (GPU
days). * means the results are taken from DARTS- (Chu et al., 2020a) and DrNAS
(Chen et al., 2020). The rest notations are the same as those in Table 2. The
first row block shows networks designed by humans manually. The second row
block shows non-gradient based search methods. The third block shows gradient-
based methods.

Table 2 shows the classification error (%), number of weight parameters
(millions), and search cost (GPU days) of different NAS methods on CIFAR-100.
From this table, we make the following observations. First, when our method
LPT is applied to different NAS baselines including DARTS-1st (first order
approximation), DARTS-2nd (second order approximation), DARTS-, DARTS+, and
P-DARTS, the classification errors of these baselines can be significantly
reduced. For example, applying our method to P-DARTS, the error reduces from
17.49% to 16.28%. Applying our method to DARTS-2nd, the error reduces from
20.58% to 18.40%. This demonstrates the effectiveness of our method in
searching for a better architecture. In our method, the learner continuously
improves its architecture by passing the tests created by the tester with
increasing levels of difficulty. These tests can help the learner to identify
the weakness of its architecture and provide guidance on how to improve it.
Our method creates a new test on the fly based on how the learner performs in
the previous round. From the test bank, the tester selects a subset of
difficult examples to evaluate the learner. This new test poses a greater
challenge to the learner and encourages the learner to improve its
architecture so that it can overcome the new challenge. In contrast, in
baseline NAS approaches, a single fixed validation set is used to evaluate the
learner. The learner can achieve a good performance via “cheating”: focusing
on performing well on the majority of easy examples and ignoring the minority
of difficult examples. As a result, the learner’s architecture does not have
the ability to deal with challenging cases in the unseen data. Second,
LPT-R50-DARTS-2nd outperforms LPT-R18-DARTS-2nd, where the former uses
ResNet-50 as the data encoder in the tester while the latter uses ResNet-18.
ResNet-50 has a better ability of learning representations than ResNet-18
since it is “deeper”: 50 layers versus 18 layers. This shows that a “stronger”
tester can help the learner to learn better. With a more powerful data
encoder, the tester can better understand examples in the test bank and can
make better decisions in creating difficult and meaningful tests. Tests with
better quality can more effectively evaluate the learner and promote its
learning capability. Third, our method LPT-R18-P-DARTS achieves the best
performance among all methods, which further demonstrates the effectiveness of
LPT in driving the frontiers of neural architecture search forward. Fourth,
the number of weight parameters and search costs corresponding to our methods
are on par with those in differentiable NAS baselines. This shows that LPT is
able to search better-performing architectures without significantly
increasing network size and search cost. A few additional remarks: 1) On
CIFAR-100, DARTS-2nd with second-order approximation in the optimization
algorithm is not advantageous compared with DARTS-1st which uses first-order
approximation; 2) In our run of DARTS-, the performance reported in (Chu et
al., 2020a) cannot be achieved; 3) In our run of DARTS+, in the architecture
evaluation stage, we set the number of epochs to 600 instead of 2000 as used
in (Liang et al., 2019a), to ensure a fair comparison with other methods
(where the epoch number is 600).

Table 3 shows the classification error (%), number of weight parameters
(millions), and search cost (GPU days) of different NAS methods on CIFAR-10.
As can be seen, applying our proposed LPT to DARTS-1st, DARTS-2nd, DARTS-, and
DARTS+ significantly reduces the errors of these baselines. For example, with
the usage of LPT, the error of DARTS-2nd is reduced from 2.76% to 2.68%. This
further demonstrates the efficacy of our method in searching better-performing
architectures, by creating tests with increasing levels of difficulty and
improving the learner through taking these tests.

Table 4 shows the results on ImageNet, including top-1 and top-5
classification errors on the test set, number of weight parameters (millions),
and search costs (GPU days). Following (Liu et al., 2019), we take the
architecture searched by LPT-R18-DARTS-2nd on CIFAR-10 and evaluate it on
ImageNet. As can be seen, applying our LPT method to DARTS-2nd, the top-1
error reduces from 26.7% to 25.3% and the top-5 error reduces from 8.7% to
7.9%, without increasing the search cost and parameter number. This further
demonstrates the effectiveness of our method.

###  4.4 Ablation Studies

In order to evaluate the effectiveness of individual modules in LPT, we
compare the full LPT framework with the following ablation settings.

  * •

Ablation setting 1. In this setting, the tester creates tests solely by
maximizing their level of difficulty, without considering their
meaningfulness. Accordingly, the second stage in LPT where the tester learns
to perform a target-task by leveraging the created tests is removed. The
tester directly learns a selection scalar $s(d)\in[0,1]$ for each example $d$
in the test bank without going through a data encoder or a test creator. The
corresponding formulation is:

$\begin{array}[]{l}\max_{S}\min_{A}\;\;\frac{1}{\sum_{d\in
D_{b}}s(d)}\sum_{d\in D_{b}}s(d)\ell(A,W^{*}(A),d)\\\
s.t.\;\;W^{*}(A)=\min_{W}\;\;L\left(A,W,D_{ln}^{(\mathrm{tr})}\right)\end{array}$
(17)

where $S=\\{s(d)|d\in D_{b}\\}$. In this study, $\lambda$ and $\gamma$ are
both set to 1. The data encoder of the tester is ResNet-18. For CIFAR-100, to
avoid performance collapse because of skip connections, LPT is applied to
P-DARTS. For CIFAR-10, LPT is applied to DARTS-2nd.

  * •

Ablation setting 2. In this setting, in the second stage of LPT, the tester is
trained solely based on the create test, without using the training data of
the target task. The corresponding formulation is:

$\begin{array}[]{l}\max_{C}\min_{A}\;\;\frac{1}{\left|\sigma\left(C,E^{*}(C),D_{b}\right)\right|}L\left(A,W^{*}\left(A\right),\sigma\left(C,E^{*}(C),D_{b}\right)\right)-\lambda
L\left(E^{*}(C),X^{*}(C),D_{tt}^{(\mathrm{val})}\right)\\\
s.t.\;\;E^{*}(C),X^{*}(C)=\min_{E,X}\;\;L\left(E,X,\sigma\left(C,E,D_{b}\right)\right)\\\
\quad\;\;\;W^{*}\left(A\right)=\min_{W}\;\;L\left(A,W,D_{ln}^{(\mathrm{tr})}\right)\end{array}$
(18)

In this study, $\lambda$ and $\gamma$ are both set to 1. The data encoder of
the tester is ResNet-18. For CIFAR-100, to avoid performance collapse because
of skip connections, LPT is applied to P-DARTS. For CIFAR-10, LPT is applied
to DARTS-2nd.

  * •

Ablation study on $\lambda$. We are interested in how the learner’s
performance varies as the tradeoff parameter $\lambda$ in Eq.(3) increases. In
this study, the other tradeoff parameter $\gamma$ in Eq.(3) is set to 1. For
both CIFAR-100 and CIFAR-10, we randomly sample 5K data from the 25K training
and 25K validation data, and use it as a test set to report performance in
this ablation study. The rest 45K data (22.5K training data and 22.5K
validation data) is used for architecture search and evaluation. Tester’s data
encoder is ResNe-18. LPT is applied to P-DARTS.

  * •

Ablation study on $\gamma$. We investigate how the learner’s performance
varies as $\gamma$ increases. In this study, the other tradeoff parameter
$\lambda$ is set to 1. Similar to the ablation study on $\lambda$, on 5K
randomly-sampled test data, we report performance of architectures searched
and evaluated on 45K data. Tester’s data encoder is ResNe-18. LPT is applied
to P-DARTS.

Method | Error (%)
---|---
Difficulty only (CIFAR-100) | 18.12$\pm$0.11
Difficulty + meaningfulness (CIFAR-100) |  17.18$\pm$0.12
Difficulty only (CIFAR-10) | 2.79$\pm$0.06
Difficulty + meaningfulness (CIFAR-10) |  2.72$\pm$0.07
Table 5: Results for ablation setting 1. “Difficulty only” denotes that the tester creates tests solely by maximizing their level of difficulty, without considering their meaningfulness, i.e., the tester does not use the tests to learn to perform the target task. “Difficulty + meaningfulness” denotes the full LPT framework where the tester creates tests by maximizing both difficulty and meaningfulness.  Method | Error (%)
---|---
Test only (CIFAR-100) | 17.54$\pm$0.07
Test + Training data (CIFAR-100) |  17.18$\pm$0.12
Test only (CIFAR-10) | 2.75$\pm$0.03
Test + Training data (CIFAR-10) |  2.72$\pm$0.07
Table 6:  Results for ablation setting 2. “Test only” denotes that the tester
is trained only using the create test to perform the target task. “Test +
Training data” denotes that the tester is trained using both the test and the
training data of the target task.

Table 5 shows the results for ablation setting 1. As can be seen, on both
CIFAR-10 and CIFAR-100, creating tests that are both difficult and meaningful
is better than creating tests solely by maximizing difficulty. The reason is
that a difficult test could be composed of bad-quality examples such as
outliers and incorrectly-labeled examples. Even a highly-accurate learner
model cannot achieve good performance on such erratic examples. To address
this problem, it is necessary to make the created tests meaningful. LPT
achieves meaningfulness of the tests by making the tester leverage the created
tests to perform the target task. The results demonstrate that this is an
effective way of improving meaningfulness.

Table 6 shows the results for ablation setting 2. As can be seen, for both
CIFAR-100 and CIFAR-10, using both the created test and the training data of
the target task to train the tester performs better than using the test only.
By leveraging the training data, the data encoder can be better trained. And a
better encoder can help to create higher-quality tests.

Figure 2: How errors change as $\lambda$ increases.

Figure 3: How errors change as $\gamma$ increases.

Figure 2 shows how classification errors change as $\lambda$ increases. As can
be seen, on both CIFAR-100 and CIFAR-10, when $\lambda$ increases from 0.1 to
0.5, the error decreases. However, further increasing $\lambda$ renders the
error to increase. From the tester’s perspective, $\lambda$ explores a
tradeoff between difficulty and meaningfulness of the tests. Increasing
$\lambda$ encourages the tester to create tests that are more meaningful.
Tests with more meaningfulness can more reliably evaluate the learner.
However, if $\lambda$ is too large, the tests are biased to be more meaningful
and less difficult. Lacking enough difficulty, the tests may not be compelling
enough to drive the learner for improvement. Such a tradeoff effect is
observed in the results on CIFAR-10 as well.

Figure 3 shows how classification errors change as $\gamma$ increases. As can
be seen, on both CIFAR-100 and CIFAR-10, when $\gamma$ increases from 0.1 to
0.5, the error decreases. However, further increasing $\gamma$ renders the
error to increase. Under a larger $\gamma$, the created test plays a larger
role in training the tester to perform the target task. This implicitly
encourages the test creator to generate tests that are more meaningful.
However, if $\gamma$ is too large, the training is dominated by the created
test which incurs the following risk: if the test is not meaningful, it will
result in a poor-quality data-encoder which further degrades the quality of
test creation.

##  5 Conclusions

In this paper, we propose a new machine learning approach – learning by
passing tests (LPT), inspired by the test-driven learning technique of humans.
In LPT, a tester model creates a sequence of tests with growing levels of
difficulty. A learner model continuously improves its learning ability by
striving to pass these increasingly more-challenging tests. We propose a
multi-level optimization framework to formalize LPT where the tester learns to
select hard validation examples rendering the learner to make large prediction
errors and the learner refines its model to rectify these prediction errors.
Our framework is applied for neural architecture search and achieves
significant improvement on CIFAR-100, CIFAR-10, and ImageNet.

## References

  * Cai et al. (2019) Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  In _ICLR_ , 2019.
  * Casale et al. (2019) Francesco Paolo Casale, Jonathan Gordon, and Nicoló Fusi.  Probabilistic neural architecture search.  _CoRR_ , abs/1902.05116, 2019.
  * Chen and Hsieh (2020) Xiangning Chen and Cho-Jui Hsieh.  Stabilizing differentiable architecture search via perturbation-based regularization.  _CoRR_ , abs/2002.05283, 2020.
  * Chen et al. (2020) Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh.  Drnas: Dirichlet neural architecture search.  _CoRR_ , abs/2006.10355, 2020.
  * Chen et al. (2019) Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian.  Progressive differentiable architecture search: Bridging the depth gap between search and evaluation.  In _ICCV_ , 2019.
  * Chu et al. (2019) Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li.  Fair DARTS: eliminating unfair advantages in differentiable architecture search.  _CoRR_ , abs/1911.12126, 2019.
  * Chu et al. (2020a) Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan.  DARTS-: robustly stepping out of performance collapse without indicators.  _CoRR_ , abs/2009.01027, 2020a.
  * Chu et al. (2020b) Xiangxiang Chu, Bo Zhang, and Xudong Li.  Noisy differentiable architecture search.  _CoRR_ , abs/2005.03566, 2020b.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Dong and Yang (2019) Xuanyi Dong and Yi Yang.  Searching for a robust neural architecture in four GPU hours.  In _CVPR_ , 2019.
  * Ganin and Lempitsky (2015) Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In _International Conference on Machine Learning_ , pages 1180–1189, 2015.
  * Goodfellow et al. (2014a) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Advances in neural information processing systems_ , pages 2672–2680, 2014a.
  * Goodfellow et al. (2014b) Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014b.
  * He et al. (2016a) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016a.
  * He et al. (2016b) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016b.
  * Hong et al. (2020) Weijun Hong, Guilin Li, Weinan Zhang, Ruiming Tang, Yunhe Wang, Zhenguo Li, and Yong Yu.  Dropnas: Grouped operation dropout for differentiable architecture search.  In _IJCAI_ , 2020.
  * Howard et al. (2017) Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _CoRR_ , abs/1704.04861, 2017.
  * Hu et al. (2020) Shoukang Hu, Sirui Xie, Hehui Zheng, Chunxiao Liu, Jianping Shi, Xunying Liu, and Dahua Lin.  DSNAS: direct neural architecture search without parameter retraining.  In _CVPR_ , 2020.
  * Huang et al. (2017) Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger.  Densely connected convolutional networks.  In _CVPR_ , 2017.
  * Kingma and Ba (2014) Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _International Conference on Learning Representations_ , 12 2014.
  * Liang et al. (2019a) Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li.  DARTS+: improved differentiable architecture search with early stopping.  _CoRR_ , abs/1909.06035, 2019a.
  * Liang et al. (2019b) Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li.  Darts+: Improved differentiable architecture search with early stopping.  _arXiv preprint arXiv:1909.06035_ , 2019b.
  * Liu et al. (2018a) Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan L. Yuille, Jonathan Huang, and Kevin Murphy.  Progressive neural architecture search.  In _ECCV_ , 2018a.
  * Liu et al. (2018b) Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu.  Hierarchical representations for efficient architecture search.  In _ICLR_ , 2018b.
  * Liu et al. (2019) Hanxiao Liu, Karen Simonyan, and Yiming Yang.  DARTS: differentiable architecture search.  In _ICLR_ , 2019.
  * Luo et al. (2018) Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Yan Liu.  Neural architecture optimization.  In _NeurIPS_ , 2018.
  * Ma et al. (2018) Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun.  Shufflenet V2: practical guidelines for efficient CNN architecture design.  In _ECCV_ , 2018.
  * Noy et al. (2020) Asaf Noy, Niv Nayman, Tal Ridnik, Nadav Zamir, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik.  ASAP: architecture search, anneal and prune.  In _AISTATS_ , 2020.
  * Pham et al. (2018) Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean.  Efficient neural architecture search via parameter sharing.  In _ICML_ , 2018.
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In _Proceedings of the aaai conference on artificial intelligence_ , volume 33, pages 4780–4789, 2019.
  * Shu et al. (2020) Michelle Shu, Chenxi Liu, Weichao Qiu, and Alan Yuille.  Identifying model weakness with adversarial examiner.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 11998–12006, 2020.
  * Szegedy et al. (2015) Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  In _CVPR_ , 2015.
  * Tan et al. (2019) Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V. Le.  Mnasnet: Platform-aware neural architecture search for mobile.  In _CVPR_ , 2019.
  * Wang et al. (2020) Xiaoxing Wang, Chao Xue, Junchi Yan, Xiaokang Yang, Yonggang Hu, and Kewei Sun.  Mergenas: Merge operations into one for differentiable architecture search.  In _IJCAI_ , 2020.
  * Xie et al. (2019) Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin.  SNAS: stochastic neural architecture search.  In _ICLR_ , 2019.
  * Xu et al. (2020) Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong.  PC-DARTS: partial channel connections for memory-efficient architecture search.  In _ICLR_ , 2020.
  * Yu et al. (2017) Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu.  Seqgan: Sequence generative adversarial nets with policy gradient.  In _AAAI_ , 2017.
  * Zela et al. (2020) Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter.  Understanding and robustifying differentiable architecture search.  In _ICLR_ , 2020.
  * Zhang et al. (2018) Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun.  Shufflenet: An extremely efficient convolutional neural network for mobile devices.  In _CVPR_ , 2018.
  * Zhou et al. (2019) Hongpeng Zhou, Minghao Yang, Jun Wang, and Wei Pan.  Bayesnas: A bayesian approach for neural architecture search.  In _ICML_ , 2019.
  * Zoph and Le (2017) Barret Zoph and Quoc V. Le.  Neural architecture search with reinforcement learning.  In _ICLR_ , 2017.
  * Zoph et al. (2018) Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In _CVPR_ , 2018.