Decision Forests#

Decision forests (also referred to as random forests) are ensembles of decision trees. Decision trees split the feature domain into rectangular regions and make predictions based on the label values in each region.

A node in the decision tree is terminal if it does not have any child nodes. Let \(m\) be the index of a terminal node in the tree. If we are solving a classification problem with two classes, the proportion of observations in the second class for node m is defined as,

\[\hat{p}^0_m = \frac{1}{N_m} \sum_{x_i \in R_m} I(y_i = 1)\]

where \(R_m\) is the rectangular region corresponding to node \(m\), \(x_i\) is a (multi-dimensional) observation, \(y_i\) is a label, and \(N_m\) is the number of observations in \(R_m\).

The node impurity is defined as,

\[C^{0}_m = Q(\hat{p}^0_m)\]

where \(Q(\hat{p}^0_m)\) is a function that quantifies the error in the classification fit, with the property that if all observations in \(R_m\) are in the same class, then \(Q(\hat{p}^0_m)=0\) and we say that the node is pure.

AOCL-DA supports the following choices of \(Q(p)\),

\[\begin{split}\mathrm{Misclassification\ error: } & \ 1 - \max(p, 1-p) \\ \mathrm{Gini\ index: } & \ 1 - 2 p (1-p) \\ \operatorname{Cross-entropy or deviance: } & \ -p \log(p) - (1-p) \log(1-p)\end{split}\]

Fitting#

Decision tree fitting is performed by growing a tree recursively, starting with a single base node. Each node has an associated depth, which corresponds to the number of splits required to get to that node from the base node. If the depth of the node is less than the maximum depth and the node is not pure, we minimize the sum of the node impurities over each possible split,

\[C_m(j^*, s^*) = \min_{j, s} \bigg( Q(\hat{p}^1_m(j,s)) + Q(\hat{p}^2_m(j,s)) \bigg)\]

where

\[\begin{split}\hat{p}^1_m(j,s) &= \sum_{ \{i \ : x_i(j) \leq s \} } I(y_i = 1) \\ \hat{p}^2_m(j,s) &= \sum_{ \{i \ : x_i(j) > s \} } I(y_i = 1)\end{split}\]

and \(j\) is the feature index, so that \(x_i(j)\) is the \(j\)-th feature of the \(i\)-th observation.

Then node \(m\) stops being a terminal node, and two new terminal nodes are created as children of node \(m\). The domains for the new child nodes are defined by splitting \(R_m\) into two rectangles using the variable index \(j^*\) and the threshold \(s^*\).

This recursive splitting continues until all terminal nodes are either pure, or have reached the maximum depth. The maximum depth is a user-defined parameter and, for decision trees, needs to be selected in such a way that avoids overfitting.

Decision forest fitting is performed by creating an ensemble of decision trees. The training data for each decision tree in the ensemble is generated by bootstrapping observations from the training data. The fitting for each decision tree in the ensemble follows a modified version of the decision tree fitting algorithm. In contrast to standard decision tree fitting, the candidate set of features for each split is a randomly sampled subset. The subset selection is repeated at each split so a different subset of candidate features is used on each split. In both decision trees and decision forests, the order in which features are selected is randomized. This means that if two different splits have the same value of \(C_m(j, s)\), then whichever value of \(j\) is sampled first will be the split variable.

Prediction#

Decision tree prediction is performed by using the set of split feature indices and thresholds to determine which terminal node a new observation belongs to. Once the terminal node has been identified, the prediction is determined by the proportion of observations with label \(1\) in the training set: if an observation \(x\) is associated with a terminal node \(m\), and \(\hat{p}^0_m > 0.5\), the predicted label is \(1\), otherwise it is \(0\).

Decision forest prediction is performed by producing an ensemble of decision tree predictions and using a majority vote to determine the prediction of the decision forest.

Typical workflow for decision trees and decision forests#

The following workflow can be used to fit a decision tree or a decision forest model and use it to make predictions,

Decision trees

  1. Initialize a aoclda.decision_tree.decision_tree() object with options set in the class constructor.

  2. Fit the model using aoclda.decision_tree.decision_tree.fit().

  3. Evaluate prediction accuracy on test data using aoclda.decision_tree.decision_tree.score().

  4. Make predictions using the fitted model using aoclda.decision_tree.decision_tree.predict().

Decision forests

  1. Initialize a aoclda.decision_forest.decision_forest() object with options set in the class constructor.

  2. Fit the model using the aoclda.decision_forest.decision_forest.fit().

  3. Evaluate prediction accuracy on test data using aoclda.decision_forest.decision_forest.score().

  4. Make predictions using the fitted model using aoclda.decision_forest.decision_forest.predict().

Decision trees

  1. Initialize a da_handle with da_handle_type da_handle_decision_tree.

  2. Pass data to the handle using da_tree_set_training_data_?.

  3. Set optional parameters, such as maximum depth, using da_options_set_? (see options section).

  4. Fit the model using da_tree_fit_?.

  5. Evaluate prediction accuracy on test data using da_tree_score_?.

  6. Make predictions using the fitted model using da_tree_predict_?.

Decision forests

  1. Initialize a da_handle with da_handle_type da_handle_decision_forest.

  2. Pass data to the handle using da_forest_set_training_data_?.

  3. Set optional parameters, such as maximum depth, using da_options_set_? (see options section).

  4. Fit the model using da_forest_fit_?.

  5. Evaluate prediction accuracy on test data using da_forest_score_?.

  6. Make predictions using the fitted model using da_forest_predict_?.

Options#

The available Python options are detailed in the aoclda.decision_tree.decision_tree() and aoclda.decision_forest.decision_forest() class constructors.

The following options can be set using da_options_set_?:

Table of options for decision forests.#

Option name

Type

Default

Description

Constraints

block size

integer

\(i=256\)

Set the size of the blocks for parallel computations.

\(1 \le i \le 2147483647\)

node minimum samples

integer

\(i=2\)

Minimum number of samples to consider a node for splitting.

\(2 \le i\)

scoring function

string

\(s=\) gini

Select scoring function to use.

\(s=\) cross-entropy, entropy, gini, misclass, misclassification, or misclassification-error.

maximum depth

integer

\(i=29\)

Set the maximum depth of trees.

\(0 \le i \le 29\)

seed

integer

\(i=-1\)

Set random seed for the random number generator. If the value is -1, a random seed is automatically generated. In this case the resulting classification will create non-reproducible results.

\(-1 \le i\)

tree building order

string

\(s=\) depth first

Select in which order to explore the nodes.

\(s=\) breadth first, or depth first.

feature threshold

real

\(r=1e-06\)

Minimum difference in feature value required for splitting.

\(0 \le r\)

bootstrap

string

\(s=\) yes

Select whether to bootstrap the samples in the trees.

\(s=\) no, or yes.

bootstrap samples factor

real

\(r=0.8\)

Proportion of samples to draw from the data set to build each tree if ‘bootstrap’ was set to ‘yes’.

\(0 < r \le 1\)

features selection

string

\(s=\) sqrt

Select how many features to use for each split.

\(s=\) all, custom, log2, or sqrt.

number of trees

integer

\(i=100\)

Set the number of trees to compute.

\(1 \le i\)

minimum split score

real

\(r=0.03\)

Minimum score needed for a node to be considered for splitting.

\(0 \le r \le 1\)

maximum features

integer

\(i=0\)

Set the number of features to consider when splitting a node. 0 means take all the features.

\(0 \le i\)

minimum split improvement

real

\(r=0.03\)

Minimum score improvement needed to consider a split from the parent node.

\(0 \le r\)

Choosing the decision forest options#

By default, the number of features to use in each split is set to be the square root of the total number of features. This can be changed through the features selection option. If features selection is set to custom, then the value of maximum features will be used. Otherwise, the value of the maximum features option is ignored.

By default, bootstrap sampling is used, with the number of bootstrap samples set through the bootstrap samples factor option. However, if the value of the bootstrap option is set to no then no bootstrapping is done, i.e., each tree uses the full dataset.

The optimal values of the optional parameters is typically problem dependent. Cross-validation is typically used to tune options / hyperparameters.

The memory requirements for decision forests are proportional to \(\textit{number of trees} \times \textit{number of bootstrap samples}\). Reducing the number of bootstrap samples through the bootstrap samples factor option may improve performance. If the dataset is large, reducing bootstrap samples factor may be needed to ensure that that all the data required to fit the decision forest can be stored in DRAM.

Examples#

The code below is supplied with your installation (see Python examples).

 1# Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
 2#
 3# Redistribution and use in source and binary forms, with or without modification,
 4# are permitted provided that the following conditions are met:
 5# 1. Redistributions of source code must retain the above copyright notice,
 6#    this list of conditions and the following disclaimer.
 7# 2. Redistributions in binary form must reproduce the above copyright notice,
 8#    this list of conditions and the following disclaimer in the documentation
 9#    and/or other materials provided with the distribution.
10# 3. Neither the name of the copyright holder nor the names of its contributors
11#    may be used to endorse or promote products derived from this software without
12#    specific prior written permission.
13#
14# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17# IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
20# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
23# POSSIBILITY OF SUCH DAMAGE.
24#
25
26"""
27Decision tree example Python script
28"""
29
30import sys
31from aoclda.decision_tree import decision_tree
32import numpy as np
33
34def decision_tree_example():
35    """
36    Decision tree classification
37    """
38
39    X_train = np.array([[0.0, 0.0], [1.0, 1.0]])
40    y_train = np.array([0, 1])
41    X_test = np.array([[2., 2.]])
42    y_test = np.array([[1]])
43
44    tree = decision_tree()
45    tree.fit(X_train, y_train)
46
47    pred = tree.predict(X_test)
48    print(f"predictions: [{pred[0]:d}]")
49
50    score = tree.score(X_test, y_test)
51    print(f"score: {score:.3f}")
52
53if __name__ == "__main__":
54    try:
55        decision_tree_example()
56    except RuntimeError:
57        sys.exit(1)

The code below can be found in decision_tree.cpp in the examples folder of your installation.

  1/*
  2 * Copyright (C) 2023-2024 Advanced Micro Devices, Inc. All rights reserved.
  3 *
  4 * Redistribution and use in source and binary forms, with or without modification,
  5 * are permitted provided that the following conditions are met:
  6 * 1. Redistributions of source code must retain the above copyright notice,
  7 *    this list of conditions and the following disclaimer.
  8 * 2. Redistributions in binary form must reproduce the above copyright notice,
  9 *    this list of conditions and the following disclaimer in the documentation
 10 *    and/or other materials provided with the distribution.
 11 * 3. Neither the name of the copyright holder nor the names of its contributors
 12 *    may be used to endorse or promote products derived from this software without
 13 *    specific prior written permission.
 14 *
 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 18 * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 19 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 20 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
 21 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 24 * POSSIBILITY OF SUCH DAMAGE.
 25 *
 26 */
 27
 28#include "aoclda.h"
 29#include <algorithm>
 30#include <iostream>
 31#include <vector>
 32
 33#ifndef DATA_DIR
 34#define DATA_DIR "data/df_data"
 35#endif
 36
 37int main() {
 38    std::cout << "----------------------------------------" << std::endl;
 39    std::cout << "Decision tree model (single precision)" << std::endl;
 40    std::cout << "----------------------------------------" << std::endl;
 41    std::cout << std::fixed;
 42    std::cout.precision(3);
 43
 44    da_status status;
 45    bool pass = true;
 46
 47    // Read in training data
 48    da_datastore csv_store = nullptr;
 49    std::string filename = DATA_DIR;
 50    filename += "/decision_train.csv";
 51    da_int n_cols = 0, n_rows = 0;
 52    pass = da_datastore_init(&csv_store) == da_status_success;
 53    pass &= da_datastore_options_set_string(csv_store, "CSV datastore precision",
 54                                            "single") == da_status_success;
 55    pass &= da_data_load_from_csv(csv_store, filename.c_str()) == da_status_success;
 56    pass &= da_data_get_n_cols(csv_store, &n_cols) == da_status_success;
 57    pass &= da_data_get_n_rows(csv_store, &n_rows) == da_status_success;
 58    pass &=
 59        da_data_select_columns(csv_store, "features", 0, n_cols - 2) == da_status_success;
 60    pass &= da_data_select_columns(csv_store, "labels", n_cols - 1, n_cols - 1) ==
 61            da_status_success;
 62    da_int n_features = n_cols - 1;
 63    da_int n_samples = n_rows;
 64    std::vector<float> X(n_features * n_samples);
 65    std::vector<da_int> y(n_rows);
 66    pass &= da_data_extract_selection_real_s(csv_store, "features", X.data(), n_rows) ==
 67            da_status_success;
 68    pass &= da_data_extract_selection_int(csv_store, "labels", y.data(), n_rows) ==
 69            da_status_success;
 70    da_int n_class = *std::max_element(y.begin(), y.end()) + 1;
 71    da_datastore_destroy(&csv_store);
 72    if (!pass) {
 73        std::cout << "Something went wrong while loading data.\n";
 74        return 1;
 75    }
 76
 77    // Set up and train the decision tree
 78    da_handle tree_handle = nullptr;
 79    pass = da_handle_init_s(&tree_handle, da_handle_decision_tree) == da_status_success;
 80    pass &=
 81        da_tree_set_training_data_s(tree_handle, n_samples, n_features, n_class, X.data(),
 82                                    n_samples, y.data()) == da_status_success;
 83    pass &= da_options_set_int(tree_handle, "maximum depth", 5) == da_status_success;
 84    pass &= da_options_set_int(tree_handle, "seed", 77) == da_status_success;
 85    pass &= da_options_set_string(tree_handle, "scoring function", "gini") ==
 86            da_status_success;
 87    if (!pass) {
 88        std::cout << "Something went wrong setting up the decision tree data and "
 89                     "optional parameters.\n";
 90        return 1;
 91    }
 92
 93    status = da_tree_fit_s(tree_handle);
 94    if (status != da_status_success) {
 95        std::cout << "Failure while fitting the tree\n";
 96        return 1;
 97    }
 98    // Read in data for making predictions
 99    filename = DATA_DIR;
100    filename += "/decision_test.csv";
101    pass = da_datastore_init(&csv_store) == da_status_success;
102    pass &= da_datastore_options_set_string(csv_store, "CSV datastore precision",
103                                            "single") == da_status_success;
104    pass &= da_data_load_from_csv(csv_store, filename.c_str()) == da_status_success;
105    pass &= da_data_get_n_rows(csv_store, &n_rows) == da_status_success;
106    pass &=
107        da_data_select_columns(csv_store, "features", 0, n_cols - 2) == da_status_success;
108    pass &= da_data_select_columns(csv_store, "labels", n_cols - 1, n_cols - 1) ==
109            da_status_success;
110    n_samples = n_rows;
111    std::vector<float> X_test(n_features * n_samples);
112    std::vector<da_int> y_test(n_samples);
113    pass &= da_data_extract_selection_real_s(csv_store, "features", X_test.data(),
114                                             n_samples) == da_status_success;
115    pass &= da_data_extract_selection_int(csv_store, "labels", y_test.data(),
116                                          n_samples) == da_status_success;
117    da_datastore_destroy(&csv_store);
118    if (!pass) {
119        std::cout << "Something went wrong while loading test data.\n";
120        return 1;
121    }
122
123    // Make predictions with model and evaluate score
124    std::vector<da_int> y_pred(n_samples);
125    pass = da_tree_predict_s(tree_handle, n_samples, n_features, X_test.data(), n_samples,
126                             y_pred.data()) == da_status_success;
127    std::vector<float> y_proba(n_samples * n_class);
128    pass = da_tree_predict_proba_s(tree_handle, n_samples, n_features, X_test.data(),
129                                   n_samples, y_proba.data(), n_class,
130                                   n_samples) == da_status_success;
131
132    for (da_int i = 0; i < 5; i++) {
133        std::cout << "Class prediction: " << y_pred[i];
134        std::cout << ", Class probabilities: ";
135        for (da_int j = 0; j < n_class - 1; j++)
136            std::cout << y_proba[j * n_samples + i] << ", ";
137        std::cout << y_proba[(n_class - 1) * n_samples + i];
138        std::cout << std::endl;
139    }
140    float mean_accuracy;
141    pass &= da_tree_score_s(tree_handle, n_samples, n_features, X_test.data(), n_samples,
142                            y_test.data(), &mean_accuracy);
143    std::cout << "Mean accuracy of the tree on the test data: " << mean_accuracy
144              << std::endl;
145    if (mean_accuracy < 0.75) {
146        std::cout << "Performance unexpectedly low.\n";
147        return 1;
148    }
149    da_handle_destroy(&tree_handle);
150
151    return 0;
152}

Further reading#

An introduction to decision trees and to decision forests can be found in Chapters 9 and 15 of Hastie et al. [2009].