pystruct.learners.NSlackSSVM¶

class pystruct.learners.NSlackSSVM(model, max_iter=100, C=1.0, check_constraints=True, verbose=0, negativity_constraint=None, n_jobs=1, break_on_bad=False, show_loss_every=0, batch_size=100, tol=0.001, inactive_threshold=1e-05, inactive_window=50, logger=None, switch_to=None)[source]¶

Structured SVM solver for the n-slack QP with l1 slack penalty.

Implements margin rescaled structural SVM using the n-slack formulation and cutting plane method, solved using CVXOPT. The optimization is restarted in each iteration.

Parameters:

Parameters:	model : StructuredModel Object containing the model structure. Has to implement loss, inference and loss_augmented_inference. max_iter : int Maximum number of passes over dataset to find constraints. C : float Regularization parameter check_constraints : bool (default=True) Whether to check if the new “most violated constraint” is more violated than previous constraints. Helpful for stopping and debugging, but costly. verbose : int (default=0) Verbosity. negativity_constraint: list of ints : Indices of parmeters that are constraint to be negative. This is useful for learning submodular CRFs (inference is formulated as maximization in SSVMs, flipping some signs). break_on_bad: bool (default=False) : Whether to break (start debug mode) when inference was approximate. n_jobs : int, default=1 Number of parallel jobs for inference. -1 means as many as cpus. show_loss_every : int, default=0 Controlls how often the hamming loss is computed (for monitoring purposes). Zero means never, otherwise it will be computed very show_loss_every’th epoch. batch_size : int, default=100 Number of constraints after which we solve the QP again. batch_size=-1 means that an update is performed only after going once over the whole training set. tol : float, default=-10 Convergence tolerance. If dual objective decreases less than tol, learning is stopped. The default corresponds to ignoring the behavior of the dual objective and stop only if no more constraints can be found. inactive_threshold : float, default=1e-5 Threshold for dual variable of a constraint to be considered inactive. inactive_window : float, default=50 Window for measuring inactivity. If a constraint is inactive for `inactive_window` iterations, it will be pruned from the QP. If set to 0, no constraints will be removed. switch_to : None or string, default=None Switch to the given inference method if the previous method does not find any more constraints. logger : logger object, default=None Pystruct logger for storing the model or extracting additional information.
Attributes:	w : nd-array, shape=(model.size_joint_feature,) The learned weights of the SVM. old_solution : dict The last solution found by the qp solver. ``loss_curve_`` : list of float List of loss values if show_loss_every > 0. ``objective_curve_`` : list of float Cutting plane objective after each pass through the dataset. ``primal_objective_curve_`` : list of float Primal objective after each pass through the dataset. ``timestamps_`` : list of int Total training time stored before each iteration.

model : StructuredModel

Object containing the model structure. Has to implement loss, inference and loss_augmented_inference.

max_iter : int

Maximum number of passes over dataset to find constraints.

C : float

Regularization parameter

check_constraints : bool (default=True)

Whether to check if the new “most violated constraint” is more violated than previous constraints. Helpful for stopping and debugging, but costly.

verbose : int (default=0)

Verbosity.

negativity_constraint: list of ints :

Indices of parmeters that are constraint to be negative. This is useful for learning submodular CRFs (inference is formulated as maximization in SSVMs, flipping some signs).

break_on_bad: bool (default=False) :

Whether to break (start debug mode) when inference was approximate.

n_jobs : int, default=1

Number of parallel jobs for inference. -1 means as many as cpus.

show_loss_every : int, default=0

Controlls how often the hamming loss is computed (for monitoring purposes). Zero means never, otherwise it will be computed very show_loss_every’th epoch.

batch_size : int, default=100

Number of constraints after which we solve the QP again. batch_size=-1 means that an update is performed only after going once over the whole training set.

tol : float, default=-10

Convergence tolerance. If dual objective decreases less than tol, learning is stopped. The default corresponds to ignoring the behavior of the dual objective and stop only if no more constraints can be found.

inactive_threshold : float, default=1e-5

Threshold for dual variable of a constraint to be considered inactive.

inactive_window : float, default=50

Window for measuring inactivity. If a constraint is inactive for inactive_window iterations, it will be pruned from the QP. If set to 0, no constraints will be removed.

switch_to : None or string, default=None

Switch to the given inference method if the previous method does not find any more constraints.

logger : logger object, default=None

Pystruct logger for storing the model or extracting additional information.

Attributes:

w : nd-array, shape=(model.size_joint_feature,)

The learned weights of the SVM.

old_solution : dict

The last solution found by the qp solver.

``loss_curve_`` : list of float

List of loss values if show_loss_every > 0.

``objective_curve_`` : list of float

Cutting plane objective after each pass through the dataset.

``primal_objective_curve_`` : list of float

Primal objective after each pass through the dataset.

``timestamps_`` : list of int

Total training time stored before each iteration.

References

Tsochantaridis, Ioannis and Joachims, Thorsten and Hofmann, Thomas and

Altun, Yasemin and Singer, Yoram: Large margin methods for structured and interdependent output variables, JMLR 2006
Joachims, Thorsten and Finley, Thomas and Yu, Chun-Nam John:

Cutting-plane training of structural SVMs, JMLR 2009

Methods

`fit`(X, Y[, constraints, warm_start, initialize])	Learn parameters using cutting plane method.
`get_params`([deep])	Get parameters for this estimator.
`predict`(X)	Predict output on examples in X.
`prune_constraints`(constraints, a)
`score`(X, Y)	Compute score as 1 - loss over whole data set.
`set_params`(**params)	Set the parameters of this estimator.

__init__(model, max_iter=100, C=1.0, check_constraints=True, verbose=0, negativity_constraint=None, n_jobs=1, break_on_bad=False, show_loss_every=0, batch_size=100, tol=0.001, inactive_threshold=1e-05, inactive_window=50, logger=None, switch_to=None)[source]¶

fit(X, Y, constraints=None, warm_start=None, initialize=True)[source]¶

Learn parameters using cutting plane method.

Parameters:

Parameters:	X : iterable Traing instances. Contains the structured input objects. No requirement on the particular form of entries of X is made. Y : iterable Training labels. Contains the strctured labels for inputs in X. Needs to have the same length as X. contraints : iterable Known constraints for warm-starts. List of same length as X. Each entry is itself a list of constraints for a given instance x . Each constraint is of the form [y_hat, delta_joint_feature, loss], where y_hat is a labeling, `delta_joint_feature = joint_feature(x, y) - joint_feature(x, y_hat)` and loss is the loss for predicting y_hat instead of the true label y. initialize : boolean, default=True Whether to initialize the model for the data. Leave this true except if you really know what you are doing.

X : iterable

Traing instances. Contains the structured input objects. No requirement on the particular form of entries of X is made.

Y : iterable

Training labels. Contains the strctured labels for inputs in X. Needs to have the same length as X.

contraints : iterable

Known constraints for warm-starts. List of same length as X. Each entry is itself a list of constraints for a given instance x . Each constraint is of the form [y_hat, delta_joint_feature, loss], where y_hat is a labeling, delta_joint_feature = joint_feature(x, y) - joint_feature(x, y_hat) and loss is the loss for predicting y_hat instead of the true label y.

initialize : boolean, default=True

Whether to initialize the model for the data. Leave this true except if you really know what you are doing.

get_params(deep=True)¶

Get parameters for this estimator.

Parameters:

Parameters:	deep: boolean, optional : If True, will return the parameters for this estimator and contained subobjects that are estimators.
Returns:	params : mapping of string to any Parameter names mapped to their values.

deep: boolean, optional :

If True, will return the parameters for this estimator and contained subobjects that are estimators.

Returns:

params : mapping of string to any

Parameter names mapped to their values.

predict(X)¶

Predict output on examples in X.

Parameters:

Parameters:	X : iterable Traing instances. Contains the structured input objects.
Returns:	Y_pred : list List of inference results for X using the learned parameters.

X : iterable

Traing instances. Contains the structured input objects.

Returns:

Y_pred : list

List of inference results for X using the learned parameters.

score(X, Y)¶

Compute score as 1 - loss over whole data set.

Returns the average accuracy (in terms of model.loss) over X and Y.

Parameters:

Parameters:	X : iterable Evaluation data. Y : iterable True labels.
Returns:	score : float Average of 1 - loss over training examples.

X : iterable

Evaluation data.

Y : iterable

True labels.

Returns:

score : float

Average of 1 - loss over training examples.

set_params(**params)¶

Set the parameters of this estimator.

The method works on simple estimators as well as on nested objects (such as pipelines). The former have parameters of the form <component>__<parameter> so that it’s possible to update each component of a nested object.

Returns:	self :