MANIFOLD FORESTS: CLOSING THE GAP ON NEURAL NETWORKS
Authors: Ronan Perry
Tyler M. Tomita
Jesse Patsolic
Benjamin Falk
Joshua Vogelstein
Venue:  (2020)
Keywords: machine learning
structured learning
projections
structured data
images
classification

Abstract: Decision forests (DF), in particular random forests and gradient boosting trees, have  demonstrated state-of-the-art accuracy compared to other methods in many supervised learning scenarios. In particular, DFs dominate other methods in tabular data, that is, when the feature space is unstructured, so that the signal is invariant to permuting feature indices.  However, in structured data lying on a manifold---such as images, text, and speech---neural nets (NN) tend to outperform DFs. We conjecture that at least part of the reason for this is that the input to NN is not simply the feature magnitudes, but also their indices (for example, the convolution operation uses ``feature locality). In contrast, naive DF implementations fail to explicitly consider feature indices. A recently proposed DF approach demonstrates that DFs, for each node, implicitly sample a random matrix from some specific distribution.  Here, we build on that to show that one can choose distributions in a manifold aware fashion. For example, for image classification, rather than randomly selecting pixels, one can randomly select contiguous patches. We demonstrate the empirical performance of  data living on three different manifolds: images, time-series, and a torus. In all three cases, our Manifold Forest (Mf) algorithm empirically dominates other state-of-the-art approaches that ignore feature space structure, achieving a lower classification error on all sample sizes. This dominance extends to the MNIST data set as well. Moreover, both training and test time is significantly faster for manifold forests as compared to deep nets. This approach, therefore, has promise to enable DFs and other machine learning methods to close the gap with deep nets on manifold-valued data. 

MANIFOLD FORESTS: CLOSING THE GAP ON NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Decision forests (DF), in particular random forests and gradient boosting trees, have demonstrated state-of-the-art accuracy compared to other methods in many supervised learning scenarios. In particular, DFs dominate other methods in tabular data, that is, when the feature space is unstructured, so that the signal is invariant to permuting feature indices. However, structured data lying on a manifold-sunn such as images, text, and speech speech-neural neural nets (NN) tend to outperform DFs. We conjecture that at least part the reason for this is that the input to NN is not simply the feature magnitudes, but also their indices (for example, the convolution operation uses "feature locality"). In contrast, naíve DF implementations fail to explicitly consider feature indices. A recently proposed DF approach demonstrates that DFs, for each node, implicitly sample random matrix from some specific distribution. Here, we build on that to show that one can choose distributions a manifold aware fashion. For example, for image classification, rather than randomly selecting pixels, one can randomly select contiguous patches. We demonstrate the empirical performance of data living on three different manifolds: images, time-series, and torus. In all three cases, our Manifold Forest (MORe) algorithm empirically dominates other state-of-the-art approaches that ignore feature space structure, achieving lower classification error on all sample sizes. This dominance extends the MNIST data set as well. Moreover, both training and test time is significantly faster for manifold forests as compared to deep nets. This approach, therefore, has promise to enable DFs and other machine learning methods to close the gap with deep nets on manifold-valued data.
1 INTRODUCTION
Decision forests, including random forests and gradient boosting trees, have solidified themselves in the past couple decades powerful ensemble learning method in supervised settings Beernnndez-Delaadee et al.) 2014 Caruana & Niculescu-Mizn 2006). including both classification and regression (Hastie et al.) (001). In classification, each forest is collection of decision trees whose individual classifications of data point are aggregated together using majority vote. One of the strengths of this approach is that each decision tree need only perform better than chance for the forest to be strong learner, given few assumptions (Schapire, 1990, Biau et al. 2008). Additionally, decision trees are relatively interpretable because they can provide an understanding of which features are most important for correct classification Breimman| 2001). Breiman originally proposed decision trees that partition the data set using hyperplanes aligned to feature axes (Breiman 2001). Yet, this limits the flexibility of the forest and requires deep trees to classify some data sets, leading to overfitting. He also suggested that algorithms which partition based on sparse linear combinations of the coordinate axes can improve performance (Breiman 2001). More recently, Sparse Projection Oblique Randomer Forest (St ORF), partitions a random projection of the data and has shown impressive improvement over other methods (Tomita et al. 2015).
randomm forests and other machine learning algorithms frequently operate in a tabular setting, viewing an observation & = (æ1,... . "pp) >p)) T E R as unstructured feature vector. In doing so, they neglect the indices in settings where the indices encode additional information. For structured data, e.g. images or time series, traditional decision forests are not able to incorporate known continuity between features to learn new features.
For decision forests to utilize known local structure in data, new features encoding this information must be manually constructed. Prior research has extended random forests variety of computer vision tasks (Lepetit et al.) 2005 Gall et al. Bosch et al. (2007] Shotton et al. [001]) ) and augmented random forests with structured pixel label information (Kontschieder al. 201 Yet these methods either generate features a priori from individual pixels, and

---

thus do not take advantage of the local topology, or lack the flexibility learn relevant patches. Decision forests have been used to learn distance metrics on unknown manifolds (Criminisi et al, 2012). but such manifold forest algorithms are unsupervised and aim learn low dimensional representation of the data.
Inspired by SPORF, we propose a projection distribution that takes into account continuity between neighboring features while incorporating enough randomness learn relevant projections. At each node in the decision tree, sets of random spatially contiguous features are randomly selected using knowledge of the underlying manifold. Summing the intensities of the sampled features yields set of projections which can then be evaluated to partition the observations. We describe this proposed classification algorithm, Manifold Forests (MORF) in detail and show its effectiveness in three simulation settings as compared to common classification algorithms. Furthermore, the optimized and parallelizable open source implementation of MO RE in R and Python is available. This addition makes for effective and flexible learner across a wide range of manifold structures.
2
BACKGROUND AND RELATED WORK
2.1 CLASSIFICATION
In the two-class classification setting, there is data set D = {1 y:) of pairs (I,, m) drawn from an unknown
distribution Fxy where I; E X C R and yi E y {0, 1}. Our goal is to train a classifier h(r; Dw.) : X xx (Xx + The performance
y based on our observations that generalizes to correctly predict the class of observed of this classifier is evaluated via the 0-1 Loss function L(h(z),)) = I[h(x) * y] to find the optimal classifier
h' argmin, ([L(h(x), v)], which minimizes the probability of incorrect classification.
2.2 RANDOM FORESTS
Originally popularized by Breiman, the random forest (RF) classifier is empirically very effective [Fernández-Delgadee
al. 2014) while maintaining strong theoretical guarantees (Breiman, (001). A random forest is an ensemble of deciston trees whose individual classifications of data point are aggregated together using majority vote. Each decision tree consists of split nodes and leaf nodes. A split node is associated with a subset of the data S = {(1,. S D and splits into two child nodes, each associated with a binary partition of S. Let ej RP denote unit vector in the standard basis (that is, a vector with a single one and the rest of the entries are zero) and 7 a threshold value. Then S is partitioned into two subsets given the pair 0, {eg, T..
S/ = {
e < <T}
S {( vi) le,,, 2 T
To choose the partition, the optimal 6" (e), r") pair is selected via greedy search from among a set of d randomly selected standard basis vectors ej. The selected partition is that which maximizes some measure of information gain. A typical measure is decrease in impurity, calculated by the Gini impurity score I(S), of the resulting partitions (Hastie)
et al. 2001). Let Pa- 18 found
[ST Enes [[[ = k] be the fraction of elements of class k in partition S, then the optimal split
K I(S) Σ Px pxx)
0 argmax [S)((S) - 1 1S I(S))
A leaf node is created once the partition reaches a stopping criterion, typically either falling below an impurity score threshold or minimum number of observations (Hastic al., 2001). The leaf nodes of the tree form disjoint partition of the feature space in which each partition of observations S₁ is assigned a class label of corresponding to the class majority.
Σ T(u = =x)) M.
argmax
A decision tree classifies a new observation by assigning it the class of the partition into which the observation falls. The forest averages the classifications over all decision trees to make the final classification (Hastie al. 200I). For
2

---

good performance of the ensemble and strong theoretical guarantees, the individual decision trees must be relatively uncorrelated from one another. Breiman's 's random forest algorithm does this in two ways:
1. At every node in the decision tree, the optimal split is determined over random subset d of the total collection of features p.
2. Each tree is trained on randomly bootstrapped sample of data points D' C D from the full training data set.
Applying these techniques means that random forests do not overfit and lowers the upper bound of the generalization error (Breiman 2001).
2.3 SPARSE PROJECTION OBLIQUE RANDOMER FORESTS
SPORF is recent modification to random forest that has shown improvement over other versions Toomia et al. 2013 Tomita et al., 2017). Recall that RF split nodes partition data along the coordinate axes by comparing the projection e/ of observation z; on standard basis ej to threshold value т. SPORT generalizes the set of possible projections, allowing for the data be partitioned along axes specified by any sparse vector a.
S/ (( Vt) a xj <<) r}
$ = ((x,, v:) T x4 2 r}
Rather than partitioning the data solely along the coordinate axes (i.e. the standard basis), SPORF creates partitions along axes specified by sparse vectors. In other words, let the dictionary be the set of atoms {a}, each atom a p-dimensional vector defining possible projection a zz. In axis-aligned forests, A is the set of standard basis vectors {ez}. In SPORE, the dictionary can much larger, because it includes, for example, all 2-sparse vectors. At each split node, SPORE samples d atoms from D according to specified distribution. By default, each of the d atoms are randomly generated with a sparsity level drawn from a Poisson distribution with a specified rate A. Then, each of the non-zero elements are uniformly randomly assigned either +1 or -1. Note that the size of the dictionary for SF SpoRe is 3" (because each of the p elements could be 11, O, or + +1), although the atoms are sampled from a distribution heavily skewed towards sparsity.
3 METHODS
3.1 RANDOM PROJECTION FORESTS ON MANIFOLDS
In the structured setting, the dictionary of projection vectors A= {a} modified to take advantage of the underlying manifold on which the data lies. We term this method the Manifold Forest (MoR7).
Each atom a projects an observation manifold, Nonzero elements of a effectively select and weight features. Since the feature space is structured, each element of a maps to a location on the underlying manifold. Thus, patterns of contiguous points on the manifold define the atoms of A: the distribution of those patterns yields distribution over the atoms. At each node in the decision tree, MORF samples d atoms, yielding d new features per observation. MORE proceeds just like SPORE by optimizing the best split according the Gini index. Algorithm pseudocode, essentially equivalent that of SpORE , be found in the Appendix.
real number and is designed with respect to prior knowledge of the data
In the case of two-dimensional arrays, such as images, an observation x; E IP is a vectorized representation of data-matrix X, E R x To capture the relevance of neighboring pixels, MORP creates projections by summing the intensities of pixels in rectangular patches. Thus the atoms of A are the vectorized representations of these rectangular patches.
A rectangular patch is fully parameterized by the location of its upper-left corner (u,v), its height ht and width w. To generate a patch, first the index of the upper left corner is uniformly sampled. Then its height and width are independently sampled from separate uniform distributions. MORF hyperparameters determine the minimum and maximum heights heights (hmin kmaw> Jor and widths { [minn , Wmaz). respectively, to sample from. Let wni } denote the discrete uniform distribution. An atom a is sampled as follows. Note that the patch cannot exceed the
3

---

data-matrix boundaries.
(0 W Wmin
mnif(0, H hminn
w ~ unif [mmin; min min(Wmar. (max, W- =u)
~ unif(hmis mina@ H - u)}
The vectorized atom a yields a projection of the data aTv, effectively selecting and summing pixel intensities in the sampled rectangular patch.
a_ .0....,,.000 W'
0.O, O.......0 I..... 1. O,
1. O. 1.0........... 0...... Og....0 ) W-w-u Wx(H-h-o)
W
W
By constructing features in this way, MORF learns low-level features in the structured data, such as edges or corners in images. The forest can therefore learn the features that best distinguish a class. The structure of these atoms flexible and task dependent. In the case of data lying on cyclic manifold, the atoms can wrap-around borders to capture the added continuity. Atoms can also be used in one-dimensional arrays, such as univariate time-series data, in which case hmin hmaa
3.2 FEATURE IMPORTANCE
One of the benefits decision trees is that their results fairly interpretable in that they allow for estimation of the relative importance of each feature. Many approaches have been suggested (Breiman Lundberg & Lee| (2017) and here a projection forest specific metric used in which the number of times given feature was used in projections across the ensemble of decision trees is counted. A decision tree 7 is composed of many nodes k; each one associated with atom ox and threshold that partition the feature space according the projection aj 24.- Thus, the indices
corresponding to nonzero elements of aj indicate important features used in the projection. For each feature j, the number of times тī is used in a projection, across all split nodes and decision trees, counted.
J ΣΣ I(akk + #0)
These normalized counts represent the relative importance of each feature in making a correct classification. Such a method applies to both SPCRF and MORF, although different results between them would be expected due to different projection distributions yielding different hyperplanes.
4 SIMULATION RESULTS
To test MORF, we evaluate its performance in three simulation settings as compared to logistic regression (Log. Reg), linear support vector machine (Lin. SVM), support vector machine with radial basis function kernel (SVM), k-nearest neighbors (kNN), random forest (RF), Multi-layer Perceptron (MLP), and SPORE (SPORF). For each experiment, we used our open source implementation of MORF and that of Se o RF All decision forest algorithms used 100 decision trees on the simulations. Each of the other classifiers were run from the Scikit-learn Python package (Pedregosa al. 2011) with default parameters. Additionally, we tested against a Convolutional Neural Network (CNN) built using PyTorch (Paszke et al. (2017) with two convolution layers, ReLU activations, and maxpooling, followed by dropout and two densely connected layers. The CNN results were averaged over 5 runs for the simulations and training was stopped early if the loss plateaued.
4.1 SIMULATION SETTINGS
Experiment (A) is a non-Euclidean example inspired by Younes (0018). Each observation is a discretization of circle into 100 features with two non-adjacent segments of I's in differing patterns: class features two segments of length five while class 2 features one segment of length four and one of length six. MORF chose one-dimensional rectangles in this setting as the observations were ane-dimensional in nature. These projection patches had a width between one and fifteen pixels and each split node of SpoRe and MORE considered 40 random projections. Figure A shows examples from the classes and classification results across various sample sizes.
4

---

In experiment (B) consists of a simple 28 28 binary image classification problem. Images in class 0 contain randomly sized and spaced horizontal bars while those in class contain randomly sized and spaced vertical bars. For each sampled image.
Poisson (A 10) bars were distributed among the rows or columns, depending on the class. The distributions of the two classes are identical if 90 degree rotation is applied to one of the classes. Projection patches were between one and four pixels in both width and height and each split node of Sp PRR and MORe considered 28 random projections. Figure [B) shows examples from the two classes and classification results across various sample sizes.
Experiment (C) is signal classification problem. One class consists of 100 values of Gaussian noise while the second class has an added exponentially decaying unit step beginning time 20.
Ft (0) Ct
Ft (1) u(t (t-2 + C,
&~ (0,11)
Projection patches were ID with width between one and five timesteps. Each split node of SPoRE and MORe considered the default number of random projections, the square root of the number of features. Vigure[C. shows examples from the two classes and classification results across various sample sizes.
4.2 CLASSIFICATION ACCURACY
(A) Circle Segments (B) Orthogonal Bars (C) Noisy Impulse
Signal
Class 0
Impulse
Class 1
Algorithm
Log. Reg
Misclassification Rate
Lin. SVM
SVM
0.4
kNN
RF
MLP
0.2
SPORF
CNN
MORF
0.0
101
103 101
103 10
103
Number of training samples
Figure 1: MORF outperforms other algorithms in three two-class classification settings. Upper row shows examples of simulated data from each setting and class. Lower row shows misclassification rate each setting, tested on 10,000 test samples. (A) Two segments in a discretized circle. Segment lengths vary by class. (B) Image setting with uniformly distributed horizontal or vertical bars. (C) White noise (class 0) vs. exponentially decaying unit impulse plus white noise (class 1).
In all three simulation settings, MORe outperforms all other classifiers, doing especially better low sample sizes, except the CNN for which there is no clear winner. The performance of MORE is particularly good in the discretized circle simulation for which most other classifiers perform at chance levels. Mo also performs well in the signal
5

---

classification problem although all the classifiers close in performance. This may be because the exponential signal is prevalent throughout most of the time-steps and so perfect continuity less relevant.
Algorithm Runtimes Orthogonal Bars
Circle Segments
Noisy Impulse
102
Algorithm
Train Time (s)
Log. Reg
100
Lin. SVM
SVM
10-2
kNN
RF
MLP
102
Test Time (s)
SPORF
CNN
100
MORF
10-2
10
103 10
103
10
103
Number of training samples
Figure 2: Algorithm train times (above) and test times (below). MORF runtime not particularly costly and well below CNN runtime in most examples.
4.3 RUN TIME
All experiments were run a single core CPU. MORF has train and test times par with those of SPORt and and so not particularly more computationally intensive to run. The CNN, however, took noticeably longer run-especially in terms of training, but also in testing-in two of the three simulations. Thus its strong performance in those settings comes at an added computational cost, a typical issue for deep learning methods (Livni et al.) 2014).
5 REAL DATA RESULTS
5.1 CLASSIFICATION ACCURACY
MORF'S performance evaluated the MNIST dataset, collection of handwritten digits stored in 28 by 28 square images (Lecun et al.). and compared to the algorithms used in the simulations. 10,000 images were held out for testing and subset of the remaining images algorithms were composed of 500 decision trees and MORF was restricted to use patches up to only pixels in height and width. MORF showed an improvement over the other algorithms, especially for smaller sample sizes. Thus, even this trivial modification can improve performance by several percentage points. Specifically, MORE achieved a better (lower) classification error than all other algorithms besides CNNs for all sample sizes on this real data problem.
used for training. The results are displayed in Figure 3 All three forest

---

MNIST Classification Results
0.4
Algorithm
Log. Reg
Lin. SVM
0.3
Test error
SVM
kNN
0.2
RF
MLP
SPORF
0.1
CNN
MORF
0.0
10a
103
Figure 3: MORE improves classification accuracy over all other non-CNN algorithms for all sample sizes, especially in small sample sizes.
5.2 FEATURE IMPORTANCE
To evaluate the capability of MORF identify importance features in manifold- data compared to Se oRe and RF. All methods were run on a subset the MNIST dataset: we only used threes and fives, 100 images from each class.
The feature importance of each pixel is shown in Figure MORF visibly results in smoother pixel importance, result most likely from the continuity of neighboring pixels in selected projections. Although Tomita et al. (2015) demonstrated empirical improvement of SPORF over RF the MNIST data, projection distribution yields scattered importance of unimportant background pixels as compared to RF. Since projections in SPORF have no continuity constraint, those that select high importance pixels will also select pixels of low importance by chance. This may be nonissue asymptotically, but is a relevant problem in low sample size settings. MORF, however, shows little or no importance of these background pixels by virtue of the modificd projection distribution.
7

---

Average 3
Average 5
Absolute Difference
3
5
RF Importance
SPORF Importance
MORF Importance
0.015
0.912
0.12
0.009
0.68
0.006
Figure 4: Averages of images in the two classes and their difference (above). Feature importance from MORF (bottom right) shows less noise than SP CRF (bottom middle) and smoother than RF (bottom left).
6 DISCUSSION
The success of sparse oblique projections in decision forests has opened up many possible ways to improve axis-aligned decision forests (including random forests and gradient boosting trees) by way of specialized projection distributions. Traditional decision forests have already been applied to structured data, using predefined features to classify images or pixels. Decision forest algorithms like that implemented in the Microsoft Kinect showed great success but ignore pixel continuity and specialize for a specific data modality, namely images (Shotton et al. 2011).
We expanded upon sparse oblique projections and introduced structural projection distribution that prior knowledge of the topology of a feature space. The open source implementation SPORP has allowed for a relatively easy implementation of MORF, creating a flexible classification method for variety of data modalities. We showed in various simulated settings that appropriate domain knowledge can improve the projection distribution to yield impressive results that challenge the strength of deep learning techniques on manifold-valued data. On the MNIST data set Mo r showed modest improvements over the other algorithms besides CNNs and smoother importance plots than the other decision forest algorithms. This is in spite of the the data set's low resolution images which are harder for the modified projection distributions to take advantage of.
Research into other, task-specific convolution kernels may lead to improved results in real-world computer vision tasks. Such structured projection distributions, while incorporated into SP SPORE here, may also be incorporated into other state of the art algorithms such as XGBooST (Chen & Guestrin, 2016).
REFERENCES
Gérard Biau, Luc Devroye, and Gábor Lugosi. Consistency of random forests and other averaging classifiers. J. Mach. Learn. Res., 9:2015-2033, June 2008. ISSN 1532-4435.
8

---

A. Bosch, A. Zisserman, and X. Munoz. Image classification using random forests and ferns. In 2007 IEEE I 11th International Conference on Computer Vision, pp. 1-8, Oct 2007. doi: 10. 10.1109//CC22200.44440000
Leo Breiman. Random forests. Machine Learning, 45(1):5-32, Oct 2001. ISSN 1573-0565. 1010933404324.
doi: 10.1023/A:
Rich Caruana and Alexandru Niculescu-Mizil. An empirical comparison of supervised learning algorithms. In Proceedings of the 23rd International Conference on Machine Learning, ICMI. '06, pp. 161-168, New York, NY, USA, 2006. ACM. ISBN 1-59593-383-2. doi:
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD "16, pp. 785-794, New York, NY, USA, 2016. ACM. ISBN 978-1 4222-----3--.... doi: 10. 01145//299667222999555
Antonio Criminisi, Jamie Shotton, and Ender Konukoglu. Decision forests: A unified framework for classification, regression, density estimation, manifold learning and semi-supervised learning. Found. Trends. Comput. Graph. Vis., 7(28##211:3))812222 February 2012. ISSN 1572-2740. doi: 10. 10666/00000000355
Manuel Brrradezz-Delgadee Eva Cernadas, Senén Barro, and Dinani Amorim. Do need hundreds of classifiers to solve real world classification problems? Journal of Machine Learning Research, 15:3133-318) 2014.
J. Gall, A. Yao, N. Razavi, L. Van Gool, and V. Lempitsky. Hough forests for object detection, tracking, and action recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(11):2188-22 2202, Nov 2011. ISSN 0162-8828. doi: 10.1109/PAM..2011.77 1.70.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001.
P. Kontschieder, S. R. Bulò, H. Bischof, and M. Pelillo. Structured class-labels in random forests for semantic image labelling. In 2011 International Conference on Computer Vision, pp. 1190-2197, Nov 2011. doi: 10.1109/ICCV, 2011.6126499
Yann Lecun, Corinna Cortes, and Christopher J.C. Burges. The MNIST Database of Handwritten Digits.
V. Lepetit, P. Lagger, and P. Fua. Randomized trees for real-time keypoint recognition. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 05), volume 2, pp. 775-781 vol. 2, June 2005. doi: 10.1109/CVPR.2005.222
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. Proceedings of the 27th International Conference Neural Information Processing Systems- Volume 1, NIPS' 14, pp. 855-863, Cambridge, MA, USA, 2014. MIT Press.
Scott Lundberg and Su-In Lee. A unified approach to interpreting model predictions. ArXiv, abs/1705.00774, 2017
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito. Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS-W, 2017.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2882 2011.
Robert E. Schapire. The strength of weak learnability, Mach. Learn., 5(2):197-227, July 1990. ISSN 0885-6125, doi:
Shotton, A. Fitzgibbon, M. Cook, T. Sharp, M. Finocchio, R. Moore, A. Kipman, and A. Blake. Real-time human pose recognition in parts from single depth images. In CVPR 20/1, pp. 1297-1304, June 2011. doi: 10.119/CVPR2011.995366
Tyler M. Tomita, James Browne, Cencheng Shen, Jesse L. Patsolic, Jason Yim, Carey E. Priebe, Randal Burns, Mauro Maggioni, and Joshua T. Vogelstein. Random Projection Forests. arXiv e-prints, art, arXiv:1506.0344 034100 Jun 2015.

---

Tyler M. Tomita, Mauro Maggioni, and Joshua T. Vogelstein. RofImao: Robust oblique forests with linear matrix
operations. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 498-506, 2017. doi:
Laurent Younes. Diffeomorphic learning. ArXiv, abs/ 800.001460, 2018.
10

---

7 APPENDIX
Algorithm Learning Manifold Forest decision tree.
Input: Dr: training data (2) d: dimensionality of the projected space, (3) fA: distribution of the atoms, (4) O: set of split eligibility criteria
Output: A R decision tree T
I: function 7' = G y, fA. θ))
C
cs the current node index M is the number of nodes currently existing b S(e) is the indices of the observations at node c visit each of the existing nodes > data at the current node
3:
M =
4: S(c) = (o,.trrap((1,....111
while c < M do
6:
(X', = (x,, 31 3i) for = L..... K do n (0)
Eiesto Ily = kj end for
class counts (for classification) do we split this node? sample random p x d matrix of atoms D random projection into new feature space
8:
if T satisfied then
A |a ............. ad SA
10:
X = A'X' = (Xi)
11:
(j*,t") t²) findbestsplit y')
Algorithm 2 assign to left child node assign right child node store best projection for current node store best split threshold for current node node indices of children of current node b update the number of nodes that exist
12:
S(M+1) : aj. X, S
Vi 5 Vi s(e)]
13:
S(M+2) {i: aj- 8; l"
14:
(c) =a,'
15:
((c)
16:
((0) {M + 1, 2
17:
M = M + 2
18:
else
19:
(a (a) (1)) 16 (0)) NULL
20:
end if
21:
c+1
move to next node
22:
end while
23:
return (8(1, (a) (-()), x(0,
,,()),n(() {ng (c)
24:
end function
11

---

Algorithm 2 Finding the best node split. This function is called by growtree (Alg 1) at every split node. For each of the dimensions in X E R a binary split is assessed at each location between adjacent observations. The dimension j" and split value 7* in j that best split the data are selected. The notion of "best" means maximizing some choice in scoring function. In classification, the scoring function is typically the reduction Gini impurity or entropy. The increment function called within this function updates the counts in the left and right partitions as the split is incrementally moved to the right.
Input: (1) (X, y) Rexx x ) where y (1...., K}
Output: (1) dimension jr, (2) split value T" 1: function (j",T") (INDBESTSPLITXX.))
for ................................ do
Let x (a] ,...,,
xn (
be the jth row X.
4:
(m,) Me(M = (o)
D. m2 is the index of the 8thh smallest value in ( D initialize split the left of all observations D- number of observations left of the current split number of observations right of the current split
t=0
6:
n' 0 n"
8:
if (task is classification) then
for 1, I...., do
10:
n2 Ei=1 [B/: = k]
total number of observations in class k number of observations class left of the current split b number of observations in class & right of the current split
11:
n
12:
n Th
13:
end for
14:
end if
15:
for
> assess split location, moving right one at a time ((n).. n n2", vmm) increment(((1' (n)) ni', ne", vmm)
= .,...,77. 72 do
16:
17:
QUi1) score( (oore(((n/))))) ) n'',"") end for end for
measure of split quality
18:
19:
20:
(j tt* = argmax Q(i.1)
3.
for = 0, do c = m end for
21:
{ (1")
Ie (f"))
22:
P compute the actual split location from the index j*
23:
return (j* ,T)
24: end function
12


Reviews:
[{"review_id": "SyeMINIucB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\n====== Post Rebuttal ======\n\nNo rebuttal was provided and all reviewers have raised issues. Therefore, I will maintain the original rating.\n\n====== Summary====== \n\nThe paper puts forward a potential issue with the standard decision tree and tries to remedy it. The issue is that standard decision trees, by independently picking the split feature(s), virtually discard the structure of the input features (if any). In this work, structure essentially refers to ordered input features such as sequences, signals, and images. The work is motivated by the fact that convolutional networks (ConvNet) exploit this structure thanks to its local convolution operation. The idea of this work is to bridge this gap by constraining the split feature selection to follow the local structures of the input where each split feature would correspond to a local bounding box of the input feature. Applying this idea to random forests, it demonstrates significant improvements over unstructured split features, on a few synthesized datasets as well as MNIST dataset. The performance is also compared to one ConvNet architecture which demonstrates similar performance on synthesized datasets while being considerably slower than the proposed random forests.\n\n\n====== Strengths and Weaknesses ====== \n\n+ The motivation to make random forests respect the input structure similar to ConvNets is well-grounded and important since random forests are still being used in certain applications where computational complexity and/or interpretability are crucial factors.\n+ It proposes a simple technique to add locality to the split criterion which brings significant improvements over the standard random forest.\n\n- I believe the paper’s title should be closing the gap to *convolutional* neural networks since fully-connected networks are not local in the first place. \n- continuing on the previous point, the proposed method pushes the decision forests closer to “locally-connected” networks where, although the features are local, they are not shared across different locations in the input. The additional “sharing” property which takes locally-connected networks to convolutional networks is an important property of ConvNets since it brings translation equivariance for the representations. The proposed random forest method is not translation-equivariant by design and is only local. \n- regarding the previous point, a larger difference between ConvNet and the proposed method is more imminent if one goes to datasets with “non-aligned” observations. This already becomes more evident in the MNIST (which contains mostly aligned digits) where ConvNet clearly outperform MORF but would likely become more significant when going to real-world datasets, e.g. CIFAR.\n\n- the proposed method is very similar to patch-based random forest image recognition methods. For instance, several variants exist that are used for object or part detection in a given image where a patch is selected from the image for the split criterion. This patch will respect locality in a similar way to the proposed MORF’s bounding boxes. For instance, see “tomography scans” example of Criminisi et al. 2012 (section 4.5).\n\n- The paper is missing to provide many important details\n- what are the actual hyperparameter (hp) values used for the different methods in figure 1,2, and 3. This includes the hp relevant for the random forests including the number of decision trees, the stopping criterion, the random data partitioning method, number of random projections, as well as h_min, h_max, w_min, and w_max. It also does not discuss the hyper parameters of the baseline methods including k for KNN, distance measure for KNN, penalty cost for SVM, variance for the RBF kernel, ConvNet architecture, etc.\n- more importantly, it is not mentioned how these hp are optimized for the different baselines as well as the proposed method. What algorithm has been used (e.g. grid search)? How much hp optimization budget is used for different baselines? Is there a validation set put aside for hp optimization?\n- from the description in the start of page 4, it seems that the atoms for the proposed MORF are vectors of binary dimensions while for the general SPORF each atom’s element can be -1 as well (page 3). Why is this choice made despite the fact that it reduces the capacity of the model?\n\n- the bounding box sampling seems biased as presented. That is, bounding boxes closer (than h_max and/or w_max) to the right and/or lower borders are more likely since the number of valid boxes will be lower. \n\n\n====== Final Decision ====== \n\nI think it will be very interesting to bridge the gap between ConvNets and random forests since the latter comes with attractive properties. While I find all the concerns that are listed above important, my rating is mainly due to the novelty of this work compared to the prior patch-based random forest techniques for image analysis.\n\n\n====== Points of improvements ====== \n\nI believe it’s important to disentangle the two main properties of convolution operation in ConvNets being shared and local parameters. Then, accordingly propose strategies to bring these properties to a decision tree.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkxVEsCjKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new method called manifold forest to improve decision forest (DF) classification results. It is motivated by that, natural data is often in some manifold but not randomly distributed. It showed how to use the 2D spatial structures of natural images by constructing structured atoms. Results on 3 toy examples and MNIST showed the better performance than standard RF and SPORF.\n\nOverall, the paper is easy to follow and well written. The idea is intuitive: using structured 2D information to improve the classification results. But there are some issues with the implemetation.\n\n1. In image classification, we definitely need 2D structure information. This is normally extracted by the descriptors such as SIFT, GIST, where the 2D information has been included. It is rare to use the pixel values as the features directly for classification.   In this case, the benefit of the proposed method is very weak. This is the main issue of the paper. No results on real features.\n\n2. The results are weak too. The real data is MNIST, which is also a very toy dataset. It would be good to include some real world image dataset, such as CIFAR, ImageNet etc.\n\n3. The algorithm is somehow incremental compared with SPORF. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HyeFQ5Kb9B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The goal of the paper is clear. However, the proposed method has only a very incremental novelty compared to SPORF and the previous approaches in computer vision (e.g., Shotton et al., 2011). Although the authors claim the method can take advantage of structure in all kinds of data, the only conducted experiment is on the image data which is fairly limited.\n\nIn Fig. 1, they claim MORF outperforms other methods given fewer training data. However, for classifying Orthogonal Bars, CNN still outperforms MORF when few training data are given. The results on MNIST is also not impressive. CNN is still much better compared to other tree-based methods. Moreover, no other real-world dataset has been conducted experiments on.\n\nIn general, the paper's goal is clear and interesting. But the authors failed to propose a novel method and the results are not convincing. Hence, I recommend rejection.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work explores how to leverage structure of this input in decision trees, the way this is done for example in convolutional networks.
All reviewers agree that the experimental validation of the method as presented is extremely weak. Authors have not provided a response to answer the many concerns raised by reviewers.
Therefore, we recommend rejection.
Decision: Reject