package jsat.classifiers.linear.kernelized;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import jsat.classifiers.BaseUpdateableClassifier;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.DataPoint;
import jsat.distributions.kernels.KernelTrick;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.random.XORWOW;
import static java.lang.Math.*;
import jsat.DataSet;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.exceptions.FailedToFitException;
import jsat.utils.random.RandomUtil;

/**
 * An implementation of Conservative Stochastic Kernel Logistic Regression. This
 * is an online algorithm that obtains sparse solutions by conservatively 
 * rejecting updates based on a binomial distribution of the error on each 
 * update. 

* This algorithm works best on data sets with a very high number of samples * where a high accuracy is obtainable using a kernel model. It is often the * case that this model produces accurate results, but has a low confidence due * to the conservative updating. This can be counteracted by having a very large * number of features, but that often increases the size of the model. *

* It is important to read the documentation and test some different values for * the {@link #setEta(double) learning rate} and {@link #setGamma(double) gamma} * variables. They behave different compared to many algorithms. *

* It is possible to obtain a more confident model and a slightly larger model * by using several epochs. Instead of using this class, the * {@link CSKLRBatch batch version} of this algorithm should be used instead. *

* See paper:
* Zhang, L., Jin, R., Chen, C., Bu, J.,&He, X. (2012). Efficient Online * Learning for Large-Scale Sparse Kernel Logistic Regression. Twenty-Sixth * AAAI Conference on Artificial Intelligence (pp. 1219–1225). Retrieved from * here * * @author Edward Raff */ public class CSKLR extends BaseUpdateableClassifier implements Parameterized { private static final long serialVersionUID = 2325605193408720811L; private double eta; private DoubleList alpha; private List vecs; private double curNorm; private KernelTrick k; private double R; private Random rand; private UpdateMode mode; private double gamma = 2; private List accelCache; /** * Creates a new CSKLR object * @param eta the learning rate to use * @param k the kernel trick to use * @param R the maximal norm of the surface * @param mode the mode to use */ public CSKLR(double eta, KernelTrick k, double R, UpdateMode mode) { setEta(eta); setKernel(k); setR(R); setMode(mode); } /** * 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); } /** * Controls when updates are performed on the model. Depending on which * update model is used, the acceptable values and behaviors of * {@link #setEta(double) } and {@link #setGamma(double) } may change. *

* The "auxiliary" modes perform updates with a probability of * log(1+e-z) / a(z), where a(z) is the auxiliary * function and z is the raw margin value times the class label. */ public enum UpdateMode { /** * NC stands for Non-Conservative, this mode will perform a model update * on every new input, creating a very dense model. The * {@link #setEta(double) learning rate} may take on any positive value, * and {@link #setGamma(double) } is not used. */ NC { @Override protected double pt(double y, double score, double preScore, double eta, double gamma) { return 1; } @Override protected double grad(double y, double score, double preScore, double gamma) { return score-1; } }, /** * Performs model updates probabilistically based on their distance from * the margin of the classifier. In this case, {@link #setEta(double) } * should be less than 2, or the model will become dense. * {@link #setGamma(double) } is not used. */ MARGIN { @Override protected double pt(double y, double score, double preScore, double eta, double gamma) { return (2-eta)/(2-eta+eta*score); } @Override protected double grad(double y, double score, double preScore, double gamma) { return score-1; } }, /** * Performs model updates based on a "auxiliary" function * a(z) = log(γ + e-z). * {@link #setGamma(double) gamma} should be in the range (1, Infinity) * where larger values increase the sparsity of the model *

* This is the main auxiliary method used by the authors. They use * values for γ in the range of 1+10± * x ∀ x ∈ {0, 1, 2, 3, 4} */ AUXILIARY_1 { @Override protected double pt(double y, double score, double preScore, double eta, double gamma) { double z = y*preScore; return log(1+exp(-z))/log(gamma+exp(-z)); } @Override protected double grad(double y, double score, double preScore, double gamma) { double z = y*preScore; return -1/(1+gamma*exp(z)); } }, /** * Performs model updates based on a "auxiliary" function * a(z) = log(1 + γ e-z). * {@link #setGamma(double) gamma} should be in the range (1, Infinity) * where larger values increase the sparsity of the model */ AUXILIARY_2 { @Override protected double pt(double y, double score, double preScore, double eta, double gamma) { double z = y*preScore; return log(1+exp(-z))/log(1+gamma*exp(-z)); } @Override protected double grad(double y, double score, double preScore, double gamma) { double z = y*preScore; return -gamma/(gamma+exp(z)); } }, /** * Performs model updates based on a "auxiliary" function * a(z) = max(loss(z), loss(γ). * {@link #setGamma(double) gamma} should be in the range (0, Infinity) * where smaller values increase the sparsity of the model */ AUXILIARY_3 { @Override protected double pt(double y, double score, double preScore, double eta, double gamma) { double z = y*preScore; return log(1+exp(-z))/log(1+exp(-gamma)); } @Override protected double grad(double y, double score, double preScore, double gamma) { return score-1; } }; /** * Returns the Bernoulli trial probability variable * @param y the sign of the input point * @param score the logistic regression score for the input * @param preScore the raw margin before the final * @param eta the learning rate * @param gamma the gamma variable * @return the Bernoulli trial probability variable */ abstract protected double pt(double y, double score, double preScore, double eta, double gamma); /** * Get the gradient value that should be applied based on the input * variable from the current model * @param y the sign of the input point * @param score the logistic regression score for the input * @param preScore the raw margin before the final * @param gamma the gamma variable * @return the coefficient to apply to the stochastic update */ abstract protected double grad(double y, double score, double preScore, double gamma); } /** * Copy constructor * @param toClone the object to copy */ protected CSKLR(CSKLR toClone) { if(toClone.alpha != null) this.alpha = new DoubleList(toClone.alpha); if(toClone.vecs != null) { this.vecs = new ArrayList(toClone.vecs); } this.curNorm = toClone.curNorm; this.mode = toClone.mode; this.R = toClone.R; this.eta = toClone.eta; this.setKernel(toClone.k.clone()); if(toClone.accelCache != null) this.accelCache = new DoubleList(toClone.accelCache); this.gamma = toClone.gamma; this.rand = RandomUtil.getRandom(); this.setEpochs(toClone.getEpochs()); } /** * Sets the learning rate to use for the algorithm. Unlike many other * stochastic algorithms, the learning rate for CSKLR should be large, often * in the range of (0.5, 1) - and can even be larger than 1 at times. If the * learning rate is too low, it may be difficult to get strong confidence * results from the algorithm. * * @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("The learning rate should be in (0, Inf), not " + eta); this.eta = eta; } /** * Returns the learning rate to use * @return the learning rate to use */ public double getEta() { return eta; } /** * Sets the maximal margin norm value for the algorithm. When the norm is * exceeded, the coefficients will be rescaled to fit in the norm. If the * maximal norm is too small (less than 5), it may be difficult to get * strong confidence results from the algorithm.
* A good range of values suggested by the original paper is 10x * ∀ x ∈ {0, 1, 2, 3, 4, 5} * @param R */ public void setR(double R) { if(R < 0 || Double.isNaN(R) || Double.isInfinite(R)) throw new IllegalArgumentException("The max norm should be in (0, Inf), not " + R); this.R = R; } /** * Returns the maximal norm of the algorithm * @return the maximal norm of the algorithm */ public double getR() { return R; } /** * Sets what update mode should be used. The update mode controls the * sparsity of the mode, and the behavior of {@link #setGamma(double) } * @param mode the update mode to use */ public void setMode(UpdateMode mode) { this.mode = mode; } /** * Returns the update mode in use * @return the update mode in use */ public UpdateMode getMode() { return mode; } /** * Sets the gamma value to use. This value, depending on which * {@link UpdateMode} is used, controls the sparsity of the model. * @param gamma the gamma parameter, which is at least always positive */ public void setGamma(double gamma) { if(gamma < 0 || Double.isNaN(gamma) || Double.isInfinite(gamma)) throw new IllegalArgumentException("Gamma must be in (0, Infity), not " + gamma); this.gamma = gamma; } /** * Returns the gamma sparsity parameter value * @return the gamma sparsity parameter value */ public double getGamma() { return gamma; } /** * Set which kernel trick to use * @param k the kernel to use */ public void setKernel(KernelTrick k) { this.k = k; } /** * Returns the kernel trick in use * @return the kernel trick in use */ public KernelTrick getKernel() { return k; } /** * Computes the margin score for the given data point * @param x the input vector * @return the margin score */ private double getPreScore(Vec x) { return k.evalSum(vecs, accelCache, alpha.getBackingArray(), x, 0, alpha.size()); } /** * Returns the binary logistic regression score * @param y the sign of the desired class (-1 or 1) * @param pre the raw coefficient score * @return the probability in [0, 1] that the score is of the desired class */ protected static double getScore(double y, double pre) { return 1/(1+Math.exp(-y*pre)); } @Override public CSKLR clone() { return new CSKLR(this); } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { if(predicting.getNumOfCategories() != 2) throw new FailedToFitException("CSKLR supports only binary classification"); alpha = new DoubleList(); vecs = new ArrayList(); curNorm = 0; rand = RandomUtil.getRandom(); if(k.supportsAcceleration()) accelCache = new DoubleList(); } @Override public void update(DataPoint dataPoint, int targetClass) { double y_t = targetClass*2-1; Vec x_t = dataPoint.getNumericalValues(); double pre = getPreScore(x_t); double score = getScore(y_t, pre); switch(mode) { case NC: break; default: double pt = mode.pt(y_t, score, pre, eta, gamma); if(rand.nextDouble() > pt) return; break; } double alpha_i = -eta*y_t*mode.grad(y_t, score, pre, gamma)*dataPoint.getWeight(); alpha.add(alpha_i); vecs.add(x_t); k.addToCache(x_t, accelCache); curNorm += Math.abs(alpha_i) * k.eval(vecs.size(), vecs.size(), vecs, accelCache); //projection step if (curNorm > R) { double coef = R/curNorm; for(int i = 0; i < alpha.size(); i++) alpha.set(i, alpha.get(i)*coef); curNorm = coef; } } @Override public CategoricalResults classify(DataPoint data) { CategoricalResults cr = new CategoricalResults(2); double p_0 = getScore(-1, getPreScore(data.getNumericalValues())); cr.setProb(0, p_0); cr.setProb(1, 1-p_0); return cr; } @Override public boolean supportsWeightedData() { return true; } }

Ads help maintain this website.