package jsat.classifiers.linear.kernelized;

import java.util.*;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.distributions.kernels.KernelTrick;
import jsat.linear.Vec;
import jsat.lossfunctions.HingeLoss;
import jsat.lossfunctions.LossC;
import jsat.parameters.Parameter;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;

/**
 * Bounded Online Gradient Descent (BOGD) is a kernel learning algorithm that 
 * uses a bounded number of support vectors. Once the maximum number of support
 * vectors is reached, old vectors are dropped either in a uniform random 
 * fashion, or weighted by the kernel function and the current coefficient for 
 * the vector. The later is the default method and is referred to as BOGD++.
*
* See: Zhao, P., Wang, J., Wu, P., Jin, R.,&Hoi, S. C. H. (2012). Fast * Bounded Online Gradient Descent Algorithms for Scalable Kernel-Based Online * Learning. In Proceedings of the 29th International Conference on Machine * Learning (pp. 169–176). Learning; Machine Learning. Retrieved from * here * @author Edward Raff */ public class BOGD extends BaseUpdateableClassifier implements BinaryScoreClassifier, Parameterized { private static final long serialVersionUID = -3547832514098781996L; @ParameterHolder private KernelTrick k; private int budget; private double eta; private double reg; private double maxCoeff; private LossC lossC; private boolean uniformSampling; private Random rand; private List vecs; /** * Stores the sqrt of each support vector's kernel product with itself */ private List selfK; private DoubleList alphas; private List accelCache; /** * Cache of values used for BOGD++ sampling */ private double[] dist; /** * Creates a new BOGD++ learner using the {@link HingeLoss} * @param k the kernel trick to use * @param budget the budget for support vectors to allow * @param eta the learning rate to use * @param reg the regularization parameter * @param maxCoeff the maximum support vector coefficient to allow */ public BOGD(KernelTrick k, int budget, double eta, double reg, double maxCoeff) { this(k, budget, eta, reg, maxCoeff, new HingeLoss()); } /** * Creates a new BOGD++ learner * @param k the kernel trick to use * @param budget the budget for support vectors to allow * @param eta the learning rate to use * @param reg the regularization parameter * @param maxCoeff the maximum support vector coefficient to allow * @param lossC the loss function to use */ public BOGD(KernelTrick k, int budget, double eta, double reg, double maxCoeff, LossC lossC) { setKernel(k); setBudget(budget); setEta(eta); setRegularization(reg); setMaxCoeff(maxCoeff); this.lossC = lossC; setUniformSampling(false); } /** * Copy constructor * @param toCopy the object to make a copy of */ public BOGD(BOGD toCopy) { this.k = toCopy.k.clone(); this.budget = toCopy.budget; this.eta = toCopy.eta; this.reg = toCopy.reg; this.maxCoeff = toCopy.maxCoeff; this.lossC = toCopy.lossC.clone(); this.uniformSampling = toCopy.uniformSampling; this.rand = RandomUtil.getRandom(); if(toCopy.vecs != null) { this.vecs = new ArrayList(budget); for(Vec v : toCopy.vecs) this.vecs.add(v.clone()); this.selfK = new DoubleList(toCopy.selfK); this.alphas = new DoubleList(toCopy.alphas); } if(toCopy.accelCache != null) this.accelCache = new DoubleList(toCopy.accelCache); if(toCopy.dist != null) this.dist = Arrays.copyOf(toCopy.dist, toCopy.dist.length); } /** * Sets the regularization parameter used for training. The original paper * suggests values in the range 2x/T2 for x * ∈ {-3, -2, -1, 0, 1, 2, 3} where T is the number of data * instances that will be trained on * * @param regularization the positive regularization parameter to use. */ public void setRegularization(double regularization) { if(regularization <= 0 || Double.isNaN(regularization) || Double.isInfinite(regularization)) throw new IllegalArgumentException("Regularization must be positive, not " + regularization); this.reg = regularization; } /** * Returns the regularization parameter used * @return the regularization parameter used */ public double getRegularization() { return reg; } /** * Sets the learning rate to use for training. The original paper suggests * values in the range 2x for x * ∈ {-3, -2, -1, 0, 1, 2, 3} * @param eta the positive learning rate to use */ public void setEta(double eta) { if(eta <= 0 || Double.isNaN(eta) || Double.isInfinite(eta)) throw new IllegalArgumentException("Eta must be positive, not " + eta); this.eta = eta; } /** * Returns the learning rate in use * @return the learning rate in use */ public double getEta() { return eta; } /** * Sets the maximum allowed value for any support vector allowed. The * original paper suggests values in the range 2x for x * ∈ {0, 1, 2, 3, 4} * @param maxCoeff the maximum value for any support vector */ public void setMaxCoeff(double maxCoeff) { if(maxCoeff <= 0 || Double.isNaN(maxCoeff) || Double.isInfinite(maxCoeff)) throw new IllegalArgumentException("MaxCoeff must be positive, not " + maxCoeff); this.maxCoeff = maxCoeff; } /** * Returns the maximum allowed value for any support vector * @return the maximum allowed value for any support vector */ public double getMaxCoeff() { return maxCoeff; } /** * Sets the budget for support vectors * @param budget the allowed budget for support vectors */ public void setBudget(int budget) { if(budget <= 0 ) throw new IllegalArgumentException("Budget must be positive, not " + budget); this.budget = budget; } /** * Returns the maximum number of allowed support vectors * @return the maximum number of allowed support vectors */ public int getBudget() { return budget; } /** * Sets the kernel to use * @param k the kernel to use */ public void setKernel(KernelTrick k) { this.k = k; } /** * Returns the kernel to use * @return the kernel to use */ public KernelTrick getKernel() { return k; } /** * Sets whether or not support vectors should be removed by uniform sampling * or not. The default is {@code false}, which corresponds to BOGD++. * @param uniformSampling {@code true} to use uniform sampling, * {@code false} otherwise. */ public void setUniformSampling(boolean uniformSampling) { this.uniformSampling = uniformSampling; } /** * Returns {@code true } is uniform sampling is in use, or {@code false} if * the BOGD++ sampling procedure is in use * @return {@code true } is uniform sampling is in use, or {@code false} if * the BOGD++ sampling procedure is in use */ public boolean isUniformSampling() { return uniformSampling; } @Override public BOGD clone() { return new BOGD(this); } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { vecs = new ArrayList(budget); alphas = new DoubleList(budget); selfK = new DoubleList(budget); if(k.supportsAcceleration()) accelCache = new DoubleList(budget); else accelCache = null; if(!uniformSampling) dist = new double[budget]; rand = RandomUtil.getRandom(); } @Override public double getScore(DataPoint dp) { Vec x = dp.getNumericalValues(); return score(x, k.getQueryInfo(x)); } private double score(Vec x, List qi) { return k.evalSum(vecs, accelCache, alphas.getBackingArray(), x, qi, 0, alphas.size()); } @Override public void update(DataPoint dataPoint, int targetClass) { final Vec x_t = dataPoint.getNumericalValues(); final double y_t = targetClass*2-1; final List qi = k.getQueryInfo(x_t); final double score = score(x_t, qi); final double lossD = lossC.getDeriv(score, y_t); if(lossD == 0) { alphas.getVecView().mutableMultiply(1-eta*reg); } else { if(vecs.size() < budget) { alphas.getVecView().mutableMultiply(1-eta*reg); alphas.add(-eta*lossD); selfK.add(Math.sqrt(k.eval(0, 0, Arrays.asList(x_t), qi))); if(k.supportsAcceleration()) accelCache.addAll(qi); vecs.add(x_t); } else//budget maintinance { final int toRemove; final double normalize; if(uniformSampling) { toRemove = rand.nextInt(budget); normalize = 1; } else { double s = 0; for(int i = 0; i < budget; i++) s += Math.abs(alphas.get(i))*selfK.get(i); s = (budget-1)/s; final double target = rand.nextDouble(); double cur = 0; int i = -1; while(cur < target) { i++; cur += dist[i] = 1-s*alphas.get(i)*selfK.get(i); } toRemove = i++; while(i < budget) cur += dist[i] = 1-s*alphas.get(i)*selfK.get(i++); normalize = cur; } for(int i = 0; i < budget; i++) { if(i == toRemove) continue; double alpha_i = alphas.getD(i); double sign = Math.signum(alpha_i); alpha_i = Math.abs(alpha_i); double tmp = uniformSampling ? 1.0/budget : dist[i]/normalize; alphas.set(i, sign*Math.min((1-reg*eta)/(1-tmp)*alpha_i, maxCoeff*eta)); } //Remove old point if(k.supportsAcceleration()) { int catToRet = accelCache.size()/budget; for(int i = 0; i < catToRet; i++) accelCache.remove(toRemove*catToRet); } alphas.remove(toRemove); vecs.remove(toRemove); selfK.remove(toRemove); //Add new point alphas.add(-eta*lossD); selfK.add(Math.sqrt(k.eval(0, 0, Arrays.asList(x_t), qi))); accelCache.addAll(qi); vecs.add(x_t); } } } @Override public CategoricalResults classify(DataPoint data) { Vec x = data.getNumericalValues(); return lossC.getClassification(score(x, k.getQueryInfo(x))); } @Override public boolean supportsWeightedData() { return false; } /** * Guesses the distribution to use for the Regularization parameter * * @param d the dataset to get the guess for * @return the guess for the Regularization parameter * @see #setRegularization(double) */ public static Distribution guessRegularization(DataSet d) { double T2 = d.getSampleSize(); T2*=T2; return new LogUniform(Math.pow(2, -3)/T2, Math.pow(2, 3)/T2); } /** * Guesses the distribution to use for the η parameter * * @param d the dataset to get the guess for * @return the guess for the η parameter * @see #setEta(double) */ public static Distribution guessEta(DataSet d) { return new LogUniform(Math.pow(2, -3), Math.pow(2, 3)); } /** * Guesses the distribution to use for the MaxCoeff parameter * * @param d the dataset to get the guess for * @return the guess for the MaxCoeff parameter * @see #setMaxCoeff(double) (double) */ public static Distribution guessMaxCoeff(DataSet d) { return new LogUniform(Math.pow(2, 0), Math.pow(2, 4)); } }

Ads help maintain this website.