package jsat.classifiers.linear.kernelized;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
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.LogisticLoss;
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;

/**
 * Online Sparse Kernel Learning by Sampling and Smooth Losses (OSKL) is an 
 * online algorithm for learning sparse kernelized solutions to binary 
 * classification problems. The number of support vectors is controlled by a a
 * sparsity parameter {@link #setG(double) G} and a specified 
 * {@link LossC loss function}. The number of support vectors is bounded by the 
 * cumulative loss of the loss function used. 
*
* The OSKL algorithm is designed for use with smooth loss functions such as * the {@link LogisticLoss logistic loss}. However, it can work with non-smooth * loss functions such as the {@link HingeLoss hinge loss}.
*
* See: Zhang, L., Yi, J., Jin, R., Lin, M.,&He, X. (2013). Online Kernel * Learning with a Near Optimal Sparsity Bound. In S. Dasgupta&D. * Mcallester (Eds.), Proceedings of the 30th International Conference on * Machine Learning (ICML-13) (Vol. 28, pp. 621–629). JMLR Workshop and * Conference Proceedings. * * @author Edward Raff */ public class OSKL extends BaseUpdateableClassifier implements BinaryScoreClassifier, Parameterized { private static final long serialVersionUID = 4207594016856230134L; @ParameterHolder private KernelTrick k; private double eta; private double R; private double G; private double curSqrdNorm; private LossC lossC; private boolean useAverageModel = true; //Data used for capturing the average private int t; /** * Last time alphaAverage was updated */ private int last_t; private int burnIn; /** * Store the average of the weights over time */ private DoubleList alphaAveraged; private List vecs; private DoubleList alphas; private DoubleList inputKEvals; private List accelCache; private Random rand; /** * Creates a new OSKL learner using the {@link LogisticLoss}. The parameters * {@link #setG(double) } and {@link #setEta(double) } are set based on the * original papers suggestions to produced a less sparse model that should * be more accurate * * @param k the kernel to use * @param R the maximum allowed norm for the model */ public OSKL(KernelTrick k, double R) { this(k, 0.9, 1, R); } /** * Creates a new OSKL learner using the {@link LogisticLoss} * @param k the kernel to use * @param eta the learning rate to use * @param G the sparsification parameter * @param R the maximum allowed norm for the model */ public OSKL(KernelTrick k, double eta, double G, double R) { this(k, eta, G, R, new LogisticLoss()); } /** * Creates a new OSKL learner * @param k the kernel to use * @param eta the learning rate to use * @param G the sparsification parameter * @param R the maximum allowed norm for the model * @param lossC the loss function to use */ public OSKL(KernelTrick k, double eta, double G, double R, LossC lossC) { setKernel(k); setEta(eta); setR(R); setG(G); this.lossC = lossC; } /** * Copy constructor * @param toCopy the object to copy */ public OSKL(OSKL toCopy) { this.k = toCopy.k.clone(); this.eta = toCopy.eta; this.R = toCopy.R; this.G = toCopy.G; this.curSqrdNorm = toCopy.curSqrdNorm; this.lossC = toCopy.lossC.clone(); this.t = toCopy.t; this.last_t = toCopy.last_t; this.useAverageModel = toCopy.useAverageModel; this.burnIn = toCopy.burnIn; if(toCopy.vecs != null) { this.vecs = new ArrayList(); for(Vec v : toCopy.vecs) this.vecs.add(v.clone()); this.alphas = new DoubleList(toCopy.alphas); this.alphaAveraged = new DoubleList(toCopy.alphaAveraged); this.inputKEvals = new DoubleList(toCopy.inputKEvals); } if(toCopy.accelCache != null) this.accelCache = new DoubleList(toCopy.accelCache); this.rand = RandomUtil.getRandom(); } /** * 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 the learning rate to use for training. The original paper suggests * setting η = 0.9/{@link #setG(double) G} * @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 sparsification parameter G. Increasing G reduces the number of * updates to the model, which increases sparsity but may reduce accuracy. * Decreasing G increases the update rate reducing sparsity. The original * paper tests values of G ∈ {1, 2, 4, 10} * @param G the sparsification parameter in [1, ∞) */ public void setG(double G) { if(G < 1 || Double.isInfinite(G) || Double.isNaN(G)) throw new IllegalArgumentException("G must be in [1, Infinity), not " + G); this.G = G; } /** * Returns the sparsification parameter * @return the sparsification parameter */ public double getG() { return G; } /** * Guesses the distribution to use for the R parameter * * @param d the dataset to get the guess for * @return the guess for the R parameter * @see #setR(double) */ public static Distribution guessR(DataSet d) { return new LogUniform(1, 1e5); } /** * Sets the maximum allowed norm of the model. The * original paper suggests values in the range 10x for x * ∈ {0, 1, 2, 3, 4, 5}. * @param R the maximum allowed norm for the model */ public void setR(double R) { if(R <= 0 || Double.isNaN(R) || Double.isInfinite(R)) throw new IllegalArgumentException("R must be positive, not " + R); this.R = R; } /** * Returns the maximum allowed norm for the model learned * @return the maximum allowed norm for the model learned */ public double getR() { return R; } /** * Sets whether or not the average of all intermediate models is used or if * the most recent model is used when performing classification * @param useAverageModel {@code true} to use the average model, * {@code false} to use the last model update */ public void setUseAverageModel(boolean useAverageModel) { this.useAverageModel = useAverageModel; } /** * Returns {@code true} if the average of all models is being used, or * {@code false} if the last model is used * @return {@code true} if the average of all models is being used, or * {@code false} if the last model is used */ public boolean isUseAverageModel() { return useAverageModel; } /** * Sets the number of update calls to consider as part of the "burn in" * phase. The averaging of the model will not start until after the burn in * phase.
* If the classification or score is requested before the burn in phase is * completed, the latest model will be used as is. * @param burnIn the number of updates to ignore before averaging. Must be * non negative. */ public void setBurnIn(int burnIn) { if(burnIn < 0) throw new IllegalArgumentException("Burn in must be non negative, not " + burnIn); this.burnIn = burnIn; } /** * Returns the number of burn in rounds * @return the number of burn in rounds */ public int getBurnIn() { return burnIn; } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { rand = RandomUtil.getRandom(); vecs = new ArrayList(); alphas = new DoubleList(); alphaAveraged = new DoubleList(); t = 0; last_t = 0; inputKEvals = new DoubleList(); if(k.supportsAcceleration()) accelCache = new DoubleList(); else accelCache = null; curSqrdNorm = 0; } /** * Returns the number of data points accepted as support vectors * @return the number of support vectors in the model */ public int getSupportVectorCount() { if(vecs == null) return 0; else return vecs.size(); } @Override public void update(DataPoint dataPoint, int targetClass) { final Vec x_t = dataPoint.getNumericalValues(); final List qi = k.getQueryInfo(x_t); final double score = scoreSaveEval(x_t, qi); final double y_t = targetClass*2-1; //4: Compute the derivative ℓ′(yt, ft(xt)) final double lossD = lossC.getDeriv(score, y_t); t++; // Step 5: Sample a binary random variable Zt with if(rand.nextDouble() > Math.abs(lossD)/G) return;//"failed", no update final double alpha_t = -eta*Math.signum(lossD)*G; //Update the squared norm curSqrdNorm += alpha_t*alpha_t*inputKEvals.getD(0); for(int i = 0; i < alphas.size(); i++) curSqrdNorm += 2*alpha_t*alphas.getD(i)*inputKEvals.getD(i+1); //add values alphas.add(alpha_t); vecs.add(x_t); if(accelCache != null) accelCache.addAll(qi); //update online alpha averages for current & old SVs alphaAveraged.add(0.0);//implicit zero for time we didn't have new SVs updateAverage(); //project alphas to maintain norm if needed if(curSqrdNorm > R*R) { double coeff = R/Math.sqrt(curSqrdNorm); alphas.getVecView().mutableMultiply(coeff); curSqrdNorm *= coeff*coeff; } }; private double score(Vec x, List qi) { DoubleList alphToUse; if(useAverageModel && t > burnIn) { updateAverage(); alphToUse = alphaAveraged; } else alphToUse = alphas; return k.evalSum(vecs, accelCache, alphToUse.getBackingArray(), x, qi, 0, alphToUse.size()); } /** * Computes the score and saves the results of the kernel computations in * {@link #inputKEvals}. The first value in the list will be the self kernel * product * @param x the input vector * @param qi the query information for the vector * @return the dot product in the kernel space */ private double scoreSaveEval(Vec x, List qi) { inputKEvals.clear(); inputKEvals.add(k.eval(0, 0, Arrays.asList(x), qi)); double sum = 0; for(int i = 0; i < alphas.size(); i++) { double k_ix = k.eval(i, x, qi, vecs, accelCache); inputKEvals.add(k_ix); sum += alphas.getD(i)*k_ix; } return sum; } @Override public CategoricalResults classify(DataPoint data) { Vec x = data.getNumericalValues(); return lossC.getClassification(score(x, k.getQueryInfo(x))); } @Override public boolean supportsWeightedData() { return false; } @Override public double getScore(DataPoint dp) { Vec x = dp.getNumericalValues(); return score(x, k.getQueryInfo(x)); } @Override public OSKL clone() { return new OSKL(this); } /** * Updates the average model to reflect the current time average */ private void updateAverage() { if(t == last_t || t < burnIn) return; else if(last_t < burnIn)//first update since done burning { for(int i = 0; i < alphaAveraged.size(); i++) alphaAveraged.set(i, alphas.get(i)); } double w = t-last_t;//time elapsed for(int i = 0; i < alphaAveraged.size(); i++) { double delta = alphas.getD(i) - alphaAveraged.getD(i); alphaAveraged.set(i, alphaAveraged.getD(i)+delta*w/t); } last_t = t;//average done } }

Ads help maintain this website.