// Catalano Machine Learning Library
// The Catalano Framework
//
// Copyright 2015 Diego Catalano
// diego.catalano at live.com
//
// Copyright 2015 Haifeng Li
// haifeng.hli at gmail.com
//
// Based on Smile (Statistical Machine Intelligence & Learning Engine)
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
package Catalano.MachineLearning.Regression.RegressionTrees.Learning;
import Catalano.Core.ArraysUtil;
import Catalano.MachineLearning.Dataset.DatasetRegression;
import Catalano.MachineLearning.Dataset.DecisionVariable;
import Catalano.MachineLearning.Regression.IRegression;
import Catalano.MachineLearning.Regression.RegressionTrees.RegressionTree;
import Catalano.Math.Tools;
import java.io.Serializable;
import java.util.Arrays;
/**
* Gradient boosting for regression. Gradient boosting is typically used
* with decision trees (especially CART regression trees) of a fixed size as
* base learners. For this special case Friedman proposes a modification to
* gradient boosting method which improves the quality of fit of each base
* learner.
*
* Generic gradient boosting at the t-th step would fit a regression tree to
* pseudo-residuals. Let J be the number of its leaves. The tree partitions
* the input space into J disjoint regions and predicts a constant value in
* each region. The parameter J controls the maximum allowed
* level of interaction between variables in the model. With J = 2 (decision
* stumps), no interaction between variables is allowed. With J = 3 the model
* may include effects of the interaction between up to two variables, and
* so on. Hastie et al. comment that typically 4 ≤ J ≤ 8 work well
* for boosting and results are fairly insensitive to the choice of in
* this range, J = 2 is insufficient for many applications, and J > 10 is
* unlikely to be required.
*
* Fitting the training set too closely can lead to degradation of the model's
* generalization ability. Several so-called regularization techniques reduce
* this over-fitting effect by constraining the fitting procedure.
* One natural regularization parameter is the number of gradient boosting
* iterations T (i.e. the number of trees in the model when the base learner
* is a decision tree). Increasing T reduces the error on training set,
* but setting it too high may lead to over-fitting. An optimal value of T
* is often selected by monitoring prediction error on a separate validation
* data set.
*
* Another regularization approach is the shrinkage which times a parameter
* η (called the "learning rate") to update term.
* Empirically it has been found that using small learning rates (such as
* η < 0.1) yields dramatic improvements in model's generalization ability
* over gradient boosting without shrinking (η = 1). However, it comes at
* the price of increasing computational time both during training and
* prediction: lower learning rate requires more iterations.
*
* Soon after the introduction of gradient boosting Friedman proposed a
* minor modification to the algorithm, motivated by Breiman's bagging method.
* Specifically, he proposed that at each iteration of the algorithm, a base
* learner should be fit on a subsample of the training set drawn at random
* without replacement. Friedman observed a substantional improvement in
* gradient boosting's accuracy with this modification.
*
* Subsample size is some constant fraction f of the size of the training set.
* When f = 1, the algorithm is deterministic and identical to the one
* described above. Smaller values of f introduce randomness into the
* algorithm and help prevent over-fitting, acting as a kind of regularization.
* The algorithm also becomes faster, because regression trees have to be fit
* to smaller datasets at each iteration. Typically, f is set to 0.5, meaning
* that one half of the training set is used to build each base learner.
*
* Also, like in bagging, sub-sampling allows one to define an out-of-bag
* estimate of the prediction performance improvement by evaluating predictions
* on those observations which were not used in the building of the next
* base learner. Out-of-bag estimates help avoid the need for an independent
* validation dataset, but often underestimate actual performance improvement
* and the optimal number of iterations.
*
* Gradient tree boosting implementations often also use regularization by
* limiting the minimum number of observations in trees' terminal nodes.
* It's used in the tree building process by ignoring any splits that lead
* to nodes containing fewer than this number of training set instances.
* Imposing this limit helps to reduce variance in predictions at leaves.
*
*
References
*
* - J. H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine, 1999.
* - J. H. Friedman. Stochastic Gradient Boosting, 1999.
*
*
* @author Haifeng Li
*/
public class GradientBoostingTree implements IRegression, Serializable{
private DecisionVariable[] attributes = null;
/**
* Regression loss function.
*/
public static enum Loss {
/**
* Least squares regression. Least-squares is highly efficient for
* normally distributed errors but is prone to long tails and outliers.
*/
LeastSquares,
/**
* Least absolute deviation regression. The gradient tree boosting based
* on this loss function is highly robust. The trees use only order
* information on the input variables and the pseudo-response has only
* two values {-1, +1}. The line searches (terminal node values) use
* only medians.
*/
LeastAbsoluteDeviation,
/**
* Huber loss function for M-regression, which attempts resistance to
* long-tailed error distributions and outliers while maintaining high
* efficency for normally distributed errors.
*/
Huber,
}
/**
* Forest of regression trees.
*/
private RegressionTree[] trees;
/**
* The intercept.
*/
private double b = 0.0;
/**
* Variable importance. Every time a split of a node is made on variable
* the impurity criterion for the two descendent nodes is less than the
* parent node. Adding up the decreases for each individual variable over
* all trees in the forest gives a simple variable importance.
*/
private double[] importance;
/**
* Loss function.
*/
private Loss loss = Loss.LeastAbsoluteDeviation;
/**
* The shrinkage parameter in (0, 1] controls the learning rate of procedure.
*/
private double shrinkage = 0.005;
/**
* The number of leaves in each tree.
*/
private int J = 6;
/**
* The number of trees.
*/
private int T = 500;
/**
* The sampling rate for stochastic tree boosting.
*/
private double f = 0.7;
/**
* Initialize a new instance of the GradientBoostingTree class.
*/
public GradientBoostingTree(){
this(500);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param T Number of trees.
*/
public GradientBoostingTree(int T) {
this(T, 6);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param T Number of trees.
* @param J Number of leafs in each tree.
*/
public GradientBoostingTree(int T, int J){
this(T, J, Loss.LeastSquares);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param T Number of trees.
* @param J Number of leafs in each tree.
* @param loss Regression loss function.
*/
public GradientBoostingTree(int T, int J, Loss loss){
this(T, J, loss, 0.005);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param T Number of trees.
* @param J Number of leafs in each tree.
* @param loss Regression loss function.
* @param shrinkage Shrinkage parameter in (0, 1] controls the learning rate of procedure.
*/
public GradientBoostingTree(int T, int J, Loss loss, double shrinkage){
this(T, J, loss, shrinkage, 0.7);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param T Number of trees.
* @param J Number of leafs in each tree.
* @param loss Regression loss function.
* @param shrinkage Shrinkage parameter in (0, 1] controls the learning rate of procedure.
* @param f Sampling rate for stochastic tree boosting.
*/
public GradientBoostingTree(int T, int J, Loss loss, double shrinkage, double f){
this(null, T, J, loss, shrinkage, f);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param attributes Attributes.
*/
public GradientBoostingTree(DecisionVariable[] attributes){
this(attributes, 500);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param attributes Attributes.
* @param T Number of trees.
*/
public GradientBoostingTree(DecisionVariable[] attributes, int T){
this(attributes, T, 6);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param attributes Attributes.
* @param T Number of trees.
* @param J Number of leafs in each tree.
*/
public GradientBoostingTree(DecisionVariable[] attributes, int T, int J){
this(attributes, T, J, Loss.LeastSquares);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param attributes Attributes.
* @param T Number of trees.
* @param J Number of leafs in each tree.
* @param loss Regression loss function.
*/
public GradientBoostingTree(DecisionVariable[] attributes, int T, int J, Loss loss){
this(attributes, T, J, loss, 0.005);
}
/**
* Initialize a new instance of the GradientBoostingTree class.
* @param attributes Attributes.
* @param T Number of trees.
* @param J Number of leafs in each tree.
* @param loss Regression loss function.
* @param shrinkage Shrinkage parameter in (0, 1] controls the learning rate of procedure.
*/
public GradientBoostingTree(DecisionVariable[] attributes, int T, int J, Loss loss, double shrinkage){
this(attributes, T, J, loss, shrinkage, 0.7);
}
/**
* Constructor. Learns a gradient tree boosting for regression.
*
* @param attributes the attribute properties.
* @param T the number of iterations (trees).
* @param J the number of leaves in each tree.
* @param loss loss function for regression. By default, least absolute
* deviation is employed for robust regression.
* @param shrinkage the shrinkage parameter in (0, 1] controls the learning rate of procedure.
* @param f the sampling fraction for stochastic tree boosting.
*/
public GradientBoostingTree(DecisionVariable[] attributes, int T, int J, Loss loss, double shrinkage, double f) {
this.attributes = attributes;
this.loss = loss;
this.T = T;
this.J = J;
this.shrinkage = shrinkage;
this.f = f;
}
@Override
public void Learn(DatasetRegression dataset) {
Learn(dataset.getInput(), dataset.getOutput());
}
@Override
public void Learn(double[][] input, double[] output) {
if (input.length != output.length) {
throw new IllegalArgumentException(String.format("The sizes of X and Y don't match: %d != %d", input.length, output.length));
}
if (shrinkage <= 0 || shrinkage > 1) {
throw new IllegalArgumentException("Invalid shrinkage: " + shrinkage);
}
if (f <= 0 || f > 1) {
throw new IllegalArgumentException("Invalid sampling fraction: " + f);
}
if (attributes == null) {
int p = input[0].length;
attributes = new DecisionVariable[p];
for (int i = 0; i < p; i++) {
attributes[i] = new DecisionVariable("F" + i);
}
}
int n = input.length;
int N = (int) Math.round(n * f);
int[] perm = new int[n];
int[] samples = new int[n];
for (int i = 0; i < n; i++) {
perm[i] = i;
}
double[] residual = new double[n];
double[] response = null; // response variable for regression tree.
RegressionTree.NodeOutput nodeOutput = null;
if (loss == Loss.LeastSquares) {
response = residual;
b = Catalano.Statistics.Tools.Mean(output);
for (int i = 0; i < n; i++) {
residual[i] = output[i] - b;
}
} else if (loss == Loss.LeastAbsoluteDeviation) {
nodeOutput = new LADNodeOutput(residual);
System.arraycopy(output, 0, residual, 0, n);
b = Catalano.Statistics.DescriptiveStatistics.Median(residual);
response = new double[n];
for (int i = 0; i < n; i++) {
residual[i] = output[i] - b;
response[i] = Math.signum(residual[i]);
}
} else if (loss == Loss.Huber) {
response = new double[n];
System.arraycopy(output, 0, residual, 0, n);
b = Catalano.Statistics.DescriptiveStatistics.Median(residual);
for (int i = 0; i < n; i++) {
residual[i] = output[i] - b;
}
}
int[][] order = sort(attributes, input);
trees = new RegressionTree[T];
for (int m = 0; m < T; m++) {
Arrays.fill(samples, 0);
Tools.Permutate(perm);
for (int i = 0; i < N; i++) {
samples[perm[i]] = 1;
}
if (loss == Loss.Huber) {
nodeOutput = new HuberNodeOutput(residual, response, 0.9);
}
trees[m] = new RegressionTree(attributes, J, order, samples, nodeOutput);
trees[m].Learn(input, response);
for (int i = 0; i < n; i++) {
residual[i] -= shrinkage * trees[m].Predict(input[i]);
if (loss == Loss.LeastAbsoluteDeviation) {
response[i] = Math.signum(residual[i]);
}
}
}
importance = new double[attributes.length];
for (RegressionTree tree : trees) {
double[] imp = tree.getImportance();
for (int i = 0; i < imp.length; i++) {
importance[i] += imp[i];
}
}
}
/**
* Returns the variable importance. Every time a split of a node is made
* on variable the impurity criterion for the two descendant nodes is less
* than the parent node. Adding up the decreases for each individual
* variable over all trees in the forest gives a simple measure of variable
* importance.
*
* @return the variable importance
*/
public double[] importance() {
return importance;
}
/**
* Class to calculate node output for LAD regression.
*/
class LADNodeOutput implements RegressionTree.NodeOutput {
/**
* Residuals to fit.
*/
double[] residual;
/**
* Constructor.
* @param residual response to fit.
*/
public LADNodeOutput(double[] residual) {
this.residual = residual;
}
@Override
public double calculate(int[] samples) {
int n = 0;
for (int s : samples) {
if (s > 0) n++;
}
double[] r = new double[n];
for (int i = 0, j = 0; i < samples.length; i++) {
if (samples[i] > 0) {
r[j++] = residual[i];
}
}
return Catalano.Statistics.DescriptiveStatistics.Median(r);
}
}
/**
* Returns the sampling rate for stochastic gradient tree boosting.
* @return the sampling rate for stochastic gradient tree boosting.
*/
public double getSamplingRate() {
return f;
}
/**
* Returns the (maximum) number of leaves in decision tree.
* @return the (maximum) number of leaves in decision tree.
*/
public int getNumLeaves() {
return J;
}
/**
* Returns the loss function.
* @return the loss function.
*/
public Loss getLossFunction() {
return loss;
}
/**
* Class to calculate node output for Huber regression.
*/
class HuberNodeOutput implements RegressionTree.NodeOutput {
/**
* Residuals.
*/
double[] residual;
/**
* Responses to fit.
*/
double[] response;
/**
* The value to choose α-quantile of residuals.
*/
double alpha;
/**
* Cutoff.
*/
double delta;
/**
* Constructor.
* @param r response to fit.
*/
public HuberNodeOutput(double[] residual, double[] response, double alpha) {
this.residual = residual;
this.response = response;
this.alpha = alpha;
int n = residual.length;
for (int i = 0; i < n; i++) {
response[i] = Math.abs(residual[i]);
}
int[] index = ArraysUtil.Argsort(response, true);
delta = response[index[(int)(n * alpha)]];
for (int i = 0; i < n; i++) {
if (Math.abs(residual[i]) <= delta) {
response[i] = residual[i];
} else {
response[i] = delta * Math.signum(residual[i]);
}
}
}
@Override
public double calculate(int[] samples) {
int n = 0;
for (int s : samples) {
if (s > 0) n++;
}
double[] res = new double[n];
for (int i = 0, j = 0; i < samples.length; i++) {
if (samples[i] > 0) {
res[j++] = residual[i];
}
}
double r = Catalano.Statistics.DescriptiveStatistics.Median(res);
double output = 0.0;
for (int i = 0; i < samples.length; i++) {
if (samples[i] > 0) {
double d = residual[i] - r;
output += Math.signum(d) * Math.min(delta, Math.abs(d));
}
}
output = r + output / n;
return output;
}
}
/**
* Sorts each variable and returns the index of values in ascending order.
* Only numeric attributes will be sorted. Note that the order of original
* array is NOT altered.
*
* @param x a set of variables to be sorted. Each row is an instance. Each
* column is a variable.
* @return the index of values in ascending order
*/
private int[][] sort(DecisionVariable[] attributes, double[][] x) {
int n = x.length;
int p = x[0].length;
double[] a = new double[n];
int[][] index = new int[p][];
for (int j = 0; j < p; j++) {
if (attributes[j].type == DecisionVariable.Type.Continuous) {
for (int i = 0; i < n; i++) {
a[i] = x[i][j];
}
index[j] = ArraysUtil.Argsort(a, true);
}
}
return index;
}
/**
* Returns the number of trees in the model.
*
* @return the number of trees in the model
*/
public int size() {
return trees.length;
}
/**
* Trims the tree model set to a smaller size in case of over-fitting.
* Or if extra decision trees in the model don't improve the performance,
* we may remove them to reduce the model size and also improve the speed of
* prediction.
*
* @param T the new (smaller) size of tree model set.
*/
public void trim(int T) {
if (T > trees.length) {
throw new IllegalArgumentException("The new model size is larger than the current size.");
}
if (T <= 0) {
throw new IllegalArgumentException("Invalid new model size: " + T);
}
if (T < trees.length) {
trees = Arrays.copyOf(trees, T);
}
}
@Override
public double Predict(double[] feature) {
double y = b;
for (int i = 0; i < T; i++) {
y += shrinkage * trees[i].Predict(feature);
}
return y;
}
@Override
public IRegression clone() {
try {
return (IRegression)super.clone();
} catch (CloneNotSupportedException ex) {
throw new IllegalArgumentException("Clone not supported: " + ex.getMessage());
}
}
}
Ads help maintain this website.