{'fraction_non_alphanumeric': 0.031526568331259996, 'fraction_numerical': 0.017878087791007642, 'mean_word_length': 4.750255466993664, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Class-dependent Compression of Deep Neural Networks

Today’s deep neural networks require substantial computation resources for their training, storage and inference, which limits their effective use on resource-constrained devices. On the one hand, many recent research activities explore different options of compressing and optimizing deep models. On the other hand, in many real-world applications we face the class imbalance problem, e.g., higher number of false positives produced by a compressed network may be tolerable, yet the number of false negatives must stay low. The problem originates from either an intrinsic nature of the imbalanced samples within the training data set, or from the fact that some classes are more important for the application domain of the model, e.g., in medical imaging. In this paper, we propose a class-dependent network compression method based on a newly introduced network pruning technique used to search for lottery tickets in an original deep network. We introduce a novel combined loss function to find efficient compressed sub-networks with the same or even lower number of false negatives compared to the original network. Our experimental evaluation using three benchmark data sets shows that the resulting compressed sub-networks achieve up to 50% lower number of false negatives and an overall higher AUC-ROC measure, yet use up to 99% fewer parameters compared to the original network.


Introduction
While deep networks are a highly successful model class, their large memory footprint puts considerable strain on energy consumption, communication bandwidth and storage requirements of the underlying hardware, and hinders their usage on resource-constrained IoT devices. For example, VGG-16 models for object detection (Simonyan and Zisserman 2014) and facial attribute classification (Lu et al. 2017) both contain over 130M parameter. Research activities on the model size reduction gained significant attention in the past years. Both theoretical analysis and empirical experiments in machine learning showed evidence of redundancy in deep models (Aghasi, Nguyen, and Romberg 2016). Also in neuroscience, recent studies point out that there is a significant number of redundant neurons in human brain and memory, that may relate to vanishing of specific synapses (De Vivo et al. 2017). This indicates that it should be possible to compress deep networks without or with little loss of prediction quality.
Recent efforts on deep model compression for embedded devices explore several directions including quantization, factorization, pruning, knowledge distillation, and efficient network design. The main idea of quantization and binarization is to use weights with discrete values. Factorization explores the low-rank basis of filters to reduce model size. Pruning removes weak network connections, while efficient network designs explore the strategies of training a performant network from scratch. Knowledge distillation methods compress a network by transferring knowledge from a larger teacher to a smaller student network. The approach presented in this paper combines network pruning with efficient network design. We additionally include class-dependency into the network compression task.
Many real-world applications, e.g., medical image classification and anomaly detection in production processes, have to deal with class imbalance when training a deep model. On the one hand, real-world data often follows a long-tailed data distribution in which a few classes account for the most of the data, while many classes have considerably fewer samples. Models trained on these data sets are biased toward dominant classes (Cui et al. 2019). Related literature treats class imbalance as a problem which leads to low model quality (Chawla et al. 2002). The proposed solutions typically adopt class re-balancing strategies such as re-sampling and re-weighting based on the number of observations in each class. On the other hand, there are many applications, which have an intrinsic unbalanced class importance: e.g., missing an event may have far more severe consequences than triggering a false alarm. This is especially the case in many detection scenarios and early warning systems in the IoT domain. In this paper, we focus on keeping the number of false negatives low when compressing a deep network.
To the best of our knowledge, this is the first paper proposing a class-dependent model compression. The proposed compression algorithm is based on the lottery ticket (LT) hypothesis (Frankle and Carbin 2018) and leverages the method of finding LT networks described in (Zhou et al. 2019). We extend the basic algorithm towards class-dependency by suggesting a novel loss function, which reduces the number of false negatives for a certain class, while optimizing the average area under the receiver operating characteristics (AUC-ROC) measure for all classes. The contributions of this paper are summarized as follows: We propose a class-dependent compression method which incorporates a joint false negatives and AUC-ROC optimization. We evaluate the new method on three public data sets and show that it achieves up to 50 % lower number of false negatives than the original network while preserving only 1 % of the weights. Surprisingly, our method with a novel loss function combined with the LT algorithm consistently outperforms its original version in all tested cases.

Class-dependent Network Compression
This section presents our deep network compression method which reduces the number of false negatives for a desired class while maximizing the overall AUC-ROC measure and the network performance. The method is based on a combination of iterative pruning with a novel combined loss function. Below we describe the proposed algorithm in detail. Lottery Ticket (LT) algorithm. Our class-dependent network compression method leverages the recently introduced in (Frankle and Carbin 2018) iterative pruning used to search for efficient sparse sub-networks called lottery tickets (LT) within an original deep network. LT networks often show superior performance when compared to the original network. The recently conducted analysis of LT networks (Zhou et al. 2019) suggests that the sub-network structure tightly coupled with network initialization are crucial to high performance of LT networks. Moreover, the authors report that the following conditions are responsible for the best results: 1) setting pruned values to zero rather then to any other value, 2) keeping the sign of the initialization weights during rewinding, and 3) keeping the weights with the largest absolute values or apply the magnitude increase mask criterion during iterative pruning. We leverage all these findings in this work. We use the magnitude increase criterion throughout the paper, i.e., we rank the differences between the final and the initial values of the weights in every round and prune the least p%.
Algorithm 1 Class-dependent network compression 1: Randomly initialize the network f (x; m W 0 ) with the initial trivial pruning mask m = 1 |W0| ; 2: Train the network for n iterations with the class-dependent loss L producing the network f (x; m W k ); 3: Prune p% of the remaining weights with the magnitude increase strategy, i.e., m[i] := 0 if W k [i] gets pruned; 4: Replace remaining weights W k with their initial values W 0 ; 5: Repeat from step 2 if the next (k + 1) round is required.
Alg. 1 provides a pseudo-code of the LT algorithm with the magnitude increase mask criterion and a class-dependent loss function L explained below. The algorithm initializes the network with random weights W 0 and applies an initially trivial pruning mask m = 1 |W0| . The operation denotes an element-wise multiplication. After training the network for n iterations we prune p% of the weights using the magnitude increase strategy by updating the mask m accordingly. The remaining weights W k are then reset to their initial values W 0 before the next round of the LT algorithm starts.
In every round of the LT algorithm we minimize a classdependent loss function L of the following form where L wCE and L SHR are a weighted binary cross-entropy loss and a squared hinge ranking loss respectively detailed below. The parameter λ controls the relative importance of the squared hinge ranking loss.
Weighted binary cross-entropy loss. Inspired by (Cui et al. 2019), we extend the notion of the classical binary crossentropy to achieve class dependency by introducing perclass weighting coefficients as follows where γ c are weighting coefficients for every class; M denotes the number of classes; y o,c ∈ {0, 1} is a binary indicator if the class label c is a correct classification for the observation o; p o,c is a predicted probability that the observation o is of class c, and n c is the number of samples in the class c.
We leverage the results in (Huang et al. 2016;Wang, Ramanan, and Hebert 2017) and handle the weighting coefficients γ c for individual classes as γ c = 1−β 1−β nc , where β ∈ [0; 1) is a hyperparameter. In contrast to their work, we choose the value of the hyperparameter β to steer the class imbalance in favour of a particular class. The setting β = 0 corresponds to no class weighting and β → 1 corresponds to weighting by inverse class frequency. Class weighting allows focusing on a specific class and thus punishes the classifier for misclassifications with respect to this class. This allows controlling the boundary between classes by changing the ratio between false positives and negatives and maintaining a low number of false negative for the desired class when compressing a deep network. Recent work by (Cui et al. 2019) shows that the weighting coefficients γ c play an important role in class-balancing. In particular, when training a CNN on imbalanced data, class-balancing by means of γ c provides a significant boost to the performance of the commonly used loss functions, including cross-entropy. Our results provide an additional confirmation of this statement. Squared hinge ranking loss. The previous literature showed that 1) optimizing classification accuracy by minimizing cross-entropy cannot guarantee maximization of the AUC-ROC (Cortes and Mohri 2004), and 2) AUC-ROC maximizaion as an optimization task yields a discontinuous non-convex objective function and thus cannot be approached by the gradient based methods (Yan et al. 2003). Proposed solutions for AUC-ROC maximizaion (Brefeld and Scheffer 2005;Gultekin et al. 2018;Eban et al. 2016) Figure 1: Images from the ISIC data set (Gutman et al. 2016): benign (left) and melanoma (right) samples. are based on approximations or surrogate functions. In this paper, we use the squared hinge ranking loss suggested in (Steck 2007).
The squared hinge ranking loss is obtained from the hinge loss by replacing p o,c by a sorted in ascending order classifier output r o,c , i.e., the smallest output value gets assigned the lowest rank.
The authors of (Steck 2007) show that AUC-ROC can be written in terms of the hinge rank loss as follows where n + , n − are the number of positive and negatives samples and C is a constant independent of the rank order. Minimizing hinge ranking loss leads to AUC-ROC maximization (Steck 2007). We use the squared hinge ranking loss L SHR to ensure our loss function L is differentiable.
In the next section we evaluate the effectiveness of the proposed class-dependent network compression algorithm on three benchmark data sets.

Experimental Evaluation
This section introduces the benchmark data sets, lists the metrics we use to evaluate the performance of our method, justifies the parameter choice we make, and the presents the final performance results.

Data Sets
We chose our benchmark data sets based on the complexity of the classification task they present. MNIST is a fairly easy classification challenge confirmed by the almost 100% accuracy reported by the state-of-the-art deep models. ISIC is a highly challenging medical imaging lesion classification data set introduced in a data science competition 1 . The CRACK data set enjoys an intermediate complexity. All three benchmarks are shortly introduced below.   (Perez et al. 2018).
MNIST is a well-known database of handwritten digits comprising 60'000 train and 10'000 test examples. The digits (0-9) have been size-normalized and centered in a fixedsize image of 28×28 pixels (LeCun et al. 1998). ISIC-2016 lesion classification dataset (Gutman et al. 2016) includes original medical images paired with a confirmed malignancy diagnosis labels obtained from expert consensus and pathology report information, i.e., each image is assigned a label either benign or melanoma. The training data set contains 900 dermoscopic lesion images with 173 positive and 727 negative examples respectively, whereas the test set includes 379 images with 76 positive and 303 negative samples respectively. Fig. 1 shows positive and negative sample images from the ISIC data set. We use the data augmentation techniques suggested in (Perez et al. 2018) to increase the number of training samples in the ISIC data set. These augmentations are used to improve the results of the ISIC classification challenge. Table 1 summarizes the augmentation operations applied to the training data. Saturation, contrast and brightness augmentations simulate changes in color due to camera settings and lesion characteristics. Affine transormation reproduces camera distortions and creates new lesion shapes. Elastic warp is generated by defining the origins as an evenly-spaced 4 × 4 grid of points, and destinations as random points around the origins (by up to 10% of the image width in each direction). These augmentations produce new lesion shapes while maintaining medical attributes (Perez et al. 2018). CRACK data set (Özgenel 2017) contains 40K images of 224×224 pixels sliced from 500 full resolution images of 4032×3024 pixels taken from the walls and floors of several concrete buildings. The images are taken approximately 1 m away from the surfaces with the camera directly facing the target. The concrete surfaces have variation in terms of surface finishes (exposed, plastering and paint). The label is positive if an image contains a crack and negative otherwise. The labels are assigned by the material science experts. Fig. 2 shows positive and negative samples in this data set.

Evaluation Metrics
In this work we adopt the following evaluation metrics: AUC-ROC measure estimates the probability that a randomly chosen member of a positive class has a smaller estimated probability of belonging to a negative class than a randomly chosen member of a negative class (Steck 2007): where n + , n − are the number of positve and negatives samples and 1 is the indicator function. r + i ∈ 1, ..., n + denotes the rank of postive examples and r − j ∈ 1, ..., n − denotes the rank of negative examples. Accuracy is the proportion of true results (both true positives and true negatives) among the total number of cases: False negative rate (FNR) / false positive rate (FPR) are the ratios of positive / negative outcomes wrongly categorized as negative / positive in the total number of the actual positive / negative events: We use the FNR measure to show that the proposed method indeed decreases the number of false negatives. We also report the FPR measure to understand the achieved trade-offs between false positive and negative rates. AUC-ROC measure presents the average true positive rate across all possible false positive rate of all classes. In addition, AUC-ROC is more useful when we have to deal with imbalanced classes. The results in (Cortes and Mohri 2004) show that the expected value of AUC-ROC over all classifications is a monotonic function of accuracy. This also holds for imbalanced data. In this work we report the accuracy measure to confirm the statement and ensure that the overall compressed network performance stays high.

Experimental Setup
For simplicity, we conduct a binary classification for the MNIST data set, i.e., given a class, we perform one-versusall classification. The results are then averaged over all 10 classes and we also provide the standard deviation where appropriate. We enforce class imbalance in the CRACK data set by using 20K images in the negative class (no crack), add 4K images of the positive class, and use 70 %, 15 %, 15 % of samples for train, validation and test, respectively. Networks. We use LeNet-5 (LeCun et al. 1998) with 43'746 parameters for MNIST binary classification. For classification on the ISIC-2016 and CRACK data sets, we adopt AlexNet (Krizhevsky, Sutskever, and Hinton 2012) pretrained on ImageNet (Deng et al. 2009) with an adjusted number of fully-connected layers to contain 256, 8, and 2 neurons. This network has 2'471'842 parameters. Since our compression method uses iterative pruning based on the LT algorithm, we use these relatively shallow networks to keep the computations manageable on the available computational resources. The technical bottleneck here is the turnoff of the gradient in the backward pass in order to keep the pruned values set to zero. Given a stronger hardware infrastructure our method can be used on deeper networks such as VGG and ResNet. Hyperparameters. To evaluate the performance of the proposed method, we first focus on finding the most suitable parameter values for β and λ. We test λ ∈ {0, 1, 2, 10}, where λ = 0 yields the best results for the standard LT algorithm, and λ = 2 performs best in all other scenarios with nonuniform weights for positive and negative classes. Inspired by the inverse class frequency, we set β close to 1 in our tests. For MNIST with γ c = 10 the class frequency of the negative class is 10 times higher than for the positive class, while for ISIC and CRACK data sets γ c = 727/173 = 4.2 and γ c = 14K/2.8K = 5 respectively. For simplicity, we use γ c = 5 in both cases. This corresponds to β = 0.99999 and to β = 0.99997 for MNIST and the other two data sets respectively.
For each round of Alg. 1 in step 2 we train the network for k = 100 iterations. With stronger hardware, it is possible to train the network longer to achieve potentially better results. By following the magnitude increase strategy we prune p = 50% of the remaining weights in every round. This yields compressed networks with |W k | = 100%, 50%, 25%, 12.5%, 6.25%. 3.12%, and 1.57% remaining weights. We use stochastic gradient descent (SGD) with a momentum setting of 0.9 for network training. Scenarios. We tested our method in three different scenarios, along with the LT algorithm as a baseline. These scenarios correspond to differently colored lines in the plots: red This scenario corresponds to the results obtained with the original LT algorithm with magnitude increase pruning criterion. The weights for both positive and negative classes are set to γ c = 1 and we use no rank loss with λ = 0. Thus, use the best performance of the classical LT algorithm as a benchmark to compare the performance of our method.
blue In this scenario, for the first round of network training, both positive and negative classes have γ c = 1, i.e., we use class-balanced training. This helps the network to initially find the boundaries between the two classes without any specific focus. However, in all subsequent rounds we use γ c2,n = 10 for the positive class with λ = 2.
green This scenario is the same as the previous one but we use γ c = 10 in the first round. By doing so we remove the effect of balanced training and set a stronger focus on the positive class right from the beginning.

Results
For the CRACK data set, Fig. 5(a) and Fig. 5(b) show the results for AUC-ROC. The best AUC-ROC is achieved when using the following set of parameters: γ 1 = 1, γ 2,n = 5, λ = 2 (black line), where γ c = 5 gives the inverse class frequency for this data set. As can be seen in Fig. 5(c) and Fig. 5(d) the accuracy for our method in the best setting (black line), which is again better than the best accuracy achieved by the LT method (red line). The best achieved FNR in Fig. 5(e) is when we set γ c = 10 for all the pruning rounds (green line). FNR for the LT algorithm and our method yield FNR of 0.15 and 0.11, which shows 27% improvement with our method. However, due to the natural trade-off between FNR and FPR, giving more weight to the positive class leads to a higher FPR. Fig. 5(e) shows that the best FNR for γ c = 10 in all the pruning rounds (green line), and in Fig. 5(f) the best FPR is achieved when γ c = 5 (black line) which is better than the LT method.

Related Work
Deep networks are known to be highly redundant. This motivated many researchers to seek for network compression techniques and efficient subnetworks. The proposed methods exploit weight quantization, factorization, pruning, knowledge distillation, and efficient network design. This section summarizes recent efforts. Quantization and binarization rely on weights with discrete values. (Soudry, Hubara, and Meir 2014) propose an algorithm, which approximates the posterior of the neural network weights, yet the weights can be restricted to have discrete or binary values. (Wu et al. 2016) quantize both filter banks and fully-connected weights of CNNs. They keep top-5 error close to the original network, while speeding up training and inference time. (Gong et al. 2014) apply k-means clustering to the weights and use quantization to achieve a balance between model size and recognition accuracy. (Rastegari et al. 2016) apply approximations to standard CNNs. Their Binary-Weight-Network approximates the filters with binary values and reduces the size of example networks by the factor of 32x. In their extended algorithm, called XNOR-Network, both inputs and filters are in the binary form. XNOR-Network uses mostly bitwise operations to approximate convolutions and provides 58x speed-up. A recent work  proposes a method to circumvent the degraded representation caused by binarizing full-precision filters. They propose new circulant binary convolutional networks implemented by a set of binary circulant filters to enhance the representation ability of binary networks. Decomposition and factorization explore low-rank basis of filters to reduce model size. (Jaderberg, Vedaldi, and Zisserman 2014) represent the learnt full-rank bank of a CNN as a combination of rank-1 filters leading to a 4.5x speed-up. (Lebedev et al. 2014) proposes a two-step approach based on tensor decomposition. They replaced the original convolutional layer with four convolutional layers with smaller kernels obtained by the low-rank CP-decomposition. (Denton et al. 2014;Rigamonti et al. 2013) found similar lowrank approximations for the convolutional layers. More recent methods (Mehta et al. 2019) rely on depth-wise and point-wise separable convolutions to reduce computational complexity. Depth-wise convolution performs light-weight filtering by applying a single convolutional kernel per input channel. Point-wise convolution expands the feature map along channels by learning linear combinations of the input channels. (Huang et al. 2018) explores the possibility of factoring input channels and convolutional kernels into groups and convolving each group independently. Pruning covers a set of methods which reduce the model size by removing network connections. There are several methods to determine unimportant connections. These methods date back to the optimal brain damage (LeCun, Denker, and Solla 1990) and the optimal brain surgeon (Hassibi and Stork 1993), where the authors suggest to prune the weights based on the Hessians of the loss function. (Han et al. 2015) propose to prune network weights with a low magnitude, where (Molchanov, Ashukha, and Vetrov 2017) use a variational dropout to prune redundant weights.  propose to prune the channels in CNNs based on their corresponding filter weight norm, while ) uses the average percentage of zeros in the output to prune unimportant channels. Multi-task zipping (He, Zhou, and Thiele 2018) propose a neuron similarity metric based on the optimal brain damage to compress multiple pre-trained networks for different tasks. The LT hypothesis (Frankle and Carbin 2018) leverage an iterative pruning algorithm to prune the network weights with small magnitude. They show that the LT algorithm can be used to search for efficient sparse subnetworks. Knowledge distillation covers methods which transfer knowledge from a larger teacher to a smaller student. (Belagiannis, Farshad, and Galasso 2018) exploit adversarial setting to train a student network. The discriminator tries to distinguish between the student and the teacher. They use the L2 loss to force the student to mimic the output of the teacher. (Aguinaldo et al. 2019) apply knowledge distillation to GANs to produce a compressed generator without neither loss of quality nor generalization. They hypothesized that there exists a fundamental compression limit of GANs similar to Shannon's compression theory. (Changyong et al. 2019) suggest to add an intermediate supervision to conduct knowledge transfer in adversarial setting. Their method utilizes rich information encoded in the intermediate layers of the teacher network, to find better students. Efficient network design,-in terms of the number of parameters,-relies on either the network architecture search or the structure learning. (Elsken, Metzen, and Hutter 2018) provide an excellent survey on the network architecture search. (Wu et al. 2019;Tan et al. 2019) suggest a platform-aware network design to find architecture which optimally fits the available hardware. (Singh, Khetan, and Karnin 2019) propose to utilize training data to learn which subcomponents of a given architecture can be replaced by cheaper alternatives. In the simplest case, their model utilizes only the depth-wise-separable approximations as compression candidates. Inspired by the wiring plan of ResNet (He et al. 2016) and DenseNet (Huang et al. 2017), the authors of (Xie et al. 2019) propose randomly wired networks driven by classical random graph models from the graph theory. Several variants of these random generators yield network instances that have competitive accuracy on the ImageNet benchmark. In a similar work, (Wortsman, Farhadi, and Rastegari 2019) relax the typical notion of layers and enable channels to form connections independent of each other instead. Their network wiring is not fixed during training, i.e., they learn the network parameters together with the structure of the network itself. The result is a sparse yet more efficient subnetwork.
Our network compression method combines network pruning with efficient network design. Unlike other compression methods, which try to minimize the overall error rate, our method optimizes AUC-ROC while focusing on a desired class which appears to be useful in a number of real applications in the IoT domain. In a large class of applications, a high number of false negatives for a desired class is not tolerable. The proposed method provides a flexibility to focus on that class while preserving the overall high AUC-ROC and accuracy.

Conclusion
In this paper, we propose a new class-dependent neural network compression method to search for optimal and efficient subnetworks in the original deep network. Our method is motivated by two close yet different facts. First, many real-world data sets have imbalanced samples for different classes. Second, in many application domains some classes are more important than others, e.g., in medical imaging a higher number of false positives may be tolerable, yet the number of false negatives must stay low. We introduce a novel combined loss function within an iterative compression algorithm, which maximizes both accuracy and AUC-ROC while mimizing the number of false negatives. Our results show that our class-dependent network compression method yields a compressed neural network with up to 1% of the original network's size, yet with higher AUC-ROC and lower false negative.