package jsat.classifiers.linear;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.SparseVector;
import jsat.linear.Vec;
import jsat.regression.RegressionDataSet;
import jsat.utils.random.RandomUtil;

/**
 * Implements an iterative and single threaded form of fast 
 * Stochastic Coordinate Decent for optimizing L1 regularized
 * linear regression problems. It performs very well when the number of data 
 * points is very large, especially when the feature count is smaller in 
 * comparison. It also works well on sparse data sets. 
* Using the squared loss is equivalent to LASSO regression, and the LOG loss * is equivalent to logistic regression.
*
* Note: This implementation requires all feature values to be in the range * [-1, 1]. By default scaling is performed to [0,1]. If your data is dense or * has negative and positive feature values, scaling to [-1, 1] may perform * better. * See {@link #setReScale(boolean) }
*
* See:
* Shalev-Shwartz, * S.,&Tewari, A. (2009). Stochastic Methods for L1-regularized * Loss Minimization. 26th International Conference on Machine Learning * (Vol. 12, pp. 929–936). * * @author Edward Raff */ public class LinearL1SCD extends StochasticSTLinearL1 { private static final long serialVersionUID = 3135562347568407186L; /** * Creates a new SCD L1 learner using default settings. */ public LinearL1SCD() { this(DEFAULT_EPOCHS, DEFAULT_REG, DEFAULT_LOSS); } /** * Creates a new SCD L1 learner. * @param epochs the number of learning iterations * @param lambda the regularization penalty * @param loss the loss function to use */ public LinearL1SCD(int epochs, double lambda, Loss loss) { this(epochs, lambda, loss, true); } /** * Creates a new SCD L1 learner. * @param epochs the number of learning iterations * @param lambda the regularization penalty * @param loss the loss function to use * @param reScale whether or not to rescale the feature values */ public LinearL1SCD(int epochs, double lambda, Loss loss, boolean reScale) { setEpochs(epochs); setLambda(lambda); setLoss(loss); setReScale(reScale); } @Override public CategoricalResults classify(DataPoint data) { if(w == null) throw new UntrainedModelException("Model has not been trained"); Vec x = data.getNumericalValues(); return loss.classify(wDot(x)); } @Override public double regress(DataPoint data) { if(w == null) throw new UntrainedModelException("Model has not been trained"); Vec x = data.getNumericalValues(); return loss.regress(wDot(x)); } /** * Performs rescaling as requested or throws an exception if a violation was * encountered * @param featureVals the array of feature values * @param m the number of data points * @throws FailedToFitException */ private void featureScaleCheck(Vec[] featureVals, int m) throws FailedToFitException { if(reScale) for(int j = 0; j < featureVals.length; j++) { if(obvMin[j] == 0 && minScaled == 0)//We can skip 1st and last step { featureVals[j].mutableMultiply(maxScaled/obvMax[j]); } else//do all steps { featureVals[j].mutableSubtract(obvMin[j]); featureVals[j].mutableMultiply((maxScaled-minScaled)/(obvMax[j]-obvMin[j])); featureVals[j].mutableAdd(minScaled); } //If we are not sparse enough after re-scaling, transform back if(featureVals[j].isSparse() && featureVals[j].nnz() > m*0.75) featureVals[j] = new DenseVector(featureVals[j]); } else //Check for violations for(int j = 0; j < obvMin.length; j++) if(obvMax[j] > 1 || obvMin[j] < -1) throw new FailedToFitException("All feature values must be in the range [-1,1]"); } private void setUpFeatureVals(Vec[] featureVals, boolean sparse, int m, DataSet dataSet) { //All feature values need to be scaled into -1, 1 obvMin = new double[featureVals.length]; Arrays.fill(obvMin, Double.POSITIVE_INFINITY); obvMax = new double[featureVals.length]; Arrays.fill(obvMax, Double.NEGATIVE_INFINITY); for(int i = 0; i < featureVals.length; i++) featureVals[i] = sparse ? new SparseVector(m) : new DenseVector(m); if(sparse) Arrays.fill(obvMin, 0.0); for(int i = 0; i < dataSet.getSampleSize(); i++) { Vec x = dataSet.getDataPoint(i).getNumericalValues(); for(IndexValue iv : x) { int j = iv.getIndex(); double v = iv.getValue(); featureVals[j].set(i, v); obvMax[j] = Math.max(obvMax[j], v); obvMin[j] = Math.min(obvMin[j], v); } } } @Override public void train(RegressionDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(RegressionDataSet dataSet) { boolean sparse = dataSet.getDataPoint(0).getNumericalValues().isSparse(); int m = dataSet.getSampleSize(); Vec[] featureVals = new Vec[dataSet.getNumNumericalVars()]; for(int i = 0; i < featureVals.length; i++) featureVals[i] = sparse ? new SparseVector(m) : new DenseVector(m); setUpFeatureVals(featureVals, sparse, m, dataSet); featureScaleCheck(featureVals, m); double[] target = new double[m]; for(int i = 0; i < dataSet.getSampleSize(); i++) target[i] = dataSet.getTargetValue(i); train(featureVals, target); } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(ClassificationDataSet dataSet) { if(dataSet.getClassSize() != 2) throw new FailedToFitException("Only binary classification problems are supported"); boolean sparse = dataSet.getDataPoint(0).getNumericalValues().isSparse(); int m = dataSet.getSampleSize(); Vec[] featureVals = new Vec[dataSet.getNumNumericalVars()]; setUpFeatureVals(featureVals, sparse, m, dataSet); featureScaleCheck(featureVals, m); double[] target = new double[m]; for(int i = 0; i < dataSet.getSampleSize(); i++) target[i] = dataSet.getDataPointCategory(i)*2-1; train(featureVals, target); } /** * * @param featureVals a vector for each feature, where each vector contains all values for the feature in dataset order * @param target target values */ private void train(Vec[] featureVals, double[] target) { final int d = featureVals.length; final int m = target.length; w = new DenseVector(d); final double[] z = new double[m]; final double beta = loss.beta(); Random rand = RandomUtil.getRandom(); for (int t = 1; t <= epochs; t++) { int j = rand.nextInt(d + 1);//+1 for the bias term double g = 0.0; if (j < d) { Vec xj = featureVals[j]; for (IndexValue iv : xj) { int i = iv.getIndex(); g += loss.deriv(z[i], target[i]) * iv.getValue(); } } else//Bias term update, all x[i]_j = 1 { for (int i = 0; i < target.length; i++) g += loss.deriv(z[i], target[i]); } g /= m; double eta; double w_j = j == d ? bias : w.get(j); if (w_j - g / beta > lambda / beta) eta = -g / beta - lambda / beta; else if (w_j - g / beta < -lambda / beta) eta = -g / beta + lambda / beta; else eta = -w_j; if (j < d) w.increment(j, eta); else bias += eta; if (j < d) for (IndexValue iv : featureVals[j]) z[iv.getIndex()] += eta * iv.getValue(); else//Bias update, all x[i]_j = 1 for (int i = 0; i < target.length; i++) z[i] += eta; } } @Override public boolean supportsWeightedData() { return false; } @Override public LinearL1SCD clone() { LinearL1SCD clone = new LinearL1SCD(epochs, lambda, loss, reScale); if(this.w != null) clone.w = this.w.clone(); clone.bias = this.bias; clone.minScaled = this.minScaled; clone.maxScaled = this.maxScaled; if(this.obvMin != null) clone.obvMin = Arrays.copyOf(this.obvMin, this.obvMin.length); if(this.obvMax != null) clone.obvMax = Arrays.copyOf(this.obvMax, this.obvMax.length); return clone; } }

Ads help maintain this website.