package jsat.regression;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.Vec;
import jsat.math.Function;
import jsat.math.Function1D;
import jsat.math.rootfinding.RootFinder;
import jsat.math.rootfinding.Zeroin;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.FakeExecutor;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;
/**
* An implementation of Stochastic Gradient Boosting (SGB) for the Squared Error
* loss. SGB is also known as Gradient Boosting Machine. There is a specialized
* version of SGB known as TreeBoost, that is not implemented by this method.
* SGB is a boosting method derived for regression. It uses many weak learners
* by attempting to estimate the residual error of all previous learners. It can
* also use an initial strong learner and use the weak learners to refine the
* initial estimate.
*
*
* See papers:
* Friedman, J. H. (2002).
*
* Stochastic gradient boosting. Computational Statistics&Data Analysis,
* 38(4), 367–378.
*
* Mohan, A., Chen, Z.,&Weinberger, K. (2011).
* Web-search
* ranking with initialized gradient boosted regression trees.
* Journal of Machine Learning Research, 14,
*
*
*
* @author Edward Raff
*/
public class StochasticGradientBoosting implements Regressor, Parameterized
{
private static final long serialVersionUID = -2855154397476855293L;
/**
* The default value for the
* {@link #setTrainingProportion(double) training proportion} is
* {@value #DEFAULT_TRAINING_PROPORTION}.
*/
public static final double DEFAULT_TRAINING_PROPORTION = 0.5;
/**
* The default value for the {@link #setLearningRate(double) } is
* {@value #DEFAULT_LEARNING_RATE}
*/
public static final double DEFAULT_LEARNING_RATE = 0.1;
/**
* The proportion of the data set to be used for each iteration of training.
* The points that make up the iteration are a random sampling without
* replacement.
*/
private double trainingProportion;
private Regressor weakLearner;
private Regressor strongLearner;
/**
* The ordered list of weak learners
*/
private List F;
/**
* The list of learner coefficients for each weak learner.
*/
private List coef;
private double learningRate;
private int maxIterations;
/**
* Creates a new initialized SGB learner.
*
* @param strongLearner the powerful learner to refine with weak learners
* @param weakLearner the weak learner to fit to the residuals in each iteration
* @param maxIterations the maximum number of algorithm iterations to perform
* @param learningRate the multiplier to apply to the weak learners
* @param trainingPortion the proportion of the data set to use for each iteration of learning
*/
public StochasticGradientBoosting(Regressor strongLearner, Regressor weakLearner, int maxIterations, double learningRate, double trainingPortion)
{
this.trainingProportion = trainingPortion;
this.strongLearner = strongLearner;
this.weakLearner = weakLearner;
this.learningRate = learningRate;
this.maxIterations = maxIterations;
}
/**
* Creates a new SGB learner that is initialized using the weak learner.
*
* @param weakLearner the weak learner to fit to the residuals in each iteration
* @param maxIterations the maximum number of algorithm iterations to perform
* @param learningRate the multiplier to apply to the weak learners
* @param trainingPortion the proportion of the data set to use for each iteration of learning
*/
public StochasticGradientBoosting(Regressor weakLearner, int maxIterations, double learningRate, double trainingPortion)
{
this(null, weakLearner, maxIterations, learningRate, trainingPortion);
}
/**
* Creates a new SGB learner that is initialized using the weak learner.
*
* @param weakLearner the weak learner to fit to the residuals in each iteration
* @param maxIterations the maximum number of algorithm iterations to perform
* @param learningRate the multiplier to apply to the weak learners
*/
public StochasticGradientBoosting(Regressor weakLearner, int maxIterations, double learningRate)
{
this(weakLearner, maxIterations, learningRate, DEFAULT_TRAINING_PROPORTION);
}
/**
* Creates a new SGB learner that is initialized using the weak learner.
*
* @param weakLearner the weak learner to fit to the residuals in each iteration
* @param maxIterations the maximum number of algorithm iterations to perform
*/
public StochasticGradientBoosting(Regressor weakLearner, int maxIterations)
{
this(weakLearner, maxIterations, DEFAULT_LEARNING_RATE);
}
/**
* Sets the maximum number of iterations used in SGB.
*
* @param maxIterations the maximum number of algorithm iterations to perform
*/
public void setMaxIterations(int maxIterations)
{
this.maxIterations = maxIterations;
}
/**
* Returns the maximum number of iterations used in SGB
* @return the maximum number of algorithm iterations to perform
*/
public int getMaxIterations()
{
return maxIterations;
}
/**
* Sets the learning rate of the algorithm. The GB version uses a learning
* rate of 1. SGB uses a learning rate in (0,1) to avoid overfitting. The
* learning rate is multiplied by the output of each weak learner to reduce
* its contribution.
*
* @param learningRate the multiplier to apply to the weak learners
* @throws ArithmeticException if the learning rate is not in the range (0, 1]
*/
public void setLearningRate(double learningRate)
{
//+- Inf case captured in >1 <= 0 case
if(learningRate > 1 || learningRate <= 0 || Double.isNaN(learningRate))
throw new ArithmeticException("Invalid learning rate");
this.learningRate = learningRate;
}
/**
* Returns the learning rate of the algorithm used to control overfitting.
* @return the learning rate multiplier applied to the weak learner outputs
*/
public double getLearningRate()
{
return learningRate;
}
/**
* The GB version uses the whole data set at each iteration. SGB can use a
* fraction of the data set at each iteration in order to reduce overfitting
* and add randomness.
*
* @param trainingProportion the fraction of training the data set to use
* for each iteration of SGB
* @throws ArithmeticException if the trainingPortion is not a valid
* fraction in (0, 1]
*/
public void setTrainingProportion(double trainingProportion)
{
//+- Inf case captured in >1 <= 0 case
if(trainingProportion > 1 || trainingProportion <= 0 || Double.isNaN(trainingProportion))
throw new ArithmeticException("Training Proportion is invalid");
this.trainingProportion = trainingProportion;
}
/**
* Returns the fraction of the data points used during each iteration of the
* training algorithm.
*
* @return the fraction of the training data set to use for each
* iteration of SGB
*/
public double getTrainingProportion()
{
return trainingProportion;
}
@Override
public double regress(DataPoint data)
{
if(F == null || F.isEmpty())
throw new UntrainedModelException();
double result = 0;
for(int i =0; i < F.size(); i++)
result += F.get(i).regress(data)*coef.get(i);
return result;
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
//use getAsDPPList to get coppies of the data points, so we can safely alter this set
final List> backingResidsList = dataSet.getAsDPPList();
F = new ArrayList(maxIterations);
coef = new DoubleList(maxIterations);
//Add the first learner. Either an instance of the weak learner, or a strong initial estimate
Regressor lastF = strongLearner == null ? weakLearner.clone() : strongLearner.clone();
lastF.train(dataSet, parallel);
F.add(lastF);
coef.add(learningRate*getMinimizingErrorConst(backingResidsList, lastF));
/**
* Instead of recomputing previous weak learner's output, keep track of
* the current total sum to know the current prediction value
*/
final double[] currPredictions = new double[dataSet.getSampleSize()];
/**
* The residuals
*/
RegressionDataSet resids = RegressionDataSet.usingDPPList(backingResidsList);
final int randSampleSize = (int) Math.round(resids.getSampleSize()*trainingProportion);
final List> randSampleList = new ArrayList>(randSampleSize);
final Random rand = RandomUtil.getRandom();
for(int iter = 0; iter < maxIterations; iter++)
{
final double lastCoef = coef.get(iter);
lastF = F.get(iter);
//Compute the new residuals
for(int j = 0; j < resids.getSampleSize(); j++)
{
//Update the current total preduction values while we do this
double lastFPred = lastF.regress(resids.getDataPoint(j));
currPredictions[j] += lastCoef*lastFPred;
//The next set of residuals could be computed from the previous,
//but its more stable to just take the total residuals fromt he
//source each time
resids.setTargetValue(j, dataSet.getTargetValue(j)-currPredictions[j]);
}
//Take a random sample
randSampleList.clear();
ListUtils.randomSample(backingResidsList, randSampleList, randSampleSize, rand);
final Regressor h = weakLearner.clone();
final RegressionDataSet tmpDataSet = RegressionDataSet.usingDPPList(randSampleList);
h.train(tmpDataSet, parallel);
double y = getMinimizingErrorConst( backingResidsList, h);
F.add(h);
coef.add(learningRate*y);
}
}
/**
* Finds the constant y such that the squared error of the
* Regressor h on the set of residuals backingResidsList
* is minimized.
* @param backingResidsList the DataPointPair list of residuals
* @param h the regressor that is having the error of its output minimized
* @return the constant y that minimizes the squared error of the regressor on the training set.
*/
private double getMinimizingErrorConst(final List> backingResidsList, final Regressor h)
{
//Find the coeficent that minimized the residual error by finding the zero of its derivative (local minima)
Function1D fhPrime = getDerivativeFunc(backingResidsList, h);
RootFinder rf = new Zeroin();
double y = rf.root(1e-4, 50, new double[]{-2.5, 2.5}, fhPrime);
return y;
}
/**
* Returns a function object that approximates the derivative of the squared
* error of the Regressor as a function of the constant factor multiplied on
* the Regressor's output.
*
* @param backingResidsList the DataPointPair list of residuals
* @param h the regressor that is having the error of its output minimized
* @return a Function object approximating the derivative of the squared error
*/
private Function1D getDerivativeFunc(final List> backingResidsList, final Regressor h)
{
final Function1D fhPrime = (double x) ->
{
double c1 = x;//c2=c1-eps
double eps = 1e-5;
double c1Pc2 = c1 * 2 - eps;//c1+c2 = c1+c1-eps
double result = 0;
/*
* Computing the estimate of the derivative directly, f'(x) approx = f(x)-f(x-eps)
*
* hEst is the output of the new regressor, target is the true residual target value
*
* So we have several
* (hEst_i c1 - target)^2 - (hEst_i c2 -target)^2 //4 muls, 3 subs
* Where c2 = c1-eps
* Which simplifies to
* (c1 - c2) hEst ((c1 + c2) hEst - 2 target)
* =
* eps hEst (c1Pc2 hEst - 2 target)//3 muls, 1 sub, 1 shift (mul by 2)
*
* because eps is on the outside and independent of each
* individual summation, we can move it out and do the eps
* multiplicatio ont he final result. Reducing us to
*
* 2 muls, 1 sub, 1 shift (mul by 2)
*
* per loop
*
* Which reduce computation, and allows us to get the result
* in one pass of the data
*/
for (DataPointPair dpp : backingResidsList)
{
double hEst = h.regress(dpp.getDataPoint());
double target = dpp.getPair();
result += hEst * (c1Pc2 * hEst - 2 * target);
}
return result * eps;
};
return fhPrime;
}
@Override
public boolean supportsWeightedData()
{
if(strongLearner != null)
return strongLearner.supportsWeightedData() && weakLearner.supportsWeightedData();
return weakLearner.supportsWeightedData();
}
@Override
public StochasticGradientBoosting clone()
{
StochasticGradientBoosting clone = new StochasticGradientBoosting(weakLearner.clone(), maxIterations, learningRate, trainingProportion);
if(F != null)
{
clone.F = new ArrayList<>(F.size());
for(Regressor f : this.F)
clone.F.add(f.clone());
}
if(coef != null)
{
clone.coef = new DoubleList(this.coef);
}
if(strongLearner != null)
clone.strongLearner = this.strongLearner.clone();
return clone;
}
}
Ads help maintain this website.