package jsat.classifiers.boosting;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.classifiers.trees.DecisionTree;
import jsat.distributions.Distribution;
import jsat.distributions.Uniform;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.FakeExecutor;
/**
* Emphasis Boost is a generalization of the Real AdaBoost algorithm, expanding
* the update term and providing the {@link #setLambda(double) λ } term
* to control the trade off. With λ = 1/2, it becomes equivalent to Real
* AdaBoost. If the weak learner does not support confidence outputs (non-hard
* decisions), then it further becomes equivalent to Discrete Ada Boost.
* Emphasis Boost only supports binary classification problems, the learner used
* should support weighted predictions.
*
* NOTE: In the face of extreme outliers, it is possible for numerical
* instability to occur. This implementation attempts to reset weights when
* numerical issues occur.
*
* See:
* Gómez-Verdejo, V., Ortega-Moral, M., Arenas-García, J.,&Figueiras-Vidal,
* A. R. (2006). Boosting by weighting critical and erroneous samples.
* Neurocomputing, 69(7-9), 679–685. doi:10.1016/j.neucom.2005.12.011
*
* @author Edward Raff
*/
public class EmphasisBoost implements Classifier, Parameterized, BinaryScoreClassifier
{
private static final long serialVersionUID = -6372897830449685891L;
@ParameterHolder
private Classifier weakLearner;
private int maxIterations;
/**
* The list of weak hypothesis
*/
protected List hypoths;
/**
* The weights for each weak learner
*/
protected List hypWeights;
protected CategoricalData predicting;
private double lambda;
/**
* Creates a new EmphasisBooster with shallow decision trees and λ = 0.35
*/
public EmphasisBoost()
{
this(new DecisionTree(6), 200, 0.35);
}
/**
* Creates a new EmphasisBoost learner
* @param weakLearner the weak learner to use
* @param maxIterations the maximum number of boosting iterations
* @param lambda the trade off parameter in [0, 1]
*/
public EmphasisBoost(Classifier weakLearner, int maxIterations, double lambda)
{
setWeakLearner(weakLearner);
setMaxIterations(maxIterations);
setLambda(lambda);
}
/**
* Copy constructor
* @param toClone the object to clone
*/
protected EmphasisBoost(EmphasisBoost toClone)
{
this(toClone.weakLearner.clone(), toClone.maxIterations, toClone.lambda);
if(toClone.hypWeights != null)
{
this.hypWeights = new DoubleList(toClone.hypWeights);
this.hypoths = new ArrayList(toClone.maxIterations);
for(Classifier weak : toClone.hypoths)
this.hypoths.add(weak.clone());
this.predicting = toClone.predicting.clone();
}
}
/**
*
* @return a list of the models that are in this ensemble.
*/
public List getModels()
{
return Collections.unmodifiableList(hypoths);
}
/**
*
* @return a list of the models weights that are in this ensemble.
*/
public List getModelWeights()
{
return Collections.unmodifiableList(hypWeights);
}
/**
* Returns the maximum number of iterations used
* @return the maximum number of iterations used
*/
public int getMaxIterations()
{
return maxIterations;
}
/**
* Sets the maximal number of boosting iterations that may be performed
* @param maxIterations the maximum number of iterations
*/
public void setMaxIterations(int maxIterations)
{
if(maxIterations < 1)
throw new IllegalArgumentException("Iterations must be positive, not " + maxIterations);
this.maxIterations = maxIterations;
}
/**
* Returns the weak learner currently being used by this method.
* @return the weak learner currently being used by this method.
*/
public Classifier getWeakLearner()
{
return weakLearner;
}
/**
* Sets the weak learner used during training.
* @param weakLearner the weak learner to use
*/
public void setWeakLearner(Classifier weakLearner)
{
if(!weakLearner.supportsWeightedData())
throw new IllegalArgumentException("WeakLearner must support weighted data to be boosted");
this.weakLearner = weakLearner;
}
/**
* Guesses the distribution to use for the λ parameter
*
* @param d the dataset to get the guess for
* @return the guess for the λ parameter
* @see #setLambda(double)
*/
public static Distribution guessLambda(DataSet d)
{
return new Uniform(0.25, 0.45);
}
/**
* λ controls the trade off between weighting the errors based on
* their distance to the margin and the quadratic error of the output. The
* three extreme values are:
*
* - λ = 0 , in this case all the weight is placed on points based
* on their distance to the margin of the classification boundary.
* - λ = 1/2, in this case weight is balanced between the margin
* distance and the quadratic error. This is equivalent to Real Ada Boost
*
* - λ = 1, in this case the weight is placed purely based on the
* quadratic error of the output
*
*
According to the original paper, values in the range [0.3, 0.4]
* often perform well.
*
* @param lambda the trade off parameter in [0, 1]
*/
public void setLambda(double lambda)
{
this.lambda = lambda;
}
/**
* Returns the value of the λ trade off parameter
* @return the value of the λ trade off parameter
*/
public double getLambda()
{
return lambda;
}
@Override
public double getScore(DataPoint dp)
{
double score = 0;
for(int i = 0; i < hypoths.size(); i++)
score += H(hypoths.get(i), dp)*hypWeights.get(i);
return score;
}
@Override
public CategoricalResults classify(DataPoint data)
{
if(predicting == null)
throw new RuntimeException("Classifier has not been trained yet");
CategoricalResults cr = new CategoricalResults(predicting.getNumOfCategories());
double score = getScore(data);
if(score < 0)
cr.setProb(0, 1.0);
else
cr.setProb(1, 1.0);
return cr;
}
private double H(Classifier weak, DataPoint dp )
{
CategoricalResults catResult = weak.classify(dp);
return catResult.getProb(1)*2-1;
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
predicting = dataSet.getPredicting();
hypWeights = new DoubleList(maxIterations);
hypoths = new ArrayList(maxIterations);
final int N = dataSet.getSampleSize();
List> dataPoints = dataSet.getTwiceShallowClone().getAsDPPList();
//Initialization step, set up the weights so they are all 1 / size of dataset
for(DataPointPair dpp : dataPoints)
dpp.getDataPoint().setWeight(1.0/N);//Scaled, they are all 1
double weightSum = 1;
//Keep track of the cumaltive score for everything
double[] H_cur = new double[N];
double[] curH_Result = new double[N];
for(int t = 0; t < maxIterations; t++)
{
Classifier weak = weakLearner.clone();
weak.train(new ClassificationDataSet(dataPoints, predicting), parallel);
double error = 0.0;
for(int i = 0; i < dataPoints.size(); i++)
{
DataPointPair dpp = dataPoints.get(i);
double y_hat = H_cur[i] = H(weak, dpp.getDataPoint());
double y_true = dpp.getPair()*2-1;//{-1 or 1}
error += dpp.getDataPoint().getWeight()*y_hat*y_true;
}
if(error < 0)
return;
double alpha_m = Math.log((1+error)/(1-error))/2;
weightSum = 0;
for(int i = 0; i < dataPoints.size(); i++)
{
curH_Result[i] += alpha_m * H_cur[i];
double f_t = curH_Result[i];
DataPointPair dpp = dataPoints.get(i);
DataPoint dp = dpp.getDataPoint();
double y_true = dpp.getPair()*2-1;
double w_i = Math.exp(lambda*Math.pow(f_t-y_true, 2) - (1-lambda)*f_t*f_t);
if(Double.isInfinite(w_i))
w_i = 50;//Let it grow back isntead of bizaro huge values
weightSum += w_i;
dp.setWeight(w_i);
}
for(int i = 0; i < dataPoints.size(); i++)
{
DataPointPair dpp = dataPoints.get(i);
DataPoint dp = dpp.getDataPoint();
dp.setWeight(dp.getWeight()/weightSum);
}
hypoths.add(weak);
hypWeights.add(alpha_m);
}
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public EmphasisBoost clone()
{
return new EmphasisBoost(this);
}
}
Ads help maintain this website.