package jsat.classifiers.svm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ExecutorService;
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.IndexTable;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;
/**
* Implementation of the Stochastic Batch Perceptron (SBP) algorithm. Despite
* its name, it solves the kernelized SVM problem. Because it is done
* stochastically, it may not produce Support Vectors that the standard SVM
* algorithm learns. It can learn at most one SV per iteration.
*
* See:
* Cotter, A., Shalev-Shwartz, S.,&Srebro, N. (2012). The Kernelized
* Stochastic Batch Perceptron. International Conference on Machine
* Learning. Learning. Retrieved from
* here
*
* @author Edward Raff
*/
public class SBP extends SupportVectorLearner implements BinaryScoreClassifier, Parameterized
{
private static final long serialVersionUID = 6112916782260792833L;
private double nu = 0.1;
private int iterations;
private double burnIn = 1.0/5.0;
/**
* Creates a new SBP SVM learner
* @param kernel the kernel to use
* @param cacheMode the type of kernel cache to use
*/
public SBP(KernelTrick kernel, CacheMode cacheMode, int iterations, double v)
{
super(kernel, cacheMode);
setIterations(iterations);
setNu(v);
}
/**
* Copy constructor
* @param other the object to copy
*/
protected SBP(SBP other)
{
this(other.getKernel().clone(), other.getCacheMode(), other.iterations, other.nu);
if(other.alphas != null)
this.alphas = Arrays.copyOf(other.alphas, other.alphas.length);
}
@Override
public SBP clone()
{
return new SBP(this);
}
/**
* Sets the number of iterations to go through. At most one SV can be
* learned per iteration. If more iterations are done than there are SVs, it
* is highly likely that O(n) SVs will be used, making the model very dense.
* It may take far fewer iterations of the algorithm than there are data
* points to get good accuracy.
* @param iterations the number of iterations of the algorithm to perform
*/
public void setIterations(int iterations)
{
this.iterations = iterations;
}
/**
* Returns the number of iterations the algorithm will perform
* @return the number of iterations the algorithm will perform
*/
public int getIterations()
{
return iterations;
}
/**
* The nu parameter for this SVM is not the same as the standard nu-SVM
* formulation, though it plays a similar role. It must be in the range
* (0, 1), where small values indicate a linearly separable problem (in the
* kernel space), and large values mean the problem is less separable. If
* the value is too small for the problem, the SVM may fail to converge or
* produce good results.
*
* @param nu the value between (0, 1)
*/
public void setNu(double nu)
{
if(Double.isNaN(nu) || nu <= 0 || nu >= 1)
throw new IllegalArgumentException("nu must be in the range (0, 1)");
this.nu = nu;
}
/**
* Returns the nu SVM parameter
* @return the nu SVM parameter
*/
public double getNu()
{
return nu;
}
/**
* Sets the burn in fraction. SBP averages the intermediate solutions from
* each step as the final solution. The intermediate steps of SBP are highly
* correlated, and the begging solutions are usually not as meaningful
* toward the converged solution. To overcome this issue a certain fraction
* of the iterations are not averaged into the final solution, making them
* the "burn in" fraction. A value of 0.25 would then be ignoring the
* initial 25% of solutions.
* @param burnIn the ratio int [0, 1) initial solutions to ignore
*/
public void setBurnIn(double burnIn)
{
if(Double.isNaN(burnIn) || burnIn < 0 || burnIn >= 1)
throw new IllegalArgumentException("BurnInFraction must be in [0, 1), not " + burnIn);
this.burnIn = burnIn;
}
/**
*
* @return the burn in fraction
*/
public double getBurnIn()
{
return burnIn;
}
@Override
public CategoricalResults classify(DataPoint data)
{
if(vecs == null)
throw new UntrainedModelException("Classifier has yet to be 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(0, 1.0);
else
cr.setProb(1, 1.0);
return cr;
}
@Override
public double getScore(DataPoint dp)
{
return kEvalSum(dp.getNumericalValues());
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(ClassificationDataSet dataSet)
{
if(dataSet.getClassSize() != 2)
throw new FailedToFitException("SBP supports only binary classification");
final int n = dataSet.getSampleSize();
/**
* First index where we start summing for the average
*/
final int T_0 = (int) Math.min((burnIn*iterations), iterations-1);
/*
* Respone values
*/
double[] C = new double[n];
double[] CSum = new double[n];
alphas = new double[n];
double[] alphasSum = new double[n];
double[] y = new double[n];
vecs = new ArrayList(n);
for(int i = 0; i < n; i++)
{
y[i] = dataSet.getDataPointCategory(i)*2-1;
vecs.add(dataSet.getDataPoint(i).getNumericalValues());
}
setCacheMode(getCacheMode());//Initiates the cahce
Random rand = RandomUtil.getRandom();
double maxKii = 0;
for(int i = 0; i < n; i++)
maxKii = Math.max(maxKii, kEval(i, i));
final double eta_0 = 1/Math.sqrt(maxKii);
double rSqrd = 0;
for(int t = 1; t <= iterations; t++)
{
final double eta = eta_0/Math.sqrt(t);
final double gamma = findGamma(C, n*nu);
int i;
i = sampleC(rand, n, C, gamma);
alphas[i] += eta;
rSqrd = updateLoop(rSqrd, eta, C, i, y, n);
rSqrd = projectionStep(rSqrd, n, C);
if(t >= T_0)
for(int j = 0; j < n; j++)
{
alphasSum[j] += alphas[j];
CSum[j] += C[j];
}
}
//Take the averages
for (int j = 0; j < n; j++)
{
alphas[j] = alphasSum[j]/(iterations-T_0);
C[j] = CSum[j]/(iterations-T_0);
}
double gamma = findGamma(C, n*nu);
for (int j = 0; j < n; j++)
alphas[j] /= gamma;
//Clean up to only the SVs
int supportVectorCount = 0;
for(int i = 0; i < vecs.size(); i++)
if(alphas[i] != 0)//its a support vector
{
ListUtils.swap(vecs, supportVectorCount, i);
alphas[supportVectorCount++] = alphas[i]*y[i];
}
vecs = new ArrayList(vecs.subList(0, supportVectorCount));
alphas = Arrays.copyOfRange(alphas, 0, supportVectorCount);
it = null;
setCacheMode(null);
setAlphas(alphas);
}
private double projectionStep(double rSqrd, final int n, double[] C)
{
if(rSqrd > 1)//1^2 = 1, so jsut use sqrd version
{
final double rInv = 1/Math.sqrt(rSqrd);
for(int j = 0; j < n; j++)
{
C[j] *= rInv;
alphas[j] *= rInv;
}
rSqrd = 1;
}
return rSqrd;
}
private int sampleC(Random rand, final int n, double[] C, final double gamma) throws FailedToFitException
{
int i = 0;
//Samply uniformly from C[i] <= gamma
int attempts = 0;//you get 5 attempts to find one quickly
do
{
i = rand.nextInt(n);
attempts++;
}
while(C[i] > gamma && attempts < 5);
if(C[i] > gamma)//find one the slow way
{
int candidates = 0;
for(int j = 0; j < C.length; j++)
{
if(C[j] < gamma)
candidates++;
}
if(candidates == 0)
throw new FailedToFitException("BUG: please report");
int randCand = rand.nextInt(candidates);
i = 0;
for(int j = 0; j < C.length && i < randCand; j++)
if(C[i] < gamma)
i++;
}
return i;
}
private double updateLoop(double rSqrd, final double eta, double[] C, int i, double[] y, final int n)
{
rSqrd += 2*eta*C[i]+eta*eta*kEval(i, i);
final double y_i = y[i];
for(int j = 0; j < n; j++)
C[j] += eta*y_i*y[j]*kEval(i, j);
return rSqrd;
}
@Override
public boolean supportsWeightedData()
{
return false;
}
private IndexTable it;
//TODO add bias version of findGamma
private double findGamma(double[] C, double d)
{
if(it == null )
it = new IndexTable(C);
else
it.sort(C);//few will change from iteration to iteration, Java's TimSort should be able to exploit this
double sum = 0;
double max;
double finalScore = 0, prevScore = 0;
int i;
for(i = 0; i < it.length(); i++)
{
max = C[it.index(i)];
sum += max;
double score = max*i-sum;
prevScore = finalScore;
finalScore = (d-max*i+sum)/i+max;
if(score >= d)
break;
}
return prevScore;
}
}
Ads help maintain this website.