package jsat.classifiers.linear;

import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.exceptions.FailedToFitException;
import jsat.linear.Vec;
import static java.lang.Math.*;
import java.util.List;
import jsat.SingleWeightVectorModel;
import jsat.linear.DenseVector;
import jsat.linear.IndexValue;
import jsat.lossfunctions.LogisticLoss;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;

/**
 * This is an implementation of Bayesian Binary Regression for L1 and
 * L2 regularized logistic regression. This model requires additional
 * memory to perform efficient column wise passes on the data set, assuming the
 * data is sparse. 

* BBR uses a Trust Region Newton algorithm that allows convergence to occur in * a small number of iterations, but each iteration may be costly. *

* See: Genkin, A., Lewis, D. D.,&Madigan, D. (2007). Large-Scale Bayesian * Logistic Regression for Text Categorization. Technometrics, 49(3), * 291–304. doi:10.1198/004017007000000245 * * @author Edward Raff */ public class BBR implements Classifier, Parameterized, SingleWeightVectorModel { private static final long serialVersionUID = 8297213093357011082L; //weight vector w is refferd to as beta in the original paper, just replace beta with w private Vec w; private int maxIterations; private double regularization; private boolean autoSetRegularization = true; private double bias; private boolean useBias = true; private double tolerance = 0.0005; private Prior prior; /** * Valid priors that control what type of regularization is applied */ public static enum Prior { /** * Laplace prior equivalent to L1 regularization */ LAPLACE, /** * Gaussian prior equivalent to L2 regularization */ GAUSSIAN } /** * Creates a new BBR for L1 Logistic Regression object that will * use the given regularization value. * * @param regularization the regularization penalty to apply * @param maxIterations the maximum number of training iterations to perform */ public BBR(double regularization, int maxIterations) { this(regularization, maxIterations, Prior.LAPLACE); } /** * Creates a new BBR Logistic Regression object that will use the given * regularization value. * * @param regularization the regularization penalty to apply * @param maxIterations the maximum number of training iterations to perform * @param prior the prior to apply for regularization */ public BBR(double regularization, int maxIterations, Prior prior) { setMaxIterations(maxIterations); setRegularization(regularization); setAutoSetRegularization(false); setPrior(prior); } /** * Creates a new BBR for L1 Logistic Regression object that will * attempt to automatically determine the regularization value to use. * * @param maxIterations the maximum number of training iterations to perform */ public BBR(int maxIterations) { this(1e-3, maxIterations, Prior.LAPLACE); } /** * Creates a new BBR Logistic Regression object that will attempt to * automatically determine the regularization value to use. * * @param maxIterations the maximum number of training iterations to perform * @param prior the prior to apply for regularization */ public BBR(int maxIterations, Prior prior) { setMaxIterations(maxIterations); setRegularization(0.01); setAutoSetRegularization(true); setPrior(prior); } /** * Copy constructor * * @param toCopy the object to copy */ protected BBR(BBR toCopy) { if (toCopy.w != null) this.w = toCopy.w.clone(); this.maxIterations = toCopy.maxIterations; this.regularization = toCopy.regularization; this.autoSetRegularization = toCopy.autoSetRegularization; this.bias = toCopy.bias; this.useBias = toCopy.useBias; this.tolerance = toCopy.tolerance; this.prior = toCopy.prior; } /** * Sets the regularization penalty to use if the algorithm has not been set * to choose one automatically. * * @param regularization sets the positive regularization penalty to use */ public void setRegularization(double regularization) { if (Double.isNaN(regularization) || Double.isNaN(regularization) || regularization <= 0) throw new IllegalArgumentException("Regularization must be positive, not " + regularization); this.regularization = regularization; } /** * Returns the regularization penalty used if the auto value is not used * * @return the regularization penalty used if the auto value is not used */ public double getRegularization() { return regularization; } /** * Sets whether or not the regularization term will be set automatically by * the algorithm, which is done as specified in the original paper. This may * choose a very large (and bad) value of the regularization term, and * should not be used with smaller data sets. This value is chosen * deterministically. *

* This value takes precedence over anything set with * {@link #setRegularization(double) } * * @param autoSetRegularization {@code true} to choose the regularization * term automatically, {@code false} to use whatever value was set before. */ public void setAutoSetRegularization(boolean autoSetRegularization) { this.autoSetRegularization = autoSetRegularization; } /** * Returns whether or not the algorithm will attempt to select the * regularization term automatically * * @return {@code true} if the regularization term is chosen automatically, * {@code false} otherwise. */ public boolean isAutoSetRegularization() { return autoSetRegularization; } /** * Sets the maximum number of iterations allowed before halting the * algorithm early. * * @param maxIterations the maximum number of training iterations */ public void setMaxIterations(int maxIterations) { this.maxIterations = maxIterations; } /** * Returns the maximum number of iterations allowed * * @return the maximum number of iterations allowed */ public int getMaxIterations() { return maxIterations; } /** * Sets the convergence tolerance target. Relative changes that are smaller * than the given tolerance will determine convergence. *

* The default value used is that suggested in the original paper of 0.0005 * * @param tolerance the positive convergence tolerance goal */ public void setTolerance(double tolerance) { if (Double.isNaN(tolerance) || Double.isInfinite(tolerance) || tolerance <= 0) throw new IllegalArgumentException("Tolerance must be positive, not " + tolerance); this.tolerance = tolerance; } /** * Returns the tolerance parameter that controls convergence * * @return the tolerance parameter that controls convergence */ public double getTolerance() { return tolerance; } /** * Sets whether or not an implicit bias term should be added to the model. * * @param useBias {@code true} to add a bias term, {@code false} to exclude * the bias term. */ public void setUseBias(boolean useBias) { this.useBias = useBias; } /** * Returns {@code true} if a bias term is in use, {@code false} otherwise. * * @return {@code true} if a bias term is in use, {@code false} otherwise. */ public boolean isUseBias() { return useBias; } /** * Sets the regularizing prior used * * @param prior the prior to use */ public void setPrior(Prior prior) { this.prior = prior; } /** * Returns the regularizing prior in use * * @return the regularizing prior in use */ public Prior getPrior() { return prior; } /** * 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 bias; } @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 CategoricalResults classify(DataPoint data) { return LogisticLoss.classify(w.dot(data.getNumericalValues()) + bias); } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { train(dataSet); } @Override public void train(ClassificationDataSet dataSet) { final int D = dataSet.getNumNumericalVars(); if (D <= 0) throw new FailedToFitException("Data set contains no numeric features"); final Vec[] columnMajor = dataSet.getNumericColumns(); w = new DenseVector(D); double[] delta = new double[useBias ? D + 1 : D]; Arrays.fill(delta, 1.0); final int N = dataSet.getSampleSize(); double[] r = new double[N]; double[] y = new double[N]; for (int i = 0; i < N; i++) y[i] = dataSet.getDataPointCategory(i) * 2 - 1; final double lambda; if (autoSetRegularization) { //see equation (21) double normSqrdSum = 0; for (int i = 0; i < N; i++) normSqrdSum += pow(dataSet.getDataPoint(i).getNumericalValues().pNorm(2), 2); double sigma = D * N / normSqrdSum; //no regularization less than precision if (prior == Prior.LAPLACE) lambda = max(sqrt(2) / sigma, 1e-15); else lambda = max(sigma * sigma, 1e-15); } else lambda = regularization; double[] r_change = new double[N]; for (int iter = 0; iter < maxIterations; iter++) { for (int j = 0; j < D; j++) { double delta_vj = 0; final double w_jOrig = w.get(j); if (prior == Prior.LAPLACE) { //Algo 2 in the paper, computing delta_vj if (w_jOrig == 0) { //(try positive direction) delta_vj = tenativeUpdate(columnMajor, j, w_jOrig, y, r, lambda, 1.0, delta); if (delta_vj <= 0)//(positive direction failed) { //(try negative direction) delta_vj = tenativeUpdate(columnMajor, j, w_jOrig, y, r, lambda, -1.0, delta); if (delta_vj >= 0)//(negative direction failed) delta_vj = 0; } } else { final double sign = signum(w_jOrig); delta_vj = tenativeUpdate(columnMajor, j, w_jOrig, y, r, lambda, sign, delta); if (sign * (w_jOrig + delta_vj) < 0)//(cross over 0) delta_vj = -w_jOrig;//Done soe that w_j+-w_j = 0 } } else//Guassian prior { delta_vj = tenativeUpdate(columnMajor, j, w_jOrig, y, r, lambda, 0, delta); } double delta_wj = min(max(delta_vj, -delta[j]), delta[j]);//(limit step to trust region) for (IndexValue iv : columnMajor[j]) { final int i = iv.getIndex(); final double change = delta_wj * iv.getValue() * y[i]; r[i] += change; r_change[i] += change; } double newW_j = w_jOrig + delta_wj; //make tiny value zero if (abs(newW_j) < 1e-15)//Less than precions? its zero newW_j = 0; w.set(j, newW_j); delta[j] = max(2 * abs(delta_wj), delta[j] / 2); //(update size of trust region) } if (useBias)//update the bias term { double delta_vj; //Algo 2 in the paper, computing delta_vj if (bias == 0) { //(try positive direction) delta_vj = tenativeUpdate(null, D, bias, y, r, lambda, 1.0, delta); if (delta_vj <= 0)//(positive direction failed) { //(try negative direction) delta_vj = tenativeUpdate(null, D, bias, y, r, lambda, -1.0, delta); if (delta_vj >= 0)//(negative direction failed) delta_vj = 0; } } else { final double sign = signum(bias); delta_vj = tenativeUpdate(null, D, bias, y, r, lambda, sign, delta); if (sign * (bias + delta_vj) < 0)//(cross over 0) delta_vj = -bias;//Done soe that w_j+-w_j = 0 } double delta_wj = min(max(delta_vj, -delta[D]), delta[D]);//(limit step to trust region) for (int i = 0; i < N; i++) { final double change = delta_wj * y[i]; r[i] += change; r_change[i] += change; } double newW_j = bias + delta_wj; //make tiny value zero if (abs(newW_j) < 1e-15)//Less than precions? its zero newW_j = 0; bias = newW_j; delta[D] = max(2 * abs(delta_wj), delta[D] / 2); //(update size of trust region) } //Check for convergence double changeSum = 0, rSum = 0; for (int i = 0; i < N; i++) { changeSum += abs(r_change[i]); rSum += abs(r[i]); } if (changeSum / (1 + rSum) <= tolerance)//converged! break; Arrays.fill(r_change, 0.0);//resent changes for the next iteration } } private static double F(double r, double delta) { if (abs(r) <= delta) return 0.25; else return 1 / (2 + exp(abs(r) - delta) + exp(delta - abs(r))); } @Override public boolean supportsWeightedData() { return false; } @Override public BBR clone() { return new BBR(this); } /** * Gets the tentative update δvj * * @param columnMajor the column major vector array. May be null if using * the implicit bias term * @param j the column to work on * @param w_j the value of the coefficient, used only under Gaussian prior * @param y the array of label values * @param r the array of r values * @param lambda the regularization value to apply * @param s the update direction (should be +1 or -1). Used only under * Laplace prior * @param delta the array of delta values * @return the tentative update value */ private double tenativeUpdate(final Vec[] columnMajor, final int j, final double w_j, final double[] y, final double[] r, final double lambda, final double s, final double[] delta) { double numer = 0, denom = 0; if (columnMajor != null) { Vec col_j = columnMajor[j]; if (col_j.nnz() == 0) return 0; for (IndexValue iv : col_j) { final double x_ij = iv.getValue(); final int i = iv.getIndex(); numer += x_ij * y[i] / (1 + exp(r[i])); denom += x_ij * x_ij * F(r[i], delta[j] * abs(x_ij)); if (prior == Prior.LAPLACE) numer -= lambda * s; else { numer -= w_j / lambda; denom += 1 / lambda; } } } else//bias term, all x_ij = 1 for (int i = 0; i < y.length; i++) { numer += y[i] / (1 + exp(r[i])) - lambda * s; denom += F(r[i], delta[j]); } return numer / denom; } }

Ads help maintain this website.