Support vector machine learning for interdependent and structured output spaces
By Ioannis Tsochantaridis, Thomas Hofmann, Thorsten Joachims, Yasemin Altun. 2004
1,486 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Information Systems, Information Extraction
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Mohit Bansal
- Percy Liang
- Jianfeng Gao
- Quoc V. Le
- Dacheng Tao
- Sergey Levine
- Trevor Darrell
In Information Systems
- Thorsten Joachims
- Hang Li
- Tie-Yan Liu
- Andrew McCallum
- Charles Sutton
- Lise Getoor
- Tao Qin
- Dacheng Tao
In Information Extraction
- Daniel Klein
- Thorsten Joachims
- David Chiang
- Stephen Clark
- Andrew McCallum
- Raquel Urtasun
- Sanja Fidler
- Chun-Nam John Yu
Citations in the corpus
- Fast Edge Detection Using Structured Forests (2014, methodology): “We demonstrate the potential of our approach as a general purpose edge detector by showing the strong cross dataset generalization of our learned edge models. ar X iv :1 40 6.”
- Learning human activities and object affordances from RGB-D videos (2012, methodology): “t nodes, i.e., 6090 variables). B. Learning. We take a large-margin approach to learning the parameter vector w of Eq. (9) from labeled training examples (x 1;y 1);:::;(x M;y M) (Taskar et al., 2004; Tsochantaridis et al., 2004). Our method optimizes a regularized upper bound on the training error R”
- Deep Metric Learning via Lifted Structured Feature Embedding (2015, neutral): “The experiments are performed with GoogLeNet [33].”
- Human Pose Estimation with Iterative Error Feedback (2015, background): “There is a rich literature on structured output learning [40, 7] (e.”
- Articulated Pose Estimation by a Graphical Model with Image Dependent Pairwise Relations (2014, methodology): “They are learnt separately by the K-means algorithm for r, DCNN for θ, and S-SVM for w.”
- Efficient Non-greedy Optimization of Decision Trees (2015, methodology): “Inspired by advances in structured prediction [24, 25, 26], we propose a convex-concave upper bound on the empirical loss.”
- Articulated Human Detection with Flexible Mixtures of Parts (2013, methodology): “This form of learning problem is known as a structural SVM, and there exist many well-tuned solvers such as the cutting plane solver of SVMStruct [43] and the stochastic gradient descent solver (SGD) in [4].”
- Structured Prediction Energy Networks (2015, methodology): “…extension of the implicit regression approach of LeCun et al. (2006) to structured objects, with a target application (multi-label classification), a family of candidate architectures (Section 3), and a training algorithm (a structured SVM (Taskar et al., 2004; Tsochantaridis et al., 2004)).”
- Multi-agent Diverse Generative Adversarial Networks (2017, methodology): “The intuition behind using these constraints comes from the well know 1 -slack formulation of the structured SVM framework [12, 24].”
- Learning to Detect Partially Overlapping Instances (2013, methodology): “This implies that we need to provide a way of imputing the latent variable such that the problem is reduced to the standard structural SVM in (3) for each iteration of the alternation algorithm.”
- Relational learning via latent social dimensions (2009, methodology): “Based on the extracted social features, a discriminative classi.er like SVM can be constructed to determine which dimensions are informative for classi.cation.”
- Online Multitask Learning (2006, background): “Much previous work on theoretical and applied multitask learning has concerned how to take advantage of cases in which a number of learning problems are related [3–8]; in contrast, we do not assume that the tasks are related and instead we consider how to take account of common consequences of error”
- Deep Multimodal Distance Metric Learning Using Click Constraints for Image Ranking (2017, methodology): “The method of cutting planes is adopted in [57] to iteratively find a small set of constraints, and then the small scale problem can be solved until the stop condition is satisfied.”
- Taxonomic Prediction with Tree-Structured Covariances (2013, methodology): “In the SVMstruct implementation of taxonomic prediction, the joint kernel function was implemented by multiplying Kij by Byiyj , which were both kept in memory to optimize computation time.”
- 3D Semantic Parsing of Large-Scale Indoor Spaces (2016, methodology): “This maximization is performed using an off-the-shelf LP/MIP solver and the weight vectors w are learned using Structured SVM [35].”
- Block Variable Selection in Multivariate Regression and High-dimensional Causal Inference (2010, background): “Multivariate Regression may be viewed as the classical precursor to many modern techniques in machine learning such as multi-task learning [15, 16, 1] and structured output prediction [18, 10, 22].”
- Glen, Glenda or Glendale: Unsupervised and Semi-supervised Learning of English Noun Gender (2009, methodology): “We train from these examples using a linear-kernel SVM via the the efficient SVM multiclass instance of the SVM struct software package (Tsochantaridis et al., 2004).”