package jsat.parameters;

import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.distributions.Distribution;
import jsat.exceptions.FailedToFitException;
import jsat.regression.*;
import jsat.utils.DoubleList;
import jsat.utils.FakeExecutor;
import jsat.utils.concurrent.ParallelUtils;

/**
 * GridSearch is a simple method for tuning the parameters of a classification 
 * or regression algorithm. It naively tries all possible pairs of parameter 
 * values given. For this reason, it works best when only a small number of 
 * parameters need to be turned. 
* The model it takes must implement the {@link Parameterized} interface. By * default, no parameters are selected for optimizations. This is because * parameters value ranges are often algorithm specific. As such, the user must * specify the parameters and the values to test using the addParameter * methods. * * @author Edward Raff * * @see #addParameter(jsat.parameters.DoubleParameter, double[]) * @see #addParameter(jsat.parameters.IntParameter, int[]) */ public class GridSearch extends ModelSearch { private static final long serialVersionUID = -1987196172499143753L; /** * The matching list of values we will test. This includes the integer * parameters, which will have to be cast back and forth from doubles. */ private List> searchValues; /** * Use warm starts when possible */ private boolean useWarmStarts = true; /** * Creates a new GridSearch to tune the specified parameters of a regression * model. The parameters still need to be specified by calling * {@link #addParameter(jsat.parameters.DoubleParameter, double[]) } * * @param baseRegressor the regressor to tune the parameters of * @param folds the number of folds of cross-validation to perform to * evaluate each combination of parameters * @throws FailedToFitException if the base regressor does not implement * {@link Parameterized} */ public GridSearch(Regressor baseRegressor, int folds) { super(baseRegressor, folds); searchValues = new ArrayList>(); } /** * Creates a new GridSearch to tune the specified parameters of a * classification model. The parameters still need to be specified by * calling * {@link #addParameter(jsat.parameters.DoubleParameter, double[]) } * * @param baseClassifier the classifier to tune the parameters of * @param folds the number of folds of cross-validation to perform to * evaluate each combination of parameters * @throws FailedToFitException if the base classifier does not implement * {@link Parameterized} */ public GridSearch(Classifier baseClassifier, int folds) { super(baseClassifier, folds); searchValues = new ArrayList>(); } /** * Copy constructor * @param toCopy the object to copy */ public GridSearch(GridSearch toCopy) { super(toCopy); this.useWarmStarts = toCopy.useWarmStarts; if(toCopy.searchValues != null) { this.searchValues = new ArrayList>(); for(List ld : toCopy.searchValues) { List newVals = new DoubleList(ld); this.searchValues.add(newVals); } } } /** * This method will automatically populate the search space with parameters * based on which Parameter objects return non-null distributions. Each * parameter will be tested with 10 different values
*
* Note, using this method with Cross Validation has the potential for * over-estimating the accuracy of results if the data set is actually used * to for parameter guessing.
*
* It is possible for this method to return 0, indicating that no default * parameters could be found. The intended interpretation is that there are * no parameters that you need to tune to get good performance from * the given model. Though there will be cases where the author has simply * missed a class. * * @param data the data set to get parameter estimates from * @return the number of parameters added */ public int autoAddParameters(DataSet data) { return autoAddParameters(data, 10); } /** * This method will automatically populate the search space with parameters * based on which Parameter objects return non-null distributions.
*
* Note, using this method with Cross Validation has the potential for * over-estimating the accuracy of results if the data set is actually used * to for parameter guessing. * * @param data the data set to get parameter estimates from * @param paramsEach the number of parameters value to try for each parameter found * @return the number of parameters added */ public int autoAddParameters(DataSet data, int paramsEach) { Parameterized obj; if(baseClassifier != null) obj = (Parameterized) baseClassifier; else obj = (Parameterized) baseRegressor; int totalParms = 0; for(Parameter param : obj.getParameters()) { Distribution dist; if (param instanceof DoubleParameter) { dist = ((DoubleParameter) param).getGuess(data); if (dist != null) totalParms++; } else if (param instanceof IntParameter) { dist = ((IntParameter) param).getGuess(data); if (dist != null) totalParms++; } } if(totalParms < 1) return 0; double[] quantiles = new double[paramsEach]; for(int i = 0; i < quantiles.length; i++) quantiles[i] = (i+1.0)/(paramsEach+1.0); for(Parameter param : obj.getParameters()) { Distribution dist; if (param instanceof DoubleParameter) { dist = ((DoubleParameter) param).getGuess(data); if (dist == null) continue; double[] vals = new double[paramsEach]; for (int i = 0; i < vals.length; i++) vals[i] = dist.invCdf(quantiles[i]); addParameter((DoubleParameter) param, vals); } else if (param instanceof IntParameter) { dist = ((IntParameter) param).getGuess(data); if (dist == null) continue; int[] vals = new int[paramsEach]; for (int i = 0; i < vals.length; i++) vals[i] = (int) Math.round(dist.invCdf(quantiles[i])); addParameter((IntParameter) param, vals); } } return totalParms; } /** * Sets whether or not warm starts are used, but only if the model in use * supports warm starts. This is set to {@code true} by default. * * @param useWarmStarts {@code true} if warm starts should be used when * possible, {@code false} otherwise. */ public void setUseWarmStarts(boolean useWarmStarts) { this.useWarmStarts = useWarmStarts; } /** * * @return {@code true} if warm starts will be used when possible. * {@code false} if they will not. */ public boolean isUseWarmStarts() { return useWarmStarts; } /** * Adds a new double parameter to be altered for the model being tuned. * * @param param the model parameter * @param initialSearchValues the values to try for the specified parameter */ public void addParameter(DoubleParameter param, double... initialSearchValues) { if(param == null) throw new IllegalArgumentException("null not allowed for parameter"); searchParams.add(param); DoubleList dl = new DoubleList(initialSearchValues.length); for(double d : initialSearchValues) dl.add(d); Arrays.sort(dl.getBackingArray());//convience, only really needed if param is warm if (param.isWarmParameter() && !param.preferredLowToHigh()) Collections.reverse(dl);//put it in the prefered order if (param.isWarmParameter())//put it at the front! searchValues.add(0, dl); else searchValues.add(dl); } /** * Adds a new double parameter to be altered for the model being tuned. * * @param name the name of the parameter * @param initialSearchValues the values to try for the specified parameter */ public void addParameter(String name, double... initialSearchValues) { Parameter param; param = getParameterByName(name); if (!(param instanceof DoubleParameter)) throw new IllegalArgumentException("Parameter " + name + " is not for double values"); addParameter((DoubleParameter) param, initialSearchValues); } /** * Adds a new int parameter to be altered for the model being tuned. * * @param param the model parameter * @param initialSearchValues the values to try for the specified parameter */ public void addParameter(IntParameter param, int... initialSearchValues) { searchParams.add(param); DoubleList dl = new DoubleList(initialSearchValues.length); for(double d : initialSearchValues) dl.add(d); Arrays.sort(dl.getBackingArray());//convience, only really needed if param is warm if (param.isWarmParameter() && !param.preferredLowToHigh()) Collections.reverse(dl);//put it in the prefered order if (param.isWarmParameter())//put it at the front! searchValues.add(0, dl); else searchValues.add(dl); } /** * Adds a new integer parameter to be altered for the model being tuned. * * @param name the name of the parameter * @param initialSearchValues the values to try for the specified parameter */ public void addParameter(String name, int... initialSearchValues) { Parameter param; param = getParameterByName(name); if (!(param instanceof IntParameter)) throw new IllegalArgumentException("Parameter " + name + " is not for int values"); addParameter((IntParameter) param, initialSearchValues); } @Override public void train(final RegressionDataSet dataSet, final boolean parallel) { final PriorityQueue bestModels = new PriorityQueue<>(folds, (RegressionModelEvaluation t, RegressionModelEvaluation t1) -> { double v0 = t.getScoreStats(regressionTargetScore).getMean(); double v1 = t1.getScoreStats(regressionTargetScore).getMean(); int order = regressionTargetScore.lowerIsBetter() ? 1 : -1; return order * Double.compare(v0, v1); }); /** * Use this to keep track of which parameter we are altering. Index * correspondence to the parameter, and its value corresponds to which * value has been used. Increment and carry counts to iterate over all * possible combinations. */ int[] setTo = new int[searchParams.size()]; /** * Each model is set to have different combination of parameters. We * then train each model to determine the best one. */ final List paramsToEval = new ArrayList(); while(true) { setParameters(setTo); paramsToEval.add(baseRegressor.clone()); if(incrementCombination(setTo)) break; } //if we are doing our CV splits ahead of time, get them done now final List preFolded; /** * Pre-combine our training combinations so that any caching can be * re-used */ final List trainCombinations; if (reuseSameCVFolds) { preFolded = dataSet.cvSet(folds); trainCombinations = new ArrayList<>(preFolded.size()); for (int i = 0; i < preFolded.size(); i++) trainCombinations.add(RegressionDataSet.comineAllBut(preFolded, i)); } else { preFolded = null; trainCombinations = null; } boolean considerWarm = useWarmStarts && baseRegressor instanceof WarmRegressor; /** * make sure we don't do a warm start if its only supported when trained * on the same data but we aren't reuse-ing the same CV splits So we get * the truth table * * a | b | (a&&b)||¬a * T | T | T * T | F | F * F | T | T * F | F | T * * where a = warmFromSameDataOnly and b = reuseSameSplit * So we can instead use * ¬ a || b */ if (considerWarm && (!((WarmRegressor) baseRegressor).warmFromSameDataOnly() || reuseSameCVFolds)) { /* we want all of the first parameter (which is the warm paramter, * taken care of for us) values done in a group. So We can get this * by just dividing up the larger list into sub lists, each sub list * is adjacent in the original and is the number of parameter values * we wanted to try */ ParallelUtils.run(parallel && trainModelsInParallel, paramsToEval.size(), (start, end)-> { final List subSet = paramsToEval.subList(start, end); Regressor[] prevModels = null; for (Regressor r : subSet) { RegressionModelEvaluation rme = new RegressionModelEvaluation(r, dataSet, !trainModelsInParallel && parallel); rme.setKeepModels(true);//we need these to do warm starts! rme.setWarmModels(prevModels); rme.addScorer(regressionTargetScore.clone()); if (reuseSameCVFolds) rme.evaluateCrossValidation(preFolded, trainCombinations); else rme.evaluateCrossValidation(folds); prevModels = rme.getKeptModels(); synchronized (bestModels) { bestModels.add(rme); } } }); } else//regular CV, train a new model from scratch at every step { ParallelUtils.run(parallel && trainModelsInParallel, paramsToEval.size(), (indx)-> { Regressor r = paramsToEval.get(indx); RegressionModelEvaluation rme = new RegressionModelEvaluation(r, dataSet, !trainModelsInParallel && parallel); rme.addScorer(regressionTargetScore.clone()); if (reuseSameCVFolds) rme.evaluateCrossValidation(preFolded, trainCombinations); else rme.evaluateCrossValidation(folds); synchronized (bestModels) { bestModels.add(rme); } }); } //Now we know the best classifier, we need to train one on the whole data set. Regressor bestRegressor = bestModels.peek().getRegressor();//Just re-train it on the whole set if (trainFinalModel) { //try and warm start the final model if we can if (useWarmStarts && bestRegressor instanceof WarmRegressor && !((WarmRegressor) bestRegressor).warmFromSameDataOnly())//last line here needed to make sure we can do this warm train { WarmRegressor wr = (WarmRegressor) bestRegressor; wr.train(dataSet, wr.clone(), parallel); } else { bestRegressor.train(dataSet, parallel); } } trainedRegressor = bestRegressor; } @Override public void train(final ClassificationDataSet dataSet, final boolean parallel) { final PriorityQueue bestModels = new PriorityQueue<>(folds, (ClassificationModelEvaluation t, ClassificationModelEvaluation t1) -> { double v0 = t.getScoreStats(classificationTargetScore).getMean(); double v1 = t1.getScoreStats(classificationTargetScore).getMean(); int order = classificationTargetScore.lowerIsBetter() ? 1 : -1; return order * Double.compare(v0, v1); }); /** * Use this to keep track of which parameter we are altering. Index * correspondence to the parameter, and its value corresponds to which * value has been used. Increment and carry counts to iterate over all * possible combinations. */ int[] setTo = new int[searchParams.size()]; /** * Each model is set to have different combination of parameters. We * then train each model to determine the best one. */ final List paramsToEval = new ArrayList(); while(true) { setParameters(setTo); paramsToEval.add(baseClassifier.clone()); if(incrementCombination(setTo)) break; } //if we are doing our CV splits ahead of time, get them done now final List preFolded; /** * Pre-combine our training combinations so that any caching can be * re-used */ final List trainCombinations; if (reuseSameCVFolds) { preFolded = dataSet.cvSet(folds); trainCombinations = new ArrayList<>(preFolded.size()); for (int i = 0; i < preFolded.size(); i++) trainCombinations.add(ClassificationDataSet.comineAllBut(preFolded, i)); } else { preFolded = null; trainCombinations = null; } boolean considerWarm = useWarmStarts && baseClassifier instanceof WarmClassifier; /** * make sure we don't do a warm start if its only supported when trained * on the same data but we aren't reuse-ing the same CV splits So we get * the truth table * * a | b | (a&&b)||¬a * T | T | T * T | F | F * F | T | T * F | F | T * * where a = warmFromSameDataOnly and b = reuseSameSplit * So we can instead use * ¬ a || b */ if (considerWarm && (!((WarmClassifier) baseClassifier).warmFromSameDataOnly() || reuseSameCVFolds)) { /* we want all of the first parameter (which is the warm paramter, * taken care of for us) values done in a group. So We can get this * by just dividing up the larger list into sub lists, each sub list * is adjacent in the original and is the number of parameter values * we wanted to try */ ParallelUtils.run(parallel && trainModelsInParallel, paramsToEval.size(), (start, end)-> { final List subSet = paramsToEval.subList(start, end); Classifier[] prevModels = null; for (Classifier r : subSet) { ClassificationModelEvaluation cme = new ClassificationModelEvaluation(r, dataSet, !trainModelsInParallel && parallel); cme.setKeepModels(true);//we need these to do warm starts! cme.setWarmModels(prevModels); cme.addScorer(classificationTargetScore.clone()); if (reuseSameCVFolds) cme.evaluateCrossValidation(preFolded, trainCombinations); else cme.evaluateCrossValidation(folds); prevModels = cme.getKeptModels(); synchronized (bestModels) { bestModels.add(cme); } } }); } else//regular CV, train a new model from scratch at every step { ParallelUtils.run(parallel && trainModelsInParallel, paramsToEval.size(), (int indx)-> { Classifier toTrain = paramsToEval.get(indx); ClassificationModelEvaluation cme = new ClassificationModelEvaluation(toTrain, dataSet, !trainModelsInParallel && parallel); cme.addScorer(classificationTargetScore.clone()); if (reuseSameCVFolds) cme.evaluateCrossValidation(preFolded, trainCombinations); else cme.evaluateCrossValidation(folds); synchronized (bestModels) { bestModels.add(cme); } }); } //Now we know the best classifier, we need to train one on the whole data set. Classifier bestClassifier = bestModels.peek().getClassifier();//Just re-train it on the whole set if (trainFinalModel) { //try and warm start the final model if we can if (useWarmStarts && bestClassifier instanceof WarmClassifier && !((WarmClassifier) bestClassifier).warmFromSameDataOnly())//last line here needed to make sure we can do this warm train { WarmClassifier wc = (WarmClassifier) bestClassifier; wc.train(dataSet, wc.clone(), parallel); } else { bestClassifier.train(dataSet, parallel); } } trainedClassifier = bestClassifier; } @Override public GridSearch clone() { return new GridSearch(this); } /** * This increments the array used to keep track of which combinations of * parameter values have been used. * @param setTo the array of length equal to {@link #searchParams} * indicating which parameters have already been tried * @return a boolean indicating true if all combinations have been * tried, or false if combinations remain to be attempted. */ private boolean incrementCombination(int[] setTo) { setTo[0]++; int carryPos = 0; while(carryPos < setTo.length-1 && setTo[carryPos] >= searchValues.get(carryPos).size()) { setTo[carryPos] = 0; setTo[++carryPos]++; } return setTo[setTo.length-1] >= searchValues.get(setTo.length-1).size(); } /** * Sets the parameters according to the given array * @param setTo the index corresponds to the parameters, and the value which * parameter value to use. */ private void setParameters(int[] setTo) { for(int i = 0; i < setTo.length; i++) { Parameter param = searchParams.get(i); if(param instanceof DoubleParameter) ((DoubleParameter)param).setValue(searchValues.get(i).get(setTo[i])); else if(param instanceof IntParameter) ((IntParameter)param).setValue(searchValues.get(i).get(setTo[i]).intValue()); } } }

Ads help maintain this website.