Training structural SVMs when exact inference is intractable

By Thomas Finley, Thorsten Joachims. 2008

312 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Optimization & Training

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

In Optimization & Training

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “The cutting plane algorithm of Tsochantaridis et al. (2005) was considered with approximate maximization by Finley & Joachims (2008), though the dependence of the running time on the the approximation error was left unclear.”
Learning human activities and object affordances from RGB-D videos (2012, methodology): “The parameters of this model are learnt using a structural support vector machine (SSVM) formulation (Finley and Joachims, 2008).”
Learning Answer-Entailing Structures for Machine Comprehension (2015, methodology): “We use a convex upper bound of the loss function (Yu and Joachims, 2009) to rewrite the objective: This problem can be solved using Concave-Convex Programming (Yuille and Rangarajan, 2003) with the cutting plane algorithm for structural SVM (Finley and Joachims, 2008).”
Structured Prediction Energy Networks (2015, methodology): “Using the LP relaxation, instead of exact MAP inference, in the inner loop of CRF SSVM learning is fairly benign, since it is guaranteed to over-generate margin violations in (8) (Kulesza & Pereira, 2007; Finley & Joachims, 2008).”
Learning message-passing inference machines for structured prediction (2011, background): “Unfortunately, learning these models with approximate inference is not well understood [9, 6].”
Multi-Level Structured Models for Document-Level Sentiment Classification (2010, unknown): “So long as the global inference procedure is tractable or has a good approximation algorithm, then the training procedure is guaranteed to converge with rigorous generalization guarantees (Finley and Joachims, 2008).”
Associative hierarchical CRFs for object class image segmentation (2009, background): “An alternative and elegant approach to this is that of [9] which we intend to investigate in future work.”
On label dependence and loss minimization in multi-label classification (2012, methodology): “Finley and Joachims (2008) and Hariharan et al. (2010) (M3L) tailored this algorithm explicitly to minimize the Hamming loss in MLC problems.”
Predicting Program Properties from "Big Code" (2015, methodology): “Approximate algorithms Previous studies [8, 12] for MAP inference in networks of arbitrary shapes discuss loopy-belief propagation, greedy algorithms, combination approaches or graph-cut based algorithms.”
Minimum-Risk Training of Approximate CRF-Based NLP Systems (2012, methodology): “Those include maximum margin (Taskar et al., 2003; Finley and Joachims, 2008) and softmax-margin (Gimpel and Smith, 2010).”
End-to-End Learning for Structured Prediction Energy Networks (2017, background): “(4) returns a lower bound, eg. by solving an LP relaxation (Finley & Joachims, 2008).”
Deep Structured Neural Network for Event Temporal Relation Extraction (2019, methodology): “To summarize, our main contributions are: • We propose a deep SSVM model for event temporal relation extraction.”
Structured Learning and Prediction in Computer Vision (2011, background): “In fact, recent results suggest that the use of suboptimal predictions during training can lead to prediction functions with bad performance [39, 86, 99], whereas alternative approaches based on relaxing the prediction problem work well in training.”
Structure preserving embedding (2009, methodology): “For the cutting plane formulation, we add constraints iteratively, and it can be shown that the algorithm will converge in polynomial time for quadratic programs with linear constraints (Finley & Joachims, 2008).”
Tractable Semi-supervised Learning of Complex Structured Prediction Models (2013, methodology): “We implemented TSVM+ based upon the Matlab version of structured SVM [33,13].”
Learning Mixtures of Submodular Shells with Application to Document Summarization (2012, background): “Generalization bounds for approximate learning with cutting-plane algorithms, with either undergenerating or overgenerating inferences, have been shown in [12].”
Predicting diverse subsets using structural SVMs (2008, methodology): “Despite using an approximate constraint generation oracle, SVM training is still known to terminate in a polynomial number of iterations (Finley & Joachims, 2008).”
Contextually Guided Semantic Labeling and Search for 3D Point Clouds (2011, methodology): “Since our training problem is an overgenerating formulation as deﬁned in (Finley and Joachims, 2008), the value of ξ at the solution is an upper bound on the training error in Eq.”
Contextually guided semantic labeling and search for three-dimensional point clouds (2013, methodology): “The model admits efficient approximate inference (Rother et al., 2007), and we show that it can be trained using a maximum-margin approach (Taskar et al., 2004; Tsochantaridis et al., 2004; Finley and Joachims, 2008) that globally minimizes an upper bound on the training loss.”