Support vector machine learning for interdependent and structured output spaces

Ioannis TsochantaridisThomas HofmannThorsten JoachimsYasemin Altun

article2004ICML1,489 citations

Presents a maximum-margin framework that extends Support Vector Machines to complex, structured prediction tasks and solves the resulting exponential-sized optimization problem via an efficient cutting-plane algorithm.

Listen

Many complex machine learning applications require predicting outputs that have rich internal structures, such as trees, sequences, or taxonomies, rather than simple individual categories. Traditional classification methods either struggle with the vast combinatorial number of possible output structures or fail to account for domain-specific error costs, such as penalizing partially correct trees less severely than completely incorrect ones.

The article develops and evaluates a generalized maximum-margin framework—specifically extending Support Vector Machines—designed to learn mappings to structured and interdependent output spaces while directly optimizing for arbitrary, task-specific loss functions.

The researchers formulated a learning objective based on joint input-output feature representations and introduced an efficient cutting-plane optimization algorithm that iteratively selects the most violated constraints. The method was evaluated across four diverse benchmark domains: hierarchical patent classification using a taxonomy of 160 groups, named entity recognition on Spanish news text, synthetic biological sequence alignment, and natural language grammar parsing on the Penn Treebank corpus.

The findings demonstrate strong empirical and theoretical advantages. First, the cutting-plane optimization scales efficiently, maintaining a small active set of constraints (often only one to two times the training set size) and guaranteeing convergence in polynomial time independent of the exponential size of the output space. Second, in hierarchical text classification, incorporating taxonomy structure and tree-based loss reduced loss by approximately 12% to 14% and improved accuracy by 5% to 8% over standard flat multi-class models. Third, in natural language parsing, tailoring the model to the target F1 evaluation metric increased the test F1 score to roughly 88.5%, significantly outperforming the standard generative probabilistic grammar baseline of 86.0%. Fourth, in sequence labeling and alignment tasks, the structured maximum-margin approach matched or outperformed traditional generative models and competing discriminative techniques like conditional random fields, especially in low-data regimes where the alignment error was reduced by about 35% to 50%.

These results show that organizations can deploy high-performing predictive models for complex, structured data without incurring prohibitive computational bottlenecks. By allowing arbitrary feature engineering and direct optimization of business-critical evaluation metrics, the framework reduces the performance risks and inflexibility associated with traditional generative statistical models.

Teams working on structured prediction tasks should consider adopting this large-margin framework within their machine learning pipelines, particularly when existing solutions are restricted by standard zero-one error metrics. Prior to full-scale deployment, engineering teams must implement efficient problem-specific decoding subroutines (such as dynamic programming parsers or sequence decoders), which represent the primary computational bottleneck during training.

While the theoretical convergence guarantees and empirical results provide high confidence in the framework's core optimization, the evaluation relies partly on synthetic benchmarks and constrained sentence lengths in parsing. Organizations should validate end-to-end performance and decoding speeds on their specific production datasets before broad rollout.

Brown University Cornell University functional dependency optimization optimization problems structured output spaces support vector machine learning kernel dependency estimation

Tsochantaridis et al (2004).pdf

Paper: Max-Margin Markov Networks, Ben Taskar et al. (2003). Introduces max-margin Markov networks combining maximum-margin estimation with structured graphical models, establishing the foundational paradigm for max-margin structured prediction.
Paper: On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines, Koby Crammer et al. (2002). Formulates direct multiclass support vector machines using joint input-class score functions that serve as the direct precursor to structured output margin formulations.
Paper: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, John D. Lafferty et al. (2001). Pioneers conditional random fields for sequence and structured labeling, providing the dominant probabilistic counterpart and structured representation framework that margin-based structured prediction aims to generalize.
Paper: A kernel method for multi-labelled classification, A. Elisseeff et al. (2001). Establishes large-margin ranking and multi-label classification formulations that motivate generalized loss functions over interdependent output representations.
Paper: Support-vector networks, Corinna Cortes et al. (1995). Develops the foundational soft-margin support vector machine optimization and dual formulation upon which large-margin structured learning is constructed.
Paper: Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers, Erin L. Allwein et al. (2000). Provides the theoretical foundation for margin-based multi-class and structured output decompositions using loss-based decoding.
Paper: Shallow Parsing with Conditional Random Fields, Fei Sha et al. (2003). Applies discriminative structured modeling to natural language shallow parsing, illustrating the exact sequence extraction problems targeted by structured SVMs.

Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). Expands the conference paper into a comprehensive journal-length framework with complete theoretical convergence proofs, margin rescaling analysis, and expanded empirical benchmarks for structured SVMs.
Paper: Training linear SVMs in linear time, Thorsten Joachims (2006). Adapts the cutting-plane optimization algorithm introduced for structured SVMs into SVM-Perf to enable linear-time training for large-scale linear classification and ranking.
Paper: Classifier chains for multi-label classification, Jesse Read et al. (2009). Presents classifier chains as an alternative, lightweight problem-transformation method to capture output label interdependencies without requiring full joint feature map optimization.
Paper: A Review on Multi-Label Learning Algorithms, Min-Ling Zhang et al. (2014). Surveys the broader landscape of multi-label and structured learning algorithms, positioning margin-based structured methods among modern algorithm-adaptation techniques.

Cover for Support vector machine learning for interdependent and structured output spaces

Abstract

Learning general functional dependencies is one of the main goals in machine learning. Recent progress in kernel-based methods has focused on designing flexible and powerful input representations. This paper addresses the complementary issue of problems involving complex outputs such as multiple dependent output variables and structured output spaces. We propose to generalize multiclass Support Vector Machine learning in a formulation that involves features extracted jointly from inputs and outputs. The resulting optimization problem is solved efficiently by a cutting plane algorithm that exploits the sparseness and structural decomposition of the problem. We demonstrate the versatility and effectiveness of our method on problems ranging from supervised grammar learning and named-entity recognition, to taxonomic text classification and sequence alignment.

Topics

functional dependency optimization optimization problems ranging support vector text classification named entity recognition kernel based methods svm syntactic structure

Keywords

structured output spaces support vector machine learning kernel dependency estimation label sequence learning multiclass classification generative PCFG margin maximization Penn Treebank grammar learning

1. Introduction
2. Discriminants and Loss Functions
3. Margins and Margin Maximization
4. Support Vector Machine Learning
4.1. Dual Programs
4.2. Algorithm
4.3. Analysis
5. Applications and Experiments
5.1. Multiclass Classification
5.2. Classification with Taxonomies
5.3. Label Sequence Learning
5.4. Sequence Alignment
5.5. Natural Language Parsing
6. Conclusions
Acknowledgments
References

Knowls

Knowl 1 — Joint Feature Representation and Linear Discriminant for Structured Prediction
model/method
To predict structured discrete outputs $y \in \mathcal{Y}$ (such as sequences, trees, or graphs) from inputs $x \in \mathcal{X}$ , hypotheses $f: \mathcal{X} \to \mathcal{Y}$ are defined via a linear discriminant function parameterized by a weight vector $w \in \mathbb{R}^N$ :

$f(x; w) = \operatorname{argmax}_{y \in \mathcal{Y}} \langle w, \Psi(x, y) \rangle$

where $\Psi: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}^N$ is a joint feature mapping extracting features from input-output pairs.

Given a training sample $S = \{(x_1, y_1), \dots, (x_n, y_n)\} \subset \mathcal{X} \times \mathcal{Y}$ , zero training error under any non-trivial loss function corresponds to the condition:

$\forall i \in \{1, \dots, n\}, \, \forall y \in \mathcal{Y} \setminus \{y_i\}: \langle w, \delta\Psi_i(y) \rangle > 0$

where $\delta\Psi_i(y) \equiv \Psi(x_i, y_i) - \Psi(x_i, y)$ . In the separable case, the hard-margin optimization problem (denoted $\text{SVM}_0$ ) identifies the unique maximum-margin vector $w$ by solving:

$\min_w \frac{1}{2} \|w\|^2 \quad \text{subject to} \quad \forall i \in \{1, \dots, n\}, \, \forall y \in \mathcal{Y} \setminus \{y_i\}: \langle w, \delta\Psi_i(y) \rangle \ge 1$
Knowl 2 — Soft-Margin Structured SVM Formulations with Loss Re-scaling
model/method
Let $\Delta: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$ be a bounded task-specific loss function measuring the discrepancy between a true output $y_i$ and a predicted output $y$ , satisfying $\Delta(y_i, y_i) = 0$ and $\Delta(y_i, y) > 0$ for $y \neq y_i$ . Given training examples $(x_1, y_1), \dots, (x_n, y_n)$ , a trade-off parameter $C > 0$ , and difference vectors $\delta\Psi_i(y) = \Psi(x_i, y_i) - \Psi(x_i, y)$ , task loss $\Delta$ is integrated into structured Support Vector Machines through two primary soft-margin mechanisms:
1. Slack Re-scaling with $L_1$ penalty (denoted $\text{SVM}_1^{\Delta s}$ ):
$\min_{w, \xi} \frac{1}{2} \|w\|^2 + \frac{C}{n} \sum_{i=1}^n \xi_i \quad \text{s.t.} \quad \forall i, \, \xi_i \ge 0, \quad \forall i, \, \forall y \in \mathcal{Y} \setminus \{y_i\}: \langle w, \delta\Psi_i(y) \rangle \ge 1 - \frac{\xi_i}{\Delta(y_i, y)}$

For the quadratic penalty formulation ( $\text{SVM}_2^{\Delta s}$ ), the objective uses $\frac{C}{2n} \sum_{i=1}^n \xi_i^2$ , and the constraint denominator is replaced by $\sqrt{\Delta(y_i, y)}$ .
1. Margin Re-scaling with $L_1$ penalty (denoted $\text{SVM}_1^{\Delta m}$ ):
$\min_{w, \xi} \frac{1}{2} \|w\|^2 + \frac{C}{n} \sum_{i=1}^n \xi_i \quad \text{s.t.} \quad \forall i, \, \xi_i \ge 0, \quad \forall i, \, \forall y \in \mathcal{Y} \setminus \{y_i\}: \langle w, \delta\Psi_i(y) \rangle \ge \Delta(y_i, y) - \xi_i$

For the quadratic penalty variant ( $\text{SVM}_2^{\Delta m}$ ), the slack penalty in the objective is $\frac{C}{2n} \sum_{i=1}^n \xi_i^2$ , and the margin requirement is $\sqrt{\Delta(y_i, y)} - \xi_i$ .
Knowl 3 — Cutting Plane Algorithm for Structured SVM Dual Optimization
algorithm
Because the number of linear margin constraints $n(|\mathcal{Y}| - 1)$ can be exponentially large or infinite, structured SVM optimization is carried out via a cutting plane algorithm in the Wolfe dual. The algorithm iteratively constructs a polynomial-sized working set $S = \bigcup_{i=1}^n S_i$ of active constraints.
Input: Training sample $(x_1, y_1), \dots, (x_n, y_n)$ , parameter $C > 0$ , precision tolerance $\epsilon > 0$
Output: Working sets $S_i$ and optimal dual variables $\alpha$
for $i = 1$ to $n$ do
     $S_i \leftarrow \emptyset$
end for
repeat
    for $i = 1$ to $n$ do
        Define score function $H(y)$ for model variants:
            For SVM1-slack: $H(y) \equiv (1 - \langle \delta\Psi_i(y), w \rangle) \Delta(y_i, y)$
            For SVM2-slack: $H(y) \equiv (1 - \langle \delta\Psi_i(y), w \rangle) \sqrt{\Delta(y_i, y)}$
            For SVM1-margin: $H(y) \equiv \Delta(y_i, y) - \langle \delta\Psi_i(y), w \rangle$
            For SVM2-margin: $H(y) \equiv \sqrt{\Delta(y_i, y)} - \langle \delta\Psi_i(y), w \rangle$
            where $w \equiv \sum_{j=1}^n \sum_{y' \in S_j} \alpha_{j y'} \delta\Psi_j(y')$
        Find most violated constraint: $\hat{y} \leftarrow \operatorname{argmax}_{y \in \mathcal{Y}} H(y)$
        Compute current slack: $\xi_i \leftarrow \max\{0, \max_{y \in S_i} H(y)\}$
        if $H(\hat{y}) > \xi_i + \epsilon$ then
             $S_i \leftarrow S_i \cup \{\hat{y}\}$
             $\alpha_S \leftarrow \text{solve dual quadratic program over working set } S = \bigcup_{j=1}^n S_j$
        end if
    end for
until no working set $S_i$ has changed during the iteration
Dual optimization utilizes inner products $\langle \delta\Psi_i(y), \delta\Psi_j(\bar{y}) \rangle$ which can be expressed in terms of a joint kernel function $K((x, y), (x', y')) = \langle \Psi(x, y), \Psi(x', y') \rangle$ .
Knowl 4 — Polynomial Bound on Working Set Size and Convergence for Structured SVM
theoretical result
Let $\Delta_i = \max_{y \in \mathcal{Y}} \Delta(y_i, y)$ , $\bar{\Delta} = \max_{1 \le i \le n} \Delta_i$ , $R_i = \max_{y \in \mathcal{Y}} \|\Psi(x_i, y_i) - \Psi(x_i, y)\|$ , and $\bar{R} = \max_{1 \le i \le n} R_i$ .

For any target precision $\epsilon > 0$ , the cutting plane algorithm applied to the $L_2$ slack-rescaling structured SVM formulation ( $\text{SVM}_2^{\Delta s}$ ) terminates after adding at most

$\frac{C \bar{\Delta}^2 \bar{R}^2 + n \bar{\Delta}}{\epsilon^2}$

constraints across all working sets $S = \bigcup_{i=1}^n S_i$ .

Whenever a constraint violating the margin requirement by more than $\epsilon$ is added to $S_i$ , re-optimizing the dual quadratic program increases the dual objective value by at least:

$\frac{\epsilon^2}{2 \left( \Delta_i R_i^2 + \frac{n}{C} \right)}$

Because the maximum dual objective is bounded above by the optimal primal value (which is at most $\frac{1}{2} C \bar{\Delta}$ ), convergence occurs in a number of iterations that depends polynomially on $n$ , $\bar{R}$ , $\bar{\Delta}$ , and $1/\epsilon$ , and is entirely independent of the output space cardinality $|\mathcal{Y}|$ .
Knowl 5 — Upper Bound on Empirical Risk for Slack Re-scaled Structured SVMs
theoretical result
Let $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$ be a training set of input-output pairs drawn from distribution $P(x, y)$ , and let $\Delta: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$ be a bounded loss function. The empirical risk associated with hypothesis $f(x; w) = \operatorname{argmax}_{y \in \mathcal{Y}} \langle w, \Psi(x, y) \rangle$ is defined as:

$R_S^\Delta(w) = \frac{1}{n} \sum_{i=1}^n \Delta(y_i, f(x_i; w))$

If $(w^*, \xi^*)$ is the optimal solution to the $L_1$ slack-rescaled structured SVM problem ( $\text{SVM}_1^{\Delta s}$ ):

$\min_{w, \xi} \frac{1}{2} \|w\|^2 + \frac{C}{n} \sum_{i=1}^n \xi_i \quad \text{s.t.} \quad \forall i, \, \xi_i \ge 0, \quad \forall i, \, \forall y \in \mathcal{Y} \setminus \{y_i\}: \langle w, \Psi(x_i, y_i) - \Psi(x_i, y) \rangle \ge 1 - \frac{\xi_i}{\Delta(y_i, y)}$

then the average optimal slack provides an upper bound on the empirical risk:

$R_S^\Delta(w^*) \le \frac{1}{n} \sum_{i=1}^n \xi_i^*$
Knowl 6 — Structured SVM Formulation for Taxonomic Classification
model/method
In classification problems where categories $y \in \mathcal{Y}$ correspond to the leaves of a hierarchical taxonomy modeled as a lattice, structural relationships are incorporated through an output feature mapping $\Lambda(y)$ . For each node $z$ in the lattice (classes and super-classes), a binary indicator $\lambda_z(y) \in \{0, 1\}$ specifies whether $z$ is an ancestor of $y$ . The joint feature mapping is defined using the tensor product $\otimes$ :

$\Psi(x, y) = \Phi(x) \otimes \Lambda(y)$

where $\Phi(x) \in \mathbb{R}^D$ is the input document feature representation. The inner product $\langle \Lambda(y), \Lambda(y') \rangle$ counts the number of shared predecessor categories between labels $y$ and $y'$ .

The loss between class labels $y$ and $y'$ is defined by the tree-loss function $\Delta_{\text{tree}}(y, y')$ , which equals the height of the lowest common ancestor of $y$ and $y'$ in the taxonomy.
Knowl 7 — Structured SVM for Supervised Natural Language Parsing
model/method
In supervised natural language parsing, an input sentence $x$ is mapped to a valid parse tree $y \in \mathcal{Y}$ derived from a context-free grammar. The joint feature representation $\Psi(x, y) \in \mathbb{R}^M$ is a histogram vector where the $j$ -th element counts the occurrences of production rule $g_j$ in parse tree $y$ :

$\Psi_j(x, y) = \text{frequency of grammar rule } g_j \text{ in tree } y$

Given rule scores $w \in \mathbb{R}^M$ , the total score of tree $y$ is $F(x, y; w) = \langle w, \Psi(x, y) \rangle = \sum_j w_j \Psi_j(x, y)$ , isomorphic to a Probabilistic Context-Free Grammar (PCFG). Inference and separation oracles $\operatorname{argmax}_{y \in \mathcal{Y}} H(y)$ are computed using dynamic programming via the Cocke-Younger-Kasami (CKY) algorithm.

The parsing loss function between a reference tree $y_i$ and candidate tree $y$ is formulated from the constituent $F_1$ score (harmonic mean of precision and recall over tree nodes):

$\Delta_{F_1}(y_i, y) = 1 - F_1(y_i, y)$
Knowl 8 — Structured SVM for Inverse Sequence Alignment
model/method
Inverse sequence alignment learning aims to learn scoring parameters $w$ (substitution matrix $\Pi$ and insertion/deletion cost $\delta$ ) from training data consisting of a sequence $x_i$ , a known true homologue sequence $z_i$ with optimal alignment $a_i$ , and decoy sequences $z_i^t$ ( $t=1,\dots,k$ ) with unknown alignments.

For any sequence pair $(x, z)$ and alignment operation sequence $a$ , the feature map $\Psi(x, z, a)$ is the histogram of alignment operations. Optimal alignment decoding uses the Smith-Waterman dynamic programming algorithm:

$\hat{a}(x, z) = \operatorname{argmax}_{a \in \mathcal{A}} \langle w, \Psi(x, z, a) \rangle$

The structured SVM seeks a parameter vector $w$ satisfying the zero-one loss margin constraints $\langle w, \Psi(x_i, z_i, a_i) \rangle - \langle w, \Psi(x_i, z_i^t, a) \rangle \ge 1 - \xi_i$ for all decoy sequences and all alignment sequences $a$ , ensuring homologues receive higher similarity scores than non-homologous sequences.

Knowl 9 — Empirical Natural Language Parsing Performance on Penn Treebank

empirical result

Supervised weighted context-free grammar parsing was evaluated on the Penn Treebank Wall Street Journal corpus restricted to sentences of length $\le 10$ (4,098 training sentences from sections F2–21, 163 test sentences from section F22) with $C = 1$ and $\epsilon = 0.01$ .

Method	Train Acc (%)	Train $F_1$ (%)	Test Acc (%)	Test $F_1$ (%)	Constraints ( $\|S\|$ )	CPU Time (h) [% QP]
PCFG (MLE)	61.4	90.4	55.2	86.0	N/A	0
$\text{SVM}_2$ ( $0/1$ loss)	66.3	92.0	58.9	86.2	7494	1.2 (81.6%)
$\text{SVM}_2^{\Delta s}$ ( $F_1$ slack-rescaling)	62.2	92.1	58.9	88.5	8043	3.4 (10.5%)
$\text{SVM}_2^{\Delta m}$ ( $F_1$ margin-rescaling)	63.5	92.3	58.3	88.4	7117	3.5 (18.0%)

Optimizing structured SVMs directly for constituent $F_1$ -loss (both slack-rescaling $\text{SVM}_2^{\Delta s}$ and margin-rescaling $\text{SVM}_2^{\Delta m}$ ) yields a statistically significant improvement in test $F_1$ score ( $88.5\%$ and $88.4\%$ ) over generative maximum-likelihood PCFG ( $86.0\%$ ) and zero-one loss SVM ( $86.2\%$ ). In all configurations, the total number of cutting planes added to the working set $S$ was small, approximately twice the number of training sentences.

Knowl 10 — Empirical Taxonomic Classification Results on the WIPO Patent Dataset

empirical result

Hierarchical document classification was tested on Section D (160 groups, 1,710 documents) of the WIPO-alpha patent corpus under 3-fold and 5-fold cross-validation, comparing standard flat multiclass SVMs against taxonomic structured SVMs trained under zero-one loss ( $0/1$ ) and tree loss ( $\Delta_{\text{tree}}$ ).

Setup	Flat $0/1$	Taxonomic $0/1$	Flat $\Delta_{\text{tree}}$	Taxonomic $\Delta_{\text{tree}}$	Relative Improvement
4 instances/class
Accuracy (%)	28.32	28.32	27.47	29.74	$+5.01\%$
$\Delta$ -loss	1.36	1.32	1.30	1.21	$+12.40\%$
2 instances/class
Accuracy (%)	20.20	20.46	20.20	21.73	$+7.57\%$
$\Delta$ -loss	1.54	1.51	1.39	1.33	$+13.67\%$

Combining taxonomy-derived output features with tree-loss optimization ( $\text{tax } \Delta$ ) outperforms standard flat multiclass SVMs, yielding a $5.01\%$ and $7.57\%$ relative accuracy increase, and a $12.40\%$ and $13.67\%$ relative reduction in tree loss for 4 and 2 training examples per class, respectively.

Knowl 11 — Empirical Named Entity Recognition and Sequence Alignment Results
empirical result
On the CoNLL-2002 Spanish Named Entity Recognition dataset (300 sentences, 9 label types, second-degree polynomial kernel, $C=1, \epsilon=0.01$ ), the structured SVM achieved a test error rate of $5.08\%$ , outperforming Hidden Markov Models ( $9.36\%$ ), Collins' Perceptron ( $5.94\%$ ), and Conditional Random Fields ( $5.17\%$ ). Across structured SVM variants on NER, $\text{SVM}_2$ achieved $5.1 \pm 0.6\%$ test error ( $2824 \pm 106$ constraints), $\text{SVM}_2^{\Delta s}$ achieved $5.1 \pm 0.8\%$ test error ( $2626 \pm 225$ constraints), and $\text{SVM}_2^{\Delta m}$ achieved $5.1 \pm 0.7\%$ test error ( $2628 \pm 119$ constraints).

On synthetic sequence alignment tasks (learning 400 substitution parameters with $C=0.01, \epsilon=0.1$ averaged over 10 splits), $\text{SVM}_2$ achieved lower error rates than a generative sequence alignment baseline at smaller training sample sizes:
- $n=1$ : $\text{SVM}_2$ test error $47.0 \pm 4.6\%$ ( $7.8 \pm 0.3$ constraints) vs. generative baseline $74.3 \pm 2.7\%$ .
- $n=4$ : $\text{SVM}_2$ test error $14.4 \pm 1.4\%$ ( $31.9 \pm 0.9$ constraints) vs. generative baseline $28.0 \pm 2.3\%$ .
- $n=80$ : $\text{SVM}_2$ test error $2.8 \pm 0.6\%$ ( $252.7 \pm 2.1$ constraints) vs. generative baseline $1.9 \pm 0.4\%$ .
The size of the active constraint set $|S|$ grew sub-linearly with the number of training examples $n$ .

Coverage note — None was omitted; all primary methodological contributions, theoretical bounds, algorithmic specifications, and empirical evaluations across the four problem domains are included.

References

1.Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003). Hidden markov support vector machines. ICML.
2.Collins, M. (2002). Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. EMNLP.
3.Collins, M. (2004). Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods.
4.Crammer, K., & Singer, Y. (2001). On the algorithmic implementation of multi-class kernel-based vector machines. Machine Learning Research, 2, 265–292.
5.Hofmann, T., Tsochantaridis, I., & Altun, Y. (2002). Learning over structured output spaces via joint kernel functions. Sixth Kernel Workshop.
6.Joachims, T. (2003). Learning to align sequences: A maximum-margin approach (Technical Report). Cornell University.
7.Johnson, M. (1999). PCFG models of linguistic tree representations. Computational Linguistics.
8.Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. ICML.
9.Manning, C. D., & Schuetze, H. (1999). Foundations of statistical natural language processing. MIT Press.
10.Taskar, B., Guestrin, C., & Koller, D. (2004). Max-margin markov networks. NIPS 16.
11.Vapnik, V. (1998). Statistical learning theory. Wiley and Sons Inc.
12.Weston, J., Chapelle, O., Elisseeff, A., Sch¨olkopf, B., & Vapnik, V. (2003). Kernel dependency estimation. NIPS 15.
13.Weston, J., & Watkins, C. (1998). Multi-class support vector machines (Technical Report CSD-TR-98-04). Department of Computer Science, Royal Holloway, University of London.

Citation

MLA

Tsochantaridis, I., et al. “Support Vector Machine Learning for Interdependent and Structured Output Spaces”. Twenty-first International Conference on Machine Learning - ICML '04, 2004, p. 104, https://doi.org/10.1145/1015330.1015341.

APA

Tsochantaridis, I., Hofmann, T., Joachims, T., & Altun, Y. (2004). Support vector machine learning for interdependent and structured output spaces. Twenty-first International Conference on Machine Learning - ICML '04, 104. https://doi.org/10.1145/1015330.1015341

Chicago

Tsochantaridis, I., T. Hofmann, T. Joachims, and Y. Altun. 2004. “Support Vector Machine Learning for Interdependent and Structured Output Spaces”. Twenty-first International Conference on Machine Learning - ICML '04, 104. https://doi.org/10.1145/1015330.1015341.

Harvard

Tsochantaridis, I. et al. (2004) “Support vector machine learning for interdependent and structured output spaces”, Twenty-first international conference on Machine learning - ICML '04. ACM Press, p. 104. Available at: https://doi.org/10.1145/1015330.1015341.

Vancouver

1. Tsochantaridis I, Hofmann T, Joachims T, Altun Y (2004) Support vector machine learning for interdependent and structured output spaces. In: Twenty-first international conference on Machine learning - ICML '04. ACM Press, p 104

BibTeX

@inproceedings{Tsochantaridis_2004, series={ICML ’04}, title={Support vector machine learning for interdependent and structured output spaces}, url={http://dx.doi.org/10.1145/1015330.1015341}, DOI={10.1145/1015330.1015341}, booktitle={Twenty-first international conference on Machine learning  - ICML ’04}, publisher={ACM Press}, author={Tsochantaridis, Ioannis and Hofmann, Thomas and Joachims, Thorsten and Altun, Yasemin}, year={2004}, pages={104}, collection={ICML ’04} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

Support vector machine learning for interdependent and structured output spaces

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Joint Feature Representation and Linear Discriminant for Structured Prediction

Knowl 2 — Soft-Margin Structured SVM Formulations with Loss Re-scaling

Knowl 3 — Cutting Plane Algorithm for Structured SVM Dual Optimization

Knowl 4 — Polynomial Bound on Working Set Size and Convergence for Structured SVM

Knowl 5 — Upper Bound on Empirical Risk for Slack Re-scaled Structured SVMs

Knowl 6 — Structured SVM Formulation for Taxonomic Classification

Knowl 7 — Structured SVM for Supervised Natural Language Parsing

Knowl 8 — Structured SVM for Inverse Sequence Alignment