Compressing neural nets is an active research problem, given the large size of state-of-the-art nets for tasks such as object recognition, and the computational limits imposed by mobile devices. We give a general formulation of model compression as constrained optimization. This includes many types of compression: quantization, low-rank decomposition, pruning, lossless compression and others. Then, we give a general algorithm to optimize this nonconvex problem based on the augmented Lagrangian and alternating optimization. This results in a "learning-compression" algorithm, which alternates a learning step of the uncompressed model, independent of the compression type, with a compression step of the model parameters, independent of the learning task. This simple, efficient algorithm is guaranteed to find the best compressed model for the task in a local sense under standard assumptions. We present separately in several companion papers the development of this general framework into specific algorithms for model compression based on quantization, pruning and other variations, including experimental results on compressing neural nets and other models. Large neural network models have become a central component in state-of-the-art practical implementations of the solution to various machine learning and artificial intelligence problems. These include, for example, classification problems involving images, audio or text, or reinforcement learning problems involving game playing or robot manipulation and navigation. This has also resulted in an enormous increase in the interest in deep neural net models from researchers in academy and industry, and even from non-experts and the public in general, as evidenced by the amount of scientific papers, blog entries or mainstream media articles published about it. These practical successes in difficult problems have ocurred thanks to the availability of large-scale datasets and of massive computational power provided by GPUs, which are particularly well suited for the kind of linear algebra operations involved in training a neural net (such as stochastic gradient descent). One notable characteristic of deep neural nets that seems to distinguish them from other machine learning models is their ability to grow with the data. That is, as the size of the training set grows, we can continue to increase the (say) classification accuracy by increasing the size of the neural net (number of hidden units and of layers, and consequently the number of weights). This is unlike, for example, a linear model, whose classification accuracy will quickly stagnate as the data keeps growing. Hence, we can continue to improve the accuracy of a neural net by making it bigger and training on more data. This means that we can expect to see ever larger neural nets in future practical applications. Indeed, models reported in the literature of computer vision have gone from less than a million weights in the 1990s to millions in the 2000s and, in recent works, to models exceeding billions of weights (each a floating-point value). The large size of the resulting model does cause an important practical problem when one intends to deploy it in a resource-constrained target device such as a mobile phone or other embedded systems. That 1 is, the large neural net is trained in a resource-rich setting, e.g. GPUs and a multicore architecture with large memory and disk, where the model designer can explore different model architectures, hyperparameter values, etc. until a model with the best accuracy on a validation set is found. This final, large model is then ready to be deployed in practice. However, the target device will typically have far more restrictive computation constraints in memory size and speed, arithmetic operations, clock rate, energy consumption, etc., which make it impossible to accommodate the large model. In other words, we can only deploy models of a certain size. Download bandwidth is also significantly limited in apps for mobile phones or software for cars. This problem has attracted considerable attention recently. Two important facts weigh upon it which have been known for some time among researchers. The first is that the large neural nets that we currently know how to train for optimal accuracy contain significant redundancy, which makes it possible to find smaller neural nets with comparable accuracy. The second is that, for reasons not entirely understood, one typically achieves a more accurate model by training a large model first and then somehow transforming it into a smaller one ("compressing" the model), than by training a small model in the first place. This leads us to the problem of compressing a neural net (or other model), which is our focus. Compressing neural nets has been recognized in recent years as an important problem and various academic and industrial research groups have shown that one can indeed significantly compress neural nets without appreciable losses in accuracy (see related work below). However, the solutions proposed so far are somewhat ad-hoc in two senses. First, they define a specific compression technique (and a specific algorithm to find the compressed model) which may work well with some types of models but not others. Second, some of these solutions are not guaranteed to be optimal in the sense of achieving the highest classification accuracy for the compression technique considered. In this paper, we provide a general formulation of model compression and a training algorithm to solve it. The formulation can accommodate any compression technique as long as it can be put in a certain mathematical form, which includes most existing techniques. The compression mechanism appears as a black box, so that the algorithm simply iterates between learning a large model and compressing it, but is guaranteed to converge to a locally optimal compressed model under some standard assumptions. In separate papers, we develop specific algorithms for various compression forms, such as quantization (Carreira-Perpiñán and Idelbayev, 2017a) or pruning (Carreira-Perpiñán and Idelbayev, 2017b), and evaluate them experimentally. In the rest of this paper, we discuss related work (section 2), give the generic formulation (section 3) and the generic LC algorithm (section 4), give conditions for convergence (section 5) and discuss the relation of our LC algorithm with other algorithms (section 6) and the relation with generalization and model selection (section 7). In a general sense, we can understand model compression as replacing a "large" model with a "small" model within the context of a given task, and this can be done in different ways. Let us discuss the setting of the problem that motivates the need for compression. Assume we define the machine learning task as classification for object recognition from images and consider as large model f (x; w): X → Y a deep neural net with inputs x ∈ X (images), outputs y ∈ Y (object class labels) and real-valued weights w ∈ R P (where the number of weights P is large). In order to train a model we use a loss L(), e.g. the cross-entropy on a large training set of input-output pairs (x n , y n ). Also assume we have trained a large, reference neural net f (x; w), i.e., w = arg min w L(f (·; w)), and that we are happy with its performance in terms of accuracy, but its size is too large. We now want a smaller model h(x; Θ): X → Y that we can apply to the same task (classifying input images x into labels y). How should we define this smaller model? One possibility is for the small model h(x; Θ) to be of the same type as the reference model f but reparameterized in terms of a low-dimensional parameter vector. That is, we construct weights w ∈ R P from low-dimensional parameters Θ ∈ R Q via some transformation w = ∆(Θ) so that the size of Θ is smaller than the size of w, i.e., Q < P (obviously, this will constrain the possible w ∈ R P that can be constructed). In the example before, h(x; Θ) would be the same deep net but, say, with weight values w = ∆(Θ) quantized using a codebook with K entries (so Θ contains the codebook and the assignment of each weight w i to a codebook entry). A second possibility 2 is for the small model h(x; Θ) to be a completely different type of model from the reference, e.g. a linear mapping with parameters Θ (so there is no relation between w and Θ). Given this, we have the following options to construct the small model h(x; Θ): • Direct learning: min Θ L(h(x; Θ)): find the small model with the best loss regardless of the reference. That is, simply train the small model to minimize the loss directly, possibly using the chain rule to compute the gradient wrt Θ. This approximates the reference model indirectly, in that both f and h are trying to solve the same task. We can have the small model h be a reparameterized version of f or a completely different model. Direct learning is the best thing to do sometimes but not always, as noted later. • Direct compression (DC): min Θ w − ∆(Θ) 2 : find the closest approximation to the parameters of the reference model, using a low-dimensional parameterization ∆(Θ). This forces h and f to be models of the same type. Direct compression can be simply done with (lossless or lossy) compression of w, but it generally will not be optimal wrt the loss since the latter is ignored in learning Θ. We discuss this later in detail. • Model compression as constrained optimization: this is our proposed approach, which we describe in section 3. It forces h and f to be models of the same type, by constraining the weights w to be constructed from a low-dimensional parameterization w = ∆(Θ), but h must optimize the loss L. • Teacher-student : min Θ X p(x) f (x; w) − h(x; Θ) 2 dx: find the closest approximation h to the reference function f , in some norm. The norm over the domain X may be approximated with a sample (e.g. the training set). Here, the reference model f "teaches" the student model h. We can have the small model h be a reparameterized version of f or a completely different model. Most existing compression approaches fall in one of these categories. In particular, traditional compression techniques have been applied using techniques most related to direct training and direct compression: using low-precision weight representations through some form of rounding (see Gupta et al., 2015; Hubara et al., 2016 and references therein), even single-bit (binary) values (Fiesler et al., 1990; Courbariaux et al., 2015; Rastegari et al., 2016; Hubara et al., 2016; Zhou et al., 2016) , ternary values (Hwang and Sung, 2014; Li et al., 2016; Zhu et al., 2017) or powers of two (Marchesi et al., 1993; Tang and Kwan, 1993) ; quantization of weight values, soft (Nowlan and Hinton, 1992; Ullrich et al., 2017) or hard (Fiesler et al., 1990; Marchesi et al., 1993; Tang and Kwan, 1993; Gong et al., 2015; Han et al., 2015) ; zeroing weights to achieve a sparse model (Hanson and Pratt, 1989; Weigend et al., 1991; LeCun et al., 1990; Hassibi and Stork, 1993; Reed, 1993; Yu et al., 2012; Han et al., 2015) ; low-rank factorization of weight matrices (Sainath et al., 2013; Denil et al., 2013; Jaderberg et al., 2014; Denton et al., 2014; Novikov et al., 2015) ; hashing (Chen et al., 2015) ; and lossless compression, such as Huffman codes (Han et al., 2016) . Some papers combine several such techniques to produce impressive results, e.g. Han et al. (2016) use pruning, trained quantization and Huffman coding. Although we comment on some of these works in this paper (particularly regarding the direct compression approach), we defer detailed discussions to our companion papers on specific compression techniques (quantization in Carreira-Perpiñán and Idelbayev, 2017a and pruning in Carreira-Perpiñán and Idelbayev, 2017b, so far). The teacher-student approach seems to have arisen in the ensemble learning literature, inspired by the desire to replace a large ensemble model (e.g. a collection of decision trees), which requires large storage and is slow at test time, with a smaller or faster model with similar classification accuracy (Zhou, 2012, section 8.5). The smaller model can be of the same type as the ensemble members, or a different type of model altogether (e.g. a neural net). The basic idea is, having trained the large ensemble on a labeled training set, to use this ensemble (the "teacher") to label a larger, unlabeled dataset (which may be available in the task at hand, or may be generated by some form of sampling). This larger, labeled dataset is then used to train the smaller model (the "student"). The hope is that the knowledge captured by the teacher is adequately represented in the synthetically created training set (although the teacher's mistakes will also be represented in it), and that the student can learn it well even though it is a smaller model. More generally, the approach can be applied with any teacher, not necessarily an ensemble model (e.g. a deep net), and the teacher's labels may be transformed to improve the student's learning, e.g. log-outputs (Ba and Caruana, 2014) or other manipulations of the output class probabilities (Hinton et al., 2015) . However, from a compression 3 point of view the results are unimpressive, with modest compression ratios (Hinton et al., 2015) or even failure to compress (using a single-layer net as student needs many more weights than the teacher deep net; Ba and Caruana, 2014). One practical problem with the teacher-student approach is that all it really does is construct the artificial training set, but it leaves the design of the student to the user, and this is a difficult model selection problem. This is unlike the compression approaches cited above, which use the teacher's model architecture but compress its parameters. In this work we understand compression in a mathematically specific sense that involves a learning task that we want to solve and a large model that sets the reference to meet. It is related to the direct training and direct compression concepts introduced above. Assume we have a large, reference model f (x; w) with P parameters (e.g. a neural net with inputs x and weights w ∈ R P ) that has been trained on a loss L() (e.g. cross-entropy on a given training set) to solve a task (e.g. classification). That is, w = arg min w L(w), where we abuse the notation to write the loss directly over the weights rather than L(f (x; w)), and the minimizer w may be local. We define compression as finding a low-dimensional parameterization ∆(Θ) of w in terms of Q < P parameters Θ. This will define a compressed model h(x; Θ) = f (x; ∆(Θ)). We seek a Θ such that its corresponding model has (locally) optimal loss. We denote this"optimal compressed" and write it as Θ * and w * ≡ ∆(Θ * ) (see fig. 1 ). Ordinarily, one could then solve the problem directly over Θ: Θ * = arg min Θ L(∆(Θ)). This is the direct learning option in the previous section. Instead, we equivalently write model compression as a constrained optimization problem: min  The reason, which will be useful later to develop an optimization algorithm, is that we decouple the part of learning the task, L(w) in the objective, from the part of compressing the model, w = ∆(Θ) in the constraints.
Much work exists on compressing neural nets, using quantization, low-rank decomposition, pruning and other techniques, see REF and references therein.
Model compression as constrained optimization, with application to neural nets. Part I: general framework
ArXiv
ArXiv
Computer Science Mathematics