summaries: This paper evaluates several transductive few-shot learning methods [15,28,20,21,23,17] on class-imbalanced FSL tasks. The class distribution in the query set follows a Dirichlet distribution. The support set is balanced. This work proposes a novel method based on $\alpha$-divergences addressing the imbalance problem. The novel method $\alpha$-TIM achieves competitive performance compared to several recent baselines.

summaries: The paper studies transductive few-shot learning in the more realistic setting with arbitrary class distributions within the query sets. In the proposed setting, authors use Dirichlet distribution to model the marginal probabilities of the classes in the query sets as random variables and generate random samples within the simplex. Focusing on two recent transductive methods PT-MAP and TIM, they first show that class-balance prior is encoded in these two methods and then extend TIM by generalizing mutual-information loss to \alpha divergences to more effectively deal with arbitrary class distributions. The experiments validate proposed \alpha-divergence approach on three standard benchmark datasets (mini-ImageNet, tiered-ImageNet and CUB) and show that the method outperforms inductive and transductive few-shot learning methods in the proposed setting.

summaries: This paper studies transductive evaluation in few-shot learning, which allows the model to use statistics of all the unlabeled query set examples when making class predictions. Models evaluated in transductive fashion typically attain higher metrics by using this extra information. Most work on transductive evaluation, however, assumes that the query set is evenly distributed across the possible classes. This is of course an unrealistic assumption for the real world and this paper specifically studies this aspect: (1) They evaluate in a more realistic transductive evaluation scenario where the class counts within the query set are sampled according to a Dirichlet distribution and show that most transductive evaluation-based methods perform worse in this setup; (2) They propose a modification of an existing model for transductive evaluation to work better in this scenario where the class counts can be varied in the query set.

summaries: The researchers use transductive inference and introduce the effect of arbitrary class distributions within the query sets of few-shot tasks, rather than using class-balanced tasks, by removing the class-balance artefact. They do this by modeling the marginal probabilities of the classes as Dirichlet-distributed random variables, rather than from a known and fixed uniform distribution. They assess their model by comparing transductive methods over 3 datasets, and show their experiment setting’s performance drops compared to inductive methods. They also propose a generalization of the mutual-information loss based on alpha-divergences, which is an extension of the Shannon mutual information and tolerates class-distribution variations more effectively.

abstractText: Transductive inference is widely used in few-shot learning, as it leverages the statistics of the unlabeled query set of a few-shot task, typically yielding substantially better performances than its inductive counterpart. The current few-shot benchmarks use perfectly class-balanced tasks at inference. We argue that such an artificial regularity is unrealistic, as it assumes that the marginal label probability of the testing samples is known and fixed to the uniform distribution. In fact, in realistic scenarios, the unlabeled query sets come with arbitrary and unknown label marginals. We introduce and study the effect of arbitrary class distributions within the query sets of few-shot tasks at inference, removing the class-balance artefact. Specifically, we model the marginal probabilities of the classes as Dirichlet-distributed random variables, which yields a principled and realistic sampling within the simplex. This leverages the current few-shot benchmarks, building testing tasks with arbitrary class distributions. We evaluate experimentally state-of-the-art transductive methods over 3 widely used data sets, and observe, surprisingly, substantial performance drops, even below inductive methods in some cases. Furthermore, we propose a generalization of the mutual-information loss, based on α-divergences, which can handle effectively class-distribution variations. Empirically, we show that our transductive α-divergence optimization outperforms state-of-the-art methods across several data sets, models and few-shot settings. Our code is publicly available at https://github.com/oveilleux/Realistic_Transductive_Few_Shot.

authors:
L. Fei-Fei
R. Fergus
P. Perona

title: One-shot learning of object categories

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 4, pp. 594–611, 2006.

authors:
E. Miller
N. Matsakis
P. Viola

title: Learning from one example through shared densities on transforms

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2000.

authors:
O. Vinyals
C. Blundell
T.P. Lillicrap
K. Kavukcuoglu
D. Wierstra

title: Matching networks for one shot learning

venue: Neural Information Processing Systems (NeurIPS), 2016.

authors:
J. Snell
K. Swersky
R. Zemel

title: Prototypical networks for few-shot learning

venue: Neural Information Processing Systems (NeurIPS), 2017.

authors:
C. Finn
P. Abbeel
S. Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: International Conference on Machine Learning (ICML), 2017.

authors:
S. Ravi
H. Larochelle

title: Optimization as a model for few-shot learning

venue: International Conference on Learning Representations (ICLR), 2017.

authors:
F. Sung
Y. Yang
L. Zhang
T. Xiang
P.H. Torr
T.M. Hospedales

title: Learning to compare: Relation network for few-shot learning

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2018.

authors:
B. Oreshkin
P.R. López
A. Lacoste

title: Tadam: Task dependent adaptive metric for improved few-shot learning

venue: Neural Information Processing Systems (NeurIPS), 2018.

authors:
N. Mishra
M. Rohaninejad
X. Chen
P. Abbeel

title: A simple neural attentive meta-learner

venue: International Conference on Learning Representations (ICLR), 2018.

authors:
A.A. Rusu
D. Rao
J. Sygnowski
O. Vinyals
R. Pascanu
S. Osindero
R. Hadsell

title: Meta-learning with latent embedding optimization

venue: International Conference on Learning Representations (ICLR), 2019.

authors:
L. Yanbin
J. Lee
M. Park
S. Kim
E. Yang
S. Hwang
Y. Yang

title: Learning to propagate labels: Transductive propagation network for few-shot learning

authors:
R. Hou
H. Chang
M. Bingpeng
S. Shan
X. Chen

title: Cross attention network for few-shot classification

venue: Neural Information Processing Systems (NeurIPS), 2019.

authors:
H.-J. Ye
H. Hu
D.-C. Zhan
F. Sha

title: Few-shot learning via embedding adaptation with set-to-set functions

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.

authors:
L. Qiao
Y. Shi
J. Li
Y. Wang
T. Huang
Y. Tian

title: Transductive episodic-wise adaptive metric for few-shot learning

venue: IEEE/CVF International Conference on Computer Vision (ICCV), 2019.

authors:
G.S. Dhillon
P. Chaudhari
A. Ravichandran
S. Soatto

title: A baseline for few-shot image classification

venue: International Conference on Learning Representations (ICLR), 2020.

authors:
S.X. Hu
P.G. Moreno
Y. Xiao
X. Shen
G. Obozinski
N.D. Lawrence
A. Damianou

title: Empirical bayes transductive meta-learning with synthetic gradients

authors:
Y. Wang
C. Xu
C. Liu
L. Zhang
Y. Fu

title: Instance credibility inference for few-shot learning

authors:
Y. Guo
N.-M. Cheung

title: Attentive weights generation for few shot learning via information maximization

authors:
L. Yang
L. Li
Z. Zhang
X. Zhou
E. Zhou
Y. Liu

title: Dpgn: Distribution propagation graph network for few-shot learning

authors:
I.M. Ziko
J. Dolz
E. Granger
I. Ben Ayed

title: Laplacian regularized few-shot learning

venue: International Conference on Machine Learning (ICML), 2020.

authors:
J. Liu
L. Song
Y. Qin

title: Prototype rectification for few-shot learning

venue: European Conference on Computer Vision (ECCV), 2020. 11

authors:
Y. Liu
B. Schiele
Q. Sun

title: An ensemble of epoch-wise empirical bayes for few-shot learning

venue: European Conference on Computer Vision (ECCV), 2020.

authors:
M. Boudiaf
I.M. Ziko
J. Rony
J. Dolz
P. Piantanida
I. Ben Ayed

title: Transductive information maximization for few-shot learning

venue: Neural Information Processing Systems (NeurIPS), 2020.

authors:
J. Bronskill
J. Gordon
J. Requeima
S. Nowozin
R.E. Turner

title: Tasknorm: Rethinking batch normalization for meta-learning

authors:
J. Gordon
J. Bronskill
M. Bauer
S. Nowozin
R. Turner

title: Meta-learning probabilistic inference for prediction

authors:
X. Zhen
H. Sun
Y. Du
J. Xu
Y. Yin
L. Shao
C. Snoek

title: Learning to learn kernels with variational random features

title: An overview of statistical learning theory

venue: IEEE Transactions on Neural Networks (TNN), vol. 10, no. 5, pp. 988–999, 1999.

title: Transductive inference for text classification using support vector machines

venue: International Conference on Machine Learning (ICML), 1999.

authors:
Z. Dengyong
O. Bousquet
T.N. Lal
J. Weston
B. Schölkopf

title: Learning with local and global consistency

venue: Neural Information Processing Systems (NeurIPS), 2004.

authors:
M. Ren
E. Triantafillou
S. Ravi
J. Snell
K. Swersky
J.B. Tenenbaum
H. Larochelle
R.S. Zemel

title: Meta-learning for semi-supervised few-shot classification

authors:
Y. Hu
V. Gripon
S. Pateux

title: Leveraging the feature distribution in transfer-based few-shot learning

authors:
W.-Y. Chen
Y.-C. Liu
Z. Kira
Y.-C.F. Wang
J.-B. Huang

title: A closer look at few-shot classification

authors:
Y. Wang
W.-L. Chao
K.Q. Weinberger
L. van der Maaten

title: Simpleshot: Revisiting nearest-neighbor classification for few-shot learning

authors:
E. Triantafillou
T. Zhu
V. Dumoulin
P. Lamblin
U. Evci
K. Xu
R. Goroshin
C. Gelada
K. Swersky
P.-A. Manzagol

title: Meta-dataset: A dataset of datasets for learning to learn from few examples

authors:
H.B. Lee
H. Lee
D. Na
S. Kim
M. Park
E. Yang
S.J. Hwang

title: Learning to balance: Bayesian meta-learning for imbalanced and out-of-distribution tasks

authors:
X. Chen
H. Dai
Y. Li
X. Gao
L. Song

title: Learning to stop while learning to predict

authors:
M. Ochal
M. Patacchiola
A. Storkey
J. Vazquez
S. Wang

title: Few-shot learning with class imbalance

title: Non-Uniform Random Variate Generation

title: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations

venue: The Annals of Mathematical Statistics, vol. 23, no. 4, pp. 493–507, 1952.

title: α-divergence is unique, belonging to both f -divergence and bregman divergence classes

venue: IEEE Transactions on Information Theory, vol. 55, no. 11, pp. 4925–4931, 2000.

authors:
J. Havrda
F. Charvát

title: Quantification method of classification processes – concept of structural a-entropy

venue: Kybernetika, vol. 3, no. 1, pp. 30–35, 1967.

title: Possible generalization of boltzmann-gibbs statistics

venue: Journal of statistical physics, vol. 52, no. 1, pp. 479–487, 1988.

authors:
A. Cichocki
S.-I. Amari

title: Families of alpha-beta-and gamma-divergences: Flexible and robust measures of similarities

title: Information measures and capacity of order α for discrete memoryless channels

venue: Topics in information theory, 1977.

authors:
O. Russakovsky
J. Deng
H. Su
J. Krause
S. Satheesh
S. Ma
Z. Huang
A. Karpathy
A. Khosla
M. Bernstein
A.C. Berg
L. Fei-Fei

title: ImageNet Large Scale Visual Recognition Challenge

venue: International Journal of Computer Vision (IJCV), vol. 115, no. 3, pp. 211–252, 2015.

authors:
C. Wah
S. Branson
P. Welinder
P. Perona
S. Belongie

title: The caltech-ucsd birds-200-2011 dataset

authors:
C. Zhang
Y. Cai
G. Lin
C. Shen

title: Deepemd: Few-shot image classification with differentiable earth mover’s distance and structured classifiers

venue: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR), 2020.

authors:
C. Finn
K. Xu
S. Levine

title: Probabilistic model-agnostic meta-learning

venue: Advances in Neural Information Processing Systems (NeurIPS), 2018.

authors:
C. Burns
J. Steinhardt

title: Limitations of post-hoc feature alignment for robustness

venue: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021. 13

heading: 1 Introduction

text:
Deep learning models are widely dominating the field. However, their outstanding performances are often built upon training on large-scale labeled data sets, and the models are seriously challenged when dealing with novel classes that were not seen during training. Few-shot learning [1, 2, 3] tackles this challenge, and has recently triggered substantial interest within the community. In standard few-shot settings, a model is initially trained on large-scale data containing labeled examples from a set of base classes. Then, supervision for a new set of classes, which are different from those seen in the base training, is restricted to just one or a few labeled samples per class. Model generalization is evaluated over few-shot tasks. Each task includes a query set containing unlabeled samples for evaluation, and is supervised by a support set containing a few labeled samples per new class.
The recent few-shot classification literature is abundant and widely dominated by convoluted metalearning and episodic-training strategies. To simulate generalization challenges at test times, such strategies build sequences of artificially balanced few-shot tasks (or episodes) during base training, each containing both query and support samples. Widely adopted methods within this paradigm include: Prototypical networks [4], which optimizes the log-posteriors of the query points within each base-training episode; Matching networks [3], which expresses the predictions of query points ∗Equal contributions, corresponding authors: {olivier.veilleux.2, malik.boudiaf.1}@ens.etsmtl.ca
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
as linear functions of the support labels, while deploying episodic training and memory architectures; MAML (Model-Agnostic Meta-Learning) [5], which encourages a model to be “easy” to fine-tune; and the meta-learner in [6], which prescribes optimization as a model for few-shot learning. These popular methods have recently triggered a large body of few-shot learning literature, for instance, [7, 8, 9, 10, 11, 12, 13], to list a few.
Recently, a large body of works investigated transductive inference for few-shot tasks, e.g., [11, 14, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23], among many others, showing substantial improvements in performances over inductive inference2. Also, as discussed in [24], most meta-learning approches rely critically on transductive batch normalization (TBN) to achieve competitive performances, for instance, the methods in [5, 25, 26], among others. Adopted initially in the widely used MAML [5], TBN performs normalization using the statistics of the query set of a given few-shot task, and yields significant increases in performances [24]. Therefore, due to the popularity of MAML, several meta-learning techniques have used TBN. The transductive setting is appealing for few-shot learning, and the outstanding performances observed recently resonate well with a well-known fact in classical transductive inference [27, 28, 29]: On small labeled data sets, transductive inference outperforms its inductive counterpart. In few-shot learning, transductive inference has access to exactly the same training and testing data as its inductive counterpart3. The difference is that it classifies all the unlabeled query samples of each single few-shot task jointly, rather than one sample at a time.
The current few-shot benchmarks use perfectly class-balanced tasks at inference: For each task used at testing, all the classes have exactly the same number of samples, i.e., the marginal probability of the classes is assumed to be known and fixed to the uniform distribution across all tasks. This may not reflect realistic scenarios, in which testing tasks might come with arbitrary class proportions. For instance, the unlabeled query set of a task could be highly imbalanced. In fact, using perfectly balanced query sets for benchmarking the models assumes exact knowledge of the marginal distributions of the true labels of the testing points, but such labels are unknown. This is, undeniably, an unrealistic assumption and an important limitation of the current few-shot classification benchmarks and datasets. Furthermore, this suggests that the recent progress in performances might be, in part, due to class-balancing priors (or biases) that are encoded in state-of-the-art transductive models. Such priors might be implicit, e.g., through carefully designed episodic-training schemes and specialized architectures, or explicit, e.g., in the design of transductive loss functions and constraints. For instance, the best performing methods in [23, 31] use explicit label-marginal terms or constraints, which strongly enforce perfect class balance within the query set of each task. In practice, those class-balance priors and assumptions may limit the applicability of the existing few-shot benchmarks and methods. In fact, our experiments show that, over few-shot tasks with random class balance, the performances of state-of-the-art methods may decrease by margins. This motivates re-considering the existing benchmarks and re-thinking the relevance of class-balance biases in state-of-the-art methods.
Contributions We introduce and study the effect of arbitrary class distributions within the query sets of few-shot tasks at inference. Specifically, we relax the assumption of perfectly balanced query sets and model the marginal probabilities of the classes as Dirichlet-distributed random variables. We devise a principled procedure for sampling simplex vectors from the Dirichlet distribution, which is widely used in Bayesian statistics for modeling categorical events. This leverages the current few-shot benchmarks by generating testing tasks with arbitrary class distributions, thereby reflecting realistic scenarios. We evaluate experimentally state-of-the-art transductive few-shot methods over 3 widely used datasets, and observe that the performances decrease by important margins, albeit at various degrees, when dealing with arbitrary class distributions. In some cases, the performances drop even below the inductive baselines, which are not affected by class-distribution variations (as they do not use the query-set statistics). Furthermore, we propose a generalization of the transductive mutualinformation loss, based on α-divergences, which can handle effectively class-distribution variations. Empirically, we show that our transductive α-divergence optimization outperforms state-of-the-art few-shot methods across different data sets, models and few-shot settings.
2The best-performing state-of-the-art few-shot methods in the transductive-inference setting have achieved performances that are up to 10% higher than their inductive counterparts; see [23], for instance.
3Each single few-shot task is treated independently of the other tasks in the transductive-inference setting. Hence, the setting does not use additional unlabeled data, unlike semi-supervised few-shot learning [30].

heading: 2 Standard few-shot settings

text:
Base training Assume that we have access to a fully labelled base dataset Dbase = {xi,yi}Nbasei=1 , where xi ∈ Xbase are data points in an input space Xbase, yi ∈ {0, 1}|Ybase| the one-hot labels, and Ybase the set of base classes. Base training learns a feature extractor fφ : X → Z , withφ its learnable parameters and Z a (lower-dimensional) feature space. The vast majority of the literature adopts episodic training at this stage, which consists in formatting Dbase as a series of tasks (=episodes) in order to mimic the testing stage, and train a meta-learner to produce, through a differentiable process, predictions for the query set. However, it has been repeatedly demonstrated over the last couple years that a standard supervised training followed by standard transfer learning strategies actually outperforms most meta-learning based approaches [32, 33, 34, 20, 23]. Therefore, we adopt a standard cross-entropy training in this work.
Testing The model is evaluated on a set of few-shot tasks, each formed with samples from Dtest = {xi,yi}Ntesti=1 , where yi ∈ {0, 1}|Ytest| such that Ybase ∩ Ytest = ∅. Each task is composed of a labelled support set S = {xi, yi}i∈IS and an unlabelled query setQ = {xi}i∈IQ , both containing instances only from K distinct classes randomly sampled from Ytest, with K < |Ytest|. Leveraging a feature extractor fφ pre-trained on the base data, the objective is to learn, for each few-shot task, a classifier fW : Z → ∆K , withW the learnable parameters and ∆K = {y ∈ [0, 1]K / ∑ k yk = 1} the (K − 1)-simplex. To simplify the equations for the rest of the paper, we use the following notations for the posterior predictions of each i ∈ IS ∪ IQ and for the class marginals within Q:
pik = fW (fφ(xi))k = P(Y = k|X = xi;W ,φ) and p̂k = 1 |IQ| ∑ i∈IQ pik = P(YQ = k;W ,φ),
where X and Y are the random variables associated with the raw features and labels, respectively; XQ and YQ means restriction of the random variable to setQ. The end goal is to predict the classes of the unlabeled samples in Q for each few-shot task, independently of the other tasks. A large body of works followed a transductive-prediction setting, e.g., [11, 14, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23], among many others. Transductive inference performs a joint prediction for all the unlabeled query samples of each single few-shot task, thereby leveraging the query-set statistics. On the current benchmarks, tranductive inference often outperforms substantially its inductive counterpart (i.e., classifying one sample at a time for a given task). Note that our method is agnostic to the specific choice of classifierfW , whose parameters are learned at inference. In the experimental evaluations of our method, similarly to [23], we used pik ∝ exp(− τ2 ‖wk − zi‖ 2 ), with W := (w1, . . . ,wK), zi = fφ(xi) ‖fφ(xi)‖2 , τ is a temperature parameter and base-training parameters φ are fixed4.
Perfectly balanced vs imbalanced tasks In standard K-way few-shot settings, the support and query sets of each task T are formed using the following procedure: (i) Randomly sample K classes YT ⊂ Ytest; (ii) For each class k ∈ YT , randomly sample nSk support examples, such that nSk = |S|/K; and (iii) For each class k ∈ YT , randomly sample n Q k query examples, such that nQk = |Q|/K. Such a setting is undeniably artificial as we assume S and Q have the same perfectly balanced class distribution. Several recent works [35, 36, 37, 38] studied class imbalance exclusively on the support set S. This makes sense as, in realistic scenarios, some classes might have more labelled samples than others. However, even these works rely on the assumption that query set Q is perfectly balanced. We argue that such an assumption is not realistic, as one typically has even less control over the class distribution of Q than it has over that of S . For the labeled support S , the class distribution is at least fully known and standard strategies from imbalanced supervised learning could be applied [38]. This does not hold forQ, for which we need to make class predictions at testing time and whose class distribution is unknown. In fact, generating perfectly balanced tasks at test times for benchmarking the models assumes that one has access to the unknown class distributions of the query points, which requires access to their unknown labels. More importantly, artificial balancing of Q is implicitly or explicitly encoded in several transductive methods, which use the query set statistics to make class predictions, as will be discussed in section 4.
4φ is either fixed, e.g., [23], or fine-tuned during inference, e.g., [15]. There is, however, evidence in the literature that freezing φ yields better performances [23, 32, 34, 33], while reducing the inference time.

heading: 3 Dirichlet-distributed class marginals for few-shot query sets

text:
Standard few-shot settings assume that pk, the proportion of the query samples belonging to a class k within a few-shot task, is deterministic (fixed) and known priori: pk = nQk /|Q| = 1/K, for all k and all few-shot tasks. We propose to relax this unrealistic assumption, and to use the Dirichlet distribution to model the proportions (or marginal probabilities) of the classes in few-shot query sets as random variables. Dirichlet distributions are widely used in Bayesian statistics to model K-way categorical events5. The domain of the Dirichlet distribution is the set of K-dimensional discrete distributions, i.e., the set of vectors in (K − 1)-simplex ∆K = {p ∈ [0, 1]K | ∑ k pk = 1}. Let Pk denotes a random variable associated with class probability pk, and P the random simplex vector given by P = (P1, . . . , PK). We assume that P follows a Dirichlet distribution with parameter vector a = (a1, . . . , aK) ∈ RK : P ∼ Dir(a). The Dirichlet distribution has the following density function: fDir(p;a) = 1 B(a) ∏K k=1 p ak−1 k for p = (p1, . . . , pK) ∈ ∆K , with B denoting the multivariate Beta
function, which could be expressed with the Gamma function6: B(a) = ∏K k=1 Γ(ak)
Γ( ∑K k=1 αk) .
Figure 1 illustrates the Dirichlet density for K = 3, with a 2-simplex support represented with an equilateral triangle, whose vertices are probability vectors (1, 0, 0), (0, 1, 0) and (0, 0, 1). We show the density for a = a1K , with 1K the K-dimensional vector whose all components are equal to 1 and concentration parameter a equal to 0.5, 2, 5 and 50. Note that the limiting case a → +∞ corresponds to the standard settings with perfectly balanced tasks, where only uniform distribution, i.e., the point in the middle of the simplex, could occur as marginal distribution of the classes.
The following result, well-known in the literature of random variate generation [39], suggests that one could generate samples from the multivariate Dirichlet distribution via simple and standard univariate Gamma generators.
Theorem 3.1. ([39, p. 594]) Let N1, . . . , NK be K independent Gamma-distributed random variables with parameters ak: Nk ∼ Gamma(ak), i.e., the probability density ofNk is univariate Gamma7, with shape parameter ak. Let Pk = Nk∑K
k=1Nk , k = 1, . . . ,K. Then, P = (P1, . . . , PK) is Dirichlet
distributed: P ∼ Dir(a), with a = (a1, . . . , aK).
A proof based on the Jacobian of random-variable transformations Pk = Nk∑K k=1Nk
, k = 1, . . . ,K, could be found in [39], p. 594. This result prescribes the following simple procedure for sampling random simplex vectors (p1, . . . , pK) from the multivariate Dirichlet distribution with parameters a = (a1, . . . , aK): First, we draw K independent random samples (n1, . . . , nK) from Gamma distributions, with each nk drawn from univariate density fGamma(n; ak); To do so, one could use standard random generators for the univariate Gamma density; see Chapter 9 in [39]. Then, we set pk =
nk∑K k=1 nk . This enables to generate randomly nQk , the number of samples of class k within query
set Q, as follows: nQk is the closest integer to pk|Q| such that ∑ k n Q k = |Q|.
5Note that the Dirichlet distribution is the conjugate prior of the categorical and multinomial distributions. 6The Gamma function is given by: Γ(a) = ∫∞ 0 ta−1 exp(−t)dt for a > 0. Note that Γ(a) = (a − 1)!
when a is a strictly positive integer. 7Univariate Gamma density is given by: fGamma(n; ak) = n
ak−1 exp(−n) Γ(ak) , n ∈ R.

heading: 4 On the class-balance bias of the best-performing few-shot methods

text:
As briefly evoked in section 2, the strict balancing of the classes in both S and Q represents a strong inductive bias, which few-shot methods can either meta-learn during training or leverage at inference. In this section, we explicitly show how such a class-balance prior is encoded in the two best-performing transductive methods in the literature [23, 31], one based on mutual-information maximization [23] and the other on optimal transport [31].
Class-balance bias of optimal transport Recently, the transductive method in [31], referred to as PT-MAP, achieved the best performances reported in the literature on several popular benchmarks, to the best of our knowledge. However, the method explicitly embeds a class-balance prior. Formally, the objective is to find, for each few-shot task, an optimal mapping matrix M ∈ R|Q|×K+ , which could be viewed as a joint probability distribution over XQ × YQ. At inference, a hard constraint M ∈ {M : M1K = r,1|Q|M = c} for some r and c is enforced through the use of the Sinkhorn-Knopp algorithm. In other words, the columns and rows of M are constrained to sum to pre-defined vectors r ∈ R|Q| and c ∈ RK . Setting c = 1K1K as done in [31] ensures that M defines a valid joint distribution, but also crucially encodes the strong prior that all the classes within the query sets are equally likely. Such a hard constraint is detrimental to the performance in more realistic scenarios where the class distributions of the query sets could be arbitrary, and not necessarily uniform. Unsurprisingly, PT-MAP undergoes a substantial performance drop in the realistic scenario with Dirichlet-distributed class proportions, with a consistent decrease in accuracy between 18 and 20 % on all benchmarks, in the 5-ways case.
Class-balance bias of transductive mutual-information maximization Let us now have a closer look at the mutual-information maximization in [23]. Following the notations introduced in section 2, the transductive loss minimized in [23] for a given few-shot task reads:
LTIM = CE− I(XQ;YQ) = CE− 1 |IQ| ∑ i∈Q K∑ k=1
pik log(pik)︸ ︷︷ ︸ H(YQ|XQ) +λ
K∑ k=1
p̂k log p̂k︸ ︷︷ ︸ −H(YQ) , (1)
where I(XQ;YQ) = −H(YQ|XQ) + λH(YQ) is a weighted mutual information between the query samples and their unknown labels (the mutual information corresponds to λ = 1), and CE := − 1|IS | ∑ i∈S ∑K k=1 yik log(pik) is a supervised cross-entropy term defined over the support samples. Let us now focus our attention on the label-marginal entropy term,H(YQ). As mentioned in [23], this term is of significant importance as it prevents trivial, single-class solutions stemming from minimizing only conditional entropyH(YQ|XQ). However, we argue that this term also encourages class-balanced solutions. In fact, we can write it as an explicit KL divergence, which penalizes deviation of the label marginals within a query set from the uniform distribution:
H(YQ) = − K∑ k=1 p̂k log (p̂k) = log(K)−DKL(p̂‖uK). (2)
Therefore, minimizing marginal entropy H(YQ) is equivalent to minimizing the KL divergence between the predicted marginal distribution p̂ = (p̂1, . . . , p̂K) and uniform distribution uK = 1K1K . This KL penalty could harm the performances whenever the class distribution of the few-shot task is no longer uniform. In line with this analysis, and unsurprisingly, we observe in section 6 that the original model in [23] also undergoes a dramatic performance drop, up to 20%. While naively removing this marginal-entropy term leads to even worse performances, we observe that simply down-weighting it, i.e., decreasing λ in Eq. (1), can drastically alleviate the problem, in contrast to the case of optimal transport where the class-balance constraint is enforced in a hard manner.

heading: 5 Generalizing mutual information with α-divergences

text:
In this section, we propose a non-trivial, but simple generalization of the mutual-information loss in (1), based on α-divergences, which can tolerate more effectively class-distribution variations. We identified in section 4 a class-balance bias encoded in the marginal Shannon entropy term. Ideally,
we would like to extend this Shannon-entropy term in a way that allows for more flexibility: Our purpose is to control how far the predicted label-marginal distribution, p̂, could depart from the uniform distribution without being heavily penalized.

heading: 5.1 Background

text:
We argue that such a flexibility could be controlled through the use of α-divergences [40, 41, 42, 43, 44], which generalize the well-known and widely used KL divergence. α-divergences form a whole family of divergences, which encompasses Tsallis and Renyi α-divergences, among others. In this work, we focus on Tsallis’s [40, 43] formulation of α-divergence. Let us first introduce the generalized logarithm [44]: logα(x) = 1 1−α ( x1−α − 1 ) . Using the latter, Tsallis α-divergence naturally extends KL. For two discrete distributions p = (pk)Kk=1 and q = (qk) K k=1, we have:
Dα(p‖q) = − K∑ k=1 pk logα ( qk pk ) = 1 1− α ( 1− K∑ k=1 pαk q 1−α k ) . (3)
Note that the Shannon entropy in Eq. (2) elegantly generalizes to Tsallis α-entropy:
Hα(p) = logα(K)−K1−α Dα(p‖uK) = 1
α− 1
( 1−
∑ k pαk
) . (4)
The derivation of Eq. (4) is provided in appendix. Also, limα→1 logα(x) = log(x), which implies:
lim α→1 Dα(p‖q) = DKL(p‖q) and lim α→1 Hα(p) = H(p) = − K∑ k=1 p̂k log (p̂k) .
Note that α-divergence Dα(p‖q) inherits the nice properties of the KL divergence, including but not limited to convexity with respect to both p and q and strict positivity Dα(p‖q) ≥ 0 with equality if p = q. Furthermore, beyond its link to the forward KL divergenceDKL(p‖q), α-divergence smoothly connects several well-known divergences, including the reverse KL divergence DKL(q‖p) (α→ 0), the Hellinger (α = 0.5) and the Pearson Chi-square (α = 2) distances [44].

heading: 5.2 Analysis of the gradients

text: As observed from Eq. (4), α-entropy is, just like Shannon Entropy, intrinsically biased toward the uniform distribution. Therefore, we still have not properly answered the question: why would α-entropy be better suited to imbalanced situations? We argue the that learning dynamics subtly but crucially differ. To illustrate this point, let us consider a simple toy logistic-regression example. Let l ∈ R denotes a logit, and p = σ(l) the corresponding probability, where σ stands for the usual sigmoid function. The resulting probability distribution simply reads p = {p, 1− p}. In Figure 2, we plot both the α-entropyHα (left) and its gradients ∂Hα/∂l (right) as functions of p. The advantage of α-divergence now becomes clearer: as α increases,Hα(p) accepts more and more deviation from the uniform distribution (p = 0.5 on Figure 2), while still providing a barrier preventing trivial solutions (i.e., p = 0 or p = 1, which corresponds to all the samples predicted as 0 or 1). Intuitively, such a behavior makes α-entropy with α > 1 better suited to class imbalance than Shannon entropy.

heading: 5.3 Proposed formulation

text:
In light of the previous discussions, we advocate a new α-mutual information loss, a simple but very effective extension of the Shannon mutual information in Eq. (1):
Iα(XQ;YQ) = Hα(YQ)−Hα(YQ|XQ) = 1
α− 1  1 |IQ| ∑ i∈IQ K∑ k=1 pαik − K∑ k=1 p̂ αk  (5) withHα the α-entropy as defined in Eq. (4). Note that our generalization in Eq. (5) has no link to the α-mutual information derived in [45]. Finally, our loss for transductive few-shot inference reads:
Lα-TIM = CE− Iα(XQ;YQ). (6)

heading: 6 Experiments

text:
In this section, we thoroughly evaluate the most recent few-shot transductive methods using our imbalanced setting. Except for SIB [16] and LR-ICI [17] all the methods have been reproduced in our common framework. All the experiments have been executed on a single GTX 1080 Ti GPU.
Datasets We use three standard benchmarks for few-shot classification: mini-Imagenet [46], tieredImagenet [30] and Caltech-UCSD Birds 200 (CUB) [47]. The mini-Imagenet benchmark is a subset of the ILSVRC-12 dataset [46], composed of 60,000 color images of size 84 x 84 pixels [3]. It includes 100 classes, each having 600 images. In all experiments, we used the standard split of 64 base-training, 16 validation and 20 test classes [6, 33]. The tiered-Imagenet benchmark is a larger subset of ILSVRC-12, with 608 classes and 779,165 color images of size 84× 84 pixels. We used a standard split of 351 base-training, 97 validation and 160 test classes. The Caltech-UCSD Birds 200 (CUB) benchmark also contains images of size 84× 84 pixels, with 200 classes. For CUB, we used a standard split of 100 base-training, 50 validation and 50 test classes, as in [32]. It is important to note that for all the splits and data-sets, the base-training, validation and test classes are all different.
Task sampling We evaluate all the methods in the 1-shot 5-way, 5-shot 5-way, 10-shot 5-way and 20-shot 5-way scenarios, with the classes of the query sets randomly distributed following Dirichlet’s distribution, as described in section 3. Note that the total amount of query samples |Q| remains fixed to 75. All the methods are evaluated by the average accuracy over 10,000 tasks, following [33]. We used different Dirichlet’s concentration parameter a for validation and testing. The validation-task generation is based on a random sampling within the simplex (i.e Dirichlet with a = 1K). Testingtask generation uses a = 2 ·1K to reflect the fact that extremely imbalanced tasks (i.e., only one class is present in the task) are unlikely to happen in practical scenarios; see Figure 1 for visualization.
Hyper-parameters Unless identified as directly linked to a class-balance bias, all the hyperparameters are kept similar to the ones prescribed in the original papers of the reproduced methods. For instance, the marginal entropy in TIM [23] was identified in section 4 as a penalty that encourages class balance. Therefore, the weight controlling the relative importance of this term is tuned. For all methods, hyper-parameter tuning is performed on the validation set of each dataset, using the validation sampling described in the previous paragraph.
Base-training procedure All non-episodic methods use the same feature extractors, which are trained using the same procedure as in [23, 20], via a standard cross-entropy minimization on the base classes with label smoothing. The feature extractors are trained for 90 epochs, using a learning rate initialized to 0.1 and divided by 10 at epochs 45 and 66. We use a batch size of 256 for ResNet-18 and of 128 for WRN28-10. During training, color jitter, random croping and random horizontal flipping augmentations are applied. For episodic/meta-learning methods, given that each requires a specific training, we use the pre-trained models provided with the GitHub repository of each method.

heading: 6.1 Main results

text:
The main results are reported in Table 1. As baselines, we also report the performances of state-ofthe-art inductive methods that do not use the statistics of the query set at adaptation and are, therefore,
unaffected by class imbalance. In the 1-shot scenario, all the transductive methods, without exception, undergo a significant drop in performances as compared to the balanced setting. Even though the best-performing transductive methods still outperforms the inductive ones, we observe that more than half of the transductive methods evaluated perform overall worse than inductive baselines in our realistic setting. Such a surprising finding highlights that the standard benchmarks, initially developed for the inductive setting, are not well suited to evaluate transductive methods. In particular, when evaluated with our protocol, the current state-of-the-art holder PT-MAP averages more than 18% performance drop across datasets and backbones, Entropy-Min around 7%, and TIM around 4%. Our proposed α-TIM method outperforms transductive methods across almost all task formats, datasets and backbones, and is the only method that consistently inductive baselines in fair setting. While stronger inductive baselines have been proposed in the literature [48], we show in the supplementary material that α-TIM keeps a consistent relative improvement when evaluated under the same setting.

heading: 6.2 Ablation studies

text:
In-depth comparison of TIM and α-TIM While not included in the main Table 1, keeping the same hyper-parameters for TIM as prescribed in the original paper [23] would result in a drastic drop of about 18% across the benchmarks. As briefly mentioned in section 4 and implemented for tuning [23] in Table 1, adjusting marginal-entropy weight λ in Eq. (1) strongly helps in imbalanced scenarios, reducing the drop from 18% to only 4%. However, we argue that such a strategy is sub-optimal in comparison to using α-divergences, where the only hyper-parameter controlling the flexibility of the marginal-distribution term becomes α. First, as seen from Table 1, our α-TIM achieves consistently better performances with the same budget of hyper-parameter optimization as the standard TIM. In fact, in higher-shots scenarios (5 or higher), the performances of α-TIM are substantially better that the standard mutual information (i.e. TIM). Even more crucially, we show in Figure 3 that α-TIM does not fail drastically when α is chosen sub-optimally, as opposed to the case of weighting parameter λ for the TIM formulation. We argue that such a robustness makes of α-divergences a particularly interesting choice for more practical applications, where such a tuning might be intractable. Our results points to the high potential of α-divergences as loss functions for leveraging unlabelled data, beyond the few-shot scenario, e.g., in semi-supervised or unsupervised domain adaptation problems.
Varying imbalance severity While our main experiments used a fixed value a = 2·1K , we wonder whether our conclusions generalize to different levels of imbalance. Controlling for Dirichlet’s parameter a naturally allows us to vary the imbalance severity. In Figure 4, we display the results obtained by varying a, while keeping the same hyper-parameters obtained through our validation protocol. Generally, most methods follow the expected trend: as a decreases and tasks become more severely imbalanced, performances decrease, with sharpest losses for TIM [23] and PT-MAP [31]. In fact, past a certain imbalance severity, the inductive baseline in [33] becomes more competitive than
most transductive methods. Interestingly, both LaplacianShot [20] and our proposed α-TIM are able to cope with extreme imbalance, while still conserving good performances on balanced tasks.
On the use of transductive BN In the case of imbalanced query sets, we note that transductive batch normalization (e.g as done in the popular MAML [49]) hurts the performances. This aligns with recent observations from the concurrent work in [50], where a shift in the marginal label distribution is clearly identified as a failure case of statistic alignment via batch normalization.
Conclusion
We make the unfortunate observation that recent transductive few-shot methods claiming large gains over inductive ones may perform worse when evaluated with our realistic setting. The artificial balance of the query sets in the vanilla setting makes it easy for transductive methods to implicitly encode this strong prior at meta-training stage, or even explicitly at inference. When rendering such a property obsolete at test-time, the current top-performing method becomes noncompetitive, and all the transductive methods undergo performance drops. Future works could study the mixed effect of imbalance on both support and query sets. We hope that our observations encourage the community to rethink the current transductive literature, and build upon our work to provide fairer grounds of comparison between inductive and transductive methods.

heading: Acknowledgments

text: This project was supported by the Natural Sciences and Engineering Research Council of Canada (Discovery Grant RGPIN 2019-05954). This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement №792464.

title: Realistic Evaluation of Transductive Few-Shot Learning


summaries: Instead of the conventional layer-by-layer execution, this paper proposes a patch-by-patch scheduler to reduce the peak memory required by a CNN for inference on MCU. The author also proposes a network redistribution method, which finetunes the network architecture (CONV kernel size), to mitigate the computation overhead caused by their patch-by-patch execution. The results show that, with a certain computation overhead, the proposed methods can effectively reduce the inference peak memory while not losing accuracy.

summaries: Working memory utilization for most CNN based models typically is more than what can be afforded on Tiny devices. Thus, it is often quite difficult to extract reasonable performance for visual tasks on tiny devices.  Authors attack this problem by a) introducing a patch based inference method that improves peak memory utilization at the cost of compute and b) introducing a redistribution process that reduces the overall compute while maintaining/improving performance.

summaries: This paper addresses the problem of large activations that quickly arises in devices with little memory, such as MCUs, when deploying larger networks. The main contribution proposes a relatively simple but effective approach to reducing the memory footprint of activations (by a large 4x-8x factor) while introducing some unavoidable extra compute (resulting in up to 15% MACs, which translate into  up to ~1.27x higher latency). The impact in terms of compute overhead of the proposed per-patch processing is alleviated by redistributing the receptive filed. Which means: reducing the filter WxH in early layers and use striding>1; then stack more blocks in deeper parts of the network where the memory peak of activations is not so high anymore. A NAS-based mechanism is introduced to jointly discover architectures and receptive filed redistribution strategies.

summaries: The main problem the paper tries to tackle is reducing the peak memory footprint of the neural networks by deviating from the usual layer-by-layer execution. The main intuition seems to be very similar to tiling combined with layer fusion-like ideas. However, the main spark of the paper seems to be leveraging this dimension in the context of Neural Architecture Search, which seems to be novel.

abstractText: Tiny deep learning on microcontroller units (MCUs) is challenging due to the limited memory size. We find that the memory bottleneck is due to the imbalanced memory distribution in convolutional neural network (CNN) designs: the first several blocks have an order of magnitude larger memory usage than the rest of the network. To alleviate this issue, we propose a generic patch-by-patch inference scheduling, which operates only on a small spatial region of the feature map and significantly cuts down the peak memory. However, naive implementation brings overlapping patches and computation overhead. We further propose receptive field redistribution to shift the receptive field and FLOPs to the later stage and reduce the computation overhead. Manually redistributing the receptive field is difficult. We automate the process with neural architecture search to jointly optimize the neural architecture and inference scheduling, leading to MCUNetV2. Patch-based inference effectively reduces the peak memory usage of existing networks by 4-8×. Co-designed with neural networks, MCUNetV2 sets a record ImageNet accuracy on MCU (71.8%), and achieves >90% accuracy on the visual wake words dataset under only 32kB SRAM. MCUNetV2 also unblocks object detection on tiny devices, achieving 16.9% higher mAP on Pascal VOC compared to the stateof-the-art result. Our study largely addressed the memory bottleneck in tinyML and paved the way for various vision applications beyond image classification.

authors:
Martín Abadi
Paul Barham
Jianmin Chen
Zhifeng Chen
Andy Davis
Jeffrey Dean
Matthieu Devin
Sanjay Ghemawat
Geoffrey Irving
Michael Isard

title: Tensorflow: A system for large-scale machine learning

authors:
Byung Hoon Ahn
Jinwon Lee
Jamie Menjay Lin
Hsin-Pai Cheng
Jilei Hou
Hadi Esmaeilzadeh

title: Ordering chaos: Memory-aware scheduling of irregularly wired neural networks for edge devices

authors:
Manoj Alwani
Han Chen
Michael Ferdman
Peter Milder

title: Fused-layer cnn accelerators

venue: In 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO),

authors:
Colby Banbury
Chuteng Zhou
Igor Fedorov
Ramon Matas
Urmish Thakker
Dibakar Gope
Vijay Janapa Reddi
Matthew Mattina
Paul Whatmough

title: Micronets: Neural network architectures for deploying tinyml applications on commodity microcontrollers

venue: Proceedings of Machine Learning and Systems,

authors:
Han Cai
Chuang Gan
Tianzhe Wang
Zhekai Zhang
Song Han

title: Once for All: Train One Network and Specialize it for Efficient Deployment

venue: In ICLR,

authors:
Han Cai
Ligeng Zhu
Song Han

title: ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware

authors:
Alessandro Capotondi
Manuele Rusci
Marco Fariselli
Luca Benini

title: Cmix-nn: Mixed low-precision cnn library for memory-constrained edge devices

venue: IEEE Transactions on Circuits and Systems II: Express Briefs,

authors:
Tianqi Chen
Thierry Moreau
Ziheng Jiang
Lianmin Zheng
Eddie Yan
Haichen Shen
Meghan Cowan
Leyuan Wang
Yuwei Hu
Luis Ceze

title: TVM}: An automated end-to-end optimizing compiler for deep learning

authors:
Jungwook Choi
Zhuo Wang
Swagath Venkataramani
Pierce I-Jen Chuang
Vijayalakshmi Srinivasan
Kailash Gopalakrishnan

title: Pact: Parameterized clipping activation for quantized neural networks

venue: arXiv preprint arXiv:1805.06085,

authors:
Aakanksha Chowdhery
Pete Warden
Jonathon Shlens
Andrew Howard
Rocky Rhodes

title: Visual wake words dataset

venue: arXiv preprint arXiv:1906.05721,

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:
Alexey Dosovitskiy
Lucas Beyer
Alexander Kolesnikov
Dirk Weissenborn
Xiaohua Zhai
Thomas Unterthiner
Mostafa Dehghani
Matthias Minderer
Georg Heigold
Sylvain Gelly

title: An image is worth 16x16 words: Transformers for image recognition at scale

venue: arXiv preprint arXiv:2010.11929,

authors:
Mark Everingham
Luc Van Gool
Christopher KI Williams
John Winn
Andrew Zisserman

title: The pascal visual object classes (voc) challenge

venue: International journal of computer vision,

authors:
Igor Fedorov
Ryan P Adams
Matthew Mattina
Paul Whatmough

title: Sparse: Sparse architecture search for cnns on resource-constrained microcontrollers

venue: NeurIPS,

authors:
Koen Goetschalckx
Marian Verhelst

title: Breaking high-resolution cnn bandwidth barriers with enhanced depth-first execution

venue: IEEE Journal on Emerging and Selected Topics in Circuits and Systems,

authors:
Song Han
Huizi Mao
William J Dally

title: Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep Residual Learning for Image Recognition

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:
Yihui He
Xiangyu Zhang
Jian Sun

title: Channel pruning for accelerating very deep neural networks

venue: In ICCV,

authors:
Yonghao He
Dezhong Xu
Lifang Wu
Meng Jian
Shiming Xiang
Chunhong Pan

title: Lffd: A light and fast face detector for edge devices

venue: arXiv preprint arXiv:1904.10633,

authors:
Andrew Howard
Mark Sandler
Grace Chu
Liang-Chieh Chen
Bo Chen
Mingxing Tan
Weijun Wang
Yukun Zhu
Ruoming Pang
Vijay Vasudevan
Quoc V. Le
Hartwig Adam

title: Searching for MobileNetV3

authors:
Andrew G. Howard
Menglong Zhu
Bo Chen
Dimitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications

authors:
Liangzhen Lai
Naveen Suda
Vikas Chandra

title: Cmsis-nn: Efficient neural network kernels for arm cortex-m cpus

venue: arXiv preprint arXiv:1801.06601,

authors:
Hamed F Langroudi
Vedant Karia
Tej Pandit
Dhireesha Kudithipudi

title: Tent: Efficient quantization of neural networks on the tiny edge with tapered fixed point

venue: arXiv preprint arXiv:2104.02233,

authors:
Edgar Liberis
Łukasz Dudziak
Nicholas D Lane

title: μnas: Constrained neural architecture search for microcontrollers

venue: arXiv preprint arXiv:2010.14246,

authors:
Edgar Liberis
Nicholas D Lane

title: Neural networks on microcontrollers: saving memory at inference via operator reordering

venue: arXiv preprint arXiv:1910.05110,

authors:
Ji Lin
Wei-Ming Chen
Yujun Lin
John Cohn
Chuang Gan
Song Han

title: Mcunet: Tiny deep learning on iot devices

authors:
Ji Lin
Yongming Rao
Jiwen Lu
Jie Zhou

title: Runtime neural pruning

venue: In NeurIPS,

authors:
Haoxiao Liu
Karen Simonyan
Yiming Yang

title: DARTS: Differentiable Architecture Search

authors:
Ze Liu
Yutong Lin
Yue Cao
Han Hu
Yixuan Wei
Zheng Zhang
Stephen Lin
Baining Guo

title: Swin transformer: Hierarchical vision transformer using shifted windows

venue: arXiv preprint arXiv:2103.14030,

authors:
Zechun Liu
Haoyuan Mu
Xiangyu Zhang
Zichao Guo
Xin Yang
Kwang-Ting Cheng
Jian Sun

title: MetaPruning: Meta Learning for Automatic Neural Network Channel Pruning

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen
Gao Huang
Shoumeng Yan
Changshui Zhang

title: Learning efficient convolutional networks through network slimming

authors:
Bo Lyu
Hang Yuan
Longfei Lu
Yunye Zhang

title: Resource-constrained neural architecture search on edge devices

venue: IEEE Transactions on Network Science and Engineering,

authors:
Ningning Ma
Xiangyu Zhang
Hai-Tao Zheng
Jian Sun

title: ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design

venue: In ECCV,

authors:
Hongyu Miao
Felix Xiaozhu Lin

title: Enabling large neural networks on tiny microcontrollers with swapping

venue: arXiv preprint arXiv:2101.08744,

authors:
Prajit Ramachandran
Barret Zoph
Quoc V Le

title: Searching for activation functions

venue: arXiv preprint arXiv:1710.05941,

authors:
Mohammad Rastegari
Vicente Ordonez
Joseph Redmon
Ali Farhadi

title: Xnor-net: Imagenet classification using binary convolutional neural networks

authors:
Manuele Rusci
Alessandro Capotondi
Luca Benini

title: Memory-driven mixed low precision quantization for enabling deep network inference on microcontrollers

venue: MLSys,

authors:
Oindrila Saha
Aditya Kusupati
Harsha Vardhan Simhadri
Manik Varma
Prateek Jain

title: Rnnpool: Efficient non-linear pooling for ram constrained inference

venue: arXiv preprint arXiv:2002.11921,

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: MobileNetV2: Inverted Residuals and Linear Bottlenecks

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Arthur Stoutchinin
Francesco Conti
Luca Benini

title: Optimally scheduling cnn convolutions for efficient memory access

venue: arXiv preprint arXiv:1902.01492,

authors:
Mingxing Tan
Bo Chen
Ruoming Pang
Vijay Vasudevan
Mark Sandler
Andrew Howard
Quoc V Le

title: MnasNet: Platform-Aware Neural Architecture Search for Mobile

authors:
Mingxing Tan
Quoc Le

title: Efficientnet: Rethinking model scaling for convolutional neural networks

venue: In International Conference on Machine Learning,

authors:
Kuan Wang
Zhijian Liu
Yujun Lin
Ji Lin
Song Han

title: HAQ: Hardware-Aware Automated Quantization with Mixed Precision

authors:
Bichen Wu
Xiaoliang Dai
Peizhao Zhang
Yanghan Wang
Fei Sun
Yiming Wu
Yuandong Tian
Peter Vajda
Yangqing Jia
Kurt Keutzer

title: FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search

authors:
Shuo Yang
Ping Luo
Chen Change Loy
Xiaoou Tang

title: Wider face: A face detection benchmark

venue: In IEEE Conference on Computer Vision and Pattern Recognition

authors:
YoungJoon Yoo
Dongyoon Han
Sangdoo Yun

title: Extd: Extremely tiny face detector via iterative filter reuse

venue: arXiv preprint arXiv:1906.06579,

authors:
Shifeng Zhang
Xiangyu Zhu
Zhen Lei
Hailin Shi
Xiaobo Wang
Stan Z Li

title: S3fd: Single shot scale-invariant face detector

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Xiangyu Zhang
Xinyu Zhou
Mengxiao Lin
Jian Sun

title: ShuffleNet: An Extremely Efficient Convolutional Neural Network for Mobile Devices

authors:
Xu Zhao
Xiaoqing Liang
Chaoyang Zhao
Ming Tang
Jinqiao Wang

title: Real-time multi-scale face detector on embedded

venue: devices. Sensors,

authors:
Shuchang Zhou
Yuxin Wu
Zekun Ni
Xinyu Zhou
He Wen
Yuheng Zou

title: Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients

venue: arXiv preprint arXiv:1606.06160,

authors:
Chenzhuo Zhu
Song Han
Huizi Mao
William J Dally

title: Trained ternary quantization

venue: arXiv preprint arXiv:1612.01064,

authors:
Barret Zoph
Quoc V Le

title: Neural Architecture Search with Reinforcement Learning

authors:
Barret Zoph
Vijay Vasudevan
Jonathon Shlens
Quoc V. Le

title: Learning Transferable Architectures for Scalable Image Recognition

heading: 1 Introduction

text:
IoT devices based on tiny hardware like microcontroller units (MCUs) are ubiquitous nowadays. Deploying deep learning models on such tiny hardware will enable us to democratize artificial intelligence. However, tiny deep learning is fundamentally different from mobile deep learning due to the tight memory budget [27]: a common MCU usually has an SRAM smaller than 512kB, which is too small for deploying most off-the-shelf deep learning networks. Even for more powerful hardware like Raspberry Pi 4, fitting inference into the L2 cache (1MB) can significantly improve energy efficiency. These pose new challenges to efficient AI inference with a small peak memory usage.
Existing work employs pruning [16, 18, 19, 32, 31], quantization [16, 54, 53, 37, 46, 9, 39], and neural architecture search [6, 44, 47, 5] for efficient deep learning. However, these methods focus on reducing the number of parameters and FLOPs, but not the memory bottleneck. The tight memory budget limits the feature map/activation size, restricting us to use a small model capacity or a small input image size. Actually, the input resolutions used in existing tinyML work are usually small (< 2242) [27], which might be acceptable for image classification (e.g., ImageNet [11], VWW [10]), but not for dense prediction tasks like objection detection: as in Figure 2, the performance of object detection degrades much faster with input resolution than image classification. Such a restriction hinders the application of tiny deep learning on many real-life tasks (e.g., person detection).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
4x4patch (int8)
A cc
ur ac
y/ m
A P
(% )
60
65
70
75
Image Resolution
160 224 288 352
VOC mAP ImgNet Top-1
larger degrade VOC mAP
ImgNet Top-1
larger degrade
Image Resolution
A cc
ur ac
y/ m
A P
(% )
160 224 228 352
75
70
65
60
Figure 2. Detection is more sensitive to smaller resolutions.
We perform an in-depth analysis on memory usage of each layer in efficient network designs and find that they have a very imbalanced activation memory distribution. Take MobileNetV2 [41] as an example, as shown in Figure 1, only the first 5 blocks have a high peak memory (>450kB), becoming the memory bottleneck of the entire network. The remaining 13 blocks have a low memory usage, which can easily fit a 256kB MCU. The peak memory of the initial memory-intensive stage is 8× higher than the rest of the network. Such a memory pattern leaves a huge room for optimization: if we can find a way to “bypass” the
memory-intensive stage, we can reduce the overall peak memory by 8×.
In this paper, we propose MCUNetV2 to address the challenge. We first propose a patch-by-patch execution order for the initial memory-intensive stage of CNNs (Figure 3). Unlike conventional layer-by-layer execution, it operates on a small spatial region of the feature map at a time, instead of the whole activation. Since we only need to store the feature of a small patch, we can significantly cut down the peak memory of the initial stage (blue to yellow in Figure 3), allowing us to fit a larger input resolution. However, the reduced peak memory comes at the price of computation overhead: in order to compute the non-overlapping output patches, the input image patches need to be overlapped (Figure 3(b)), leading to repeated computation. The overhead is positively related to the receptive field of the initial stage: the larger the receptive field, the larger the input patches, which leads to more overlapping. We further propose receptive field redistribution to shift the receptive field and workload to the later stage of the network. This reduces the patch size as well as the computation overhead caused by overlapping, without hurting the performance of the network. Finally, patch-based inference brings a larger design space for the neural network, giving us more freedom trading-off input resolution, model size, etc. We also need to minimize the computation overhead under patch-based execution. To explore such a large and entangled space, we propose to jointly design the optimal deep model and its inference schedule with neural architecture search given a specific dataset and hardware.
Patch-based inference effectively reduces the peak memory usage of existing networks by 4-8× (Figure 5). The results are further improved when co-designing neural architecture with inference scheduling. On ImageNet [11], we achieve a record accuracy of 71.8% on MCU (Table 2); on visual wake words dataset [10], we are able to achieve >90% accuracy under only 32kB SRAM, which is 4.0× smaller compared to MCUNetV1 [27], greatly lowering the boundary of tiny deep learning (Figure 7). MCUNetV2 further unlocks the possibility to perform dense prediction tasks on MCUs (e.g., object detection), which was not practical due to the limited input resolution. We are able to achieve 64.6% mAP under 256kB SRAM constraints and 68.3% under 512kB, which is 16.9% higher compared to the existing state-of-the-art solution, making object detection applicable on a tiny ARM Cortex-M4 MCU. Our contributions can be summarized as follows:
• We systematically analyze the memory usage pattern of efficient CNN designs and find that they suffer from a imbalanced memory distribution, leaving a huge room for optimization. • We propose a patch-based inference scheduling to significantly reduce the peak memory required for running CNN models, together with receptive field redistribution to minimize the computation overhead.
• With the joint design of network architecture and inference scheduling, we achieve a record performance for tiny image classification and objection detection on MCUs. Our work largely addressed the memory bottleneck for tinyML, paving the way for various vision applications.

heading: 2 Understanding the Memory Bottleneck of Tiny Deep Learning

text:
We systematically analyze the memory bottleneck of CNN models. Imbalanced memory distribution. As an example, we provide the per-block peak memory usage of MobileNetV2 [41] in Figure 1. The profiling is done in int8 (details in Section 4). We can observe a clear pattern of imbalanced memory usage distribution. The first 5 blocks have large peak memory, exceeding the memory constraints of MCUs, while the remaining 13 blocks easily fit 256kB memory constraints. The third block has 8× larger memory usage than the rest of the network, becoming the memory bottleneck. We also inspect other efficient network designs and find the phenomenon quite common across different CNN backbones, even for models specialized for memory-limited microcontrollers [27]. The detailed statistics are provided in the supplementary.
We find that this situation applies to most single-branch or residual CNN designs due to the hierarchical structure*: after each stage, the image resolution is down-sampled by half, leading to 4× fewer pixels, while the channel number increases only by 2× [42, 17, 22] or by an even smaller ratio [41, 21, 45], resulting in a decreasing activation size. Therefore, the memory bottleneck tends to appear at the early stage of the network, after which the peak memory usage is much smaller. Challenges and opportunities. The imbalanced memory distribution significantly limits the model capacity and input resolution executable on MCUs. In order to accommodate the initial memoryintensive stage, the whole network needs to be scaled down even though the majority of the network already has a small memory usage. It also makes resolution-sensitive tasks (e.g., object detection) difficult, as a high-resolution input will lead to large initial peak memory. Consider the first convolutional layer in MobileNetV2 [41] with input channels 3, output channels 32, and stride 2, running it on an image of resolution 224 × 224 requires a memory of 3 × 2242 + 32 × 1122 = 539kB even when quantized in int8, which cannot be fitted into microcontrollers. On the other hand, if we can find a way to “bypass” the initial memory-intensive stage, we can greatly reduce the peak memory of the whole network, leaving us a large room for optimization.

heading: 3 MCUNetV2: Memory-Efficient Patch-based Inference

heading: 3.1 Breaking the Memory Bottleneck with Patch-based Inference

text:
We propose to break the memory bottleneck of the initial layers with patch-based inference (Figure 3). Existing deep learning inference frameworks (e.g., TensorFlow Lite Micro [1], TinyEngine [27], microTVM [8], etc.) use a layer-by-layer execution. For each convolutional layer, the inference library first allocates the input and output activation buffer in SRAM, and releases the input buffer after the whole layer computation is finished. Such an implementation makes inference optimization easy (e.g., im2col, tiling, etc.), but the SRAM has to hold the entire input and output activation for
*some CNN designs have highly complicated branching structure (e.g., NASNet [56]), but they are generally less efficient for inference [34, 44, 6]; thus not widely used for edge computing.
each layer, which is prohibitively large for the initial stage of the CNN. Our patch-based inference runs the initial memory-intensive stage in a patch-by-patch manner. For each time, we only run the model on a small spatial region (>10× smaller than the whole area), which effectively cuts down the peak memory usage. After this stage is finished, the rest of the network with a small peak memory is executed in a normal layer-by-layer manner (upper notations in Figure 1).
We show an example of two convolutional layers (with stride 1 and 2) in Figure 3. For conventional per-layer computation, the first convolutional layer has large input and output activation size, leading to a high peak memory. With spatial partial computation, we allocate the buffer for the final output and compute its values patch-by-patch. In this manner, we only need to store the activation from one patch instead of the whole feature map. Note that the first activation is the input image, which can be partially decoded from a compressed format like JPEG and does not require full storage. Computation overhead. The significant memory saving comes at the cost of computation overhead. To maintain the same output results as per-layer inference, the non-overlapping output patches correspond to overlapping patches in the input image (the shadow area in Figure 3(b)). This is because convolutional filters with kernel size >1 contribute to increasing receptive fields. The bordering pixel on the output patches is dependent on the inputs from neighboring patches. Such repeated computation can increase the overall network computation by 10-17% even under optimal hyper-parameter choice (Figure 5), which is undesirable for low-power edge devices.

heading: 3.2 Reducing Computation Overhead by Redistributing the Receptive Field

text:
The computation overhead is related to the receptive field of the patch-based initial stage. Consider the output of the patch-based stage, the larger receptive field it has on the input image, the larger resolution for each patch, leading to a larger overlapping area and repeated computation (see Section 4.4 for quantitative analysis). For MobileNetV2, if we only consider down-sampling, each input patch has a side length of 224/4 = 56. But when considering the increased receptive field, each input patch has to use a shape of 75× 75, leading to a large overlapping area. We propose to redistribute the receptive field (RF) of the CNN to reduce computation overhead. The basic idea is: (1) reduce the receptive field of the patch-based initial stage; (2) increase the receptive field of the later stage. Reducing RF for the initial stage helps to reduce the size of each input patch and repeated computation. However, some tasks may have degraded performance if the overall RF is smaller (e.g., detecting large objects). Therefore, we further increase the RF of the later stage to compensate for the performance loss.
We take MobileNetV2 as a study case and modify its architecture. The comparison is shown in Figure 4. We used smaller kernels and fewer blocks in the per-patch inference stage, and increased
the number of blocks in the later per-layer inference stage. The process needs manual tuning and varies case-by-case. We will later discuss how we automate the process with NAS. We compare the performance of the two architectures in Table 1. Per-patch inference reduces the peak SRAM by 8× for all cases, but the original MobileNetV2 design has 42% computation overhead for the patch-based stage and 10% for the overall network. After redistributing the receptive field (“MbV2-RD”), we can reduce the input patch size from 75 to 63, while maintaining the same level of performance in image classification and object detection. After redistribution, the computation overhead is only 3%, which is negligible considering the benefit in memory reduction.

heading: 3.3 Joint Neural Architecture and Inference Scheduling Search

text:
Redistributing the receptive field allows us to enjoy the benefit of memory reduction at minimal computation/latency overhead, but the strategy varies case-by-case for different backbones. The reduced peak memory also allows larger freedom when designing the backbone architecture (e.g., using a larger input resolution). To explore such a large design space, we propose to jointly optimize the neural architecture and the inference scheduling in an automated manner. Given a certain dataset and hardware constraints (SRAM limit, Flash limit, latency limit, etc.), our goal is to achieve the highest accuracy while satisfying all the constraints. We have the following knobs to optimize:
Backbone optimization. We follow [27] to use a MnasNet-alike search space [44, 6] for NAS, so that we can have a fair comparison. The space includes different kernel sizes for each inverted residual block k[ ] (3/5/7), different expansion ratios e[ ] (3/4/6), and a different number of blocks for each stage d[ ] (2/3/4). More recent search space designs like MobileNetV3 [21] have better accuracy-computation trade-off, but are hard to quantize due to Swish activation function [36], making deployment on MCU difficult. As shown in [27], the search space configuration (i.e., the global width multiplier w and input resolution r) is crucial to the final NAS performance. We argue that the best search space configuration is not only hardware-aware but also task-aware: for example, some tasks may prefer a higher resolution over a larger model size, and vice versa. Therefore, we also put r and w into the search space. We further extend w to support per-block width scaling w[ ]. Including w[ ] (0.5/0.75/1.0) and r (96-256) expands the search space scalability, allowing us to fit different MCU models and tight resource budgets (ablation study provided in the supplementary).
Inference scheduling optimization. Given a model and hardware constraints, we will find the best inference scheduling. Our inference engine is developed based on TinyEngine [27] to further patch-based inference. Apart from the optimization knobs in TinyEngine, we also need to determine the patches number p and the number of blocks n to perform patch-based inference, so that the inference satisfies the SRAM constraints. According to Section 4.4, a smaller p and n lead to a smaller computation overhead and faster inference. But it varies case-by-case, so we jointly optimize it with the architecture.
Joint search. We need to co-design the backbone optimization and inference scheduling. For example, given the same constraints, we can choose to use a smaller model that fits per-layer execution (p = 1, no computation overhead), or a larger model and per-patch inference (p > 1, with a small computation overhead). Therefore, we put both sides in the same loop and use evolutionary search to find the best set of (k[ ], e[ ], d[ ], w[ ], r, p, n) satisfying constraints. Specifically, we randomly sample neural networks from the super network search space; for each sampled network, we enumerate all the p and n choices (optimized together with other knobs in TinyEngine) and find the satisfying combinations. We then report the best (p, n) pair with minimal computation/latency, and use the statistics to supervise architecture search. We provide the details and pseudo code in supplementary.

heading: 4 Experiments

text:
Memory profiling. The memory usage is dependent on the inference framework implementation [27]. To ease the comparison, we study two profiling settings:
(1) We first study analytic profiling, which is only related to the model architecture but not the inference framework. Following [10, 40], the memory required for a layer is the sum of input and output activation (since weights can be partially fetched from Flash); for networks with multi-branches (e.g., residual connection), we consider the sum of memory required for all branches at the same time (if the same input is shared by multiple branches, it will only be counted once).
Per-layer Per-patch
OOM
0
56765164 85
132 94113
234
310300315
(2) We also study on-device profiling to report the measured SRAM and Flash usage when executing the deep model on MCU. The number is usually larger than the analytic results since we need to account for temporary buffers storing partial weights, Im2Col buffer, etc. Datasets. We analyze the advantage of our method on image classification datasets: ImageNet [11] as the standard benchmark, and Visual Wake Words [10] to reflect TinyML applications. We further validate our method on object detection datasets: Pascal VOC [13] and WIDER FACE [48] to show our advantage: be able to fit larger resolution on the MCU. Training&deployment. We follow [27] for super network training and evolutionary search, detailed in the supplementary. Models are quantized to int8 for deployment. We extend TinyEngine [27] to support patch-based inference, and benchmark the models on 3 MCU models with different hardware resources: STM32F412 (Cortex-M4, 256kB SRAM/1MB Flash), STM32F746 (Cortex-M7, 320kB SRAM/1MB Flash), STM32H743 (Cortex-M7, 512kB SRAM/2MB Flash).

heading: 4.1 Reducing Peak Memory of Existing Networks

text:
We first analyze how patch-based inference can significantly reduce the peak memory for model inference, both in analytic profiling and on-device profiling. Analytic profiling. We study several widely used deep network backbones designed for edge inference in Figure 5: MobileNetV2 [41] (MbV2), redistributed MobileNetV2 (MbV2-RD), OnceFor-All CPU (OFA-CPU) [5], MnasNet [44], and FBNet-A [47]. All the networks use an input resolution of 224× 224; for patch-based inference, we used 4× 4 patches. The memory is profiled in int8. Per-patch inference significantly reduces the peak memory by 3.7-8.0×, while only incurring 8-17% of computation overhead. For MobileNetV2, we can reduce the computation overhead from 10% to 3% by redistributing the receptive field without hurting accuracy (Table 1). The memory saving and computation reduction are related to the network architecture. Some models like MnasNet have a larger overhead since it uses large kernel sizes in the initial stage, which increases receptive fields. It shows the necessity to co-design the network architecture with the inference engine. On-device measurement. We further profile existing networks running on STM32F746 MCU. We measure the SRAM usage of the network with per-layer and per-patch (2 × 2 or 3 × 3 patches) inference. Due to the memory limit of MCU (320kB SRAM, 1MB Flash), we have to scale down the width multiplier w and input resolution r. As in Figure 6, per-patch based inference reduces the measured peak SRAM by 4-6×. Some models may have a large latency overhead, since the initial
STM32F412 (256kB SRAM, 1MB Flash)
MbV2 0.35× (r=144) [41] / TinyEngine [27] int8 24M 308kB 862kB 49.0% 73.8% Proxyless 0.3× (r=176) [6] / TinyEngine [27] int8 38M 292kB 892kB 56.2% 79.7% MbV1 0.5× (r=192) [22] / Rusci et al. [39] mixed 110M <256kB <1MB 60.2% MCUNet (TinyNAS / TinyEngine) [27] int8 68M 238kB 1007kB 60.3% - MCUNet (TinyNAS / TinyEngine) [27] int4 134M 233kB 1008kB 62.0% -
MCUNetV2-M4 int8 119M 196kB 1010kB 64.9% 86.2%
STM32H743 (512kB SRAM, 2MB Flash)
MbV1 0.75× (r=224) [22] / Rusci et al. [39] mixed 317M <512kB <2MB 68.0% MCUNet (TinyNAS / TinyEngine) [27] int8 126M 452kB 2014kB 68.5% - MCUNet (TinyNAS / TinyEngine) [27] int4 474M 498kB 2000kB 70.7% -
V W
W A
cc ur
ac y
(% ) 92
94
finetune_proxyless384-vww_mcu128kb-1mb-patch4-fixedp_10e_qat
finetune_proxyless384-vww_mcu64kb-1mb-patch4-fixedp_10e_qat
finetune_proxyless384-vww_mcu32kb-1mb-patch4-fixedp_10e_qat
84
86
88
90
92
94
150 320 490 660 830 1000
old results
stage has worse hardware utilization. But with a proper architecture design (MbV2-RD), we can reduce the latency overhead to 4%, which is negligible compared to the memory reduction benefit.

heading: 4.2 MCUNetV2 for Tiny Image Classification

text:
With joint optimization of neural architecture and inference scheduling, MCUNetV2 significantly pushes the state-of-the-art results for MCU-based tiny image classification. Pushing the ImageNet record on MCUs. We compared MCUNetV2 with existing state-of-the-art solutions on ImageNet classification under two hardware settings: 256kB SRAM/1MB Flash and 512kB SRAM/2MB Flash. The former represents a widely used Cortex-M4 microcontroller; the latter corresponds to a higher-end Cortex-M7. The goal is to achieve the highest ImageNet accuracy on resource-constrained MCUs (Table 2). MCUNetV2 significantly improves the ImageNet accuracy of tiny deep learning on microcontrollers. Under 256kB SRAM/1MB Flash, MCUNetV2 outperforms the state-of-the-art method [27] by 4.6% at 18% lower peak SRAM. Under 512kB SRAM/2MB Flash, MCUNetV2 achieves a new record ImageNet accuracy of 71.8% on commercial microcontrollers, which is 3.3% compared to the best solution under the same quantization policy. Lower-bit (int4) or mixed-precision quantization can further improve the accuracy (marked in gray in the table). We believe that we can further improve the accuracy of MCUNetV2 with a better quantization policy, which we leave to future work.
Visual Wake Words under 32kB SRAM. Visual wake word (VWW) reflects the low-energy application of tinyML. MCUNetV2 allows us to run a VWW model with a modest memory requirement. As in Figure 7, MCUNetV2 outperforms state-of-the-art method [27] for both accuracy vs.
peak memory and accuracy vs. latency trade-off. We perform neural architecture search under both per-layer and per-patch inference settings using the same search space and super network for ablation. Compared to per-layer inference, MCUNetV2 can achieve better accuracy using 4.0× smaller memory. Actually, it can achieve >90% accuracy under 32kB SRAM requirement, allowing us to deploy the model on low-end MCUs like STM32F410 costing only $1.6. For the latency-constrained setting, we jointly optimized the model architecture and inference scheduling, where a smaller patch number is used when possible. Per-patch inference also expands the search space, giving us more freedom to find models with better accuracy vs. latency trade-off.

heading: 4.3 MCUNetV2 for Tiny Object Detection

text:
Object detection is sensitive to a smaller input resolution (Figure 2). Current state-of-the-art [27] cannot achieve a decent detection performance on MCUs due to the resolution bottleneck. MCUNetV2 breaks the memory bottleneck for detectors and improves the mAP by double digits.
MCU-based detection on Pascal VOC. We show the object detection results on Pascal VOC trained with YOLOv3 [38] on Table 3. We provide MCUNetV2 results for M4 MCU with 256kB SRAM and H7 MCU with 512kB SRAM. On H7 MCU, MCUNetV2-H7 improves the mAP by 16.7% compared to the state-of-the-art method MCUNet [27]. It can also scale down to fit a cheaper commodity Cortex-M4 MCU with only 256kB SRAM, while still improving the mAP by 13.2% at 1.9× smaller peak SRAM. Note that MCUNetV2-M4 shares a similar computation with MCUNet (172M vs. 168M) but a much better mAP. This is because the expanded search space from patch-based inference allows us to choose a better configuration of larger input resolution and smaller models.
Memory-efficient face detection. We benchmarked MCUNetV2 for memory-efficient face detection on WIDER FACE [48] dataset in Table 4. We report the analytic memory usage of the detector backbone in fp32 following [40]. We train our methods with S3FD face detector [50] following [40] for a fair comparison. We also report mAP on samples with ≤ 3 faces, which is a more realistic setting for tiny devices. MCUNetV2 outperforms existing solutions under different scales. MCUNetV2-L achieves comparable performance at 3.4× smaller peak memory compared to RNNPool-Face-C [27] and 9.9× smaller peak memory compared to LFFD [20]. The computation is also 1.6× and 8.4×
smaller. MCUNetV2-S consistently outperforms RNNPool-Face-A [40] and EagleEye [52] at 1.8× smaller peak memory.

heading: 4.4 Analysis

text:
Hyper-parameters for patch-based inference. We study the hyper-parameters used for patchbased inference: the number of blocks to be executed under patch-based inference n; the number of patches to split the input image p (splitting the image into p× p overlapping patches). We analyze MobileNetV2 [41] in Figure 8(a), with a larger n, the patch size increases due to the growing receptive field. The peak memory first goes down since the output feature map is smaller then goes up due to larger receptive field overhead. n = 5 is optimal. For a larger p (given n=5), each patch is smaller, which helps to reduce the peak memory. However, it also leads to more computation overhead due to more spatial overlapping (Figure 8(b)). Receptive field redistribution can reduce the overhead significantly (MbV2-RD). The optimal design is n∗ = 5, p∗ = 4 to reach the minimum peak memory with the smallest overhead. The choice of p and n varies for different networks. Therefore, we use an automated method to jointly optimize with neural architecture (Section 3.3). Comparison to other solutions. We also compare MCUNetV2 with other methods that reduce inference peak memory. The comparison on MobileNetV2 [41] is shown in Table 5. A straightforward way is to split the input image into non-overlapping patches (“Non-overlap”) for the first several blocks as done in [12]. Such a practice does not incur extra computation, but it breaks the feature propagation between patches and the translational invariance of CNNs. It achieves lower image classification accuracy and significantly degraded object detection mAP (on Pascal VOC) due to the lack of cross-patch communication (a similar phenomenon is observed in [30]). For MobileNetV2 with RNNPool [40], it can reduce the peak memory but leads to inferior ImageNet accuracy and object detection mAP. Its training time is also 3.2× longer† due to the complicated data path and the RNN module. On the other hand, MCUNetV2 acts exactly the same as a normal network during training (per-layer forward/backward), while also matching the image classification and objection detection performance. MCUNetV2 can further improve the results with joint neural architecture and inference scheduling search (Section 4.2). Dissecting MCUNetV2 architecture. We visualize one of the MCUNetV2 model architecture on the VWW [10] dataset in Figure 9. We can find the following patterns:
• The kernel size in the per-patch inference stage is small (1 × 1 and 3 × 3) to reduce the receptive field and spatial overlapping, thus reducing computation overhead.
†measured with official PyTorch code (MIT License) using a batch size of 64 on NVIDIA Titan RTX.
• The expansion ratio of the middle stage (early in per-layer stage) is small to further reduce the peak memory; while the expansion ratio for the later stage is large to increase performance. • Large expansion ratios and large kernel sizes usually do not appear together to reduce the computational cost and latency: if the expansion ratio is large (like 6), the kernel size is small (3× 3 or 5× 5); if the kernel size is large (7× 7), the expansion ratio is small (3 or 4). • The input resolution is larger on resolution-sensitive datasets like VWW compared to MCUNet [27], since per-layer inference cannot fit a large input resolution.
Notice that all the patterns are automatically discovered by the joint neural architecture and inference scheduling search algorithm, without human expertise.

heading: 5 Related Work

text:
Tiny deep learning on microcontrollers. Deploying deep learning models on memory-constrained microcontrollers requires an efficient inference framework and model architecture. Existing deployment frameworks include TensorFlow Lite Micro [1], CMSIS-NN [23], TinyEngine [27], MicroTVM [8], CMix-NN [7], etc. However, all of the above frameworks support only per-layer inference, which limits the model capacity executable under a small memory and makes higher resolution input impossible.
Efficient neural network. For efficient deep learning, people apply pruning [16, 18, 28, 19, 32, 31] and quantization [16, 54, 53, 37, 46, 9, 39, 24] to compress an off-the-shelf deep network, or directly design an efficient network architecture [22, 41, 21, 34, 51]. Neural architecture search (NAS) [55, 56, 29, 6, 44, 47] can design efficient models in an automated way. It has been used to improve tinyML on MCUs [27, 4, 25, 14, 33]. However, most of the NAS methods use the conventional hierarchy CNN backbone design, which leads to an imbalanced memory distribution under per-layer inference (Section 2), restricting the input resolution. Therefore, they are not able to achieve good performance on tasks like object detection without our patch-based inference scheduling.
Computation scheduling/re-ordering. The memory requirement to run a deep neural network is related to the implementation. It is possible to reduce the required memory by optimizing the convolution loop-nest [43], reordering the operator executions [26, 2], or temporarily swapping data off SRAM [35]. Computing partial spatial regions across multiple layers can reduce the peak memory [15, 3, 40]. However, system-only optimization leads to either large repeated computation or a highly complicated dataflow. Our work explores joint system and model optimization to reduce the peak memory at a negligible computation overhead while still allowing conventional convolution optimization techniques like im2col, tiling, etc.

heading: 6 Conclusion

text: In this paper, we propose patch-based inference to reduce the memory usage for tiny deep learning by up to 8×, which greatly expands the design space and unlocks powerful vision applications on IoT devices. We jointly optimize the neural architecture and inference scheduling to develop MCUNetV2. MCUNetV2 significantly improves the object detection performance on microcontrollers by 16.9% and achieves a record ImageNet accuracy (71.8%). For the VWW dataset, MCUNetV2 can achieve >90% accuracy under only 32kB SRAM, 4× smaller than existing work. Our study largely addresses the memory bottleneck in tinyML and paves the way for vision applications beyond classification.

heading: Acknowledgments

text: We thank MIT-IBM Watson AI Lab, Samsung, Woodside Energy, and NSF CAREER Award #1943349 for supporting this research.

title: MCUNetV2: Memory-Efficient Patch-based Inference for Tiny Deep Learning