summaries: This work makes use of uncertainty estimation methods from active learning to select a subset of training data that produces models with similar (or better) performance compared to models trained on the full training set. It proposes a way to improve the Monte Carlo estimation of model uncertainty by including multiple checkpoints that are generated "for free" during a training run, thereby increasing the number of samples from 5-10 in previous work to 100 in this work. It compares several initialization schemes for the subset model using mutual information as the acquisition function, finds that a "build-up" approach (based on Chitta et. al 2018a) works best, and uses that for the rest of the studies. It then compares several acquisition functions, using the build-up approach, finds that variation ratio performs best, and uses that for the rest of the studies. Next, it compares the Top-1 accuracy on ImageNet obtained by evaluating the ensemble models produced by different ensembling schemes, and finds that ensembling 20 checkpoints from 5 training runs with different random seeds work best. Then, it uses acquisition models that use ensembles from each ensembling scheme to select subsets of the ImageNet data to be used for training the subset model, and then compares the performance of the subset models. Finally, it demonstrates this method of selecting a subset of the training data works even if the subset is used to train a model with a different architecture from the acquisition model.

summaries: Overall, I'm not quite convinced this method would be worth the trouble to implement. On the more realistic benchmarks, they need to keep ~80% of the total dataset size and the claimed "improvement" is rather small (less than 0.6% absolute gain in accuracy, e.g. from 81.86% to 82.37% on CIFAR100 and from 72.33% to 72.78% on ImageNet). There is no runtime comparison, there are missing baselines, and most of the method development seems guided by trying out many options instead of taking a principled approach. Without these, the paper is just not ready for a top conference like ICLR.

abstractText: Deep Neural Networks (DNNs) often rely on very large datasets for training. Given the large size of such datasets, it is conceivable that they contain certain samples that either do not contribute or negatively impact the DNN’s optimization. Modifying the training distribution in a way that excludes such samples could provide an effective solution to both improve performance and reduce training time. In this paper, we propose to scale up ensemble Active Learning methods to perform acquisition at a large scale (10k to 500k samples at a time). We do this with ensembles of hundreds of models, obtained at a minimal computational cost by reusing intermediate training checkpoints. This allows us to automatically and efficiently perform a training data subset search for large labeled datasets. We observe that our approach obtains favorable subsets of training data, which can be used to train more accurate DNNs than training with the entire dataset. We perform an extensive experimental study of this phenomenon on three image classification benchmarks (CIFAR-10, CIFAR-100 and ImageNet), analyzing the impact of initialization schemes, acquisition functions and ensemble configurations. We demonstrate that data subsets identified with a lightweight ResNet-18 ensemble remain effective when used to train deep models like ResNet-101 and DenseNet121. Our results provide strong empirical evidence that optimizing the training data distribution can provide significant benefits on large scale vision tasks.

authors:
William H. Beluch
Tim Genewein
Andreas Nurnberger
Jan M. Kohler

title: The power of ensembles for active learning in image classification

authors:
Vighnesh Birodkar
Hossein Mobahi
Samy Bengio

title: Semantic Redundancies in ImageClassification Datasets: The 10% You Don’t Need

venue: arXiv e-prints, art

authors:
Haw-Shiuan Chang
Erik Learned-Miller
Andrew McCallum

title: Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples

authors:
Kashyap Chitta
Jose M. Alvarez
Adam Lesnikowski

title: Large-Scale Visual Active Learning with Deep Probabilistic Ensembles

venue: arXiv e-prints, art. arXiv:1811.03575,

authors:
Kashyap Chitta
Jianwei Feng
Martial Hebert

title: Adaptive Semantic Segmentation with a Strategic Curriculum of Proxy Labels

venue: arXiv e-prints, art. arXiv:1811.03542,

authors:
David Cohn
Les Atlas
Richard Ladner

title: Improving generalization with active learning

venue: Mach. Learn.,

authors:
Cody Coleman
Stephen Mussmann
Baharan Mirzasoleiman
Peter Bailis
Percy Liang
Jure Leskovec
Matei Zaharia

title: Select via proxy: Efficient data selection for training deep networks, 2019

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: In CVPR,

authors:
Stefan Depeweg
José Miguel Hernández-Lobato
Finale Doshi-Velez
Steffen Udluft

title: Decomposition of Uncertainty in Bayesian Deep Learning for Efficient and Risk-sensitive Learning

authors:
Xuanyi Dong
Yi Yang

title: Searching for a robust neural architecture in four gpu hours

authors:
Thomas Elsken
Jan Hendrik Metzen
Frank Hutter

title: Neural Architecture Search: A Survey

title: Uncertainty in Deep Learning

venue: PhD thesis, University of Cambridge,

authors:
Yarin Gal
Zoubin Ghahramani

title: Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning

authors:
Yarin Gal
Riashat Islam
Zoubin Ghahramani

title: Deep Bayesian Active Learning with Image Data

authors:
E. Gavves
T. Mensink
T. Tommasi
C.G.M. Snoek
T. Tuytelaars

title: Active transfer learning with zero-shot priors: Reusing past datasets for future tasks

venue: In ICCV,

authors:
Daniel Golovin
Benjamin Solnik
Subhodeep Moitra
Greg Kochanski
John Karro
D. Sculley

title: Google vizier: A service for black-box optimization

venue: In SIGKDD,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

title: Identity Mappings in Deep Residual Networks

authors:
Xin He
Kaiyong Zhao
Xiaowen Chu

title: AutoML: A Survey of the State-of-the-Art

authors:
Yihui He
Ji Lin
Zhijian Liu
Hanrui Wang
Li-Jia Li
Song Han

title: AMC: AutoML for Model Compression and Acceleration on Mobile Devices

authors:
Neil Houlsby
Ferenc Huszár
Zoubin Ghahramani
Máté Lengyel

title: Bayesian Active Learning for Classification and Preference Learning

authors:
Gao Huang
Zhuang Liu
Laurens van der Maaten
Kilian Q. Weinberger

title: Densely Connected Convolutional Networks

authors:
Gao Huang
Yixuan Li
Geoff Pleiss
Zhuang Liu
John E. Hopcroft
Kilian Q. Weinberger

title: Snapshot Ensembles: Train 1, get M for free

authors:
Kirthevasan Kandasamy
Karun Raju Vysyaraju
Willie Neiswanger
Biswajit Paria
Christopher R. Collins
Jeff Schneider
Barnabas Poczos
Eric P. Xing

title: Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly

authors:
Alex Kendall
Yarin Gal

title: What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision

authors:
K. Konyushkova
R. Sznitman
P. Fua

title: Introducing geometry in active learning for image segmentation

title: Learning multiple layers of features from tiny images

venue: Technical report,

authors:
Balaji Lakshminarayanan
Alexander Pritzel
Charles Blundell

title: Simple and scalable predictive uncertainty estimation using deep ensembles

venue: In NIPS,

authors:
Agata Lapedriza
Hamed Pirsiavash
Zoya Bylinskii
Antonio Torralba

title: Are all training examples equally valuable

authors:
Hanxiao Liu
Karen Simonyan
Yiming Yang

title: DARTS: Differentiable Architecture Search

authors:
David Lowell
Zachary C. Lipton
Byron C. Wallace

title: How transferable are the datasets collected by active learners

authors:
Renqian Luo
Fei Tian
Tao Qin
Enhong Chen
Tie-Yan Liu

title: Neural architecture optimization

authors:
Andrey Malinin
Mark Gales

title: Predictive Uncertainty Estimation via Prior Networks

authors:
Mojmir Mutny
Andreas Krause

title: Efficient high dimensional bayesian optimization with additivity and quadrature fourier features

venue: In NIPS

authors:
Yaniv Ovadia
Emily Fertig
Jie Ren
Zachary Nado
D Sculley
Sebastian Nowozin
Joshua V. Dillon
Balaji Lakshminarayanan
Jasper Snoek

title: Can You Trust Your Model’s Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift

authors:
Remus Pop
Patric Fulop

title: Deep Ensemble Bayesian Active Learning : Addressing the Mode Collapse issue in Monte Carlo dropout via Ensembles

authors:
Greg Schohn
David Cohn

title: Less is more: Active learning with support vector machines

venue: In ICML,

authors:
Ozan Sener
Silvio Savarese

title: Active Learning for Convolutional Neural Networks: A Core-Set Approach

title: Active learning literature survey

title: A mathematical theory of communication

venue: The Bell System Technical Journal, 27(3):379–423,

authors:
Samarth Sinha
Sayna Ebrahimi
Trevor Darrell

title: Variational Adversarial Active Learning

authors:
Lewis Smith
Yarin Gal

title: Understanding Measures of Uncertainty for Adversarial Example Detection

authors:
Nitish Srivastava
Geoffrey Hinton
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Dropout: A simple way to prevent neural networks from overfitting

authors:
Chen Sun
Abhinav Shrivastava
Saurabh Singh
Abhinav Gupta

title: Revisiting Unreasonable Effectiveness of Data in Deep Learning Era

authors:
Mariya Toneva
Alessandro Sordoni
Remi Tachet des Combes
Adam Trischler
Yoshua Bengio
Geoffrey J. Gordon

title: An Empirical Study of Example Forgetting during Deep Neural Network Learning

authors:
Evgenii Tsymbalov
Maxim Panov
Alexander Shapeev

title: Dropout-based Active Learning for Regression

authors:
Kailas Vodrahalli
Ke Li
Jitendra Malik

title: Are All Training Examples Created Equal? An Empirical Study

authors:
Catherine Wong
Neil Houlsby
Yifeng Lu
Andrea Gesmundo

title: Transfer learning with neural automl

authors:
Sirui Xie
Hehui Zheng
Chunxiao Liu
Liang Lin

title: SNAS: stochastic neural architecture search

venue: In International Conference on Learning Representations,

authors:
I. Zeki Yalniz
Hervé Jégou
Kan Chen
Manohar Paluri
Dhruv Mahajan

title: Billion-scale semisupervised learning for image classification

heading: 1 INTRODUCTION

text:
Deep Neural Networks (DNNs) have become the dominant approach for addressing supervised learning problems. They are trained using stochastic gradient methods, where (i) data is subsampled into mini-batches, and (ii) the network parameters are iteratively updated by the gradient of the parameter weights, relative to a loss function for the given labeled mini-batch of data. The architecture of the DNN, hyper-parameters of the training process, and distribution of the dataset used are all crucial ingredients that impact the final performance of the DNN.
Given the remarkable success of this recipe for supervised learning, there is significant interest in automating the end-to-end process of applying DNNs to real-world problems (Wong et al., 2018; He et al., 2018; 2019). While there has been a considerable effort towards methods and frameworks that automate DNN architecture search (Elsken et al., 2018; Luo et al., 2018; Liu et al., 2018; Xie et al., 2019; Dong & Yang, 2019) and training hyper-parameter search (Golovin et al., 2017; Mutny & Krause, 2018; Kandasamy et al., 2019); the process of searching for the right training data distribution (also called dataset curation) is still performed by experts, requiring several heuristics and significant manual effort. With the rapid growth in the availability of labeled data for large-scale vision tasks, to the order of billions of samples (Sun et al., 2017; Zeki Yalniz et al., 2019), automating the training data subset search would make the application of DNNs much easier for non-experts, and potentially lead to datasets and models that outperform those that were curated by hand. With the cost of data storage also becoming increasingly important, the ability to automatically identify data to remove from the training distribution is appealing from a practical perspective.
In this paper, we present a simple yet effective method to perform a training data subset search by using ensemble Active Learning (AL). The typical goal of AL is to to select, from a large unlabeled dataset, the smallest possible training set to label in order to solve a specific task (Cohn et al., 1994). We instead propose to use AL to build data subsets of a large labeled training dataset that give more
accurate DNNs in less training time. We tackle several key issues that have not been addressed so far by state-of-the-art AL methods. The first is the difficulty in scaling the number of models for ensemble AL. While it seems intuitive that more ensembles can improve performance, existing studies show no gains in AL performance beyond 10 models, and even recommend the use of only 5 models (Lakshminarayanan et al., 2017; Ovadia et al., 2019). Implicit ensemble methods for AL have been found similarly ineffective, but only evaluated in settings with with < 10 models (Beluch et al., 2018). In this study, we propose the use of implicit ensembles with hundreds of training checkpoints from different experimental runs, and empirically demonstrate the effectiveness of this approach. Second, we switch to a large-scale experimental setting compared to what is typically used for AL experiments. For example, Beluch et al. (2018) and Sinha et al. (2019) only acquire 40k and 64k samples at a time respectively on ImageNet, never use more than 30% of the dataset, and do not compare to the full dataset performance. In contrast, for ResNet-18 training on ImageNet, we acquire up to 500k samples at a time and use 80% of the dataset, improving top-1 accuracy by 0.5% over a model trained with the entire dataset. Third, we demonstrate the transferability of the subsets obtained with our approach between DNNs with very different network capacities, ranging from 10-layer ResNets (He et al., 2016) to 121-layer DenseNets (Huang et al., 2016). Given the rapid pace of model development, this shows that our data subsets remain valuable even after a particular model is surpassed by newer architectures. This has been difficult to achieve in prior AL studies (Lowell et al., 2018), and not investigated in detail for large-scale vision tasks.
To summarize, our contributions are as follows: (i) we propose a simple approach to scale up ensemble AL methods to hundreds of models with a negligible computational overhead at train time; (ii) we evaluate several methods to reduce the size of existing large datasets with AL; and (iii) we conduct a detailed empirical study on three popular image classification benchmarks, studying the impact of key design choices, and the robustness of the selected subsets to changes in model architecture. Our study has significant practical implications for DNN training with stochastic gradient methods, as well as for storage of large training datasets.

heading: 2 BUILDING DATA SUBSETS WITH ACTIVE LEARNING

text:
Consider a distribution p(x, y) over inputs x and labels y. In a Bayesian framework, the predictive uncertainty of a particular input x∗ after training on a dataset L is denoted as P(y = k|x∗, L). The predictive uncertainty will result from data (aleatoric) uncertainty and model (epistemic) uncertainty (Kendall & Gal, 2017). A model’s estimates of data uncertainty are described by the posterior distribution over class labels y given a set of model parameters θ. This is typically the softmax output in a classification DNN. Additionally, the model uncertainty is described by the posterior distribution over the parameters θ given the training data L (Malinin & Gales, 2018):
P(y = k|x∗, L)︸ ︷︷ ︸ Predictive =
∫ P(y = k|x∗, θ)︸ ︷︷ ︸
Data
p(θ|L)︸ ︷︷ ︸ Model dθ. (1)
We see that, uncertainty in the model parameters p(θ|L) induces a distribution over the softmax distributions P(y = k|x∗, θ). The expectation is obtained by marginalizing out the parameters θ. Unfortunately, obtaining the full posterior p(θ|L) using Bayes’ rule is intractable. If we train a single DNN, we only obtain a single sample from the distribution p(θ|L). Ensemble uncertainty estimation techniques approximate the integral from Eq. 1 by Monte Carlo estimation, generating multiple samples using different members of an ensemble (Lakshminarayanan et al., 2017):
P(y = k|x∗, L) ≈ 1 E ∑ e∈E P(y = k|x∗, θe), θe ∼ q(θ). (2)
where q(θ) represents an approach used for building the ensemble. The strength of the ensemble approximation depends on both the number of samples drawn (E), and how the parameters for each model in the ensemble are sampled (i.e., how closely the distribution q(θ) matches p(θ|L)).
Algorithm 1 Building Data Subsets with Active Learning.
Initialize parameters of acquisition model {θ(e)a }Ee=1 and subset model θs . initialization Initialize data subset S Compute acquisition function α(x,Ma) ∀ x ∈ L . acquisition Append Ns samples with the maximum acquisition function to S Use S to optimize parameters θs of subset model . optimization
Uncertainty estimation acts as the core component of our approach to build data subsets, for which the pseudo code is presented in Algorithm 1. The algorithm is a modification of the typical AL setting, and involves the following:
1. A labeled dataset, consisting of Nl labeled pairs, L = {(xjl , y j l )} Nl j=1, where each xj ∈ X
is a data point and each yj ∈ Y is its corresponding label.
2. An acquisition model, Ma : X → Y . For our ensemble AL approach, the acquisition modelMa takes the form of a set of E different DNNs with parameters {θ(e)a }Ee=1.
3. A data subset, S = {(xjs, yjs)} Ns j=1, where S is a subset of L selected using an acquisition
function α(x,Ma).
4. A subset model,Ms : X → Y , with parameters θs, trained on S.
As detailed in Algorithm 1, we decouple the data selection and final optimization of AL into two different models. The acquisition model selects a subset of data using ensemble uncertainty estimation, which is then used to optimize the parameters of the subset model.

heading: 2.1 INITIALIZATION SCHEMES

text:
We consider three different initialization schemes for the parameters of the acquisition and subset models: pretrain, compress and build up. The pretrain scheme uses the entire dataset L for pretraining both the acquisition and subset models. During optimization, the subset model is then finetuned on the data subset S. In the compress scheme, the acquisition model is pretrained on L but the subset model is randomly initialized and trained from scratch on S. The acquisition model therefore accesses all the data and then ’compresses’ the dataset for the subset model. For the pretrain and compress schemes, the subset S is initialized with an empty set.
Finally, in the build up scheme, we follow an iterative AL loop. Specifically, we start by initializing S with a randomly selected subset of the data to train an acquisition model. After performing acquisition, instead of training a single subset model, we optimize an ensemble of E networks. This ensemble is used as an acquisition model for a subsequent iteration. Our goal is to finally reach a subset of Ns samples. As observed by Chitta et al. (2018a), exponentially growing the dataset size offers practical benefits in an AL loop setting. We therefore follow this approach, by initializing S with Ns8 random samples, and iterating two further times at Ns 4 and Ns 2 samples before obtaining a final subset of size Ns.

heading: 2.2 ACQUISITION FUNCTIONS

text:
In our experiments, we empirically evaluate four acquisition functions of the form α : x → R for AL– entropy, mutual information, variation ratios and error count. We choose these well-known acquisition functions to maintain simplicity and scalability. For a detailed theoretical analysis of these acquisition functions, we refer the reader to Gal (2016).
Bayesian AL approaches argue that the acquisition function must target samples with high model uncertainty rather than data uncertainty. Intuitively, the reasoning behind this is that model uncertainty is a result of not knowing the correct parameters, which can be reduced by adding the right data and retraining the model. However, data uncertainty exists even for a model with the most optimal parameters, and cannot be reduced by adding more data (Kendall & Gal, 2017).
In the case of classification, the predictive uncertainty for a sample P(y = k|x∗, L) from Eq. 1 is a multinomial distribution, which can be represented as a vector of probabilities p over each of the K classes. We can obtain the predictive uncertainty for a sample as its entropy (Shannon, 1948):
H(p) = −pT log p. (3)
However, once we marginalize out θ from Eq. 1 it is impossible to tell if this predictive uncertainty is a result of model uncertainty or data uncertainty. One acquisition function that explicitly looks for large disagreement between the models (i.e., model uncertainty), is mutual information (Houlsby et al., 2011; Smith & Gal, 2018), also called BALD and Jensen-Shannon Divergence:
J (p)︸ ︷︷ ︸ Model = H(p)︸ ︷︷ ︸ Predictive − 1 E ∑ e∈E H(p(e))︸ ︷︷ ︸
Data
. (4)
where p(e) denotes the prediction of an individual member of the ensemble before marginalization. Since entropy is always positive, the maximum possible value for J (p) isH(p). However, when the models make similar predictions, 1E ∑E e=1H(pe) → H(p), and J (p) → 0, which is its minimum value. This shows that J encourages samples with high disagreement to be selected during the data acquisition process. An alternate way to look at the metric is that from the predictive uncertainty, we subtract away the expected data uncertainty, leaving an approximate of the model uncertainty (Depeweg et al., 2017).
Variation ratios (Gal, 2016) is another acquisition function that looks for disagreement. It is defined as the fraction of members in the ensemble that do not agree with the majority vote M = Mode
e∈E (argmax k∈K p(e)k ):
V(p) = 1− 1 E ∑ e∈E (argmax k∈K p(e)k =M), (5)
where K is the number of classes. This is the simplest quantitative measure of variation, and prior applications in literature show that it works well in practice (Gal et al., 2017; Beluch et al., 2018; Chitta et al., 2018b). Our work focuses on classification due to its prevalence in the large-scale setting, but we note that V shares similarities to variance and standard deviation, which are used as acquisition functions in the Bayesian setting for regression (Tsymbalov et al., 2018).
Our final acquisition function, error count, is similar to variation ratios, but checks for disagreement with the ground truth label y rather than the mode of predictions M :
E(p) = 1− 1 E ∑ e∈E (argmax k∈K p(e)k = y). (6)
This is typically not used in AL experiments as it cannot be computed without the ground truth labels. In our setting, where the labels are available, we use this function as a baseline which, in principle, prioritizes mistakes made by the network when selecting data.

heading: 2.3 ENSEMBLE CONFIGURATIONS

text:
State-of-the-art ensemble-based AL approaches use different random seeds to construct ensembles (Beluch et al., 2018). They recommend the number of samples drawn to be in the range E ∈ (5, 10) models (Lakshminarayanan et al., 2017). In theory, the error of a Monte Carlo estimator should decrease with more samples, which is evident in other BNN based uncertainty estimation techniques, that require the number of stochastic samples drawn to be increased to the range E ∈ (50, 100) (Gal & Ghahramani, 2015).
The major limiting factor preventing the training of E ∈ (50, 100) models with different random seeds for ensemble AL is the computational burden at train time. Implicit ensembling approaches that are computationally inexpensive, such as Dropout (Srivastava et al., 2014), suffer from mode
collapse, where the different members in the ensemble lack sufficient diversity for reliable uncertainty estimation (Pop & Fulop, 2018). An alternate approach, called snapshot ensembles, that is less computationally expensive at train time, uses a cyclical learning rate to converge to multiple local optima in a single training run (Huang et al., 2017). However, this technique is also limited to ensembles in the range of E = 6 members. In our work, we present an implicit ensembling approach that allows users to draw a large number of samples using the catastrophic forgetting property in DNNs (Toneva et al., 2018). Specifically, we exploit the disagreement between different checkpoints stored during successive training epochs to efficiently construct large and diverse ensembles. We collect several training checkpoints over multiple training runs with different random seeds.
Though we study the impact of the number of samples, our work does not attempt specifically to better match q(θ) from Eq. 1 and p(θ|L) from Eq. 2, which is an open and active research area (Malinin & Gales, 2018). The overall algorithm is generic and can potentially benefit from more advanced techniques for uncertainty estimation.

heading: 3 EXPERIMENTS

text: In this section, we demonstrate the effectiveness of AL for building data subsets of three image classification benchmarks. We initially investigate the impact of the initialization schemes discussed in Section 2.1 and acquisition functions from Section 2.2 for the ResNet-18 architecture (He et al., 2016). We then focus on scaling up the ensemble and evaluating the robustness of our subsets to architecture shifts. We experiment with three datasets: CIFAR-10 and CIFAR-100 (Krizhevsky, 2009), as well as ImageNet (Deng et al., 2009). The CIFAR datasets involve object classification tasks over natural images: CIFAR-10 is coarse-grained over 10 classes, and CIFAR-100 is finegrained over 100 classes. For both tasks, there are 50k training images and 10k validation images of resolution 32 × 32, which are balanced in terms of the number of training samples per class. ImageNet consists of 1000 object classes, with annotation available for 1.28 million training images and 50k validation images of resolution 256 × 256. This dataset has a slight class imbalance, with 732 to 1300 training images per class.

heading: 3.1 IMPLEMENTATION DETAILS

text: Unless otherwise specified, we use 8 models with the ResNet-18 (He et al., 2016) architecture to build the acquisition and subset models. For ImageNet, each ResNet-18 uses the standard kernel sizes and counts. For CIFAR-10 and CIFAR-100, we use a variant of ResNet-18 as proposed in He et al. (2016). For all three tasks, we do mean-std pre-processing, and augment the labeled dataset on-line with random crops and horizontal flips. Optimization is done using Stochastic Gradient Descent with a learning rate of 0.1 and momentum of 0.9, and weight decay of 10−4. On CIFAR, we use a patience parameter (set to 25) for counting the number of epochs with no improvement in validation accuracy, in which case the learning rate is dropped by a factor of 0.1. We end training when dropping the learning rate also gives no improvement in the validation accuracy after a number of epochs equal to twice the patience parameter. If the early stopping criterion is not met, we train for a maximum of 400 epochs. On ImageNet, we train for a total of 150 epochs, scaling the learning rate by a factor of 0.1 after 70 and 130 epochs. Experiments are run on Tesla V100 GPUs.

heading: 3.2 RESULTS

text:
Initialization schemes. In our first experiment, we compare the three initialization schemes introduced in Section 2.1 to a random subsampling baseline. For this experiment, we fix the number of ensemble members to 8 for CIFAR and 4 for ImageNet, each with a different random seed. We fix the acquisition function to Mutual Information (J ), as defined in Eq. 4. For the pretrain scheme, we pretrain 8 (or 4) models with different random seeds on the entire dataset L, and finetune them starting with a learning rate of 10−3 on the chosen subset S. For the other schemes, we train the subset model from scratch on S. We report the top-1 validation accuracy of three independent ensembles, each from a different experimental trial, plotting the mean with one standard deviation as an error bar. These results are summarized in Fig. 1.
We observe certain common trends for all three datasets: random subsampling (blue in Fig. 1) leads to a steady drop-off in performance; and the pretrain scheme (orange in Fig. 1) does not significantly
impact the performance in comparison to training with the full dataset. Interestingly, the compress scheme (green in Fig. 1) performs extremely poorly when the subset chosen is very small, but performs well when the acquisition and subset models have a similar overall dataset size (eg., 1M samples on ImageNet). The poor performance of the compress scheme implies that the uncertainty estimates for this experiment are not robust to large changes in the dataset distribution between the acquisition and subset models. The build up scheme (red in Fig. 1) consistently outperforms random subsampling by a large margin. The performance is robust across all three tasks. Based on these observations, we fix the initialization scheme to build up for the next experiments. With a sufficiently large subset of the data (eg., 25k on CIFAR-10, 1M on ImageNet), the build up scheme slightly outperforms a model trained on the full dataset.
Acquisition functions. In our next experiment, we compare random subsampling against the four acquisition functions from Section 2.2. Similar to the previous experiment, we use ensembles of 8 members for CIFAR and 4 members for ImageNet for both the acquisition and subset models. We run three experimental trials, and report the mean validation accuracy of the subset model ensemble for each trial, in Table 1.
For all four acquisition functions, the subset models significantly outperform the baseline (random) at the final iteration. Further, when using 50% of the data on CIFAR-10, and 80% of the data on CIFAR-100 and ImageNet, we obtain subsets of data that improve performance compared to training on the full dataset (100%). Among the four functions, mutual information (J ) and variation ratios (V) outperform entropy (H) and error count (E). Interestingly, though the E acquisition function is similar to V , and also has access to the ground truth labels, the data selected by it in the first iteration leads to poor performance, which is not completely recovered in the subsequent iterations. This indicates that a sample for which all the ensemble members collectively make an error may be ’too difficult’ and therefore not an ideal choice for the training dataset.
Among the two best acquisition functions, on the CIFAR-10 dataset, J outperforms V . This is because there are very few absolute disagreements in this setting due to the small number of classes and high performance, which leads to a very small number of samples with non-zero values for V . However, on the CIFAR-100 and ImageNet datasets, with more classes and lower overall performance, there is a greater number of disagreements, and V outperforms J by a significant amount when using 80% of the dataset. Compared to training on the full dataset, we obtain a 0.5% absolute improvement in validation accuracy on both CIFAR-100 and ImageNet when using the subset acquired by V . Additionally, this performance improvement is accompanied by a 20% reduction in training time on both these tasks.
Ensemble configurations. We now explore the possibility of further gains in performance by scaling up the ensemble to increase the number of samples drawn in the Monte Carlo estimator as per Eq. 2. For the remaining experiments, we focus on the final AL iteration for the ImageNet dataset as per the build up scheme. To do this, we start by setting up 5 different training runs on 40% of the
ImageNet dataset (512k samples) as selected by the best performing acquisition function in Table 1 (J ). For each of these 5 training runs, we store the 21 checkpoints obtained in the final stage of training (epochs 130-150, exact implementation details provided in appendix). We pick 4 ensemble configurations from these ResNet-18 training runs to utilize as the acquisition model for an ablation study: (i) random seeds, which uses a total of 5 models from the best performing epoch of each run; (ii) 5 checkpoints, which uses the 5 models from epochs 130:5:150 of a single run; (iii) 20 checkpoints, which uses the 20 models from epochs 131:1:150 of a single run; and (iv) combined, which uses the ’20 checkpoints’ combined over all 5 runs to give 100 models.
We initially evaluate the performance of these four ensemble configurations on the data available for sampling. To this end, we report the top-1 accuracy of the four ensemble configurations, along with a baseline of a single model, when evaluated on the 40% selected data (i.e, the training set) and 60% unselected data of ImageNet. Our results are shown in Table 2. Results for the Single (1), Checkpoints (5) and Checkpoints (20) columns use the best seed of 5 runs. As the number of members in the ensemble is scaled up, we observe large and clear improvements in performance on both selected and unselected data. This shows that the checkpoints obtained with no additional computational cost at train time can be used to generate diverse ensembles. A detailed analysis of the diversity and agreement between checkpoints is provided in the appendix.
The significant gains (around 3%) in performance on unselected data in Table 2 as the number of models is increased from 5 to 100 indicates the potential for better sampling by scaling up. It is additionally worth noting that for all ensemble configurations, the performance is better on the larger unselected subset of data than on the selected training set. For a single model, the gap in top-1 accuracy between these two subsets is nearly 13%. This demonstrates the huge amount of redundancy in the unselected part of the dataset as a result of our AL based selection.
Further, we are interested in how the ensemble configurations affect the acquisition function. To this end, we query for an additional 40% of the unselected data (512k samples) using the variation ratios (V) acquisition function, with each of the four ensemble configurations. We obtain four new subsets, each with 80% of the samples in ImageNet. The top-1 validation accuracy of a subset model trained using each of these new subsets is shown in Table 3, along with a baseline of random sampling of 80% of the data. We observe a steady increase in performance as the number of models in Ma during acquisition is increased, showing the benefits of scaling up ensemble AL. In particular, the combined configuration improves top-1 accuracy over random sampling by 1.1%. Note that the earlier results in Table 1 use an ensemble of 4 models for evaluation; but Table 3 always evaluates
a single model, to allow for a fair comparison between the datasets acquired with 5 models vs. 100 models. Our results show that scaling up is key to exploiting implicit ensembling techniques for AL. Existing work that uses the related idea of snapshot ensembles for AL performs poorly (Beluch et al., 2018). This is likely due to (i) the small number of models used, and (ii) the smaller-scale experimental setting (only 2k samples acquired each iteration).
Robustness to architecture shift. Finally, we evaluate the robustness of the subsets to changes in model capacity. Specifically, we evaluate the robustness of the best performing subset selected with a ResNet-18 acquisition model in Table 3 (’combined’). Additionally, we consider the subset obtained with an even more lightweight ResNet-10 model, where we remove 2 convolutional layers from each residual block of a ResNet-18. We use these subsets (referred to as AL-R18-80 and AL-R10-80) to train subset models with the ResNet-18, ResNet-34, ResNet-50, ResNet-101 (He et al., 2016) and DenseNet-121 (Huang et al., 2016) architectures. For reference, we also evaluate a randomly subsampled 80% of ImageNet (Random-80) and the full dataset (Full-100). Our results are summarized in Table 4. As shown, on all 5 architectures, the subset obtained by AL with ResNet-18 achieves similar performance to training on the full dataset, with a 20% reduction in overall training time. The AL-R10-80 subset also strongly outperforms the random baseline. This ability to transfer selected subsets to larger architectures has significant implications in domains where training time is crucial, such as MLPerf (MLP, 2019).

heading: 4 RELATED WORK

text:
A comprehensive review of classical approaches to AL is presented in Settles (2010). In these approaches, data samples for which the current model is uncertain are queried for labeling. It is occasionally observed in the classical AL literature that training on a subset of data can give better models than training on the full dataset (Schohn & Cohn, 2000; Lapedriza et al., 2013; Gavves et al., 2015; Konyushkova et al., 2015). However, this is not investigated with state-of-the-art AL techniques for DNNs (Beluch et al., 2018; Sinha et al., 2019). These methods typically assume that the performance obtained by training on the entire data pool is an upper bound. We show that the full dataset is not an upper bound, demonstrating distinct advantages of training on data subsets when they are sufficiently large.
Despite the widespread use of image classification datasets, there has only recently been an increased interest in understanding the properties of data subsets. Core-set selection (Sener & Savarese, 2017) is one such attempt to reduce dataset sizes, by finding a representative subset of points based on relative distances in the DNN feature space. Vodrahalli et al. (2018) also aims to find representative subsets, using the magnitude of the gradient generated by each sample for the DNN as an impor-
tance measure. It is important to note that these techniques are unable to match or improve the performance of a model trained with all the data for DNNs.
More recent techniques are able to successfully reduce dataset sizes by identifying redundant examples, albeit to a much smaller extent than our approach. Birodkar et al. (2019) uses clustering in the DNN feature space to identify redundant samples, leading to a discovery of 10% redundancy in the CIFAR-10 and ImageNet datasets. Select via proxy (Coleman et al., 2019) uses simple uncertainty metrics (confidence, margin and entropy) to select a subset of data for training, and removes 40% of the samples in CIFAR-10 without reducing the network performance. In comparison to these methods, our technique not only maintains, but also improves the performance of a DNN. Further, we empirically show that this can be done with much less data than these methods, for example, on CIFAR-10, we only require 50% of the training dataset.
A second category of works on data subsets is closely related to catastrophic forgetting in DNNs. Toneva et al. (2018) uses the number of instances in which a previously correctly classified sample is ’forgotten’ and misclassified during training as an importance measure. By doing so, this method is able to remove 30% of the samples that are ’unforgettable’ from CIFAR-10 without significantly reducing performance. Chang et al. (2017) propose a similar idea of emphasizing data points whose predictions have changed most over the previous epochs during training. Rather than directly subsampling, this variance in predictions is used to increase or decrease the sampling weight during training, and therefore the approach has no significant impact on training time. In comparison, by training on only a specific subset, we not only improve performance but also cut down training time by 20% to 50% for the datasets used in our study.

heading: 5 CONCLUSION

text: In this paper, we presented an approach to build data subsets for deep neural networks. Our method uses ensemble Active Learning to estimate the uncertainty of each sample in a dataset, and then chooses only the highest uncertainty samples for training. Our results demonstrate that this improves the performance of a DNN compared to training with the entire dataset on three different image classification benchmarks. Moreover, we propose a simple technique to scale up ensembles leading to additional accuracy gains with minimum computational overhead. Importantly, our results demonstrate that datasets obtained using AL can be effectively reused for training new models with different capacity or network architectures.

heading: No Outliers 12.5% Outliers 25% Outliers No Outliers 12.5% Outliers 25% Outliers

heading: A ADDITIONAL EXPERIMENTS

text:
Validation curves for different initialization schemes. To analyze the runtime and convergence of different models, we plot the top-1 validation error of a single ResNet-18 model for the three initialization schemes from Section 2.1. This experiment is run using the variation ratios acquisition function on 80% of ImageNet in three settings: Pretrain-80, Compress-80 and Build-Up-80. We compare to the baselines of 80% randomly sampled data (Random-80) and the full dataset (Full100). Our results are shown in Fig. 2. Initially, the error for Pretrain-80 is lower than the other approaches, but towards the end of training, Pretrain-80, Compress-80 and Build-Up-80 obtain a similar validation accuracy. All three initialization schemes finish training in 20% less time than using the full dataset.
Outliers. It is possible that a very small subset with high uncertainty is informative to the acquisition model, but too difficult for the subset model which is trained from scratch with just these samples. To check for this, we repeat the experiment for the compress scheme on CIFAR from Fig. 1 while choosing a subset of 25k samples (50%), but set aside a percentage of the highest uncertainty samples as outliers instead of adding them to S them during acquisition. For example, for 12.5% outliers, after sorting by the acquisition function, we select the samples in the range 37.5% to 87.5% as the subset S instead of 50% to 100%. As shown in Table 5, leaving outliers does not improve the performance of the compress scheme on CIFAR-10. Even in the case of CIFAR-100, where there is an improvement in performance after removing outliers, the obtained accuracy of 76.76% is well
Table 6: Effect of class-balanced random sampling on the ImageNet dataset. Results shown are the top-1 validation accuracy of a single trial for training a single ResNet-18 model. We observe that class balancing does not have significant impact on performance.
Random Random with Class Balance 10% 20% 40% 10% 20% 40%

heading: 49.57 57.76 64.43 49.10 57.80 64.34

text:
Figure 3: Analyzing the prediction consensus between different checkpoints during ImageNet training. We observe very little, but consistent agreement in predictions between any consecutive pair of checkpoints. The overall agreement among the group of models decays rapidly. With 20 checkpoints, there is only consensus on around 90k samples for ResNet-18 and 50k samples for ResNet-10 out of the 768k samples used for this evaluation.
short of the build up scheme (red in Fig. 1), which reaches 79.37%. This indicates that though the highest uncertainty samples are sub-optimal for training when taken alone, they are important when used as part of a larger set of samples.
Additionally, we conduct an experiment checking for outliers on ImageNet with the build up scheme in the setting of Table 3. In this experiment, we sample 80% of the dataset while leaving out 50k samples (approximately 4%) as outliers for the ’combined’ ensemble configuration. Doing so reduces subset model performance from 70.34% to 70.09%, indicating that the highest uncertainty samples are indeed crucial to outperforming the model trained on the full dataset.
Class-balanced sampling on ImageNet. While CIFAR-10 and CIFAR-100 have a balanced number of samples per class, ImageNet has a slight class imbalance. This allows a potentially more refined baseline than pure random sampling, by additionally incorporating class balance. We implement this approach by collecting 128, 256 and 512 samples per class randomly for all 1000 classes. This leads to datasets of 10%, 20% and 40% of the full dataset. We compare this baseline to standard random sampling in terms of top-1 validation accuracy for ResNet-18 training. Our results are summarized in Table 6. We observe no significant differences between standard random sampling and the new random sampling with class balance.
Checkpoint consensus. We extend our analysis on the 768k unselected samples of ImageNet from the setting in Table 2, by checking the consensus between the group of n final training checkpoints using both the ResNet-18 and ResNet-10 architectures for n = 2 to 20. In addition, we check the consensus in predictions for every consecutive pair of checkpoints as a reference. Our results are presented in Fig. 3. We observe that for ResNet-18 training, any consecutive pair of checkpoints
only agree on the top-1 prediction of around 450k samples (blue in Fig. 3, which is 58% of the data). All 20 checkpoints of a single run only agree on 90k samples (orange in Fig. 3, which is 11.7% of the data). This is surprising, since the top-1 accuracy of each model on the unselected data is above 70%, indicating that though they are all from the same training run and have similar accuracy, each checkpoint makes different kinds of errors. These results also provide further support to the findings of Toneva et al. (2018), which show that a very small subset of samples are ’unforgettable’ once learned by the network, and many samples are repeatedly relearned and forgotten. Since the number of disagreements provides valuable information about the uncertainty of each sample for the acquisition functions used in our study, these results showcase the benefits of using more models in an ensemble for uncertainty estimation. The consensus trends for both pairwise and all models remain similar for the ResNet-10 architecture, though the absolute values are lower than ResNet-18 due to the lower model accuracy (green and red in Fig. 3).


summaries: Authors improve upon dynamic routing between capsules by removing the squash function (norm normalization) and apply a layerNorm normalization instead. Furthermore, they experiment with concurrent routing rather than sequential routing (route all caps layers once, then all layers concurrently again and again). This is an interesting development since provides better gradient in conjunction with layerNorm. They report results on Cifar10 and Cifar100 and achieve similar to CNN (resnet) performance.

summaries: This paper presents a new simpler routing mechanism for capsule networks and achieves good performance on real world data sets making use of this new capsule structure along with a restnet backbone. Strong performance on the cifar10 and cifar100 datasets are presented and the network outperforms earlier versions of capsule networks. This new structure also performs well on an augmented MNIST dataset of overlapping digits (similar to the one used by Sabour et al 2017).

abstractText: We introduce a new routing algorithm for capsule networks, in which a child capsule is routed to a parent based only on agreement between the parent’s state and the child’s vote. The new mechanism 1) designs routing via inverted dot-product attention; 2) imposes Layer Normalization as normalization; and 3) replaces sequential iterative routing with concurrent iterative routing. When compared to previously proposed routing algorithms, our method improves performance on benchmark datasets such as CIFAR-10 and CIFAR-100, and it performs at-par with a powerful CNN (ResNet-18) with 4× fewer parameters. On a different task of recognizing digits from overlayed digit images, the proposed capsule model performs favorably against CNNs given the same number of layers and neurons per layer. We believe that our work raises the possibility of applying capsule networks to complex real-world tasks. Our code is publicly available at: https://github. com/apple/ml-capsules-inverted-attention-routing. An alternative implementation is available at: https://github.com/ yaohungt/Capsules-Inverted-Attention-Routing/blob/ master/README.md.

authors:
Shaojie Bai
J. Zico Kolter
Vladlen Koltun

title: Deep equilibrium models

venue: In Neural Information Processing Systems (NeurIPS),

authors:
Jaewoong Choi
Hyun Seo
Suee Im
Myungju Kang

title: Attention routing between capsules

venue: arXiv preprint arXiv:1907.01750,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Geoffrey E Hinton
Alex Krizhevsky
Sida D Wang

title: Transforming auto-encoders

venue: In International Conference on Artificial Neural Networks,

authors:
Geoffrey E Hinton
Sara Sabour
Nicholas Frosst

title: Matrix capsules with em routing

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Adam R Kosiorek
Sara Sabour
Yee Whye Teh
Geoffrey E Hinton

title: Stacked capsule autoencoders

venue: arXiv preprint arXiv:1906.06818,

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Juho Lee
Yoonho Lee
Jungtaek Kim
Adam Kosiorek
Seungjin Choi
Yee Whye Teh

title: Set transformer: A framework for attention-based permutation-invariant neural networks

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
Hongyang Li
Xiaoyang Guo
Bo DaiWanli Ouyang
Xiaogang Wang

title: Neural network encapsulation

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Sai Samarth R Phaye
Apoorva Sikka
Abhinav Dhall
Deepti Bathula

title: Dense and diverse capsule networks: Making the capsules learn better

venue: arXiv preprint arXiv:1805.04001,

authors:
Sara Sabour
Nicholas Frosst
Geoffrey E Hinton

title: Dynamic routing between capsules

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Dilin Wang
Qiang Liu

title: An optimization view on dynamic routing between capsules

title: A MODEL CONFIGURATIONS FOR CIFAR-10/CIFAR-100 A.1 MODEL SPECIFICATIONS The configuration choices of Dynamic Routing CapsNets and EM Routing CapsNets are followed by prior work (Sabour et al., 2017

heading: 1 INTRODUCTION

text:
Capsule Networks (CapsNets) represent visual features using groups of neurons. Each group (called a “capsule”) encodes a feature and represents one visual entity. Grouping all the information about one entity into one computational unit makes it easy to incorporate priors such as “a part can belong to only one whole” by routing the entire part capsule to its parent whole capsule. Routing is mutually exclusive among parents, which ensures that one part cannot belong to multiple parents. Therefore, capsule routing has the potential to produce an interpretable hierarchical parsing of a visual scene. Such a structure is hard to impose in a typical convolutional neural network (CNN). This hierarchical relationship modeling has spurred a lot of interest in designing capsules and their routing algorithms (Sabour et al., 2017; Hinton et al., 2018; Wang & Liu, 2018; Zhang et al., 2018; Li et al., 2018; Rajasegaran et al., 2019; Kosiorek et al., 2019).
In order to do routing, each lower-level capsule votes for the state of each higher-level capsule. The higher-level (parent) capsule aggregates the votes, updates its state, and uses the updated state to explain each lower-level capsule. The ones that are well-explained end up routing more towards that parent. This process is repeated, with the vote aggregation step taking into account the extent to which a part is routed to that parent. Therefore, the states of the hidden units and the routing probabilities are inferred in an iterative way, analogous to the M-step and E-step, respectively, of an Expectation-Maximization (EM) algorithm. Dynamic Routing (Sabour et al., 2017) and EMrouting (Hinton et al., 2018) can both be seen as variants of this scheme that share the basic iterative structure but differ in terms of details, such as their capsule design, how the votes are aggregated, and whether a non-linearity is used.
We introduce a novel routing algorithm, which we called Inverted Dot-Product Attention Routing. In our method, the routing procedure resembles an inverted attention mechanism, where dot products are used to measure agreement. Specifically, the higher-level (parent) units compete for the attention of the lower-level (child) units, instead of the other way around, which is commonly used in attention
models. Hence, the routing probability directly depends on the agreement between the parent’s pose (from the previous iteration step) and the child’s vote for the parent’s pose (in the current iteration step). We also propose two modifications for our routing procedure – (1) using Layer Normalization (Ba et al., 2016) as normalization, and (2) doing inference of the latent capsule states and routing probabilities jointly across multiple capsule layers (instead of doing it layer-wise). These modifications help scale up the model to more challenging datasets.
Our model achieves comparable performance as the state-of-the-art convolutional neural networks (CNNs), but with much fewer parameters, on CIFAR-10 (95.14% test accuracy) and CIFAR-100 (78.02% test accuracy). We also introduce a challenging task to recognize single and multiple overlapping objects simultaneously. To be more precise, we construct the DiverseMultiMNIST dataset that contains both single-digit and overlapping-digits images. With the same number of layers and the same number of neurons per layer, the proposed CapsNet has better convergence than a baseline CNN. Overall, we argue that with the proposed routing mechanism, it is no longer impractical to apply CapsNets on real-world tasks. We will release the source code to reproduce the experiments.

heading: 2 CAPSULE NETWORK ARCHITECTURE

text:
An example of our proposed architecture is shown in Figure 1. The backbone is a standard feedforward convolutional neural network. The features extracted from this network are fed through another convolutional layer. At each spatial location, groups of 16 channels are made to create capsules (we assume a 16-dimensional pose in a capsule). LayerNorm is then applied across the 16 channels to obtain the primary capsules. This is followed by two convolutional capsule layers, and then by two fully-connected capsule layers. In the last capsule layer, each capsule corresponds to a class. These capsules are then used to compute logits that feed into a softmax to computed the classification probabilities. Inference in this network requires a feed-forward pass up to the primary capsules. After this, our proposed routing mechanism (discussed in the next section) takes over.
In prior work, each capsule has a pose and some way of representing an activation probability. In Dynamic Routing CapsNets (Sabour et al., 2017), the pose is represented by a vector and the activation probability is implicitly represented by the norm of the pose. In EM Routing CapsNets (Hinton et al., 2018), the pose is represented by a matrix and the activation probability is determined by the EM algorithm. In our work, we consider a matrix-structured pose in a capsule. We denote the capsules in layer L as PL and the i-th capsule in layer L as pLi . The pose p L i ∈ RdL in a vector form and will be reshaped to R √ dL× √ dL when representing it as a matrix, where dL is the number of hidden units grouped together to make capsules in layer L. The activation probability is not explicitly represented. By doing this, we are essentially asking the network to represent the absence of a capsule by some special value of its pose.

heading: 3 INVERTED DOT-PRODUCT ATTENTION ROUTING

text:
The proposed routing process consists of two steps. The first step computes the agreement between lower-level capsules and higher-level capsules. The second step updates the pose of the higher-level capsules. Step 1: Computing Agreement: To determine how capsule j in layer L + 1 (pL+1j ) agrees with capsule i in layer L (pLi ), we first transform the pose p L i to the vote vLij for the pose p L+1 j . This
Higher-level Capsules
Lower-level Capsules
pose
…
…
Agreement by Dot-Product Attention
multiplication
∑ LayerNorm( ⋅ )routing coefficients
Pose UpdateRouting Coefficients as Normalized Agreement
agreement
weight
matrix multiplication
reshape
⋅dot product ⊤ Softmax( ⋅ ) …
…
…
…
Figure 2: Illustration of the Inverted Dot-Product Attention Routing with the pose admitting matrix structure.
Procedure 1 Inverted Dot-product Attention Routing algorithm returns updated poses of the capsules in layer L + 1 given poses in layer L and L + 1 and weights between layer L and L + 1.
1: procedure INVERTED DOT-PRODUCT ATTENTION ROUTING(PL, PL+1, WL) 2: for all capsule i in layer L and capsule j in layer (L + 1): vLij ←WLij · pLi . vote 3: for all capsule i in layer L and capsule j in layer (L + 1): aLij ← p L+1 j
> · vLij . agreement 4: for all capsule i in layer L: rLij ← exp(aLij) / ∑ j′ exp(a L ij′) . routing coefficient
5: for all capsule j in layer (L + 1): pL+1j ← ∑ i r L ijv L ij . pose update 6: for all capsule j in layer (L + 1): pL+1j ← LayerNorm(p L+1 j ) . normalization 7: return PL+1
transformation is done using a learned transformation matrix WLij :
vLij = W L ij · pLi , (1)
where the matrix WLij ∈ RdL+1×dL if the pose has a vector structure and WLij ∈ R √ dL+1× √ dL (requires dL+1 = dL) if the pose has a matrix structure. Next, the agreement (aLij) is computed by the dot-product similarity between a pose pL+1j and a vote v L ij :
aLij = p L+1 j > · vLij . (2)
The pose pL+1j is obtained from the previous iteration of this procedure, and will be set to 0 initially.
Step 2: Computing Poses: The agreement scores aLij are passed through a softmax function to determine the routing probabilities rLij :
rLij = exp(aLij)∑ j′ exp(a L ij′) , (3)
where rLij is an inverted attention score representing how higher-level capsules compete for attention of lower-level capsules. Using the routing probabilities, we update the pose pL+1j for capsule j in layer L + 1 from all capsules in layer L:
pL+1j = LayerNorm (∑ i rLijv L ij ) . (4)
We adopt Layer Normalization (Ba et al., 2016) as the normalization, which we empirically find it to be able to improve the convergence for routing. The routing algorithm is summarized in Procedure 1 and Figure 2.

heading: 4 INFERENCE AND LEARNING

text:
To explain how inference and learning are performed, we use Figure 1 as an example. Note that the choice of the backbone, the number of capsules layers, the number of capsules per layer, the design of the classifier may vary for different sets of experiments. We leave the discussions of configurations in Sections 5 and 6, and in the Appendix.
Procedure 2 Inference. Inference returns class logits given input images and parameters for the model. Capsule layer 1 denotes the primary capsules layer and layer N denotes the class capsules layer.
1: procedure INFERENCE(I;θ,W1:N−1) /* Pre-Capsules Layers: backbone features extraction */ 2: F← backbone(I;θ) . backbone feature /* Capsules Layers: initialization */
3: P1 ← LayerNorm ( convolution(F;θ) ) . primary capsules
4: for L in layers 2 to N : PL ← 0s . non-primary capsules /* Capsules Layers (1st Iteration): sequential routing */ 5: for L in layers 1 to (N − 1) do 6: PL+1 ← Routing (PL, PL+1; WL) . non-primary capsules
/* Capsules Layers (2nd to tth Iteration): concurrent routing */ 7: for (t− 1) iterations do 8: for L in layers 1 to (N − 1): P̄L+1 ← Routing (PL, PL+1; WL) 9: for L in layers 2 to N : PL ← P̄L . non-primary capsules
/* Post-Capsules Layers: classification */ 10: for all capsule i in layer N : ŷi ← classifier(pNi ;θ) . class logits 11: return ŷ

heading: 4.1 INFERENCE

text:
For ease of exposition, we decompose a CapsNet into pre-capsule, capsule and post-capsule layers.
Pre-Capsule Layers: The goal is to obtain a backbone feature F from the input image I. The backbone model can be either a single convolutional layer or ResNet computational blocks (He et al., 2016).
Capsule Layers: The primary capsules P1 are computed by applying a convolution layer and Layer Normalization to the backbone feature F. The non-primary capsules layers P2:N are initialized to be zeros 1. For the first iteration, we perform one step of routing sequentially in each capsule layer. In other words, the primary capsules are used to update their parent convolutional capsules, which are then used to update the next higher-level capsule layer, and so on. After doing this first pass, the rest of the routing iterations are performed concurrently. Specifically, all capsule layers look at their preceding lower-level capsule layer and perform one step of routing simultaneously. This procedure is an example of a parallel-in-time inference method. We call it “concurrent routing” as it concurrently performs routing between capsules layers per iteration, leading to better parallelism. Figure 3 illustrates this procedure from routing iteration 2 to t. It is worth noting that, our proposed variant of CapsNet is a weight-tied concurrent routing architecture with Layer Normalization, which Bai et al. (2019) empirically showed could converge to fixed points.
Previous CapsNets (Sabour et al., 2017; Hinton et al., 2018) used sequential layer-wise iterative routing between the capsules layers. For example, the model first performs routing between layer L − 1 and layer L for a few iterations. Next, the model performs routing between layer L and L + 1 for a few iterations. When unrolled, this sequential iterative routing defines a very deep computational graph with a single path going from the inputs to the outputs. This deep graph could lead to a vanishing gradients problem and limit the depth of a CapsNet that can be trained well, especially if any squashing non-linearities are present. With concurrent routing, the training can be made more stable, since each iteration has a more cumulative effect.
Post-Capsule Layers: The goal is to obtain the predicted class logits ŷ from the last capsule layer (the class capsules) PN . In our CapsNet, we use a linear classifier for class i in class capsules: ŷi = classifier(p N i ). This classifier is shared across all the class capsules.
1 As compared to 0 initialization, we observe that a random initialization leads to similar converged performance but slower convergence speed. We also tried to learn biases for capsules’ initialization, which results in similar converged performance and same convergence speed. As a summary, we initialize the capsule’s value to 0 for simplicity.

heading: 4.2 LEARNING

text: We update the parameters θ,W1:N−1 by stochastic gradient descent. For multiclass classification, we use multiclass cross-entropy loss. For multilabel classification, we use binary cross-entropy loss. We also tried Margin loss and Spread loss which are introduced by prior work (Sabour et al., 2017; Hinton et al., 2018). However, these losses do not give us better performance against cross-entropy and binary cross-entropy losses.

heading: 4.3 COMPARISONS WITH EXISTING CAPSNET MODELS

text:
Having described our model in detail, we can now place the model in the context of previous work. In the following table, we list the major differences among different variants of CapsNets.
Dynamic Routing (Sabour et al., 2017)
EM Routing (Hinton et al., 2018)
Inverted Dot-Product Attention Routing (ours)
Routing sequential iterative routing sequential iterative routing concurrent iterative routing
Poses vector matrix matrix Activations n/a (norm of poses) determined by EM n/a
Non-linearity Squash function n/a n/a Normalization n/a n/a Layer Normalization
Loss Function Margin loss Spread loss Cross Entropy/Binary Cross Entropy

heading: 5 EXPERIMENTS ON CIFAR-10 AND CIFAR-100

text:
CIFAR-10 and CIFAR-100 datasets (Krizhevsky et al., 2009) consist of small 32 × 32 real-world color images with 50, 000 for training and 10, 000 for evaluation. CIFAR-10 has 10 classes, and CIFAR-100 has 100 classes. We choose these natural image datasets to demonstrate our method since they correspond to a more complex data distribution than digit images.
Comparisons with other CapsNets and CNNs: In Table 1, we report the test accuracy obtained by our model, along with other CapsNets and CNNs. Two prior CapsNets are chosen: Dynamic Routing CapsNets (Sabour et al., 2017) and EM Routing CapsNets (Hinton et al., 2018). For each CapsNet, we apply two backbone feature models: simple convolution followed by ReLU nonlinear activation and a ResNet (He et al., 2016) backbone. For CNNs, we consider a baseline CNN with 3 convolutional layers followed by 1 fully-connected classifier layer. ResNet-18 is selected as a representative of SOTA CNNs. See Appendix A.1 for detailed configurations.
First, we compare previous routing approaches against ours. In a general trend, the proposed CapsNets perform better than the Dynamic Routing CapsNets, and the Dynamic Routing CapsNets perform better than EM Routing CapsNets. The performance differs more on CIFAR-100 than on CIFAR-10. For example, with simple convolutional backbone, EM Routing CapsNet can only achieve 37.73% test accuracy while ours can achieve 57.32%. Additionally, for all CapsNets, we see improved performance when replacing a single convolutional backbone with ResNet backbone. This result is not surprising since ResNet structure has better generalizability than a single convolutional layer. For the number of parameters, ours and EM Routing CapsNets have much fewer as compared to Dynamic Routing CapsNets. The reason is due to different structures of capsule’s pose. Ours and EM Routing CapsNets have matrix-structure poses, and Dynamic Routing CapsNets have vector-structure poses. With matrix structure, weights between capsules are only O(d) with d being pose’s dimension; with vector structure, weights are O(d2). To conclude, combining the proposed Inverted Dot-Product Attention Routing with ResNet backbone gives us both the advantages of a low number of parameters and high performance.
Second, we discuss the performance difference between CNNs and CapsNets. We see that, with a simple backbone (a single convolutional layer), it is hard for CapsNets to reach the same performance as CNNs. For instance, our routing approach can only achieve 57.32% test accuracy on CIFAR-100 while the baseline CNN achieves 62.30%. However, with a SOTA backbone structure (ResNet backbone), the proposed routing approach can reach competitive performance (95.14% on CIFAR-10) as compared to the SOTA CNN model (ResNet-18 with 95.11% on CIFAR-10).
Convergence Analysis: In Figure 4, top row, we analyze the convergence for CapsNets with respect to the number of routing iterations. The optimization hyperparameters are chosen optimally for each routing mechanism. For Dynamic Routing CapsNets (Sabour et al., 2017), we observe a mild performance drop when the number of iterations increases. For EM Routing CapsNets (Hinton et al., 2018), the best-performed number of iterations is 2. Increasing or decreasing this number severely hurts the performance. For our proposed routing mechanism, we find a positive correlation between performance and number of routing iterations. The performance variance is also the smallest among
the three routing mechanisms. This result suggests our approach has better optimization and stable inference. However, selecting a larger iteration number may not be ideal since memory usage and inference time will also increase (shown in the bottom right in Figure 4). Note that, we observe sharp performance jitters during training when the model has not converged (especially when the number of iterations is high). This phenomenon is due to applying LayerNorm on a low-dimensional vector. The jittering is reduced when we increase the pose dimension in capsules.
Ablation Study: Furthermore, we inspect our routing approach with the following ablations: 1) Inverted Dot-Product Attention-A: without Layer Normalization; 2) Inverted Dot-Product AttentionB: replacing concurrent to sequential iterative routing; and 3) Inverted Dot-Product Attention-C: adding activations in capsules 2. The results are presented in Figure 4 bottom row. When removing Layer Normalization, performance dramatically drops from our routing mechanism. Notably, the prediction becomes uniform when the iteration number increases to 5. This result implies that the normalization step is crucial to the stability of our method. When replacing concurrent with sequential iterative routing, the positive correlation between performance and iteration number no longer exists. This fact happens in the Dynamic Routing CapsNet as well, which also uses sequential iterative routing. When adding activations to our capsule design, we obtain a performance deterioration. Typically, squashing activations such as sigmoids make it harder for gradients to flow, which might explain this. Discovering the best strategy to incorporate activations in capsule networks is an interesting direction for future work.

heading: 6 EXPERIMENTS ON DIVERSEMULTIMNIST

text:
The goal in this section is to compare CapsNets and CNNs when they have the same number of layers and the same number of neurons per layer. Specifically, we would like to examine the difference of the representation power between the routing mechanism (in CapsNets) and the pooling operation (in CNNs). A challenging setting is considered in which objects may be overlapping with each other, and there may be a diverse number of objects in the image. To this end, we construct the DiverseMultiMNIST dataset which is extended from MNIST (LeCun et al., 1998), and it contains both single-digit and two overlapping digit images. The task will be multilabel classification, where the prediction is said to be correct if and only if the recognized digits match all the digits in the image. We plot the convergence curve when the model is trained on 21M images from DiverseMultiMNIST. Please see Appendix B.2 for more details on the dataset and Appendix B.1 for detailed model configurations. The results are reported in Figure 5.
First, we compare our routing method against the Dynamic routing one. We observe an improved performance from the CapsNet∗ to the CapsNet (83.39% to 85.74% with vector-structured poses). The result suggests a better viewpoint generalization for our routing mechanism.
Second, we compare baseline CNN against our CapsNet. From the table, we see that CapsNet has better test accuracy compared to CNN. For example, the CapsNet with vector-structured poses reaches 85.74% test accuracy, and the baseline CNN reaches 79.81% test accuracy. In our CNN implementation, we use average pooling from the last convolutional layer to its next fully-connected
2We consider the same kind of capsules activations as described in EM Routing CapsNets (Hinton et al., 2018).
layer. We can see that having a routing mechanism works better than pooling. However, one may argue that the pooling operations requires no extra parameter but routing mechanism does, and hence it may not be fair to compare their performance. To address this issue, in the baseline CNN, we replace the pooling operation with a fully-connected operation. To be more precise, instead of using average pooling, we learn the entire transformation matrix from the last convolutional layer to its next fully-connected layer. This procedure can be regarded as considering pooling with learnable parameters. After doing this, the number of parameters in CNN increases to 42.49M , and the corresponding test accuracy is 84.84%, which is still lower than 85.74% from the CapsNet. We conclude that, when recognizing overlapping and diverse number of objects, the routing mechanism has better representation power against the pooling operation.
Last, we compare CapsNet with different pose structures. The CapsNet with vector-structured poses works better than the CapsNet with matrix-structured poses (80.59% vs 85.74%). However, the former requires more parameters, more memory usage, and more inference time. If we increase the number of parameters in the matrix-pose CapsNet to 42M , its test accuracy rises to 91.17%. Nevertheless, the model now requires more memory usage and inference time as compared to using vector-structured poses. We conclude that more performance can be extracted from vector-structured poses but at the cost of high memory usage and inference time.

heading: 7 RELATED WORK

text:
The idea of grouping a set of neurons into a capsule was first proposed in Transforming AutoEncoders (Hinton et al., 2011). The capsule represented the multi-scale recognized fragments of the input images. Given the transformation matrix, Transforming Auto-Encoders learned to discover capsules’ instantiation parameters from an affine-transformed image pair. Sabour et al. (2017) extended this idea to learn part-whole relationships in images systematically. Hinton et al. (2018) cast the routing mechanism as fitting a mixture of Gaussians. The model demonstrated an impressive ability for recognizing objects from novel viewpoints. Recently, Stacked Capsule AutoEncoders (Kosiorek et al., 2019) proposed to segment and compose the image fragments without any supervision. The work achieved SOTA results on unsupervised classification. However, despite showing promising applications by leveraging inherent structures in images, the current literature on capsule networks has only been applied on datasets of limited complexity. Our proposed new routing mechanism instead attempts to apply capsule networks to more complex data.
Our model also relates to Transformers (Vaswani et al., 2017) and Set Transformers (Lee et al., 2019), where dot-product attention is also used. In the language of capsules, a Set Transformer can be seen as a model in which a higher-level unit can choose to pay attention to K lower-level units (using K attention heads). Our model inverts the attention direction (lower-level units “attend” to parents), enforces exclusivity among routing to parents and does not impose any limits on how many lower-level units can be routed to any parent. Therefore, it combines the ease and parallelism of dot-product routing derived from a Transformer, with the interpretability of building a hierarchical parsing of a scene derived from capsule networks.
There are other works presenting different routing mechanisms for capsules. Wang & Liu (2018) formulated the Dynamic routing (Sabour et al., 2017) as an optimization problem consisting of a clustering loss and a KL regularization term. Zhang et al. (2018) generalized the routing method within the framework of weighted kernel density estimation. Li et al. (2018) approximated the routing process with two branches and minimized the distributions between capsules layers by an optimal transport divergence constraint. Phaye et al. (2018) replaced standard convolutional structures before capsules layers by densely connected convolutions. It is worth noting that this work was the first to combine SOTA CNN backbones with capsules layers. Rajasegaran et al. (2019) proposed DeepCaps by stacking 10+ capsules layers. It achieved 92.74% test accuracy on CIFAR-10, which was the previous best for capsule networks. Instead of looking for agreement between capsules layers, Choi et al. (2019) proposed to learn deterministic attention scores only from lower-level capsules. Nevertheless, without agreement, their best-performed model achieved only 88.61% test accuracy on CIFAR-10. In contrast to these prior work, we present a combination of inverted dotproduct attention routing, layer normalization, and concurrent routing. To the best of our knowledge, we are the first to show that capsule networks can achieve comparable performance against SOTA CNNs. In particular, we achieve 95.14% test accuracy for CIFAR-10 and 78.02% for CIFAR-100.

heading: 8 CONCLUSION AND FUTURE WORK

text:
In this work, we propose a novel Inverted Dot-Product Attention Routing algorithm for Capsule networks. Our method directly determines the routing probability by the agreements between parent and child capsules. Routing algorithms from prior work require child capsules to be explained by parent capsules. By removing this constraint, we are able to achieve competitive performance against SOTA CNN architectures on CIFAR-10 and CIFAR-100 with the use of a low number of parameters. We believe that it is no longer impractical to apply capsule networks to datasets with complex data distribution. Two future directions can be extended from this paper:
• In the experiments, we show how capsules layers can be combined with SOTA CNN backbones. The optimal combinations between SOTA CNN structures and capsules layers may be the key to scale up to a much larger dataset such as ImageNet.
• The proposed concurrent routing is as a parallel-in-time and weight-tied inference process. The strong connection with Deep Equilibrium Models (Bai et al., 2019) can potentially lead us to infinite-iteration routing.

text:
A.1 MODEL SPECIFICATIONS
The configuration choices of Dynamic Routing CapsNets and EM Routing CapsNets are followed by prior work (Sabour et al., 2017; Hinton et al., 2018). We empirically find their configurations perform the best for their routing mechanisms (instead of applying our network configurations to their routing mechanisms). The optimizers are chosen to reach the best performance for all models. We list the model specifications in Table 2, 3, 4, 5, 6, 7, 8, and 9.
We only show the specifications for CapsNets with a simple convolutional backbone. When considering a ResNet backbone, two modifications are performed. First, we replace the simple feature backbone with ResNet feature backbone. Then, the input dimension of the weights after the backbone is set as 128. A ResNet backbone contains a 3× 3 convolutional layer (output 64-dim.), three 64-dim. residual building block (He et al., 2016) with stride 1, and four 128-dim. residual building block with stride 2. The ResNet backbone returns a 16× 16× 128 tensor. For the optimizers, we use stochastic gradient descent with learning rate 0.1 for our proposed method, baseline CNN, and ResNet-18 (He et al., 2016). We use Adam (Kingma & Ba, 2014) with learning rate 0.001 for Dynamic Routing CapsNets and Adam with learning rate 0.01 for EM Routing CapsNets. We decrease the learning rate by 10 times when the model trained on 150 epochs and 250 epochs, and there are 350 epochs in total.
A.2 DATA AUGMENTATIONS
We consider the same data augmentation for all networks. During training, we first pad four zerovalue pixels to each image and randomly crop the image to the size 32× 32. Then, we horizontally flip the image with probability 0.5. During evaluation, we do not perform data augmentation. All the model is trained on a 8-GPU machine with batch size 128.

heading: B MODEL CONFIGURATIONS FOR DIVERSE MULTIMNIST

text:
B.1 MODEL SPECIFICATIONS
To fairly compare CNNs and CapsNets, we fix the number of layers and the number of neurons per layer in the models. These models consider the design: 36x36 image→ 18x18x1024 neurons → 8x8x1024 neurons→ 6x6x1024 neurons→ 640 neurons→ 10 class logits. The configurations are presented in Table 10, 11, and 12. We also fix the optimizers across all the models. We use stochastic gradient descent with learning rate 0.1 and decay the learning rate by 10 times when the models trained on 150 steps and 250 steps. One step corresponds to 60, 000 training samples, and we train the models with a total of 350 steps.
B.2 DATASET CONSTRUCTION
Diverse MultiMNIST contains both single-digit and overlapping-digit images. We generate images on the fly and plot the test accuracy for training models over 21M (21M = 350(steps) × 60, 000(images)) generated images. We also generate the test images, and for each evaluation step, there are 10, 000 test images. Note that we make sure the training and the test images are from the disjoint set. In the following, we shall present how we generate the images. We set the probability of generating a single-digit image as 16 and the probability of generating an overlapping-digit image as 56 .
The single-digit image in DiverseMultiMNIST training/ test set is generated by shifting digits in MNIST (LeCun et al., 1998) training/ test set. Each digit is shifted up to 4 pixels in each direction and results in 36× 36 image. Following Sabour et al. (2017), we generate overlapping-digit images in DiverseMultiMNIST training/ test set by overlaying two digits from the same training/ test set of MNIST. Two digits are selected from different classes. Before overlaying the digits, we shift the digits in the same way which we shift for the digit in a single-digit image. After overlapping, the generated image has size 36× 36. We consider no data augmentation for both training and evaluation. All the model is trained on a 8-GPU machine with batch size 128.

title: CAPSULES WITH INVERTED DOT-PRODUCT ATTENTION ROUTING