edu.illinois.cs.cogcomp.lbjava.learn

Class SparseMIRA

java.lang.Object

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

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

edu.illinois.cs.cogcomp.lbjava.learn.SparseMIRA

All Implemented Interfaces:

Serializable, Cloneable

public class SparseMIRA
extends Learner

An implementation of the Margin Infused Relaxed Algorithm of Crammer and Singer. This is a multi-class, online learner that maintains a separate weight vector for every prediction class, just as SparseNetworkLearner does. However, updates to these weight vectors given an example vector x with label y are dependent on each other as follows. For each weight vector w_v corresponding to a prediction value v, a multiplier t_v is selected and used to update w_v as w_v += t_v x. t_v must be less than or equal to zero for all v != y. t_y must be less than or equal to one. MIRA selects these multipliers so that they sum to 0 and so that the vector norm of all updated weight vectors concatenated is as small as possible.

In this sparse implementation of the algorithm, weight vectors corresponding to labels and weights for features within those vectors are added as they are observed in the data. Whenever a feature is observed for the first time, its corresponding weight in any given weight vector is set to a random number, which is necessary to make this algorithm work. It must never be the case that all weight vectors are equal to each other, or updates will stop happening. To ensure that results are reproducible, the random number generator is seeded with the same seed every time.

In addition to the observed features, each weight vector also contains a bias. For this reason, we also halucinate an extra dimension on every example vector containing a feature whose strength is 1.

It is assumed that a single discrete label feature will be produced in association with each example object. A feature taking one of the values observed in that label feature will be produced by the learned classifier.

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:

Nick Rizzolo

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SparseMIRA.Parameters Simply a container for all of SparseMIRA's configurable parameters.

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	conjunctiveLabels Whether or not this learner's labeler produces conjunctive features.
protected edu.illinois.cs.cogcomp.core.datastructures.vectors.OVector	network A map from labels to the weight vector corresponding to that label.
static double	TOLERANCE Used to decide if two values are nearly equal to each other.

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
SparseMIRA() This algorithm has no parameters to set!
SparseMIRA(SparseMIRA.Parameters p) Initializing constructor.
SparseMIRA(String n) This algorithm has no parameters to set!
SparseMIRA(String n, SparseMIRA.Parameters p) Initializing constructor.

Method Summary

Modifier and Type	Method and Description
FeatureVector	classify(int[] exampleFeatures, double[] exampleValues) This implementation uses a winner-take-all comparison of the individual weight vectors' dot products.
Object	clone() Returns a deep clone of this learning algorithm.
protected ScoreSet	conjunctiveScores(int[] exampleFeatures, double[] exampleValues, Iterator I) This method is a surrogate for scores(int[],double[],Collection) when the labeler is known to produce conjunctive features.
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) This implementation uses a winner-take-all comparison of the individual weight vectors' dot products.
Feature	featureValue(int[] f, double[] v) Returns the classification of the given example as a single feature instead of a FeatureVector.
void	forget() Clears the network.
Learner.Parameters	getParameters() Retrieves the parameters that are set in this learner.
void	learn(int[] exampleFeatures, double[] exampleValues, int[] exampleLabels, double[] labelValues) Finds the optimal multiplier settings before updating the weight vectors.
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.
ScoreSet	scores(int[] exampleFeatures, double[] exampleValues) Produces a set of scores indicating the degree to which each possible discrete classification value is associated with the given example object.
ScoreSet	scores(int[] exampleFeatures, double[] exampleValues, Collection candidates) Returns scores for only those labels in the given collection.
ScoreSet	scores(Object example, Collection candidates) Returns scores for only those labels in the given collection.
void	setLabeler(Classifier l) Sets the labeler.
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, countFeatures, createPrediction, createPrediction, demandLexicon, discreteValue, discreteValue, doneLearning, doneWithRound, emptyClone, featureValue, featureValue, getCurrentLexicon, getExampleArray, getExampleArray, getExtractor, getLabeler, getLabelLexicon, getLexicon, getLexiconDiscardCounts, getLexiconLocation, getModelLocation, getPrunedLexiconSize, initialize, 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

allowableValues, 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

TOLERANCE

public static final double TOLERANCE

Used to decide if two values are nearly equal to each other.

See Also:

nearlyEqualTo(double,double), Constant Field Values

network

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

A map from labels to the weight vector corresponding to that label.

conjunctiveLabels

protected boolean conjunctiveLabels

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

Constructor Detail

SparseMIRA

public SparseMIRA()

This algorithm has no parameters to set!

SparseMIRA

public SparseMIRA(SparseMIRA.Parameters p)

Initializing constructor. This constructor appears here for completeness; the algorithm takes no parameters.

Parameters:

p - The settings of all parameters.

SparseMIRA

public SparseMIRA(String n)

This algorithm has no parameters to set!

Parameters:

n - The name of the classifier.

SparseMIRA

public SparseMIRA(String n,
                  SparseMIRA.Parameters p)

Initializing constructor. This constructor appears here for completeness; the algorithm takes no parameters.

Parameters:

n - The name of the classifier.

p - The settings of all parameters.

Method Detail

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 labeler.

Overrides:

setLabeler in class Learner

Parameters:

l - A labeling classifier.

learn

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

Finds the optimal multiplier settings before updating the weight vectors.

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 label(s).

labelValues - The labels' values.

forget

public void forget()

Clears the network.

Overrides:

forget in class Learner

scores

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

Produces a set of scores indicating the degree to which each possible discrete classification value is associated with the given example object. These scores are just the dot product of each weight vector with the example vector.

Specified by:

scores in class Learner

Parameters:

exampleFeatures - The example's array of feature indices.

exampleValues - The example's array of feature values.

Returns:

A set of scores indicating the degree to which each possible discrete classification value is associated with the given example object.

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)

This implementation uses a winner-take-all comparison of the individual weight vectors' dot products.

Overrides:

discreteValue in class Learner

Parameters:

exampleFeatures - The example's array of feature indices.

exampleValues - The example's array of feature values.

Returns:

The discrete value of the best prediction.

classify

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

This implementation uses a winner-take-all comparison of the individual weight vectors' dot products.

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 single feature with the winning weight vector's associated value.

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 Strings.

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 prediction as a feature or null if the network did not contain any of the specified labels.

scores

public ScoreSet scores(Object example,
                       Collection candidates)

Returns scores for only those labels in the given collection. If the given collection is empty, scores for all labels will be returned. If there is no BiasedRandomWeightVector associated with a given label from the collection, that label's score in the returned ScoreSet will be set to Double.NEGATIVE_INFINITY.

The elements of candidates must all be Strings.

Parameters:

example - The example object.

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

Returns:

Scores for only those labels in candidates.

scores

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

Returns scores for only those labels in the given collection. If the given collection is empty, scores for all labels will be returned. If there is no BiasedRandomWeightVector associated with a given label from the collection, that label's score in the returned ScoreSet will be set to Double.NEGATIVE_INFINITY.

The elements of candidates must all be 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:

Scores for only those labels in candidates.

conjunctiveScores

protected ScoreSet conjunctiveScores(int[] exampleFeatures,
                                     double[] exampleValues,
                                     Iterator I)

This method is a surrogate for scores(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.

write

public void write(PrintStream out)

Writes the algorithm's internal representation as text.

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.

clone

public Object clone()

Returns a deep clone of this learning algorithm.

Overrides:

clone in class Learner

Returns:

A shallow clone.