design
The R GBM package allows users to train gradient boosting machines primarily for the purposes of prediction and feature selection. The package is built using RCpp and is composed of two parts: a R front-end that takes user inputs and performs pre-processing before passing a series of arguments to the second part; the C++ back-end. The main algorithmic work is done in the C++ layer, which on completion passes R objects back to the R front-end for postprocessing and reporting. This design document focusses on the C++ back-end, providing descriptions of its scope, functionality and structure; for documentation on the R API please see the R GBM package vignettes.
The C++ back-end, from here on referred to as the "system", provides algorithms to: train a GBM model, make predictions on new data using such a fitted model and calculate the marginal effects of variable data within such a fitted model via "integrating out" the other variables. The main bulk of the C++ codebase focusses on the training of a GBM model, tasks involved in this process include: set-up of datasets, calculation of model residuals, fitting a tree to said residuals and determining the optimal node predictions for the fitted tree. The other pieces of functionality, that is prediction and calculating the marginal effects of variables, are singular functions with little or no developer designed classes associated with them.
The structure imposed on the C++ back-end was selected to:
-
Replace a legacy setup with one more amenable to change.
-
Make the structure and functionality of the system more transparent via appropriate OO design and encapsulation.
-
Implement design patterns where appropriate - in particular to simplify memory management through the application of the RAII idiom.
Within the GBM package the system performs the main algorithmic calculations. It undertakes all of the algorithmic work in training a gradient boosted model, making prediction based on new covariate datasets and calculating the marginal effects of covariates given a fitted model. It does not perform any formatting or postprocessing beyond converting the fitted trees, errors etc. to a R list object and passing it back to the front-end.
system, the description of the system will focus on the behaviour of
the system and its structure is captured by the Functional and
Development views respectively. Within the package the system is
located in the /src directory. To conclude this introduction, it
should be noted that the system has been developed in line with Google
C++ style.
The main use cases of the system are:
- Training a gradient boosted model using data and an appropriate statistical model.
- Predicting the response from new covariates using a trained model.
- Calculating Marginal effects of data using a trained model.
The system is composed of numerous classes used almost exclusively for
training along with an interface to the R front-end. This entry point
is appropriately named gbmentry.cpp and contains 3 functions: gbm,
gbm_pred and gbm_plot. These functions perform the training,
prediction and marginal effects calculations described in Section 2.1
respectively. The functionality and dynamic behaviour of these
methods will now be described.
Figure 1. Component diagram showing the interface between the R layer and the system.
The procedure to train a gbm model follows a sequence of simple steps as shown in Figure 2. Upon entry to the gbm method the user specified parameters are converted to an appropriate GBM configuration objects, see datadistparams.h and treeparams.h. These configuration objects are then used to initialize the GBM engine, this component stores both the tree parameters, which define the tree to be fitted, and the data/distribution container. Upon initialization the GBM engine will also initialize an instance of an appropriate dataset class, a bagged data class and a distribution object from the GBM configuration object. The dataset object contains both the training and validation data; these sets live together in vector containers and to swap between them the pointer to the first element in the set of interest is shifted by the appropriate amount. The bagged data class defines which elements of the dataset are used in growing an individual tree; how these elements are chosen is distribution dependent. After this, the GbmFit object is initialized. This object contains the current fitted learner, the errors associated with the fit and the function estimate (a Rcpp numeric vector). The function estimate is set to the previous estimates if provided or an appropriate value for the distribution selected otherwise.
With the GBM engine and the fit object initialized, the algorithm loops over the number of trees to fit and performs the following actions:
- Create a tree object using .
- Bag the data to use for fitting the tree.
- Calculate the residuals using the current estimate, bagged data and distribution object.
- Fit the tree to the calculated residuals - this is done by generating all possible splits for a subset of variables and choosing the split to minimize the variance of the residuals within nodes. The best splits for each node are cached so if a node is not split on this round, no future splitting of that node is evaluated.
- Set the terminal node predictions which minimize the error.
- Adjust the tree, so non-terminal nodes also have predictions.
- Update the estimate, for both training and validation sets, and calculate the: training errors, validation errors and the improvement in the out of bag error from the update.
- Wrap up the fitted tree and errors, along with a reference to the dataset, in a FittedLearner object (see
FittedLearner.h).
The returned fitted learner object defines the "current fit" in the GbmFit object, which is used to update the errors. At the end of a single iteration, the tree and the associated errors are converted to a R List representation which is then output to the R layer once all the trees have been fitted.
Figure 2. Activity diagram for the process of training a GBM model.
The bagging of the data from the training set and calculation of residuals is distribution dependent and so is incorporated in the system as appropriate methods in the distribution class and its container. The tree object is comprised of several components, the principle ones are: a root node, a vector of the terminal nodes and a vector mapping the bagged data to terminal nodes. A node splitter which generates and assigns the best potential split to each terminal node is used in the tree growing method. This structure is shown below in Figure 3.
Figure 3. Component diagram showing what the GBM Engine component is comprised of.
Using a previously fitted GBM model, the system can predict the response of further covariate data. The R frontend passes the following variables to the gbm_pred function in gbmentry.cpp: the covariates for prediction, the number of trees to use to predict, the initial prediction estimate, the fitted trees, the categories of the splits, the variable types and a bool indicating whether to return the results using a single fitted tree or not.
The prediction for the new covariates is then initialized, either to the previous tree prediction or the initial estimate value from the model training if it is the first tree prediction to be calculating. The number of trees to be fitted is then looped over, within each iteration the observations are in the covariate dataset are also looped over. Each observation is initially in the root node, a counter which tracks the current node the observation is in is thus set to 0. This observation is then moved through the tree, updating its current node, until it reaches the appropriate terminal node. Once the algorithm reaches a terminal node, the prediction for that observation and tree is set to the final split value of the terminal node's parent in the tree. This process is repeated over all observations and for all trees, once completed the prediction vector is wrapped up and passed back to the R front-end, see Figure 4.
Figure 4. Activity diagram showing how the algorithm performs predictions on new covariate data.
The final piece of functionality offered by the system is to calculate the marginal effects of a variable by "integrating" out the others. As well as a fitted gbm model and covariate data the user also specifies which variables they're interested in at the R layer. This method utilises a NodeStack class which is defined at the beginning of gbmentry.cpp, this is a simple class that defines a stack of pairs. These pairs contain the node index, that is what node in the tree we are looking at, and its weight.
With this in mind the method works as follows:
- the initial prediction is set to user specified initial values.
- the algorithm loops over the number of trees to fit.
- the algorithm then loops over the observations.
- in the observation loop it creates a root node, puts it on the stack and sets the observation's current node to be 0 with weight 1.0.
- it gets the top node off the stack and checks if it is split.
- (a) if it isn't split the predicted function for this variable and tree is set to the split value times the weight of the node.
- (b) if the node is non-terminal it checks if the split variable is in the user specified variables of interested. If so the observation is moved to the appropriate child node which is then added to the stack. If this is not the case, two nodes (an average of both left/right splits - this "integrates" out the other variables) are added to the stack and it returns to step 5.
- When the observation reaches a terminal node it gets another observation and repeats steps 5 & 6.
- With all trees fitted the predicted function is wrapped up and output.
Figure 5. Activity diagram for calculating the marginal effects of specific variables.
The near entirety of the system is devoted to the task of training a gbm model and so this Section will focus on describing the classes and design patterns implemented to meet this end. Starting at a high level the primary objects are the "gbm engine" found in gbm_engine.cpp and the fit defined in gbm_fit.h. The component has the data and distribution container, see gbm_datacontainer.cpp, and a reference to the tree parameters (treeparams.h) as private members; this is shown in Figure 3. The "gbm engine" generates the initial function estimate and through the FitLearner method which run the methods of the gbm_datacontainer.cpp and tree.cpp to perform tasks such as growing trees and calculating errors/bagging data. The system is built on the RAII idiom and these container classes are initialized on contruction of this gbm engine object and released on its destruction. This idiom is applied across the system to simplify the task of memory management and further elicit appropriate object design. Beyond this, encapsulation and const. correctness are implemented where possible within the system.
The R layer passes a number of parameters/R objects to the system. These are converted to appropriate parameters and stored in simple objects for use in initializing the data and distribution container and tree objects. After construction of the gbm engine the DataDistParams class is not used again during training while the TreeParams object are stored within the engine and used to initialize trees for fitting on each iteration.
The dataset class, dataset.h, is part of the data/distribution container and is initialized using the DataDistParams described in the previous Section. This class stores both appropriate R objects, e. g. the response is stored as RCpp::NumericMatrix, and standard C++ datatypes describing the data, e. g. unsigned long num_traindata_. To iterate over these R vectors/arrays the dataset object has appropriate pointers to these arrays which can be accessed via the corresponding getter methods. The R objects stored here contain both training and validation data, to access a particular dataset the appropriate pointers are shifted by the length of the dataset so they point to the beginning of the validation/training set. Most of this class is defined within the header as the number of calls to the dataset's getter functions means that inlining these methods has a significant impact on the system's overall performance. It also has a RandomOrder() method which takes the predictor variables and shuffles them, this is used during the tree growing phase where all splits are generated for a random subset of features in the data. Finally, an associated class is the "Bag"; this class contains a vector of integers (0/1's) called the "bag" which defines the training data to be used in growing the tree.
The distribution class, distribution.h, is an abstract class which defines the implementation any other distributions to be included in the system must follow. The distribution object performs numerous features using an instance of thedataset class defined in the previous Section. Importantly it constructs the bag for the data, this method appropriately titled BagData is only different for the pairwise distribution where data groupings affect the bagging procedure. Before constructing the bags, the distribution object needs to be initialized with the data. This initialization will take the data rows and construct a multi-map which maps those rows to their corresponding observation ids, often each row is an unique observation but this is not always the case. This multi-map ensures bagging occurs on a by-observation basis as opposed to a by-row basis, as the latter would result in overly optimistic errors and potentially a failure of the training method where data from a single observation could appear both in the bag and out of it. The distribution object is also responsible for calculating the residuals for tree growing, the errors in the training and validation sets, initializing the function estimate and calculating the out of bag error improvement on fitting a new tree. These methods are all accessed via its container class stored within the gbm engine object.
Figure 6. Diagram showing the distributions currently implemented within the system.
The construction of the a distribution object is done using a dynamic factory pattern, see Figure 7. In this design, the constructors of the concrete distribution classes are private and they contain a static Create method. This method is registered to a map in the factory, distribution_factory.cpp, where the name of the distribution, a string, is its key. On creation of a gbm engine object, a distribution factory is created and the appropriate distribution is generated from the factory using the user selected distribution, a string which acts as key to the same map, and DataDistParams struct.
Figure 7. Dynamic Factory pattern used to control the creation of distribution objects. The distribution factory itself is a singleton.
To conclude this subsection, there are some concrete distribution specific details to describe. The pairwise distribution, CPairwise.h, uses several objects which specify the information ratio measure that this distribution uses in its implementation. These classes all inherit from an abstract IRMeasure class and are defined in the CPairwise.h and CPairwise.cpp files.
Figure 8. Diagram displaying the information ratio classes used by the pairwise distribution.
The other distribution which has a unique design is the Cox partial hazards model. The Cox partial hazards model is a survival model whose implementation depends on whether the response matrix provided to the system is that of "censored" data or "start-stop" data. In essence, if the response matrix has 2 columns it is censored and if it has more than 2 it is start-stop. To incorporate this added complexity, the CCoxPH.h class follows a state pattern, whereby the Cox PH object contains a pointer to an object implementing the correct methods for a specific scenario and those objects contain a pointer to the Cox PH object. This design is shown in Figure 9.
Figure 9. The Cox Partial Hazards distribution employs a state design pattern to accommodate the dependency of its implementation on the response matrix.
The final component of the gbm engine to consider is the tree class defined in tree.h. As described in Section 2.1 the tree class contains: a rootnode, of class CNode, a vector of pointers to terminal nodes, a vector assigning data to those terminal nodes, a node search object (see node_searcher.h) and various data describing the tree (such as its maximum depth etc.). The tree class has methods that grow the tree, reset it for another growth, prediction on validation data, adjusting the tree once predictions are assigned to the terminal nodes and outputting it in a suitable format for the R layer to use.
The most important part of this class is the method for the growing of the tree. A key component in growing a tree is identifying appropriate splits, this role is the responsibility of the node searcher object. The node searcher object stores the best split identified for each terminal node. It uses vectors of variable splitters (see vec_varsplitters.h and varsplitter.h) to determine the best splits generated for each node and for each variable. Within the GenerateAllSplits() method, one vector of NodeParams, see below, copies the current best splits stored in the node searcher object. The variables to split on are then looped over and a vector of variable splits, one for each terminal node, is initialized to calculate the best split for the current variable in each node.
The best split for the current variable is extracted from this vector and used to update the copy of the best splits. At the end of this loop, the updated copy of best splits are then assigned to the best splits stored in the node search object. This design follows a MapReduce structure and allows for parallelisation of this search process; the details of this parallelisation (see parallel_details.h) are also stored as a private member in the node search class.
The node class itself contains pointers to its children and its methods, such as calculating predictions, are dependent on the type of split present. The node can either be terminal, so it has no split, or have a continuous/categorical split. To account for this dependency on the split, the node class is implemented with a state design pattern , similar to the Cox PH distribution, but in this instance it posseses a SetStrategy() method so the implementation of a node can change as a tree grows. The variable splitter objects contain "node parameters", see node_parameters.h, which encapsulate the properties of the proposed split nodes. These NodeParams objects use NodeDef structs, located in node_parameters.h, to define the proposed node splits and provides methods to evaluate the quality of the proposed splits. Finally, the varsplitter class has a state design pattern where on construction the methods for how the variable of interest should be split are set, see Figure 11.
Figure 10. State pattern for the node object, it possesses a "SetStrategy()" method so nodes can change type as the tree grows.
Figure 11. State pattern for the variable splitter object. How it splits on a variable is set on construction.
To conclude this Secion formal system class and interaction diagrams are presented in Figures 12 & 13 repsectively. These provide a complete and more detailed picture of the classes and their interactions which define the system, in particular the process of training a gbm.
Figure 12. System class diagram showing the classes and how they interface in the training method.
Figure 13. Sequence diagram for training a single tree when fitting a gradient boosted model.
To use the GBM package it is necessary to install a version of R on your system, preferably 3.2 or higher. With R installed, the GBM package may be installed by opening up a R terminal and using the install.packages("gbm") command to install the package.
The system is subject to two types of testing: black-box system and acceptance tests and unit testing. These tests are designed to run with the testthat package and ship with the GBM package in /tests/ folder. The package can be checked using R CMD check <built package> which will automatically run all of the tests within it and report any warnings or errors.
Currently the system has a series of black box system tests which check that the package is operating as expected using what can be considered 'sanity test cases' as well testing for errors. These tests focus primarily on the Gaussian, Bernoulli and CoxPH distributions at this time. Some tests, such as the checking the effects of the offset, touch all distributions implemented in the system. Using the covr package, the travis CI server automatically collects code coverage data and sends it to codecov.io. As of 03/06/2016 this coverage is at 66.07%, with a coverage of the R layer at 42.15% and coverage of the system at 79.28%.
This coverage tool is not perfect and when measuring exercisation of inlined code it is likely to say that the inlined functionality has been missed when in fact it has been exercised. Beyond this the tests do not exercise the counting Cox PH functionality, misses node functionality such as PrintSubTree and GetVarRelativeInfluence, does not touch many unhappy paths/error throwing paths and completely misses the gbm_plot functionality. That being said, even with only the higher level black-box testing in place most of the important paths within the system are exercised. By contrast the R layer has a few well tested pieces of functionality, such as gbm.fit.R, but a large number of functions have no coverage at all.
Finally, the system itself can now be tested using R's testthat package thanks to a recent update. These unit tests have yet to be written.