Adria Ruiz

Jakob Verbeek

Adaptative Inference Cost With Convolutional Neural Mixture Models

Despite the outstanding performance of convolutional neural networks (CNNs) for many vision tasks, the required computational cost during inference is problematic when resources are limited. In this context, we propose Convolutional Neural Mixture Models (CNMMs), a probabilistic model embedding a large number of CNNs that can be jointly trained and evaluated in an efficient manner. Within the proposed framework, we present different mechanisms to prune subsets of CNNs from the mixture, allowing to easily adapt the computational cost required for inference. Image classification and semantic segmentation experiments show that our method achieve excellent accuracy-compute trade-offs. Moreover, unlike most of previous approaches, a single CNMM provides a large range of operating points along this trade-off, without any re-training.

Introduction

Convolutional neural networks (CNNs) form the basis of many state-of-the-art computer vision models. Despite their outstanding performance, the computational cost of inference in these CNN-based models is typically very high. This holds back applications on mobile platforms, such as autonomous vehicles, drones, or phones, where computational resources are limited, concurrent data-streams need to be processed, and low-latency prediction is critical.

To accelerate CNNs we can reduce their complexity before training, e.g. by decreasing the number of filters or network layers. This solution, however, may lead to suboptimal results given that over-parametrization plays a critical role in the optimization of deep networks [START_REF] Simon S Du | Gradient descent provably optimizes over-parameterized neural networks[END_REF][START_REF] Frankle | The lottery ticket hypothesis: Training pruned neural networks[END_REF]. Fortunately, other studies have found a complementary phenomena: given a trained CNN, a large number of its filters are redundant and do not have a significant impact on the final prediction [START_REF] Jaderberg | Speeding up convolutional neural networks with low rank expansions[END_REF]. Motivated by these two findings, much research has focused on accelerating CNNs using network pruning [START_REF] Ghosh | Structured variational learning of bayesian neural networks with horseshoe priors[END_REF][START_REF] Huang | Condensenet: An efficient densenet using learned group convolutions[END_REF][START_REF] Huang | Data-driven sparse structure selection for deep neural networks[END_REF][START_REF] Li | Pruning filters for efficient convnets[END_REF][START_REF] Liu | Learning efficient convolutional networks through network slimming[END_REF][START_REF] Louizos | Learning sparse neural networks through l 0 regularization[END_REF][START_REF] Neklyudov | Structured bayesian pruning via log-normal multiplicative noise[END_REF][START_REF] Véniat | Learning time/memoryefficient deep architectures with budgeted super networks[END_REF]. Pruning can be applied at multiple levels, e.g. by removing independent filters [START_REF] Li | Pruning filters for efficient convnets[END_REF][START_REF] Louizos | Learning sparse neural networks through l 0 regularization[END_REF], groups of them [START_REF] Ghosh | Structured variational learning of bayesian neural networks with horseshoe priors[END_REF][START_REF] Huang | Condensenet: An efficient densenet using learned group convolutions[END_REF], or entire layers [START_REF] Véniat | Learning time/memoryefficient deep architectures with budgeted super networks[END_REF]. Despite the encouraging results of these methods, their ability to provide a wide range of operating points along the trade-off between accuracy and computation is limited. The reason is that these approaches typically require to train a separate model for each specific pruning level.

In this paper, we propose Convolutional Neural Mixture Models (CNMMs), which provide a novel perspective on network pruning. A CNMM define a distribution over a large number of CNNs. The mixture is naturally pruned by removing networks with low probabilities, see Figure 1. Despite the appealing simplicity of this approach, it presents several challenges. First, learning a large ensemble of CNNs may require a prohibitive amount of computation. Second, even if many networks in the mixture are pruned, their independent evaluation during inference is likely to be less efficient than computing the output of a single large model.

In order to ensure tractability, we design a parametersharing scheme between different CNNs. This enables us to (i) jointly train all the networks, and (ii) efficiently compute an approximation of the mixture output without independently evaluating all the networks.

Image classification and semantic segmentation experiments show that CNMMs achieve an excellent trade-off between prediction accuracy and computational cost. Unlike most previous network pruning approaches, a single CNMM model achieves a wide range of operating points along this trade-off without any re-training.

Related work

Neural network ensembles. Learning ensembles of neural networks is a long-standing research topic. Seminal works explored different strategies to combine the outputs of different networks to obtain more accurate predictions [START_REF] Krogh | Neural network ensembles, cross validation, and active learning[END_REF][START_REF] Naftaly | Optimal ensemble averaging of neural networks[END_REF][START_REF] Zhou | Ensembling neural networks: many could be better than all[END_REF]. Recently, the success of deep models has renewed interest in ensemble methods.

For this purpose, many approaches have been explored. For instance, [START_REF] Balaji Lakshminarayanan | Simple and scalable predictive uncertainty estimation using deep ensembles[END_REF][START_REF] Zhu | Binary ensemble neural network: More bits per network or more networks per bit? CVPR[END_REF] used bagging [START_REF] Breiman | Bagging predictors[END_REF] and boosting [START_REF] Robert E Schapire | The boosting approach to machine learning: An overview[END_REF] to train multiple networks. Other works have considered to learn diverse models by employing different parameter initializations [START_REF] Lee | Why m heads are better than one: Training a diverse ensemble of deep networks[END_REF], or re-training a subset of layers [START_REF] Zhao | Retraining: A simple way to improve the ensemble accuracy of deep neural networks for image classification[END_REF]. While these strategies are effective to learn diverse networks, their main limitation is the required training cost. In practice, training a deep model can take multiple days, and therefore large ensembles may have a prohibitive cost. To reduce the training time, it has been suggested [START_REF] Huang | Snapshot ensembles: Train 1, get m for free[END_REF][START_REF] Loshchilov | Sgdr: Stochastic gradient descent with warm restarts[END_REF] to train a single network and to use parameters from multiple iterations of the optimization process to define the ensemble. Despite the efficiency of this method during training, this approach does not reduce inference cost, since multiple networks must be evaluated independently at test time.

An alternative strategy to allow efficient training and inference is to use implicit ensembles [START_REF] Ghosh | Structured variational learning of bayesian neural networks with horseshoe priors[END_REF][START_REF] Huang | Deep networks with stochastic depth[END_REF][START_REF] Larsson | Fractalnet: Ultra-deep neural networks without residuals[END_REF][START_REF] Neklyudov | Structured bayesian pruning via log-normal multiplicative noise[END_REF]. By relying on sampling, these methods allow to jointly train all the individual components in the ensemble and perform approximate inference during testing. Bayesian neural networks (BNNs) fall in this paradigm and use a distribution over parameters, rather than a single point estimate [START_REF] Ghosh | Structured variational learning of bayesian neural networks with horseshoe priors[END_REF][START_REF] Durk P Kingma | Variational dropout and the local reparameterization trick[END_REF][START_REF] Louizos | Multiplicative normalizing flows for variational bayesian neural networks[END_REF][START_REF] Neklyudov | Structured bayesian pruning via log-normal multiplicative noise[END_REF]. A sample from the parameter distribution can be considered as an individual network. Other works have implemented the notion of implicit ensembles by using dropout [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF] mechanisms. Dropping neurons can be regarded as sampling over a large ensemble of different networks [START_REF] Baldi | Understanding dropout[END_REF]. Moreover, scaling outputs during testing according to the dropout probability can be understood as an approximated inference mechanism. Motivated by this idea, different works have applied dropout over individual weights [START_REF] Gal | Concrete dropout[END_REF], network activations [START_REF] Singh | Swapout: Learning an ensemble of deep architectures[END_REF], or connections in multi-branch architectures [START_REF] Han | Branchout: Regularization for online ensemble tracking with convolutional neural networks[END_REF][START_REF] Larsson | Fractalnet: Ultra-deep neural networks without residuals[END_REF]. Interestingly, it has been observed that ResNets [START_REF] He | Identity mappings in deep residual networks[END_REF] behave like an ensemble of models, where some residual connections can be removed without significantly reducing prediction accuracy [START_REF] Veit | Residual networks behave like ensembles of relatively shallow networks[END_REF]. This idea was used by ResNets with stochastic depth [START_REF] Huang | Deep networks with stochastic depth[END_REF], where different dropout probabilities are assigned to the residual connections.

Our proposed Convolutional Neural Mixture Model is an implicit ensemble defining a mixture distribution over an exponential number of CNNs. This allows to use the learned probabilities to prune the model by removing nonrelevant networks. Using a mixture of CNNs for model pruning is a novel approach, which contrasts to previous methods employing ensembles for other purposes such as boosting performance [START_REF] Dutt | Coupled ensembles of neural networks[END_REF][START_REF] Lee | Why m heads are better than one: Training a diverse ensemble of deep networks[END_REF], improving learning dynamics [START_REF] Huang | Deep networks with stochastic depth[END_REF], or uncertainty estimation [START_REF] Ilg | Uncertainty estimates and multi-hypotheses networks for optical flow[END_REF][START_REF] Balaji Lakshminarayanan | Simple and scalable predictive uncertainty estimation using deep ensembles[END_REF].

Efficient inference in deep networks. A number of strategies have been developed to reduce the inference time of CNNs, including the design of efficient convolutional operators [START_REF] Howard | Mobilenets: Efficient convolutional neural networks for mobile vision applications[END_REF][START_REF] Forrest N Iandola | Squeezenet: Alexnet-level accuracy with 50x fewer parameters and¡ 0.5 mb model size[END_REF][START_REF] Zhang | Shufflenet: An extremely efficient convolutional neural network for mobile devices[END_REF], knowledge distillation [START_REF] Chen | Learning efficient object detection models with knowledge distillation[END_REF][START_REF] Hinton | Distilling the knowledge in a neural network[END_REF], neural architecture search [START_REF] He | AMC: AutoML for model compression and acceleration on mobile devices[END_REF][START_REF] Zoph | Learning transferable architectures for scalable image recognition[END_REF], weight compression [START_REF] Masana | Domain-adaptive deep network compression[END_REF][START_REF] Tai | Convolutional neural networks with low-rank regularization[END_REF], and quantization [START_REF] Jacob | Quantization and training of neural networks for efficient integer-arithmetic-only inference[END_REF][START_REF] Lin | Fixed point quantization of deep convolutional networks[END_REF]. Network pruning has emerged as one of the most effective frameworks for this purpose [START_REF] Ghosh | Structured variational learning of bayesian neural networks with horseshoe priors[END_REF][START_REF] Lecun | Optimal brain damage[END_REF][START_REF] Li | Pruning filters for efficient convnets[END_REF][START_REF] Véniat | Learning time/memoryefficient deep architectures with budgeted super networks[END_REF]. Pruning methods aim to remove weights which do not have a significant impact on the network output. Among these methods, we can differentiate between two main strategies: online and offline pruning. In offline pruning, a network is first optimized for a given task using standard training. Subsequently, non-relevant weights are identified using different heuristics including their norm [START_REF] Li | Pruning filters for efficient convnets[END_REF], similarity to other weights [START_REF] Srinivas | Data-free parameter pruning for deep neural networks[END_REF], or second order derivatives [START_REF] Lecun | Optimal brain damage[END_REF]. The main advantage of this strategy is that it can be applied to any pre-trained network. However, these approaches require a costly process involving several prune/retrain cycles in order to recover the original network performance. Online approaches, on the other hand, perform pruning during network training. For example, sparsity inducing regularization can be used over individual weights [START_REF] Liu | Learning efficient convolutional networks through network slimming[END_REF][START_REF] Louizos | Multiplicative normalizing flows for variational bayesian neural networks[END_REF], groups of them [START_REF] Ghosh | Structured variational learning of bayesian neural networks with horseshoe priors[END_REF][START_REF] Huang | Condensenet: An efficient densenet using learned group convolutions[END_REF][START_REF] Neklyudov | Structured bayesian pruning via log-normal multiplicative noise[END_REF], or over the connections in multi-branch architectures [START_REF] Ahmed | Maskconnect: Connectivity learning by gradient descent[END_REF][START_REF] Véniat | Learning time/memoryefficient deep architectures with budgeted super networks[END_REF]. These methods typically have a hyper-parameter, to be set before training, determining the trade-off between the final performance and the pruning ratio.

In contrast to previous approaches, we prune entire CNNs by removing the networks with the smallest probabilities in the mixture. This approach offers two main advantages. First, it does not require to define a hyper-parameter before training to determine the balance between the potential compression and the final performance. Second, the number of removed networks can be controlled after optimization. Therefore, a learned CNMM can be deployed at multiple operating points to trade-off computation and prediction accuracy. For example, across different devices with varying computational resources, or on the same device with different computational constraints depending on the processor load of other processes. The recently proposed Slimmable Neural Networks [START_REF] Yu | Slimmable neural networks[END_REF] have also focused on adapting the accuracy-efficiency trade-off at run time. This is achieved by embedding a small set of CNNs with varying widths into a single model. Different from this approach, our CNMMs embed a large number of networks with different depths, which allows for a finer granularity to control the computational cost during pruning. applied to compute the CNN output. In this manner, sequences with common sub-sequences share functions and their parameters in the corresponding networks. (Right) Illustration of the distribution p(s0:T ) that defines the mixing weights over the CNN models, here T = 4. Each p(st-1|st) is a Bernoulli distribution on whether st-1 equals st or t -1. This defines a binary tree generating all the valid sequences.

Convolutional Neural Mixture Models

Without loss of generality, we consider a CNN as a function F(H 0 ) = H T mapping an RGB image H 0 ∈ R W0×H0×3 to a tensor H T ∈ R W ×H×C . In particular, we assume that F is defined as a sequence of T operations:

F(H 0 ) = f T T -1 (. . . (f 2 1 (f 1 0 (H 0 )))), (1)
where

H t = f t t-1 (H t-1
) is computed from the previous feature map H t-1 . We assume that the functions f t t-1 can be either the identity function, or a standard CNN block composed of different operations such as batchnormalization, convolution, activation functions, or spatial pooling. In this manner, the effective depth of the network, i.e. the number of non-identity layers f t t-1 , is at most T . The output tensor H T of the CNN is used to make predictions for a specific task. For example, in image classification, a linear classifier over H T can be used in order to estimate the class probabilities for the entire image. For semantic segmentation the same linear classifier is used for each spatial position in H T .

Given these definitions, a convolutional neural mixture model (CNMM) defines a distribution over output H T as:

p(H T |H 0 ) = F ∈F p(F)p(H T |H 0 , F), (2)
where

F = {F 1 , F 2 , ..., F K } is a finite set of CNNs, p(H T |H 0 , F k ) is a delta function centered on the output F k (H 0 )
of each network, and p(F) defines the mixing weights over the CNNs in F.

Modelling a distribution over CNNs

We now define mixtures that contain a number of CNNs that is exponential in the maximum depth T , in a way that allows us to manipulate these mixtures in a tractable manner.

Each component in the mixture is a chain-structured CNN uniquely characterised by a sequence s 0:T of length T + 1, where the sequences are constrained to be a nondecreasing set of integers from 0 to T , i.e. with s 0 = 0, s T = T and s t+1 ≥ s t . This sequence determines the set of functions that are used in Eq. ( 1). In particular, given a sequence s 0:T , the output of the corresponding network is computed as:

F(H 0 ) = f s T s T -1 (. . . (f s2 s1 (f s1 s0 (H 0 )). (3)
For i < j the function f j i is a convolutional block as described above with its own parameters, while the functions f i i are identity functions that leave the input unchanged. By, imposing s t-1 ∈ {t -1, s t }, there is a one-toone mapping between sequences s 0:T and the corresponding CNNs. 1 If multiple networks use the same function f j i , these networks share their parameters on this function, which ensures that the total number of parameters of the mixture does not grow exponentially, although there are exponentially many mixture components. For instance, for T = 4, the mixture will be composed of eight different networks illustrated in Figure 2 (Left). From the illustration it is easy to see that, in general, the mixture contains 2 T -1 components with shared parameters.

In order to define the probabilities p(F) for each network in the mixture, we define a distribution over sequences s 0:T as a reversed Markov chain:

p(s 0:T ) = p(s T ) T t=1 p(s t-1 |s t ). (4)
To ensure that sequences have positive probability if and only if they are valid, i.e. satisfy the constraints defined above, we set p(s T = T ) = p(s 0 = 0|s 1 ) = 1 and define:

p(s t-1 |s t ) =      π st t-1 if s t-1 = (t -1), 1 -π st t-1 if s t-1 = s t , 0 otherwise. ( 5
)
As illustrated in Figure 2 (Right), these constraints generate a binary tree generating valid non-decreasing sequences. The conditional probabilities p(s t-1 |s t ) are modelled by a Bernoulli distribution with probability π st st-1 , indicating whether the previous number in the sequence is s t or t -1.

Sampling outputs from CNMMs

The graphical model defined in Figure 3 shows that we can sample from the output distribution p(H T |H 0 ) in Eq. ( 2) by first generating a sequence from p(s 0:T ) and then evaluating the associated network with Eq. ( 3). In the following, we formulate an alternative strategy to sample from the model. This formulation offers two advantages. (i) It is amenable to continuous relaxation, which facilitates learning. (ii) It suggests an iterative algorithm to compute feature map expectations, which can be used instead of sampling for efficient inference.

The conditional p(H t |s t = l, H 0 ) gives the distribution over H t across the networks with s t = l. For example, p(H 2 |s 2 = 4, H 0 ) consists of two weighted delta peaks, located at f 4 0 (H 0 ) and f 1 0 (f 4 1 (H 0 )), respectively. See Figure 2 (Left). These conditional distributions can be expressed as the forwards recurrence:

p(H t |s t , H 0 ) = Ht-1,st-1 p(H t |H t-1 , s t , s t-1 )p(s t-1 |s t ) × p(H t-1 |s t-1 , H 0 ) Recurrent term , (6)
where p(H t |H t-1 , s t , s t-1 ) is a delta function centered on f st st-1 (H t-1 ). Therefore, unbiased samples hst t from p(H t |s t , H 0 ) can be obtained through sample propagation. Recall from Eq. ( 5) that, given s t , there are only two possible values of s t-1 that remain, namely s t and t -1. As a consequence, the sum over s t-1 in Eq. ( 6) only consists of two terms. Given this observation, samples hst t ∼ p(H t |s t , H 0 ) can be obtained from samples obtained in the previous iteration, (ii) the corresponding functions f s t t-1 and (iii) samples πs t t-1 from p(st-1|st). Bottom: Network with dense connectivity implementing the sampling algorithm.

hst-1

t-1 ∼ p(H t-1 |s t-1 , H 0 ) as:

hst t = πst t-1 f st t-1 ( ht-1 t-1 ) + (1 -πst t-1 ) hst t-1 , (7)
where for a given value of s t we sample s t-1 from p(s t-1 |s t ) to compute a binary indicator πst

t-1 = [[s t-1 = t -1]], which signals whether the resulting hst t is equal to hst t-1 or f st t-1 ( ht-1 t-1
). Using Eq. ( 7) we iterative sample from distributions p(H t |s t , H 0 ) for t = 1, . . . , T , and for each t we compute samples for s t = t, . . . , T . An illustration of the algorithm is shown in Figure 4. The computational complexity of a complete pass in this iterative process is O(T (T + 1)/2), since for each t = 1, . . . , T , we compute T -t + 1 samples, each of which is computed in O(1) from the samples already computed for t -1. This is roughly equivalent to the cost of evaluating a single network with dense layer connectivity of depth T [START_REF] Huang | Densely connected convolutional networks[END_REF], which has a total of T (T -1)/2 connections implemented by the functions f j i . Sampling outputs from networks of bounded depth. Using the described algorithm, hT T ∼ p(H T |s T = T, H 0 ) correspond to output tensors H L sampled from the mixture defined in Eq. ( 2). Moreover, for any t, samples from p(H t |s t = T, H 0 ) are output feature maps generated by networks with depth bounded by t. For instance, in Figure 2, samples hT 2 are generated with one of the networks coded by the sequences 01444 and 04444.

Training and inference

We use ψ to collectively denote the parameters of the convolutional blocks f j i and the parameters π st st-1 defining the mixing weights via Eq. ( 5). Moreover, the parameters of the classifier that predict the image label(s) from the output tensor H T are denoted as θ. Given a training set D = {(X 1 , y 1 ), . . . , (X N , y N )} composed of images X n and labels y n , we optimize the parameters by minimizing [START_REF] Dutt | Coupled ensembles of neural networks[END_REF] where L (y n , H T , θ) is the cross-entropy loss comparing the label y n with the class probabilities computed from H T . In practice, we replace the expectation over H T in each training iteration with samples from p(H T |H 0 = X n ; ψ). Learning from subsets of networks. As discussed in Section 3.2, samples from the distribution p(H t |s t = T, H 0 ) correspond to outputs of CNNs in the mixture with depth at most t. In order to improve performance of models with reduced inference time, we explicitly emphasize the loss for such efficient relatively shallow networks. Therefore, we sum the above loss function over the outputs sampled from networks of increasing depth:

L single (ψ, θ) = N n=1 E p(H T |H0=Xn;ψ) L (y n , H T , θ) ,
L(θ, ψ) = N n=1 T t=1 E p(Ht|st=T,Xn;ψ) L y n , H t , θ t , (9)
where we use a separate classifier for each t. In practice, we balance each loss with a weight increasing linearly with t. Relaxed binary variables with concrete distributions. The recurrence in Eq. ( 7) requires sampling from p(s t-1 |s t ), defined in Eq. ( 5). The sampling renders the parameters π st t-1 non-differentiable, which prevents gradientbased optimization for them. To address this limitation, we use a continuous relaxation by modelling p(s t-1 |s t ) as a binary "concrete" distribution [START_REF] Chris J Maddison | The concrete distribution: A continuous relaxation of discrete random variables[END_REF]. In this manner, we can use the re-parametrization trick [START_REF] Kingma | Auto-encoding variational Bayes[END_REF][START_REF] Rezende | Stochastic backpropagation and approximate inference in deep generative models[END_REF] to back-propagate gradients w.r.t. samples πst t-1 in Eq. ( 7) and, thus to compute gradients for the parameters π st t-1 . Efficient inference by expectation propagation. Once the CNMM is trained, the predictive distribution on y is given by p(y|X; θ) = E p(H T |X) [p(y|H T ; θ)]. The expectation is intractable to compute exactly, contrary to our goal of efficient inference. A naive Monte-Carlo sample approximation is still requires multiple evaluations of the full CNMM. Instead, we propose an alternative approximation by propagating expectations instead of samples in Eq. ( 7), i.e. using the approximation HT ≈ p(H T |X), where HT is obtained by running the sampling algorithm replacing the samples πst t-1 with their expectations π st t-1 .

Accelerating CNNMs

CNMMs offer two complementary mechanisms in order to accelerate inference. We describe both in the following. Evaluating intermediate classifiers. The different classifiers θ t learned by minimizing Eq. ( 9) operate over the outputs of a mixture of networks with maximum depth t. Therefore, at each iteration t of the inference algorithm in Eq. ( 7) we can already output predictions based on classifier θ t . This strategy is related with the one employed in multiscale dense networks (MSDNets) [START_REF] Huang | Multi-scale dense convolutional networks for efficient prediction[END_REF], where "early-exit" classifiers are used to provide predictions at various points in time during the inference process.

Network pruning. A complementary strategy to accelerate CNMMs is to remove networks from the mixture. The computational cost of the inference process is dominated by the evaluation of the CNN blocks f st t-1 ( ht-1 t-1 ) in Eq. ( 7). However, these function does not need to be computed when the variable πst t-1 = 0. Therefore, a natural approach to prune CNMMs is to set certain π st t-1 to zero, removing all the CNNs from the mixture that use f st t-1 . We use the learned distribution p(s 0:T ) in order to remove networks with a low probability. Note that for a given value of s t , the pairwise marginal p(s t , s t-1 = t -1) is exactly the sum of probabilities of all the networks involving the function f st t-1 . Using this observation, we use an iterative pruning algorithm where, at each step, we compute all pairwise marginals p(s t , s t-1 = t -1) for all possible values of s t and t. We then set π s t t -1 = 0 where (s t ,t ) = arg min (st,t) p(s t , s t-1 = t -1). Finally, the marginals are updated, and we iterate.

In this manner, we achieve different pruning levels by progressively removing convolutional blocks that will not be evaluated during inference. This process does not require any re-training of the model, allowing to dynamically set different pruning ratios. Note that this process is complementary to the use of intermediate classifiers, as discussed above. The reason for this is that our pruning strategy may be used to remove functions f j i for any "early" prediction step t < T . Finally, it is interesting observe that the proposed pruning mechanism can be regarded as a form of neural architecture search [START_REF] Liu | Darts: Differentiable architecture search[END_REF][START_REF] Zoph | Learning transferable architectures for scalable image recognition[END_REF], where the optimal network connectivity for a given pruning ratio is automatically discovered by taking into account the learned probabilities p(s t-1 = t -1|s t ).

Experiments

We perform experiments over two different tasks: image classification and semantic segmentation. Following previous work, we measure the computational cost in terms of the number of floating point multiply and addition operations (FLOPs) required for inference. The number of FLOPs provides a metric that correlates very well with the actual inference wall-time, while being independent of implementation and hardware used for evaluation.

Datasets and experimental setup

CIFAR-10/100 datasets. These datasets [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] are composed of 50k train and 10k test images with a resolution of 32×32 pixels. The goal is to classify each image across 10 or 100 classes, respectively. Images are normalized using the means and standard deviations of the RGB channels. We apply standard data augmentation operations: (i) a 4pixel zeros padding followed by 32×32 cropping. (ii) Random horizontal flipping with probability 0.5. Performance is evaluated in terms of the mean accuracy across classes. CityScapes dataset. This dataset [START_REF] Cordts | The cityscapes dataset for semantic urban scene understanding[END_REF] contains 1024×2048 pixel images of urban scenes with pixel-level labels across 19 classes. The dataset is split into training, validation and test sets with 2,975, 500 and 1,525 samples each. The ground-truth annotations for the test set are not public, and we use the validation set instead for evaluation. To assess performance we use the standard mean intersection-overunion (mIoU) metric. We follow the setup of [START_REF] Mehta | Espnetv2: A light-weight, power efficient, and general purpose convolutional neural network[END_REF], and down-sample the images by a factor two before processing them. As a data augmentation strategy during training, we apply random horizontal flipping and resizing by using a scaling factor between 0.75 and 1.1. Finally, we use random crops of 384×768 pixels from the down-sampled images. Base architecture. As discussed in Section 3.2, the learning and inference algorithms for CNMMs can be implemented using a network with dense layer connectivity [START_REF] Huang | Densely connected convolutional networks[END_REF]. Based on this observation, we use an architecture similar to MSDNets [START_REF] Huang | Multi-scale dense convolutional networks for efficient prediction[END_REF]. Specifically. we define a set of B blocks, each composed of a set of S feature maps H t . See Fig. [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF].

The initial feature map in each block has C channels and, at each subsequent feature map in the block, the spatial resolution is reduced by a factor two in each dimension, and the number of channels is doubled. Feature maps are connected by functions f j i if the output feature map H j has the same or half the resolution of the input feature map H i . Finally, we consider the output tensor H T to have different connectivity and spatial resolution depending on the task.

Implementation for image classification. We implement the convolutional layers as the set of operations (BN-ReLU-DConv-BN-ReLU-Conv-BN), where BN refers to batch normalization, DConv is a

(3 × 3 × C × C
4 ) depth-wise separable convolution [START_REF] Howard | Mobilenets: Efficient convolutional neural networks for mobile vision applications[END_REF], and Conv is a (1 × 1 × C 4 × C) convolution. In order to reduce computation, for a given tensor H i , the different functions f j i share the parameters of the initial operations (BN-ReLU-DConv) for all j. Moreover, when the resolution of the feature map is reduced, we use average pooling after these three initial operations. In all our experiments, the number of initial channels in H 1 is set to C = 64. This is achieved by using a

(3 × 3 × 3 × C 4
) convolution over the input image H 0 and then apply a (1 × 1 × C 4 × C) convolutional block. Finally, all the tensors H l with the lowest spatial resolution are connected to the output H L . Concretely, H T is a vector R 512 obtained by applying the operations (BN-ReLU-GP-FC-BN) to the input tensors, where GP refers to global average pooling, and FC corresponds to a fully-connected layer. The classifier θ maps H T linearly to a vector of dimension equal to the number of classes. When using Eq. ( 9) to train the CNMM, we connect a classifier θ t with the end of each block.

Implementation for semantic segmentation. We use the same setup as for image classification, but replace the ReLU activations with parametric ReLUs as in [START_REF] Mehta | Espnet: Efficient spatial pyramid of dilated convolutions for semantic segmentation[END_REF]. Moreover, we use max instead of average pooling to reduce the spa- tial resolution. The input tensor H 1 has C = 48 channels and a resolution four times lower than the original images. This is achieved by applying a (3 × 3 × 3 × C 4 ) convolution with stride 2 to the input and then using a (BN-ReLU-Conv) block followed by max pooling. The output tensor H L receives connections from all the previous feature maps and has the same channels and spatial resolution as H 1 . Given that the input feature maps are at different scales, we apply a (BN-PReLU-Conv-BN) block over the input tensor and use bi-linear up-sampling with different scaling factors in order to recover the original spatial resolution. The final classifier θ computing the class probabilities using H T are defined as blocks (UP-BN-PReLU-Conv-UP-BN-PReLU-DConv), where UP refers to bilinear upsampling, which allows to recover the original image resolution. The first and second convolutions in the block have 12 and K output channels respectively, where K is the number of classes. As in image classification, we use an intermediate classifier θ t at each step t where a full block of computation is finished. Optimization details. In our experiments, we use SGD with momentum by setting the initial learning rate to 0.1 and weight decay to 10 -4 . In CIFAR, we use a cosine annealing schedule to accelerate convergence. On the other hand, in Cityscapes we employ a cyclic schedule with warm restarts as in [START_REF] Mehta | Espnetv2: A light-weight, power efficient, and general purpose convolutional neural network[END_REF]. The temperature of the concrete distributions modelling p(s t-1 |s t ) is set to 2. We train our model by using 300 and 200 epochs, and batch size of 64 and 6, for respectively CIFAR-10/100 and Cityscapes. For the cyclic scheduler, the learning rate is divided by two at epochs {30, 60, 90, 120, 150, 170, 190}. Additionally, the models trained in Cityscapes are fine-tuned during 10 epochs by using random crops of size 512×1024 instead of 384×768.

Pruning and intermediate classifiers

We evaluate the proposed pruning and intermediate classifiers strategies to reduce the inference time of trained CN-MMs. For CIFAR-10/100 we learn a CNMM with B = 6 blocks, using S = 3 scales each. For Cityscapes we use B = 5 blocks and S = 5 scales. For each dataset, we train one model that uses a single classifier θ, optimized using Eq. ( 8). In addition, we train a second model with intermediate classifiers θ t , minimizing the loss function in Eq. ( 9). In the following, we will refer to the first and second variant as CNMM-single and CNMM respectively.

In Figure 6 we report prediction accuracy vs. FLOPs for inference. Each model is represented as a curve, traced by pruning the model to various degrees. Across the three datasets, the CNMM model with intermediate classifiers achieves higher accuracy in fast inference settings than the CNMM-single model. Recall that all the operation point across the different CNMM curves are obtained from a single trained model. Therefore, this single model can realize the upper-envelope of the performance curves. As expected, the maximum performance of the intermediate classifiers increases with the step number. The accuracy of CNMM at the final step is comparable to the level obtained by the CNMM-single model: slightly worse on CIFAR-10, and slightly better at CIFAR-100 and CityScapes. This is because the minimized intermediate losses provide additional supervisory signal which is particularly useful to encourage accurate prediction for shallow, but fast, CNNs. In conclusion, the CNMM model with intemediate classifiers is to be preferred, since it provides a better trade-off between accuracy and computation at a wider range of FLOP counts.

By analysing the operating points along each curve, we can observe the effectiveness of the proposed pruning algorithm. For the CIFAR datasets we can reduce the FLOP count by a factor two without significant loss in accuracy. For CityScapes, about 25% pruning can be achieved without a significant loss. In general, if several exit points can achieve the same FLOP count by applying varying amounts of pruning, best performance is obtained pruning less for an earlier classifier, rather than pruning more for a later exit.

Comparison with the state of the art

Image classification. We compare our model with dif- ferent state-of-the-art CNN acceleration strategies [START_REF] Huang | Multi-scale dense convolutional networks for efficient prediction[END_REF][START_REF] Huang | Condensenet: An efficient densenet using learned group convolutions[END_REF][START_REF] Huang | Data-driven sparse structure selection for deep neural networks[END_REF][START_REF] Liu | Learning efficient convolutional networks through network slimming[END_REF][START_REF] Véniat | Learning time/memoryefficient deep architectures with budgeted super networks[END_REF]. We consider methods applying pruning at different levels, such as independent filters (Network slimming [START_REF] Liu | Learning efficient convolutional networks through network slimming[END_REF]), groups of weights (CondenseNet) [START_REF] Huang | Condensenet: An efficient densenet using learned group convolutions[END_REF], connections in multi-branch architectures (SuperNet) [START_REF] Véniat | Learning time/memoryefficient deep architectures with budgeted super networks[END_REF], or a combination of them (SSS) [START_REF] Huang | Data-driven sparse structure selection for deep neural networks[END_REF]. We also compare our method with any-time models based on early-exit classifiers (MSDNet) [START_REF] Huang | Multi-scale dense convolutional networks for efficient prediction[END_REF]. Among other previous state-of-theart methods, the compared approaches have shown the best performance among efficient inference methods with ≤200 million FLOPs. We compare to CNMMs using 6 and 12 blocks, using three scales is both cases.

The results in Figure 7 (left, center) show that CNMMs achieve similar or better accuracy-compute trade-off across a broad range of FLOP counts than all the compared methods in the CIFAR datasets. Only CondenseNets shows somewhat better performance for medium FLOP counts. Moreover, note that the different operating points shown for the compared methods (except for MSDNets) are obtained by using different models trained independently, e.g. by different settings of a hyper-parameter controlling the pruning ratio. In contrast, CNMM embeds a large number operating points in a single model. This feature is interesting when the available computational budget can change dynamically, based on concurrent processes, or when the model is deployed across a wide range of devices. In these scenarios, a single CNMM can be accelerated on-the-fly depending on the available resources. Note that a single MSDNet is also able to provide early-predictions by using intermediate classifiers. However, our CNMM provides better performance for a given FLOP count and allows for a finer granularity to control the computational cost.

Semantic segmentation.

State-of-the-art methods for real-time semantic segmentation have mainly focused on the manual-design of efficient network architectures. By employing highly optimized convolutional modules, ES-PNet [START_REF] Mehta | Espnet: Efficient spatial pyramid of dilated convolutions for semantic segmentation[END_REF] and ESPNetv2 [START_REF] Mehta | Espnetv2: A light-weight, power efficient, and general purpose convolutional neural network[END_REF] have achieved impressive accuracy-computation trade-offs. Other methods, such as [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF][START_REF] Zhao | Pyramid scene parsing network[END_REF], offer higher accuracy but at several orders of magnitude higher inference cost, limiting their application in resource constrained scenarios.

In Figure 7 (right) we compare our CNMM results to these two approaches. Note that the original results reported in [START_REF] Mehta | Espnetv2: A light-weight, power efficient, and general purpose convolutional neural network[END_REF] are obtained by using a model pre-trained in ImageNet. For a fair comparison with our CNMMs, we have trained EspNetv2 from scratch by using the code provided by the authors2 . As can be observed, CNMM provides a better trade-off compared to ESPNet. In particular, a full CNMM without pruning obtains an improvement of 0.5 points of mIoU, while reducing the FLOP count by 45%. Moreover, an accelerated CNMM achieves a similar performance compared to the most efficient ESPNet that needs more than two times more FLOPs. On the other hand, ESP-Netv2 gives slightly better trade-offs compared to our CN-MMs. However, this model relies on an efficient inceptionlike module [START_REF] Szegedy | Rethinking the inception architecture for computer vision[END_REF] that also includes group point-wise and dilated convolutions. These are orthogonal design choices that can be integrated in our model as well, and we expect that to further improve our results. Additionally, the different operating points in ESPNet and ESPNetv2 are achieved using different models trained independently. Therefore, unlike our approach, these methods do not allow for a finegrained control over the accuracy-computation trade-off, and multiple models need to be trained. Figure 8 shows qualitative results using different operating points from a single CNMM.

Conclusions

We proposed to address model pruning by using Convolutional Neural Mixture Models (CNMMs), a novel probabilistic framework that embeds a mixture of an exponential number of CNNs. In order to make training and inference tractable, we rely on massive parameter sharing across the models, and use concrete distributions to differentiate across the discrete sampling of mixture components. To achieve efficient inference in CNMM we use an early-exit mechanism that allows prediction after evaluating only a subset of the networks. In addition, we use a pruning algorithm to remove CNNs that have low mixing probabilities. Our experiments on image classification and semantic segmentation tasks show that CNMMs achieve excellent trade-offs between prediction accuracy and computational cost. Unlike most of previous works, a single CNMM model allows for a large number and wide range of accuracy-compute trade-offs, without any re-training.

A. Supplementary material

We provide further results on CIFAR100 in order to show the importance of all components of our proposed CNMMs. Moreover, we provide additional qualitative results of semantic segmentation on the CityScapes dataset.

A.1. Ablative study of CNMM Using sampling during training. During learning, CN-MMs generate a set of samples πst t-1 using Eq. ( 7). In contrast, during inference we use the expectations π st t-1 instead. In order to evaluate the importance of sampling during learning, we have optimized a CNMM by using the aforementioned expectations instead of samples. Figure 9 shows the results obtained by the model using this approach, denoted as "Training with expectations". We observe that, compared to the CNMM using sampling, the accuracy decreases faster when different pruning ratios are applied. We attribute this to the fact that our sampling procedure can be regarded as a continuous-relaxation of dropout, where a subset of functions f st t-1 (h t-1 t-1 ) are randomly removed when computing the output tensor h st t-1 . As a consequence, the learned model is more robust to the pruning process where some of the convolutional blocks are removed during inference. This is not the case when deterministic expectations are used in Eq. ( 7) rather than samples.

Comparison with a deterministic model. We compare the performance of our CNMM with a deterministic variant using the same architecture. Concretely, in Eq. ( 7) we ignore samples πst t-1 and simply sum the feature maps hst t-1

and ht-1 t-1 . Note that the resulting model is analogous to a MSDNet [START_REF] Huang | Multi-scale dense convolutional networks for efficient prediction[END_REF] using early-exit classifiers. We report the results in Figure 9, denoted as "Deterministic with earlyexits". We observe that our CNMM model obtains better performance than its deterministic counterpart. Moreover, same as MSDNets, accelerating the deterministic model is only possible by using the early-exits. In contrast, the complementary pruning algorithm available in CNMM allows for a finer granularity to control the computational cost. Expectation approximation during inference. In order to validate our approximation of p(y|X; θ) = E p(H T |X) [p(y|H T ; θ)] during inference, we evaluate the performance obtained by using a Monte-Carlo procedure for the same purpose. In particular, we generate N samples from the output distribution p(H T |H 0 ). Then, we compute the class probabilities p(y|H T ; θ) for each sample and average them. Table 1 shows the results obtained by varying the number of samples. We observe that our approach offers a similar performance as the Monte-Carlo approximation using N = 5. For a higher number of samples, we observe slight improvements in the results. However, note that a Monte-Carlo approximation is very inefficient since it requires N independent evaluations of the model. 7 of the main paper, the curves are obtained by using the optimal combination of early-exits and pruning when possible. In this manner, results for CNMM represent upper-envelope of all the different curves depicted in Fig. 6 of the main paper.

In particular, the last row in Table 1 is 30 times more costly to obtain than the two first rows. The minimal gain obtained with more samples could probably be more efficiently obtained by using a larger model.

A.2. Additional Qualitative Results

In Figure 10 we provide additional qualitative results for semantic segmentation obtained by a single trained CNMM model, using various opertating points with different number of FLOPs during inference.

Figure 1 .

 1 Figure 1. A Convolutional Neural Mixture Model embeds a large number of CNNs. Weight sharing enables efficient joint training of all networks and computation of the mixture output. The learned mixing weights can be used to remove networks from the mixture, and thus reduce the computational cost of inference.

Figure 2 .

 2 Figure 2. (Left) Illustration of how a large collection of CNNs is represented in a CNMM. Each network is uniquely identified by a non-decreasing sequence s0:T , containing numbers from 0 to T . Consecutive entries in the sequence determine the functions f s t s t-1

Figure 3 .

 3 Figure 3. Graphical model representation of the CNMM. The sequence s1:T codes for the CNN architecture. Each Ht is an intermediate feature map generated by the sampled CNN. It is computed from the previous feature map Ht-1 using f s t s t-1 .

Figure 4 .

 4 Figure 4. Top: Illustration of the algorithm used to sample intermediate feature maps from the mixture distribution. At each iteration t, we generate hs t t ∼ p(Ht|st, H0) by using: (i) samples ht-1 t-1

Figure 5 .

 5 Figure 5. Dense network with sparse connectivity implementing the inference algorithm of our CNMMs. See text for details.

Figure 6 .

 6 Figure 6. Prediction accuracy vs. FLOPs for accelerated CNMMs. Black curves depict the performance of a CNMM learned using a single final classifier. Colored curves correspond to intermediate classifiers at different steps of the inference algorithm. Points on one curve are obtained by progressively pruning convolutional layers.

Figure 7 .

 7 Figure 7. Comparison of the our CNMM with state-of-the-art efficient inference approaches on the CIFAR and CityScapes datasets. Disconnected markers refer to models that are trained independently. Curves correspond to a single model that can operate at different number of FLOPs. CNMM curves are obtained by using the optimal combination of pruning and intermediate classifiers.

Figure 8 .

 8 Figure 8. Pixel-level predictions for a single CNMM operating under different computational constraints. As discussed, our model allows to dynamically dynamically set the trade-off between accuracy and inference time with no additional cost.

Figure 9 .

 9 Figure 9. FLOPs vs. performance curves for our model (CNMM), and the variants described in Section A.1. As in Figure7of the main paper, the curves are obtained by using the optimal combination of early-exits and pruning when possible. In this manner, results for CNMM represent upper-envelope of all the different curves depicted in Fig.6of the main paper.

Figure 10 .

 10 Figure 10. Pixel-level predictions for a single CNMM adapting the number of FLOPs required during inference.

Table 1 .

 1 Comparison of the results obtained in CIFAR100 by approximating the CNMM output using our approach or a Monte-Carlo procedure with different number of samples N .

	Approximation	FLOPs Top-1 Accuracy
	Expectation (used)	93M	74.4
	Sampling N=1	93M	71.2
	Sampling N=5	463M	74.4
	Sampling N=15	1390M	74.5
	Sampling N=30	2780M	74.6

In particular, this constraint ensures that, e.g., the networkf 4 1 (f 1 0 (H 0 )) is uniquely encoded by the sequence '01444', ruling out the alternative sequences '01144' and '01114'. See Figure

(Left).

https://github.com/sacmehta/EdgeNets

Acknowledgements

This work is supported by ANR grants ANR-16-CE23-0006 and ANR-11-LABX-0025-01.