package jsat.classifiers.linear;

import static java.lang.Math.*;
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.Vec;
import jsat.regression.RegressionDataSet;
import jsat.utils.random.RandomUtil;

/**
 * Implements the iterative and single threaded stochastic solver for 
 * L1 regularized linear regression problems SMIDAS (Stochastic 
 * Mirror Descent Algorithm mAde Sparse). It performs very well when the number 
 * of features is large relative to or greater than the number of data points. 
 * It also works decently on smaller 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] to preserve sparseness. 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 SMIDAS extends StochasticSTLinearL1 { private static final long serialVersionUID = -4888083541600164597L; private double eta; /** * Creates a new SMIDAS learner * @param eta the learning rate for each iteration */ public SMIDAS(double eta) { this(eta, DEFAULT_EPOCHS, DEFAULT_REG, DEFAULT_LOSS); } /** * Creates a new SMIDAS learner * @param eta the learning rate for each iteration * @param epochs the number of learning iterations * @param lambda the regularization penalty * @param loss the loss function to use */ public SMIDAS(double eta, int epochs, double lambda, Loss loss) { this(eta, epochs, lambda, loss, true); } /** * Creates a new SMIDAS learner * @param eta the learning rate for each iteration * @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 SMIDAS(double eta, int epochs, double lambda, Loss loss, boolean reScale) { setEta(eta); setEpochs(epochs); setLambda(lambda); setLoss(loss); setReScale(reScale); } /** * Sets the learning rate used during training * @param eta the learning rate to use */ public void setEta(double eta) { if(Double.isNaN(eta) || Double.isInfinite(eta) || eta <= 0) throw new ArithmeticException("convergence parameter must be a positive value"); this.eta = eta; } /** * Returns the current learning rate used during training * @return the learning rate in use */ public double getEta() { return eta; } @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)); } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(ClassificationDataSet dataSet) { if(dataSet.getNumNumericalVars() < 3) throw new FailedToFitException("SMIDAS requires at least 3 features"); else if(dataSet.getClassSize() != 2) throw new FailedToFitException("SMIDAS only supports binary classification problems"); Vec[] x = setUpVecs(dataSet); Vec obvMinV = DenseVector.toDenseVec(obvMin); Vec obvMaxV = DenseVector.toDenseVec(obvMax); Vec multitpliers = new DenseVector(obvMaxV.length()); multitpliers.mutableAdd(maxScaled-minScaled); multitpliers.mutablePairwiseDivide(obvMaxV.subtract(obvMinV)); boolean allZeroMins = true; for(double min : obvMin) if(min != 0) allZeroMins = false; double[] target = new double[x.length]; for(int i = 0; i < dataSet.getSampleSize(); i++) { //Copy and scale each value if(allZeroMins && minScaled == 0.0) { x[i].mutablePairwiseMultiply(multitpliers); } else//destroy all sparsity and our dreams { x[i] = x[i].subtract(obvMinV); x[i].mutablePairwiseMultiply(multitpliers); x[i].mutableAdd(minScaled); } target[i] = dataSet.getDataPointCategory(i)*2-1; } train(x, target); } @Override public void train(RegressionDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(RegressionDataSet dataSet) { if(dataSet.getNumNumericalVars() < 3) throw new FailedToFitException("SMIDAS requires at least 3 features"); Vec[] x = setUpVecs(dataSet); Vec obvMinV = DenseVector.toDenseVec(obvMin); Vec obvMaxV = DenseVector.toDenseVec(obvMax); Vec multitpliers = new DenseVector(obvMaxV.length()); multitpliers.mutableAdd(maxScaled-minScaled); multitpliers.mutablePairwiseDivide(obvMaxV.subtract(obvMinV)); boolean allZeroMins = true; for(double min : obvMin) if(min != 0) allZeroMins = false; double[] target = new double[x.length]; for(int i = 0; i < dataSet.getSampleSize(); i++) { if(allZeroMins && minScaled == 0.0) { x[i].mutablePairwiseMultiply(multitpliers); } else { //Copy and scale each value x[i] = x[i].subtract(obvMinV); x[i].mutablePairwiseMultiply(multitpliers); x[i].mutableAdd(minScaled); } target[i] = dataSet.getTargetValue(i); } train(x, target); } private void train(Vec[] x, double[] y) { final int m = x.length; final int d = x[0].length(); final double p = 2*Math.log(d); Vec theta = new DenseVector(d); double theta_bias = 0; double lossScore = 0; w = new DenseVector(d); Random rand = RandomUtil.getRandom(); for(int t = 0; t < epochs; t++) { int i = rand.nextInt(m); lossScore = loss.deriv(w.dot(x[i])+bias, y[i]); theta.mutableSubtract(eta*lossScore, x[i]); theta_bias -= eta*lossScore; for(IndexValue iv : theta) { int j = iv.getIndex(); double theta_j = iv.getValue();//theta.get(j); theta.set(j, signum(theta_j)*max(0, abs(theta_j)-eta*lambda)); } theta_bias = signum(theta_bias)*max(0, abs(theta_bias)-eta*lambda); final double thetaNorm = theta.pNorm(p); if(thetaNorm > 0) { //w = f^-1(theta) final double logThetaNorm = log(thetaNorm); for(int j = 0; j < w.length(); j++) { double theta_j = theta.get(j); w.set(j, signum(theta_j) * exp((p-1) * log(abs(theta_j)) - (p-2) * logThetaNorm)); } bias = signum(theta_bias)*exp((p-1) * log(abs(theta_bias)) - (p-2) * logThetaNorm); } else { theta.zeroOut(); theta_bias = 0; w.zeroOut(); bias = 0; } } } @Override public boolean supportsWeightedData() { return true; } @Override public SMIDAS clone() { SMIDAS clone = new SMIDAS(eta, 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; } private Vec[] setUpVecs(DataSet dataSet) { obvMin = new double[dataSet.getNumNumericalVars()]; Arrays.fill(obvMin, Double.POSITIVE_INFINITY); obvMax = new double[dataSet.getNumNumericalVars()]; Arrays.fill(obvMax, Double.NEGATIVE_INFINITY); Vec[] x = new Vec[dataSet.getSampleSize()]; for(int i = 0; i < dataSet.getSampleSize(); i++) { x[i] = dataSet.getDataPoint(i).getNumericalValues(); for(IndexValue iv : x[i]) { int j = iv.getIndex(); double v = iv.getValue(); obvMin[j] = Math.min(obvMin[j], v); obvMax[j] = Math.max(obvMax[j], v); } } if(x[0].isSparse())//Assume implicit min zeros from sparsity for(int i = 0; i < obvMin.length; i++) obvMin[i] = Math.min(obvMin[i], 0); if(!reScale) { for(double min : obvMin) if(min < -1) throw new FailedToFitException("Values must be in the range [-1,1], " + min + " violation encountered"); for(double max : obvMax) if(max > 1) throw new FailedToFitException("Values must be in the range [-1,1], " + max + " violation encountered"); } return x; } }

Ads help maintain this website.