/*
* Copyright (C) 2017 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.classifiers.svm.extended;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.distributions.Uniform;
import jsat.exceptions.FailedToFitException;
import jsat.linear.*;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.FakeExecutor;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
/**
* This class implements the Convex Polytope Machine (CPM), which is an
* extension of the Linear SVM. It is a binary classifier that has training time
* proportionate to the linear case, but can obtain accuracies closer to that of
* a kernelized SVM.
* Similar to the {@link AMM AMM} classifier, CPM uses multiple linear
* hyper-planes to create a non-linear classifier. Increasing the number of
* hyper-planes increases training/prediction time, but also increases the
* amount of non-linearity the model can tolerate.
*
* While the CPM implements the {@link BinaryScoreClassifier} interface, the CPM
* decision algorithm does not completely lend itself to producing a natural
* score in this manner. For this reason you may observe unusual behavior from
* the CPM if you rely on this interface, compared with other approaches.
*
*
*
See: Kantchelian, A., Tschantz, M. C., Huang, L., Bartlett, P. L.,
* Joseph, A. D., & Tygar, J. D. (2014). Large-margin Convex Polytope Machine.
* In Proceedings of the 27th International Conference on Neural Information
* Processing Systems (pp. 3248–3256). Cambridge, MA, USA: MIT Press. Retrieved
* from here
* @author Edward Raff
*/
public class CPM implements BinaryScoreClassifier, Classifier, Parameterized
{
private static final long serialVersionUID = 3171068484917637037L;
private int epochs;
private double lambda;
private int K;
private double entropyThreshold;
private double h;
private Matrix Wp;
private Matrix Wn;
private Vec bp;
private Vec bn;
/**
* Creates a new CPM classifier, with default parameters that should work
* well for most cases.
*/
public CPM()
{
this(1.0);
}
/**
* Creates a new CPM classifier
* @param K the number of hyper-planes to learn with.
*/
public CPM(int K)
{
this(1.0, K);
}
/**
* Creates a new CPM classifier
* @param lambda the regularization parameter
*/
public CPM(double lambda)
{
this(lambda, 16);
}
/**
* Creates a new CPM classifier
* @param lambda the regularization parameter
* @param K the number of hyper-planes to learn with.
*/
public CPM(double lambda, int K)
{
this(lambda, K, 3.0);
}
/**
* Creates a new CPM classifier
* @param lambda the regularization parameter
* @param K the number of hyper-planes to learn with.
* @param entropyThreshold the parameter that encourages non-linearity to be exploited
*/
public CPM(double lambda, int K, double entropyThreshold)
{
this(lambda, K, entropyThreshold, 50);
}
/**
* Creates a new CPM classifier
* @param lambda the regularization parameter
* @param K the number of hyper-planes to learn with.
* @param entropyThreshold the parameter that encourages non-linearity to be exploited
* @param epochs the number of training iterations
*/
public CPM(double lambda, int K, double entropyThreshold, int epochs)
{
setEpochs(epochs);
setLambda(lambda);
setK(K);
setEntropyThreshold(entropyThreshold);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public CPM(CPM toCopy)
{
this.epochs = toCopy.epochs;
this.lambda = toCopy.lambda;
this.K = toCopy.K;
this.entropyThreshold = toCopy.entropyThreshold;
this.h = toCopy.h;
if(toCopy.Wp != null)
this.Wp = toCopy.Wp.clone();
if(toCopy.Wn != null)
this.Wn = toCopy.Wn.clone();
if(toCopy.bp != null)
this.bp = toCopy.bp.clone();
if(toCopy.bn != null)
this.bn = toCopy.bn.clone();
}
/**
* Sets the entropy threshold used for training. It ensures a diversity of
* hyper-planes are used, where larger values encourage using more of the
* hyper planes.
*
* This method is adjusted from the paper's definition so that the input can
* be any non-negative value. It is recommended to try values in the range
* of [0, 10]
*
* @param entropyThreshold the non-negative parameter for hyper-plane diversity
*/
public void setEntropyThreshold(double entropyThreshold)
{
if(entropyThreshold < 0 || Double.isNaN(entropyThreshold) || Double.isInfinite(entropyThreshold))
throw new IllegalArgumentException("Entropy threshold must be non-negative, not " + entropyThreshold);
this.entropyThreshold = entropyThreshold;
set_h_properly();
}
private void set_h_properly()
{
h = Math.log(entropyThreshold * K / 10.0)/Math.log(2);
if(h <= 0)
h = 0;
}
/**
*
* @return the non-negative parameter for hyper-plane diversity
*/
public double getEntropyThreshold()
{
return entropyThreshold;
}
/**
* Sets the regularization parameter λ to use. Larger values penalize
* model complexity. This value is adjusted from the form in the original
* paper so that you do not need to consider the number of epochs
* explicitly. The effective regularization will be divided by the total
* number of training updates.
*
* @param lambda the regularization parameter value to use, the recommended
* range range is (0, 104]
*/
public void setLambda(double lambda)
{
this.lambda = lambda;
}
/**
*
* @return the regularization parameter value
*/
public double getLambda()
{
return lambda;
}
/**
* Sets the number of hyper planes to use when training. A normal linear
* model is equivalent to using only 1 hyper plane. The more hyper planes
* used, the more modeling capacity the algorithm has, but the slower it
* will run.
*
* @param K the number of hyper planes to use.
*/
public void setK(int K)
{
this.K = K;
set_h_properly();
}
/**
*
* @return the number of hyper planes to use.
*/
public int getK()
{
return K;
}
/**
* Sets the number of whole iterations through the training set that will be
* performed for training
* @param epochs the number of whole iterations through the data set
*/
public void setEpochs(int epochs)
{
if(epochs < 1)
throw new IllegalArgumentException("epochs must be a positive value");
this.epochs = epochs;
}
/**
* Returns the number of epochs used for training
* @return the number of epochs used for training
*/
public int getEpochs()
{
return epochs;
}
@Override
public CategoricalResults classify(DataPoint data)
{
Vec x = data.getNumericalValues();
double pos_score = Wp.multiply(x).add(bp).max();
double neg_score = Wn.multiply(x).add(bn).max();
CategoricalResults cr = new CategoricalResults(2);
if(neg_score > 0 && pos_score > 0)//ambigious case, lets go with larger magnitude
{
if(neg_score > pos_score)
cr.setProb(0, 1.0);
else
cr.setProb(1, 1.0);
}
else if(neg_score > 0)
cr.setProb(0, 1.0);
else if(pos_score > 0)
cr.setProb(1, 1.0);
else if(neg_score > pos_score )//not actually how describes in paper, but its ambigious - so lets use larger to tie break
//ambig b/c if no model claims ownership, we get a score of 0
cr.setProb(0, 1.0);
else
cr.setProb(1, 1.0);
return cr;
}
@Override
public double getScore(DataPoint dp)
{
Vec x = dp.getNumericalValues();
double pos_score = Wp.multiply(x).add(bp).max();
double neg_score = Wn.multiply(x).add(bn).max();
return pos_score-neg_score;
}
@Override
public boolean supportsWeightedData()
{
return false;
}
/**
*
* @param dots dot product between the input and each of the k hyper planes
* @param owned a count of how many data points are assigned to this hyper plane
* @param assignments maps each data point to the hyper plane that owns it. May have negative values for points not yet assigned
* @param assigned_positive_instances the number of positive instances taht have been assigned to a hyper plane
*/
private int ASSIGN(Vec dots, int indx, int k_true_max, int[] owned, int[] assignments, int assigned_positive_instances)
{
//Done outside this function
// int k_true_max = 0;
// for(int i = 1; i < dots.length(); i++)
// if(dots.get(i) > dots.get(k_true_max))
// k_true_max = i;
int old_owner = assignments[indx];
double cur_entropy = 0;
double new_entropy = Double.POSITIVE_INFINITY;
int max_owned = 0;
if(assigned_positive_instances > K*10)//we have enough assignments to start estimating entropy
{
new_entropy = 0;
for(int i = 0; i < K; i++)
{
max_owned = Math.max(max_owned, owned[i]);//used later
// double p_i = owned[i]/(double)assigned_positive_instances;
double numer = owned[i];
double denom = assigned_positive_instances;
if(numer > 0 )
// cur_entropy += -p_i * Math.log(p_i)/Math.log(2);
cur_entropy += -numer*(Math.log(numer)-Math.log(denom))/(Math.log(2)*denom);
//now calculate for new_entropy
if(old_owner < 0)//every point has a differnt value, b/c denominator changes
{
denom++;
if(i == k_true_max)//numer changes here too
numer++;
if(numer > 0 )
new_entropy += -numer*(Math.log(numer)-Math.log(denom))/(Math.log(2)*denom);
}
else if(old_owner == k_true_max)//no change in ownership, means no change in entropy
{
new_entropy = cur_entropy;
}
else//change in ownership, denom remains the same, numer may change
{
if(i == k_true_max)
numer++;
else if(i == old_owner)
numer--;
if(numer > 0 )
new_entropy += -numer*(Math.log(numer)-Math.log(denom))/(Math.log(2)*denom);
}
}
new_entropy += cur_entropy;//new was calcualted as a delta from cur, so by adding we get the correct value
}
if(new_entropy >= h)//if ENTROPY(UNADJ +(x, kunadj)) ≥ h then
return k_true_max;
//else
//find max that would result in an increase in entropy
int k_inc_max = 0;
if (old_owner >= 0)//don't need to compute entropy, moving to any position that owns fewer would increase entropy
{
for (int i = 1; i < dots.length(); i++)
if (owned[old_owner] > owned[i] && dots.get(i) > dots.get(k_inc_max))
k_inc_max = i;
}
else//not assigned, assign to anyone owns less than the most to improve
{
double best_score = Double.NEGATIVE_INFINITY;
for (int i = 1; i < dots.length(); i++)
if (max_owned > owned[i] && dots.get(i) > best_score)
{
k_inc_max = i;
best_score = dots.get(i);
}
if(Double.isInfinite(best_score))//why couldn't we find someone? Bail out
return k_true_max;//Lets just give the original max
}
return k_inc_max;
}
/**
* Training procedure that can be applied to each version of the CPM
* sub-problem.
*
* @param D the dataset to train on
* @param W the weight matrix of vectors to use
* @param b a vector that stores the associated bias terms for each weigh
* vector.
* @param sign_mul Either positive or negative 1. Controls whether or not
* the positive or negative class is to be enveloped by the polytype
*/
private void sgdTrain(ClassificationDataSet D, MatrixOfVecs W, Vec b, int sign_mul, boolean parallel)
{
IntList order = new IntList(D.getSampleSize());
ListUtils.addRange(order, 0, D.getSampleSize(), 1);
final double lambda_adj = lambda/(D.getSampleSize()*epochs);
int[] owned = new int[K];//how many points does thsi guy own?
int assigned_positive_instances = 0;//how many points in the positive class have been assigned?
int[] assignments = new int[D.getSampleSize()];//who owns each data point
Arrays.fill(assignments, -1);//Starts out that no one is assigned!
Vec dots = new DenseVector(W.rows());
long t = 0;
for(int epoch = 0; epoch < epochs; epoch++)
{
Collections.shuffle(order);
for(int i : order)
{
t++;
double eta = 1/(lambda_adj*t);
Vec x_i = D.getDataPoint(i).getNumericalValues();
int y_i = (D.getDataPointCategory(i)*2-1)*sign_mul;
//this sets dots = bias, which we then add to with matrix-vector product
//result is the same as dots = W x_i + b
b.copyTo(dots);
W.multiply(x_i, 1.0, dots);
if(y_i == -1)
{
for(int k = 0; k < K; k++)
if(dots.get(k) > -1)
{
W.getRowView(k).mutableSubtract(eta, x_i);
b.increment(k, -eta);
}
}
else//y_i == 1
{
int k_true_max = 0;
for(int k = 1; k < dots.length(); k++)
if(dots.get(k) > dots.get(k_true_max))
k_true_max = k;
if(dots.get(k_true_max) < 1)
{
int z = ASSIGN(dots, i, k_true_max, owned, assignments, assigned_positive_instances);
W.getRowView(z).mutableAdd(eta, x_i);
b.increment(z, eta);
//book keeping
if(assignments[i] < 0)//first assignment, inc counter
assigned_positive_instances++;
else//change owner, decrement ownership count
owned[assignments[i]]--;
owned[z]++;
assignments[i] = z;
}
}
// W.mutableMultiply(1-eta*lambda);
//equivalent form, more stable
W.mutableMultiply(1-1.0/t);
b.mutableMultiply(1-1.0/t);
}
}
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
if(dataSet.getPredicting().getNumOfCategories() > 2)
throw new FailedToFitException("CPM is a binary classifier, it can not be trained on a dataset with " + dataSet.getPredicting().getNumOfCategories() + " classes");
final int d = dataSet.getNumNumericalVars();
List Wv_p = new ArrayList(K);
List Wv_n = new ArrayList(K);
bp = new DenseVector(K);
bn = new DenseVector(K);
for(int i = 0; i < K; i++)
{
Wv_p.add(new ScaledVector(new DenseVector(d)));
Wv_n.add(new ScaledVector(new DenseVector(d)));
}
MatrixOfVecs W_p = new MatrixOfVecs(Wv_p);
MatrixOfVecs W_n = new MatrixOfVecs(Wv_n);
sgdTrain(dataSet, W_p, bp, +1, parallel);
sgdTrain(dataSet, W_n, bn, -1, parallel);
this.Wp = new DenseMatrix(W_p);
this.Wn = new DenseMatrix(W_n);
}
@Override
public CPM clone()
{
return new CPM(this);
}
/**
* Provides a distribution of reasonable values for the
* {@link #setLambda(double) λ} parameter
*
* @param d the dataset to get the guess for
* @return the distribution to search this parameter from
*/
public static Distribution guessLambda(DataSet d)
{
return new LogUniform(1e-1, 1e4);
}
/**
* Provides a distribution of reasonable values for the {@link #setEntropyThreshold(double)
* } parameter
*
* @param d the dataset to get the guess for
* @return the distribution to search this parameter from
*/
public static Distribution guessEntropyThreshold(DataSet d)
{
return new Uniform(1e-1, 10);
}
}
Ads help maintain this website.