package jsat.classifiers.linear;
import static java.lang.Math.*;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.SimpleWeightVectorModel;
import jsat.classifiers.*;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.ConstantVector;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.math.MathTricks;
import jsat.math.decayrates.DecayRate;
import jsat.math.decayrates.ExponetialDecay;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
/**
* This is a Stochastic implementation of Multinomial Logistic Regression. It
* supports regularization from several different priors, and performs prior
* updates in a lazy fashion to avoid destroying the sparsity of training
* inputs.
*
* Algorithm is based on the technical report:
* Carpenter, B. (2008). Lazy Sparse Stochastic Gradient Descent for
* Regularized Mutlinomial Logistic Regression. Retrieved from
* http://lingpipe-blog.com/lingpipe-white-papers/
*
* @author Edward Raff
*/
public class StochasticMultinomialLogisticRegression implements Classifier, Parameterized, SimpleWeightVectorModel
{
private static final long serialVersionUID = -492707881682847556L;
private int epochs;
private boolean clipping = true;
private double regularization;
private double tolerance = 1e-4;
private double initialLearningRate;
private double alpha = 0.5;
private DecayRate learningRateDecay = new ExponetialDecay();
private Prior prior;
private boolean standardized = true;
private boolean useBias = true;
private int miniBatchSize = 1;
private Vec[] B;
private double[] biases;
/**
* Creates a new Stochastic Multinomial Logistic Regression object
* @param initialLearningRate the initial learning rate to use
* @param epochs the maximum number of training epochs to go through
* @param regularization the scale factor applied to the regularization term
* @param prior the prior to use for regularization
*/
public StochasticMultinomialLogisticRegression(double initialLearningRate, int epochs, double regularization, Prior prior)
{
setEpochs(epochs);
setRegularization(regularization);
setInitialLearningRate(initialLearningRate);
setPrior(prior);
}
/**
* Creates a new Stochastic Multinomial Logistic Regression that uses a
* {@link Prior#GAUSSIAN} prior with a regularization scale of 1e-6.
*
* @param initialLearningRate the initial learning rate to use
* @param epochs the maximum number of training epochs to go through
*/
public StochasticMultinomialLogisticRegression(double initialLearningRate, int epochs)
{
this(initialLearningRate, epochs, 1e-6, Prior.GAUSSIAN);
}
/**
* Creates a new Stochastic Multinomial Logistic Regression that uses a
* {@link Prior#GAUSSIAN} prior with a regularization scale of 1e-6. It
* will do at most 50 epochs with a learning rate of 0.1
*/
public StochasticMultinomialLogisticRegression()
{
this(0.1, 50);
}
/**
* Copy constructor
* @param toClone the classifier to create a copy of
*/
protected StochasticMultinomialLogisticRegression(StochasticMultinomialLogisticRegression toClone)
{
this.epochs = toClone.epochs;
this.clipping = toClone.clipping;
this.regularization = toClone.regularization;
this.tolerance = toClone.tolerance;
this.initialLearningRate = toClone.initialLearningRate;
this.alpha = toClone.alpha;
this.learningRateDecay = toClone.learningRateDecay;
this.prior = toClone.prior;
this.standardized = toClone.standardized;
if(toClone.B != null)
{
this.B = new Vec[toClone.B.length];
for(int i = 0; i < toClone.B.length; i++)
this.B[i] = toClone.B[i].clone();
}
if(toClone.biases != null)
this.biases = Arrays.copyOf(toClone.biases, toClone.biases.length);
}
/**
* Represents a prior of the coefficients that can be applied to perform
* regularization.
*/
public enum Prior
{
/**
* A Gaussian prior, this is equivalent to L2 regularization.
*/
GAUSSIAN
{
@Override
protected double gradientError(double b_i, double s_i)
{
return - b_i/s_i;
}
@Override
protected double logProb(double b_i, double s_i)
{
return -0.5*log(2*PI*s_i)-2*b_i*b_i*s_i/2;
}
},
/**
* A Laplace prior, this is equivalent to L1 regularization
*/
LAPLACE
{
@Override
protected double gradientError(double b_i, double s_i)
{
return - sqrt(2)*signum(b_i)/sqrt(s_i);
}
@Override
protected double logProb(double b_i, double s_i)
{
return -signum(b_i)*sqrt(2)*b_i/sqrt(s_i)-0.5*log(2*s_i);
}
},
/**
* This is the Elastic Net prior, and it uses the extra
* {@link #setAlpha(double) alpha} parameter. This prior is a mix of
* both {@link #LAPLACE} and {@link #GAUSSIAN}. Alpha should be in the
* range [0,1]. Alpha weight will be applied to the Laplace prior, and
* (1-alpha) weight will be applied to the Gaussian prior. The extreme
* values of this collapse into the Laplace and Gaussian priors.
*/
ELASTIC
{
@Override
protected double gradientError(double b_i, double s_i)
{
throw new UnsupportedOperationException();
}
@Override
protected double gradientError(double b_i, double s_i, double alpha)
{
return alpha*LAPLACE.gradientError(b_i, s_i)
+ (1-alpha)*GAUSSIAN.gradientError(b_i, s_i);
}
@Override
protected double logProb(double b_i, double s_i)
{
return Double.NaN;
}
@Override
protected double logProb(double b_i, double s_i, double alpha)
{
return alpha*LAPLACE.logProb(b_i, s_i)
+ (1-alpha)*GAUSSIAN.logProb(b_i, s_i);
}
},
/**
* This is a prior from the Cauchy (student-t) distribution, and it uses
* the extra {@link #setAlpha(double) alpha} parameter. Alpha should be
* in the range (0, Infty).
*/
CAUCHY
{
@Override
protected double gradientError(double b_i, double s_i)
{
throw new UnsupportedOperationException();
}
@Override
protected double gradientError(double b_i, double s_i, double alpha)
{
return - 2*b_i/(b_i*b_i+alpha*alpha);
}
@Override
protected double logProb(double b_i, double s_i)
{
return Double.NaN;
}
@Override
protected double logProb(double b_i, double s_i, double alpha)
{
return -log(PI)+log(alpha)-log(b_i*b_i+alpha*alpha);
}
},
/**
* This is the Uniform prior. The uniform prior is equivalent to
* no regularization.
*/
UNIFORM
{
@Override
protected double gradientError(double b_i, double s_i)
{
return 0;
}
@Override
protected double logProb(double b_i, double s_i)
{
return 0;
}
};
abstract protected double gradientError(double b_i, double s_i);
protected double gradientError(double b_i, double s_i, double alpha)
{
return gradientError(b_i, s_i);
}
abstract protected double logProb(double b_i, double s_i);
protected double logProb(double b_i, double s_i, double alpha)
{
return logProb(b_i, s_i);
}
}
/**
* Sets whether or not to learn the bias term for a model. If no bias term
* is in use, the model learned must pass through the origin of the world.
* The use of the bias term is very important for low dimensional problems,
* but less so for many higher dimensional problems.
* @param useBias {@code true} if the bias term should be used,
* {@code false} otherwise
*/
public void setUseBias(boolean useBias)
{
this.useBias = useBias;
}
/**
* Returns {@code true} if the bias term is in use
* @return {@code true} if the bias term is in use
*/
public boolean isUseBias()
{
return useBias;
}
/**
* Sets the maximum number of epochs that occur in each iteration. Each
* epoch goes through the whole data set once.
*
* @param epochs the maximum number of epochs to train
*/
public void setEpochs(int epochs)
{
if(epochs <= 0)
throw new IllegalArgumentException("Number of epochs must be positive");
this.epochs = epochs;
}
/**
* Returns the maximum number of epochs
* @return the maximum number of epochs
*/
public int getEpochs()
{
return epochs;
}
/**
* Sets the extra parameter alpha. This is used for some priors that take
* an extra parameter. This is {@link Prior#CAUCHY} and
* {@link Prior#ELASTIC}. If these two priors are not in use, the value is
* ignored.
*
* @param alpha the extra parameter value to use. Must be positive
*/
public void setAlpha(double alpha)
{
if(alpha < 0 || Double.isNaN(alpha) || Double.isInfinite(alpha))
throw new IllegalArgumentException("Extra parameter must be non negative, not " + alpha);
this.alpha = alpha;
}
/**
* Returns the extra parameter value
* @return the extra parameter value
*/
public double getAlpha()
{
return alpha;
}
/**
* Sets whether or not the clip changes in coefficient values caused by
* regularization so that they can not make the coefficients go from
* positive to negative or negative to positive. If clipping is on, the
* value will go to zero instead. If off, the value will be allowed to
* change signs.
* If there is no regularization, this has no impact.
*
* @param clipping {@code true} if clipping should be used, false otherwise
*/
public void setClipping(boolean clipping)
{
this.clipping = clipping;
}
/**
* Returns whether or not coefficient clipping is on.
* @return {@code true} if clipping is on.
*/
public boolean isClipping()
{
return clipping;
}
/**
* Sets the initial learning rate to use for the first epoch. The learning
* rate will decay according to the
* {@link #setLearningRateDecay(jsat.math.decayrates.DecayRate) decay rate}
* in use.
*
* @param initialLearningRate the initial learning rate to use
*/
public void setInitialLearningRate(double initialLearningRate)
{
if(initialLearningRate <= 0 || Double.isInfinite(initialLearningRate) || Double.isNaN(initialLearningRate))
throw new IllegalArgumentException("Learning rate must be a positive constant, not " + initialLearningRate);
this.initialLearningRate = initialLearningRate;
}
/**
* Returns the current initial learning rate
* @return the learning rate in use
*/
public double getInitialLearningRate()
{
return initialLearningRate;
}
/**
* Sets the decay rate used to reduce the learning rate after each epoch.
*
* @param learningRateDecay the decay rate to use
*/
public void setLearningRateDecay(DecayRate learningRateDecay)
{
this.learningRateDecay = learningRateDecay;
}
/**
* Returns the decay rate in use
* @return the decay rate in use
*/
public DecayRate getLearningRateDecay()
{
return learningRateDecay;
}
/**
* Sets the coefficient applied to the regularization penalty at each
* update. This is usual set to a small value less than 1. If set to zero,
* it effectively turns off the use of regularization.
*
* @param regularization the non negative regularization coefficient to apply
*/
public void setRegularization(double regularization)
{
if(regularization < 0 || Double.isNaN(regularization) || Double.isInfinite(regularization))
throw new IllegalArgumentException("Regualrization must be a non negative constant, not " + regularization);
this.regularization = regularization;
}
/**
* Returns the regularization coefficient in use
* @return the regularization coefficient in use
*/
public double getRegularization()
{
return regularization;
}
/**
* Sets the prior used to perform regularization
* @param prior the prior to use
*/
public void setPrior(Prior prior)
{
this.prior = prior;
}
/**
* Returns the prior used for regularization
* @return the prior used
*/
public Prior getPrior()
{
return prior;
}
/**
* Sets the tolerance that determines when the training stops early because
* the change has become too insignificant.
*
* @param tolerance the minimum change in log likelihood to stop training
*/
public void setTolerance(double tolerance)
{
this.tolerance = tolerance;
}
/**
* Returns the minimum tolerance for early stopping.
* @return the minimum change in log likelihood to stop training
*/
public double getTolerance()
{
return tolerance;
}
/**
* Sets whether or not to perform implicit standardization of the feature
* values when performing regularization by the prior. If set on, the input
* data will be adjusted to have zero mean and unit variance. This is done
* without destroying sparsity. If there is not regularization, this
* parameter has no impact.
*
* @param standardized {@code true} if the input will be standardized,
* {@code false} if ti will be left as is.
*/
public void setStandardized(boolean standardized)
{
this.standardized = standardized;
}
/**
* Returns whether or not the input is standardized for the priors
* @return {@code true} if the input is standardized for the priors
*/
public boolean isStandardized()
{
return standardized;
}
/**
* Sets the amount of data points used to form each gradient update.
* Increasing the batch size can help convergence. By default, a mini batch
* size of 1 is used.
*
* @param miniBatchSize the number of data points used to perform each
* update
*/
public void setMiniBatchSize(int miniBatchSize)
{
this.miniBatchSize = miniBatchSize;
}
/**
* Returns the number of data points used to perform each gradient update
* @return the number of data points used to perform each gradient update
*/
public int getMiniBatchSize()
{
return miniBatchSize;
}
@Override
public Vec getRawWeight(int index)
{
if(index == B.length)
return new ConstantVector(0, B[0].length());
else
return B[index];
}
@Override
public double getBias(int index)
{
if(index == biases.length)
return 0;
else
return biases[index];
}
@Override
public int numWeightsVecs()
{
return B.length+1;
}
@Override
public CategoricalResults classify(DataPoint data)
{
if(B == null)
throw new UntrainedModelException("Model has not yet been trained");
final Vec x = data.getNumericalValues();
double[] probs = new double[B.length + 1];
for (int i = 0; i < B.length; i++)
probs[i] = x.dot(B[i])+biases[i];
probs[B.length] = 1;
MathTricks.softmax(probs, false);
return new CategoricalResults(probs);
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(ClassificationDataSet dataSet)
{
final int n = dataSet.getSampleSize();
final double N = n;
final int d = dataSet.getNumNumericalVars();
if(d < 1)
throw new FailedToFitException("Data set has no numeric attributes to train on");
B = new Vec[dataSet.getClassSize()-1];
biases = new double[B.length];
for(int i = 0; i < B.length; i++)
B[i] = new DenseVector(d);
IntList randOrder = new IntList(n);
ListUtils.addRange(randOrder, 0, n, 1);
Vec means = null, stdDevs = null;
if(standardized)
{
Vec[] ms = dataSet.getColumnMeanVariance();
means = ms[0];
stdDevs = ms[1];
stdDevs.applyFunction(Math::sqrt);
//Now transform it so that stdDevs holds standard deviations, and means is the mean / standDev
means.pairwiseDivide(stdDevs);
stdDevs.applyFunction((x)-> 1/x);
}
double[] zs = new double[B.length];
/**
* Contains the last time each feature was used
*/
int[] u = new int[d];
/**
* Contains the current time.
*/
int q = 0;
double prevLogLike = Double.POSITIVE_INFINITY;
//learing rate in use
double eta;
for(int iter = 0; iter < epochs; iter++)
{
Collections.shuffle(randOrder);
double logLike = 0;
eta = learningRateDecay.rate(iter, epochs, initialLearningRate);
final double etaReg = regularization*eta;
for (int batch = 0; batch < randOrder.size(); batch += miniBatchSize)
{
int batchCount = Math.min(miniBatchSize, randOrder.size() - batch);
double batchFrac = 1.0 / batchCount;
for (int k = 0; k < batchCount; k++)
{
int j = randOrder.get(batch+k);
final int c_j = dataSet.getDataPointCategory(j);
final Vec x_j = dataSet.getDataPoint(j).getNumericalValues();
//compute softmax
for (int i = 0; i < B.length; i++)
zs[i] = x_j.dot(B[i]) + biases[i];
MathTricks.softmax(zs, true);
//lazy apply lost rounds of regularization
if (prior != Prior.UNIFORM)
{
for (IndexValue iv : x_j)
{
int i = iv.getIndex();
if(u[i] == 0)
continue;
double etaRegScaled = etaReg * (u[i] - q) / N;
for (Vec b : B)
{
double bVal = b.get(i);
double bNewVal = bVal;
if (standardized)
bNewVal += etaRegScaled * prior.gradientError(bVal * stdDevs.get(i) - means.get(i), 1, alpha);
else
bNewVal += etaRegScaled * prior.gradientError(bVal, 1, alpha);
if (clipping && signum(bVal) != signum(bNewVal))
b.set(i, 0);
else
b.set(i, bNewVal);
}
u[i] = q;
}
//No need to do bias here, b/c bias is always up to date
}
for (int c = 0; c < B.length; c++)
{
Vec b = B[c];
double p_c = zs[c];
double log_pc = log(p_c);
if (!Double.isInfinite(log_pc))
logLike += log_pc;
double errScaling = (c == c_j ? 1 : 0) - p_c;
b.mutableAdd(batchFrac*eta * errScaling, x_j);
if (useBias)
biases[c] += batchFrac*eta * errScaling + etaReg * prior.gradientError(biases[c] - 1, 1, alpha);
}
}
q++;
}
logLike *= -1;
if (prior != Prior.UNIFORM)
{
for (int i = 0; i < d; i++)
{
if (u[i] - q == 0)
{
for (Vec b : B)
if (standardized)
logLike += regularization*prior.logProb(b.get(i) * stdDevs.get(i) - means.get(i), 1, alpha);
else
logLike += regularization*prior.logProb(b.get(i), 1, alpha);
continue;
}
double etaRegScaled = etaReg * (u[i] - q) / N;
for (Vec b : B)
{
double bVal = b.get(i);
if (bVal == 0.0)
continue;
double bNewVal = bVal;
if (standardized)
bNewVal += etaRegScaled * prior.gradientError(bVal * stdDevs.get(i) - means.get(i), 1, alpha);
else
bNewVal += etaRegScaled * prior.gradientError(bVal, 1, alpha);
if (clipping && signum(bVal) != signum(bNewVal))
b.set(i, 0);
else
b.set(i, bNewVal);
if(standardized)
logLike += regularization*prior.logProb(b.get(i) * stdDevs.get(i) - means.get(i), 1, alpha);
else
logLike += regularization*prior.logProb(b.get(i), 1, alpha);
}
u[i] = q;
}
}
double dif = abs(prevLogLike-logLike)/(abs(prevLogLike)+abs(logLike));
if(dif < tolerance)
break;
else
prevLogLike = logLike;
}
}
@Override
public boolean supportsWeightedData()
{
return false;
}
/**
* Returns the raw coefficient vector used without the bias term. For a
* multinomial Logistic model, there are C-1 coefficient vectors. C is the
* number of output classes. Altering the returned vector will alter the
* model. The i'th index of the vector corresponds to the weight therm for
* the i'th index in an input.
*
* @param id which coefficient vector to obtain
* @return the vector of variable coefficients.
*/
public Vec getCoefficientVector(int id)
{
return B[id];
}
@Override
public Classifier clone()
{
return new StochasticMultinomialLogisticRegression(this);
}
}
Ads help maintain this website.