package jsat.classifiers.linear;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.SingleWeightVectorModel;
import jsat.classifiers.*;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.lossfunctions.*;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;
/**
* Implementation of Stochastic Coordinate Descent for L1 regularized
* classification and regression. Which one is supported is controlled by the
* {@link LossFunc} used. To be used the loss function must be twice
* differentiable with a finite maximal second derivative value.
* {@link LogisticLoss} for classification and {@link SquaredLoss} for
* regression are the ones used in the original paper.
*
* Because the SCD needs column major data for efficient implementation, a
* second copy of data will be created in memory during training.
*
* See: Shalev-Shwartz, S.,&Tewari, A. (2009). Stochastic Methods for
* L1-regularized Loss Minimization. In 26th International
* Conference on Machine Learning (Vol. 12, pp. 929–936). Retrieved from
* here
*
* @author Edward Raff
*/
public class SCD implements Classifier, Regressor, Parameterized, SingleWeightVectorModel
{
private static final long serialVersionUID = 3576901723216525618L;
private Vec w;
private LossFunc loss;
private double reg;
private int iterations;
/**
* Creates anew SCD learner
*
* @param loss the loss function to use
* @param regularization the regularization term to used
* @param iterations the number of iterations to perform
*/
public SCD(LossFunc loss, double regularization, int iterations)
{
double beta = loss.getDeriv2Max();
if (Double.isNaN(beta) || Double.isInfinite(beta) || beta <= 0)
throw new IllegalArgumentException("SCD needs a loss function with a finite positive maximal second derivative");
this.loss = loss;
setRegularization(regularization);
setIterations(iterations);
}
/**
* Copy constructor
*
* @param toCopy the object to copy
*/
public SCD(SCD toCopy)
{
this(toCopy.loss.clone(), toCopy.reg, toCopy.iterations);
if (toCopy.w != null)
this.w = toCopy.w.clone();
}
/**
* Sets the number of iterations that will be used.
*
* @param iterations the number of training iterations
*/
public void setIterations(int iterations)
{
if(iterations < 1)
throw new IllegalArgumentException("The iterations must be a positive value, not " + iterations);
this.iterations = iterations;
}
/**
* Returns the number of iterations used
*
* @return the number of iterations used
*/
public int getIterations()
{
return iterations;
}
/**
* Sets the regularization constant used for learning. The regularization
* must be positive, and the learning rate is proportional to the
* regularization value. This means regularizations very near zero will take
* a long time to converge.
*
* @param regularization the regularization to apply in (0, Infinity)
*/
public void setRegularization(double regularization)
{
if (Double.isInfinite(regularization) || Double.isNaN(regularization) || regularization <= 0)
throw new IllegalArgumentException("Regularization must be a positive value");
this.reg = regularization;
}
/**
* Returns the regularization parameter value used for learning.
*
* @return the regularization parameter value used for learning.
*/
public double getRegularization()
{
return reg;
}
@Override
public Vec getRawWeight()
{
return w;
}
@Override
public double getBias()
{
return 0;
}
@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 CategoricalResults classify(DataPoint data)
{
if (w != null && loss instanceof LossC)
return ((LossC) loss).getClassification(w.dot(data.getNumericalValues()));
else
throw new UntrainedModelException("Model was not trained with a classification function");
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(ClassificationDataSet dataSet)
{
double[] targets = new double[dataSet.getSampleSize()];
for (int i = 0; i < targets.length; i++)
targets[i] = dataSet.getDataPointCategory(i) * 2 - 1;
train(dataSet.getNumericColumns(), targets);
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public double regress(DataPoint data)
{
if (w != null && loss instanceof LossR)
return ((LossR) loss).getRegression(w.dot(data.getNumericalValues()));
else
throw new UntrainedModelException("Model was not trained with a classification function");
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(RegressionDataSet dataSet)
{
train(dataSet.getNumericColumns(), dataSet.getTargetValues().arrayCopy());
}
/**
*
* @param columns columns of the training matrix
* @param y the target values
*/
private void train(Vec[] columns, double[] y)
{
final double beta = loss.getDeriv2Max();
double[] z = new double[y.length];///stores w.dot(x)
w = new DenseVector(columns.length);
Random rand = RandomUtil.getRandom();
for (int iter = 0; iter < iterations; iter++)
{
final int j = rand.nextInt(columns.length);
double g = 0;
for (IndexValue iv : columns[j])
g += loss.getDeriv(z[iv.getIndex()], y[iv.getIndex()]) * iv.getValue();
g /= y.length;
final double w_j = w.get(j);
final double eta;
if (w_j - g / beta > reg / beta)
eta = -g / beta - reg / beta;
else if (w_j - g / beta < -reg / beta)
eta = -g / beta + reg / beta;
else
eta = -w_j;
w.increment(j, eta);
for (IndexValue iv : columns[j])
z[iv.getIndex()] += eta * iv.getValue();
}
}
@Override
public SCD clone()
{
return new SCD(this);
}
}
Ads help maintain this website.