package jsat.classifiers.neuralnetwork;
import java.io.Serializable;
import static java.lang.Math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.distributions.Normal;
import jsat.linear.DenseMatrix;
import jsat.linear.DenseVector;
import jsat.linear.Matrix;
import jsat.linear.Vec;
import jsat.math.Function1D;
import jsat.math.decayrates.DecayRate;
import jsat.math.decayrates.ExponetialDecay;
import jsat.parameters.IntParameter;
import jsat.parameters.ObjectParameter;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;
/**
* An implementation of a Feed Forward Neural Network (NN) trained by Back
* Propagation. NNs are powerful classifiers and regressors, but can suffer from
* slow training time and overfitting.
*
* NOTE: This class should generally not be used any more. The
* {@link DReDNetSimple} provides an easier to use class for most cases that
* will likely converge faster.
*
* @author Edward Raff
*/
public class BackPropagationNet implements Classifier, Regressor, Parameterized
{
private static final long serialVersionUID = 335438198218313862L;
private int inputSize, outputSize;
private ActivationFunction f = softsignActiv;
private DecayRate learningRateDecay = new ExponetialDecay();
private double momentum = 0.1;
private double weightDecay = 0;
private int epochs = 1000;
private double initialLearningRate = 0.2;
private WeightInitialization weightInitialization = WeightInitialization.TANH_NORMALIZED_INITIALIZATION;
private double targetBump = 0.1;
private int batchSize = 10;
/**
* Length of the array determines how many layers of hidden units. Value at
* each index determines how many neurons are in each hidden layer.
*/
private int[] npl;
/**
* Matrix of weights for each hidden layer and output layer
*/
private List Ws;
/**
* Bias terms corresponding to each layer
*/
private List bs;
/**
* Target min and max and scaling multiplier for regression problems to make
* the target into a range that the activation function can reach
*/
private double targetMax, targetMin, targetMultiplier;
/**
* Creates a new back propagation network with one hidden layer of 1024 neurons.
* @param npl the array of hidden layer information. The length indicates
* how many hidden layers, and the value of each index indicates how many
* neurons to place in each hidden layer
*/
public BackPropagationNet()
{
this(1024);
}
/**
* Creates a new back propagation network.
* @param npl the array of hidden layer information. The length indicates
* how many hidden layers, and the value of each index indicates how many
* neurons to place in each hidden layer
*/
public BackPropagationNet(final int... npl )
{
if(npl.length < 1)
throw new IllegalArgumentException("There must be at least one hidden layer");
this.npl = npl;
}
/**
* Copy constructor
* @param toClone the one to copy
*/
protected BackPropagationNet(BackPropagationNet toClone)
{
this(Arrays.copyOf(toClone.npl, toClone.npl.length));
this.inputSize = toClone.inputSize;
this.outputSize = toClone.outputSize;
this.f = toClone.f;
this.momentum = toClone.momentum;
this.weightDecay = toClone.weightDecay;
this.epochs = toClone.epochs;
this.initialLearningRate = toClone.initialLearningRate;
this.learningRateDecay = toClone.learningRateDecay;
this.weightInitialization = toClone.weightInitialization;
this.targetBump = toClone.targetBump;
this.targetMax = toClone.targetMax;
this.targetMin = toClone.targetMin;
this.targetMultiplier = toClone.targetMultiplier;
this.batchSize = toClone.batchSize;
if(toClone.Ws != null)
{
this.Ws = new ArrayList(toClone.Ws);
for(int i = 0; i < this.Ws.size(); i++)
this.Ws.set(i, this.Ws.get(i).clone());
}
if(toClone.bs != null)
{
this.bs = new ArrayList(toClone.bs);
for(int i = 0; i < this.bs.size(); i++)
this.bs.set(i, this.bs.get(i).clone());
}
}
/**
* The main work for training the neural network
* @param dataSet the data set to train from
*/
private void trainNN(DataSet dataSet)
{
//batchSize
List> activations = new ArrayList>(batchSize);
List> derivatives = new ArrayList>(batchSize);
List> deltas = new ArrayList>(batchSize);
List updates = new ArrayList(Ws.size());
List cur_x = new ArrayList(batchSize);
List prev_x = new ArrayList(batchSize);
for(int i = 0; i < batchSize; i++)
{
activations.add(new ArrayList(Ws.size()));
derivatives.add(new ArrayList(Ws.size()));
deltas.add(new ArrayList(Ws.size()));
for(Matrix w : Ws)
{
int L = w.rows();
activations.get(i).add(new DenseVector(L));
derivatives.get(i).add(new DenseVector(L));
deltas.get(i).add(new DenseVector(L));
if(i == 0)
updates.add(new DenseMatrix(w.rows(), w.cols()));
}
}
IntList iterOrder = new IntList(dataSet.getSampleSize());
ListUtils.addRange(iterOrder, 0, dataSet.getSampleSize(), 1);
final double bSizeInv = 1.0/batchSize;
for(int epoch = 0; epoch < epochs; epoch++)
{
Collections.shuffle(iterOrder);
final double eta = learningRateDecay.rate(epoch, epochs, initialLearningRate);//learningRate;
double error = 0.0;
for(int iter = 0; iter < dataSet.getSampleSize(); iter+=batchSize)
{
if(dataSet.getSampleSize() - iter < batchSize)
continue;//we have run out of enough sampels to do an update
cur_x.clear();
//Feed batches thought network and get final mistakes
for(int bi = 0; bi < batchSize; bi++)
{
final int idx = iterOrder.get(iter+bi);
Vec x = dataSet.getDataPoint(idx).getNumericalValues();
cur_x.add(x);
feedForward(x, activations.get(bi), derivatives.get(bi));
//Compution of Deltas
Vec delta_out = deltas.get(bi).get(npl.length);
Vec a_i = activations.get(bi).get(npl.length);
Vec d_i = derivatives.get(bi).get(npl.length);
error += computeOutputDelta(dataSet, idx, delta_out, a_i, d_i);
}
//Propigate the collected errors back
for(int bi = 0; bi < batchSize; bi++)
{
for(int i = Ws.size()-2; i >= 0; i--)
{
Vec delta = deltas.get(bi).get(i);
delta.zeroOut();
Matrix W = Ws.get(i+1);
W.transposeMultiply(1, deltas.get(bi).get(i+1), delta);
delta.mutablePairwiseMultiply(derivatives.get(bi).get(i));
}
//Apply weight changes
for(int i = 1; i < Ws.size(); i++)
{
Matrix W = Ws.get(i);
Vec b = bs.get(i);
W.mutableSubtract(eta*weightDecay, W);
if(momentum != 0)
{
Matrix update = updates.get(i);
update.mutableMultiply(momentum);
Matrix.OuterProductUpdate(update, deltas.get(bi).get(i), activations.get(bi).get(i-1), -eta*bSizeInv);
W.mutableAdd(update);
}
else//update directly
{
Matrix.OuterProductUpdate(W, deltas.get(bi).get(i), activations.get(bi).get(i-1), -eta*bSizeInv);
}
b.mutableAdd(-eta*bSizeInv, deltas.get(bi).get(i));
}
//input layer
Matrix W = Ws.get(0);
W.mutableSubtract(eta*weightDecay, W);
Vec b = bs.get(0);
if(momentum != 0)
{
Matrix update = updates.get(0);
update.mutableMultiply(momentum);
Matrix.OuterProductUpdate(update, deltas.get(bi).get(0), cur_x.get(bi), -eta*bSizeInv);
W.mutableAdd(update);
}
else//update directly
{
Matrix.OuterProductUpdate(W, deltas.get(bi).get(0), cur_x.get(bi), -eta*bSizeInv);
}
b.mutableAdd(-eta*bSizeInv, deltas.get(bi).get(0));
}
}
}
}
/**
* Different methods of initializing the weight values before training
*/
public enum WeightInitialization
{
UNIFORM
{
@Override
public double getWeight(int inputSize, int layerSize, double eta, Random rand)
{
return rand.nextDouble()*1.4-0.7;
}
},
GUASSIAN
{
@Override
public double getWeight(int inputSize, int layerSize, double eta, Random rand)
{
return Normal.invcdf(rand.nextDouble(), 0, pow(inputSize, -0.5));
}
},
TANH_NORMALIZED_INITIALIZATION
{
@Override
public double getWeight(int inputSize, int layerSize, double eta, Random rand)
{
double cnst = sqrt(6.0/(inputSize+layerSize));
return rand.nextDouble()*cnst*2-cnst;
}
};
/**
*
* @param inputSize also referred to as the fanin
* @param layerSize also referred to as the fanout
* @param eta the initial learning rate
* @param rand the source of randomness
* @return one weight value
*/
abstract public double getWeight(int inputSize, int layerSize, double eta, Random rand);
}
/**
* Sets the non negative momentum used in training.
* @param momentum the momentum to apply to training
*/
public void setMomentum(double momentum)
{
if(momentum < 0 || Double.isNaN(momentum) || Double.isInfinite(momentum))
throw new ArithmeticException("Momentum must be non negative, not " + momentum);
this.momentum = momentum;
}
/**
* Returns the momentum in use
* @return the momentum
*/
public double getMomentum()
{
return momentum;
}
/**
* Sets the initial learning rate used for the first epoch
* @param initialLearningRate the positive learning rate to use
*/
public void setInitialLearningRate(double initialLearningRate)
{
if(initialLearningRate <= 0 || Double.isNaN(initialLearningRate) || Double.isInfinite(initialLearningRate))
throw new ArithmeticException("Learning rate must be a positive cosntant, not " + initialLearningRate );
this.initialLearningRate = initialLearningRate;
}
/**
* Returns the learning rate used
* @return the learning rate used
*/
public double getInitialLearningRate()
{
return initialLearningRate;
}
/**
* Sets the decay rate used to adjust the learning rate after each epoch
* @param learningRateDecay the decay for the learning rate
*/
public void setLearningRateDecay(DecayRate learningRateDecay)
{
this.learningRateDecay = learningRateDecay;
}
/**
* Returns the decay rate used to adjust the learning rate after each epoch
* @return the decay rate used for learning
*/
public DecayRate getLearningRateDecay()
{
return learningRateDecay;
}
/**
* Sets the number of epochs of training used. Each epoch goes through the
* whole data set once.
* @param epochs the number of training epochs
*/
public void setEpochs(int epochs)
{
if(epochs < 1)
throw new ArithmeticException("number of training epochs must be positive, not " + epochs);
this.epochs = epochs;
}
/**
* Returns the number of epochs of training epochs for learning
* @return the number of training epochs
*/
public int getEpochs()
{
return epochs;
}
/**
* Sets the weight decay used for each update. The weight decay must be in
* the range [0, 1). Weight decay values must often be very small, often
* 1e-8 or less.
*
* @param weightDecay the weight decay to apply when training
*/
public void setWeightDecay(double weightDecay)
{
if(weightDecay < 0 || weightDecay >= 1 || Double.isNaN(weightDecay))
throw new ArithmeticException("Weight decay must be in [0,1), not " + weightDecay);
this.weightDecay = weightDecay;
}
/**
* Returns the weight decay used for each update
* @return the weight decay used.
*/
public double getWeightDecay()
{
return weightDecay;
}
/**
* Sets how the weights are initialized before training starts
* @param weightInitialization the method of weight initialization
*/
public void setWeightInitialization(WeightInitialization weightInitialization)
{
this.weightInitialization = weightInitialization;
}
/**
* Returns the method of weight initialization used
* @return the method of weight initialization used
*/
public WeightInitialization getWeightInitialization()
{
return weightInitialization;
}
/**
* Sets the batch size use to estimate the gradient of the error for
* training
* @param batchSize the number of training instances to use on each update
*/
public void setBatchSize(int batchSize)
{
this.batchSize = batchSize;
}
/**
* Returns the training batch size
* @return the batch size used for training
*/
public int getBatchSize()
{
return batchSize;
}
/**
* Sets the activation function used for the network
* @param f the activation function to use
*/
public void setActivationFunction(ActivationFunction f)
{
this.f = f;
}
/**
* Returns the activation function used for training the network
* @return the activation function in use
*/
public ActivationFunction getActivationFunction()
{
return f;
}
@Override
public CategoricalResults classify(DataPoint data)
{
CategoricalResults cr = new CategoricalResults(outputSize);
Vec x = feedForward(data.getNumericalValues());
x.mutableSubtract(f.min()+targetBump);
for(int i = 0; i < x.length(); i++)
cr.setProb(i, Math.max(x.get(i), 0));
cr.normalize();
return cr;
}
@Override
public double regress(DataPoint data)
{
Vec x = feedForward(data.getNumericalValues());
double val = x.get(0);
val = (val - f.min()-targetBump)/targetMultiplier+targetMin;
return val;
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(ClassificationDataSet dataSet)
{
inputSize = dataSet.getNumNumericalVars();
outputSize = dataSet.getClassSize();
Random rand = RandomUtil.getRandom();
setUp(rand);
trainNN(dataSet);
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(RegressionDataSet dataSet)
{
targetMax = Double.NEGATIVE_INFINITY;
targetMin = Double.POSITIVE_INFINITY;
for(int i = 0; i < dataSet.getSampleSize(); i++)
{
double val = dataSet.getTargetValue(i);
targetMax = Math.max(targetMax, val);
targetMin = Math.min(targetMin, val);
}
targetMultiplier = ((f.max()-targetBump)-(f.min()+targetBump))/(targetMax-targetMin);
inputSize = dataSet.getNumNumericalVars();
outputSize = 1;
Random rand = RandomUtil.getRandom();
setUp(rand);
trainNN(dataSet);
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public BackPropagationNet clone()
{
return new BackPropagationNet(this);
}
/**
* The neural network needs an activation function for the neurons that is
* used to predict from inputs and train the network by propagating the
* errors back through the network.
*/
public static abstract class ActivationFunction implements Function1D, Serializable
{
private static final long serialVersionUID = 8002040194215453918L;
/**
* Computes the response of the response of this activation function on
* the given input value
* @param x the input value
* @return the response value
*/
abstract public double response(double x);
/**
* The minimum possible response value
* @return the min value
*/
abstract public double min();
/**
* The maximum possible response value
* @return the max value
*/
abstract public double max();
/**
* Returns the function object for the derivative of this activation
* function. The derivative must be calculated using only the output of
* the response when given the original input. Meaning: given an input
* {@code x}, the value of f'(x) must be computable as g(f(x))
*
* @return the function for computing the derivative of the response
*/
abstract public Function1D getD();
@Override
public double f(double x)
{
return response(x);
}
}
/**
* The logit activation function. This function goes from [0, 1]. It has
* more difficultly learning than symmetric activation functions, often
* requiring considerably more layers and neurons than other activation
* functions.
*/
public static final ActivationFunction logitActiv = new ActivationFunction()
{
private static final long serialVersionUID = -5675881412853268432L;
@Override
public double response(double x)
{
return 1 / (1+exp(-x));
}
@Override
public double min()
{
return 0;
}
@Override
public double max()
{
return 1;
}
@Override
public Function1D getD()
{
return logitPrime;
}
@Override
public String toString()
{
return "Logit";
}
};
private static final Function1D logitPrime = (double x) ->
{
return x * (1 - x);
};
/**
* The tanh activation function. This function is symmetric in the range of
* [-1, 1]. It works well for many problems in general.
*/
public static final ActivationFunction tanhActiv = new ActivationFunction()
{
private static final long serialVersionUID = 5531922338473526216L;
@Override
public double response(double x)
{
return tanh(x);
}
@Override
public double min()
{
return -1;
}
@Override
public double max()
{
return 1;
}
@Override
public Function1D getD()
{
return (x)-> 1-x*x;
}
@Override
public String toString()
{
return "Tanh";
}
};
/**
* The softsign activation function. This function is symmetric in the range
* of [-1, 1]. It works well for classification problems, and is very fast
* to compute. It sometimes requires more neurons to learn more complicated
* functions / boundaries. It sometimes has reduced performance in regression
*/
public static final ActivationFunction softsignActiv = new ActivationFunction()
{
private static final long serialVersionUID = 1618447580574194519L;
@Override
public double response(double x)
{
return x/(1.0 + abs(x));
}
@Override
public double min()
{
return -1;
}
@Override
public double max()
{
return 1;
}
@Override
public Function1D getD()
{
return (x) -> Math.pow(1-abs(x), 2);
}
@Override
public String toString()
{
return "Softsign";
}
};
/**
* Creates the weights for the hidden layers and output layer
* @param rand source of randomness
*/
private void setUp(Random rand)
{
Ws = new ArrayList<>(npl.length);
bs = new ArrayList<>(npl.length);
//First Hiden layer takes input raw
DenseMatrix W = new DenseMatrix(npl[0], inputSize);
Vec b = new DenseVector(W.rows());
initializeWeights(W, rand);
initializeWeights(b, W.cols(), rand);
Ws.add(W);
bs.add(b);
//Other Hiden Layers Layers
for(int i = 1; i < npl.length; i++)
{
W = new DenseMatrix(npl[i], npl[i-1]);
b = new DenseVector(W.rows());
initializeWeights(W, rand);
initializeWeights(b, W.cols(), rand);
Ws.add(W);
bs.add(b);
}
//Output layer
W = new DenseMatrix(outputSize, npl[npl.length-1]);
b = new DenseVector(W.rows());
initializeWeights(W, rand);
initializeWeights(b, W.cols(), rand);
Ws.add(W);
bs.add(b);
}
/**
* Computes the delta between the networks output for a same and its true value
* @param dataSet the data set we are learning from
* @param idx the index into the data set for the current data point
* @param delta_out the place to store the delta, may already be initialized with random noise
* @param a_i the activation of the final output layer for the data point
* @param d_i the derivative of the activation of the final output layer
* @return the error that occurred in predicting this data point
*/
private double computeOutputDelta(DataSet dataSet, final int idx, Vec delta_out, Vec a_i, Vec d_i)
{
double error = 0;
if (dataSet instanceof ClassificationDataSet)
{
ClassificationDataSet cds = (ClassificationDataSet) dataSet;
final int ct = cds.getDataPointCategory(idx);
for (int i = 0; i < outputSize; i++)
if (i == ct)
delta_out.set(i, f.max() - targetBump);
else
delta_out.set(i, f.min() + targetBump);
for (int j = 0; j < delta_out.length(); j++)
{
double val = delta_out.get(j);
error += pow((val - a_i.get(j)), 2);
val = -(val - a_i.get(j)) * d_i.get(j);
delta_out.set(j, val);
}
}
else if(dataSet instanceof RegressionDataSet)
{
RegressionDataSet rds = (RegressionDataSet) dataSet;
double val = rds.getTargetValue(idx);
val = f.min()+targetBump + targetMultiplier*(val-targetMin);
error += pow((val - a_i.get(0)), 2);
delta_out.set(0, -(val - a_i.get(0)) * d_i.get(0));
}
else
{
throw new RuntimeException("BUG: please report");
}
return error;
}
/**
* Feeds a vector through the network to get an output
* @param input the input to feed forward though the network
* @param activations the list of allocated vectors to store the activation
* outputs for each layer
* @param derivatives the list of allocated vectors to store the derivatives
* of the activations
*/
private void feedForward(Vec input, List activations, List derivatives)
{
Vec x = input;
for(int i = 0; i < Ws.size(); i++)
{
Matrix W_i = Ws.get(i);
Vec b_i = bs.get(i);
Vec a_i = activations.get(i);
a_i.zeroOut();
W_i.multiply(x, 1, a_i);
a_i.mutableAdd(b_i);
a_i.applyFunction(f);
Vec d_i = derivatives.get(i);
a_i.copyTo(d_i);
d_i.applyFunction(f.getD());
x = a_i;
}
}
/**
* Feeds an input through the network
* @param inputthe input vector to feed in
* @return the output vector for the given input at the final layer
*/
private Vec feedForward(Vec input)
{
Vec x = input;
for(int i = 0; i < Ws.size(); i++)
{
Matrix W_i = Ws.get(i);
Vec b_i = bs.get(i);
Vec a_i = W_i.multiply(x);
a_i.mutableAdd(b_i);
a_i.applyFunction(f);
x = a_i;
}
return x;
}
private void initializeWeights(Matrix W, Random rand)
{
for(int i = 0; i < W.rows(); i++)
for(int j = 0; j < W.cols(); j++)
W.set(i, j, weightInitialization.getWeight(W.cols(), W.rows(), initialLearningRate, rand));
}
private void initializeWeights(Vec b, int inputSize, Random rand)
{
for(int i = 0; i < b.length(); i++)
b.set(i, weightInitialization.getWeight(inputSize, b.length(), initialLearningRate, rand));
}
@Override
public List getParameters()
{
ArrayList params = new ArrayList(Parameter.getParamsFromMethods(this));
for(int i = 0; i < npl.length; i++)
{
final int ii = i;
if(npl[ii] < 1)
throw new ArithmeticException("There must be a poistive number of hidden neurons in each layer");
params.add(new IntParameter()
{
private static final long serialVersionUID = -827784019950722754L;
@Override
public int getValue()
{
return npl[ii];
}
@Override
public boolean setValue(int val)
{
if(val <= 0)
return false;
npl[ii] = val;
return true;
}
@Override
public String getASCIIName()
{
return "Neurons for Hidden Layer " + ii;
}
});
}
params.add(new ObjectParameter()
{
private static final long serialVersionUID = 6871130865935243583L;
@Override
public ActivationFunction getObject()
{
return getActivationFunction();
}
@Override
public boolean setObject(ActivationFunction obj)
{
setActivationFunction(obj);
return true;
}
@Override
public List parameterOptions()
{
return Arrays.asList(logitActiv, tanhActiv, softsignActiv);
}
@Override
public String getASCIIName()
{
return "Activation Function";
}
});
return Collections.unmodifiableList(params);
}
@Override
public Parameter getParameter(String paramName)
{
return Parameter.toParameterMap(getParameters()).get(paramName);
}
}
Ads help maintain this website.