package jsat.classifiers.linear;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.SimpleWeightVectorModel;
import jsat.classifiers.BaseUpdateableClassifier;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.DataPoint;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.ScaledVector;
import jsat.linear.Vec;
import jsat.lossfunctions.HingeLoss;
import jsat.lossfunctions.LossC;
import jsat.lossfunctions.LossFunc;
import jsat.lossfunctions.LossMC;
import jsat.lossfunctions.LossR;
import jsat.math.decayrates.DecayRate;
import jsat.math.decayrates.PowerDecay;
import jsat.math.optimization.stochastic.GradientUpdater;
import jsat.math.optimization.stochastic.SimpleSGD;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.regression.BaseUpdateableRegressor;
import jsat.regression.RegressionDataSet;
import jsat.regression.UpdateableRegressor;

/**
 * LinearSGD learns either a classification or regression problem depending on 
 * the {@link #setLoss(jsat.lossfunctions.LossFunc) loss function ℓ(w,x)}
 * used. The solution attempts to minimize 
 * ∑i ℓ(w,xi) + 
 * {@link #setLambda0(double) λ0}/2 ||w||22 + 
 * {@link #setLambda1(double) λ1} ||w||1, and is 
 * trained by Stochastic Gradient Descent. 
*
*
* NOTE: To support L1 regularization with sparse results and online * learning at the same time, the normalization of the regularization penalty by * the number of data points is not present in the implementation at this time. * Setting {@link #setLambda1(double) λ1} to the desired value * divided by the number of unique data points in the whole set will result in * the correct regularization penalty being applied. * * See: * * @author Edward Raff */ public class LinearSGD extends BaseUpdateableClassifier implements UpdateableRegressor, Parameterized, SimpleWeightVectorModel { private static final long serialVersionUID = -59695592724956535L; private LossFunc loss; private GradientUpdater gradientUpdater; private double eta; private DecayRate decay; private Vec[] ws; private GradientUpdater[] gus; private double[] bs; private int time; private double lambda0; private double lambda1; private double l1U; private double[][] l1Q; private boolean useBias = true; /** * Creates a new LinearSGD learner for multi-class classification problems. */ public LinearSGD() { this(new HingeLoss(), 1e-4, 0.0); } /** * Creates a new LinearSGD learner * @param loss the loss function to use * @param lambda0 the L2 regularization term * @param lambda1 the L1 regularization term */ public LinearSGD(LossFunc loss, double lambda0, double lambda1) { this(loss, 0.001, new PowerDecay(1, 0.1), lambda0, lambda1); } /** * Creates a new LinearSGD learner. * @param loss the loss function to use * @param eta the initial learning rate * @param decay the decay rate for η * @param lambda0 the L2 regularization term * @param lambda1 the L1 regularization term */ public LinearSGD(LossFunc loss, double eta, DecayRate decay, double lambda0, double lambda1) { setLoss(loss); setEta(eta); setEtaDecay(decay); setGradientUpdater(new SimpleSGD()); setLambda0(lambda0); setLambda1(lambda1); } /** * Copy constructor * @param toClone the object to copy */ public LinearSGD(LinearSGD toClone) { this.loss = toClone.loss.clone(); this.eta = toClone.eta; this.decay = toClone.decay.clone(); this.time = toClone.time; this.lambda0 = toClone.lambda0; this.lambda1 = toClone.lambda1; this.l1U = toClone.l1U; this.useBias = toClone.useBias; this.gradientUpdater = toClone.gradientUpdater; if(toClone.l1Q != null) { this.l1Q = new double[toClone.l1Q.length][]; for(int i = 0; i < toClone.l1Q.length; i++) this.l1Q[i] = Arrays.copyOf(toClone.l1Q[i], toClone.l1Q[i].length); } if(toClone.ws != null) { this.ws = new Vec[toClone.ws.length]; this.bs = new double[toClone.bs.length]; this.gus = new GradientUpdater[toClone.gus.length]; for(int i = 0; i < ws.length; i++) { this.ws[i] = toClone.ws[i].clone(); this.bs[i] = toClone.bs[i]; this.gus[i] = toClone.gus[i].clone(); } } } /** * Sets the method that will be used to update the weight vectors given * their gradient information. * @param gradientUpdater the method to use for updating the weight vectors * from the gradient */ public void setGradientUpdater(GradientUpdater gradientUpdater) { if(gradientUpdater == null ) throw new IllegalArgumentException("Gradient updater must be non-null"); this.gradientUpdater = gradientUpdater; } /** * * @return the method to use for updating the weight vectors from the * gradient */ public GradientUpdater getGradientUpdater() { return gradientUpdater; } /** * Sets the rate at which {@link #setEta(double) η} is decayed at each * update. * @param decay the decay rate to use */ public void setEtaDecay(DecayRate decay) { this.decay = decay; } /** * Returns the decay rate in use * @return the decay rate in use */ public DecayRate getEtaDecay() { return decay; } /** * Sets the initial learning rate η to use. It should generally be in * (0, 1), but any positive value is acceptable. * @param eta the learning rate to use. */ public void setEta(double eta) { if(eta <= 0 || Double.isNaN(eta) || Double.isInfinite(eta)) throw new IllegalArgumentException("eta must be a positive constant, not " + eta); this.eta = eta; } /** * Returns the current learning rate in use * @return the current learning rate in use */ public double getEta() { return eta; } /** * Sets the loss function used for the model. The loss function controls * whether or not regression, binary classification, or multi-class * classification is supported. * @param loss the loss function to use */ public void setLoss(LossFunc loss) { this.loss = loss; } /** * Returns the loss function in use * @return the loss function in use */ public LossFunc getLoss() { return loss; } /** * λ0 controls the L2 regularization penalty. * @param lambda0 the L2 regularization penalty to use */ public void setLambda0(double lambda0) { if(lambda0 < 0 || Double.isNaN(lambda0) || Double.isInfinite(lambda0)) throw new IllegalArgumentException("Lambda0 must be non-negative, not " + lambda0); this.lambda0 = lambda0; } /** * Returns the L2 regularization term in use * @return the L2 regularization term in use */ public double getLambda0() { return lambda0; } /** * λ1 controls the L1 regularization penalty. * @param lambda1 the L1 regularization penalty to use */ public void setLambda1(double lambda1) { if(lambda1 < 0 || Double.isNaN(lambda1) || Double.isInfinite(lambda1)) throw new IllegalArgumentException("Lambda1 must be non-negative, not " + lambda1); this.lambda1 = lambda1; } /** * Returns the L1 regularization term in use * @return the L1 regularization term in use */ public double getLambda1() { return lambda1; } /** * Sets whether or not an implicit bias term will be added to the data set * @param useBias {@code true} to add an implicit bias term */ public void setUseBias(boolean useBias) { this.useBias = useBias; } /** * Returns whether or not an implicit bias term is in use * @return {@code true} if a bias term is in use */ public boolean isUseBias() { return useBias; } @Override public LinearSGD clone() { return new LinearSGD(this); } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { if(!(loss instanceof LossC)) throw new FailedToFitException("Loss function " + loss.getClass().getSimpleName() + " only supports regression"); if(predicting.getNumOfCategories() == 2) { ws = new Vec[1]; bs = new double[1]; gus = new GradientUpdater[1]; } else { if(!(loss instanceof LossMC)) throw new FailedToFitException("Loss function " + loss.getClass().getSimpleName() + " only supports binary classification"); ws = new Vec[predicting.getNumOfCategories()]; bs = new double[predicting.getNumOfCategories()]; gus = new GradientUpdater[predicting.getNumOfCategories()]; } setUpShared(numericAttributes); } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes) { if(!(loss instanceof LossR)) throw new FailedToFitException("Loss function " + loss.getClass().getSimpleName() + "does not support regression"); ws = new Vec[1]; bs = new double[1]; gus = new GradientUpdater[1]; setUpShared(numericAttributes); } private void setUpShared(int numericAttributes) { if(numericAttributes <= 0 ) throw new FailedToFitException("LinearSGD requires numeric features to use"); for(int i = 0; i < ws.length; i++) { ws[i] = new ScaledVector(new DenseVector(numericAttributes)); gus[i] = gradientUpdater.clone(); gus[i].setup(ws[i].length()); } time = 0; l1U = 0; if(lambda1 > 0) l1Q = new double[ws.length][ws[0].length()]; else l1Q = null; } @Override public void update(DataPoint dataPoint, int targetClass) { final double eta_t = decay.rate(time++, eta); Vec x = dataPoint.getNumericalValues(); applyL2Reg(eta_t); //apply gradient updates if(ws.length == 1) { final double y = targetClass*2-1; final double lossD = ((LossC)loss).getDeriv(ws[0].dot(x)+bs[0], y); performGradientUpdate(0, eta_t, lossD, x); } else { Vec pred = new DenseVector(ws.length); for(int i = 0; i < ws.length; i++) pred.set(i, ws[i].dot(x)+bs[i]); ((LossMC)loss).process(pred, pred); ((LossMC)loss).deriv(pred, pred, targetClass); for(IndexValue iv : pred) { final int i = iv.getIndex(); final double lossD = iv.getValue(); performGradientUpdate(i, eta_t, lossD, x); } } applyL1Reg(eta_t, x); } /** * * @param i the index of the weight vector array to update * @param eta_t the learning rate to use * @param lossD the loss for the specified weight vector * @param x the input vector the loss was incurred on */ private void performGradientUpdate(final int i, final double eta_t, final double lossD, Vec x) { final Vec grad = new ScaledVector(lossD, x); if (useBias) bs[i] -= gus[i].update(ws[i], grad, eta_t, bs[i], lossD); else gus[i].update(ws[i], grad, eta_t); } @Override public void update(DataPoint dataPoint, double targetValue) { final double eta_t = decay.rate(time++, eta); Vec x = dataPoint.getNumericalValues(); applyL2Reg(eta_t); final double lossD = ((LossR)loss).getDeriv(ws[0].dot(x)+bs[0], targetValue); performGradientUpdate(0, eta_t, lossD, x); applyL1Reg(eta_t, x); } @Override public CategoricalResults classify(DataPoint data) { Vec x = data.getNumericalValues(); if(ws.length == 1) return ((LossC)loss).getClassification(ws[0].dot(x)+bs[0]); else { Vec pred = new DenseVector(ws.length); for(int i = 0; i < ws.length; i++) pred.set(i, ws[i].dot(x)+bs[i]); ((LossMC)loss).process(pred, pred); return ((LossMC)loss).getClassification(pred); } } @Override public double regress(DataPoint data) { Vec x = data.getNumericalValues(); return ((LossR)loss).getRegression(ws[0].dot(x)+bs[0]); } @Override public boolean supportsWeightedData() { return false; } /** * Applies L2 regularization to the model * @param eta_t the learning rate in use */ private void applyL2Reg(final double eta_t) { if(lambda0 > 0)//apply L2 regularization for(Vec v : ws) v.mutableMultiply(1-eta_t*lambda0); } /** * Applies L1 regularization to the model * @param eta_t the learning rate in use * @param x the input vector the update is from */ private void applyL1Reg(final double eta_t, Vec x) { //apply l1 regularization if(lambda1 > 0) { l1U += eta_t*lambda1;//line 6: in Tsuruoka et al paper, figure 2 for(int k = 0; k < ws.length; k++) { final Vec w_k = ws[k]; final double[] l1Q_k = l1Q[k]; for(IndexValue iv : x) { final int i = iv.getIndex(); //see "APPLYPENALTY(i)" on line 15: from Figure 2 in Tsuruoka et al paper final double z = w_k.get(i); double newW_i = 0; if (z > 0) newW_i = Math.max(0, z - (l1U + l1Q_k[i])); else if(z < 0) newW_i = Math.min(0, z + (l1U - l1Q_k[i])); l1Q_k[i] += (newW_i - z); w_k.set(i, newW_i); } } } } @Override public void train(RegressionDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(RegressionDataSet dataSet) { BaseUpdateableRegressor.trainEpochs(dataSet, this, getEpochs()); } @Override public Vec getRawWeight(int index) { return ws[index]; } @Override public double getBias(int index) { return bs[index]; } @Override public int numWeightsVecs() { return ws.length; } /** * Guess the distribution to use for the regularization term * {@link #setLambda0(double) λ0} . * * @param d the data set to get the guess for * @return the guess for the λ0 parameter */ public static Distribution guessLambda0(DataSet d) { return new LogUniform(1e-7, 1e-2); } /** * Guess the distribution to use for the regularization term * {@link #setLambda0(double) λ1} . * * @param d the data set to get the guess for * @return the guess for the λ1 parameter */ public static Distribution guessLambda1(DataSet d) { int N = d.getSampleSize(); return new LogUniform(1e-7/N, 1e-3/N); } }

Ads help maintain this website.