package jsat.regression;

import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.SingleWeightVectorModel;
import jsat.classifiers.DataPoint;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.math.decayrates.DecayRate;
import jsat.math.decayrates.NoDecay;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.IntList;
import jsat.utils.ListUtils;

/**
 * A Stochastic implementation of Ridge Regression. Ridge 
 * Regression is equivalent to {@link MultipleLinearRegression} with an added 
 * L2 penalty for the weight vector. 

* This algorithm works best for problems with a large number of data points or * very high dimensional problems. * * @author Edward Raff */ public class StochasticRidgeRegression implements Regressor, Parameterized, SingleWeightVectorModel { private static final long serialVersionUID = -3462783438115627128L; private double lambda; private int epochs; private int batchSize; private double learningRate; private DecayRate learningDecay; private Vec w; private double bias; /** * Creates a new stochastic Ridge Regression learner that does not use a * decay rate * @param lambda the regularization term * @param epochs the number of training epochs to perform * @param batchSize the batch size for updates * @param learningRate the learning rate */ public StochasticRidgeRegression(double lambda, int epochs, int batchSize, double learningRate) { this(lambda, epochs, batchSize, learningRate, new NoDecay()); } /** * Creates a new stochastic Ridge Regression learner * @param lambda the regularization term * @param epochs the number of training epochs to perform * @param batchSize the batch size for updates * @param learningRate the learning rate * @param learningDecay the learning rate decay */ public StochasticRidgeRegression(double lambda, int epochs, int batchSize, double learningRate, DecayRate learningDecay) { setLambda(lambda); setEpochs(epochs); setBatchSize(batchSize); setLearningRate(learningRate); setLearningDecay(learningDecay); } /** * Sets the regularization parameter used. * @param lambda the positive regularization constant in (0, Inf) */ public void setLambda(double lambda) { if(Double.isNaN(lambda) || Double.isInfinite(lambda) || lambda <= 0) throw new IllegalArgumentException("lambda must be a positive constant, not " + lambda); this.lambda = lambda; } /** * Returns the regularization constant in use * @return the regularization constant in use */ public double getLambda() { return lambda; } /** * Sets the learning rate used, and should be in the range (0, 1). * * @param learningRate the learning rate to use */ public void setLearningRate(double learningRate) { this.learningRate = learningRate; } /** * Returns the learning rate in use. * @return the learning rate to use. */ public double getLearningRate() { return learningRate; } /** * Sets the learning rate decay function to use. The decay is applied after * each epoch through the data set. Using a decay rate can reduce the time * to converge and quality of the solution for difficult problems. * @param learningDecay the decay function to apply to the learning rate */ public void setLearningDecay(DecayRate learningDecay) { this.learningDecay = learningDecay; } /** * Returns the learning decay rate used * @return the learning decay rate used */ public DecayRate getLearningDecay() { return learningDecay; } /** * Sets the batch size to learn from. If larger than the training set, the * problem will reduce to classic gradient descent. * * @param batchSize the number of training points to use in each batch update */ public void setBatchSize(int batchSize) { if(batchSize <= 0) throw new IllegalArgumentException("Batch size must be a positive constant, not " + batchSize); this.batchSize = batchSize; } /** * Returns the batch size for updates * @return the batch size for updates */ public int getBatchSize() { return batchSize; } /** * Sets the number of iterations through the whole training set that will be * performed. * @param epochs the number of training iterations */ public void setEpochs(int epochs) { if(epochs <= 0) throw new IllegalArgumentException("At least one epoch must be performed, can not use " + epochs); this.epochs = epochs; } /** * Returns the number of training iterations * @return the number of training iterations */ public int getEpochs() { return epochs; } @Override public Vec getRawWeight() { return w; } @Override public double getBias() { return bias; } @Override public Vec getRawWeight(int index) { if(index < 1) return getRawWeight(); else throw new IndexOutOfBoundsException("Model has only 1 weight vector"); } @Override public double getBias(int index) { if (index < 1) return getBias(); else throw new IndexOutOfBoundsException("Model has only 1 weight vector"); } @Override public int numWeightsVecs() { return 1; } @Override public double regress(DataPoint data) { return regress(data.getNumericalValues()); } private double regress(Vec data) { return w.dot(data) + bias; } @Override public void train(RegressionDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(RegressionDataSet dataSet) { int batch = Math.min(batchSize, dataSet.getSampleSize()); w = new DenseVector(dataSet.getNumNumericalVars()); IntList sample = new IntList(dataSet.getSampleSize()); ListUtils.addRange(sample, 0, dataSet.getSampleSize(), 1); //Time and last time used to lazy update the parameters that do not get touched on a sparse update int time = 0; double[] errors = new double[batch]; final boolean sparseUpdates; { int sparse = 0; for (int i = 0; i < dataSet.getSampleSize(); i++) if(dataSet.getDataPoint(i).getNumericalValues().isSparse()) sparse++; if(sparse > dataSet.getSampleSize()/4) sparseUpdates = true; else sparseUpdates = false; } int[] lastTime = sparseUpdates ? new int[w.length()] : null; for(int epoch = 0; epoch < epochs; epoch++) { Collections.shuffle(sample); final double alpha = learningDecay.rate(epoch, epochs, learningRate)/batch; final double alphaReg = alpha*lambda; for(int i = 0; i < sample.size(); i+= batch) { if(i+batch >= sample.size()) continue;//skip, not enough in the batch time++; //get errors for(int b = i; b < i+batch; b++) errors[b-i] = regress(dataSet.getDataPoint(sample.get(i)))-dataSet.getTargetValue(sample.get(i)); //perform updates for(int b = i; b < i+batch; b++) { final double error = errors[b-i]; final double alphaError = alpha*error; //update bias bias -= alphaError; Vec x = dataSet.getDataPoint(sample.get(i)).getNumericalValues(); if(sparseUpdates) { for(IndexValue iv : x) { int idx = iv.getIndex(); if(lastTime[idx] != time)//update the theta for all missed updates { double theta_idx = w.get(idx); w.set(idx, theta_idx*Math.pow(1-alphaReg, time-lastTime[idx])); lastTime[idx] = time; } //now accumlate errors w.increment(idx, -alphaError*iv.getValue()); } } else//dense updates, no need to track last time we updated weight values { if(b == i)//update on first access w.mutableMultiply(1-alphaReg); //add error w.mutableSubtract(alphaError, x); } } } /* * if sparse, accumulate missing weight updates due to * regularization. If the learning rate changes, the weights must be * updated at the end of every epoch. If the learing rate is * constant, we only have to update on the last epoch */ if (sparseUpdates && ( !(learningDecay instanceof NoDecay) || (epoch == epochs-1) )) { for (int idx = 0; idx < w.length(); idx++) { if (lastTime[idx] != time)//update the theta for all missed updates { double theta_idx = w.get(idx); w.set(idx, theta_idx * Math.pow(1 - alphaReg, time - lastTime[idx])); lastTime[idx] = time; } } } } } @Override public boolean supportsWeightedData() { return false; } @Override public StochasticRidgeRegression clone() { StochasticRidgeRegression clone = new StochasticRidgeRegression(lambda, epochs, batchSize, learningRate, learningDecay); if(this.w != null) clone.w = this.w.clone(); clone.bias = this.bias; return clone; } }

Ads help maintain this website.