Bernoulli Random Forests: Closing the Gap between Theoretical Consistency and Empirical Soundness

1 Introduction

Random forests (RF) represent a class of ensemble learning methods that construct a large number of randomized decision trees and combine results from all trees for classification or regression. The training of the random forests, at least for the original Breiman version [Breiman, 2001], is extremely easy and efficient. Because predictions are derived from a large number of trees, random forests are very robust, and have demonstrated superb empirical performance for many real-world learning tasks (e.g., [Svetnik et al., 2003;

Prasad et al., 2006; Cutler et al., 2007; Shotton et al., 2011; Xiong et al., 2012]).

Different from their well recognized empirical reputation across numerous domain applications, the theoretical properties of random forests have yet been fully established and are still under active research investigation. Particularly, one of the most fundamental theoretical properties of a learning algorithm is the consistency, which guarantees that the algorithm will converge to optimum (i.e. the Bayes risk) as the data grow infinitely large. Due to the inherent bootstrap randomization as well as attribute bagging process employed by random forests, and the highly data-dependent tree structure, it is very difficult to prove the theoretical consistency of random forests. As shown in Fig. 1(a), Breiman's original random forests have two random processes, bootstrap instance sampling and attribute bagging, which intend to make the tree less data-dependent. However, when constructing each internal node of the tree, the attribute selected for splitting and the splitting point used by the attribute are controlled by a deterministic criterion (such as Gini index [Breiman et al., 1984]). As a result, the constructed trees eventually become data-dependent, making theoretical analysis difficult.

Notice the difficulty of proving the consistency of random forests, several random forests variants [Breiman, 2004; Biau et al., 2008; Genuer, 2010; 2012; Biau, 2012; Denil et al., 2014] relax or simplify the deterministic tree construction process by employing two randomized approaches: (1) replacing the attribute bagging by randomly sampling one attribute; or (2) splitting the tree node with a more elementary split protocol in place of the complicated impurity criterion. For both approaches, the objective is to make the tree less data-dependent, such that the consistency analysis can be carried out. Unfortunately, although the properties of such approaches can be theoretically analyzed, they all suffer from poor empirical performance, and are mostly incomparable to Breiman's original random forests in terms of the classification accuracies. The dilemma of the theoretical consistency vs. empirical soundness persists and continuously motivates the research to close the gap.

Motivated by the above observations, in this paper, we propose a novel Bernoulli random forests model (BRF) with proved theoretical consistency and comparable performance to Breiman's original random forests. As shown in Fig. 1(b), our key is to introduce two Bernoulli distributions to drive/control the tree construction process, so we can ensure a certain degree of randomness in the trees, but still keep the quality of the tree for classification. Because each Bernoulli trial involves a probability value controlled random process, BRF can ensure that the tree construction is random with respect to a probability value or being deterministic, otherwise. As a result, the trees constructed by BRF are much less data-dependent, compared to Breiman's original random forests, yet still have much better performance compared to all existing theoretically consistent random forests.

The main contribution of the paper is threefold: (1) BRF has the least simplification changes, compared to Breiman's original random forests, and its theoretical consistency is fully proved; (2) The two independent Bernoulli distributions controlled attribute and splitting point selection process provides a solution to resolve the dilemma of theoretical consistency vs. empirical soundness; and (3) empirically, a series of experimental comparisons demonstrate that BRF achieves the best performance among all theoretical random forests.

2 Bernoulli RandomForests

Compared to Breiman's original random forests, the proposed BRF makes three alterations, as shown in Fig. 1, to close the gap between theoretical consistency and empirical soundness.

2.1 Data point partitioning

Given a data set Dn with n instances, for each instance (X↪ Y ), we have X 2 RD with D being the number of attributes and Y 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ C♦ with C being the number of classes. Before the construction of each individual tree, we randomly partition the entire data points into two parts, i.e., Structure points and Estimation points. The two parts perform different roles in the individual tree construction, which helps establish the consistency property of the proposed BRF.

Structure points are used to construct the tree. They are only used to determine the attributes and splitting points in each internal node of the tree, but are not allowed to be used for estimating class labels in tree leaves.

Estimation points are only used to fit leaf predictors (estimating class labels in tree leaves). Note that these points are also split obeying the rules created by structure points along the construction of the tree, but they have no effect on the structure of the tree.

For each tree, the points are partitioned randomly and independently. The ratio of the two parts is parameterized by Ratio = ♣Structure points♣◁♣Entire points♣.

2.2 Tree construction

In the proposed BRF, firstly, as stated above, the data point partitioning process replaces the bootstrap technique in training instances. Secondly, two independent Bernoulli distributions are introduced into the strategies of selecting attributes and splitting points.

The first novel alteration in BRF is to choose candidate attributes with a probability satisfying a Bernoulli distribution. Let B1 2 ¶0↪ 1♦ be a binary random variable with "success" probability of p1, then B1 has a Bernoulli distribution which takes 1 in a probability of p1. We define B1 = 1 if 1 candidate attribute is chosen and B1 = 0 if pD candidate attributes are chosen. To be specific, for each internal node, we choose 1 or pD candidate attributes in a probability of p1 or 1 - p1 respectively.

The second novel alteration is to choose splitting points using two different methods with a probability satisfying another Bernoulli distribution. Similar to B1, we assume B2 2 ¶0↪ 1♦ satisfies another Bernoulli distribution which takes 1 in a probability of p2. We define B2 = 1 if the random sampling method is used and B2 = 0 if the optimizing impurity criterion method is used. Specifically, we choose the splitting point through random sampling or optimizing impurity criterion in a probability of p2 or 1 - p2 respectively in each candidate attribute.

The impurity criterion is denoted by:

Here v is the splitting point which is chosen by maximizing I(v). D is the cell belonging to the node to be split, which contains structure points DS and estimation points DE . D0 and D00 are two children that would be created if D is split at v. The function T (DS ) is the impurity criterion, e.g. Shannon entropy or Gini index, which computes over the labels of the structure points DS . In BRF, the impurity criterion is Gini index and it is certain that Shannon entropy is also acceptable.

Through the above two steps, for each internal node of the tree, one attribute and its corresponding splitting point is selected to split the data and grow the tree. Note that only the structure points are involved in the tree construction. The process recursively repeats until the stopping condition is met.

Similar to Breiman's original random forests, BRF's stopping condition is also based on the minimum leaf size. But, we only restrict the estimation points rather than the entire data points. In other words, in each leaf, we require that the number of estimation points must be larger than kn which depends on the number of training instances, i.e., kn !1 and kn◁n ! 0 when n ! 1.

2.3 Prediction

Once the trees are trained by structure points and the leaf predictors are fitted by estimation points, BRF can be used to predict labels of new unlabeled instances.

When making predictions, each individual tree will predict independently. We denote a base decision tree classifier created by our algorithm as g. Assuming the unlabeled instance is x, the probability of each class c 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ C♦ is

and the prediction of the tree is the class that maximizes ⌘c (x):

where N(AE (x)) denotes the number of estimation points in the leaf containing the instance x. I(e) is the indicator function which takes 1 if e is true and takes 0 for other cases.

Second, the prediction of the forests is the class which receives the most votes from individual trees.

where M is the number of individual trees in the random forests.

3 Consistency

In this section, we first give an outline of the lemmas for establishing the consistency of random forests. Then we prove the consistency of the proposed BRF. We use a variable Z to denote the randomness involved in the construction of the tree, including the selection of attributes and splitting points.

3.1 Preliminaries

Definition 1. Given the data set Dn, a sequence of classifiers ¶g♦ are consistent for a certain distribution of (X↪ Y ) if the error probability L satisfies

where L⇤ is the Bayes risk that is the minimum achievable risk of any classifier for the distribution of (X↪ Y ).

The consistency of random forests is implied by the consistency of the trees they are comprised of, which will be shown in the following two lemmas.

Lemma 1. Suppose a sequence of classifiers ¶g♦ are consistent, then the voting classifier g(M) obtained by taking the majority vote over M copies of g with different randomizing variables is also consistent.

Lemma 2. Suppose each class posterior estimation is ⌘(c) (x) = P (Y = c ♣ X = x), and that these estimations are each consistent. The classifier

is consistent for the corresponding multi-class classification problem.

Lemma 1 shows that the consistency of random forests is determined by the individual trees [Biau et al., 2008]. Lemma 2 allows us to reduce the consistency of multi-class classifiers to the consistency of posterior estimates for each class [Denil et al., 2013].

Lemma 3. Suppose a sequence of classifiers ¶g♦ are conditionally consistent for a specified distribution on (X↪ Y ), i.e.

where I represents the randomness in the data point partitioning. If the random partitioning produces acceptable structure and estimation parts with probability 1, then ¶g♦ are unconditionally consistent, i.e.

Lemma 3 shows that data point partitioning procedure of the tree construction almost would not affect the consistency of the base decision tree [Denil et al., 2013].

To prove the consistency of the base decision tree, we employ a general consistency lemma used for decision rules as follows:

Lemma 4. Consider a classification rule which builds a prediction by averaging the labels in each leaf node, if the labels of the voting data do not influence the structure of the classification rule thenE [L] !L⇤ as n!1 (9)

provided that

1. diam(A(X)) ! 0 in probability,
2. N(AE (X)) !1 in probability,

where A(X) denotes the leaf containing X and N(AE (X)) denotes the number of estimation points in A(X).

Generally, the construction of decision trees can be viewed as a partitioning of the original instance space. Thus, each node of the tree corresponds to a rectangular subset/cell of RD and the tree root corresponds to all of RD . Therefore, diam(A(X)) ! 0 is equal to that the size of hypercube A(X) is close to 0.

Lemma 4 shows that the consistency of the tree construction can be proved on condition that the hypercubes/cells belonging to leaves are sufficiently small but contain infinite number of estimation points [Devroye et al., 2013].

3.2 Consistency theorem

With these preliminary results in hand, we are equipped to prove the main consistency theorem.

Theorem 1. Suppose that X is supported on [0↪ 1]D and has non-zero density almost everywhere. Moreover, the cumulative distribution function (CDF) of the splitting points is right-continuous at 0 and left-continuous at 1. Then BRF is consistent provided that kn ! 1 and kn◁n ! 0 as n ! 1.

According to Subsection 3.1, we know that the consistency of random forests is determined by the consistency of the base decision tree (Lemma 1 and 2), which is further dependent on the consistency of the tree construction (Lemma 3 and 4). More specifically, the proof of Theorem 1 is to prove the two conditions of Lemma 4, i.e., diam(A(X)) ! 0 and N(AE (X)) ! 1 in probability.

Proof. Firstly, since BRF requires N(AE (X)) ≥ kn, N(AE (X)) ! 1 is trivial when n ! 1.

For any given d, the largest size of the child node for the d-th attribute is denoted by V ⇤ (d). Recalling that the splitting point is chosen either by randomly sampling in [0↪ 1] with a probability p2 or by optimizing the impurity criterion with a probability 1 - p2, we have

Secondly, we prove diam(A(X)) ! 0 in probability. Let V (d) be the size of the d-th attribute of A(X). It suffices to show that E [V (d)] ! 0 for all d 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ D♦.

where U is the splitting point for random sampling method and U ⇠ Uniform[0↪ 1].

Revisiting that 1 or pD candidate attributes are selected with a probability p1 or 1 - p1 respectively, we define the following events:

E1 = ¶One candidate attribute is split♦

E2 = ¶The splitting attribute is exactly the d-th one♦

Denoting the size of the child node for the d-th attribute by V 0 (d), then

Assuming K is the distance from the tree root to a leaf and iterating (11) after K splits, we have:

The consistency of BRF suffices to have K ! 1 in probability, which will be shown in Lemma 5.

Lemma 5. For sufficiently large n, every node of the tree will be split infinite times in probability, on the condition that the CDF of the splitting points is right-continuous at 0 and leftcontinuous at 1.

Proof. Revisit that the splitting point is obtained either by random sampling method with a probability p2 or by optimizing the impurity criterion with a probability 1-p2. Thus, the final selected splitting point through the two methods can be viewed as a random variable Wi(i 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ K♦) with CDF FWi from the tree root to a leaf.

For any given K and a constant δ > 0, the smallest child node of the root has the size M1 = min(W1↪ 1-W1) at least δ1◁K with the probability:

Without loss of generality, we scale the values of attributes to the range [0↪ 1] for each node, then after K splits, the smallest child at the K-th level have the size at least δ with the probability at least

which is derived by assuming that the same attribute is split at each level of the tree. If different attributes are split at different levels, the bound (14) also holds. Since FWi is rightcontinuous at 0 and left-continuous at 1, FWi (1 - δ1◁K ) - FWi (δ1◁K ) ! 1 as δ ! 0. Thus, 8✏1 > 0, 9δ1 > 0, such that

Besides, 8✏ > 0, 9✏1 > 0, such that

The above (15) and (16) show that each node at K-th level of the tree has the size of δ with probability at least 1 - ✏.

Because the distribution of X has a non-zero density, each of these nodes has a positive measure with respect to θX. Defining

we know p > 0 since the minimum is over finitely many leaves and each leaf contains a set of positive measure.

In a data set of size n, the number of data points falling in the leaf A is Binomial(n↪ p). Then, the number of estimation points in A is np◁2 assuming the Ratio is 0.5 without loss of generality. According to Chebyshev's inequality, we can bound N(AE ) as follows:

where the equation (a) is due to the fact that kn - np 2 is negative as n !1. The RHS of (18) goes to zero as n !1, so the leaf contains at least kn estimation points in a high probability. According to the stopping condition, if the number of estimation points in the node is larger than kn, the tree will continue to grow. So, K ! 1 in probability.

4 Discussion

In this section we discuss the proposed BRF with three variants of random forests which have the proved consistency, i.e., [Biau et al., 2008], [Biau, 2012] and [Denil et al., 2014] denoted by Biau08, Biau12 and Denil14 respectively. Besides, we also discuss these models with Breiman's original random forests [Breiman, 2001] denoted by Breiman.

In terms of the data point partitioning, as long as the trees in the forests are constructed using the labels of data points, it is a must to partition the data points to ensure consistency, because Lemma 4 requires the labels of the voting data do not influence the structure of the tree. Thus, BRF, Biau12 and Denil14 all require data partitioning, whereas Biau08 and Breiman do not need it.

For candidate attribute selection, according to Lemma 4, to ensure consistency, every attribute of the data must be split in probability as n !1. For Biau08, it chooses a single attribute uniformly at random. Biau12 chooses a fixed number of random candidate attributes with replacement. Denil14 chooses min(1 + P oisson(λ)↪ D) candidate attributes without replacement. BRF chooses 1 or pD attributes with a probability satisfying a Bernoulli distribution B1 without replacement. At last, Breiman chooses a fixed number of random candidate attributes without replacement.

Thirdly, as for the selection of splitting points, according to Lemma 4, each candidate splitting point should be selected to split in probability so as to guarantee the consistency. Biau08 selects a point uniformly at random to split. Biau12 selects the midpoint in each attribute as the splitting point. Denil14 selects a few structure points at random and searches for the optimal splitting point over the range defined by previously selected points. BRF implements two strategies for splitting point selection in another Bernoulli distribution B2. The two strategies either select a point uniformly at random to split or search for the splitting point that gives the largest impurity decrease. Lastly, Breiman checks all the candidate splitting points and chooses the one with the largest impurity decrease.

According to the above discussion, we can find that the proposed BRF closely resembles to Breiman's original random forests. The key difference is that two independent Bernoulli distributions are introduced into the selection of splitting attributes and points to ensure consistency. Another noticeable difference is the data point partitioning procedure. In fact, all strategies implemented in BRF are to ensure the theoretical consistency as well as maintain the empirical performance.

5 Experiments

5.1 Data sets

Table 1 reports the 9 benchmark data sets [Lichman, 2013] ranked by the number of attributes. The benchmark data sets have different number of instances (from small to large), and also include low, moderate, and high dimensional attributes for binary and multi-class classification. Therefore, they are sufficiently representative to demonstrate the ability of random forests to handle different types of data.

5.2 Experimental settings

Since the algorithms are each parameterized slightly differently, it is not possible to use the same parameters for all methods. Breiman, Denil14 and BRF specify a minimum leaf size, which is set to 5 as suggested in [Breiman, 2001]. Biau08 and Biau12 are parameterized in terms of a target number of leaves which we set to be n◁5, meaning the trees are approximately the same size as those parameterized by the minimum leaf size. For the forest size M, we set M = 100. As for the ratio of structure points to entire points (Ratio), we all set Ratio = 0▷5 for Biau12, Denil14 and BRF.

Moreover, Denil14 needs to choose m structure points for determining the search range of the splitting point which we set m = 100 according to [Denil et al., 2014]. For BRF, we set the probability p1 = p2 = 0▷05 in the two Bernoulli distributions respectively. Besides, for each data set, a 10 times 10-fold cross-validation is performed to reduce the influence of randomness.

5.3 Comparisons of different random forests

Table 2 reports the accuracies of different algorithms. The highest accuracy of the consistent random forests algorithms on each data set is in boldfaced. Besides, ∆theory shows the improvement of the proposed BRF compared to the state-ofthe-art consistent random forests; ∆practice exhibits the gap between BRF and Breiman's original random forests.

As expected, among all consistent random forests algorithms, BRF achieves the highest accuracy. Compared to the state-of-the-art consistent random forests, i.e., Denil14, the accuracy improvement is remarkable, especially on INDOORLOC data set where the improvement is up to 65▷58%. The reason behind the huge improvement is that the INDOORLOC data set has some attributes with numerous values. Thus, in Denil14, the preselected m structure points may only possess a few values of the attribute, which have a great effect on selecting the splitting point and further influence the tree structure as well as performance. The classification accuracy improvement over Denil14 is also supported by Wilcoxon signed ranked test [Demˇsar, 2006] which assures the statistical significance on almost all data sets, as shown in Table 2. Combining the comparisons with other consistent algorithms, we conclude that the improvement of BRF is mainly attributed to the two Bernoulli distributions in the strategies of selecting splitting attributes and points.

When comparing BRF to Breiman, the gap still remains

• 1 Biau08, Biau12, and Denil14 are consistent random forests algorithms.
• 2 Breiman is the original random forests algorithm. (It has not been proved to be consistent.)
• ÷ BRF is significantly better than Denil14 at a level of significance 0▷05.

but has been significantly narrowed down to within 3% in almost all data sets. Actually, the gap is caused by the data point partitioning procedure in BRF which reduces the instance size for constructing the trees. Particularly, on MADELON data set, the gap is still 7▷35% although BRF has already tremendously outperformed Denil14. The main reason is that after the partitioning, the number of instances are severely insufficient for 500 attributes.

Overall, BRF is proved to be consistent. In addition, BRF not only empirically outperforms all other consistent random forests, but also achieves the closest empirical performance to Breiman than previous theoretical variants including the state-of-the-art consistent random forests Denil14.

5.4 Cross-test for parameter settings

In this subsection, we conduct a series of cross-test experiments to evaluate the influence of parameters in BRF, i.e., the ratio of structure points to entire points (Ratio), the number of trees M and the probabilities p1 as well as p2 in the Bernoulli distributions.

Due to page limitations, we select three representative data sets with small, middle and large instances or attributes, i.e., CHESS, MADELON and ADS. We test Ratio among ¶0▷15↪ 0▷3↪ 0▷45↪ 0▷6↪ 0▷75↪ 0▷9♦, M among ¶1↪ 10↪ 100↪ 500↪ 1000↪ 5000♦, p1 and p2 among ¶0▷05↪ 0▷15↪ 0▷25↪ 0▷35↪ 0▷45↪ 0▷5♦.

The results in Fig. 2 show that the accuracy increases gradually and approaches to a stable value as the number of trees M increases. Besides, Fig. 2 indicates that the best Ratio varies across data sets (e.g., 0.45 for CHESS, 0.75 for MADELON, 0.3 for ADS). In addition, Fig. 3 demonstrates that BRF is not sensitive to p1 and p2 as long as they have small values (i.e., p1↪ p2  0▷25). Recalling the tree construction procedure of BRF, we know that p1 and p2 are two parameters to balance the consistency analysis and empirical performance. When p1↪ p2 ! 0, BRF is close to Breiman. When p1↪ p2 ! 1, BRF is close to Biau08. Therefore, p1 and p2 can use small values empirically. Meanwhile, on one hand, a large Ratio value implies less estimation points, which results in imprecise leaf predictors. On the other hand, a small Ratio value will lead to less structure points, so the structure of the tree will not be optimal. Generally, Ratio value is set as 0▷5 to balance the structure and estimation parts, without favour of any part. Besides, the ensemble size (i.e., the number of trees M) is set considering the computation time and accuracy, because the accuracy tends to be stable once the ensemble size is larger than a threshold.

6 Conclusion

In this paper, we proposed a new Bernoulli random forests model (BRF) with sound empirical performance and proved theoretical consistency. We argued that although Breiman's original random forests have very good empirical performance, their theoretical consistency has yet to be proved due to the highly sensitive data-driven tree construction procedure. On the other hand, several random forests variants have nice theoretical consistency but they all suffer from poor empirical performance. In the proposed BRF, we employ two Bernoulli distributions to help determine the attributes as well as the splitting points used by each node. For each Bernoulli trial, it determines whether to use a random process or a deterministic process to build the tree with a probability value. As a result, the trees constructed by BRF are much less datadependent, compared to Breiman's original random forests, yet still have much better performance compared to theoretically consistent random forests. Experiments and comparisons validate that BRF significantly outperforms all existing consistent random forests, and its performance is very close to Breiman's original random forests. BRF takes a step forward to close the gap between theoretical consistency and empirical soundness of random forests classification.

Acknowledgments

This research is supported in part by the Major State Basic Research Development Program of China (973 Program, 2012CB315803), the National Natural Science Foundation of China (61371078), and the Research Fund for the Doctoral Program of Higher Education of China (20130002110051).