summaries: The paper introduces an approach to decision tree induction based on sub-sampling and pruning heuristics.  Typically, inducing a tree involves O(D*N_j*log(N_j)) work at each node j, where D is the number of features and N_j is the number of observations at node j.  This is because we can find the optimal split at node j for each feature in O(N_j) time after sorting each of the N_j observations. The basic idea introduced in this paper is to reduce the computational complexity incurred at each node by starting with a subsample of N_j, pruning features with sub-par performance, increasing the subsample size, pruning sub-par performing features, .... until the best feature has been chosen on the full sample of N_j observations.  The idea is very simple and the authors attempt to bolster this simple idea with some theoretical results and a wide array of experiments. The method does appear to be effective for datasets with very large D, which for example occurs when constructing Haar features on image data.   The paper proposes a stochastic (i.e. approximate) algorithm to fasten node splitting during tree induction. The idea of the method is to filter out the most irrelevant features using a (growing) subsample of training examples and then to optimize the split using all samples only for the remaining features. The approach is shown to improve computing times for tree construction by several orders of magnitude without impacting accuracy.  The paper presents a simple iterative sub-sampling procedure that can substantially reduce the runtime required for finding a split on a numeric feature in axis-parallel decision trees. In each iteration of the algorithm, the lowest-ranked half of features is discarded from further consideration, and the amount of data used for computing the value of a feature is increased for the next iteration, starting with a very small initial set of data. Once a user-specified maximum number of iterations has been reached, standard split selection is performed based on the remaining features and the full dataset available at the node. The paper derives a bound on the runtime, proves that the algorithm will monotonically decrease an upper bound on the split metric, and shows that the probability of discarding a feature depends on the overlap of classes wrt the feature (in a binary classification scenario). It also shows that the algorithm produces a consistent estimator and that the objective function decreases monotonically as new nodes are added. Experimental results on six high-dimensional datasets show that the proposed method produces decision trees that are competitive with standard trees that are obtained after pre-filtering features using chi-square or mRmR, but at a substantially reduced training time. The paper also has an additional experiment on MNIST and F-MNIST looking at trees generated using Haar features. This paper focuses on improving the computational efficiency of the construction of a decision tree. The paper proposes a scheme that combines row sub-sampling and an adaptive column subsampling to reduce the computational cost of finding the best split at each internal node during the tree construction. The authors present some theoretical guarantees for the computational gain and the reduction in the loss function. The empirical evaluation compares the train/test error vs computational complexity tradeoffs of the proposed scheme against various baselines and demonstrate significantly better tradeoffs, at times demonstrating over 2-3 orders of magnitude speedups. The empirical evaluation also highlights an application where the number of columns are very high -- a decision tree for Haar features of images, again showing significantly better tradeoffs than considered baselines. 
abstractText: Decision trees are a convenient and established approach for any supervised learning task. Decision trees are used in a broad range of applications from medical imaging to computer vision. Decision trees are trained by greedily splitting the leaf nodes into a split and two leaf nodes until a certain stopping criterion is reached. The procedure of splitting a node consists of finding the best feature and threshold that minimizes a criterion. The criterion minimization problem is solved through an exhaustive search algorithm. However, this exhaustive search algorithm is very expensive, especially, if the number of samples and features are high. In this paper, we propose a novel stochastic approach for the criterion minimization. Asymptotically, the proposed algorithm is faster than conventional exhaustive search by several orders of magnitude. It is further shown that the proposed approach minimizes an upper bound for the criterion. Experimentally, the algorithm is compared with several other related state-of-the-art decision tree learning methods, including the baseline non-stochastic approach. The proposed algorithm outperforms every other decision tree learning (including online and fast) approaches and performs as well as the baseline algorithm in terms of accuracy and computational cost, despite being non-deterministic. For empirical evaluation, we apply the proposed algorithm to learn a Haar tree over MNIST dataset that consists of over 200, 000 features and 60, 000 samples. This tree achieved a test accuracy of 94% over MNIST which is 4% higher than any other known axis-aligned tree. This result is comparable to the performance of oblique trees, while providing a significant speed-up at both inference and training times.
references.authors: Frénay Benoı̂t Mark Van Heeswijk Yoan Miche Michel Verleysen Amaury Lendasse
references.title: Feature selection for nonlinear models with extreme learning
references.venue: machines. Neurocomputing,
references.authors: Dhruba Kumar Bhattacharyya Jugal Kumar Kalita
references.title: Network anomaly detection: A machine learning perspective
references.venue: Crc Press,
references.authors: Paul S Bradley Olvi L Mangasarian
references.title: Feature selection via concave minimization and support vector machines
references.venue: In ICML,
references.authors: Leo J. Breiman Jerome H. Friedman R.A. Olshen Charles J. Stone
references.title: Classification and Regression Trees
references.authors: Qing Chen Nicolas D Georganas Emil M Petriu
references.title: Real-time vision-based hand gesture recognition using haar-like features
references.venue: IMTC
references.authors: Jaesik Choi
references.title: Realtime on-road vehicle detection with optical flows and haar-like feature detectors
references.venue: Technical report,
references.authors: José Carlos Cortizo Ignacio Giraldez
references.title: Multi criteria wrapper improvements to naive bayes learning
references.venue: In International Conference on Intelligent Data Engineering and Automated Learning,
references.authors: Antonio Criminisi Jamie Shotton
references.title: Decision Forests for Computer Vision and Medical Image Analysis
references.venue: Advances in Computer Vision and Pattern Recognition. Springer-Verlag,
references.authors: Sanmay Das
references.title: Filters, wrappers and a boosting-based hybrid for feature selection
references.venue: In Icml,
references.authors: Manoranjan Dash Huan Liu
references.title: Feature selection for classification
references.venue: Intelligent data analysis,
references.authors: Cem Demirkir B Sankur
references.title: Face detection using boosted tree classifier stages
references.venue: In Proceedings of the IEEE 12th Signal Processing and Communications Applications Conference,
references.authors: Luc Devroye László Györfi Gábor Lugosi
references.title: A probabilistic theory of pattern recognition, volume 31
references.venue: Springer Science & Business Media,
references.authors: Yoav Freund Robert Schapire Naoki Abe
references.title: A short introduction to boosting
references.venue: Journal-Japanese Society For Artificial Intelligence,
references.authors: Johannes Gehrke Venkatesh Ganti Raghu Ramakrishnan Wei-Yin Loh
references.title: Boatoptimistic decision tree construction
references.venue: In Proceedings of the 1999 ACM SIGMOD international conference on Management of Data,
references.authors: Isabelle Guyon André Elisseeff
references.title: An introduction to variable and feature selection
references.venue: Journal of machine learning research,
references.authors: Trevor Hastie Robert Tibshirani Jerome H. Friedman
references.title: The elements of statistical learning: data mining, inference, and prediction
references.authors: David Heath Simon Kasif Steven Salzberg
references.title: Induction of oblique decision trees
references.venue: In IJCAI,
references.authors: Charles Antony Richard Hoare
references.title: Algorithm 64: quicksort
references.venue: Communications of the ACM,
references.authors: Vijay S Iyengar Chidanand Apte Tong Zhang
references.title: Active learning using adaptive resampling
references.venue: In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: George H John Ron Kohavi Karl Pfleger
references.title: Irrelevant features and the subset selection problem
references.venue: In Machine Learning Proceedings
references.authors: Michael Jones Paul Viola
references.title: Fast multi-view face detection
references.venue: Mitsubishi Electric Research Lab TR-20003-96,
references.authors: Alan Jović Karla Brkić Nikola
references.title: Bogunović. A review of feature selection methods with applications. In 2015 38th international convention on information and communication technology, electronics and microelectronics (MIPRO)
references.authors: Ron Kohavi Dan Sommerfield
references.title: Feature subset selection using the wrapper method: Overfitting and dynamic search space topology
references.venue: In KDD, pp
references.authors: Daphne Koller Mehran Sahami
references.title: Toward optimal feature selection
references.venue: Technical report, Stanford InfoLab,
references.authors: Flip Korn B-U Pagel Christos Faloutsos
references.title: On the” dimensionality curse” and the” self-similarity blessing
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Ju-Hyun Kwak Il-Young Woen Chang-Hoon Lee
references.title: Learning algorithm for multiple distribution data using haar-like feature and decision tree
references.venue: KIPS Transactions on Software and Data Engineering,
references.authors: Natalia Larios Bilge Soran Linda G Shapiro Gonzalo Martı́nez-Muñoz Junyuan Lin Thomas G Dietterich
references.title: Haar random forest features and svm spatial matching kernel for stonefly species identification
references.venue: In 2010 20th International Conference on Pattern Recognition,
references.authors: Rainer Lienhart Jochen Maydt
references.title: An extended set of haar-like features for rapid object detection
references.venue: In Proceedings. international conference on image processing,
references.authors: Chao Liu Dongxiang Jiang Wenguang Yang
references.title: Global geometric similarity scheme for feature selection in fault diagnosis
references.venue: Expert Systems with Applications,
references.authors: Linxi Liu Wing Hung Wong
references.title: Multivariate density estimation based on adaptive partitioning: Convergence rate, variable selection and spatial adaptation
references.authors: Sebastián Maldonado Richard Weber Fazel Famili
references.title: Feature selection for high-dimensional class-imbalanced data sets using support vector machines
references.venue: Information sciences,
references.authors: Takeshi Mita Toshimitsu Kaneko Osamu Hori
references.title: Joint haar-like features for face detection
references.venue: In Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1,
references.authors: Mohammad Mahdi Moghimi Maryam Nayeri Majid Pourahmadi Mohammad Kazem Moghimi
references.title: Moving vehicle detection using adaboost and haar-like feature in surveillance
references.venue: videos. arXiv preprint arXiv:1801.01698,
references.authors: Ki-Yeong Park Sun-Young Hwang
references.title: An improved haar-like feature for efficient object detection
references.venue: Pattern Recognition Letters,
references.authors: Minh-Tri Pham Tat-Jen Cham
references.title: Fast training and selection of haar features using statistics in boosting-based face detection
references.venue: IEEE 11th International Conference on Computer Vision,
references.authors: J. Ross Quinlan
references.title: Induction of decision trees
references.venue: Machine learning,
references.authors: J Ross Quinlan. C
references.title: 5: programs for machine learning
references.authors: Parikshit Ram Alexander G Gray
references.title: Density estimation trees
references.venue: In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Irene Rodriguez-Lujan Charles Elkan Carlos Santa Cruz Ramón Huerta
references.title: Quadratic programming feature selection
references.venue: Journal of Machine Learning Research,
references.authors: Marco Sandri Paola Zuccolotto
references.title: Variable selection using random forests. In Data analysis, classification and the forward search
references.authors: Jeffrey C Schlimmer Douglas Fisher
references.title: A case study of incremental concept induction
references.venue: In AAAI,
references.authors: Shai Shalev-Shwartz
references.title: Online learning and online convex optimization
references.venue: Foundations and trends in Machine Learning,
references.authors: Sanaz Sheikhi Seyed Morteza Babamir
references.title: A predictive framework for load balancing clustered web servers
references.venue: The Journal of Supercomputing,
references.authors: Sanaz Sheikhi Seyed Morteza Babamir
references.title: Using a recurrent artificial neural network for dynamic self-adaptation of cluster-based web-server systems
references.venue: Applied Intelligence,
references.authors: Jiliang Tang Salem Alelyani Huan Liu
references.title: Feature selection for classification: A review
references.venue: Data classification: Algorithms and applications, pp
references.authors: Pooya Tavallali Mehran Yazdi Mohammad Reza Khosravi
references.title: Robust cascaded skin detector based on adaboost
references.venue: Multimedia Tools and Applications,
references.authors: Pooya Tavallali Peyman Tavallali Mohammad Reza Khosravi Mukesh Singhal
references.title: Interpretable synthetic reduced nearest neighbor: An expectation maximization approach
references.venue: IEEE International Conference on Image Processing (ICIP),
references.authors: Paul E Utgoff
references.title: Incremental induction of decision trees
references.venue: Machine learning,
references.authors: Paul Viola Michael Jones
references.title: Rapid object detection using a boosted cascade of simple features
references.venue: In Proceedings of the 2001 IEEE computer society conference on computer vision and pattern recognition. CVPR 2001,
references.authors: Haixun Wang Wei Fan Philip S Yu Jiawei Han
references.title: Mining concept-drifting data streams using ensemble classifiers
references.venue: In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Ian H Witten Eibe Frank
references.title: Data mining: practical machine learning tools and techniques with java implementations
references.venue: Acm Sigmod Record,
references.authors: Kun Yang Wing Hung Wong
references.title: Density estimation via adaptive partition and discrepancy control
references.venue: arXiv preprint arXiv:1404.1425,
references.authors: Lei Yu Huan Liu
references.title: Feature selection for high-dimensional data: A fast correlation-based filter solution
references.venue: In Proceedings of the 20th international conference on machine learning
references.authors: Devroye
references.title: Proof sketch of theorem 5: Proof Sketch: Assuming the data IID. The criterion is bounded by 0 from below. At each node, a partition that is minimum of the objective function over a set of features
sections.text: Decision trees are a convenient and established approach for any supervised learning task. Decision trees are used in a broad range of applications from medical imaging to computer vision. Decision trees are trained by greedily splitting the leaf nodes into a split and two leaf nodes until a certain stopping criterion is reached. The procedure of splitting a node consists of finding the best feature and threshold that minimizes a criterion. The criterion minimization problem is solved through an exhaustive search algorithm. However, this exhaustive search algorithm is very expensive, especially, if the number of samples and features are high. In this paper, we propose a novel stochastic approach for the criterion minimization. Asymptotically, the proposed algorithm is faster than conventional exhaustive search by several orders of magnitude. It is further shown that the proposed approach minimizes an upper bound for the criterion. Experimentally, the algorithm is compared with several other related state-of-the-art decision tree learning methods, including the baseline non-stochastic approach. The proposed algorithm outperforms every other decision tree learning (including online and fast) approaches and performs as well as the baseline algorithm in terms of accuracy and computational cost, despite being non-deterministic. For empirical evaluation, we apply the proposed algorithm to learn a Haar tree over MNIST dataset that consists of over 200, 000 features and 60, 000 samples. This tree achieved a test accuracy of 94% over MNIST which is 4% higher than any other known axis-aligned tree. This result is comparable to the performance of oblique trees, while providing a significant speed-up at both inference and training times.
sections.heading: 1 INTRODUCTION
sections.text: Decision trees are among the most established machine learning models in the scientific community and have been widely used in various applications, such as computer vision and medical imaging Criminisi & Shotton (2013); Freund et al. (1999); Breiman (2001); Tavallali et al. (2019). Decision trees are extensively used as a sub-procedure in ensemble models, such as boosting and forest Criminisi & Shotton (2013). Decision tree training consists of recursively splitting a leaf node into one split and two leaf nodes Breiman et al. (1984); Gehrke et al. (1999). The split node consists of a decision stump that routs the samples to either of its left or right children. The splitting of a leaf node is cast as selecting the best feature and threshold that minimizes a desired criterion. The criterion is an impurity function, such as Gini index Breiman et al. (1984), cross-entropy Quinlan (1986), uniform piece-wise constant densities Ram & Gray (2011), Gaussian differential (continuous) entropy Criminisi & Shotton (2013) and others Yang & Wong (2014); Liu & Wong (2014); Sheikhi & Babamir (2018; 2016). The best feature and threshold are selected through an incremental algorithm that evaluates combination of every possible feature and threshold. However, this algorithm becomes computationally very expensive if the dataset is large or high dimensional. The computational complexity of solving criterion minimization problem isO(DNlogN), whereN and D are number of samples and dimensionality, respectively. The computational complexity becomes very high especially when N and D are high since N and D are multiplied in the computational complexity term (O(DNlogN)). In this paper, we tackle the abovementioned issue by applying the splitting algorithm in a novel iterative and stochastic fashion, where less important features are discarded at each iteration.
  The literature includes many proposals for speeding up the training procedures of various learning algorithms. One common approach is preprocessing the dataset by reducing the sample size or applying some feature selection technique Dash & Liu (1997); Jović et al. (2015); John et al. (1994). Pre-training feature selection will potentially lead to a less computationally expensive process for learning Jović et al. (2015); Kohavi & Sommerfield (1995); Koller & Sahami (1996); Korn et al. (2001). Feature selection algorithms are generally categorized in two groups of filter and wrapper approaches.
  The filter approaches consist of selecting features with regard to a desired criterion Jović et al. (2015). Generally, filter approaches use statistical measures, such as minimum Redundancy maximum Relevance-(mRmR) Tang et al. (2014), correlation Yu & Liu (2003), chi-square Moh’d A Mesleh (2007), information gain Bhattacharyya & Kalita (2013), gain ratio Witten & Frank (2002), etc.
  The wrapper approaches consist of selecting features and minimizing the loss function jointly Bhattacharyya & Kalita (2013); Bradley & Mangasarian (1998); Maldonado et al. (2014); Hastie et al. (2009). However, feature selection as a preprocessing method might not lead to an accurate final model since features are not guaranteed to contribute to lower loss Jović et al. (2015). Nevertheless, wrappers are practical only for fast modeling algorithms or greedy search strategies, such as linear SVM Liu et al. (2014), Nave Bayes Cortizo & Giraldez (2006), and Extreme Learning Machines Benoı̂t et al. (2013).
  In Embedded approaches, first a filter approach is applied to select a subset of features and then followed by a wrapper approach to select the best candidate feature Guyon & Elisseeff (2003); Das (2001). Different decision tree algorithms, such as CART Breiman et al. (1984), C4.5 Quinlan (2014), and random forest are commonly used as embedded methods Sandri & Zuccolotto (2006).
  The feature selection as a preprocessing approach decreases the computational complexity of training algorithm. However, it is suboptimal w.r.t. the objective function of training, and is inefficient for large datasets since it does not decrease computation over number of samples Rodriguez-Lujan et al. (2010).
  A well-known approach that tackles the issue of large datasets is online learning Utgoff (1989). Various studies consider applying online learning to decision trees Utgoff (1989); Schlimmer & Fisher (1986); Wang et al. (2003). Such algorithms are fast, simple, and often make few statistical assumptions. The objective of online learning is to update and train the model from a stream of data Shalev-Shwartz et al. (2011). At each time step, the model gets updated optimally with respect to the recently acquired samples. Online learning is more computationally efficient compared to offline learning where the entire trainset is used for training Shalev-Shwartz et al. (2011). However, these algorithms increase the size of the tree when visiting a new batch of the data.
  Despite the extensive usages and applications of decision trees Criminisi & Shotton (2013), few algorithms have focused on decreasing the high computational cost of inducing a tree ??. However, the literature leaves a gap in treating the high computational complexity of inducing the decision tree and exploring potential improvements. None of the previous research propose the computational complexity of their algorithm or provide any analysis of the goodness of features selected at the split node. To address this gap, we investigated both computational complexity of SDT and its efficiency in finding near optimum feature at the split node. In ?, authors propose to randomly select a subset of features at the split node and then find the best feature among the set using all samples present at the node. However, due to randomness, the optimality of this process is not guaranteed.
  The high computational cost is mainly rooted in the exhaustive search algorithm applied for solving the split criterion. This algorithm specially becomes computationally expensive if the dataset is large and high dimensional. It is because the computational complexity of solving the splitting criterion is O(DNlogN) Hoare (1961); Breiman et al. (1984). To counter the aforementioned issues, we propose an accurate and fast Stochastic Decision Tree (SDT) induction algorithm that minimizes the splitting criterion efficiently. At a node, the proposed algorithm starts with an empty set St and all D features. At node j, the algorithm iteratively selects a tiny random set of samples from Sj (in order of 2−C × |Sj |) and discards half of the less important features w.r.t St. Sj and |Sj | are the set and number of samples present at the jth node,
  respectively. For the best feature and threshold found at each iteration, SDT minimizes an upper bound of the splitting criterion, monotonically. Overall, the algorithm steeply descends towards the minimum of the criterion function. It is also demonstrated by the results at the experiments section. Mathematically speaking, we show that the algorithm provides higher priority to more distinctive features. Essentially, the more distinctive a feature, the greater the chance of it being selected at the final iteration. The computational complexity of the algorithm for constructing a tree of depth ∆ is O(∆DNlog N 2C
  2C ). C is a hyperparameter and in our experiments we set it to 10. The computational
  complexity achieved by SDT is smaller than that of the original approach (withO(∆DNlogN)) and its optimal implementation (O(∆DN +DNlogN)) by several orders of magnitude. Our approach is faster because it focuses on breaking down the computational complexity created due to the large number of samples and features. Numerically speaking, SDT shows its advantage over other implementations when the sizes of samples and features are high (ND is very high). Experimentally, the proposed algorithm could achieve same or improved accuracy as the original greedy algorithm Breiman et al. (1984) while surpassing every other related state-of-the-art algorithms both in terms of accuracy and complexity by several orders of magnitude. For empirical evaluation, we applied our algorithm to learn a Haar tree over MNIST where Haar Viola & Jones (2001) filters were used to extract 200, 000 features from the dataset. The Haar tree could achieve competitive accuracy to more complicated trees, such as oblique trees and optimal oblique trees while its inference time was far smaller. Theoretically, an oblique tree needs O(D∆) operations to produce prediction, while Haar tree only needs O(D + ∆). ∆ is the maximum depth of the tree. In terms of size, Haar tree takes O(2∆) space while oblique tree takes O(D2∆) space.
sections.heading: 2 PRELIMINARIES
sections.heading: 2.1 INDUCTION OF A DECISION TREE
sections.text: Every decision tree construction algorithm tends to minimize the following objective function
  Lα(T ) = L(T ) + α× leaves(T ), α > 0, (1)
  where, L(T ) is a loss function of the tree (T ) over a trainset, leaves(.) represents the number of leaves in a tree, and α > 0 is cost complexity coefficient. After constructing the tree, pruning is performed to minimize the cost function Lα(T ) over the validationset. Finding the optimum of this problem is NP-complete ?. Therefore, state-of-the-art algorithms for constructing a tree consist of greedily splitting a leaf node into a split and two leaf nodes.
  Assume a dataset S consisting N pairs of observation {(xi, yi)}Ni=1 where xi ∈ RD and yi ∈ {1, 2, 3, ...,M}. The function fj(x) at the jth split node consists of a decision stump fj(x) = sign(xp − th) where superscript p and th represent pth feature and the threshold, respectively. At the growing phase of a decision tree, p and th are found optimally with respect to some criteria Breiman et al. (1984). Usually the tree is grown until some stopping criterion or maximum depth is reached.
  The problem of constructing a split node consist of minimizing the desired criterion over the samples of each child of the node.
  min fj ∑ fj={−1,1} |Sfjj | |Sj | H(S fj j )
  s.t fj(x) = sign(x p − th)
  (2)
  where, Sfjj is set of samples at the left child (fj = −1) or right child (fj = 1) of a node j, Sj is the set of samples present at the jth node, and |.| returns the number of samples at its input set. H is an entropy function. The optimum of problem equation 2 can be found in O(DNj logNj) where Nj and D are number of samples at node j (|Sj |) and features, respectively. This is done by sorting all samples along each feature and incrementally finding the best threshold for each feature Breiman et al. (1984).
sections.heading: 3 PROPOSED METHOD
sections.text: The computational complexity of solving problem equation 2 is high, especially, if the number of features and samples are large. In this section, we propose an algorithm that minimizes problem equation 2 faster than original approach Breiman et al. (1984) by several orders of magnitude.
  Basic idea: Problem equation 2 consists of selecting the best feature to partition the space into two parts optimally. State-of-the-art algorithms find the best feature through the exhaustive search mentioned in Section 2.1. In this section, we propose a stochastic exhaustive search method for solving problem equation 2 that has a low computational cost. The idea is based on 3 pieces of information. Info. #1 Each feature can be approximately ranked based on the objective function of equation 2 over a small random subset of the samples. Info. #2 A precise ranking of the features requires larger subset of the samples. Info. #3 The good news is that only ranking of the most competitive features require high precision. As a result, by combining Info #1-3, the algorithm consists of discarding less important features and randomly selecting more samples from the dataset at each iteration. This procedure gradually increases the precision of ranking for more important features. We call this algorithm the stochastic induction of decision tree (SDT).
  The algorithm Now we describe the proposed algorithm for solving criterion problem equation 2. The algorithm starts with Sjc = Sj , an empty set Sjt , and set of features Dt = {p}Dp=1 features. p represents the pth feature. The algorithm proceeds as follows:
  Step 1 Randomly select and remove Nj 2C
  samples from Sjc and add them to set Sjt . C is a user defined hyper-parameter.
  Step 2 ∀p ∈ Dt, at kth iteration, find feature importance of pth feature (FIkp ) by solving
  (FIkp ) −1 = min
  th
  ∑ fj={−1,1} |Sfjjt | |Sjt | H(S fj jt )
  s.t fj(x) = sign(x p − th)
  (3)
  where, Sfjjt represents the set of samples from Sjt routed to the left child (fj = −1) or the right child fj = 1. FIkp represents the feature importance of p
  th feature at kth iteration. Note that the optimization is only happening over th in equation 3 and (FIkp )
  −1 is equal to the optimum of objective function in equation 3. Problem in equation 3 can be efficiently solved in O(|Sjt |log(|Sjt |)) Breiman et al. (1984).
  Step 3 Sort all the features in Dt based on FIkp and discard half of the features in Dt with lowest FI .
  Step 4 Iterate over steps 1-3 for α times. α is a user-defined hyper-parameter.
  Step 5 Solve problem equation 2 for only the remaining features in Dt over the Sj .
  In practice, we select C to be around 10 and α to be around 7 − 10, depending on the dataset. Intuitively, C and α are the hyper-parameters that control the computational complexity of the algorithm. C controls the number of samples to be used at each iteration and α controls the number of features to be used at the last iteration. With higher values for C and α, the computational complexity decreases further. However, there is a possibility that the model loses accuracy with extremely high C and α .
  To keep the computational complexity low, one can keep the samples in Sjt sorted for the remaining features (Dt) from the previous iterations at Step 2. Only the newly selected samples from Step 1 have to be sorted and merged with Sjt . The merging will take at most |Sjt |. In total, this will keep the computational complexity of step 2 atO(2DNj
  2C log( Nj 2C )) for all the α steps (assuming α→∞).
sections.heading: 4 ANALYSIS OF THE PROPOSED ALGORITHM
sections.text: In this section, several theoretical properties of the algorithm are explored and analyzed.
sections.heading: 4.1 COMPUTATIONAL COMPLEXITY
sections.text: The computational complexity of splitting a node and induction of a tree are analyzed in this Subsection.
  In the following theorem, we assume that the samples of Sjt from previous iterations are NOT kept sorted. After the theorem, we will show how keeping samples sorted can affect the node training complexity and storage overhead. Theorem 1 (node training complexity). The computational complexity of splitting the node using SDT is O(4DN0logN0), where N0 = Nj2C .
  Proof. At each iteration, N0 samples are added to the set Sjt and half of the features are discarded. To solve equation 3, samples along each remaining feature have to be sorted that takes O(|Sjt |logSjt). At the kth iteration, |Sjt | is (k + 1)N0. Therefore, the total complexity of steps 1-4 is as follows:
  α∑ k=0 D 2k (k + 1)N0log(k + 1)N0 (4)
  The summation in equation 4 can further be simplified to: α∑ k=0 D 2k (k + 1)N0(logN0 + log(k + 1)) ≤ DN0(logN0 + log(α+ 1)) α∑ k=0 k + 1 2k (5)
  Using the formula for the geometrical series of ∑∞ k=0 k+1 2k = ∑∞ k=0 1 2k + ∑∞ k=1 1 2k + ∑∞ k=2 1 2k + ... = 2 + 1 + 12 + 1 4 + ... = 4 in the right hand side of inequality of equation 5, we have
  DN0(logN0 + log(α+ 1)) α∑ k=0 k + 1 2k ≤ 4DN0(logN0 + log(α+ 1)) (6)
  Asymptotically speaking, the computational complexity is being driven by the term 4DN0logN0. Note that log(α + 1) is relatively very small compared to logN0 (Numerically speaking, N0 is in order of 100 − 200 while α is in order of 7 − 10). Therefore, the computational complexity asymptotically becomes O(4DN0logN0).
  The computational complexity of the baseline algorithm for solving equation 2 is O(DNj logNj), which is 2C times larger than the proposed stochastic approach.
  Effect of keeping the Sjt sorted Effect of keeping the Sjt sorted is that k+1 is removed from the formula equation 4. Therefore, the computational complexity changes to O(2DN0logN0). However, it will increase the space usage slightly ((k + 1)N0 new variables need to be saved to keep the label of samples along each feature).
  Assuming a maximum depth of ∆ for the tree, the computational complexity of inducing the whole tree will be O(∆4DNlog N 2C
  2C ). It is trivial to prove by simply using the fact that the children of each
  node receive a disjoint set of samples from its parent and the fact that total samples at the same depth are at most N . This complexity is smaller than complexity of the baseline approach Breiman et al. (1984) by an order of 2C .
sections.heading: 4.2 RELATION TO OBJECTIVE FUNCTION
sections.text: In this section, the value of the objective function in equation 2 is evaluated using the best combination of feature and threshold found by the SDT at each iteration over Sjt . For simplicity, throughout this section, the objective function of equation 2 is represented by L(Sj). Consequently, L(Sjt) represents error over the set Sjt . In this section, we assume the used criterion is misclassification error H(S
  fj j ) = 1−p fj m∗ , where p fj m andm∗ represent ratio of classm in the fj child and majority class in the partition, respectively. All the theorems and analysis can be readily extended to Gini-index and Cross-entropy Breiman et al. (1984) by applying their corresponding differences. The differences and how to apply them are explained after next theorem.
  Theorem 2 (Monotonic decrease of an upper bound). The algorithm will monotonically decrease an upper bound over the objective function of equation 2.
  Proof. At each iteration k, the following equality holds:
  |Sj |Lk(Sj) = |Skjt |Lk(Skjt) + |Skjc |Lk(Skjc) (7)
  where, the superscript k for sets and Lk(.) represents the set of samples at the kth iteration and the value of error with optimum parameters for Skjt over the input set, respectively. The loss L(.) is always bounded from above (e.g., for misclassification, it is 1) by a constant value Lmax. By replacing Lk(Skjc) with Lmax in equation 7, for iteration k we have
  |Sj |Lk(Sj) ≤ |Skjt |Lk(Skjt) + |Skjc |Lmax = |Sj |Lkupper(Sj) (8)
  At each iteration, the first term in equation 8 is minimized. Therefore, the new optimum parameters at each iteration provide lower error to the first term of equation 8 than the optimum parameters of previous iteration which is |Sk+1jt |L k(Sk+1jt ) ≥ |S k+1 jt |L
  k+1(Sk+1jt ). Note that the superscript of the loss L is different for both sides of the inequality. Also, |Sk+1jc | < |Skjc |. Therefore,
  |Sk+1jt |L k+1(Sk+1jt ) + |S k+1 jc |Lmax
  |Sj | = Lk+1upper(Sj) ≤ Lkupper(Sj) (9)
  For the case of Gini-index or Cross-entropy, formula equation 7 should be replaced with Lk(Sj) ≤ Lk(Skjt) + L k(Skjc). The reason for this change is that the algorithm finds optimum over S k jt and min(Lk(Skjt), L k(Skjc)) ≤ Lk(Sj) ≤ max(Lk(Skjt), Lk(Skjc)).
  Average Decrease The Theorem equation 2 is based on worst case scenario. The proof of Theorem equation 2 assumes that the samples selected at each iteration do not have any correlation with the rest of samples. In reality, this is not necessarily correct and set of Sjt can partially represent the whole trainset Sj and as size of Sjt increases through iterations, the FIp is measured more correctly. In our experiments, we observed a very steep decrease in Lk(Sjt) after each iteration and after several iterations, it almost converged to the loss of the best possible feature and threshold. More discussion and experiments are presented in supplemental materials. Theorem 3 (Probability of discarding a feature). Assume a binary classification dataset where samples are generated from some distribution along each feature and features are independent. We assume the samples of both classes have varying degrees of overlap along each feature. Probability of a sample being generated from the overlap area is P po for p
  th feature. The probability of discarding a feature depends on P po .
  Proof. Picking N0 samples randomly from an infinitely large Nj is equivalent to directly sampling from the distribution itself. Selecting samples is the same as flipping a coin with probability of P po to be 1 and 1− P po to be 0. Expectation of observing 1 is P po and essentially, on average, we expect to observe P po ×N0 samples from the overlap area. Probability of deviating from average case and observing FIkp being worse than the true FIp (please note that FI corresponds to goodness of a
  feature) over the whole trainset is equivalent to probability of observing at least 1 extra (observing P p0 × N0 + 1 from overlap area) sample from the overlap area. Therefore, P (FIkp < FIp) = 1− (1− P ko )N0(1−P k o ) (or 1− probability of observing no extra sample from overlap area) which is an upper bound to probability of discarding a feature.
  The probability of overlap area P po is inversely related to FI k p since samples with lower overlap area (lower P po ) are more distinctive; thus, such features have higher FI k p . The Theorem 3 implies that the features with higher true FIp are more likely to stay in the iterations on average. For example, assume a feature that completely separates samples of both classes (P po = 0) – any random set of samples will represent this distinction because of having no overlap. Such a feature will achieve FIkp =∞, hence, the feature will remain in the Dt. Theorem 4 (Consistency of SDT). The SDT is consistent and can learn the function that generated the classes.
  Theorem 5 (Decrease of the cost). The objective function of equation 2 decreases as new nodes are added.
  The proofs are provided in the supplemental materials. It is worth mentioning that both the theorems of 4 and 5 are true for original decision trees (such as CART) under some mild assumptions and here we show that SDT follows them too.
sections.heading: 5 EXPERIMENTAL RESULTS
sections.text: In this section, we present results of experiments to show the merits of our proposed method. The SDT is compared with several other state-of-the-art algorithms and the baseline tree induction. Figures 1 and 2 present error ratio of train and test versus the computational complexity of each studied algorithm. The existing algorithms selected in the study consist of adaptive re-sampling Iyengar et al. (2000), using feature selection as pre-training procedureTang et al. (2014); Moh’d A Mesleh (2007), C4.5 Quinlan (2014), and CART Breiman et al. (1984). The adaptive re-sampling consists of iteratively training a tree from the scratch with respect to a tiny set of samples and expanding the set with wrongly classified samples by the tree at each iteration. We applied the adaptive re-sampling in two different setups. In one setup, we applied the adaptive re-sampling of Iyengar et al. (2000) until the algorithm achieves better accuracy or similar to that of SDT (Adaptive re-sampling 2). In the other setup, we followed the same steps as provided by Iyengar et al. (2000) (Adaptive re-sampling 2). For feature selection as a pre-training setup, we used ChiSquare and mRmR Tang et al. (2014); Moh’d A Mesleh (2007). The pre-training feature selections were applied to select 1%, 50%, and
  90% of features. The C4.5 was trained using the same setup as Quinlan (2014). The decision tree curve represents the CART algorithm Breiman et al. (1984). All the trees were trained for depths of 5-12. In figures 1 and 2, the number at each point on the curve represents the depth of the tree. The vertical axis shows the error ratio and horizontal axis shows the computational complexity of the trained model. For SDT, we set N0 = 20 for all experiments. The SDT iterated until the number of features remained in Dt are around 0.5% of the total features. Description of datasets are presented in table 1.
  Figures 1 and 2 depict that SDT outperformed other fast tree training algorithms in both accuracy and computational complexity. The training complexity of SDT is smaller by several orders of magnitude (102−3). It is worth mentioning that although SDT uses less computation, its accuracy is the same as CART algorithm. Therefore, SDT has served its purpose which was decreasing the complexity of training while maintaining the accuracy.
sections.heading: 5.1 HAAR TREE
sections.text: Haar-like features are well-known in the literature of image processing and have been extensively used for face detection Viola & Jones (2001); Jones & Viola (2003); Demirkir & Sankur (2004); Mita et al. (2005); Pham & Cham (2007), object detection Lienhart & Maydt (2002); Park & Hwang (2014); Chen et al. (2007); Choi (2012) and ensembles Moghimi et al. (2018); Kwak et al. (2013); Larios et al. (2010). The Haar-like features are extracted by convolving various sizes of
  the Haar-filters with the image. Haar features are explained further in the supplemental materials. However, the number of features extracted by Haarlike features is very high; thus, training a model using these features can be very challenging and expensive. SDT is designed to overcome such a challenging task and we trained trees over Haar-like features using SDT. We call such tree as Haar tree. We applied
  Haar-like features to MNIST and FMNIST to extract new features. The size of each region of used Haar filters are (3n, 3m) for m,n = 1, 2, ..., 8. 121000 features were extracted from images of 28× 28. Figure 3 presents inference complexity versus error ratio for each model. We compared Haar trees with oblique trees Heath et al. (1993), axis-aligned trees Breiman et al. (1984), RBF-SVM and nearest neighbor k-means. The RBF-SVM consists of training SVM over various Radial Basis Functions (RBF). The center of RBFs are found using k-means algorithm. The width of the RBFs were found using a validationset (trainset was split to 80% train and 20% validation). The k-means model consisted of training a k-means and then using centroids as a nearest neighbor model (used similar to Tavallali et al. (2020)). The label of centroids were selected as the majority of label of samples assigned to each centroid. The horizontal axis in figure 3 represents the computational complexity of evaluating the model for an input (inference complexity). The vertical axis shows the error ratio over the testset. The number at each point on a curve represents the depth of the tree or number of centroids. We observed that the Haar trees were able to achieve better accuracy than the other trees and also better or similar accuracy to other nearest neighbor-based models. The Haar trees are the first axis-aligned trees to achieve accuracy higher than any other axis-aligned trees as per our study. Other axis-aligned trees have never passed the accuracy of 90% over MNIST while Haar Tree could achieve accuracy of 93%. Asymptotically, the inference of a Haar Tree isO(D+∆) because first an integral image is calculated and then at each node, the desired feature is calculated only using the integral image Viola & Jones (2001). The inference of oblique tree (OC1), k-means, and RBF-SVM are O(D∆), O(DK) and O(D(K + 1)), respectively. As can be observed, Haar Trees are faster than other models asymptotically while Haar Trees could achieve smaller test error.
sections.heading: 6 LIMITATIONS:
sections.text: This paper provides the first stochastic approach for induction of a decision tree. Consequently, the model and the proposed algorithm suffers from limitations that a decision tree might suffer. However, in the context of decision tree and ensemble models it potentially can enhance the state of the field, since the approach enables faster and more computationally efficient creation of decision tree and forest models. The approach essentially opens the path for introduction of tree-based convolution filters.
sections.heading: 7 CONCLUSION
sections.text: The tree training is expensive because of the exhaustive search for solving the criterion minimization problem. Despite the vast usage of decision trees in a broad range of applications such image processing, computer vision, and medical diagnosis, the mentioned problem has not been objectively approached. We tackled the problem by proposing a novel stochastic approach for tree induction. To the best of our knowledge, the SDT is the first stochastic algorithm designed for induction of trees through greedy approach. Asymptotically, the SDT improved the decision tree induction complexity by orders of magnitude. It was shown that the algorithm is likely to find the best feature and threshold at the split node. It was also shown that the algorithm minimizes an upper bound for the criterion problem. Experimentally, the SDT could achieve same accuracy as the baseline tree CART and outperformed other similar methods (e.g., online and fast tree induction). In the experiments, SDT could train a tree faster than other algorithms by several orders of magnitude. Finally, using SDT, we tackled the challenging problem of training Haar Trees. The Haar Trees could achieve better accuracy than other more complicated machine learning models, such as oblique trees and nearest neighbor-based models.
sections.heading: 8 REPRODUCIBILITY
sections.text: The experiment codes (currently attached as supplementary materials) will be published on a Github repository to facilitate reproduction and extension of our results. Furthermore, the datasets used in our experiments are publicly available via the UCI repository.
sections.heading: A APPENDIX
sections.text: This is the Appendix (supplemental materials) for Stochastic Induction of Decision Trees with Application to Learning Haar Tree.
  A.1 PROPERTIES OF THE SDT
  Theorem 4 is a result of theorem 20.1 and Lemma 20.1 in Devroye et al. (2013).
  Proof sketch of theorem 5:
  Proof Sketch: Assuming the data IID. The criterion is bounded by 0 from below. At each node, a partition that is minimum of the objective function over a set of features is found. As a result, after partitioning each node, the error will decrease.
  A.2 HAAR FEATURES
  The exact haar features used for generating new features are presented in figure 4. The sizes of row pixels and column pixels are written right to each filter. For each filter, various filters with every combination of possible row and column pixels are created and convolved with the image to extract create new features.
  A.3 EXPERIMENTAL RESULTS
  In this section, several experiments that demonstrate properties of SDT are presented.
  Figure 5 shows the reduction in impurity (criterion in formula 2) at each iteration of the algorithm for MNIST dataset. Each point on the curve represents the impurity of the best feature and threshold found by the algorithm (Lk(Sj)). As figure 5 demonstrate, at each iteration, the loss function has decreased drastically and eventually has converged to the true best feature and threshold.
  Figures 6 and 7 present the importance of features at each iteration for problem of inducing one single split node for 2 classes. The feature importances were normalized to between 0 and 1.
  From figures 6 and 7, it is observable that the SDT gradually discards the less discriminative features and gives higher value to more distinctive features.
  Figures A.3 and A.3 represents computational complexity versus error ratio of train and test. In figures A.3 and A.3 various values are used for N0 to explore the effect of N0 over the final tree.
  Each curve represents the N0 by its color. The N0 for each color is defined at the legend of the plot. The depth of the tree is shown at the points on each curve.