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.parameters.Parameterized;
import jsat.utils.DoubleList;
/**
* This is an implementation of the Multi-Class AdaBoost method SAMME (Stagewise Additive Modeling using
* a Multi-Class Exponential loss function), presented in Multi-class AdaBoost by Ji Zhu,
* Saharon Rosset, Hui Zou,&Trevor Hasstie
*
* This algorithm reduces to {@link AdaBoostM1 } for binary classification problems. Its often performs
* better for k class classification problems, and has a weaker requirement of besting 1/k
* accuracy for any k instead of 1/2.
*
* @author Edward Raff
*/
public class SAMME implements Classifier, Parameterized
{
private static final long serialVersionUID = -3584203799253810599L;
private Classifier weakLearner;
private int maxIterations;
/**
* The list of weak hypothesis
*/
private List hypoths;
/**
* The weights for each weak learner
*/
private List hypWeights;
private CategoricalData predicting;
public SAMME(Classifier weakLearner, int maxIterations)
{
if(!weakLearner.supportsWeightedData())
throw new RuntimeException("WeakLearner must support weighted data to be boosted");
this.weakLearner = weakLearner;
this.maxIterations = maxIterations;
}
@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;
}
/**
*
* @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);
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
predicting = dataSet.getPredicting();
hypWeights = new DoubleList(maxIterations);
hypoths = new ArrayList();
/**
* The number of classes we are predicting
*/
int K = predicting.getNumOfCategories();
double logK = Math.log(K-1.0)/Math.log(2);
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 sumOfWeights = 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);
//Error is the same as in AdaBoost.M1
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 /= sumOfWeights;
if(error >= (1.0-1.0/K) || error == 0.0)///Diference, we only need to be better then random guessing classes
return;
//The main difference - a different error term
double am = Math.log((1.0-error)/error)/Math.log(2) +logK;
//Update Distribution weights
for(int i = 0; i < wasCorrect.length; i++)
{
DataPoint dp = dataPoints.get(i).getDataPoint();
if(!wasCorrect[i])
{
double w = dp.getWeight();
double newW = w*Math.exp(am);
sumOfWeights += (newW-w);
dp.setWeight(newW);
}
}
hypoths.add(weakLearner.clone());
hypWeights.add(am);
}
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public SAMME clone()
{
SAMME clone = new SAMME(weakLearner.clone(), maxIterations);
if(this.hypWeights != null)
clone.hypWeights = new DoubleList(this.hypWeights);
if(this.hypoths != null)
{
clone.hypoths = new ArrayList(this.hypoths.size());
for(int i = 0; i < this.hypoths.size(); i++)
clone.hypoths.add(this.hypoths.get(i).clone());
}
if(this.predicting != null)
clone.predicting = this.predicting.clone();
return clone;
}
}
Ads help maintain this website.