Title: No title found

Abstract: In this paper we propose a novel approach to model compression termed Architecture Compression. Instead of operating on the weight or filter space of the network like classical model compression methods, our approach operates on the architecture space. A 1-D CNN encoder/decoder is trained to learn a mapping from discrete architecture space to a continuous embedding and back. Additionally, this embedding is jointly trained to regress accuracy and parameter count in order to incorporate information about the architecture's effectiveness on the dataset. During the compression phase, we first encode the network and then perform gradient descent in continuous space to optimize a compression objective function that maximizes accuracy and minimizes parameter count. The final continuous feature is then mapped to a discrete architecture using the decoder. We demonstrate the merits of this approach on visual recognition tasks such as CIFAR-10/100, FMNIST and SVHN and achieve a greater than 20x compression on CIFAR-10.

1. INTRODUCTION:

The recent adoption of CNNs for real-time, on-device applications has fueled a great demand for better model compression. Conventional methods such as quantization, pruning and distillation have proven to be reliable approaches in reducing redundancies in networks. However, one avenue where there has been little progress is that of architecture space based compression.

Approaches such as Iandola et al. (2016 ), Howard et al. (2017) , Rastegari et al. (2016) , have introduced hand defined heuristics to design networks that are efficient without sacrificing accuracy. However, designing such networks still remains a laborious task, requiring much human expertise. In such a context, an efficient dataset-driven approach to determine the optimal architecture is desirable.

Recent methods such as Ashok et al. (2018) ; He et al.; Zhou et al. (2018) ; Tan et al. (2018) have proposed dataset-driven architecture based model compression using reinforcement learning. However, one drawback of such RL based methods is that they are less sample-efficient, often requiring a large number of architecture evaluations and several hours or days of training to find a single compressed model. Furthermore, it is unclear how these approaches compare to random search and whether they only succeed due to large-scale exploration and evaluation of many architectures.

To the best of our knowledge, this is the first paper to introduce a novel gradient descent based approach to perform architecture compression. To facilitate learning, we describe a mapping from discrete architecture space to a continuous space that encodes the structure of architecture for a specific dataset. We train a one-dimensional convolutional encoder/decoder neural network to learn the structure of discrete architecture space while using accuracy and parameter regressors to impose the structure inherent to learning the dataset. For compression, we encode an input architecture and leverage this learned continuous latent space to perform gradient descent on the encoded feature. The augmented feature is then decoded into a compressed discrete architecture.

We demonstrate the effectiveness of our approach on several visual learning tasks of varying difficulty (FMNIST, SVHN, CIFAR-10, CIFAR-100) and show 5-20x compression on architectures. We also compare this approach to conventional compression methods such as pruning, distillation and reinforcement learning and show that our architectures are smaller and faster than those produced by the baseline methods. Real et al. (2017) , that use reinforcement learning or evolutionary algorithms to traverse the space of architectures. These approaches characterize architectures as discrete entities in a non-differentiable space and use either a constrained state space or heuristics to discover architectures. These approaches have been subject to criticism from the machine learning community for using large amounts of computation.

Work such as Ashok et al. (2018) , Tan et al. (2018) , Zhou et al. (2018) , He et al. attempt to search for efficient architectures instead of just the best. However these approaches also currently rely on reinforcement learning. In contrast to these approaches, our method shows that we can leverage classical optimization techniques such as gradient descent to effectively search the space of architectures for a constrained objective. Methods such as Liu et al. (2018) and Luo et al. (2018) attempt to make the space of architectures differentiable however this work is focused on discovering repeatable convolutional cells instead of optimizing the architecture as a whole.

2.2. PRUNING, QUANTIZATION, HAND DESIGNED MODELS:

Pruning-based methods preserve the weights that matter most and remove the redundant weights LeCun et al. (1989) , Hassibi et al. (1993) , Srinivas & Babu (2015) , Han et al. (2015b) , Han et al. (2015a) , Mariet & Sra (2015) , Anwar et al. (2015) , Guo et al. (2016) . While pruning-based approaches typically operate on weight space, our approach operates on the the model architecture. Additionally, our method offers greater flexibility as we can use memory, inference time, power, and other hardware constraints to guide the compression process, resulting in the optimal architecture for a given dataset and constraints.

Hand designed models such as Iandola et al. (2016) and Howard et al. (2017) have been shown to work well in practical applications such as self-driving cars and mobile phones. These are good stepping stones in making progress in designing efficient architectures. Our work focuses on designing a general method to design such architectures in a fully automated data-driven manner.

3. STRUCTURE OF ARCHITECTURE COMPRESSION SPACE:

In this section we show how to map certain classes of architectures to a unique vector representation in order to enable learning. We then analyze the cardinality of architecture space for compression and prove that this space has several desirable properties for learning a mapping.

3.1. TOPOLOGICAL REPRESENTATION OF ARCHITECTURES:

We observe that most modern neural network architectures A ∈ A, with the exception of recurrent neural networks can be expressed as a directed acyclic graph (DAG). We use the property that every DAG has a topological ordering (Proof in section 7) to represent an architecture as a partially ordered sequence of layers, l i ∈ L. Formally,

l 1:N = [l 0 , l 1 ...l N ] such that ∀i, j ∈ [1, N ], i > j, l i → l j (1)

where the → operator denotes that the activation of l i is the input of l j . Furthermore, this topological ordering is unique (Proof in section 7.2) for standard convolutional networks and those with simple skip connections (e.g. ResNet). We will denote this ordered representation of an architecture as

o : A → L N : A → l 1:N (2)

where o is the topological sorting function. Note also that for unique, one-to-one mappings, there exists an inverse function o -1 to recover A given

EQUATION

3.2. CARDINALITY OF ARCHITECTURE COMPRESSION SPACE:

Let A ∈ A be an architecture that is parameterized by θ and trained on some dataset D. Then we can model the accuracy a ∈ [0, 1] as a continuous random variable stochastically sampled from a distribution P θ (a|A, D), since θ is typically optimized using a variant of stochastic gradient descent.

The expected accuracy E θ [a|A, D], while not exactly computable due to the large dimension of θ, can be approximated by training and evaluating the network under varying intializations θ 0 , i.e.

E θ [a|A, D] ≈ 1 N N i g θ (A, D, θ i ) (4)

where g minimizes an objective function over D with respect to θ. Thus, we are interested in learning a mapping from discrete architecture space to the expected accuracy

EQUATION

However, since we are interested in model compression, we also want to construct the inverse mapping from the expected accuracy to discrete architecture space for a given parameter count

EQUATION

In the following subsections, we prove that such a mapping, while not unique, is feasible to learn since the range of valid discrete architectures is finite.

For the following sections, we will denote parametric layers i.e. convolutional layers, batch normalization and fully connected layers as f θ (x), where x is the activation of the previous layer and θ represents the parameters of the layer.

Non-parametric pooling layers as max pooling and average pooling layers are written as q s (x), where s > 1 (no upsampling) is the stride of the layer. Lastly activations such as sigmoid, ReLU, softmax etc. are represented as σ(x).

We also make the following practical assumptions in the following proofs:

1. The input X ∈ R H×W ×C , where H, W, C ∈ N + and H, W, C are fixed.

2.. For layers l:

i ∈ A, if l i ∈ Σ, l i+1 / ∈ Σ,

where Σ is the set of possible activation functions. Proof. Let x i be the input of the ith layer with spatial dimension d i ∈ N + . We observe that a pooling operation with stride s ∈ N + > 1 and kernel size k

∈ N + x i+1 = q s (x i ) results in an output of d i+1 = di-k s + 1 < d i . Since d 0 is fixed (Assumption 1

) and s is discrete, for any d 0 there is a finite number of pooling layers possible in a valid architecture.

Theorem 3.2. For a given parameter constraint p, the set of valid architectures that meet the parameter constraint A p = {A| numParams(A) ≤ p} is finite.

Proof. Next, suppose we have a partially constructed network with parameter count p 0 . Then by assumption 2, we can add at most one activation function. Furthermore by Lemma 3.2, we have a finite choice of pooling layers such that the architecture still remains valid.

Suppose we add a parametric layer l i = f θi , the parameter constraint exceeded if p 0 + |θ i | > p. Thus, we have the upperbound |θ i | ≤ p -p 0 . Since |θ i | is discrete, we have a finite number of choices of layers such that the partially constructed network is still valid.

We then observe that since d i monotonically decreases if we add a pooling layer and the upperbound of |θ i | monotonically decreases if we add a parametric layer.

Since at least every other layer has to be one of these types, the length of any valid architecture is finite. Thus, we arrive at the conclusion that there are a finite number of valid architectures for a given parameter constraint.

4. APPROACH:

Having proved that a mapping is feasible, we now describe our approach to train a 1-dimensional convolutional encoder/decoder, an accuracy regressor and a parameter regressor to learn such a mapping (Outline in Fig. 1 ).

The variable length input vector to the network denoted by x 1:T = [x i , ..., x T ] ∈ Z 5×T is a topologically ordered representation of the architecture as per Section 3.1. Each layer is represented by the hyperparameters of each layer. Specifically, it is a discrete 5 dimensional vector as follows:

EQUATION

)

where t is the layer type, k the kernel size, o the number of output channels, s the stride and p the padding.

4.1. ENCODER AND DECODER:

The encoder is a one-dimensional convolutional neural network that takes as input the discrete architecture representation and outputs a continuous feature. Prior approaches use recurrent networks such as LSTMs or bidirectional RNNs where backpropagating through large sequences can result in vanishing gradients and difficult credit assignment Hochreiter et al. (2001) .

In our approach, we use a 1D-CNN encoder for several reasons. It can operate on variable length sequences, CNNs with sufficient depth have a large receptive field over the input sequence and it does not suffer from vanishing gradients since the length of gradient propagation is no longer a function of the sequence length but a function of the depth of the inference network.

The encoder E, computes the function: y = E(x 1:T ) (8) where x 1:T ∈ Z 5×T is a variable length sequence representing the architecture and y ∈ R N a continuous feature embedding. Details of the network can be found in the appendix.

The decoder has a similar residual 1D-CNN architecture as the encoder except that convolutions are replaced with transposed convolutions.

The decoder D, computes the function:

x * 1:T = D(y) (9) where x * 1:T ∈ R 5×T is a continuous variable length sequence representing the architecture and y ∈ R N a continuous feature embedding. The continuous variable x * 1:T is discretized to x1:T ∈ Z 5×T .

4.2. ACCURACY AND PARAMETER REGRESSORS:

The accuracy regressor and parameter regressor are two fully connected networks that take the continuous embedding of the architecture y as input and predict the expected accuracy, E θ [a] and parameter count, p of the architecture A.

The accuracy regressor learns the function a = f a (y) (10) where a ∈ [0, 1] ⊂ R is trained to predict a * = E θ [a] (which is approximated as per 3.2 by training the network with multiple intitializations). This network consists of 3 fc-relu blocks with a sigmoid output activation to convert the output to [0, 1].

The parameter regressor learns the function p = f p (y) (11) where p ∈ R + is trained to match the ground truth parameter count p * . The ground truth parameter count is computed as

p * = N i |li|-p σp

where |l i | is the number of parameters of each layer in the network. The mean parameter count p is subtracted to center the parameter count around 0 and the standard deviation of the parameter count σ p , is used to scale the parameter count for better conditioning of the range of the output. This network consists of 3 fc-relu blocks with a ReLU function to predict a non-negative real scalar.

4.3. OPTIMIZATION:

In order to learn to encode/decode the architecture and predict accuracy/parameter count, we jointly optimize a multi-task loss function. While all four tasks are formulated as regression problems, each has a differing domain. To account for this, we choose appropriate loss functions to best suit each task.

The decoder is trained to approximate positive integral values of varying scale since we may have small values for padding, kernel size, type and stride and large values for number of outputs. To enable faster convergence, we use a mean squared error.

EQUATION

A standard L-1 loss is used for the accuracy regressor since the output of the sigmoid function is bounded between

[0, 1]. L a (â, a * ) = |â -a * | 1 (13)

For training the parameter regressor, we use the Huber loss with δ = 1. This loss is less sensitive to outliers in the data and does not suffer from exploding gradients as described in Girshick (2015) . This is important since the domain of the parameter count is R and it is possible that the training set may have outliers such as large networks that do not converge.

EQUATION

)

The network is then trained to minimize the joint loss function: p * ← (num_params(A) -p)/σp 5:

EQUATION

x ← o(A) 6:

y ← encoder θ 1 (x) 7:

â ← acc_regressor θ 1 (y) 8:

p ← param_regressor θ 3 (y) 9:

x ← decoder θ 4 (y) 10:

L = Ld(x, x) + λ1La(â, a * ) + λ2Lp(p, p * ) 11: θ = argmin θ L 12:

end for 13: end procedure 14: procedure COMPRESS(A) 15:

x Once the inference network has converged and can predict the accuracy and number of parameters of a network, we use the network for architecture compression.

In order to compress an architecture, we perform gradient descent on the continuous embedding space using the compression objective function.

L c (â, p) = L a (â, 1) + λL p (p, 0)

The compression objective function simultaneously minimizes the number of parameters and maximizes the accuracy of the network to achieve compression. We can also incorporate known hardware constraints p 0 or accuracy requirements a 0 to relax this objective function by modifying it as follows

EQUATION

The gradient from this objective is then backpropagated to the continuous embedding y with learning rate η to generate a new embedding y .

EQUATION

)

The decoder converts this embedding into a temporal sequence x comp that is then discretized and converted into an architecture A comp = o -1 (x comp ). In this section, we empirically evaluate our approach, showing that it is capable of compressing networks by upwards of 10x by benchmarking them on modern classification tasks such as CIFAR-10, CIFAR-100, FMNIST and SVHN.We show that our approach outperforms current state of the art architecture compression techniques by comparing the results to several baselines. 

5. EXPERIMENTS:



5.1. DATASETS:

FMNIST The Fashion- MNIST Xiao et al. (2017) dataset consists of 28 × 28 pixel grey-scale images depicting images of fashion products from 10 categories. We use the standard 60,000 training images and 10,000 test images for experiments.

CIFAR-10:

The CIFAR-10 Krizhevsky & Hinton (2009) dataset consists of 10 classes of objects and is divided into 50,000 train and 10,000 test images (32x32 pixels). This dataset provides an incremental level of difficulty over the FMNIST dataset, using multi-channel inputs to perform model compression.

SVHN The Street View House Numbers Netzer et al. (2011) dataset contains 32x32 colored digit images with 73257 digits for training, 26032 digits for testing. This dataset is slightly larger that CIFAR-10 and allows us to observe the performance on a wider breadth of visual tasks.

CIFAR-100:

To further test the robustness of our approach, we evaluated it on the CIFAR-100 dataset. CIFAR-100 is a harder dataset with 100 classes instead of 10, but the same amount of data, 50,000 train and 10,000 test images (32x32). Since there is less data per class, there is a steeper size-accuracy tradeoff. In this section we evaluate the ability of our approach to compress architectures. For our experiments, we use a standard convolutional architecture consisting of stacked conv-bn-relu blocks and a fully connected layer. We use a 7 block network CONV-7 for Fashion-MNIST and 10 block network CONV-10 for the others. Table shows original average accuracy of the model on the validation set, followed by the number of parameters in the original model followed by two columns for the improvement in accuracy in the compressed architecture and the compression rate. We notice a minor improvement in accuracy by the compressed architecture in Fashion-MNIST while observing a minor drop in the other datasets. Additionally, our method is able to achieve solid compression on all the datasets and up to 20x compression on CIFAR-10 (1.2M parameters for final compressed architecture).

5.2. COMPRESSION EXPERIMENTS:



5.2.1. BASELINES:

We compare our approach to various model compression baselines including reinforcement learning, pruning and knowledge distillation on the CIFAR-10 dataset. The experiments show that our approach is able to find a smaller and more accurate model than the other approaches. 

6. CONCLUSION:

In conclusion, we have described a novel approach to compress CNNs by first training a continuous embedding on a representation of the architecture and then performing gradient descent to determine an optimal architecture for the given task. We also introduced a novel theoretical analysis of CNNs which we hope will inspire future work. We also demonstrate that our method performs well over a variety of computer vision datasets. Given that this is a novel direction of research, we note that there exist multiple future directions to go. Expanding the search space to include networks of greater complexity such as ResNets or DenseNets would be of practical interest. Analyzing the transfer learning properties of this approach via the reuse of the weights for other tasks would be of great practical use as well.

Since v has no incoming edges, no partial order is violated by placing v at the head of the topologically ordered sequence.

Thus T = [v, T * ] is a valid topological ordering of G and the lemma is proven.

Lemma 7.2. If a topological sort l 1:T = [l 0 ...l i ...l T ] has the property that ∀i, ∃ edge(i, i + 1), then it is unique Proof. It follows directly that the above property implies that there exists a Hamiltonian path on the graph since traversing the graph in the topologically sorted order satisfies each node being visited once. We can then show that the existence of a Hamiltonian path in a DAG implies unique ordering.

Suppose a DAG has two Hamiltonian paths, then let x ∈ P 1 , y ∈ P 2 be the first nodes on the paths (P 1 , P 2 ) that differ.

This implies that there is a path from x → y that is a subpath of P 1 and a path from y → x that is a subpath of P 2 . This implies a cycle in the graph, which is a contradiction. 8 DETAILS ON 1-D CNN ARCHITECTURE Let x i ∈ Z K×T be the ith activation or in the case of the first layer, the discrete representation of an architecture. Then a 1-d convolution operation applies a filter w ∈ R L×K to a window of L features in the input vector. We then add a bias b ∈ R to this output, to produce a feature map h i . Finally we apply a batch normalization function g, an activation function σ and add the residual to produce a new activation x i+1 as follows. Appropriate padding is added to the output in order to preserve the dimension and allow element-wise addition of the residual.

h i = w * x i + b ĥi = g(h i ) x i+1 = σ( ĥi ) + x i

In the case of a strided convolution where the temporal dimension of the output is smaller than the original input, we apply a convolution with the same stride s. The operations then become the following.

h i = f s (x i , w 1 , b 1 ) = g(h i ) xi = f s (x i , w 2 , b 2 ) x i+1 = σ( ĥi ) + xi

where f s (x, w, b) performs convolutions on input x with stride s, weights w and bias b.

9. SAMPLING OF RANDOM ARCHITECTURES:

In section 4.4, we describe a set of randomly generated architectures that are trained and then used to learn a continuous architecture search space. In this section, we detail how this set of architectures is generated.

In order to generate a sensible set of architectures, we randomly sample architectures and then reject degenerate architectures.

First we sample the length of the architecture randomly from a discrete unifrom distribution l ∼ U (2, 50). We set the lower bound to be 2 since we need at least one classification layer (fully connected) and one convolution layer for the architecture to be valid. Furthermore, we set the upperbound to 50 layers as an arbitrary limit that is within experimental constraints.

After this, we sample the 5 layer configuration variables for each of the l layers randomly. Specifically, t ∼ U (1, 8) where: For layers that do not have certain configuration variables (e.g. batch normalization has no stride), we set the variable to be 0. For certain layers like MaxPool, ReLU or BatchNorm that do not change the number of output channels, we set the variable to the number of input channels. Furthermore, We also enforce that the number of input channels to the first is the same as the input of the task example and that the final layer is a fully connected layer with the number of outputs corresponding to the number of classes in the task.

Lastly, we filter out degenerate architectures if they do not contain any convolutional layers, the output dimension is too small to proceed or the memory/computational footprint is too large to be practical.

:



Figures and Tables:

Figure 1: High level overview of 1D-CNN encoder-decoder system

Figure 2: Structure of architecture compression spaces with forward (blue) and backward (red) mappings visualized

Figure 3: Joint training loss on (from top-bottom) FMNIST, SVHN, CIFAR-10, CIFAR-100

In the following experiments, we used a randomly generated dataset of 1500 architectures for training the encoder/decoder and regressors. Each architecture was trained for each task for 5 epochs with m=5 different random initializations to obtain a target expected accuracy. As observed in Ashok et al. (2018); Zoph & Le (2016); Tan et al. (2018), 5 epochs of training seems to provide sufficient signal about the convergence characteristics of the network. All of the following experiments were run on 2x NVIDIA 1080TI GPUs. Additional training details such as choice of optimizer and hyperparameters are included in Section 10 in the appendix.

Figure 4: First 100 layer 1 filters for encoder (left) and decoder (right). Each column represents an input channel and rows represent filters.

∼ U (1, 10), s ∼ U (1, 10), o ∼ U (16, 4096), p ∼ U (1, 10).

Summary of compression results

Table content: <table><tr><td>Model</td><td>Acc.</td><td colspan="2">#Params ∆ Acc. Compr</td></tr><tr><td/><td/><td>Fashion-MNIST</td></tr><tr><td>CONV-7</td><td colspan="2">91.46% 708K</td><td>+0.98% 7.61x</td></tr><tr><td/><td/><td>CIFAR-10</td></tr><tr><td colspan="3">CONV-10 92.35% 24.4M</td><td>-0.04% 20.33x</td></tr><tr><td/><td/><td>CIFAR-100</td></tr><tr><td colspan="3">CONV-10 70.95% 24.4M</td><td>-1.32% 4.51x</td></tr><tr><td/><td/><td>SVHN</td></tr><tr><td colspan="3">CONV-10 96.02% 24.4M</td><td>-0.63% 8.76x</td></tr></table>

Baselines on CIFAR-10

Table content: <table><tr><td>Model</td><td>Acc.</td><td>#Params</td></tr><tr><td colspan="3">Romero et al. (2014) (Distillation) 91.33% 1.2M</td></tr><tr><td colspan="3">Molchanov et al. (2016) (Pruning) 91.06% 2.3M</td></tr><tr><td>Ashok et al. (2018) (RL)</td><td colspan="2">92.05% 1.7M</td></tr><tr><td>Ours</td><td colspan="2">92.31% 1.2M</td></tr></table>

Peer review (iclr2019):
 Even though many people have considered prunning as architecture search, it has not been explored enough so far. This paper comprises a good approach for compression of achitectures using pruning. Based on the uniqueness of the topological ordering of commonly used neural networks (feed forward, skip connection), the paper proposes a simple and easily manipulable vector (sequence) representation for a wide class of neural networks. Instead of using RNN networks, such long seqeunce representation are mapped to a continuous embedding by 1D-CNN. While training this embedding, for the purpose of compression, predictors needed for compression are jointly trained with embedding. Consequently, the proposed method presents a possiblity of including many other constraints during the architecture search. In the specification of layers, the layer type is just appointed to an integer variable, even though in reality the layer type is a categorical variable. This choice is ok for standard neural network layers, where effectively the choice is between a single catecorical aspect. However, for more sophisticated layer configurations, where you may need many categorical choices, this model choice will not be adequate and will likely lead to artificially biased design choices. The authors should explain the limitations of this model design and propose methods these limitations can be tackled. The overall model achieves quite good result in compression. On CIFAR10 the model show good performance as compared to existing compression methods. It should be noted that other methods start with a given stucture, so their search space is more limited than this paper*s approach. Specifically, compared to those methods, the search space for the proposed paper is larger because although the number of layers is fixed, the connections between layers give more freedom to the compression algorithm. Currently, the number of experiments is borderline. They are enough to indicate the potentials of this approach. However, additional experiments would be welcome. For one, it would be to evaluate the proposed model in more challenging setups: evaluate on ImageNet dataset, using some of the recent architectures (e.g., ResNet, VGGnet, and so on). What is more, for more compressed architectures with better accuracy, when searching for a compressed architecture global optimization methods like Bayesian Optimization is worth to try, for instance using the recently proposed BOCK (Oh et al, ICML 2018). Some additional comments. - For a finite number of edges the number of possible graphs (including the valid architecture) are finite when the input is finite and pooling reduces the feature map size. Thus, it seems that the statement in theorem 3.2 is rather trivial and it is not worth calling it a Theorem. Overall, this was an interesting paper to read and worth of acceptance, provided that the proposed method delivers also in more competitive experimental settings.