package jsat.classifiers.boosting;

import java.util.*;
import jsat.classifiers.*;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;

/**
 * Modest Ada Boost is a generalization of Discrete Ada Boost that attempts to 
 * reduce the generalization error and avoid over-fitting. Empirically, 
 * ModestBoost usually maintains a higher training-set error, and may take more
 * iterations to obtain the same test set error as other algorithms, but doesn't
 * not increase as much after it reaches the minimum error - which should make 
 * it easier to obtain the higher accuracy.
 * 
* See:
* Vezhnevets, A.,&Vezhnevets, V. (2005). “Modest AdaBoost” – Teaching * AdaBoost to Generalize Better. GraphiCon. Novosibirsk Akademgorodok, * Russia. Retrieved from * * here * * @author Edward Raff */ public class ModestAdaBoost implements Classifier, Parameterized, BinaryScoreClassifier { private static final long serialVersionUID = 8223388561185098909L; 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; /** * Creates a new ModestBoost learner * @param weakLearner the weak learner to use * @param maxIterations the maximum number of boosting iterations */ public ModestAdaBoost(Classifier weakLearner, int maxIterations) { setWeakLearner(weakLearner); setMaxIterations(maxIterations); } /** * Copy constructor * @param toClone the object to clone */ protected ModestAdaBoost(ModestAdaBoost toClone) { this(toClone.weakLearner.clone(), toClone.maxIterations); 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; } @Override public double getScore(DataPoint dp) { double score = 0; for(int i = 0; i < hypoths.size(); i++) score += (hypoths.get(i).classify(dp).getProb(1)*2-1)*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; } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { predicting = dataSet.getPredicting(); hypWeights = new DoubleList(maxIterations); hypoths = new ArrayList(maxIterations); final int N = dataSet.getSampleSize(); double[] D_inv = new double[N]; double[] D = new double[N]; List> dataPoints = dataSet.getTwiceShallowClone().getAsDPPList(); Arrays.fill(D, 1.0/N); for(DataPointPair dpp : dataPoints) dpp.getDataPoint().setWeight(D[0]);//Scaled, they are all 1 double weightSum = 1; double[] H_cur = new double[N]; for(int t = 0; t < maxIterations; t++) { Classifier weak = weakLearner.clone(); weak.train(new ClassificationDataSet(dataPoints, predicting), parallel); double invSum = 0; for(int i = 0; i < N; i++) invSum += (D_inv[i] = 1-D[i]); for(int i = 0; i < N; i++) D_inv[i] /= invSum; double p_d = 0, p_id = 0, n_d = 0, n_id = 0; for(int i = 0; i < N; i++) { DataPointPair dpp = dataPoints.get(i); H_cur[i] = (weak.classify(dpp.getDataPoint()).getProb(1)*2-1); double outPut = Math.signum(H_cur[i]); int c = dpp.getPair(); if(c == 1)//positive example case { p_d += outPut * D[i]; p_id += outPut * D_inv[i]; } else { n_d += outPut * D[i]; n_id += outPut * D_inv[i]; } } double alpha_m = p_d * (1 - p_id) - n_d * (1 - n_id); if(Math.signum(alpha_m) != Math.signum(p_d-n_d) || Math.abs((p_d - n_d)) < 1e-6 || alpha_m <= 0) return; weightSum = 0; for(int i = 0; i < N; i++) { DataPoint dp = dataPoints.get(i).getDataPoint(); double w_i = dp.getWeight(); int y_i = dataPoints.get(i).getPair()*2-1; w_i *= Math.exp(-y_i*alpha_m*H_cur[i]); if(Double.isInfinite(w_i)) w_i = 1;//Let it grow back else if(w_i <= 0) w_i = 1e-3/N;//Dont let it go quit to zero weightSum += w_i; dp.setWeight(w_i); } for(int i = 0; i < N; i++) { DataPoint dp = dataPoints.get(i).getDataPoint(); double w_i = dp.getWeight(); dp.setWeight(Math.max(w_i/weightSum, 1e-10));//no zeros allowed } hypWeights.add(alpha_m); hypoths.add(weak); } } @Override public boolean supportsWeightedData() { return false; } @Override public ModestAdaBoost clone() { return new ModestAdaBoost(this); } }

Ads help maintain this website.