package jsat.classifiers.linear;

import java.util.List;
import jsat.DataSet;
import jsat.SingleWeightVectorModel;
import jsat.classifiers.BaseUpdateableClassifier;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.DataPoint;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.linear.Matrix;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;

/**
 * Implementation of the Normal Herd (NHERD) algorithm for learning a linear 
 * binary classifier. It is related to both {@link AROW} and the PA-II variant 
 * of {@link PassiveAggressive}. 
* Unlike similar algorithms, several methods of using only the diagonal values * of the covariance are available. *
* NOTE: This implementation does not add an implicit bias term, so the solution * goes through the origin *

* See:
* Crammer, K.,&Lee, D. D. (2010). Learning via Gaussian Herding. * Pre-proceeding of NIPS (pp. 451–459). Retrieved from * * here * * @author Edward Raff */ public class NHERD extends BaseUpdateableClassifier implements BinaryScoreClassifier, Parameterized, SingleWeightVectorModel { private static final long serialVersionUID = -1186002893766449917L; private Vec w; /** * Full covariance matrix */ private Matrix sigmaM; /** * Diagonal only covariance matrix */ private Vec sigmaV; private CovMode covMode; private double C; /** * Temp vector used to store Sigma * x_t */ private Vec Sigma_xt; /** * Sets what form of covariance matrix to use */ public static enum CovMode { /** * Use the full covariance matrix */ FULL, /** * Standard diagonal method, only the diagonal values get updated by * dropping the other terms. */ DROP, /** * Creates the diagonal by dropping the terms of the inverse of the * covariance matrix that is used to perform the update. This authors * suggest this is usually the best for diagonal covariance matrices * from empirical testing. */ PROJECT, /** * Creates the diagonal by solving the derivative with respect to the * specific objective function of NHERD */ EXACT } /** * Creates a new NHERD learner * @param C the aggressiveness parameter * @param covMode how to form the covariance matrix * @see #setC(double) * @see #setCovMode(jsat.classifiers.linear.NHERD.CovMode) */ public NHERD(double C, CovMode covMode) { setC(C); setCovMode(covMode); } /** * Copy constructor * @param other the object to copy */ protected NHERD(NHERD other) { this.C = other.C; this.covMode = other.covMode; if(other.w != null) this.w = other.w.clone(); if(other.sigmaM != null) this.sigmaM = other.sigmaM.clone(); if(other.sigmaV != null) this.sigmaV = other.sigmaV.clone(); if(other.Sigma_xt != null) this.Sigma_xt = other.Sigma_xt.clone(); } /** * Set the aggressiveness parameter. Increasing the value of this parameter * increases the aggressiveness of the algorithm. It must be a positive * value. This parameter essentially performs a type of regularization on * the updates * * @param C the positive aggressiveness parameter */ public void setC(double C) { if(Double.isNaN(C) || Double.isInfinite(C) || C <= 0) throw new IllegalArgumentException("C must be a postive constant, not " + C); this.C = C; } /** * Returns the aggressiveness parameter * @return the aggressiveness parameter */ public double getC() { return C; } /** * Sets the way in which the covariance matrix is formed. If using the full * covariance matrix, rank-1 updates mean updates to the model take * O(d2) time, where d is the dimension of the * input. Runtime can be reduced by using only the diagonal of the matrix to * perform updates in O(s) time, where s ≤ d is the number * of non-zero values in the input * * @param covMode the way to form the covariance matrix */ public void setCovMode(CovMode covMode) { this.covMode = covMode; } /** * Returns the mode for forming the covariance * @return the mode for forming the covariance */ public CovMode getCovMode() { return covMode; } /** * Returns the weight vector used to compute results via a dot product.
* Do not modify this value, or you will alter the results returned. * @return the learned weight vector for prediction */ public Vec getWeightVec() { return w; } @Override public Vec getRawWeight() { return w; } @Override public double getBias() { return 0; } @Override public Vec getRawWeight(int index) { if(index < 1) return getRawWeight(); else throw new IndexOutOfBoundsException("Model has only 1 weight vector"); } @Override public double getBias(int index) { if (index < 1) return getBias(); else throw new IndexOutOfBoundsException("Model has only 1 weight vector"); } @Override public int numWeightsVecs() { return 1; } @Override public NHERD clone() { return new NHERD(this); } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { if(numericAttributes <= 0) throw new FailedToFitException("AROW requires numeric attributes to perform classification"); else if(predicting.getNumOfCategories() != 2) throw new FailedToFitException("AROW is a binary classifier"); w = new DenseVector(numericAttributes); Sigma_xt = new DenseVector(numericAttributes); if(covMode != CovMode.FULL) { sigmaV = new DenseVector(numericAttributes); sigmaV.mutableAdd(1); } else sigmaM = Matrix.eye(numericAttributes); } @Override public void update(DataPoint dataPoint, int targetClass) { Vec x_t = dataPoint.getNumericalValues(); double y_t = targetClass*2-1; double pred = x_t.dot(w); if(y_t*pred > 1) return;//No update needed //else, wrong label or margin too small double alpha; if(covMode != CovMode.FULL) { alpha = 0; //Faster to set only the needed final values for (IndexValue iv : x_t) { double x_ti = iv.getValue(); alpha += x_ti * x_ti * sigmaV.get(iv.getIndex()); } } else { sigmaM.multiply(x_t, 1, Sigma_xt); alpha = x_t.dot(Sigma_xt); } final double loss = Math.max(0, 1 - y_t * pred); final double w_c = y_t * loss / (alpha + 1 / C); if (covMode == CovMode.FULL) w.mutableAdd(w_c, Sigma_xt); else for (IndexValue iv : x_t) w.increment(iv.getIndex(), w_c * iv.getValue() * sigmaV.get(iv.getIndex())); double numer = C*(C*alpha+2); double denom = (1+C*alpha)*(1+C*alpha); switch (covMode) { case FULL: Matrix.OuterProductUpdate(sigmaM, Sigma_xt, Sigma_xt, -numer/denom); break; case DROP: final double c = -numer/denom; for (IndexValue iv : x_t) { int idx = iv.getIndex(); double x_ti = iv.getValue()*sigmaV.get(idx); sigmaV.increment(idx, c*x_ti*x_ti); } break; case PROJECT: for(IndexValue iv : x_t)//only the nonzero values in x_t will cause a change in value { int idx = iv.getIndex(); double x_r = iv.getValue(); double S_rr = sigmaV.get(idx); sigmaV.set(idx, 1/(1/S_rr+numer*x_r*x_r)); } break; case EXACT: for(IndexValue iv : x_t)//only the nonzero values in x_t will cause a change in value { int idx = iv.getIndex(); double x_r = iv.getValue(); double S_rr = sigmaV.get(idx); sigmaV.set(idx, S_rr/(Math.pow(S_rr*x_r*x_r*C+1, 2))); } break; } //zero out temp space if(covMode == CovMode.FULL) Sigma_xt.zeroOut(); } @Override public CategoricalResults classify(DataPoint data) { if(w == null) throw new UntrainedModelException("Model has not yet ben trained"); CategoricalResults cr = new CategoricalResults(2); double score = getScore(data); if(score < 0) cr.setProb(0, 1.0); else cr.setProb(1, 1.0); return cr; } @Override public double getScore(DataPoint dp) { return w.dot(dp.getNumericalValues()); } @Override public boolean supportsWeightedData() { return false; } /** * Guess the distribution to use for the regularization term * {@link #setC(double) C} . * * @param d the data set to get the guess for * @return the guess for the C parameter */ public static Distribution guessC(DataSet d) { return new LogUniform(Math.pow(2, -4), Math.pow(2, 4));//from Exact Soft Confidence-Weighted Learning paper } }

Ads help maintain this website.