package jsat.classifiers.neuralnetwork;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.atomic.AtomicIntegerArray;

import jsat.DataSet;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.svm.DCDs;
import jsat.clustering.kmeans.HamerlyKMeans;
import jsat.clustering.SeedSelectionMethods;
import jsat.datatransform.DataTransform;
import jsat.distributions.Distribution;
import jsat.distributions.Uniform;
import jsat.distributions.discrete.UniformDiscrete;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.SparseVector;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.distancemetrics.MahalanobisDistance;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.BoundedSortedList;
import jsat.utils.DoubleList;
import jsat.utils.IntSet;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * This provides a highly configurable implementation of a Radial Basis Function
 * Neural Network. A RBF network is a type of neural network that contains one
 * hidden layer, and is related to the {@link LVQ} algorithm. In a classical RBF
 * Network, the distance between two data points is generally the
 * {@link EuclideanDistance} or {@link MahalanobisDistance}. This implementation
 * allows the specification of any arbitrary distance metric. 
*
* Another restriction on classical RBF Nets is that a weighted sum of the * output of the hidden units be used to make the final decision. Instead this * implementation allows the specification of an arbitrary Classifier or * Regressor to estimate the outputs based on the hidden unit activations. * Whether or not the predictor supports Classification, Regression, and what * classification features it supports - will determine what the RBF Network * supports. This allows for models technically more complicated and powerful * than the standard RBF network.
*
* The initial phases of a RBF Network is to learn the neuron locations and * activations. This part can also be seen as learning a data transformation. As * such, the RBF Network can be used as a DataTransform itself.
* The last phase of the network is to learn the model based on the data point * activations.
*
* It is highly recommended to use a base learning method that can efficiently * use sparse vectors. * * @author Edward Raff */ public class RBFNet implements Classifier, Regressor, DataTransform, Parameterized { private static final long serialVersionUID = 5418896646203518062L; private int numCentroids; private Phase1Learner p1l; private Phase2Learner p2l; private double alpha; private int p; private DistanceMetric dm; private boolean normalize = true; private Classifier baseClassifier; private Regressor baseRegressor; private List centroidDistCache; private List centroids; private double[] bandwidths; /** * Creates a new RBF Network suitable for binary classification or * regression and uses 100 hidden nodes. One of the other constructors * should be used if you need classification for multi-class or if you need * probability outputs.
*
* This will use {@link Phase1Learner#K_MEANS} for neuron selection and * {@link Phase2Learner#NEAREST_OTHER_CENTROID_AVERAGE} for activation * tuning. The {@link EuclideanDistance} will be use as the metric. * */ public RBFNet() { this(100); } /** * Creates a new RBF Network suitable for binary classification or * regression. One of the other constructors should be used if you need * classification for multi-class or if you need probability outputs.
*
* This will use {@link Phase1Learner#K_MEANS} for neuron selection and * {@link Phase2Learner#NEAREST_OTHER_CENTROID_AVERAGE} for activation tuning. * The {@link EuclideanDistance} will be use as the metric. * * @param numCentroids the number of centroids or neurons to use in the * network's hidden layer */ public RBFNet(int numCentroids) { this(numCentroids, Phase1Learner.K_MEANS, Phase2Learner.NEAREST_OTHER_CENTROID_AVERAGE, 3, 3, new EuclideanDistance(), (Classifier) new DCDs()); } /** * Creates a new RBF Network for classification tasks. If the classifier can * also perform regression, then the network will be able to perform both. * * @param numCentroids the number of centroids or neurons to use in the * network's hidden layer * @param cl the method to learn the neuron locations * @param bl the method to learn the neuron activations * @param alpha a parameter that may have an effect on the neuron activation * learning method. * @param p a parameter that may have an effect on the neuron activation * learning method * @param dm the distance metric to use * @param baseClassifier the base classifier to learn on top of the hidden * layer activations. */ public RBFNet(int numCentroids, Phase1Learner cl, Phase2Learner bl, double alpha, int p, DistanceMetric dm, Classifier baseClassifier) { setNumCentroids(numCentroids); setPhase1Learner(cl); setPhase2Learner(bl); setAlpha(alpha); setP(p); setDistanceMetric(dm); this.baseClassifier = baseClassifier; if(baseClassifier instanceof Regressor) baseRegressor = (Regressor) baseClassifier; } /** * Creates a new RBF Network for regression tasks. If the regressor can * also perform classification, then the network will be able to perform * both. * * @param numCentroids the number of centroids or neurons to use in the * network's hidden layer * @param cl the method to learn the neuron locations * @param bl the method to learn the neuron activations * @param alpha a parameter that may have an effect on the neuron activation * learning method. * @param p a parameter that may have an effect on the neuron activation * learning method * @param dm the distance metric to use * @param baseRegressor the base regressor to learn on op of the hidden * layer activations. */ public RBFNet(int numCentroids, Phase1Learner cl, Phase2Learner bl, double alpha, int p, DistanceMetric dm, Regressor baseRegressor) { setNumCentroids(numCentroids); setPhase1Learner(cl); setPhase2Learner(bl); setAlpha(alpha); setP(p); setDistanceMetric(dm); this.baseRegressor = baseRegressor; if(baseRegressor instanceof Classifier) baseClassifier = (Classifier) baseRegressor; } /** * Copy constructor * @param toCopy the network to copy */ public RBFNet(RBFNet toCopy) { setNumCentroids(toCopy.getNumCentroids()); setPhase1Learner(toCopy.getPhase1Learner()); setPhase2Learner(toCopy.getPhase2Learner()); setAlpha(toCopy.getAlpha()); setP(toCopy.getP()); setDistanceMetric(toCopy.getDistanceMetric().clone()); if(toCopy.baseRegressor != null) { this.baseRegressor = toCopy.baseRegressor.clone(); if(baseRegressor instanceof Classifier) baseClassifier = (Classifier) baseRegressor; } else if(toCopy.baseClassifier != null) { this.baseClassifier = toCopy.baseClassifier.clone(); if(baseClassifier instanceof Regressor) baseRegressor = (Regressor) baseClassifier; } if(toCopy.centroids != null) { this.centroids = new ArrayList(toCopy.centroids.size()); for(Vec v : toCopy.centroids) this.centroids.add(v.clone()); if(toCopy.centroidDistCache != null) this.centroidDistCache = new DoubleList(toCopy.centroidDistCache); } if(toCopy.bandwidths != null) this.bandwidths = Arrays.copyOf(toCopy.bandwidths, toCopy.bandwidths.length); } @Override public DataPoint transform(DataPoint dp) { final Vec x = dp.getNumericalValues(); final List qi = dm.getQueryInfo(x); Vec sv = new SparseVector(numCentroids); double sum = 0; /* * Keep track of the highest activation in case none of the neurons have * a numericaly stable activation value. if this occurs we will do our * best by simply setting the one largest activation */ double maxActivation = Double.NEGATIVE_INFINITY; int highestNeuron = -1; for(int i = 0; i < centroids.size(); i++) { double dist = dm.dist(i, x, qi, centroids, centroidDistCache); double sig = bandwidths[i]; double activation = Math.exp(-(dist*dist)/(sig*sig*2)); if(activation > maxActivation) { maxActivation = activation; highestNeuron = i; } if(activation > 1e-16) { sv.set(i, activation); sum += activation; } } if(sv.nnz() == 0)//no activations { sv.set(highestNeuron, maxActivation); sum = maxActivation; } if(normalize && sum != 0.0)//-0.0 not an issue with rbf kernel sv.mutableDivide(sum); if(sv.nnz() > sv.length()/2)//at this point we would be using more memory than needed. Just switch to dense sv = new DenseVector(sv); return new DataPoint(sv, dp.getCategoricalValues(), dp.getCategoricalData(), dp.getWeight()); } /** * The first phase of learning a RBF Neural Network is to determine the * neuron locations. This enum controls which method is used. */ public static enum Phase1Learner { /** * Selects the Neurons at random from the training data */ RANDOM { @Override protected List getCentroids(DataSet data, int centroids, DistanceMetric dm, boolean parallel) { Random rand = RandomUtil.getRandom(); List toRet = new ArrayList<>(); Set points = new IntSet(); while (points.size() < centroids) points.add(rand.nextInt(data.getSampleSize())); for (int i : points) toRet.add(data.getDataPoint(i).getNumericalValues()); return toRet; } }, /** * Selects the Neurons by performing k-Means clustering on the data */ K_MEANS { @Override protected List getCentroids(DataSet data, int centroids, DistanceMetric dm, boolean parallel) { HamerlyKMeans kmeans = new HamerlyKMeans(dm, SeedSelectionMethods.SeedSelection.KPP); kmeans.cluster(data, centroids, parallel); return kmeans.getMeans(); } }; /** * Obtains the centroids for the given data set * @param data the data set to get the centroids for * @param centroids the number of centroids to obtain * @param dm the distance metric that is being used * @param parallel the source of threads for parallel computation * @return the java.util.List */ abstract protected List getCentroids(DataSet data, int centroids, DistanceMetric dm, boolean parallel); } /** * The second phase of learning a RBF Neural Network is to determine how the * neurons are activated to produce the output of the hidden layer. This * enum control which method is used. */ public static enum Phase2Learner { /** * This method sets the bandwidth for each neuron based on the distances * to the neuron from each data point that is closest to said neuron. If * μ is the average distance to the neuron, and σ the standard * deviation, then the bandwidth b of the j'th neuron is * seto to bj = μj + * {@link #setAlpha(double) α} σj */ CENTROID_DISTANCE { @Override protected double[] estimateBandwidths(double alpha, int p, DataSet data, final List centroids, final List centroidDistCache, final DistanceMetric dm, ExecutorService threadpool) { final double[] bandwidths = new double[centroids.size()]; final OnLineStatistics[] averages = new OnLineStatistics[bandwidths.length]; for(int i = 0; i < averages.length; i++) averages[i] = new OnLineStatistics(); List X = data.getDataVectors(); ParallelUtils.run(true, data.getSampleSize(), (start, end) -> { final OnLineStatistics[] localAverages = new OnLineStatistics[bandwidths.length]; for (int i = 0; i < localAverages.length; i++) localAverages[i] = new OnLineStatistics(); for (int z = start; z < end; z++) { Vec x = X.get(z); double minDist = Double.POSITIVE_INFINITY; int minI = 0; for (int i = 0; i < centroids.size(); i++) { double dist = dm.dist(i, x, centroids, centroidDistCache); if (dist < minDist) { minDist = dist; minI = i; } } localAverages[minI].add(minDist); } synchronized(averages) { for (int i = 0; i < localAverages.length; i++) { if (localAverages[i].getSumOfWeights() == 0) continue; averages[i] = OnLineStatistics.add(averages[i], localAverages[i]); } } }, threadpool); for (int i = 0; i < bandwidths.length; i++) bandwidths[i] = averages[i].getMean() + averages[i].getStandardDeviation() * alpha; return bandwidths; } }, /** * This bandwidth estimator only works for classification problems. Each * neuron is assigned a class based on the majority class labels of the * data points closes to said neuron. The bandwidth is then estimated as * {@link #setAlpha(double) α} times the distance from the neuron * to the closest neuron with a different class label.
*
* For this method α values between (0, 1) usually work best, 0.25 is a * good starting value. The value of α can go past 1. */ CLOSEST_OPPOSITE_CENTROID { @Override protected double[] estimateBandwidths(final double alpha, int p, DataSet data, final List centroids, final List centroidDistCache, final DistanceMetric dm, ExecutorService threadpool) { final ClassificationDataSet cds; if(data instanceof ClassificationDataSet ) cds = (ClassificationDataSet) data; else throw new FailedToFitException("CLOSEST_OPPOSITE_CENTROID only works for classification data sets"); final double[] bandwidths = new double[centroids.size()]; /** * An array of arrays. Each centroid gets its own atomic array, * where each value indicates how many objects of class is stored. */ final AtomicIntegerArray[] classLabels = new AtomicIntegerArray[centroids.size()]; for(int i =0; i < classLabels.length; i++) classLabels[i] = new AtomicIntegerArray(cds.getClassSize()); ParallelUtils.run(true, data.getSampleSize(), (start, end)-> { for(int id = start; id < end; id++) { final Vec x = cds.getDataPoint(id).getNumericalValues(); double minDist = Double.POSITIVE_INFINITY; int minI = 0; for (int i = 0; i < centroids.size(); i++) { double dist = dm.dist(i, x, centroids, centroidDistCache); if (dist < minDist) { minDist = dist; minI = i; } } classLabels[minI].incrementAndGet(cds.getDataPointCategory(id)); } }, threadpool); //Figure out the class label for each neuron final int[] neuronClass = new int[centroids.size()]; for(int i = 0; i < neuronClass.length; i++) { int maxVal = -1; int maxClass = 0; for(int j = 0; j < classLabels[i].length(); j++) { if(classLabels[i].get(j) > maxVal) { maxClass = j; maxVal = classLabels[i].get(j); } } neuronClass[i] = maxClass; } //Now set the bandwidth based on the distance to the nearest centroid with a different class label ParallelUtils.run(true, centroids.size(), (center) -> { double minDist = Double.POSITIVE_INFINITY; for (int i = 0; i < centroids.size(); i++) if (neuronClass[center] != neuronClass[i])//dont check for ourselves b/c we have the same class as ourselves, so no need minDist = Math.min(minDist, dm.dist(i, center, centroids, centroidDistCache)); if (Double.isInfinite(minDist))//possible if there is high class imbalance, run again but lie for (int i = 0; i < centroids.size(); i++) if (center != i) minDist = Math.min(minDist, dm.dist(i, center, centroids, centroidDistCache)); bandwidths[center] = alpha * minDist; }, threadpool); return bandwidths; } }, /** * This method sets the bandwidth for each neuron based on the average * distance of the {@link #setP(int) p} nearest neurons. The number of * standard deviations to add to the activation is controlled by * {@link #setAlpha(double) α} */ NEAREST_OTHER_CENTROID_AVERAGE { @Override protected double[] estimateBandwidths(final double alpha, final int p, DataSet data, final List centroids, final List centroidDistCache, final DistanceMetric dm, ExecutorService threadpool) { final double[] bandwidths = new double[centroids.size()]; final CountDownLatch latch = new CountDownLatch(centroids.size()); ParallelUtils.run(true, centroids.size(), (center)-> { BoundedSortedList closestDistances = new BoundedSortedList<>(p); for (int i = 0; i < centroids.size(); i++) if (i != center) closestDistances.add(dm.dist(i, center, centroids, centroidDistCache)); OnLineStatistics stats = new OnLineStatistics(); for (double dist : closestDistances) stats.add(dist); bandwidths[center] = stats.getMean() + alpha * stats.getStandardDeviation(); }, threadpool); return bandwidths; } }; abstract protected double[] estimateBandwidths(double alpha, int p, final DataSet data, final List centroids, final List centroidDistCache, final DistanceMetric dm, ExecutorService threadpool); } /** * Sets the alpha parameter. This value is used for certain * {@link Phase2Learner} learners as a parameter. A good default value for * most methods is often 1 or 3. However the parameter must always be * a non-negative value. * * @param alpha a non negative value that controls the width of the learned * bandwidths. */ public void setAlpha(double alpha) { if(alpha < 0 || Double.isInfinite(alpha) || Double.isNaN(alpha)) throw new IllegalArgumentException("Alpha must be a positive value, not " + alpha); this.alpha = alpha; } /** * Returns the alpha bandwidth learning parameter * @return the alpha bandwidth learning parameter * @see #setAlpha(double) */ public double getAlpha() { return alpha; } /** * Guesses the distribution for the {@link #setAlpha(double) } parameter * @param data the data to create a guess for * @return a guess for the distribution of the Alpha parameter */ public static Distribution guessAlpha(DataSet data) { return new Uniform(0.8, 3.5); } /** * Sets the nearest neighbor parameter. This value is used for certain * {@link Phase2Learner} learners as a parameter. It is used to control the * number of neighbors taken into account in learning the parameter value. * It must always be a positive value. 3 is usually a good value for * this parameter. * * @param p the positive integer used that controls the width of the learned * bandwidths */ public void setP(int p) { if(p < 1) throw new IllegalArgumentException("neighbors parameter must be positive, not "+p); this.p = p; } /** * Returns the nearest neighbors parameter. * @return the nearest neighbors parameter. * @see #setP(int) */ public int getP() { return p; } /** * Guesses the distribution for the {@link #setP(int) } parameter * @param data the data to create a guess for * @return a guess for the distribution of the P parameter */ public static Distribution guessP(DataSet data) { return new UniformDiscrete(2, 5); } /** * Sets the number of centroids to learn for this model. Increasing the * number of centroids increases the complexity of the model as well as * training and evaluation time. The centroids serve as the hidden units in * the network. *

* The centroids learned are controlled via the * {@link #setPhase1Learner(jsat.classifiers.neuralnetwork.RBFNet.Phase1Learner)} * method * * @param numCentroids the number of centroids to use in the model */ public void setNumCentroids(int numCentroids) { if(numCentroids < 1) throw new IllegalArgumentException("Number of centroids must be positive, not " + numCentroids); this.numCentroids = numCentroids; } /** * Returns the number of centroids to use when training * @return * Returns the number of centroids to use when training */ public int getNumCentroids() { return numCentroids; } /** * Guesses the distribution for the {@link #setNumCentroids(int) } parameter * @param data the data to create a guess for * @return a guess for the distribution of the number of centroids to use */ public static Distribution guessNumCentroids(DataSet data) { return new UniformDiscrete(25, 1000);//maybe change in the future } /** * Sets the distance metric used to determine neuron activations. * @param dm the distance metric to use */ public void setDistanceMetric(DistanceMetric dm) { this.dm = dm; } /** * Returns the distance metric in use * @return the distance metric in use */ public DistanceMetric getDistanceMetric() { return dm; } /** * Sets the method used for learning the centroids (or hidden units) of the * network. * * @param p1l the learning method to use */ public void setPhase1Learner(Phase1Learner p1l) { this.p1l = p1l; } /** * Returns the method to use for learning the centroids of the network. * * @return the method to use for learning the centroids of the network. */ public Phase1Learner getPhase1Learner() { return p1l; } /** * Sets the method used for learning the bandwidths for each centroid in the * network. Depending on the method used, {@link #setAlpha(double) } or * {@link #setP(int)} may impact the learned bandwidths. * * @param p2l the learning method to use */ public void setPhase2Learner(Phase2Learner p2l) { this.p2l = p2l; } /** * Returns the learning method to use for determining the bandwidths of each * center in the network. * @return the learning method to use for the bandwidths */ public Phase2Learner getPhase2Learner() { return p2l; } /** * Sets whether or not to normalize the outputs of the neurons in the * network so that the activations sum to one. Normalizing the outputs can * increase the generalization ability of the network. By default this is * set to {@code true} * * @param normalize {@code true} to normalize the neuron outputs, * {@code false} to use the raw activation values. */ public void setNormalize(boolean normalize) { this.normalize = normalize; } /** * Returns whether or not the network is currently normalizing its neuron * outputs. * * @return whether or not the neuron outputs are normalized */ public boolean isNormalize() { return normalize; } @Override public CategoricalResults classify(DataPoint data) { return baseClassifier.classify(transform(data)); } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { if(baseClassifier == null) throw new FailedToFitException("RBFNet was not given a base classifier"); ExecutorService threadPool = ParallelUtils.getNewExecutor(parallel); //Learn Centroids centroids = p1l.getCentroids(dataSet, numCentroids, dm, parallel); centroidDistCache = dm.getAccelerationCache(centroids, parallel); //Learn Parameter Values bandwidths = p2l.estimateBandwidths(alpha, p, dataSet, centroids, centroidDistCache, dm, threadPool); //apply transform ClassificationDataSet transformedData = dataSet.shallowClone(); transformedData.applyTransform(this, parallel); //learn final model on transformed inputs baseClassifier.train(transformedData, parallel); } @Override public boolean supportsWeightedData() { if(baseClassifier != null) return baseClassifier.supportsWeightedData(); else return baseRegressor.supportsWeightedData(); } @Override public double regress(DataPoint data) { return baseRegressor.regress(transform(data)); } @Override public void fit(DataSet data) { if (data instanceof ClassificationDataSet) train((ClassificationDataSet) data); else if(data instanceof RegressionDataSet) train((RegressionDataSet) data); else throw new FailedToFitException("Data must be a classifiation or regression dataset, not " + data.getClass().getSimpleName()); } @Override public void train(RegressionDataSet dataSet, boolean parallel) { if(baseRegressor == null) throw new FailedToFitException("RBFNet was not given a base classifier"); ExecutorService threadPool = ParallelUtils.getNewExecutor(parallel); //Learn Centroids centroids = p1l.getCentroids(dataSet, numCentroids, dm, parallel); centroidDistCache = dm.getAccelerationCache(centroids, parallel); //Learn Parameter Values bandwidths = p2l.estimateBandwidths(alpha, p, dataSet, centroids, centroidDistCache, dm, threadPool); //apply transform RegressionDataSet transformedData = dataSet.shallowClone(); transformedData.applyTransform(this, parallel); //learn final model on transformed inputs baseRegressor.train(transformedData, parallel); } @Override public RBFNet clone() { return new RBFNet(this); } }

Ads help maintain this website.