summaries: The authors presented in this submission a nice novel idea of building a tree ensemble in a cascading style so that any positive predictions are decided and explained by the first tree predicting them positively. The reviewer finds this idea very interesting and clearly elaborated in this paper. However, more theoretical and empirical justification is crucially necessary in order to make the claims in the submission convincing. The issues listed here are some questions that the reviewer believes should have been discussed or answered in the paper.

summaries: This paper introduces the Cascading Decision Tree, a novel variant of decision trees with permits to extract short explanations for a class of interest. The idea is to realize a cascade of small decision trees: at a certain level, the tree is built using all points except the positive ones correctly classified by trees in previous levels. The method has been tested using three standard datasets and a novel application.

summaries: This paper introduces a new type of classification model called the "cascading decision tree." The cascading decision tree is a rule-based classifier designed to have an overlapping hierarchical structure between its nodes to produce succinct explanations. The paper introduces these models, presents an induction algorithm to learn them from data, and includes an empirical evaluation on three UCI datasets as well as a propietary dataset. The submission includes code.

abstractText: Classic decision tree learning is a binary classification algorithm that constructs models with first-class transparency every classification has a directly derivable explanation. However, learning decision trees on modern datasets generates large trees, which in turn generate decision paths of excessive depth, obscuring the explanation of classifications. To improve the comprehensibility of classifications, we propose a new decision tree model that we call Cascading Decision Trees. Cascading Decision Trees shorten the size of explanations of classifications, without sacrificing model performance overall. Our key insight is to separate the notion of a decision path and an explanation path. Utilizing this insight, instead of having one monolithic decision tree, we build several smaller decision subtrees and cascade them in sequence. Our cascading decision subtrees are designed to specifically target explanations for positive classifications. This way each subtree identifies the smallest set of features that can classify as many positive samples as possible, without misclassifying any negative samples. Applying cascading decision trees to new samples results in a significantly shorter and succinct explanation, if one of the subtrees detects a positive classification. In that case, we immediately stop and report the decision path of only the current subtree to the user as an explanation for the classification. We evaluate our algorithm on standard datasets, as well as new real-world applications and find that our model shortens the explanation depth by over 40.8% for positive classifications compared to the classic decision tree model.

authors:
Gaël Aglin
Siegfried Nijssen
Pierre Schaus

title: Learning optimal decision trees using caching branch-and-bound search

venue: In The Thirty-Fourth AAAI Conference on Artificial Intelligence,

authors:
M. Gethsiyal Augasta
T. Kathirvalavakumar

title: Reverse engineering the neural networks for rule extraction in classification problems

venue: Neural Processing Letters,

authors:
Leo Breiman
Jerome H Friedman
Richard A Olshen
Charles J Stone

title: Classification and regression trees

authors:
Carla E. Brodley
Paul E. Utgoff

title: Multivariate decision trees

venue: Machine Learning,

authors:
Rich Caruana
Hooshang Kangarloo
JD Dionisio
Usha Sinha
David Johnson

title: Case-based explanation of non-case-based learning methods

venue: In Proceedings of the AMIA Symposium,

authors:
F.K. Doilovi
M. Bri
N. Hlupi

title: Explainable artificial intelligence: A survey

venue: 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO),

authors:
F. Esposito
D. Malerba
G. Semeraro
J. Kay

title: A comparative analysis of methods for pruning decision trees

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

title: Comprehensible classification models: A position paper

venue: SIGKDD Explor. Newsl.,

authors:
Joo Gama
Pavel Brazdil

title: Cascade generalization

authors:
Georgios Gousios
Martin Pinzger
Arie van Deursen

title: An exploratory study of the pull-based software development model

venue: ICSE

authors:
Jan Havrda
Frantiek Charvt
Frantisek Charvt

title: Quantification method of classification processes: Concept of structural a-entropy

venue: Kybernetika,

authors:
Johan Huysmans
Karel Dejaeger
Christophe Mues
Jan Vanthienen
Bart Baesens

title: An empirical evaluation of the comprehensibility of decision table, tree and rule based predictive models

venue: Decision Support Systems,

authors:
Laurent Hyafil
Ronald L. Rivest

title: Constructing optimal binary decision trees is np-complete

venue: Information Processing Letters,

authors:
Maximilian Junker
Ralf Huuck
Ansgar Fehnker
Alexander Knapp

title: Smt-based false positive elimination in static program analysis

venue: In International Conference on Formal Engineering Methods,

authors:
Guang-He Lee
Tommi S. Jaakkola

title: Oblique decision trees from derivatives of relu networks

venue: In 8th International Conference on Learning Representations,

authors:
Sreerama K. Murthy
Simon Kasif
Steven Salzberg

title: A system for induction of oblique decision trees

venue: J. Artif. Int. Res.,

title: Knowledge discovery from data

venue: IEEE Intelligent Systems and their Applications,

title: Simplifying decision trees

venue: International Journal of Man-Machine Studies,

authors:
Marco Tulio Ribeiro
Sameer Singh
Carlos Guestrin

title: why should i trust you?” explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
Mark Santolucito
Jialu Zhang
Ennan Zhai
Ruzica Piskac

title: Statically verifying continuous integration configurations, 2018

title: The strength of weak learnability

title: A mathematical theory of communication

venue: The Bell System Technical Journal,

authors:
Anneleen Van Assche
Hendrik Blockeel

title: Seeing the forest through the trees: Learning a comprehensible model from an ensemble

venue: Machine Learning: ECML

authors:
Sicco Verwer
Yingqian Zhang

title: Learning optimal classification trees using a binary linear program formulation

venue: In The Thirty-Third AAAI Conference on Artificial Intelligence,

authors:
Xi Wang
Nickolai Zeldovich
M. Frans Kaashoek
Armando Solar-Lezama

title: Towards optimization-safe systems: Analyzing the impact of undefined behavior

venue: In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles,

authors:
H. Zhao
Sudha Ram

title: Constrained cascade generalization of decision trees

venue: IEEE Transactions on Knowledge and Data Engineering,

heading: 1 INTRODUCTION

text:
Binary classification is the process of classifying the given input set into two classes based on some classification criteria. Binary classification is widely used in everyday life: for example, a typical application for binary classification is determining whether a patient has some disease by analyzing their comprehensive medical record. Existing work on binary classification mainly uses the accuracy of prediction as the main criterion for evaluating model performance. However, in order for a model to be useful in real-world applications, it is imperative that users are able to understand and explain the logic underlying model predictions. Model comprehensibility1 in some real-world applications, especially in the medical and scientific domains, is of the utmost importance. In these cases, users need to understand the classification model to scientifically explain the reasons behind the classification or even rely on the model itself to discover the possible solution to the target problem.
It is difficult to provide explainability without sacrificing classification accuracy using current models. “Black-box” models such as deep neural network, random forests, and ensembles of classifiers tend to have the highest accuracy in binary classification Freitas (2014); Doilovi et al. (2018). However, their opaque structure hinders understandability, making the logic behind the predictions difficult to trace. This lack of transparency may further discourage users from using the model Augasta & Kathirvalavakumar (2012); Van Assche & Blockeel (2007).
Decision tree models, on the other hand, have transparent decision making steps. A traversal of features on the decision path from the root to the leaf node is presented to users as a rule. Therefore, compared to other models, the decision tree model has historically been characterized as having
1In this paper, comprehensibility and interpretability are used interchangeably.
high comprehensibility Freitas (2014); Doilovi et al. (2018). However, whether models generated by classic decision trees provide enough comprehensibility has been challenged: “decision trees [...] can grow so large that no human can understand them or verify their correctness“ Caruana et al. (1999), or they may contain subtrees with redundant attribute conditions, resulting in potential misinterpretation of the root cause for model predictions Freitas (2014).
The work presented in this paper introduces an algorithm for deriving succinct explanations for positive classifications, while maintaining the overall prediction accuracy. To this end, we introduce a novel cascading decision tree model. A cascading decision tree is a sequence of several smaller decision trees (subtrees) with the predefined tree depth. After every subtree sequentially follows another subtree, mimicking in this way a cascading waterfall, thus the name. The sequence ends when the subtree does not contain any leaves describing positively classified samples. Fig. 2 depicts one such cascading decision tree.
The main idea behind cascading decision trees is that, while most algorithms for constructing decision trees are greedy and they try to classify as many samples as soon as possible, such classification results in large explanation paths for the samples in the lower levels of the tree. Instead, we construct a subtree of the predefined depth. That subtree contains a short explanation for the samples it managed to classify. However, the subtree with a short depth will misclassify samples. We next repeat the process on the training set with the samples that were previously classified positively removed. This way, the samples classified as positive in the second subtree will have a much shorter explanation path than they would in the original decision tree. In the cascading decision tree model, an explanation path for positively classified sample is the path that starts in the root of the corresponding subtree.
We target explanations for only positive classifications, based on real-world motivation. In the medical domain, a positive classification result indicates that a person has the disease for which the test is being done NIH (2020). The positive classification is also combined with additional testings needed for a full diagnosis CDC (2020). Note that, if a practical application arises, our cascading decision trees model could easily be changed to target the negative classifications.
Reducing the size and the depth of a decision tree to improve comprehensibility has been studied, both from a theoretical and a practical perspective. However, constructing such optimally small decision trees is an NP-complete problem Hyafil & Rivest (1976), and the main drawback of these approaches is that the model is computationally too expensive to train. Even when using the stateof-the-art libraries Aglin et al. (2020); Verwer & Zhang (2019), we observed that complexity. To illustrate this on an example, to learn a model on the Ionosphere dataset (from the UCI Machine Learning Repository), the BinOCT tool needs approximately 10 minutes, while our approach completes this task in 1.1 seconds.
We demonstrate the applicability of the cascading decision tree model in two ways. First, we use our model to perform standard binary classification on three numerical datasets from the UCI Machine Learning Repository. Second, we apply our model to a new application of binary classification, namely continuous integration (CI) build status prediction Santolucito et al. (2018). Overall, we report that compared to the classical decision tree algorithm, our approach shortens the explanation depth for positive classifications by more than 40.8% while maintaining the prediction accuracy.

heading: 2 MOTIVATING EXAMPLES

text:
In this section we demonstrate how cascading decision trees can generate a shorter and more succinct explanation.
The following simple synthetic example is contrived to illustrate our tool’s basic functionality. Given the dataset in Table1, a classical decision tree will construct a model shown in Fig. 1. Using the same dataset, our cascading decision trees algorithm generates a model with three subtrees in shown in Fig. 2. Let’s assume that there is a new sample ,“Sample11”, with the feature vector (F, F, F, T ). Both models classify “Sample11” with the same prediction result, “Positive”. However, the explanations extracted from these two models are different.
In the classic decision tree model (Fig. 1), “Sample11” falls into node (9). Thus, the explanation path here is “Feature1 = F”, “Feature2 = F” and “Feature3 = F”, with the explanation depth of three.
Using the cascading decision tree model (Fig. 2), “Sample11” first falls into node (7) in the first subtree. Node (7) is not classifying positive samples, so “Sample11” is passed to the second subtree and eventually falls into node (10). This way, the explanation path for“Sample11” is “Feature4 = T”, with an explanation depth of only one.

heading: 3 RELATED WORK

text:
Ensemble Methods. The cascading decision trees algorithm pursues a different goal than existing ensemble methods, such as Bagging Breiman (1996) and Boosting Schapire (1990). Ensemble methods for decision trees combine multiple weaker classifiers into a larger classifier with the goal of increasing overall accuracy, while cascading decision trees focus on shortening explanations. Bagging divides the dataset into multiple, smaller datasets, generates the classifier for each dataset and produces the final classification via a voting process. Boosting algorithms iteratively learn weak classifiers, gives them weights, and adds them one after another to generate a final strong classifier. The combination strategies of these ensemble methods obfuscate the traceability of a classic decision tree, which is the source of simple explanations for classifications Zhao & Sudha Ram (2004). The limited model comprehensibility of Bagging and Boosting is also shared by other ensemble methods, which makes their output difficult to interpret.
Oblique Decision Trees. Oblique decision trees Murthy et al. (1994) extend the classic decision tree model by allowing each decision node to combine checks against multiple features. This series of work contains a rich family of models such as multivariate decision trees Brodley & Utgoff (1995), loose and tight coupling Gama & Brazdil (2000), and constrained cascade generalization of decision trees Zhao & Sudha Ram (2004). However, compared to cascading decision trees, this oblique design is not only the training stage computationally expensive Lee & Jaakkola (2020), but also makes the explaining a classification in the decision-making stage opaque and hard to interpret Zhao & Sudha Ram (2004).
Optimal Decision Trees. Optimal decision tree algorithms learn models with the optimal prediction accuracy under the constraints of the predefined depth of the tree. However, learning an fixed depth optimal decision tree without heuristics is an NP-complete problem Hyafil & Rivest (1976). The main drawback of using this approach in practice is that the model is too computationally expensive to train. For example, the state-of-the-art optimal decision trees implementations Aglin et al. (2020); Verwer & Zhang (2019) need ten minutes to train the ionosphere dataset2. On the same dataset, we show in our evaluation (Sec. 5) that our cascading decision trees learning process terminated in seconds with competitive accuracy (cf. Verwer & Zhang (2019)). In addition, instead of being a direct competitor, an optimal decision tree learner could be used as the base decision tree inducer in our algorithm to potentially improve the prediction accuracy, though at the cost of training time.
Model Interpretability. The comprehensibility of classification models, including decision tree models, has been extensively explored Doilovi et al. (2018). Specifically, Quinlan (1987) demonstrated that small models are more interpretable than larger ones in the decision tree. Similarly, Huysmans et al. (2011) ran a user study to illustrate that larger representations result in a decrease in both the accuracy of user’s answers and users confidence in the model itself. This work supports the motivation that minimizing explanations is a valuable direction to explore.

heading: 4 METHODOLOGY

text:
Formalism. For interpretability, we take inspiration from the LIME system Ribeiro et al. (2016), which states that interpretable explanations should “provide qualitative understanding between joint values of input variables and the resulting predicted response value”. In our work, we specifically focus on binary classification, and only target explanations for positive classifications. An explanation in our system should capture the essence of the positive classification. That is, the explanation identifies the key input values that contributed to the positive classification. The classification should still be the same, no matter the state of the input values not included in the explanation. It is possible the sample will be classified positively in a different way, but as long as the input values in the explanation are unchanged, the classification will still be positive.
To define a valid explanation, we consider a dataset of samples with binary labels. Without loss of generality (as we consider only the decision tree setting), let (x, y) : (2n, C) denote a sample as an n-dimensional Boolean vector and its ground-truth classification respectively. The number of classes is |C| - in our application we consider only binary classification, where |C| = 2, though
2https://archive.ics.uci.edu/ml/datasets/Ionosphere
the definition of valid explanations generalizes to larger |C|. Given a test set T : {(x, y)}, we can learn a model M : 2n → C which maps input vectors of samples to a classification. An explanatory model, M+ : 2n → E expands upon the modelM to additionally map input vectors to explanations, E . An explantation E : 2n is a Boolean vector, where every true element means that the feature at the corresponding index in the input vector is a necessary part of the classification result. The size of an explanation, |E| = ∑ i∈n E [i], is the number of true elements in the explanation vector.
We define the validity of an explanation via array multiplication. An explanation, E , is valid over an input vector x, when any part of the input vector not captured by the explanation may be modified without changing the classification result of the model.
isV alid(E , x) ⇐⇒ ∀z ∈ 2n. M(x) =M(E ∗ x+ z ∗ ¬ E) Example 1 A trivial explanation is always available for any sample - the explanation that every element of the sample vector is important. From Fig. 1, for input vector “Sample5”, a valid explanation is E = [1, 1, 1, 1]. This means that as long as no features change, the classification remains the same. Example 2 In general, a shorter explanation can be extracted from classic decision trees. As an example, the explanation of “Sample5” from the decision tree in Fig. 1 is the explanation that keeps only the elements in the decision path of the tree: E = [1, 1, 1, 0]. This is the commonly accepted approach to explanations of decision tree classifications.
Example 3 An even shorter explanation is possible with cascading decision trees. Looking again to “Sample5” as classified by the cascading decision tree in Fig. 2, a valid explanation keeps only “Feature 4” - E = [0, 0, 0, 1]. Although changes to “Feature 1-3” may change the decision path, the classification remains the same as long as “Feature 4” is unchanged.
A explanatory model is valid if and only if the provided explanation is valid for all possible inputs, that is: ∀x ∈ 2n. isV alid(M+(x), x). We note that a valid explanatory model only needs to correctly explain its classifications for all inputs - not correctly classify all inputs.
The above definition of a valid explanation is always true of the decision path of a classic decision tree. This aligns with the notion that the decision path of a classification in a classic decision tree is a valid explanation for the resultant classification of a sample. As we will show, this definition of a valid explanation is also always true of the shortened “explanation path” we propose with our cascading decision trees. Cascading decision trees provide explanations only over samples classified as positive, though the definition is more general.
Building Cascading Decision Trees. The cascading decision trees algorithm is described through pseudocode in Algorithm 1. Our insight is in the training process - it is the goal of each cascading decision subtree to identify the smallest set of features that can classify as many Positive samples as possible, without misclassifying any Negative samples. Specifically, the procedure Fit builds a classic decision tree, clf, on our training set, T R and adds it to the cascading tree list - initially this list is empty. For every leaf node we compute the mixed value, which is the percentage of samples from T R classified by this leaf node that are also Positive samples. Positive nodes are leaf nodes with a mixed value greater than the threshold (we use 80% in this paper). If clf has no Positive nodes, it means we have learned a sufficiently good classifier and we stop (Line 11). Otherwise, we first remove samples truly classified by Positive nodes in this clf from T R, and then obtain a new T R to use in the next iteration of the loop (Line 14). Our cascading decision trees algorithm1 presented here has no pruning phase. However, our algorithm is generic enough to be combined with any pruning techniques Esposito et al. (1997) and different goodness measurement for decision nodes split, such as entropy Shannon (1948) and gini impurity Havrda et al. (1967).
The time complexity of cascading decision tree algorithm is bounded by the size of the training set. Suppose the training time for building classic decision trees is a function of the number of the training samples, n and the number of features k. We use the decision tree module in scikit-learn3 as our base classic decision tree inducer, which is built upon the CART Breiman et al. (1984) method. Since features are recursively reused in every decision node based on a numerical splitting criterion,
3https://scikit-learn.org/stable/
Algorithm 1 Build Cascading Decision Trees Classifier Input: T R :Labelled Training Set Input: θ :Threshold Input: depth :Maximum depth of each decision subtree Output: cascadingTree :A list of cascading decision subtrees
1: procedure FIT(T R, θ, depth) 2: done = False 3: cascadingTree = [] 4: while done = False do 5: clf = classicDecisionTree.fit(T R, depth) 6: cascadingTree.append(clf ) 7: done = True 8: for leafNode in clf do 9: if (mixed(leafNode) >= θ) then
10: done = False 11: if (done = True) then 12: Break 13: else 14: T R = filter (clf .predict(sample, θ) = Positive, T R)
return cascadingTree
the depth of the decision tree is bounded by the number of the training samples n in our model. Therefore, the time complexity for building one base decision tree is bounded by O(n2k). According to our cascading decision trees algorithm1, after building one decision subtree, samples that are classified as True Positive are removed from the next round of decision subtree construction. In the worst case, every time, only one True Positive is classified in the current decision tree. The time complexity for building the next cascading decision subtree is in O((n−)2k). Therefore, the overall cascading decision trees training time T is bounded by: O( ∑n m=1m 2k) = O(n(n+1)(2n+1)6 k) = O(n 3k).
Testing Cascading Decision Trees. Our cascading decision trees testing process is described in Algorithm 2. In the procedure Test, we run all decision trees sequentially, and we report the decision path of that tree only as our explanation path.
Algorithm 2 Test Cascading Decision Trees Classifier Input: cascadingTree :A list of cascading decision tree classfier Input: θ :Threshold Output: Prediction Result: A boolean variable, Postive or Negative. Output: Explanation Paths: A conjunction of boolean statements to explain the decisions.
1: procedure TEST(cascadingTree, θ) 2: for clf in cascadingTree do 3: if clf.predict(sample, θ) = Positive then 4: return (Postive, clf .path(sample))
return (Negative)

heading: 5 EVALUATION

text: This section aims to evaluate the cascading decision trees algorithm by answering the following questions: (1) compared to the classic decision trees algorithm, what is the percentage of explanation depth for positive classifications that has been shortened by using cascading decision trees? (2) what is the prediction accuracy and the turn-around efficiency of cascading decision trees algorithm? (3) how well does cascading decision trees algorithm perform in real-world edge application such as continuous integration (CI) build status prediction? All experiments were conducted on a MacBook Pro with a 2.5 GHz Intel i7 processor with 16GB of RAM.

heading: 5.1 EMPIRICAL EVALUATION

text:
To empirically evaluate the explainability and accuracy of the cascading decision trees algorithm, we collect three datasets from UCI machine learning repositories4 as our benchmark set. The UCI machine learning datasets are standard benchmarks for comparing the performance of tree-based classification methods. We select these three binary classification datasets out of the 32 UCI datasets Zhao & Sudha Ram (2004). We select only the binary classification tasks, as our method provides explanations for positive classifications. While our method could be applied to multiclass classification, the user must pick a class to focus on creating succinct explanations, which is not clear from the UCI datasets. Additionally, we select only the datasets with exclusively numeric features, as the underlying library, sccikit-learn5, of our implementation is limited in this respect.
Each of the three UCI datasets reflect tasks clearly benefit from more succinct explanations for positive predictions. They are:
1. Classification of breast cancer. “Positive” samples mean the tumor turns out to be malignant, while “Negative” samples are benign.
2. Detection of free electrons in the ionosphere. “Positive” samples show the detecting signals fail to detect the free electrons; the signals just pass through the ionosphere. “Negative” samples show some evidence of the stucture in the ionosphere.
3. Discrimination of objects. This dataset includes bouncing sonar signals off a mine (metal cylinder) at various angles and under various conditions. “Positive” samples indicate the object is indeed a rock not a mine, while “Negative” samples indicate the object is a mine.
We compare the performance of the proposed cascading decision trees algorithm to the performance of the classic decision trees algorithm with various bounds on the depth of the learned tree. We quantify algorithm performance using five-fold cross validation, and randomly shuffle the datasets. The maximum depth of the cascading decision trees algorithm is uniformly set to three in all tests. The threshold in cascading decision trees algorithm is set to a fixed number 0.8.
Explainability. The shorter an explanation, the more comprehensible that explanation is to users Quinlan (1987); Huysmans et al. (2011); Pazzani (2000). The ability to clearly explain the output of machine learning models is critical to their acceptance and use in practice, an idea summarize by Huysmans et al. (2011) - “Larger representations result in a decrease in user’s answer accuracy and a decrease in user’s confidence to the model.”
Table 2 shows the comparison of the average explanation depth of model generated by cascading decision trees and classic decision trees. Our cascading decision trees algorithm shortens the explainable paths to users by 40.8% on average among three datasets. The average representation size of our cascading decision trees model is 1.78 among three datasets. We specifically focus on the explanations for positive classifications. This means on average, only 1.78 features are necessary for the classification of a positive sample in cascading decision trees. However, for classical decision trees, 3.06 features are necessary for the classification of a positive sample. This succinctness of the explanation of positive predictions enhances qualitative understanding to users, which could be used to diagnose the medical causals and back up the scientific hypothesis.
Accuracy. Table 3 shows the breakdown empirical evaluation of cascading decision trees. In two out of three datasets, our cascading decision tree surprisingly outperforms the base classic decision trees in prediction accuracy.
4http://archive.ics.uci.edu/ml/index.php/ 5The decision trees module in scikit-learn is also used as the implementation for the classic decision trees
algorithm in our evaluation.
To lower the explanation path of the decision trees model, one common technique is to set the maximum depth to a classic decision trees classifier. However, compared with the cascading decision trees, setting the maximum depth to three incurs a decrease in average prediction accuracy by around 4.0%. Even with this max depth and lower accuracy, in all three datasets, the average explanation path is still longer than cascading decision trees algorithm.
In conclusion, compared with the classical decision trees model both with and without a fixed depth, our cascading decision trees algorithm delivers better model comprehensibility via significantly shorter explanation depth while maintaining high prediction accuracy.
Low False-positive Rate. In addition to better model comprehensibility, the cascading decision trees model has another key advantage, which is the low false-positive rate in prediction. In medical and scientific domains, explanations behind positive classification results are often more useful than explanations behind the negatives. For example, in the medical domain if the prediction result is positive, the doctor needs to justify the accurate reasons behind the diagnosis of the disease and then report them to patients. A high false-positive rate not only greatly reduces physicians’ confidence in adopting the prediction result but also leads to unnecessary and invasive follow-up tests on patients HNR (2020). Therefore, it is crucial to have a competitive accuracy prediction model with very low false-positive rate. As shown in Table 3, the cascading decision trees algorithm has the lowest false positive (FP) rate for all three datasets compared to the classical decision trees algorithm.
Turn-around Efficiency. Although this paper does not focus on building fast classifier, the turnaround efficiency of our cascading decision trees algorithm turns out to be great in practice. The training process finishes in seconds in all three real-world UCI datasets. Taking the ionosphere dataset as an example, our cascading decision trees learning process terminates in 1.1 seconds with accuracy of 88.7%. This is comparable to accuracy of 87.0% of the state-of-the-art optimal decision trees algorithm BioOCT when depth of the tree are three (cf. Verwer & Zhang (2019)). However, BioOCT takes around ten minutes to train.
Real-world Application. The second part of our evaluation was to apply the cascading decision trees for predicting the build status in the continuous integration (CI) environment Gousios et al. (2014). Notifying that the attempt to build the project might fail, could save software engineers countless hours. We ran a study (link omitted for anonymity) where we learn how to classify potential build failures. The evaluation results demonstrate that cascading decision trees provides a shorter explanation, with a competitive prediction accuracy of 90.55%. Moreover, the ratio of the average number of false positives reports to the average number of correct classifications is only 1.8% . Our study shows that the use of cascading decision trees provides developers with a more succinct but comprehensible set of rules that are responsible for positive classifications.

heading: 6 CONCLUSIONS

text: Learning decision trees on modern datasets generates large trees, which in turn produce decision paths of excessive depth, obscuring the explanation of classifications. This paper intends to maximize model comprehensibility while maintaining prediction accuracy in binary classification. The cascading decision trees algorithm has been proposed to provide more succinct explanations in binary decision trees. We evaluated our algorithm in real-world medical, scientific and program analysis datasets, where the explainability of the positive test result is of the utmost importance. Our cascading decision trees algorithm shortens the explanation depth by over 40.8% for positive classifications compared to the classic decision trees algorithm.

heading: A APPENDIX

text:
Real-world Application. Encouraged by the prior results from our empirical study, we conduct our second part of our evaluation by using our cascading decision trees algorithm in a novel real-world application, continuous integration (CI) build status prediction.
In CI environment, developers upload their code as one commit, and CI starts to build and tests users’ code when they finish their uploading. Feedback from the positive CI build status enables developers to quickly locate and troubleshoot errors in the code, expediting the software development cycle. However, one major drawback of CI is that a CI build attempt can be extremely time consuming, and can even take longer than a day Santolucito et al. (2018), discouraging the usage of CI itself. Previous work Santolucito et al. (2018) used the historical data stored in the CI environment to predict the CI build status and report the root causes behind the failures to users.
We choose this dataset because it is an ideal testbed for our cascading decision trees algorithm, binary classification task on all numerical features. As opposed to other common source of programming error such as buffer overflow, divide by zero and so on Wang et al. (2013), CI build failure is mainly caused by library version inconsistency. Therefore, all features extracted in this dataset are numerical, and as a result, is amenable to analysis by our algorithm. Moreover, in program analysis domain, a very low false-positive rate is crucial for user acceptance of the tool Junker et al. (2012).
Table 4 shows the breakdown evaluation of using cascading decision trees on CI build status prediction. The strategy we employ in the evaluation is the following; for a repository with n total historical commits, we build our model with n/2 commits, and use that model to evaluate commit (n/2) + 1. We then rebuild the model with a training set of (n/2) + 1 commits and used that incremental model to predict the status of the next coming commit. Using this approach, we find that cascading decision tree classifier can predict build status with an overall accuracy of 90.55%, which is almost the same as the accuracy of 90.50% if using only classic decision tree classifier. However, in addition to competitive prediction accuracy, cascading decision tree shortens the explanation depth for failed builds by 5.6%. This could help developers identify error locations more quickly and shorten the software development cycle.
In addition, our evaluation results show that the ratio of the average number of false positive reports to the average number of correct classifications is only 1.8% (FP/TP+TN). In conclusion, the use of cascading decision trees provides developers with a more succinct but comprehensible set of rules that are responsible for positive classifications. This allows developers to more accurately and confidently troubleshoot the CI build failure.


summaries: This paper analyzed the influence of neural network width on the network performances while fixing the total number of parameters. Specifically, the authors introduced several ways to change the model width without increasing the number of parameters, and showed experimentally that for widened networks with a random static mask on weights to keep the number of parameters, increasing the width can improve the performances of the models until the network become very sparse and hard to train. They author theoretically showed that for a not so sparse one-hidden-layer neural network, increasing width decreases the distance to the Gaussian Process kernel corresponding to the infinith-width limit, which partially supports their experimental findings.

summaries: In this paper, the authors analyze the enhancements brought by widening networks with the number of parameters fixed. From the experimental side, they conduct various experiments to compare the methods of widening the networks and demonstrate different ratios of widening different networks on diverse datasets. From the theoretical side, the authors relate the training dynamics of neural networks to kernel-based learning, in  the infinite-width limit. As a consequence, the authors claim that wider networks indeed improve the performance of algorithms under certain conditions.

summaries: This manuscript provides an intriguing discussion on the different roles that the width and parameter size could play in a neural network. While these two aspects are traditionally treated as -if not identical- correlated, the authors managed to develop a couple of configurations to decouple and analyze both separately. Especially the wide and sparse approach could be a new way to design neural networks that are supposed to be small and expressive at the same time.

abstractText: Empirical studies demonstrate that the performance of neural networks improves with increasing number of parameters. In most of these studies, the number of parameters is increased by increasing the network width. This begs the question: Is the observed improvement due to the larger number of parameters, or is it due to the larger width itself? We compare different ways of increasing model width while keeping the number of parameters constant. We show that for models initialized with a random, static sparsity pattern in the weight tensors, network width is the determining factor for good performance, while the number of weights is secondary, as long as the model achieves high training accuarcy. As a step towards understanding this effect, we analyze these models in the framework of Gaussian Process kernels. We find that the distance between the sparse finite-width model kernel and the infinite-width kernel at initialization is indicative of model performance.1

authors:
Behnam Neyshabur
Ryota Tomioka
Nathan Srebro

title: In search of the real inductive bias: On the role of implicit regularization in deep learning

venue: In ICLR (Workshop),

authors:
Behnam Neyshabur
Zhiyuan Li
Srinadh Bhojanapalli
Yann LeCun
Nathan Srebro

title: The role of over-parametrization in generalization of neural networks

venue: In International Conference on Learning Representations,

authors:
Joel Hestness
Sharan Narang
Newsha Ardalani
Gregory Diamos
Heewoo Jun
Hassan Kianinejad
Md Patwary
Mostofa Ali
Yang Yang
Yanqi Zhou

title: Deep learning scaling is predictable, empirically

venue: arXiv preprint arXiv:1712.00409,

authors:
Jared Kaplan
Sam McCandlish
Tom Henighan
Tom B Brown
Benjamin Chess
Rewon Child
Scott Gray
Alec Radford
Jeffrey Wu
Dario Amodei

title: Scaling laws for neural language models

authors:
Simon S Du
Xiyu Zhai
Barnabas Poczos
Aarti Singh

title: Gradient descent provably optimizes over-parameterized neural networks

authors:
Zeyuan Allen-Zhu
Yuanzhi Li
Zhao Song

title: A convergence theory for deep learning via overparameterization

venue: In International Conference on Machine Learning,

authors:
Arthur Jacot
Franck Gabriel
Clément Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks

venue: In Advances in neural information processing systems,

authors:
Sanjeev Arora
Simon S Du
Wei Hu
Zhiyuan Li
Russ R Salakhutdinov
Ruosong Wang

title: On exact computation with an infinitely wide neural net

venue: In Advances in Neural Information Processing Systems,

authors:
Andrew Gordon Wilson
Zhiting Hu
Ruslan Salakhutdinov
Eric P Xing

title: Deep kernel learning

venue: In Artificial intelligence and statistics,

authors:
Jaehoon Lee
Yasaman Bahri
Roman Novak
Samuel S Schoenholz
Jeffrey Pennington
Jascha Sohl-Dickstein

title: Deep neural networks as gaussian processes

venue: arXiv preprint arXiv:1711.00165,

authors:
Mahdi Soltanolkotabi
Adel Javanmard
Jason D Lee

title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

venue: IEEE Transactions on Information Theory,

authors:
Blake Woodworth
Suriya Gunasekar
Jason D Lee
Edward Moroshko
Pedro Savarese
Itay Golan
Daniel Soudry
Nathan Srebro

title: Kernel and rich regimes in overparametrized models

authors:
Mikhail Belkin
Daniel Hsu
Siyuan Ma
Soumik Mandal

title: Reconciling modern machinelearning practice and the classical bias–variance trade-off

venue: Proceedings of the National Academy of Sciences,

authors:
Jaehoon Lee
Samuel S. Schoenholz
Jeffrey Pennington
Ben Adlam
Lechao Xiao
Roman Novak
Jascha Sohl-Dickstein

title: Finite Versus Infinite Neural Networks: an Empirical Study

venue: arXiv e-prints, art

authors:
Saining Xie
Ross Girshick
Piotr Dollár
Zhuowen Tu
Kaiming He

title: Aggregated Residual Transformations for Deep Neural Networks

authors:
Jongsoo Park
Sheng R. Li
Wei Wen
Hai Li
Yiran Chen
Pradeep Dubey

title: Holistic sparsecnn: Forging the trident of accuracy

venue: speed, and size. ArXiv,

authors:
Sharan Narang
Greg Diamos
Shubho Sengupta
Erich Elsen

title: Exploring sparsity in recurrent neural networks. ArXiv

authors:
Guillaume Bellec
David Kappel
Wolfgang Maass
Robert A. Legenstein

title: Deep rewiring: Training very sparse deep

venue: networks. ArXiv,

authors:
Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Training pruned neural networks

authors:
Trevor Gale
Erich Elsen
Sara Hooker

title: The state of sparsity in deep neural networks. ArXiv

authors:
Haoran You
Chaojian Li
Pengfei Xu
Yonggan Fu
Yue Wang
Xiaohan Chen
Richard G. Baraniuk
Zhangyang Wang
Yingyan Lin

title: Drawing early-bird tickets: Towards more efficient training of deep networks, 2019

authors:
Namhoon Lee
Thalaiyasingam Ajanthan
Philip H.S. Torr

title: SNIP: single-shot network pruning based on connection sensitivity

authors:
Utku Evci
Trevor Gale
Jacob Menick
Pablo Samuel Castro
Erich Elsen

title: Rigging the lottery: Making all tickets winners, 2019

authors:
Chaoqi Wang
Guodong Zhang
Roger Grosse

title: Picking winning tickets before training by preserving gradient flow, 2020

authors:
Hidenori Tanaka
Daniel Kunin
Daniel L.K. Yamins
Surya Ganguli

title: Pruning neural networks without any data by iteratively conserving synaptic flow, 2020

authors:
Jonathan Frankle
Gintare Karolina Dziugaite
Daniel M. Roy
Michael Carbin

title: Pruning neural networks at initialization: Why are we missing the mark

authors:
Jimmy Ba
Rich Caruana

title: Do deep nets really need to be deep? In Advances in neural information processing

authors:
Gregor Urban
Krzysztof J Geras
Samira Ebrahimi Kahou
Ozlem Aslan
Shengjie Wang
Rich Caruana
Abdelrahman Mohamed
Matthai Philipose
Matt Richardson

title: Do deep convolutional nets really need to be deep and convolutional

venue: arXiv preprint arXiv:1603.05691,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
Jaehoon Lee
Lechao Xiao
Samuel Schoenholz
Yasaman Bahri
Roman Novak
Jascha SohlDickstein
Jeffrey Pennington

title: Wide neural networks of any depth evolve as linear models under gradient descent

venue: Advances in Neural Information Processing Systems

authors:
Youngmin Cho
Lawrence K Saul

title: Kernel methods for deep learning

text:
1 INTRODUCTION
Deep neural networks have shown great empirical success in solving a variety of tasks across different application domains. One of the prominent empirical observations about neural nets is that increasing the number of parameters leads to improved performance (Neyshabur et al., 2015; 2019; Hestness et al., 2017; Kaplan et al., 2020). The consequences of this effect for model optimization and generalization have been explored extensively. In the vast majority of these studies, both empirical and theoretical, the number of parameters is increased by increasing the width of the network (Neyshabur et al., 2019; Du et al., 2019; Allen-Zhu et al., 2019). Network width itself on the other hand has been the subject of interest in studies analyzing its effect on the dynamics of neural network optimization, e.g. using Neural Tangent Kernels (Jacot et al., 2018; Arora et al., 2019) and
∗Work done while an intern at Blueshift. 1Code is available at https://github.com/google-research/wide-sparse-nets
Gaussian Process Kernels (Wilson et al., 2016; Lee et al., 2017).
All studies we know of suffer from the same fundamental issue: When increasing the width, the number of parameters is being increased as well, and therefore it is not possible to separate the effect of increasing width from the effect of increasing number of parameters. How does each of these factors — width and number of parameters — contribute to the improvement in performance? We conduct a principled study addressing this question, proposing and testing methods of increasing network width while keeping the number of parameters constant. Suprisingly, we find scenarios under which most of the performance benefits come from increasing the width.

heading: 1.1 OUR CONTRIBUTIONS

text:
In this paper we make the following contributions:
• We propose three candidate methods (illustrated in Figure 2) for increasing network width while keeping the number of parameters constant. (a) Linear bottleneck: Substituting each weight matrix by a product of two weight
matrices. This corresponds to limiting the rank of the weight matrix. (b) Non-linear bottleneck: Narrowing every other layer and widening the rest. (c) Static sparsity: Setting some weights to zero using a mask that is randomly chosen at
initialization and remains static throughout training. • We show that performance can be improved by increasing the width, without increas-
ing the number of model parameters. We find that test accuracy can be improved using method (a) or (c), while method (b) only degrades performance. However, we find that (a) suffers from another degradation caused by the reparameterization, even before widening the network. Consequently, we focus on the sparsity method (c), as it leads to the best results and is applicable to any network type.
• We empirically investigate different ways in which random, static sparsity can be distributed among layers of the network and, based on our findings, propose an algorithm to do this effectively (Section 2.3).
• We demonstrate that the improvement due to widening (while keeping the number of parameters fixed) holds across standard image datasets and models. Surprisingly, we obesrve that for ImageNet, increasing the width according to (c) leads to almost identical performance as when we allow the number of weights to increase along with the width (Section 2.3).
• To understand the observed effect theoretically, we study a simplified model and show that the improved performance of a wider, sparse network is correlated with a reduced distance between its Gaussian Process kernel and that of an infinitely wide network. We propose that reduced kernel distance may explain the observed effect (Section 3).

heading: 1.2 RELATED WORK

text:
Our work is similar in nature to the body of work studying the role of overparametrization and width. Neyshabur et al. (2015) observed that increasing the number of hidden units beyond what
is necessary to fit the training data leads to improved test performance, and attributed this to the inductive bias of the optimization algorithm. Soltanolkotabi et al. (2018); Neyshabur et al. (2019); Allen-Zhu et al. (2019) further studied the role of over-parameterization in improving optimization and generalization. Woodworth et al. (2020) studied the implicit regularization of gradient descent in the over-parameterized setting, and Belkin et al. (2019) investigated the behavior at interpolation. Furthermore, Lee et al. (2017) showed that networks at initialization become Gaussian Processes in the large width limit, and Jacot et al. (2018) showed that infinitely wide networks behave as linear models when trained using gradient flow. Lee et al. (2020) systematically compared these different theoretical approaches. In all the above works, the number of parameters is increased by increasing the width. However, in this work, we conduct a controlled study of the effect of width by keeping the number of parameters fixed.
Perhaps Littwin et al. (2020) is the closest work to ours, which investigates overparametrization achieved through ensembling as opposed to layer width. Ensembling is achieved by connecting several networks in parallel into one “collegial” ensemble. They show that for large ensembles the optimization dynamics simplify and resemble the dynamics of wide models, yet scale much more favorably in terms of number of parameters. However, the method employed there is borrowed from the ResNeXt architecture (Xie et al., 2016), which involves altering the overall structure of the network as width is increased. In this work we try to make minimal changes to network structure, in order to isolate the effect of width on network performance.
Finally, static sparsity is the basis of the main method we use to increase network width while keeping the number of parameters fixed. There is a large body of work on the topic of sparse neural networks (Park et al., 2016; Narang et al., 2017; Bellec et al., 2018; Frankle and Carbin, 2018; Elsen et al., 2019; Gale et al., 2019; You et al., 2019), and many studies derive sophisticated approaches to optimize the sparsity pattern (Lee et al., 2018; Evci et al., 2019; Wang et al., 2020; Tanaka et al., 2020). In our study, however, sparsity itself is not the subject of interest. In order to minimize its effect in our controlled experiments, the sparsity pattern that we apply is randomly chosen and static. A recent work (Frankle et al., 2020) demonstrates that a random, fixed sparsity pattern leads to equal performance as the more involved methods for pruning applied at initialization, when the per-layer sparsity distribution is the same. However, we do not explore this direction in our study.

heading: 2 EMPIRICAL INVESTIGATION

text: In this section, we first explain our experimental methodology and then investigate the effectiveness of different approaches to increase width while keeping the number of parmeters fixed. Finally, we discuss the respective roles of width and the number of parameters in improving performance.

heading: 2.1 METHODOLOGY

text:
In order to identify how width and number of parameters separately affect performance, we need to decouple these quantities. For a fully-connected layer, width is the number of hidden units, and for a convolutional layer, width corresponds to the number of output channels. Increasing the width of one layer ordinarily entails an increase in the number of weights. Therefore, some adjustment is required to keep the total number of weights constant. This adjustment can be made at the level of layers by reducing some other dimension (i.e., by introducing a “bottleneck”), or at the level of weights by setting some of them to be zero. When choosing a method for our analysis, we take particular care about possible confounding variables, as many aspects of a neural network are intertwined. For example, we prefer to keep the number of non-linear layers in the network fixed, as it has been shown that changing it can significantly affect the experssive power, optimization dynamics and generalizaiton properties of the network. With these constraints in mind, we specify three different methods listed in Section 1.1. In this section, we discuss these methods in detail, evaluate them, and present the results obtained on image classification tasks.
In summary, our approach is as follows: We select a network architecture which specifies layer types and arrangement (e.g., MLP with some number of hidden layers, or ResNet-18), set layer widths, and count the number of weights. We refer to this model as the baseline, and derive other models from it by increasing the width while keeping the number of weights constant. In this way, we obtain a
family of models that we train using the same training procedure, and compare their test accuracies. For comparison and as a sanity check, we also consider the dense variants of the wider models.
We tested a variety of simple models, and observed the same general behavior in the context of our research question. For the discussion in this paper, we focus on two model types: a MLP with one hidden layer, and a ResNet-18. We chose the ResNet-18 architecture because it is a standard model widely used in practice. Its size is small enough that it allows us to increase the width substantially, yet it has sufficient representational power to obtain a nontrivial accuracy on standard image datasets. When creating a family of ResNet-18 models, we refer to the number of output channels of the first convolutional layer as the width, and do not alter the default width ratios of all following layers. Further details of each experiment and figure are specified in Appendix A.

heading: 2.2 BOTTLENECK METHODS

text:
Here we discuss the two bottleneck methods described in the previous section and in Figure 2.
Linear Bottleneck: Substitute each weight matrix W ∈ Rdi×do by W1W2, where W1 ∈ Rdi×db , W2 ∈ Rdb×do and db ≤ min(di, do).2 Note that if db = min(di, do), then this reparametrization has the exact same expressive power 3 as the original network. Now, one can make the network wider by increasing the number of hidden units (di and do here) and reducing the bottleneck size db. This would correspond to imposing a low-rank constraint on the original weight matrix W . Linear bottleneck has been proposed as a way to reduce the number of parameters and improve training speed (Ba and Caruana, 2014; Urban et al., 2016). The caveat of this method is that, even though the expressive power of the reparametrized network is the same as the original one, the reparameterization changes the gradient descent trajectory and hence can affect the final results. It is therefore not possible to control the implicit regularization caused by this transformation. Note that substituting the weight matrix by a product of two matrices changes the number of parameters of the model.
Non-linear Bottleneck: One way to create a non-linear bottleneck is to split each layer in two as described above and add a non-linearity to the first layer. The problem with this approach is that adding a non-linearity changes the expressive power of the model, and hence adds a factor that we cannot control. An alternative approach, which is more favorable in our case and which we adopt here, is to modify the layers in pairs. The input dimension of the first layer is increased, while its output dimension (and consequently the input dimension of the second layer) is reduced (db < d). Non-linear bottlenecks are widely used in practice, particularly as a way to save parameters in very deep architectures, such as deeper variants of ResNet (He et al., 2016) and DenseNet (Huang et al., 2017).
The performance of these methods on CIFAR-10 and CIFAR-100 datasets is demonstrated in Figure 3. The results indicate that increasing width using the linear bottleneck indeed leads to improved
2In the case of a ResNet-18 model, each convolutional layer is replaced by two convolutional layers with kernel dimensions 3× 3 and 1× 1, respectively, and with db = di = do before widening.
3Here, expressive power refers to the set of functions that can be represented by the network.
accuracy up to a certain width. Moreover, this effect is more pronounced in smaller models that are less overparameterized. This is similar to the improvement gained when increasing the width along with the number of parameters (without a bottleneck): The improvement tends to be diminished when the base network is wider. However, as discussed above, the act of substituting a weight matrix by a product of two weight matrices changes the optimization trajectory which could in turn affect generalization. Indeed, the performance of the original model, indicated by dashed horizontal lines in the Figure, is significantly higher than that of the transformed models. Therefore, even though the width increase at a constant number of weights with the linear bottleneck method improves the result of the most narrow model obtained after the transformation, it typically does not outperform the default ResNet-18 model. Due to lack of control over the effect of inductive bias, we conclude that this choice does not qualify to be used in our controlled experiments.
The non-linear bottleneck method does not suffer from the same issues as the linear version in terms of inductive bias of reparametrization. However, as Figure 3 demonstrates, no empirical improvement is obtained by increasing the width, except for the model with 1.8e+05 weights (and then the improvement is mild). Therefore, we conclude that the non-linear bottleneck model does not show a significant enough improvement to be considered as an effective method for our study.

heading: 2.3 SPARSITY METHOD

text:
We now turn to the sparsity method illustrated in Figure 2c, which is the main method considered in this work. We start with a baseline model that has dense weight tensors. We then increase the width by a widening factor f and sparsify the weight tensors such that the total number of trainable weights is the same as in the baseline model. In an attempt to run a controlled experiment and minimize the differences between the sparsified setup and the baseline setup, we choose the sparsity mask at random at initialization and keep it static during training. In this sense, our method differs from most other pruning methods discussed in the literature, where the aim is to maximize performance. The advantage of the sparsity method over the bottleneck methods considered earlier is that it allows us to control the number of weights without altering the overall network structure. We define the connectivity of a sparse model to be the ratio between the number of its parameters and the number of parameters in a dense model of the same width.
In order to implement the sparsity method, we need to choose how to distribute the sparsity both across network layers and within each layer. To prevent smaller layers from being cut out entirely, we choose the number of weights to be removed in each layer to be proportional to the number of weights in that layer (except for BatchNorm layers, which are kept intact). Figure 4 demonstrates the principle of our algorithm for sparsity distribution. Within each layer, we distribute the sparsity uniformly across all dimensions of the weight tensor. Overall, this method of distributing the weights led to the best performance among the different methods we tried in our experiments (see Appendix C for more details).
8e-03 1.0 connectivity of whole network
1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1co n n ec ti vi ty of la st la ye r ? ?
≤ 0.70
0.75
0.80
0.85
0.90
0.95
(a) ReLU
8e-03 1.0 connectivity of whole network
1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1co n n ec ti vi ty of la st la ye r ?
≤ 0.70
0.75
0.80
0.85
0.90
(b) Linear
Figure 5: Test accuracy (color-coded) on MNIST obtained by MLP models with 1 hidden layer and ReLU or linear activations, as a function of overall connectivity (horizontal axis) and of connectivity in the last layer (vertical axis). White stars indicate points with the highest test accuracy.
MLP. We study a fully-connected network with one hidden layer trained on MNIST. We use this simple setup to compare different sparsity distribution patterns across layers for a given network connectivity, and to compare the effects of increased width with and without ReLU non-linearities.
The dense MLP at width n has two weight matrices: The first layer matrix has size 784× n and the last layer has size n×10. In the experiments, we set the total number of weights to 3970 and consider widths ranging from 5 to 640, corresponding to network connectivities between 1 and 5/640 ≈ 0.008. At each width, we vary the connectivity of the last layer (the smaller of the two) between 1.0 and 0.1.
The results are shown in Figure 5. We find that sparse, wide models can outperform the dense, baseline models for both ReLU and linear activations. The ReLU model attains its maximum performance at around 3− 6% connectivity, which corresponds to a widening factor of 16 or 32. At the optimal point the connectivity of the last layer is high, above 80%. It is therefore advantageous in this case to remove more weights from the first layer than from the last layer. This makes intuitive sense: Removing weights from a layer that starts out with fewer weights can be expected to make optimization more difficult. This result motivates our choice to remove weights proportionally to layer size when sparsifying other models. Finally, the fact that larger width leads to improvement even in the deep linear model implies that the improvement cannot be attributed only to the increased model capacity that a wider ReLU network enjoys.
ResNet-18. We train families of ResNet-18 models on ImageNet, CIFAR-10, CIFAR-100 and SVHN, covering a range of widths and model sizes. A detailed example of the sparsity distribution over all layers is shown in Appendix D.
Table 1 shows the results obtained on ImageNet. As expected, the performance improves as the width and the number of weights increase (row 1). However, up to a certain width, a comparable improvement is achieved when only the width grows and the number of weights remains fixed (row 2). We point out that test accuracy declines around the same width that training accuracy declines (see additional plots presented in Appendix E). Therefore, in this case the determining factor for model performance is width rather than number of parameters. Figure 6 shows the results of training model families on several additional datasets. We again find that performance improves with width at a fixed number of parameters, up to a certain widening factor. The effect is most pronounced for more difficult tasks and for smaller models that do not reach 100% training accuracy, yet it is still present for models that do fit the training set (see also Appendix E).
Figure 7 compares the performance improvement of a sparse, wide model against that of a dense model with the same width. In particular, it shows the fraction of the improvement that can be attributed to width alone: That is, the ratio between the sparse/baseline accuracy gap and the dense/baseline accuracy gap. We see that as long as the model can achieve high training accuracy, most of the improvement in performance can be attributed to the width.

heading: 3 THEORETICAL ANALYSIS IN A SIMPLIFIED SETTING

text:
We showed empirically that wide, sparse networks with random connectivity patterns can outperform dense, narrower networks when the number of parameters is fixed. The performance as a function of the width has a maximum when the network is sparse. In this section we investigate a potential theoretical explanation for this effect.
It is well known that wider (dense) networks can achieve consistently better performance. In the infinite-width limit, the training dynamics of neural networks is equivalent under certain conditions to kernel-based learning. In particular, consider a network function fθ(x) with model parameters θ. The Neural Tangent Kernel is defined by Θ(x1, x2) := ∇θf(x1)T∇θf(x2). Jacot et al. (2018) showed that, in the infinite width limit (and with appropriate parameterization defined below), training the network fθ using gradient flow is equivalent to training a linear model with the kernel Θ. Lee et al. (2019) showed empirically that the NTK lineraization result can be a good approximation for the training dynamics of networks with large but finite width.
Based on these results, we propose a possible explanation for the main effect observed in this paper, which is valid for networks with sufficiently large but finite width. We conjecture that the kernel of a
(a)
(b)
finite-width network at initialization is indicative of its performance, and that optimal performance is achieved when its distance to the infinite-width kernel is minimized. We further hypothesize that this distance can be reduced by increasing the network width at a fixed number of parameters. In the following, we formalize this conjecture and derive expressions for the kernel of a sparse finite-width network with one hidden layer. We calculate the kernel distance theoretically, and show that the distance predicted using this result is in good agreement with experiments.
Consider a 2-layer ReLU network function f : Rd → R given by f(x) = (nd)−1/2vT [ux]+, [z]+ := zH(z). Here, x ∈ Rd is the input, the network parameters are u ∈ Rn×d and v ∈ Rn (for simplicity, we omit the biases), and H(·) is the Heaviside step function. We note that in this section we use NTK parameterization (Jacot et al., 2018) for simplicity, whereas in previous sections we used LeCun parameterization. Each network parameter is sampled independently from N (0, σ2) with probability p, and is set to zero with probability 1− p. We set σ2 = p−1. The probability density function for each parameter θ is therefore given by Pr(θ) = p(2πσ2)−1/2 exp ( −θ2/2σ2 ) + (1− p)δ(θ), where δ(·) is the Dirac delta function. In the following, we consider the Gaussian Process (GP) kernel of the network, defined as ΘGP(x, y) := ∇vf(x)T∇vf(y). Theorem 1. Consider the GP kernel ΘGP of a 2-layer network with ReLU activations, where the weights are sampled from Pr(θ). The mean distance squared between ΘGP to the (dense) infinite-width kernel Θ∞GP is
Eθ [ (ΘGP(x, y)−Θ∞GP(x, y))2 ] = 1
d2
[ K̃1,p(x, y)−K1(x, y) ]2 + 1
d2n
[ K̃2,p(x, y)− K̃1,p(x, y)2 ] .
(1)
Here,
K̃l,p(x, y) = σ 2l · ∑ s1,...,sd∈{0,1} p ∑d i si(1− p)d− ∑d i siKl(xs, ys) , (2)
Kl(x, y) = 1
(2π)d/2 ∫ ∞ −∞ ddw e−‖w‖ 2 2/2(w · x)l(w · y)lH(w · x)H(w · y) . (3)
s = (s1, . . . , sd) is a vector with elements in {0, 1}, and xs := (s1x1, . . . , xdsd) is the x vector with some elements zeroed out.
The proof is provided in Appendix F. Also in the Appendix, we derive the following closed-form approximation to the kernel distance (1) under the assumptions that the input vectors x, y are independent random vectors and pd 1:
Eθ [ (ΘGP(x, y)−Θ∞GP(x, y))2 ] ≈ 1
4d
[ 1
4 ( 1 √ p − 1 )2 + d n ( 1− 1 π2 )] . (4)
In order to keep the number of parameters fixed as we change the width, we set np = const. Under this constraint, and assuming n 1, the distance (4) is minimized when p∗ ≈ √ np/4d.
In Figure 8b we compare this approximation with the GP kernel computed empirically at initialization. We find good agreement with the theoretical prediction (4) when dp 1. Furthermore, we see that the minimal kernel distance at initialization and the optimal performance of the trained network are obtained at a similar width, providing evidence in support of our hypothesis.

heading: 4 DISCUSSION

text:
In this work we studied the question: Do wider networks perform better because they have more parameters, or because of the larger width itself? We considered several ways of increasing the width while keeping the number of parameters fixed, either by introducing bottlenecks into the network, or by sparsifying the weight tensors using a static, random mask. Among the methods we tested, the one that led to the best results was removing weights at random in proportion to the layer size, using a static mask generated at initialization. In our image classification experiments, increasing the width using this sparsity method (while keeping the total number of parameters constant) led to significant improvements in model performance. The effect was strongest when starting with a narrow basline model. Additionally, when comparing the wide, sparse models against dense models of the same width, we found that the width itself accounts for most of the performance gains; this holds true up to the width above which the training accuracy of the sparse models begins to deteriorate, presumably due to low connectivity between neurons.
Focusing on the sparsity method, we initiated a theoretical study of the effect, hypothesizing that the improvemenet in performance is correlated with having a Gaussian Process kernel that is closer to the infinite-width kernel. We computed the GP kernel of a sparse, 2-layer ReLU network, and derived a simple approximate formula for the distance between this kernel and the infinite-width dense kernel. In our experiment, we found surprisingly strong correlation between the model performance and the distance to the infinite-width kernel.
While our work is fundamental in nature, and sparsity is not the subject of this paper, the method we propose may lead to practical benefits in the future. Using current hardware and available deep learning libraries, we cannot reap the benefits of a sparse weight tensor in terms of reduced computational budget. However, in our experiments we find that the optimal sparsity can be around 1-10% for convolutional models (corresponding to a widening factor of between 3-10). Therefore, using an implementation that natively supports sparse operations, our method may be used to build faster, more memory-efficient networks.

heading: ACKNOWLEDGEMENTS

text: The authors would like to thank Ethan Dyer, Utku Evci, Etai Littwin, Joshua Susskind, and Shuangfei Zhai for useful discussions.

heading: A EXPERIMENTAL DETAILS

text:
In this section we provide experimantal details and additional information about the figures in the main text.
Figures 1 and 6: In all experiments, we use a standard PyTorch implementation of the ResNet-18 model. We set the number of weights in the model by changing the number of output channels in the first convolutional layer (referred to as the model width), while leaving the width ratios between the first convolutional layer and the subsequent four blocks of the ResNet-18 at their default values 1 : 2 : 4 : 8. We do not include the weights in the BatchNorm layers into the total weight count, and we do not sparsify these layers.
All models are trained using SGD with momentum=0.9, Cross-Entropy loss, and initial learning rate 0.1. The learning rate value and schedule were tuned for the smallest baseline model. We do not apply early stopping, and we report the best achieved test accuracy. For ImageNet, we use weight decay 1e-4, cosine learning rate schedule, and train for 150 epochs. Because of the computational cost of ImageNet experiments, we did not repeat each run multiple times. We have checked for two datapoints that the variance in training and test accuracy for different random seeds is smaller than 0.1%. For other datasets, we use weight decay 5e-4, train for 300 epochs, and the initial learning rate 0.1 is decayed at epochs 50, 120 and 200 with gamma=0.1. The reported results are averages over 3 runs with different random seeds.
In Figure 1, the baseline model has width 64 (1e7 weights) for ImageNet, and 18 (9e5 weights) for the other datasets.
In Figure 6, we consider baseline models with base widths [8, 12, 18, 40, 64], corresponding to a total of [1.8e5, 4.0e5, 9.0e5, 4.4e6, 1.1e7] weights respectively.
Figure 5: All networks are MLPs with one hidden layer, a total of 3970 weights (base width is 5), and either (a) ReLU or (b) Linear activation function. The networks are parameterized according to the standard Pytorch implementation (weights and biases are randomly initialized from the uniform distribution). We train these models on MNIST for a fixed number of 300 epochs (ensuring convergence), with SGD optimizer, no momentum, Cross-Entropy loss, with a constant learning rate 0.1 and mini-batch size 100.
For ReLU, highest test accuracy (marked by white stars in the plot) is 96.3%, and is achieved by models with connectivity 0.06 (width 80) or 0.03 (width 160). For Linear, it is 92.7%, achieved at connectivity 0.13 (width 40). The color scheme is centered at the test accuracy value attained by the baseline model (approximately 90% in both cases), and its upper limit is set to the respective highest achieved value. Empty (white) cells correspond to invalid combinations of connectivity values. Note that the range on the horizontal axis is not equally spaced.
Figure 8: The MLP has one hidden layer, no biases, ReLU activation function, and NTK-style parameterization. It is trained on a subset of 2048 samples from the MNIST training set and tested on the full MNIST test set. The input is normalized with pixel mean and standard deviation as (image - mean)/stdev. We train for 300 epochs with vanilla SGD using Cross-Entropy loss and batch size 256. The learning rate was tuned separately for each width. The reported numbers are averages over 10 random seeds.
The number of weights in dense models is (784 + 10)·width, while all sparse models have the same number of weights as the smallest dense model (width 8): 6,352. The empirical approximation of the infinite-width kernel is computed on a dense MLP with width 104 at initialization.
A.1 IMAGENET DATA PREPROCESSING
In order to decrease the size of the dataset and be able to download it to cloud instances with limited storage, we resized all images in the dataset by keeping their proportions fixed and setting their smallest dimension to 256. This procedure reduces the accuracy of ResNet models by aboud 1-2%.
Transformations for ImageNet: We follow the standard transformations used is training Imagenet. Following is the list of PyTorch data transformations applied on each image.
• RandomResizedCrop(size=224, scale=(0.2, 1.0)) on the training set.
• Resize(256, transforms.CenterCrop(224)) on the test set.

heading: B SPARSITY DISTRIBUTION CODE

text:
The following code implements our algorithm for distributing sparsity over model layers. Figure 4 illustrates the procedure.
def get_ntf(num_to_freeze_tot, num_W, tensor_dims, lnames_sorted): """ Distribute the total number of weights to freeze over model layers.
Parameters num_to_freeze_tot (int) - total number of weights to freeze. num_W (dict) - layer names (keys) and number of weights in layer
(vals).↪→ tensor_dims (dict) - layer names (keys) and the dimensions of layer tensor (vals).↪→ lnames_sorted (list of str) - layer names, sorted by magnitude in descending order.↪→
Returns num_to_freeze (list of int) - number of weights to freeze per layer,
order corresponding to lnames_sorted.↪→ """
num_layers = len(lnames_sorted) num_to_freeze = np.zeros(num_layers, dtype=int) # init
# list of num. weights in layer, in sorted order (largest first) num_W_sorted_list = [num_W[lname] for lname in lnames_sorted]
# compute num. weights differences between layers num_W_diffs = np.diff(num_W_sorted_list) num_W_diffs = [abs(d) for d in num_W_diffs]
# auxiliary vector for the following dot product to compute the bins aux_vect = np.arange( 1,len(num_W_diffs)+1 )
# the bins of the staggered sparsification: array of max. num. of weights that can be frozen within the given layer before the next-smaller layer gets involved into sparsification
↪→ ↪→ ntf_lims = [np.dot(aux_vect[:k], num_W_diffs[:k]) for k in
range(1,num_layers)]↪→
# find in which bin num_to_freeze_tot falls - this gives the number of layers to sparsify↪→ lim_val, lim_ind = find_ge(ntf_lims, num_to_freeze_tot) num_layers_to_sparsify = lim_ind+1
# base fill: chunks of num. weights that are frozen in each involved layer until all involved layers have equal num. weights remaining↪→ base_fill = [sum(num_W_diffs[lind:lim_ind]) for lind in range(lim_ind)] base_fill.append(0)
# the rest is distributed evenly over all layers involved rest_tot = num_to_freeze_tot-sum(base_fill) rest = int(np.floor(rest_tot/num_layers_to_sparsify)) num_to_freeze[:num_layers_to_sparsify] = np.array(base_fill)+rest
# first layer gets the few additional frozen weights when rest_tot is not evenly divisible by num_layers_to_sparsify↪→ rest_mismatch = rest_tot - rest*num_layers_to_sparsify num_to_freeze[0]+= rest_mismatch
assert sum(num_to_freeze)==num_to_freeze_tot
return num_to_freeze

heading: C SPARSITY DISTRIBUTION IN CONVOLUTIONAL LAYERS

text: The weight tensor of a convolutional layer has 4 dimensions: input, output, kernel width, kernel height. As discussed in section 2.3, when reducing network connectivity, we remove weights randomly across all dimensions of a weight tensor. A reasonable alternative for convolutional layers is to remove weights in the input and output dimensions only, leaving the kernels themselves unchanged. We test this approach on ResNet-18 and find that it leads to very similar results in general. Specifically for smaller models, removing weights along all tensor dimensions results in better performance. For the smallest networks (base widths 8 and 12) and small connectivity, we observed a gap up to 3% in test accuracy on both CIFAR datasets. Figure 9 shows results for on CIFAR-100, where the effect is more pronounced, for models with base widths 8, 12 and 18 (1.8e5, 4.0e5 and 9.0e5 weights, respectively). Each experiment was repeated for 10 random seeds.

heading: D SPARSITY DISTRIBUTION IN RESNET-18

text:
On a coarse level, the ResNet-18 architecture is as follows: one convolutional layer, followed by four modules, followed by one fully-connected layer; each module comprises two blocks, and each block contains two convolutional layers. The number of output channels in the first convolutional layer is the same for the first module, and the ratio of output channel numbers in the subsequent modules is 1 : 2 : 4 : 8 – we do not change this ratio in our experiments. When building a family of ResNet-18 models, we vary the number of output channels of the first convolutional layer, and refer to this as the width of the model, while the widths of all subsequent layers are set according to the mentioned ratio.
When reducing the connectivity of a ResNet-18 model, we remove weights from each layer according to layer size. More precisely, we first remove weights from the layer with the largest number of weights until it reaches the size of the next-smaller layer. We then proceed with removing weights from these two layers equally, and continue this procedure until the targeted total number of weights in the network is achieved.
Figures 10 shows layer-wise sparsity distribution in ResNet-18 with 1.8e5 weights and various widths as an example.

heading: E ADDITIONAL FIGURES FOR RESNET-18 EXPERIMENTS

text: In this section we show additional plots for ResNet-18 experiments – see Figures 11, 12, 13, and 14.

heading: F THEORETICAL DETAILS

text:
In this section we provide additional details on the theoretical analysis of Section 3.
Proof (Theorem 1). We begin by defining the integral
K̃l,p(x, y) :=
∫ ddw d∏ i Pr(wi)(w · x)l(w · y)lH(w · x)H(w · y) . (5)
In particular, for p = 1 we have the relation K̃l,p(x, y) = Kl(x, y).
A straightforward calculation gives the following. K̃l,p(x, y) = ∑
s1,...,sd∈{0,1}
pΣs(1− p)d−Σs
× (2πσ2)−Σs/2 ∫ dws e −|ws|2/2σ2(ws · x)l(ws · y)lH(ws · x)H(ws · y) (6)
= σ2l · ∑
s1,...,sd∈{0,1}
pΣs(1− p)d−ΣsKl(xs, ys) . (7)
Here s = (s1, . . . , sd) is a 0,1 vector of length d, Σs = ∑d i si, and ws = (s1w1, . . . , wdsd) is the w vector with some elements zeroed out (xs and ys are defined similarly). The integration is over all the non-zero ws, namely dws = ∏ i|si=1 dwi.
Consider now the sparse kernel ΘGP. It is easy to check that
Eθ[ΘGP(x, y)] = 1
d K̃1,p(x, y) , (8)
Var[ΘGP(x, y)] = 1
d2n
[ K̃2,p(x, y)− K̃1,p(x, y)2 ] . (9)
Let ΘnGP be the dense kernel (with p = 1) at width n, and let Θ ∞ GP = limn→∞Θ n GP be the dense infinite-width kernel. From (8) and (9) we see that Eθ[Θ∞GP(x, y)] = 1dK1(x, y), and Var[Θ∞GP(x, y)] = 0. Using these results, the mean square distance between the sparse and infinitewidth kernels is now given by
Eθ [ (ΘGP(x, y)−Θ∞GP(x, y))2 ] = [Eθ[ΘGP(x, y)]−Θ∞GP(x, y)]2 + Var[ΘGP(x, y)]
= 1
d2
[ K̃1,p(x, y)−K1(x, y) ]2 + 1
d2n
[ K̃2,p(x, y)− K̃1,p(x, y)2 ] .
(10)
F.1 APPROXIMATING THE KERNEL DISTANCE
Next, we derive the approximate form (4) by using plausible arguments. In this calculation we assume that dp 1, and that x, y ∈ Rd are independent random vectors with elements sampled from N (0, 1). The derivation is not rigorous, but we compare the results against an empirical calculation in Figure 8 and find good agreement when dp 1. For given p we expect the dominant contribution to K̃l in the sum (7) to come from terms where Σs = ∑ i si ≈ pd, and so we consider a mask s with this property. We can then approximate
xs · ys ≈ dp and ‖xs‖2 ≈ √ dp(1 − 1/4dp) (and similarly for ‖ys‖2).4 We denote by θ the angle between x, y, and by θs the angle between xs, ys. Then, from the above we expect
cos θs ≈ ξ√ dp
, sin θs ≈ √
1− 1 dp ≈ 1− 1 2dp , θs ≈ π 2 − ξ√ dp , (11)
where ξ = ±1 is a random sign. Next, we consider the integrals Kl(x, y). We will rely on the following result from Cho and Saul (2009).5 For x, y, w ∈ Rd,
Kl(x, y) = 1
(2π)d/2
∫ ddw e−‖w‖ 2 2/2(w · x)l(w · y)lH(w · x)H(w · y) (12)
= 1
2π |x|l|y|lJl(θ(x, y)) , (13)
θ(x, y) = arccos ( x · y |x||y| ) , (14)
J1(θ) = sin θ + (π − θ) cos θ , (15) J2(θ) = 3 sin θ cos θ + (π − θ)(1 + 2 cos2 θ) . (16)
Using the random vector approximations, we find
K1(xs, ys) = 1
2π |xs||ys|J1(θs) ≈
dp
2π
[ 1 + πξ
2 √ dp
] , (17)
K2(xs, ys) = 1
2π |xs|2|ys|2J2(θs) ≈
(dp)2
2π
[ π
2 + 4ξ√ dp + π dp +
ξ
2(dp)3/2
] . (18)
For the sparse functions K̃l(x, y), we assume as before that the contribution from the sum over masks is concentrated where the mask Σisi ≈ dp. For a mask s obeying this condition we then have K̃l,p(x, y) ≈ σ2lKl(xs, ys). In particular,
K̃1,p(x, y) ≈ d
2π
[ 1 + πξ
2 √ dp
+ 1
2dp
] , (19)
K̃2,p(x, y) ≈ d2
2π
[ π
2 + 4ξ√ dp + π dp +
ξ
2(dp)3/2
] . (20)
We can also consider the diagonal elements, setting x = y and θs = θ = 0. We have K̃l,p(x, x) ≈ σ2lKl(xs, xs) ≈ σ 2l(dp)l
2π [ 1 + l(l−1)dp ] Jl(0). In particular,
K̃1,p(x, x) ≈ d
2 , (21)
K̃2,p(x, x) ≈ 3d2
2
( 1 + 2
dp
) . (22)
4Here we used the fact that these are random vectors of effective dimension ≈ dp, and that for such a vector we have Eθ [ ‖xs‖l2 ] = 2l/2 Γ((d+l)/2) Γ(d/2) .
5The definition here has a factor of 2 difference compared with Cho and Saul (2009).
We are now ready to derive the approximate kernel distance (4) from the exact relation (1). Using the approximations (19), (20), (21), (22), we end up with the following.
Eθ [ (Θ̄n,p(x, y)− Θ̄∞(x, y))2 ] ≈ 1
4d
[ 1
4 ( 1√ p − 1 )2 + d n ( 1− 1 π2 )] , (23)
Eθ [ (Θ̄n,p(x, x)− Θ̄∞(x, x))2 ] ≈ 1 n
( 5
4 +
3
dp
) . (24)
We would like to find the minimum of the distance (23) when keeping the mean number of parameters np fixed. Roughly, we would like to minimize 14 (p
−1/2 − 1)2 + dpnp with np constant. Assuming that the minimum is at √ p 1, we find that the minimum p∗ is at
p∗ ≈ √ np
4d . (25)

title: ARE WIDER NETS BETTER GIVEN THE SAME NUMBER OF PARAMETERS?