package jsat.classifiers.linear;

import static java.lang.Math.*;
import java.util.*;
import jsat.DataSet;
import jsat.SimpleWeightVectorModel;
import jsat.classifiers.*;
import jsat.distributions.Distribution;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.IndexTable;

/**
 * Support class Passive Aggressive (SPA) is a multi class generalization of 
 * {@link PassiveAggressive}. It works in the same philosophy, and can obtain 
 * better multi class accuracy then PA  used with a meta learner. 
* SPA is more sensitive to small values for the {@link #setC(double) * aggressiveness parameter}.
* If working with a binary classification problem, SPA reduces to PA, and the * original PA implementation should be used instead.
* By default, the {@link #setUseBias(boolean) biast term} is not used. *

* See:
* Matsushima, S., Shimizu, N., Yoshida, K., Ninomiya, T.,&Nakagawa, H. * (2010). Exact Passive-Aggressive Algorithm for Multiclass Classification * Using Support Class. SIAM International Conference on Data Mining - SDM * (pp. 303–314). Retrieved from * here * * @author Edward Raff */ public class SPA extends BaseUpdateableClassifier implements Parameterized, SimpleWeightVectorModel { private static final long serialVersionUID = 3613279663279244169L; private Vec[] w; private double[] bias; private double C = 1; private boolean useBias = false; private PassiveAggressive.Mode mode; /** * Creates a new Passive Aggressive learner that does 10 epochs and uses * PA2. */ public SPA() { this(10, PassiveAggressive.Mode.PA2); } /** * Creates a new Passive Aggressive learner * * @param epochs the number of training epochs to use during batch training * @param mode which version of the update to perform */ public SPA(int epochs, PassiveAggressive.Mode mode) { setEpochs(epochs); setMode(mode); } /** * Sets whether or not the implementation will use an implicit bias term * appended to the inputs or not. * @param useBias {@code true} to add an implicit bias term, {@code false} * to use the data as given */ public void setUseBias(boolean useBias) { this.useBias = useBias; } /** * Returns true if an implicit bias term will be added, false otherwise * @return true if an implicit bias term will be added, false otherwise */ public boolean isUseBias() { return useBias; } /** * 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 *
* An infinitely large value is equivalent to being completely aggressive, * and is performed when the mode is set to {@link PassiveAggressive.Mode#PA}. * * @param C the positive aggressiveness parameter */ public void setC(double C) { if(Double.isNaN(C) || Double.isInfinite(C) || C <= 0) throw new ArithmeticException("Aggressiveness must be a positive constant"); this.C = C; } /** * Returns the aggressiveness parameter * @return the aggressiveness parameter */ public double getC() { return C; } /** * Sets which version of the PA update is used. * @param mode which PA update style to perform */ public void setMode(PassiveAggressive.Mode mode) { this.mode = mode; } /** * Returns which version of the PA update is used * @return which PA update style is used */ public PassiveAggressive.Mode getMode() { return mode; } @Override public Vec getRawWeight(int index) { return w[index]; } @Override public double getBias(int index) { return bias[index]; } @Override public int numWeightsVecs() { return w.length; } @Override public SPA clone() { SPA clone = new SPA(); if(this.w != null) { clone.w = new Vec[this.w.length]; for(int i = 0; i < w.length; i++) clone.w[i] = this.w[i].clone(); } if(this.it != null) clone.it = new IndexTable(this.it.length()); if(this.loss != null) clone.loss = Arrays.copyOf(this.loss, this.loss.length); clone.C = this.C; clone.mode = this.mode; if(this.bias != null) clone.bias = Arrays.copyOf(this.bias, this.bias.length); clone.useBias = this.useBias; return clone; } @Override public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes, CategoricalData predicting) { w = new Vec[predicting.getNumOfCategories()]; for(int i = 0; i < w.length; i++) w[i] = new DenseVector(numericAttributes); bias = new double[w.length]; loss = new double[w.length]; it = new IndexTable(w.length); } private double[] loss; private IndexTable it; /** * Part A of SPA algorithm * @param xNorm the value of the squared 2 norm training input * @param k the value of k * @param loss_k the loss of the k'th sorted value * @return the target support class goal to be less than */ private double getSupportClassGoal(final double xNorm, final int k, final double loss_k) { if(mode == PassiveAggressive.Mode.PA1) return min((k-1)*loss_k+C*xNorm, k*loss_k); else if(mode == PassiveAggressive.Mode.PA2) return ((k*xNorm+(k-1)/(2*C))/(xNorm+1.0/(2*C)))*loss_k; else return k*loss_k; } /** * Part B of SPA algorithm * @param loss_cur the loss for the current value in consideration * @param xNorm the value of the squared 2 norm training input * @param k the value of k (number of support classes +1) * @param supLossSum the sum of the loss for the support classes * @return the update step size */ private double getStepSize(final double loss_cur, final double xNorm, int k, final double supLossSum) { if(mode == PassiveAggressive.Mode.PA1) return max(0, loss_cur-max(supLossSum/(k-1)-C/(k-1)*xNorm, supLossSum/k))/xNorm; else if(mode == PassiveAggressive.Mode.PA2) return max(0, loss_cur-(xNorm+1/(2*C))/(k*xNorm+(k-1)/(2*C))*supLossSum )/xNorm; else return max(0, loss_cur-supLossSum/k)/xNorm; } @Override public void update(DataPoint dataPoint, int targetClass) { Vec x = dataPoint.getNumericalValues(); final double w_y_dot_x = w[targetClass].dot(x) + bias[targetClass]; for (int v = 0; v < w.length; v++) if (v != targetClass) loss[v] = max(0, 1 - (w_y_dot_x - w[v].dot(x) - bias[v])); else loss[v] = Double.POSITIVE_INFINITY;//set in Inft so its ends up in index 0, and gets skipped final double xNorm = pow(x.pNorm(2) + (useBias ? 1 : 0), 2); it.sortR(loss); int k = 1; double T31 = 0;//Theorem 3.1 while (k < loss.length && T31 < getSupportClassGoal(xNorm, k, loss[it.index(k)])) T31 += loss[it.index(k++)]; double supportLossSum = 0; for (int j = 1; j < k; j++) supportLossSum += loss[it.index(j)]; for (int j = 1; j < k; j++) { final int v = it.index(j); double tau = getStepSize(loss[v], xNorm, k, supportLossSum); w[targetClass].mutableAdd(tau, x); w[v].mutableSubtract(tau, x); if (useBias) { bias[targetClass] += tau; bias[v] -= tau; } } } @Override public CategoricalResults classify(DataPoint data) { Vec x = data.getNumericalValues(); CategoricalResults cr = new CategoricalResults(w.length); int maxIdx = 0; double maxVAl = w[0].dot(x)+bias[0]; for(int i = 1; i < w.length; i++) { double val = w[i].dot(x)+bias[i]; if(val > maxVAl) { maxVAl = val; maxIdx = i; } } cr.setProb(maxIdx, 1.0); return cr; } @Override public boolean supportsWeightedData() { return false; } /** * Guess the distribution to use for the regularization term * {@link #setC(double) C} in Support PassiveAggressive. * * @param d the data set to get the guess for * @return the guess for the C parameter */ public static Distribution guessC(DataSet d) { return PassiveAggressive.guessC(d); } }

Ads help maintain this website.