package jsat.classifiers.linear;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.SingleWeightVectorModel;
import jsat.classifiers.*;
import jsat.classifiers.svm.PlattSMO;
import jsat.distributions.Distribution;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.lossfunctions.LogisticLoss;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.IntList;
import jsat.utils.ListUtils;

/**
 * This provides an implementation of regularized logistic regression using Dual
 * Coordinate Descent. This algorithm works well on both dense and sparse large
 * data sets. 
 * 

* The regularized problem is of the form:
* C Σ log(1+exp(-yiwTxi)) + wTw/2 *

* See:
* Yu, H.-F., Huang, F.-L.,&Lin, C.-J. (2010). Dual Coordinate Descent * Methods for Logistic Regression and Maximum Entropy Models. Machine * Learning, 85(1-2), 41–75. doi:10.1007/s10994-010-5221-8 * * @author Edward Raff */ public class LogisticRegressionDCD implements Classifier, Parameterized, SingleWeightVectorModel { private static final long serialVersionUID = -5813704270903243462L; private static final double eps_1 = 1e-3; private static final double eps_2 = 1e-8; private Vec w; private double bias; private boolean useBias; private double C; private int maxIterations; /** * Creates a new Logistic Regression learner that does no more than 100 * training iterations with a default regularization tradeoff of C = 1 */ public LogisticRegressionDCD() { this(1.0); } /** * Creates a new Logistic Regression learner that does no more than 100 * training iterations. * @param C the regularization tradeoff term */ public LogisticRegressionDCD(double C) { this(C, 100); } /** * Creates a new Logistic Regression learner * @param C the regularization tradeoff term * @param maxIterations the maximum number of iterations through the data set */ public LogisticRegressionDCD(double C, int maxIterations) { setC(C); setMaxIterations(maxIterations); } /** * Copy constructor * @param toCopy the object to copy */ protected LogisticRegressionDCD(LogisticRegressionDCD toCopy) { this(toCopy.C, toCopy.maxIterations); if(toCopy.w != null) this.w = toCopy.w.clone(); this.bias = toCopy.bias; this.useBias = toCopy.useBias; } /** * Sets the regularization trade-off term. larger values reduce the amount * of regularization, and smaller values increase the regularization. * * @param C the positive regularization tradeoff value */ public void setC(double C) { if(C <= 0 || Double.isInfinite(C) || Double.isNaN(C)) throw new IllegalArgumentException("C must be a positive constant, not " + C); this.C = C; } /** * Returns the regularization tradeoff parameter * @return the regularization tradeoff parameter */ public double getC() { return C; } /** * Sets the maximum number of iterations the algorithm is allowed to run * for. * @param maxIterations the maximum number of iterations */ public void setMaxIterations(int maxIterations) { if(maxIterations < 1) throw new IllegalArgumentException("iterations must be a positive value, not " + maxIterations); this.maxIterations = maxIterations; } /** * Returns the maximum number of iterations the algorithm is allowed to run * @return the maximum number of iterations the algorithm is allowed to run */ public int getMaxIterations() { return maxIterations; } /** * 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; } @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) { if(dataSet.getClassSize() != 2) throw new FailedToFitException("Logistic Regression is a binary classifier, can can not handle " + dataSet.getClassSize() + " class problems"); final int N = dataSet.getSampleSize(); List x = dataSet.getDataVectors(); double[] alpha = new double[N]; double[] alphaPrime = new double[N]; double[] Q_ii = new double[N]; int[] y = new int[N]; /* * All points start will small eps, because LR dosn't tend to zero out * coefficients. But we expect a few alphas to quickly go to larger * values. */ Arrays.fill(alpha, Math.min(eps_1*C, eps_2)); Arrays.fill(alphaPrime, C-alpha[0]); w = new DenseVector(dataSet.getNumNumericalVars()); bias = 0; for(int i = 0; i < N; i++) { y[i] = dataSet.getDataPointCategory(i)*2-1; Vec x_i = x.get(i); Q_ii[i] = x_i.dot(x_i); w.mutableAdd(alpha[0]*y[i], x_i);//all alpha are the same right now if(useBias) bias += alpha[0]*y[i]; } IntList permutation = new IntList(N); ListUtils.addRange(permutation, 0, N, 1); for(int iter = 0; iter < maxIterations; iter++) { Collections.shuffle(permutation); double maxChange = 0; for(int i : permutation) { Vec x_i = x.get(i); //Step 1. final double c1 = alpha[i], c2 = alphaPrime[i]; double a = Q_ii[i], b = y[i] * (w.dot(x_i) + bias); double z_m = (c2 - c1) / 2, s = c1 + c2; boolean case1 = z_m >= -b / a; double z;//see eq (35) if (case1) { if (c1 >= s / 2) z = 0.1 * c1; else z = c1; } else { if (c2 >= s / 2) z = 0.1 * c2; else z = c2; } //what if z is very small? Leave it alone.. if(z < 1e-20) continue; //Step 2. //Algorithm 4 solving equation (18) //would it really take more than 100 iterations? for(int subIter = 0; subIter < 100; subIter++) { double gP = Math.log(z/(C-z)); if(case1) gP += a*(z-c1)+ b; else gP += a*(z-c2)-b; //check if "0" if(Math.abs(gP) < 1e-6) break; double gPP= a + s/(z*(s-z)); double d = -gP/gPP; if(z + d <= 0) z *= 0.1;//unsepcified shrinkage term: just use 0.1 else z += d; } //Step 4. alpha_i = Z1, alpha'_i = Z2. if(case1) { alpha[i] = z; alphaPrime[i] = C-z; } else { alpha[i] = C-z; alphaPrime[i] = z; } //Step 3. w = w + (Z1 −alpha_i) yi xi double change = (alpha[i]-c1); w.mutableAdd(change*y[i], x_i); if(useBias) bias += change*y[i]; maxChange = Math.max(maxChange, change); } //Convergence check if(Math.abs(maxChange) < 1e-4) return; } } @Override public boolean supportsWeightedData() { return false; } @Override public Classifier clone() { return new LogisticRegressionDCD(this); } /** * 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; } /** * Guess the distribution to use for the regularization term * {@link #setC(double) C} in Logistic Regression. * * @param d the data set to get the guess for * @return the guess for the C parameter */ public static Distribution guessC(DataSet d) { return PlattSMO.guessC(d); } }

Ads help maintain this website.