Learning as search optimization: approximate large margin methods for structured prediction

By Hal Daumé Iii, Daniel Marcu. 2005

278 citations recorded by the source corpus.

Mappings to structured output spaces (strings, trees, partitions, etc.) are typically learned using extensions of classification algorithms to simple graphical structures (eg., linear chains) in which search and parameter estimation can be performed exactly. Unfortunately, in many complex problems, it is rare that exact search or parameter estimation is tractable. Instead of learning exact models and searching via heuristic means, we embrace this difficulty and treat the structured output problem in terms of approximate search. We present a framework for learning as search optimization, and two parameter updates with convergence the-orems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.

Subfields: Computer Science Applications, Developmental and Educational Psychology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Science Applications

In Developmental and Educational Psychology

Citations in the corpus

Sequence-to-Sequence Learning as Beam-Search Optimization (2016, methodology): “In practice, generation is accomplished by searching over output sequences greedily or with beam search.”
Learning to Search Better than Your Teacher (2015, neutral): “Daumé III et al. (2014)).”
Differentiable Scheduled Sampling for Credit Assignment (2017, background): “These include reinforcement learning (Ranzato et al., 2016; Bahdanau et al., 2017), imitation learning (Daum´e et al., 2009; Ross et al., 2011; Bengio et al., 2015), and beam-based approaches (Wiseman and Rush, 2016; Andor et al., 2016; Daum´e III and Marcu, 2005).”
Maximum Margin Reward Networks for Learning from Explicit and Implicit Supervision (2017, background): “Later, the learning to search framework is proposed (Daumé and Marcu, 2005; Daumé et al., 2009), which casts the structured prediction task as a general search problem.”
Discriminative Syntax-Based Word Ordering for Text Generation (2015, unknown): “Our learning algorithm is similar to LaSO with best-ﬁrst inference, but the parameter updates are different.”
Structured learning with constrained conditional models (2012, background): “Recently, Daumé and Marcu (2005), Kazama and Torisawa (2007), Huang (2008) proposed to use approximate inference procedure and let the weights of the long distance features guide the search procedure.”
Structured Learning with Approximate Inference (2007, unknown): “(The instances are algorithmically separable with margin γ.) Suppose that there also exists R such that ‖Φ(xi, zi) − Φ(xi, z)‖ ≤ R for all z ∈ Z ′(xi).”
Multi-domain spoken language understanding with transfer learning (2009, methodology): “…including structured perceptron (Collins, 2002), conditional random fields (Lafferty et al., 2001), maximum-margin Markov network (Taskar et al., 2003), support vector machine for structured outputs (Tsochantaridis et al., 2005) and search-based structured prediction (Daumé and Marcu, 2005).”
Learning to Search in Branch and Bound Algorithms (2014, background): “The number of branches in this process is NB(m, opt)= m 11−2 1 .”
Training Deterministic Parsers with Non-Deterministic Oracles (2013, background): “Other related approaches in the machine learning literature include stacked sequential learning (Cohen and Carvalho, 2005), LaSO (Daum´e III and Marcu, 2005), Searn (Daum´e III et al., 2009) and SMILe (Ross and Bagnell, 2010).”
Structured prediction with reinforcement learning (2009, methodology): “As a follow up of this work ([4],[7],[6]), we investigate here the use of reinforcement learning algorithms for SP tasks.”