package jsat.classifiers.svm;

import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.SingleWeightVectorModel;
import jsat.classifiers.*;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.Distribution;
import jsat.distributions.Gamma;
import jsat.distributions.LogUniform;
import jsat.exceptions.FailedToFitException;
import jsat.linear.*;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.IntList;
import jsat.utils.ListUtils;

/**
 * Implements the linear kernel mini-batch version of the Pegasos SVM 
 * classifier. It performs updates stochastically and is very fast. 
* Because Pegasos updates the primal directly, there are no support vectors * saved from the training set. *

* See: Shalev-Shwartz, S., Singer, Y.,&Srebro, N. (2007). Pegasos : Primal * Estimated sub-GrAdient SOlver for SVM. 24th international conference on * Machine learning (pp. 807–814). New York, NY: ACM. * doi:10.1145/1273496.1273598 * * @author Edward Raff */ public class Pegasos implements BinaryScoreClassifier, Parameterized, SingleWeightVectorModel { private static final long serialVersionUID = -2145631476467081171L; private int epochs; private double reg; private int batchSize; private boolean projectionStep = false; private Vec w; private double bias; /** * The default number of epochs is {@value #DEFAULT_EPOCHS} */ public static final int DEFAULT_EPOCHS = 5; /** * The default regularization value is {@value #DEFAULT_REG} */ public static final double DEFAULT_REG = 1e-4; /** * The default batch size is {@value #DEFAULT_BATCH_SIZE} */ public static final int DEFAULT_BATCH_SIZE = 1; /** * Creates a new Pegasos SVM classifier using default values. */ public Pegasos() { this(DEFAULT_EPOCHS, DEFAULT_REG, DEFAULT_BATCH_SIZE); } /** * Creates a new Pegasos SVM classifier * @param epochs the number of training iterations * @param reg the regularization term * @param batchSize the batch size */ public Pegasos(int epochs, double reg, int batchSize) { setEpochs(epochs); setRegularization(reg); setBatchSize(batchSize); } /** * Copy constructor * @param toCopy the object to copy */ public Pegasos(Pegasos toCopy) { this.epochs = toCopy.epochs; this.reg = toCopy.reg; this.batchSize = toCopy.batchSize; if(toCopy.w != null) this.w = toCopy.w.clone(); this.bias = toCopy.bias; this.projectionStep = toCopy.projectionStep; } /** * Sets the batch size used during training. At each epoch, a batch of * randomly selected data points will be used to update. * * @param batchSize the number of data points to use when updating */ public void setBatchSize(int batchSize) { if(batchSize < 1) throw new ArithmeticException("At least one sample must be take at each iteration"); this.batchSize = batchSize; } /** * Returns the number of points used in each iteration * @return the number of points used in each iteration */ public int getBatchSize() { return batchSize; } /** * Sets the number of iterations through the training set that will be * performed. * @param epochs the number of iterations */ public void setEpochs(int epochs) { if(epochs < 1) throw new ArithmeticException("Must perform a positive number of epochs"); this.epochs = epochs; } /** * Returns the number of iterations of updating that will be done * @return the number of iterations */ public double getEpochs() { return epochs; } /** * Sets whether or not to use the projection step after each update per * iteration * * @param projectionStep whether or not to use the projection step */ public void setProjectionStep(boolean projectionStep) { this.projectionStep = projectionStep; } /** * Returns whether or not the projection step is in use after each iteration * @return true if the projection step will be performed */ public boolean isProjectionStep() { return projectionStep; } /** * Sets the regularization constant used for learning. The regularization * must be positive, and the learning rate is proportional to the * regularization value. This means regularizations very near zero will * take a long time to converge. * * @param reg the regularization to apply */ public void setRegularization(double reg) { if(Double.isInfinite(reg) || Double.isNaN(reg) || reg <= 0.0) throw new ArithmeticException("Pegasos requires a positive regularization cosntant"); this.reg = reg; } /** * Returns the amount of regularization to used in training * @return the regularization parameter. */ public double getRegularization() { return reg; } @Override public Vec getRawWeight() { return w; } @Override public double getBias() { return bias; } @Override public Vec getRawWeight(int index) { if(index < 1) return getRawWeight(); else throw new IndexOutOfBoundsException("Model has only 1 weight vector"); } @Override public double getBias(int index) { if (index < 1) return getBias(); else throw new IndexOutOfBoundsException("Model has only 1 weight vector"); } @Override public int numWeightsVecs() { return 1; } @Override public Pegasos clone() { return new Pegasos(this); } @Override public CategoricalResults classify(DataPoint data) { CategoricalResults cr = new CategoricalResults(2); if(getScore(data) < 0) cr.setProb(0, 1.0); else cr.setProb(1, 1.0); return cr; } @Override public double getScore(DataPoint dp) { return w.dot(dp.getNumericalValues())+bias; } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(ClassificationDataSet dataSet) { if(dataSet.getClassSize() != 2) throw new FailedToFitException("SVM only supports binary classificaiton problems"); final int m = dataSet.getSampleSize(); w = new DenseVector(dataSet.getNumNumericalVars()); if(projectionStep) w = new VecWithNorm(w, 0.0); w = new ScaledVector(w); bias = 0; IntList miniBatch = new IntList(batchSize); IntList randOrder = new IntList(m); ListUtils.addRange(randOrder, 0, m, 1); int t = 0; for (int epoch = 0; epoch < epochs; epoch++)//start at 1 for convinence { Collections.shuffle(randOrder); for (int indx = 0; indx < m; indx += batchSize) { t++; miniBatch.clear(); miniBatch.addAll(randOrder.subList(indx, Math.min(indx+batchSize, m))); //Filter to only the points that have the correct label Iterator iter = miniBatch.iterator(); while (iter.hasNext()) { int i = iter.next(); if (getSign(dataSet, i) * (w.dot(getX(dataSet, i)) + bias) >= 1) iter.remove(); } final double nt = 1.0 / (reg * t); w.mutableMultiply(1.0 - nt * reg); for (int i : miniBatch) { double sign = getSign(dataSet, i); Vec x = getX(dataSet, i); final double s = sign * nt /batchSize; w.mutableAdd(s, x); bias += s; } if (projectionStep) { double norm = w.pNorm(2); double mult = Math.min(1, 1.0 / (Math.sqrt(reg) * norm)); w.mutableMultiply(mult); bias *= mult; } } } } @Override public boolean supportsWeightedData() { return false; } private Vec getX(ClassificationDataSet dataSet, int i) { return dataSet.getDataPoint(i).getNumericalValues(); } private double getSign(ClassificationDataSet dataSet, int i) { return dataSet.getDataPointCategory(i) == 1 ? 1.0 : -1.0; } /** * Guess the distribution to use for the regularization term * {@link #setRegularization(double) } in Pegasos. * * @param d the data set to get the guess for * @return the guess for the λ parameter */ public static Distribution guessRegularization(DataSet d) { return new LogUniform(1e-7, 1e-2); } }

Ads help maintain this website.