GradientBoost

Forked:

This package covers the gradient boosting paradigm: a framework that builds additive expansions based on any fitting criteria.

In machine learning parlance, this is typically referred to as gradient boosting machines, generalized boosted models and stochastic gradient boosting.

Normally, gradient boosting implementations cover a specific algorithm: gradient boosted decision trees. This package covers the framework itself, including such implementations.

References:

• Friedman, Jerome H. "Greedy function approximation: a gradient boosting machine." Annals of Statistics (2001): 1189-1232.
• Friedman, Jerome H. "Stochastic gradient boosting." Computational Statistics & Data Analysis 38.4 (2002): 367-378.
• Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
• Ridgeway, Greg. "Generalized Boosted Models: A guide to the gbm package." Update 1.1 (2007).
• Pedregosa, Fabian, et al. "Scikit-learn: Machine learning in Python." The Journal of Machine Learning Research 12 (2011): 2825-2830.
• Natekin, Alexey, and Alois Knoll. "Gradient boosting machines, a tutorial." Frontiers in neurorobotics 7 (2013).

Machine Learning API

Module GradientBoost.ML is provided for users who are only interested in using existing gradient boosting algorithms for prediction. To get a feel for the API, we will run a demonstration of gradient boosted decision trees on the iris dataset.

Obtain Data

At the moment only two-class classification is handled, so our learner will attempt to separate "setosa" from the other species.

using GradientBoost.ML
using RDatasets

# Obtain iris dataset
iris = dataset("datasets", "iris")
instances = array(iris[:, 1:end-1])
labels = [species == "setosa" ? 1.0 : 0.0 for species in array(iris[:, end])]

# Obtain training and test set (20% test)
num_instances = size(instances, 1)
train_ind, test_ind = GradientBoost.Util.holdout(num_instances, 0.2)

Build Learner

The gradient boosting (GB) learner comprises of a GB algorithm and what output it must produce. In this case, we shall assign a gradient boosted decision tree to output classes.

# Build GBLearner
gbdt = GBDT(;
  loss_function = BinomialDeviance(),
  sampling_rate = 0.6,
  learning_rate = 0.1,
  num_iterations = 100
)
gbl = GBLearner(
  gbdt,  # Gradient boosting algorithm
  :class # Output (:class, :class_prob, :regression)
)

Train and Predict

Currently Matrix{Float64} instances and Vector{Float64} labels are the only handled types for training and prediction. In this case, it is not an issue.

# Train
ML.fit!(gbl, instances[train_ind, :], labels[train_ind])

# Predict
predictions = ML.predict!(gbl, instances[test_ind, :])

Evaluate

If all is well, we should obtain better than baseline accuracy (67%).

# Obtain accuracy
accuracy = mean(predictions .== labels[test_ind]) * 100.0
println("GBDT accuracy: $(accuracy)")

That concludes the demonstration. Detailed below are the available GB learners.

Algorithms

Documented below are the currently implemented gradient boosting algorithms.

GB Decision Tree

Gradient Boosted Decision Tree algorithm backed by DecisionTree.jl regression trees. Current loss functions covered are: LeastSquares, LeastAbsoluteDeviation and BinomialDeviance.

gbdt = GBDT(;
  loss_function = BinomialDeviance(), # Loss function
  sampling_rate = 0.6,                # Sampling rate
  learning_rate = 0.1,                # Learning rate
  num_iterations = 100,               # Number of iterations
  tree_options = {                    # Tree options (DecisionTree.jl regressor)
    :maxlabels => 5,
    :nsubfeatures => 0
  }
)

GB Base Learner

Gradient boosting with a given base learner. Current loss functions covered are: LeastSquares and LeastAbsoluteDeviation. In order to use this, ML.learner_fit and ML.learner_predict functions must be extended. Example provided below for linear regression found in GLM.jl.

import GLM: fit, predict, LinearModel

# Extend functions
function ML.learner_fit(lf::LossFunction,
  learner::Type{LinearModel}, instances, labels)

  model = fit(learner, instances, labels)
end
function ML.learner_predict(lf::LossFunction,
  learner::Type{LinearModel}, model, instances)

  predict(model, instances)
end

Once this is done, the algorithm can be instantiated with the respective base learner.

gbl = GBBL(
  LinearModel;                    # Base Learner
  loss_function = LeastSquares(), # Loss function
  sampling_rate = 0.8,            # Sampling rate
  learning_rate = 0.1,            # Learning rate
  num_iterations = 100            # Number of iterations
)
gbl = GBLearner(gbl, :regression)

Gradient Boosting Framework

All previously developed algorithms follow the framework provided by GradientBoost.GB.

As this package is in its preliminary stage, major changes may occur in the near future and as such we provide minimal README documentation.

All of what is required to be implemented is exampled below:

import GradientBoost.GB
import GradientBoost.LossFunctions: LossFunction

# Must subtype from GBAlgorithm defined in GB module.
type ExampleGB <: GB.GBAlgorithm
  loss_function::LossFunction
  sampling_rate::FloatingPoint
  learning_rate::FloatingPoint
  num_iterations::Int
end

# Model training and co-efficient optimization should be done here.
function GB.build_base_func(
  gb::ExampleGB, instances, labels, prev_func_pred, psuedo)

  model_const = 0.5
  model_pred = (instances) -> Float64[
    sum(instances[i,:]) for i = 1:size(instances, 1)
  ]

  return (instances) -> model_const .* model_pred(instances)
end

A relatively light algorithm that implements GBAlgorithm is GBBL, found in src/gb_bl.jl.

Misc

The links provided below will only work if you are viewing this in the GitHub repository.

Changes

See CHANGELOG.yml.

Future Work

See FUTUREWORK.md.

Contributing

See CONTRIBUTING.md.

License

MIT "Expat" License. See LICENSE.md.