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;

/**
 * An implementation of Adaptive Regularization of Weight Vectors (AROW), which 
 * uses second order information to learn a large margin binary classifier. As 
 * such, updates can occur on correctly classified instances if they are not far
 * enough from the margin. Unlike many margin algorithms, it handles noise well.
 * 
* NOTE: This implementation does not add an implicit bias term, so the solution * goes through the origin *

* See: Crammer, K., Kulesza, A.,&Dredze, M. (2013). Adaptive * regularization of weight vectors. Machine Learning, 91(2), 155–187. * doi:10.1007/s10994-013-5327-x * * @author Edward Raff */ public class AROW extends BaseUpdateableClassifier implements BinaryScoreClassifier, Parameterized, SingleWeightVectorModel { private static final long serialVersionUID = 443803827811508204L; private Vec w; /** * Full covariance matrix */ private Matrix sigmaM; /** * Diagonal only covariance matrix */ private Vec sigmaV; private boolean diagonalOnly = false; private double r; /** * Temp vector used to store Sigma * x_t. Make sure the vector is zeroed out * before returning from update */ private Vec Sigma_xt; /** * Creates a new AROW learner */ public AROW() { this(1e-2, true); } /** * Creates a new AROW learner * @param r the regularization parameter * @param diagonalOnly whether or not to use only the diagonal of the covariance * @see #setR(double) * @see #setDiagonalOnly(boolean) */ public AROW(double r, boolean diagonalOnly) { setR(r); setDiagonalOnly(diagonalOnly); } /** * Copy constructor * @param other object to copy */ protected AROW(AROW other) { this.r = other.r; this.diagonalOnly = other.diagonalOnly; 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(); } /** * Using the full covariance matrix requires O(d2) work on * mistakes, where d is the dimension of the data. 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 diagonalOnly {@code true} to use only the diagonal of the covariance */ public void setDiagonalOnly(boolean diagonalOnly) { this.diagonalOnly = diagonalOnly; } /** * Returns {@code true} if the covariance matrix is restricted to its diagonal entries * @return {@code true} if the covariance matrix is restricted to its diagonal entries */ public boolean isDiagonalOnly() { return diagonalOnly; } /** * Sets the r parameter of AROW, which controls the regularization. Larger * values reduce the change in the model on each update. * @param r the regularization parameter in (0, Inf) */ public void setR(double r) { if(Double.isNaN(r) || Double.isInfinite(r) || r <= 0) throw new IllegalArgumentException("r must be a postive constant, not " + r); this.r = r; } /** * Returns the regularization parameter * @return the regularization parameter */ public double getR() { return r; } /** * 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 AROW clone() { return new AROW(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(diagonalOnly) { sigmaV = new DenseVector(numericAttributes); sigmaV.mutableAdd(1); } else sigmaM = Matrix.eye(numericAttributes); } @Override public void update(DataPoint dataPoint, int targetClass) { final Vec x_t = dataPoint.getNumericalValues(); final double y_t = targetClass*2-1; double m_t = x_t.dot(w); if(y_t == Math.signum(m_t)) return;//no update needed double v_t = 0; if(diagonalOnly) { for(IndexValue iv : x_t) { double x_ti = iv.getValue(); v_t += x_ti * x_ti * sigmaV.get(iv.getIndex()); } } else { sigmaM.multiply(x_t, 1, Sigma_xt); v_t = x_t.dot(Sigma_xt); } double b_t_inv = v_t+r; double alpha_t = Math.max(0, 1-y_t*m_t)/b_t_inv; if(!diagonalOnly) w.mutableAdd(alpha_t * y_t, Sigma_xt); else for (IndexValue iv : x_t) w.increment(iv.getIndex(), alpha_t * y_t * iv.getValue() * sigmaV.get(iv.getIndex())); if(diagonalOnly) { /* diagonal is pairwise products as well: * S += S x x' S * S x == x' S b/c symmetry * S += Sx Sx * so just square the values and then add */ for(IndexValue iv : x_t) { int idx = iv.getIndex(); double xt_i = iv.getValue()*sigmaV.get(idx); sigmaV.increment(idx, -(xt_i*xt_i)/b_t_inv); } } else { //Because Sigma is symetric, x*S == S*x Matrix.OuterProductUpdate(sigmaM, Sigma_xt, Sigma_xt, -1/b_t_inv); } //Zero out temp store if(diagonalOnly) 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; } @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; } /** * Guess the distribution to use for the regularization term * {@link #setR(double) r} . * * @param d the data set to get the guess for * @return the guess for the r parameter */ public static Distribution guessR(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.