package jsat.classifiers.linear.kernelized;

import java.util.*;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.classifiers.linear.ALMA2;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.Distribution;
import jsat.distributions.Uniform;
import jsat.distributions.kernels.KernelTrick;
import jsat.exceptions.FailedToFitException;
import jsat.linear.ScaledVector;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.IntList;

/**
 * Provides a kernelized version of the {@link ALMA2} algorithm. It is important
 * to note that the number of "support vectors" ALMA may learn is unbounded.
 * 
* The averaged output of all previous hyperplanes is supported at almost no * overhead, and can be turned on by setting {@link #setAveraged(boolean) }. * This information is always collected, and the output can be changed once * already learned. *

* See: Gentile, C. (2002). A New Approximate Maximal Margin Classification * Algorithm. The Journal of Machine Learning Research, 2, 213–242. * Retrieved from here * * @author Edward Raff */ public class ALMA2K extends BaseUpdateableClassifier implements BinaryScoreClassifier, Parameterized { private static final long serialVersionUID = 7247320234799227009L; private static final double p = 2; private double alpha; private double B; private double C = Math.sqrt(2); private int k; private int curRounds; @ParameterHolder private KernelTrick K; private List supports; private List signedEtas; private List associatedScores; private List normalizers; private List rounds; private boolean averaged = false; /** * Creates a new kernelized ALMA2 object * @param kernel the kernel function to use * @param alpha the alpha parameter of ALMA */ public ALMA2K(KernelTrick kernel, double alpha) { setKernelTrick(kernel); setAlpha(alpha); } /** * Copy constructor * @param other the ALMA2K object to copy */ protected ALMA2K(ALMA2K other) { this.alpha = other.alpha; this.B = other.B; this.C = other.C; this.k = other.k; this.K = other.K.clone(); this.averaged = other.averaged; if(other.supports != null) { this.supports = new ArrayList(other.supports.size()); for(Vec v : other.supports) this.supports.add(v.clone()); this.signedEtas = new DoubleList(other.signedEtas); this.associatedScores = new DoubleList(other.associatedScores); this.normalizers = new DoubleList(other.normalizers); this.rounds = new IntList(other.rounds); } } @Override public ALMA2K clone() { return new ALMA2K(this); } /** * ALMA2K supports taking the averaged output of all previous hypothesis * weighted by the number of successful uses of the hypothesis during * training. This effectively reduces the variance of the classifier. It has * no impact on the training / update phase, only the classification results * are impacted. *

* Unlike most algorithms, this can be changed at any time without issue - * even after the algorithm has been trained the type of output (averaged or * last) can be switched on the fly. * @param averaged {@code true} to use the averaged out, {@code false} to * only use the last hypothesis */ public void setAveraged(boolean averaged) { this.averaged = averaged; } /** * Returns whether or not the averaged or last hypothesis is used * @return whether or not the averaged or last hypothesis is used */ public boolean isAveraged() { return averaged; } /** * Sets the kernel to use * @param K the kernel to use */ public void setKernelTrick(KernelTrick K) { this.K = K; } /** * Returns the kernel in use * @return the kernel in use */ public KernelTrick getKernelTrick() { return K; } /** * Alpha controls the approximation of the large margin formed by ALMA, * with larger values causing more updates. A value of 1.0 will update only * on mistakes, while smaller values update if the error was not far enough * away from the margin. *

* NOTE: Whenever alpha is set, the value of {@link #setB(double) B} will * also be set to an appropriate value. This is not the only possible value * that will lead to convergence, and can be set manually after alpha is set * to another value. * * @param alpha the approximation scale in (0.0, 1.0] */ public void setAlpha(double alpha) { if(alpha <= 0 || alpha > 1 || Double.isNaN(alpha)) throw new ArithmeticException("alpha must be in (0, 1], not " + alpha); this.alpha = alpha; setB(1.0/alpha); } /** * Returns the approximation coefficient used * @return the approximation coefficient used */ public double getAlpha() { return alpha; } /** * Sets the B variable of the ALMA algorithm, this is set automatically by * {@link #setAlpha(double) }. * @param B the value for B */ public void setB(double B) { this.B = B; } /** * Returns the B value of the ALMA algorithm * @return the B value of the ALMA algorithm */ public double getB() { return B; } /** * Sets the C value of the ALMA algorithm. The default value is the one * suggested in the paper. * @param C the C value of ALMA */ public void setC(double C) { if(C <= 0 || Double.isInfinite(C) || Double.isNaN(C)) throw new ArithmeticException("C must be a posative cosntant"); this.C = C; } public double getC() { return C; } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { if(numericAttributes <= 0) throw new FailedToFitException("ALMA2 requires numeric features"); if(predicting.getNumOfCategories() != 2) throw new FailedToFitException("ALMA2 works only for binary classification"); supports = new ArrayList(); signedEtas = new DoubleList(); associatedScores = new DoubleList(); normalizers = new DoubleList(); rounds = new IntList(); k = 1; curRounds = 0; } @Override public void update(DataPoint dataPoint, int targetClass) { final Vec x_t = dataPoint.getNumericalValues(); final double y_t = targetClass*2-1; double gamma = B * Math.sqrt(p-1) / k; double wx = score(x_t, false); if(y_t*wx <= (1-alpha)*gamma)//update { double eta = C/Math.sqrt(p-1)/Math.sqrt(k++); double norm = Math.sqrt(K.eval(x_t, x_t)); associatedScores.add(score(new ScaledVector(1/norm, x_t), false)); supports.add(x_t); normalizers.add(norm); signedEtas.add(eta*y_t); rounds.add(curRounds); curRounds = 0; } else curRounds++; } /** * Computes the output of the summations of the input vector with the * current weight vector as a recursive linear combination of all previous * support vectors and their associated score values.
* See Remark 5 in the original paper. * @param x the input vector to compute the score value * @return the score for the input indicating which side of the hyperplane * it is on */ private double score(Vec x, boolean averaged) { /* * Score for the current dot procut with the weight vector, denom for * the current normalizing constant. */ double score = 0; double denom = 0; double finalScore = 0; for(int i = 0; i < supports.size(); i++) { double eta_s = signedEtas.get(i); double tmp = eta_s*K.eval(supports.get(i), x)/normalizers.get(i); double denom_tmp = 2*eta_s*associatedScores.get(i)+eta_s*eta_s; denom += denom/Math.max(1, denom)+ denom_tmp; score += tmp/Math.max(1, denom); if(averaged) finalScore += score*rounds.get(i); } if(averaged) return finalScore; else return score; } @Override public CategoricalResults classify(DataPoint data) { double wx = getScore(data); CategoricalResults cr =new CategoricalResults(2); if(wx < 0) cr.setProb(0, 1.0); else cr.setProb(1, 1.0); return cr; } @Override public double getScore(DataPoint dp) { return score(dp.getNumericalValues(), averaged); } @Override public boolean supportsWeightedData() { return false; } /** * Guesses the distribution to use for the α parameter * * @param d the dataset to get the guess for * @return the guess for the α parameter * @see #setAlpha(double) */ public static Distribution guessAlpha(DataSet d) { return new Uniform(1e-3, 1.0); } }

Ads help maintain this website.