package jsat.classifiers.linear;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;
import java.util.concurrent.atomic.DoubleAdder;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.SimpleWeightVectorModel;
import jsat.classifiers.*;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.exceptions.FailedToFitException;
import jsat.linear.ConcatenatedVec;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.SubVector;
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.math.Function;
import jsat.math.FunctionVec;
import jsat.math.optimization.*;
import jsat.parameters.Parameterized;
import jsat.regression.*;
import jsat.utils.ListUtils;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;

/**
 * LinearBatch 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, and is 
 * trained using a batch optimization method. 
*
* LinearBatch can be warm started from any model implementing the * {@link SimpleWeightVectorModel} interface. *
*
* Note: the current implementation does not currently use bias terms * @author Edward Raff */ public class LinearBatch implements Classifier, Regressor, Parameterized, SimpleWeightVectorModel, WarmClassifier, WarmRegressor { private static final long serialVersionUID = -446156124954287580L; /** * Weight vectors */ private Vec[] ws; /** * bias terms for each weight vector */ private double[] bs; private LossFunc loss; private double lambda0; private Optimizer optimizer; private double tolerance; private boolean useBiasTerm = true; /** * Creates a new Linear Batch learner for classification using a small * regularization term */ public LinearBatch() { this(new SoftmaxLoss(), 1e-6); } /** * Creates a new Linear Batch learner * @param loss the loss function to use * @param lambda0 the L2 regularization term */ public LinearBatch(LossFunc loss, double lambda0) { this(loss, lambda0, 1e-3); } /** * Creates a new Linear Batch learner * @param loss the loss function to use * @param lambda0 the L2 regularization term * @param tolerance the threshold for convergence */ public LinearBatch(LossFunc loss, double lambda0, double tolerance) { this(loss, lambda0, tolerance, null); } /** * Creates a new Linear Batch learner * @param loss the loss function to use * @param lambda0 the L2 regularization term * @param tolerance the threshold for convergence * @param optimizer the batch optimization method to use */ public LinearBatch(LossFunc loss, double lambda0, double tolerance, Optimizer optimizer) { setLoss(loss); setLambda0(lambda0); setOptimizer(optimizer); setTolerance(tolerance); } /** * Copy constructor * @param toCopy the object to copy */ public LinearBatch(LinearBatch toCopy) { this(toCopy.loss.clone(), toCopy.lambda0, toCopy.tolerance, toCopy.optimizer == null ? null : toCopy.optimizer.clone()); if(toCopy.ws != null) { this.ws = new Vec[toCopy.ws.length]; for(int i = 0; i < toCopy.ws.length; i++) this.ws[i] = toCopy.ws[i].clone(); } if(toCopy.bs != null) this.bs = Arrays.copyOf(toCopy.bs, toCopy.bs.length); } public void setUseBiasTerm(boolean useBiasTerm) { this.useBiasTerm = useBiasTerm; } public boolean isUseBiasTerm() { return useBiasTerm; } /** * λ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; } /** * 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; } /** * Sets the method of batch optimization that will be used. {@code null} is * valid for this value, in which case the implementation will attempt to * select a reasonable optimizer automatically.
*
* NOTE: the current implementation requires the optimizer to work based off * only the function value and its derivative. * * @param optimizer the method to use for function minimization */ public void setOptimizer(Optimizer optimizer) { this.optimizer = optimizer; } /** * Returns the optimization method in use, or {@code null}. * @return the optimization method in use, or {@code null}. */ public Optimizer getOptimizer() { return optimizer; } /** * Sets the convergence tolerance to user for training. Smaller values reach * a more accuracy solution but may take longer to complete.
* While zero is a valid tolerance value, it is not usually useful in * practice. Values in [10-4, 10-2] are usually more * practical. * * @param tolerance the convergence tolerance */ public void setTolerance(double tolerance) { if(tolerance < 0 || Double.isNaN(tolerance) || Double.isInfinite(tolerance)) throw new IllegalArgumentException("Tolerance must be a non-negative constant, not " + tolerance); this.tolerance = tolerance; } /** * Returns the value of the convergence tolerance parameter * @return the convergence tolerance parameter */ public double getTolerance() { return tolerance; } @Override public CategoricalResults classify(DataPoint data) { final 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) { final Vec x = data.getNumericalValues(); return ((LossR)loss).getRegression(ws[0].dot(x)+bs[0]); } @Override public void train(final ClassificationDataSet D, final boolean parallel) { train(D, null, parallel); } @Override public void train(ClassificationDataSet D, Classifier warmSolution, boolean parallel) { if(D.getNumNumericalVars() <= 0) throw new FailedToFitException("LinearBath requires numeric features to work"); if(!(loss instanceof LossC)) throw new FailedToFitException("Loss function " + loss.getClass().getSimpleName() + " does not support classification"); if(D.getClassSize() > 2) if (!(loss instanceof LossMC)) throw new FailedToFitException("Loss function " + loss.getClass().getSimpleName() + " does not support multi-class classification"); else { ws = new Vec[D.getClassSize()]; bs = new double[ws.length]; } else { ws = new Vec[1]; bs = new double[1]; } for (int i = 0; i < ws.length; i++) ws[i] = new DenseVector(D.getNumNumericalVars()); Optimizer optimizerToUse; if(optimizer == null) optimizerToUse = new LBFGS(10); else optimizerToUse = optimizer.clone(); doWarmStartIfNotNull(warmSolution); ExecutorService threadPool = ParallelUtils.getNewExecutor(parallel); if(ws.length == 1) { if(useBiasTerm) { //Special wrapper class that will handle it - tight coupling with the implementation of LossFun and GradFunc Vec w_tmp = new VecWithBias(ws[0], bs); optimizerToUse.optimize(tolerance, w_tmp, w_tmp, new LossFunction(D, loss), new GradFunction(D, loss), parallel); } else optimizerToUse.optimize(tolerance, ws[0], ws[0], new LossFunction(D, loss), new GradFunction(D, loss), parallel); } else { LossMC lossMC = (LossMC) loss; ConcatenatedVec wAll; if(useBiasTerm)//append bias terms and logic in the Loss and Grad functions wil handle it { ArrayList vecs = new ArrayList<>(Arrays.asList(ws)); vecs.add(DenseVector.toDenseVec(bs)); wAll = new ConcatenatedVec(vecs); } else wAll = new ConcatenatedVec(Arrays.asList(ws)); optimizerToUse.optimize(tolerance, wAll, new DenseVector(wAll), new LossMCFunction(D, lossMC), new GradMCFunction(D, lossMC), parallel); } threadPool.shutdownNow(); } /** * Performs a warm start if the given object is of the appropriate class. * Nothing happens if input it null. * * @param warmSolution * @throws FailedToFitException */ private void doWarmStartIfNotNull(Object warmSolution) throws FailedToFitException { if(warmSolution != null ) { if(warmSolution instanceof SimpleWeightVectorModel) { SimpleWeightVectorModel warm = (SimpleWeightVectorModel) warmSolution; if(warm.numWeightsVecs() != ws.length) throw new FailedToFitException("Warm solution has " + warm.numWeightsVecs() + " weight vectors instead of " + ws.length); for(int i = 0; i < ws.length; i++) { warm.getRawWeight(i).copyTo(ws[i]); if(useBiasTerm) bs[i] = warm.getBias(i); } } else throw new FailedToFitException("Can not warm warm from " + warmSolution.getClass().getCanonicalName()); } } @Override public void train(RegressionDataSet D, boolean parallel) { train(D, this, parallel); } @Override public void train(RegressionDataSet dataSet, Regressor warmSolution) { train(dataSet, warmSolution, false); } @Override public void train(RegressionDataSet D, Regressor warmSolution, boolean parallel) { if(D.getNumNumericalVars() <= 0) throw new FailedToFitException("LinearBath requires numeric features to work"); if(!(loss instanceof LossR)) throw new FailedToFitException("Loss function " + loss.getClass().getSimpleName() + " does not regression"); ws = new Vec[]{ new DenseVector(D.getNumNumericalVars()) }; bs = new double[1]; Optimizer optimizerToUse; if(optimizer == null) optimizerToUse = new LBFGS(10); else optimizerToUse = optimizer.clone(); doWarmStartIfNotNull(warmSolution); ExecutorService threadPool = ParallelUtils.getNewExecutor(parallel); if(useBiasTerm) { Vec w_tmp = new VecWithBias(ws[0], bs); optimizerToUse.optimize(tolerance, w_tmp, w_tmp, new LossFunction(D, loss), new GradFunction(D, loss), parallel); } else optimizerToUse.optimize(tolerance, ws[0], ws[0], new LossFunction(D, loss), new GradFunction(D, loss), parallel); threadPool.shutdownNow(); } private static double getTargetY(DataSet D, int i) { double y; if (D instanceof ClassificationDataSet) y = ((ClassificationDataSet) D).getDataPointCategory(i) * 2 - 1; else y = ((RegressionDataSet) D).getTargetValue(i); return y; } @Override public boolean warmFromSameDataOnly() { return false; } @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; } private class VecWithBias extends Vec { public Vec w; public double[] b; public VecWithBias(Vec w, double[] b) { this.w = w; this.b = b; } //2 hacks below to make the original code work with bias terms "transparently" This means we need to know which functions will be called with a miss-matched size @Override public double dot(Vec v) { if(v.length() == w.length()) return w.dot(v)+b[0]; return super.dot(v); } @Override public void mutableAdd(double c, Vec b) { if(b.length() == w.length()) { w.mutableAdd(c, b); this.b[0] += c; } else super.mutableAdd(c, b); } @Override public int length() { return w.length()+1; } @Override public double get(int index) { if(index < w.length()) return w.get(index); else if (index == w.length()) return b[0]; else throw new IndexOutOfBoundsException(); } @Override public void set(int index, double val) { if(index < w.length()) w.set(index, val); else if (index == w.length()) b[0] = val; else throw new IndexOutOfBoundsException(); } @Override public boolean isSparse() { return w.isSparse(); } @Override public Vec clone() { return new VecWithBias(w.clone(), Arrays.copyOf(b, b.length)); } } /** * Function for using the single weight vector loss functions related to * {@link LossC} and {@link LossR}. */ public class LossFunction implements Function { private static final long serialVersionUID = -576682206943283356L; private final DataSet D; private final LossFunc loss; public LossFunction(DataSet D, LossFunc loss) { this.D = D; this.loss = loss; } @Override public double f(Vec w, boolean parallel) { DoubleAdder sum = new DoubleAdder(); DoubleAdder weightSum = new DoubleAdder(); ParallelUtils.run(parallel, D.getSampleSize(), (start, end)-> { for(int i = start; i < end; i++) { DataPoint dp = D.getDataPoint(i); Vec x = dp.getNumericalValues(); double y = getTargetY(D, i); sum.add(loss.getLoss(w.dot(x), y)*dp.getWeight()); weightSum.add(dp.getWeight()); } }); if(lambda0 > 0) return sum.sum()/weightSum.sum() + lambda0*w.dot(w); else return sum.sum()/weightSum.sum(); } } /** * Function for using the single weight vector loss functions related to * {@link LossC} and {@link LossR} */ public class GradFunction implements FunctionVec { private final DataSet D; private final LossFunc loss; private ThreadLocal tempVecs; public GradFunction(DataSet D, LossFunc loss) { this.D = D; this.loss = loss; } @Override public Vec f(Vec w, Vec s, boolean parallel) { if(s == null) s = w.clone(); s.zeroOut(); DoubleAdder weightSum = new DoubleAdder(); ThreadLocal tl_s = ThreadLocal.withInitial(s::clone); ParallelUtils.run(parallel, D.getSampleSize(), (start, end)-> { Vec s_l = tl_s.get(); for (int i = start; i < end; i++) { DataPoint dp = D.getDataPoint(i); Vec x = dp.getNumericalValues(); double y = getTargetY(D, i); s_l.mutableAdd(loss.getDeriv(w.dot(x), y)*dp.getWeight(), x); weightSum.add(dp.getWeight()); } return s_l; }, (a,b)->a.add(b)) .copyTo(s); s.mutableDivide(weightSum.sum()); if(lambda0 > 0) s.mutableSubtract(lambda0, w); return s; } } public class LossMCFunction implements Function { private static final long serialVersionUID = -861700500356609563L; private final ClassificationDataSet D; private final LossMC loss; public LossMCFunction(ClassificationDataSet D, LossMC loss) { this.D = D; this.loss = loss; } @Override public double f(Vec w, boolean parallel) { DoubleAdder sum = new DoubleAdder(); Vec pred = new DenseVector(D.getClassSize());//store the predictions in //bias terms are at the end, treat them seperate and special final int subWSize = (w.length() - (useBiasTerm ? bs.length : 0) )/D.getClassSize(); DoubleAdder weightSum = new DoubleAdder(); ParallelUtils.run(parallel, D.getSampleSize(), (start, end)-> { Vec pred_local = pred.clone(); for (int i = start; i < end; i++) { DataPoint dp = D.getDataPoint(i); Vec x = dp.getNumericalValues(); for(int k = 0; k < pred_local.length(); k++) pred_local.set(k, new SubVector(k*subWSize, subWSize, w).dot(x)); if(useBiasTerm) pred_local.mutableAdd(new SubVector(w.length()-bs.length, bs.length, w)); loss.process(pred_local, pred_local); int y = D.getDataPointCategory(i); sum.add(loss.getLoss(pred_local, y)*dp.getWeight()); weightSum.add(dp.getWeight()); } }); if(lambda0 > 0 ) return sum.sum()/weightSum.sum() + lambda0*w.dot(w); return sum.sum(); } } private class GradMCFunction implements FunctionVec { private final ClassificationDataSet D; private final LossMC loss; private ThreadLocal tempVecs; public GradMCFunction(ClassificationDataSet D, LossMC loss) { this.D = D; this.loss = loss; } @Override public Vec f(Vec w, Vec s, boolean parllel) { if(s == null) s = w.clone(); s.zeroOut(); ThreadLocal tl_s = ThreadLocal.withInitial(s::clone); Vec pred = new DenseVector(D.getClassSize());//store the predictions in final int subWSize = (w.length() - (useBiasTerm ? bs.length : 0) )/D.getClassSize(); DoubleAdder weightSum = new DoubleAdder(); ParallelUtils.run(parllel, D.getSampleSize(), (start, end)-> { Vec s_l = tl_s.get(); Vec pred_local = pred.clone(); for (int i = start; i < end; i++) { DataPoint dp = D.getDataPoint(i); Vec x = dp.getNumericalValues(); for(int k = 0; k < pred_local.length(); k++) pred_local.set(k, new SubVector(k*subWSize, subWSize, w).dot(x)); if(useBiasTerm) pred_local.mutableAdd(new SubVector(w.length()-bs.length, bs.length, w)); loss.process(pred_local, pred_local); int y = D.getDataPointCategory(i); loss.deriv(pred_local, pred_local, y); for(int k = 0; k < pred_local.length(); k++) new SubVector(k*subWSize, subWSize, s_l).mutableAdd(pred_local.get(k)*dp.getWeight(), x); weightSum.add(dp.getWeight()); } return s_l; }, (a,b)->a.add(b)).copyTo(s); s.mutableDivide(weightSum.sum()); if(lambda0 > 0) s.mutableSubtract(lambda0, w); return s; } } @Override public boolean supportsWeightedData() { return true; } @Override public LinearBatch clone() { return new LinearBatch(this); } /** * 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); } }

Ads help maintain this website.