package jsat.classifiers.linear.kernelized;
import static java.lang.Math.*;
import java.util.Arrays;
import java.util.List;
import jsat.classifiers.BaseUpdateableClassifier;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.DataPoint;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.classifiers.neuralnetwork.Perceptron;
import jsat.distributions.kernels.KernelTrick;
import jsat.exceptions.FailedToFitException;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
/**
* Implementation of the first two Forgetron algorithms. The Forgetron is a
* kernelized version of the {@link Perceptron} that maintains a fixed sized
* buffer of data instances that it uses to form its decision boundary.
*
* See:
* Dekel, O., Shalev-Shwartz, S.,&Singer, Y. (2008). The Forgetron: A
* kernel-based perceptron on a fixed budget. SIAM Journal on Computing,
* 37(5), 1342–1372.
*
* @author Edward Raff
*/
public class Forgetron extends BaseUpdateableClassifier implements BinaryScoreClassifier, Parameterized
{
private static final long serialVersionUID = -2631315082407427077L;
@ParameterHolder
private KernelTrick K;
private Vec[] I;
/**
* Stores the label times the weight. Getting the true weight is an abs
* operation. Getting the true label is a signum operation.
*/
private double[] s;
private int size;
/**
* Will always point to current insert position. Either empty, or the last
* value ever inserted
*/
private int curPos;
private int budget;
private double U;
private double Bconst;
private double Q, M;
private boolean selfTuned = true;
/**
* Creates a new Forgetron
* @param kernel the kernel function to use
* @param budget the maximum number of data points to use
*/
public Forgetron(KernelTrick kernel, int budget)
{
this.K = kernel;
setBudget(budget);
}
/**
* Sets whether or not the self-tuned variant of the Forgetron is used, the
* default is {@code true}
*
* @param selfTurned {@code true} to use the self-tuned variance,
* {@code false} otherwise.
*/
public void setSelfTurned(boolean selfTurned)
{
this.selfTuned = selfTurned;
}
/**
*
* @return {@code true} if the self-tuned variant is used, {@code false}
* otherwise.
*/
public boolean isSelfTuned()
{
return selfTuned;
}
/**
* Copy constructor
* @param toClone the forgetron to clone
*/
protected Forgetron(Forgetron toClone)
{
super(toClone);
this.K = toClone.K.clone();
this.budget = toClone.budget;
this.U = toClone.U;
this.Bconst = toClone.Bconst;
this.Q = toClone.Q;
this.M = toClone.M;
this.curPos = toClone.curPos;
this.size = toClone.size;
if(toClone.I != null)
{
this.I = new Vec[toClone.I.length];
for(int i = 0; i < toClone.I.length; i++)
if(toClone.I[i] != null)
this.I[i] = toClone.I[i].clone();
}
if(toClone.s != null)
this.s = Arrays.copyOf(toClone.s, toClone.s.length);
}
/**
* Sets the new budget, which is the maximum number of data points the
* Forgetron can use to form its decision boundary.
* @param budget the maximum number of data points to use
*/
public void setBudget(int budget)
{
this.budget = budget;
double B = budget;
U = sqrt((B+1)/log(B+1))/4;
Bconst = pow(B+1, 1.0/(2*B+2));
}
/**
* Returns the current budget
* @return the current budget
*/
public int getBudget()
{
return budget;
}
/**
* Sets the kernel trick to use
* @param K the kernel trick to use
*/
public void setKernelTrick(KernelTrick K)
{
this.K = K;
}
/**
* Returns the current kernel trick
* @return the current kernel trick
*/
public KernelTrick getKernelTrick()
{
return K;
}
@Override
public CategoricalResults classify(DataPoint data)
{
CategoricalResults cr = new CategoricalResults(2);
int winner = (int) ((signum(getScore(data))+1)/2);
cr.setProb(winner, 1);
return cr;
}
@Override
public double getScore(DataPoint dp)
{
return classify(dp.getNumericalValues());
}
private double classify(Vec x)
{
double r = 0;
for(int i = 0; i < size; i++)
r += s[i]*K.eval(I[i], x);
return r;
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public Forgetron clone()
{
return new Forgetron(this);
}
@Override
public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting)
{
if(predicting.getNumOfCategories() != 2)
throw new FailedToFitException("Forgetron only supports binary classification");
else if(numericAttributes == 0)
throw new FailedToFitException("Forgetron requires numeric attributes");
I = new Vec[budget];
s = new double[budget];
Q = M = 0;
size = 0;
curPos = 0;
}
/**
* See equation 15
* @param lambda
* @param mu
* @return the update for equation 15
*/
private double psi(double lambda, double mu)
{
return lambda*lambda+2*lambda-2*lambda*mu;
}
@Override
public void update(DataPoint dataPoint, int targetClass)
{
Vec x = dataPoint.getNumericalValues();
double f_t = classify(x);
double y_t = targetClass*2-1;
if(y_t*f_t > 0)
{
//its all cool bro
}
else//not cool bro (error)
{
M++;
if (selfTuned)
{
if (size + 1 <= budget)//in budget, we can add safly
{
size++;
I[curPos] = x;
s[curPos] = y_t;
}
else//over budget, remove oldest
{
final int r = curPos;
//f'_t equation (27)
final double fp_t = classify(I[r]) + y_t * K.eval(x, I[r]);
//equations (44)
final double s_r = abs(s[r]);
final double y_r = signum(s[r]);
final double a = s_r * s_r - 2 * y_r * s_r * fp_t;
final double b = 2 * s_r;
final double c = Q - (15.0 / 32.0) * M;
final double d = b * b - 4 * a * c;
//equations (43)
double phi_t;
if ((a > 0 || (a < 0 && d > 0 && (-b - sqrt(d)) / (2 * a) > 1)))
phi_t = min(1, (-b + sqrt(d)) / (2 * a));
else if (abs(a) <= 1e-13)
phi_t = min(1, -c / b);
else
phi_t = 1;
double fpp_t_r = phi_t * fp_t;
Q += psi(phi_t * s_r, y_r * fpp_t_r);
I[curPos] = x;
s[curPos] = y_t;
if (phi_t != 1)
for (int i = 0; i < s.length; i++)
s[i] *= phi_t;
}
}
else//normal version
{
double ff = 1;//for the added term that makes us remove one.
if(size > 0)
{
for (int i = 0; i < size; i++)
ff += pow(s[i], 2) * K.eval(I[i], I[i]);
}
double fNorm = sqrt(ff);//obtained from after equation 2
double phi = min(Bconst, U/fNorm);
I[curPos] = x;
s[curPos] = y_t;
if(size < budget)
size++;
for(int i = 0; i < size; i++)
s[i] *= phi;
}
curPos = (curPos + 1) % I.length;
}
}
}
Ads help maintain this website.