package jsat.classifiers.boosting;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.classifiers.OneVSAll;
import jsat.exceptions.FailedToFitException;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
/**
* Implementation of Experiments with a New Boosting Algorithm, by Yoav Freund&Robert E. Schapire.
*
* This is the first AdaBoost algorithm presented in the paper, and the first boosting algorithm.
* Though not often mentioned, AdaBoost does support non binary classification tasks. However,
* for any k labels, the weak learner's error still needs to be better then 1/2, which
* is not an easy requirement to satisfy. For this reason, many use AdaBoostM1 by reducing
* k class classification problems to several 2 class problems.
*
* Many Boosting methods, when given a binary classification task, reduce to having the same results as this class.
*
* AdaBoost is often combined with {@link OneVSAll} to obtain better classification accuracy.
*
*
* @author Edward Raff
*/
public class AdaBoostM1 implements Classifier, Parameterized
{
private static final long serialVersionUID = 4205232097748332861L;
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;
public AdaBoostM1(Classifier weakLearner, int maxIterations)
{
setWeakLearner(weakLearner);
this.maxIterations = maxIterations;
}
public AdaBoostM1(AdaBoostM1 toCopy)
{
this(toCopy.weakLearner.clone(), toCopy.maxIterations);
if(toCopy.hypWeights != null)
this.hypWeights = new DoubleList(toCopy.hypWeights);
if(toCopy.hypoths != null)
{
this.hypoths = new ArrayList<>(toCopy.hypoths.size());
for(int i = 0; i < toCopy.hypoths.size(); i++)
this.hypoths.add(toCopy.hypoths.get(i).clone());
}
if(toCopy.predicting != null)
this.predicting = toCopy.predicting.clone();
}
/**
* Returns the maximum number of iterations used
* @return the maximum number of iterations used
*/
public int getMaxIterations()
{
return maxIterations;
}
/**
*
* @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);
}
/**
* 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("Number of iterations must be a positive value, no " + 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 FailedToFitException("WeakLearner must support weighted data to be boosted");
this.weakLearner = weakLearner;
}
@Override
public CategoricalResults classify(DataPoint data)
{
if(predicting == null)
throw new RuntimeException("Classifier has not been trained yet");
CategoricalResults cr = new CategoricalResults(predicting.getNumOfCategories());
for(int i=0; i < hypoths.size(); i++)
cr.incProb(hypoths.get(i).classify(data).mostLikely(), hypWeights.get(i));
cr.normalize();
return cr;
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
/*
* Implementation note: We want all weights to be >= 1, so we will scale all weight values by the smallest weight value
*/
predicting = dataSet.getPredicting();
hypWeights = new DoubleList(maxIterations);
hypoths = new ArrayList<>(maxIterations);
List> dataPoints = dataSet.getAsDPPList();
//Initialization step, set up the weights so they are all 1 / size of dataset
for(DataPointPair dpp : dataPoints)
dpp.getDataPoint().setWeight(1.0);//Scaled, they are all 1
double scaledBy = dataPoints.size();
//Rather then reclasify points, we just save this list
boolean[] wasCorrect = new boolean[dataPoints.size()];
for(int t = 0; t < maxIterations; t++)
{
weakLearner.train(new ClassificationDataSet(dataPoints, predicting), parallel);
double error = 0.0;
for(int i = 0; i < dataPoints.size(); i++)
if( !(wasCorrect[i] = weakLearner.classify(dataPoints.get(i).getDataPoint()).mostLikely() == dataPoints.get(i).getPair()) )
error += dataPoints.get(i).getDataPoint().getWeight();
error /= scaledBy;
if(error > 0.5 || error == 0.0)
return;
double bt = error /( 1.0 - error );
//Update Distribution weights
double Zt = 0.0;
double newScale = scaledBy;//Not scaled
for(int i = 0; i < wasCorrect.length; i++)
{
DataPoint dp = dataPoints.get(i).getDataPoint();
if(wasCorrect[i])//Put less weight on the points we got correct
{
double w = dp.getWeight()*bt;
dp.setWeight(w);
}
double trueWeight = dp.getWeight()/scaledBy;
if(1.0/trueWeight > newScale)
newScale = 1.0/trueWeight;
Zt += dp.getWeight()/scaledBy;//Sum the values
}
for(DataPointPair dpp : dataPoints)//Normalize so the weights make a distribution
dpp.getDataPoint().setWeight(dpp.getDataPoint().getWeight()/scaledBy*newScale/Zt);
scaledBy = newScale;
hypoths.add(weakLearner.clone());
hypWeights.add(Math.log(1/bt));
}
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public AdaBoostM1 clone()
{
return new AdaBoostM1(this);
}
}
Ads help maintain this website.