## SVM
^{struct} ## Support Vector Machine for Complex OutputsAuthor: Thorsten Joachims <thorsten@joachims.org> Version: 2.00 |

*SVM ^{struct}* is a Support Vector Machine (SVM) algorithm for predicting multivariate outputs. Unlike regular SVMs, which consider only univariate predictions like in classification and regression,

The sparse approximation algorithm implemented in *SVM ^{struct}* is described in [1][2]. The implementation is based on the

*SVM ^{struct}* can be thought of as an API for implementing different kinds of complex prediction algorithms. Currently, we have implemented the following learning tasks:

: Learning to align sequences. Given examples of how sequence pairs align, the goal is to learn the substitution matrix as well as the insertion and deletion costs of operations so that one can predict alignments of new sequences.*SVM*^{align}

More information and source code.: Learns a weighted context free grammar from examples. Training examples (e.g. for natural language parsing) specify the sentence along with the correct parse tree. The goal is to predict the parse tree of new sentences.*SVM*^{pcfg}

More information and source code coming soon.: Learns a Markov model from examples. Training examples (e.g. for part-of-speech tagging) specify the sequence of words along with the correct assignment of tags (i.e. states). The goal is to predict the tag sequences for new sentences.*SVM*^{hmm}

More information and source code coming soon.

- A function for computing the feature vector Psi.
- A function for computing the argmax of the linear discriminant function.
- A loss function.

http://kodiak.cs.cornell.edu/svm_struct/current/svm_struct.tar.gzThe archive contains the source code of the most recent version of

gunzip –c svm_struct.tar.gz | tar xvf –This expands the archive into the current directory, which now contains all relevant files. You can compile

makeIt will output some warnings, since the functions of the API are only templates and do not return values as required. However, it should produce the executable

`svm_struct_api.c``svm_struct_api_types.h`

svm_struct_learn -c 1.0 train.dat model.datwhich trains and SVM on the training set

General options: -? -> this help -v [0..3] -> verbosity level (default 1) -y [0..3] -> verbosity level for svm_light (default 0) Learning options: -c float -> C: trade-off between training error and margin (default 0.01) -d [1,2] -> L-norm to use for slack variables. Use 1 for L1-norm, use 2 for squared slacks. (default 1) -r [0..] -> Slack rescaling method to use for loss. 1: slack rescaling 2: margin rescaling (default 1) -l [0..] -> Loss function to use. 0: zero/one loss (default 0) Optimization options (see [1]): -q [2..] -> maximum size of QP-subproblems (default 10) -n [2..q] -> number of new variables entering the working set in each iteration (default n = q). Set nThe options starting witheps: Allow that error for termination criterion (default 0.01) -h [5..] -> number of iterations a variable needs to be optimal before considered for shrinking (default 100) Output options: -a string -> write all alphas to this file after learning (in the same order as in the training set) Structure learning options: -u* string -> custom parameters that can be adapted for struct learning. The * can be replaced by any character and there can be multiple options starting with -u.

**[1]** I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support Vector Learning for Interdependent and Structured Output Spaces, ICML, 2004.

**[2]** T. Joachims. Learning to Align Sequences: A Maximum Margin Approach, Technical Report, August, 2003.

**[3]** T. Joachims, Making Large-Scale SVM Learning Practical. Advances in Kernel Methods - Support Vector Learning, B. Schölkopf and C. Burges and A. Smola (ed.), MIT Press, 1999.