1 Programming Problem: Random Forests
1.1
Table 1: The training and test RMSE of random forest, least square regression, and ridge regression on Boston housing price dataset.RF outperforms both least square and ridge regression on training and test RMSE.
1.2
Table 2: The training and test accuracy of random forest on bad credit risk and breast cancer prediction.
2 Programming Problem: Gradient Boosting Decision Trees
2.1
For a tree of depth d, it has at most 2d − 1 nodes. For each node, there are m choices of feature dimension and nj choices of threshold.
A naive way to find the best feature and the threshold (pj,τj) is: we first sort all the data points by a candidate feature p′j. and try all thresholds . For each τj′, we have
and and . We compute the gain based on
GL,GR,HL,HR and compare it with the best gain so far.
Therefore, for every candidate (pj,τj) on node j, we need to compute the corresponding gain, which takes O(nj) time. There are O(mnj) combinations of (pj,τj), so for one node the time complexity is O(mn2j).
For all the possible depths d′ ∈ [0,d), we have Pj,depth(j)=d′ nj = n. We know depth(j)=d′ n2j < n2.
Therefore, depth(j)=d′ m · n2j = O(n2md). Therefore, the computational complexity is O(n2md).
2.2
As stated in 2.1, the most computationally expensive part in GBDT training (and also in other decision tree algorithms) is the pick of (pj,τj), which takes O(n2jm) time for a single node. While different pj’s can be tested in parallel, we suggest a method can improve the efficiency of choosing τj given pj without parallelism.
Suppose data split D on node j has size nj; the candidate feature is pj. Then we have k possible thresholds where k ≤ n − 1. Suppose the thresholds satisfy . We observe that
(t+1) X
GL = gi
{i|x(pij)≤τj(t+1)}
= X gi + X gi
{i|x(pij)≤τj(t)} {i|τj(t)<x(pij)≤τj(t+1)}
(t) X = GL + gi
{i|τj(t)<x(pij)≤τj(t+1)}
Similarly, . The same observation holds for HL and HR as well.
In practice, we sort the data split D by dimension pj, and reorder g and h to match the sorted data points
(takes O(nj lognj) time). As a result, each time we only need to compute the difference between and to obtain , and examining k thresholds only takes O(nj) time.
Therefore, the new time complexity is depth(j)=d′ mnj lognj). For a given layer d′, we have n(log(n) − d′) < Pj,depth(j)=d′ nj log(nj) < nlog(n), therefore, the new time complexity is O(nmdlogn).
2.3
There are parts in GBDT we can compute in parallel: (1) the evaluation of different nodes on the same level; (2) the different candidate features dimensions given a node; (3) the different thresholds given a feature dimension.
In our practice, we parallelize the evaluation of different candidate features dimensions given a node. In Python, we take the evaluation of each feature dimension(decision rule) as an individual function, and use multiprocess.Pool.starmap() to execute the functions in parallel.
2.4
Table 3: The training and test RMSE of GBDT, least square regression, and ridge regression on Boston housing price dataset. GBDT outperforms both least square and ridge regression on training and test RMSE.
2.5
Table 4: The training and test accuracy of GBDT on bad credit risk and breast cancer prediction.
2.6
By comparing Table 1 and Table 3, Table 2 and Table 4, we observe that GBDT outperforms RF on all the datasets.
A possible explanation is that while GBDT corrects the errors made by previous trees along the direction of the gradient, RF corrects the error randomly by randomly sampling data points from the training set. As a result, directed correction brings better accuracy to the model compared to random correction.
Another important factor is that we conducted parameter-tuning for GBDT, including tuning of the number of trees to prevent over-correction, and tuning of the learning rate to obtain an optimal optimization result.
