package jsat.classifiers.svm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.kernels.KernelTrick;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.FakeExecutor;
import jsat.utils.ListUtils;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * Implements the kernelized version of the {@link Pegasos} algorithm for SVMs. 
 * Unlike standard SVM algorithms, this one relies on randomness and has no 
 * guarantee to reach the optimal solution, however it is very fast to train. 
 * Each iteration of the algorithm randomly selects one datapoint to potentially 
 * update the coefficient of. 
* The resulting set of support vectors may be more or less sparse than a normal * SVM implementation.
* Because the Pegasos algorithm is stochastic and the kernelized updates on * errors given regularization, the kernelized version may have more difficulty * with noisy or overlapping class distributions. *

* 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 PegasosK extends SupportVectorLearner implements BinaryScoreClassifier, Parameterized { private static final long serialVersionUID = 5405460830472328107L; private double regularization; private int iterations; /** * Creates a new kernelized Pegasos SVM solver * * @param regularization the amount of regularization to apply, normally a very small positive value * @param iterations the number of update iterations to perform * @param kernel the kernel to use */ public PegasosK(double regularization, int iterations, KernelTrick kernel) { this(regularization, iterations, kernel, CacheMode.NONE); } /** * Creates a new kernelized Pegasos SVM solver * * @param regularization the amount of regularization to apply, normally a very small positive value * @param iterations the number of update iterations to perform * @param kernel the kernel to use * @param cacheMode what type of kernel caching to use */ public PegasosK(double regularization, int iterations, KernelTrick kernel, CacheMode cacheMode) { super(kernel, cacheMode); setRegularization(regularization); setIterations(iterations); } /** * Sets the number of iterations of the algorithm to perform. Each iteration * may or may not update a single coefficient for a specific data point. * * @param iterations the number of learning iterations to perform */ public void setIterations(int iterations) { this.iterations = iterations; } /** * Returns the number of iterations used during training * @return the number of iterations used in training */ public int getIterations() { return iterations; } /** * Sets the amount of regularization to apply. The regularization must be a * positive value * @param regularization the amount of regularization to apply */ public void setRegularization(double regularization) { if(Double.isNaN(regularization) || Double.isInfinite(regularization) || regularization <= 0) throw new ArithmeticException("Regularization must be a positive constant, not " + regularization); this.regularization = regularization; } /** * Returns the amount of regularization used * @return the amount of regularization used */ public double getRegularization() { return regularization; } @Override public PegasosK clone() { PegasosK clone = new PegasosK(regularization, iterations, getKernel().clone(), getCacheMode()); if(this.vecs != null) { clone.vecs = new ArrayList(vecs); clone.alphas = new double[this.alphas.length]; for(int i = 0; i < this.vecs.size(); i++) { clone.vecs.set(i, this.vecs.get(i).clone()); clone.alphas[i] = this.alphas[i]; } } return clone; } @Override public CategoricalResults classify(DataPoint data) { if(alphas == null) throw new UntrainedModelException("Model has not been trained"); CategoricalResults cr = new CategoricalResults(2); double sum = getScore(data); //SVM only says yess / no, can not give a percentage if(sum > 0) cr.setProb(1, 1); else cr.setProb(0, 1); return cr; } @Override public double getScore(DataPoint dp) { return kEvalSum(dp.getNumericalValues()); } /** * Does part of the run through the data to compute the predictoin */ private class PredictPart implements Callable { int i; int start; int end; int[] sign; public PredictPart(int i, int start, int end, int[] sign) { this.i = i; this.start = start; this.end = end; this.sign = sign; } @Override public Double call() throws Exception { final double sign_i = sign[i]; double val = 0; for(int j = start; j < end; j++) { if(j == i || alphas[j] == 0) continue; val += alphas[j]*sign_i* kEval(i, j); } return val; } } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { if (dataSet.getClassSize() != 2) throw new FailedToFitException("Pegasos only supports binary classification problems"); Random rand = RandomUtil.getRandom(); final int m = dataSet.getSampleSize(); alphas = new double[m]; int[] sign = new int[m]; vecs = new ArrayList<>(m); for (int i = 0; i < dataSet.getSampleSize(); i++) { vecs.add(dataSet.getDataPoint(i).getNumericalValues()); sign[i] = dataSet.getDataPointCategory(i) == 1 ? 1 : -1; } setCacheMode(getCacheMode());//Initiates the cahce for (int t = 1; t <= iterations; t++) { final int i = rand.nextInt(m); final double sign_i = sign[i]; final AtomicDouble val = new AtomicDouble(0.0); ParallelUtils.run(true, m, (start, end) -> { double val_local = 0; for(int j = start; j < end; j++) { if(j == i || alphas[j] == 0) continue; val_local += alphas[j]*sign_i* kEval(i, j); } val.addAndGet(val_local); }); val.set(val.get() * sign_i / (regularization * t)); if(val.get() < 1) alphas[i]++; } //Collect the non zero alphas int pos = 0; for (int i = 0; i < alphas.length; i++) if (alphas[i] != 0) { alphas[pos] = alphas[i] * sign[i]; ListUtils.swap(vecs, pos, i); pos++; } alphas = Arrays.copyOf(alphas, pos); vecs = new ArrayList<>(vecs.subList(0, pos)); setCacheMode(null); setAlphas(alphas); } @Override public boolean supportsWeightedData() { return false; } }

Ads help maintain this website.