package jsat.classifiers.linear.kernelized;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.BaseUpdateableClassifier;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.classifiers.UpdateableClassifier;
import jsat.classifiers.linear.LinearSGD;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.distributions.kernels.KernelPoint;
import jsat.distributions.kernels.KernelPoints;
import jsat.distributions.kernels.KernelTrick;
import jsat.distributions.kernels.RBFKernel;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.lossfunctions.LossC;
import jsat.lossfunctions.LossFunc;
import jsat.lossfunctions.LossMC;
import jsat.lossfunctions.LossR;
import jsat.lossfunctions.SoftmaxLoss;
import jsat.parameters.Parameter;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.regression.BaseUpdateableRegressor;
import jsat.regression.RegressionDataSet;
import jsat.regression.UpdateableRegressor;
/**
* Kernel SGD is the kernelized counterpart to {@link LinearSGD}, and learns
* nonlinear functions via the kernel trick. The implementation is built upon
* {@link KernelPoint} and {@link KernelPoints} to support budgeted learning.
* Following the LinearSGD implementation, whether or not this algorithm
* supports regression, binary-classification, or multi-class classification is
* controlled by the {@link #setLoss(jsat.lossfunctions.LossFunc) loss function}
* used.
*
*
* The learning rate decay is not configurable for this implementation, and is
* decayed at a rate of {@link #setEta(double) η} /
* ({@link #setLambda(double) λ} * (t + 2 / λ)) , where {@code t}
* is the time step.
*
* @author Edward Raff
*/
public class KernelSGD implements UpdateableClassifier, UpdateableRegressor, Parameterized
{
private static final long serialVersionUID = -4956596506787859023L;
private LossFunc loss;
@ParameterHolder
private KernelTrick kernel;
private double lambda;
private double eta;
private KernelPoint.BudgetStrategy budgetStrategy;
private int budgetSize;
private double errorTolerance;
private int time;
private KernelPoint kpoint;
private KernelPoints kpoints;
private int epochs = 1;
/**
* Creates a new Kernel SGD object for classification with the RBF kernel
*/
public KernelSGD()
{
this(new SoftmaxLoss(), new RBFKernel(), 1e-4, KernelPoint.BudgetStrategy.MERGE_RBF, 300);
}
/**
* Creates a new Kernel SGD object
* @param loss the loss function to use
* @param kernel the kernel trick to use
* @param lambda the regularization penalty
* @param budgetStrategy the budget maintenance strategy to use
* @param budgetSize the maximum support vector budget
*/
public KernelSGD(LossFunc loss, KernelTrick kernel, double lambda, KernelPoint.BudgetStrategy budgetStrategy, int budgetSize)
{
this(loss, kernel, lambda, budgetStrategy, budgetSize, 1.0, 0.05);
}
/**
* Creates a new Kernel SGD object
* @param loss the loss function to use
* @param kernel the kernel trick to use
* @param lambda the regularization penalty
* @param eta the initial learning rate
* @param budgetStrategy the budget maintenance strategy to use
* @param errorTolerance the error tolerance used in certain budget maintenance steps
* @param budgetSize the maximum support vector budget
*/
public KernelSGD(LossFunc loss, KernelTrick kernel, double lambda, KernelPoint.BudgetStrategy budgetStrategy, int budgetSize, double eta, double errorTolerance)
{
setLoss(loss);
setKernel(kernel);
setLambda(lambda);
setEta(eta);
setBudgetStrategy(budgetStrategy);
setErrorTolerance(errorTolerance);
setBudgetSize(budgetSize);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public KernelSGD(KernelSGD toCopy)
{
this.loss = toCopy.loss.clone();
this.kernel = toCopy.kernel.clone();
this.lambda = toCopy.lambda;
this.eta = toCopy.eta;
this.budgetStrategy = toCopy.budgetStrategy;
this.budgetSize = toCopy.budgetSize;
this.errorTolerance = toCopy.errorTolerance;
this.time = toCopy.time;
this.epochs = toCopy.epochs;
if(toCopy.kpoint != null)
this.kpoint = toCopy.kpoint.clone();
if(toCopy.kpoints != null)
this.kpoints = toCopy.kpoints.clone();
}
/**
* Sets the number of iterations of the training set done during batch
* training
* @param epochs the number of iterations in batch training
*/
public void setEpochs(int epochs)
{
if(epochs < 1)
throw new IllegalArgumentException("Epochs must be a poistive constant, not " + epochs);
this.epochs = epochs;
}
/**
* Returns the number of epochs to use
* @return the number of epochs to use
*/
public int getEpochs()
{
return epochs;
}
/**
* Sets the loss function to use. The loss function controls whether or not
* classification or regression is supported.
* @param loss
*/
public void setLoss(LossFunc loss)
{
if(loss == null)
throw new NullPointerException("Loss may not be null");
this.loss = loss;
}
/**
* Returns the loss function in use
* @return the loss function in use
*/
public LossFunc getLoss()
{
return loss;
}
/**
* Sets the L2 regularization parameter used during learning.
* @param lambda the positive regularization parameter
*/
public void setLambda(double lambda)
{
if(lambda <= 0 || Double.isNaN(lambda) || Double.isInfinite(lambda))
throw new IllegalArgumentException("lambda must be a positive constant, not " + lambda);
this.lambda = lambda;
}
/**
* Returns the L2 regularization parameter
* @return the L2 regularization parameter
*/
public double getLambda()
{
return lambda;
}
/**
* Sets the error tolerance used for certain
* {@link #setBudgetStrategy(jsat.distributions.kernels.KernelPoint.BudgetStrategy) budget strategies}
* @param errorTolerance the error tolerance in [0, 1]
*/
public void setErrorTolerance(double errorTolerance)
{
if(errorTolerance < 0 || errorTolerance > 1 || Double.isNaN(errorTolerance))
throw new IllegalArgumentException("Error tolerance must be in [0, 1], not " + errorTolerance);
this.errorTolerance = errorTolerance;
}
/**
* Returns the error tolerance that would be used
* @return the error tolerance that would be used
*/
public double getErrorTolerance()
{
return errorTolerance;
}
/**
* Sets the maximum budget size, or number of support vectors, to allow
* during training. Increasing the budget size will increase the accuracy of
* the model, but will also increase the computational cost
* @param budgetSize the maximum allowed number of support vectors
*/
public void setBudgetSize(int budgetSize)
{
if(budgetSize < 1)
throw new IllegalArgumentException("Budgest size must be a positive constant, not " + budgetSize);
this.budgetSize = budgetSize;
}
/**
* Returns the budget size, or maximum number of allowed support vectors.
* @return the maximum number of allowed support vectors
*/
public int getBudgetSize()
{
return budgetSize;
}
/**
* Sets the budget maintenance strategy.
* @param budgetStrategy the method to meet budget size requirements
*/
public void setBudgetStrategy(KernelPoint.BudgetStrategy budgetStrategy)
{
if(budgetStrategy == null)
throw new NullPointerException("Budget strategy must be non null");
this.budgetStrategy = budgetStrategy;
}
/**
* Returns the method of budget maintenance
* @return the method of budget maintenance
*/
public KernelPoint.BudgetStrategy getBudgetStrategy()
{
return budgetStrategy;
}
/**
* Sets the base learning rate to start from. Because of the decay rate in
* use a good value for η is 1.0.
* @param eta the starting learning rate to use
*/
public void setEta(double eta)
{
this.eta = eta;
}
/**
* Returns the base learning rate
* @return the base learning rate
*/
public double getEta()
{
return eta;
}
/**
* Sets the kernel to use
* @param kernel the kernel to use
*/
public void setKernel(KernelTrick kernel)
{
if(kernel == null)
throw new NullPointerException("kernel trick must be non null");
this.kernel = kernel;
}
/**
* Returns the kernel in use
* @return the kernel in use
*/
public KernelTrick getKernel()
{
return kernel;
}
@Override
public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting)
{
if(!(loss instanceof LossC))
throw new FailedToFitException("Loss in use (" + loss.getClass().getSimpleName() + ") does not support classification");
if(predicting.getNumOfCategories() == 2)
{
kpoint = new KernelPoint(kernel, errorTolerance);
kpoint.setBudgetStrategy(budgetStrategy);
kpoint.setErrorTolerance(errorTolerance);
kpoint.setMaxBudget(budgetSize);
kpoints = null;
}
else
{
if(!(loss instanceof LossMC))
throw new FailedToFitException("Loss in use (" + loss.getClass().getSimpleName() + ") does not support multi-class classification");
kpoint = null;
kpoints = new KernelPoints(kernel, predicting.getNumOfCategories(), errorTolerance);
kpoints.setBudgetStrategy(budgetStrategy);
kpoints.setErrorTolerance(errorTolerance);
kpoints.setMaxBudget(budgetSize);
}
time = 0;
}
@Override
public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes)
{
if(!(loss instanceof LossR))
throw new FailedToFitException("Loss in use (" + loss.getClass().getSimpleName() + ") does not support regession");
kpoint = new KernelPoint(kernel, errorTolerance);
kpoint.setBudgetStrategy(budgetStrategy);
kpoint.setErrorTolerance(errorTolerance);
kpoint.setMaxBudget(budgetSize);
kpoints = null;
time = 0;
}
@Override
public void update(DataPoint dataPoint, int targetClass)
{
final Vec x = dataPoint.getNumericalValues();
final List qi = kernel.getQueryInfo(x);
final double eta_t = getNextEta();
if(kpoint != null)
{
kpoint.mutableMultiply(1-eta_t*lambda);
final double y = targetClass*2-1;
double dot = kpoint.dot(x, qi);
double lossD = ((LossC)loss).getDeriv(dot, y);
if(lossD != 0)
kpoint.mutableAdd(-eta_t*lossD, x, qi);
}
else if(kpoints != null)
{
kpoints.mutableMultiply(1-eta_t*lambda);
Vec pred = new DenseVector(kpoints.dot(x, qi));
((LossMC)loss).process(pred, pred);
((LossMC)loss).deriv(pred, pred, targetClass);
pred.mutableMultiply(-eta_t);//should we wrap in a scaledVec? Probably fine unless someone pulls out a 200 class problem
kpoints.mutableAdd(x, pred, qi);
}
}
@Override
public void update(DataPoint dataPoint, double targetValue)
{
final Vec x = dataPoint.getNumericalValues();
final List qi = kernel.getQueryInfo(x);
final double eta_t = getNextEta();
kpoint.mutableMultiply(1 - eta_t * lambda);
final double y = targetValue;
double dot = kpoint.dot(x, qi);
double lossD = ((LossR) loss).getDeriv(dot, y);
if (lossD != 0)
kpoint.mutableAdd(-eta_t * lossD, x, qi);
}
@Override
public CategoricalResults classify(DataPoint data)
{
final Vec x = data.getNumericalValues();
final List qi = kernel.getQueryInfo(x);
if(kpoint != null)
return ((LossC)loss).getClassification(kpoint.dot(x, qi));
else
{
Vec pred = new DenseVector(kpoints.dot(x, qi));
((LossMC)loss).process(pred, pred);
return ((LossMC)loss).getClassification(pred);
}
}
@Override
public double regress(DataPoint data)
{
final Vec x = data.getNumericalValues();
final List qi = kernel.getQueryInfo(x);
return ((LossR)loss).getRegression(kpoint.dot(x, qi));
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(ClassificationDataSet dataSet)
{
BaseUpdateableClassifier.trainEpochs(dataSet, this, epochs);
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(RegressionDataSet dataSet)
{
BaseUpdateableRegressor.trainEpochs(dataSet, this, epochs);
}
@Override
public KernelSGD clone()
{
return new KernelSGD(this);
}
private double getNextEta()
{
return eta / (lambda * (++time + 2 / lambda));
}
/**
* Guess the distribution to use for the regularization term
* {@link #setLambda(double) λ} .
*
* @param d the data set to get the guess for
* @return the guess for the λ parameter
*/
public static Distribution guessLambda(DataSet d)
{
return new LogUniform(1e-7, 1e-2);
}
}
Ads help maintain this website.