package jsat.classifiers.linear;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.SingleWeightVectorModel;
import jsat.classifiers.*;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.regression.BaseUpdateableRegressor;
import jsat.regression.RegressionDataSet;
import jsat.regression.UpdateableRegressor;
/**
* This provides an implementation of Sparse Truncated Gradient Descent for
* L1 regularized linear classification and regression on sparse data
* sets.
*
* Unlike normal L1 regression, regularization is controlled by the
* {@link #setGravity(double) gravity} parameter, but other parameters
* contribute to the level of sparsity.
*
* See: Langford, J., Li, L.,&Zhang, T. (2009). Sparse online learning via
* truncated gradient. The Journal of Machine Learning Research, 10,
* 777–801. Retrieved from
* here
* @author Edward Raff
*/
public class STGD extends BaseUpdateableClassifier implements UpdateableRegressor, BinaryScoreClassifier, Parameterized, SingleWeightVectorModel
{
private static final long serialVersionUID = 5753298014967370769L;
private Vec w;
private int K;
private double learningRate;
private double threshold;
private double gravity;
private int time;
private int[] t;
/**
* Creates a new STGD learner
* @param K the regularization frequency
* @param learningRate the learning rate to use
* @param threshold the regularization threshold
* @param gravity the regularization parameter
*/
public STGD(int K, double learningRate, double threshold, double gravity)
{
setK(K);
setLearningRate(learningRate);
setThreshold(threshold);
setGravity(gravity);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
protected STGD(STGD toCopy)
{
if(toCopy.w != null)
this.w = toCopy.w.clone();
this.K = toCopy.K;
this.learningRate = toCopy.learningRate;
this.threshold = toCopy.threshold;
this.gravity = toCopy.gravity;
this.time = toCopy.time;
if(toCopy.t != null)
this.t = Arrays.copyOf(toCopy.t, toCopy.t.length);
}
/**
* Sets the frequency of applying the {@link #setGravity(double) gravity}
* parameter to the weight vector. This value must be positive, and the
* gravity will be applied every K updates. Increasing this value
* encourages greater sparsity.
*
* @param K the frequency to apply regularization in [1, Infinity )
*/
public void setK(int K)
{
if(K < 1)
throw new IllegalArgumentException("K must be positive, not " + K);
this.K = K;
}
/**
* Returns the frequency of regularization application
* @return the frequency of regularization application
*/
public int getK()
{
return K;
}
/**
* Sets the learning rate to use
* @param learningRate the learning rate > 0.
*/
public void setLearningRate(double learningRate)
{
if(Double.isInfinite(learningRate) || Double.isNaN(learningRate) || learningRate <= 0)
throw new IllegalArgumentException("Learning rate must be positive, not " + learningRate);
this.learningRate = learningRate;
}
/**
* Returns the learning rate to use
* @return the learning rate to use
*/
public double getLearningRate()
{
return learningRate;
}
/**
* Sets the threshold for a coefficient value to avoid regularization. While
* a coefficient reaches this magnitude, regularization will not be applied.
* @param threshold the coefficient regularization threshold in
* ( 0, Infinity ]
*/
public void setThreshold(double threshold)
{
if(Double.isNaN(threshold) || threshold <= 0)
throw new IllegalArgumentException("Threshold must be positive, not " + threshold);
this.threshold = threshold;
}
/**
* Returns the coefficient threshold parameter
* @return the coefficient threshold parameter
*/
public double getThreshold()
{
return threshold;
}
/**
* Sets the gravity regularization parameter that "weighs down" the
* coefficient values. Larger gravity values impose stronger regularization,
* and encourage greater sparsity.
*
* @param gravity the regularization parameter in ( 0, Infinity )
*/
public void setGravity(double gravity)
{
if(Double.isInfinite(gravity) || Double.isNaN(gravity) || gravity <= 0)
throw new IllegalArgumentException("Gravity must be positive, not " + gravity);
this.gravity = gravity;
}
/**
* Returns the regularization parameter
* @return the regularization parameter
*/
public double getGravity()
{
return gravity;
}
@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 STGD clone()
{
return new STGD(this);
}
@Override
public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting)
{
if(predicting.getNumOfCategories() != 2)
throw new FailedToFitException("STGD supports only binary classification");
setUp(categoricalAttributes, numericAttributes);
}
@Override
public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes)
{
if(numericAttributes < 1)
throw new FailedToFitException("STGD requires numeric features");
w = new DenseVector(numericAttributes);
t = new int[numericAttributes];
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(RegressionDataSet dataSet)
{
BaseUpdateableRegressor.trainEpochs(dataSet, this, getEpochs());
}
private static double T(double v_j, double a, double theta)
{
if(v_j >= 0 && v_j <= theta)
return Math.max(0, v_j-a);
else if(v_j <= 0 && v_j >= -theta)
return Math.min(0, v_j+a);
else
return v_j;
}
@Override
public void update(DataPoint dataPoint, int targetClass)
{
time++;
final Vec x = dataPoint.getNumericalValues();
final int y = targetClass*2-1;
final int yHat = (int) Math.signum(w.dot(x));
if(yHat == y)//Not part of the described algorithm (using signum), but needed
return;
performUpdate(x, y, yHat);
}
@Override
public void update(DataPoint dataPoint, final double y)
{
time++;
final Vec x = dataPoint.getNumericalValues();
final double yHat = w.dot(x);
performUpdate(x, y, yHat);
}
/**
* Performs the sparse update of the weight vector
* @param x the input vector
* @param y the true value
* @param yHat the predicted value
*/
private void performUpdate(final Vec x, final double y, final double yHat)
{
for(IndexValue iv : x)
{
final int j = iv.getIndex();
w.set(j,
T(w.get(j)+2*learningRate*(y-yHat)*iv.getValue(),
((time-t[j])/K)*gravity*learningRate,
threshold));
t[j] += ((time-t[j])/K)*K;
}
}
@Override
public CategoricalResults classify(DataPoint data)
{
CategoricalResults cr = new CategoricalResults(2);
if(getScore(data) > 0)
cr.setProb(1, 1.0);
else
cr.setProb(0, 1.0);
return cr;
}
@Override
public double regress(DataPoint data)
{
return getScore(data);
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public double getScore(DataPoint dp)
{
return w.dot(dp.getNumericalValues());
}
}
Ads help maintain this website.