edu.illinois.cs.cogcomp.lbjava.learn

Class SupportVectorMachine

java.lang.Object

edu.illinois.cs.cogcomp.lbjava.classify.Classifier

edu.illinois.cs.cogcomp.lbjava.learn.Learner

edu.illinois.cs.cogcomp.lbjava.learn.SupportVectorMachine

All Implemented Interfaces:

Serializable, Cloneable

public class SupportVectorMachine
extends Learner

Wrapper class for the liblinear library which supports support vector machine classification. That library must be downloaded separately and placed on your CLASSPATH for this class to work correctly. This class can perform both binary classification and multi-class classification. It is assumed that Learner.labeler is a single discrete classifier that produces the same feature for every example object. Assertions will produce error messages if this assumption does not hold.

When calling this algorithm in a with clause inside an LBJava source file, there is no need to specify the rounds clause. At runtime, calling Learner.learn(Object) merely performs feature extraction and stores an indexed representation of the example vector in memory. The learning algorithm executes when doneLearning() is called. This call also frees the memory in which the example vectors are stored. Thus, subsequent calls to Learner.learn(Object) and doneLearning() will discard the previous hypothesis and learn an entirely new one.

liblinear performs binary classification (as opposed to 1-vs.-all) whenever the solver type is not MCSVM_CS and exactly two class labels are observed in the training data.

This algorithm's user-configurable parameters are stored in member fields of this class. They may be set via either a constructor that names each parameter explicitly or a constructor that takes an instance of Parameters as input. The documentation in each member field in this class indicates the default value of the associated parameter when using the former type of constructor. The documentation of the associated member field in the Parameters class indicates the default value of the parameter when using the latter type of constructor.

Author:

Michael Paul

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SupportVectorMachine.Parameters A container for all of SupportVectorMachine's configurable parameters.

Field Summary

Fields

Modifier and Type	Field and Description
protected edu.illinois.cs.cogcomp.core.datastructures.vectors.OVector	allExamples The array of example vectors.
protected edu.illinois.cs.cogcomp.core.datastructures.vectors.IVector	allLabels The array of example labels
protected String[]	allowableValues The label producing classifier's allowable values.
protected double	bias If bias >= 0, an instance vector x becomes [x; bias]; otherwise, if bias < 0, no bias term is added.
protected int	biasFeatures The number of bias features; there are either 0 or 1 of them.
protected double	C The cost parameter C; default defaultC
protected boolean	conjunctiveLabels Whether or not this learner's labeler produces conjunctive features.
static double	defaultBias Default for bias.
static double	defaultC Default for C.
static double	defaultEpsilon Default for epsilon.
static String	defaultSolverType Default for solverType.
protected boolean	displayLL Controls if liblinear-related messages are output
protected double	epsilon The tolerance of termination criterion; default defaultEpsilon.
protected Lexicon	newLabelLexicon Created during doneLearning() in case the training examples observed by learn(int[],double[],int[],double[]) are only a subset of a larger, pre-extracted set.
protected int	numClasses The number of unique class labels seen during training.
protected int	numFeatures The number of unique features seen during training.
protected String	solverType The type of solver; default defaultSolverType unless there are more than 2 labels observed in the training data, in which case "MCSVM_CS" becomes the default.
protected double[]	weights An array of weights representing the weight vector learned after training with liblinear.

Fields inherited from class edu.illinois.cs.cogcomp.lbjava.learn.Learner

candidates, encoding, extractor, labeler, labelLexicon, lcFilePath, lexFilePath, lexicon, lossFlag, predictions, readLexiconOnDemand

Fields inherited from class edu.illinois.cs.cogcomp.lbjava.classify.Classifier

containingPackage, name

Constructor Summary

Constructors

Constructor and Description
SupportVectorMachine() Default constructor.
SupportVectorMachine(double c) Initializing constructor.
SupportVectorMachine(double c, double e) Initializing constructor.
SupportVectorMachine(double c, double e, double b) Initializing constructor.
SupportVectorMachine(double c, double e, double b, String s) Initializing constructor.
SupportVectorMachine(double c, double e, double b, String s, boolean d) Initializing constructor.
SupportVectorMachine(String n) Initializing constructor.
SupportVectorMachine(String n, double c) Initializing constructor.
SupportVectorMachine(String n, double c, double e) Initializing constructor.
SupportVectorMachine(String n, double c, double e, double b) Initializing constructor.
SupportVectorMachine(String n, double c, double e, double b, String s) Initializing constructor.
SupportVectorMachine(String n, double c, double e, double b, String s, boolean d) Initializing constructor.
SupportVectorMachine(String n, SupportVectorMachine.Parameters p) Initializing constructor.
SupportVectorMachine(SupportVectorMachine.Parameters p) Initializing constructor.

Method Summary

Modifier and Type	Method and Description
String[]	allowableValues() Returns the array of allowable values that a feature returned by this classifier may take.
FeatureVector	classify(int[] exampleFeatures, double[] exampleValues) Evaluates the given example using liblinear's prediction method.
protected Feature	conjunctiveValueOf(int[] exampleFeatures, double[] exampleValues, Iterator I) This method is a surrogate for valueOf(int[],double[],Collection) when the labeler is known to produce conjunctive features.
String	discreteValue(int[] exampleFeatures, double[] exampleValues) The evaluate method returns the class label which yields the highest score for this example.
void	doneLearning() This method converts the arrays of examples stored in this class into input for the liblinear training method.
Feature	featureValue(int[] f, double[] v) Returns the classification of the given example as a single feature instead of a FeatureVector.
void	forget() Resets the internal bookkeeping.
int	getNumClasses()
Learner.Parameters	getParameters() Retrieves the parameters that are set in this learner.
double[]	getWeights()
void	initialize(int ne, int nf) Initializes the example vector arrays.
void	learn(int[] exampleFeatures, double[] exampleValues, int[] exampleLabels, double[] labelValues) This method adds the example's features and labels to the arrays storing the training examples.
void	read(edu.illinois.cs.cogcomp.core.datastructures.vectors.ExceptionlessInputStream in) Reads the binary representation of a learner with this object's run-time type, overwriting any and all learned or manually specified parameters as well as the label lexicon but without modifying the feature lexicon.
double	score(int[] exampleFeatures, double[] exampleValues, int label) Computes the dot product of the specified feature vector and the weight vector associated with the supplied class.
double	score(Object example) Computes the dot product of the specified example vector and the weight vector associated with the supplied class.
double	score(Object example, int label) Computes the dot product of the specified example vector and the weight vector associated with the supplied class.
ScoreSet	scores(int[] exampleFeatures, double[] exampleValues) An SVM returns a classification score for each class.
void	setLabeler(Classifier l) Sets the labels list.
void	setParameters(SupportVectorMachine.Parameters p) Sets the values of parameters that control the behavior of this learning algorithm.
Feature	valueOf(int[] exampleFeatures, double[] exampleValues, Collection candidates) Using this method, the winner-take-all competition is narrowed to involve only those labels contained in the specified list.
Feature	valueOf(Object example, Collection candidates) Using this method, the winner-take-all competition is narrowed to involve only those labels contained in the specified list.
void	write(edu.illinois.cs.cogcomp.core.datastructures.vectors.ExceptionlessOutputStream out) Writes the learned function's internal representation in binary form.
void	write(PrintStream out) Writes the algorithm's internal representation as text.

Methods inherited from class edu.illinois.cs.cogcomp.lbjava.learn.Learner

classify, classify, classify, classify, clone, countFeatures, createPrediction, createPrediction, demandLexicon, discreteValue, discreteValue, doneWithRound, emptyClone, featureValue, featureValue, getCurrentLexicon, getExampleArray, getExampleArray, getExtractor, getLabeler, getLabelLexicon, getLexicon, getLexiconDiscardCounts, getLexiconLocation, getModelLocation, getPrunedLexiconSize, learn, learn, learn, learn, read, readLabelLexicon, readLearner, readLearner, readLearner, readLearner, readLearner, readLearner, readLexicon, readLexicon, readLexiconOnDemand, readLexiconOnDemand, readModel, readModel, readParameters, realValue, realValue, realValue, save, saveLexicon, saveModel, scores, scores, scoresAugmented, setCandidates, setEncoding, setExtractor, setLabelLexicon, setLexicon, setLexiconLocation, setLexiconLocation, setLossFlag, setModelLocation, setModelLocation, setParameters, setReadLexiconOnDemand, unclone, unsetLossFlag, write, writeLexicon, writeModel, writeParameters

Methods inherited from class edu.illinois.cs.cogcomp.lbjava.classify.Classifier

classify, discreteValueArray, getCompositeChildren, getInputType, getOutputType, realValueArray, test, toString, valueIndexOf

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

defaultSolverType

public static final String defaultSolverType

Default for solverType.

See Also:

Constant Field Values

defaultC

public static final double defaultC

Default for C.

See Also:

Constant Field Values

defaultEpsilon

public static final double defaultEpsilon

Default for epsilon.

See Also:

Constant Field Values

defaultBias

public static final double defaultBias

Default for bias.

See Also:

Constant Field Values

solverType

protected String solverType

The type of solver; default defaultSolverType unless there are more than 2 labels observed in the training data, in which case "MCSVM_CS" becomes the default. Note that if you are doing multi-class classification, you can still override the "MCSVM_CS" default to use another solver type.

Possible values:

• "L2_LR" = L2-regularized logistic regression;
• "L2LOSS_SVM_DUAL" = L2-loss support vector machines (dual);
• "L2LOSS_SVM" = L2-loss support vector machines (primal);
• "L1LOSS_SVM_DUAL" = L1-loss support vector machines (dual);
• "MCSVM_CS" = multi-class support vector machines by Crammer and Singer

C

protected double C

The cost parameter C; default defaultC

epsilon

protected double epsilon

The tolerance of termination criterion; default defaultEpsilon.

bias

protected double bias

If bias >= 0, an instance vector x becomes [x; bias]; otherwise, if bias < 0, no bias term is added.

biasFeatures

protected int biasFeatures

The number of bias features; there are either 0 or 1 of them.

displayLL

protected boolean displayLL

Controls if liblinear-related messages are output

numClasses

protected int numClasses

The number of unique class labels seen during training.

numFeatures

protected int numFeatures

The number of unique features seen during training.

conjunctiveLabels

protected boolean conjunctiveLabels

Whether or not this learner's labeler produces conjunctive features.

weights

protected double[] weights

An array of weights representing the weight vector learned after training with liblinear.

allLabels

protected edu.illinois.cs.cogcomp.core.datastructures.vectors.IVector allLabels

The array of example labels

allExamples

protected edu.illinois.cs.cogcomp.core.datastructures.vectors.OVector allExamples

The array of example vectors.

allowableValues

protected String[] allowableValues

The label producing classifier's allowable values.

newLabelLexicon

protected Lexicon newLabelLexicon

Created during doneLearning() in case the training examples observed by learn(int[],double[],int[],double[]) are only a subset of a larger, pre-extracted set. If this is not the case, it will simply be a duplicate reference to Learner.labelLexicon.

Constructor Detail

SupportVectorMachine

public SupportVectorMachine()

Default constructor. C, epsilon, the bias, and the solver type take the default values while the name of the classifier gets the empty string.

SupportVectorMachine

public SupportVectorMachine(double c)

Initializing constructor. The name of the classifier gets the empty string.

Parameters:

c - The desired C value.

SupportVectorMachine

public SupportVectorMachine(double c,
                            double e)

Initializing constructor. The name of the classifier gets the empty string.

Parameters:

c - The desired C value.

e - The desired epsilon value.

SupportVectorMachine

public SupportVectorMachine(double c,
                            double e,
                            double b)

Initializing constructor. The name of the classifier gets the empty string.

Parameters:

c - The desired C value.

e - The desired epsilon value.

b - The desired bias.

SupportVectorMachine

public SupportVectorMachine(double c,
                            double e,
                            double b,
                            String s)

Initializing constructor. The name of the classifier gets the empty string.

Parameters:

c - The desired C value.

e - The desired epsilon value.

b - The desired bias.

s - The solver type.

SupportVectorMachine

public SupportVectorMachine(double c,
                            double e,
                            double b,
                            String s,
                            boolean d)

Initializing constructor. The name of the classifier gets the empty string.

Parameters:

c - The desired C value.

e - The desired epsilon value.

b - The desired bias.

s - The solver type.

d - Toggles if the liblinear-related output should be displayed.

SupportVectorMachine

public SupportVectorMachine(String n)

Initializing constructor. C, epsilon, the bias, and the solver type take the default values.

Parameters:

n - The name of the classifier.

SupportVectorMachine

public SupportVectorMachine(String n,
                            double c)

Initializing constructor.

Parameters:

n - The name of the classifier.

c - The desired C value.

SupportVectorMachine

public SupportVectorMachine(String n,
                            double c,
                            double e)

Initializing constructor.

Parameters:

n - The name of the classifier.

c - The desired C value.

e - The desired epsilon value.

SupportVectorMachine

public SupportVectorMachine(String n,
                            double c,
                            double e,
                            double b)

Initializing constructor.

Parameters:

n - The name of the classifier.

c - The desired C value.

e - The desired epsilon value.

b - The desired bias.

SupportVectorMachine

public SupportVectorMachine(String n,
                            double c,
                            double e,
                            double b,
                            String s)

Initializing constructor.

Parameters:

n - The name of the classifier.

c - The desired C value.

e - The desired epsilon value.

b - The desired bias.

s - The solver type.

SupportVectorMachine

public SupportVectorMachine(String n,
                            double c,
                            double e,
                            double b,
                            String s,
                            boolean d)

Initializing constructor.

Parameters:

n - The name of the classifier.

c - The desired C value.

e - The desired epsilon value.

b - The desired bias.

s - The solver type.

d - Toggles if the liblinear-related output should be displayed.

SupportVectorMachine

public SupportVectorMachine(SupportVectorMachine.Parameters p)

Initializing constructor. Sets all member variables to their associated settings in the SupportVectorMachine.Parameters object. The name of the classifier gets the empty string.

Parameters:

p - The settings of all parameters.

SupportVectorMachine

public SupportVectorMachine(String n,
                            SupportVectorMachine.Parameters p)

Initializing constructor. Sets all member variables to their associated settings in the SupportVectorMachine.Parameters object.

Parameters:

n - The name of the classifier.

p - The settings of all parameters.

Method Detail

getWeights

public double[] getWeights()

getNumClasses

public int getNumClasses()

setParameters

public void setParameters(SupportVectorMachine.Parameters p)

Sets the values of parameters that control the behavior of this learning algorithm.

Parameters:

p - The parameters.

getParameters

public Learner.Parameters getParameters()

Retrieves the parameters that are set in this learner.

Overrides:

getParameters in class Learner

Returns:

An object containing all the values of the parameters that control the behavior of this learning algorithm.

setLabeler

public void setLabeler(Classifier l)

Sets the labels list.

Overrides:

setLabeler in class Learner

Parameters:

l - A new label producing classifier.

allowableValues

public String[] allowableValues()

Returns the array of allowable values that a feature returned by this classifier may take.

Overrides:

allowableValues in class Classifier

Returns:

The allowable values of this learner's labeler, or an array of length zero if the labeler has not yet been established or does not specify allowable values.

initialize

public void initialize(int ne,
                       int nf)

Initializes the example vector arrays.

Overrides:

initialize in class Learner

Parameters:

ne - The number of examples to train.

nf - The number of features.

learn

public void learn(int[] exampleFeatures,
                  double[] exampleValues,
                  int[] exampleLabels,
                  double[] labelValues)

This method adds the example's features and labels to the arrays storing the training examples. These examples will eventually be passed to liblinear.Linear.train() for training.

Note that learning via the liblinear library does not actually take place until doneLearning() is called.

Specified by:

learn in class Learner

Parameters:

exampleFeatures - The example's array of feature indices.

exampleValues - The example's array of feature values.

exampleLabels - The example's array of label indices.

labelValues - The example's array of label values.

doneLearning

public void doneLearning()

This method converts the arrays of examples stored in this class into input for the liblinear training method. The learned weight vector is stored in weights.

Overrides:

doneLearning in class Learner

write

public void write(PrintStream out)

Writes the algorithm's internal representation as text. In the first line of output, the name of the classifier is printed, followed by C, epsilon, bias, and finally solverType.

Specified by:

write in class Learner

Parameters:

out - The output stream.

write

public void write(edu.illinois.cs.cogcomp.core.datastructures.vectors.ExceptionlessOutputStream out)

Writes the learned function's internal representation in binary form.

Overrides:

write in class Learner

Parameters:

out - The output stream.

read

public void read(edu.illinois.cs.cogcomp.core.datastructures.vectors.ExceptionlessInputStream in)

Reads the binary representation of a learner with this object's run-time type, overwriting any and all learned or manually specified parameters as well as the label lexicon but without modifying the feature lexicon.

Overrides:

read in class Learner

Parameters:

in - The input stream.

featureValue

public Feature featureValue(int[] f,
                            double[] v)

Returns the classification of the given example as a single feature instead of a FeatureVector.

Overrides:

featureValue in class Learner

Parameters:

f - The features array.

v - The values array.

Returns:

The classification of the example as a feature.

discreteValue

public String discreteValue(int[] exampleFeatures,
                            double[] exampleValues)

The evaluate method returns the class label which yields the highest score for this example.

Overrides:

discreteValue in class Learner

Parameters:

exampleFeatures - The example's array of feature indices

exampleValues - The example's array of feature values

Returns:

The computed feature (in a vector).

classify

public FeatureVector classify(int[] exampleFeatures,
                              double[] exampleValues)

Evaluates the given example using liblinear's prediction method. Returns a DiscretePrimitiveStringFeature set to the label value.

Specified by:

classify in class Learner

Parameters:

exampleFeatures - The example's array of feature indices

exampleValues - The example's array of feature values

Returns:

A vector of Features about the input object.

scores

public ScoreSet scores(int[] exampleFeatures,
                       double[] exampleValues)

An SVM returns a classification score for each class. The score for each class is the result of score(int[],double[],int).

Specified by:

scores in class Learner

Parameters:

exampleFeatures - The example's array of feature indices

exampleValues - The example's array of feature values

Returns:

The set of scores as described above.

score

public double score(Object example)

Computes the dot product of the specified example vector and the weight vector associated with the supplied class. If no label is specified, it defaults to a label of 0 (that is, a positive example), but this should only be done in binary classification.

Parameters:

example - The example object.

Returns:

The score for the given example vector.

score

public double score(Object example,
                    int label)

Computes the dot product of the specified example vector and the weight vector associated with the supplied class.

Parameters:

example - The example object.

label - The class label

Returns:

The score for the given example vector.

score

public double score(int[] exampleFeatures,
                    double[] exampleValues,
                    int label)

Computes the dot product of the specified feature vector and the weight vector associated with the supplied class.

Parameters:

exampleFeatures - The example's array of feature indices

exampleValues - The example's array of feature values

label - The class label

Returns:

The score for the given example vector.

valueOf

public Feature valueOf(Object example,
                       Collection candidates)

Using this method, the winner-take-all competition is narrowed to involve only those labels contained in the specified list. The list must contain only ByteStrings.

Parameters:

example - The example object.

candidates - A list of the only labels the example may take.

Returns:

The prediction as a feature or null if the network did not contain any of the specified labels.

valueOf

public Feature valueOf(int[] exampleFeatures,
                       double[] exampleValues,
                       Collection candidates)

Using this method, the winner-take-all competition is narrowed to involve only those labels contained in the specified list. The list must contain only Strings.

Parameters:

exampleFeatures - The example's array of feature indices.

exampleValues - The example's array of feature values.

candidates - A list of the only labels the example may take.

Returns:

The prediction as a feature or null if the network did not contain any of the specified labels.

conjunctiveValueOf

protected Feature conjunctiveValueOf(int[] exampleFeatures,
                                     double[] exampleValues,
                                     Iterator I)

This method is a surrogate for valueOf(int[],double[],Collection) when the labeler is known to produce conjunctive features. It is necessary because when given a string label from the collection, we will not know how to construct the appropriate conjunctive feature key for lookup in the label lexicon. So, we must go through each feature in the label lexicon and use Feature.valueEquals(String).

Parameters:

exampleFeatures - The example's array of feature indices.

exampleValues - The example's array of feature values.

I - An iterator over the set of labels to choose from.

Returns:

The label chosen by this classifier or null if the network did not contain any of the specified labels.

forget

public void forget()

Resets the internal bookkeeping.

Overrides:

forget in class Learner