Predicting Structured Data

The MIT Press eBooksPublished 27 July 2007

DOI10.7551/mitpress/7443.001.0001

Citations533

TL;DR

This volume presents the state of the art in machine learning algorithms and theory in this novel field and discusses applications as diverse as machine translation, document markup, computational biology, and information extraction, providing a timely overview of an exciting field.

Abstract

State-of-the-art algorithms and theory in a novel domain of machine learning, prediction when the output has structure. Machine learning develops intelligent computer systems that are able to generalize from previously seen examples. A new domain of machine learning, in which the prediction must satisfy the additional constraints found in structured data, poses one of machine learning's greatest challenges: learning functional dependencies between arbitrary input and output domains. This volume presents and analyzes the state of the art in machine learning algorithms and theory in this novel field. The contributors discuss applications as diverse as machine translation, document markup, computational biology, and information extraction, among others, providing a timely overview of an exciting field. Contributors Yasemin Altun, Gökhan Bakir, Olivier Bousquet, Sumit Chopra, Corinna Cortes, Hal Daumé III, Ofer Dekel, Zoubin Ghahramani, Raia Hadsell, Thomas Hofmann, Fu Jie Huang, Yann LeCun, Tobias Mann, Daniel Marcu, David McAllester, Mehryar Mohri, William Stafford Noble, Fernando Pérez-Cruz, Massimiliano Pontil, Marc'Aurelio Ranzato, Juho Rousu, Craig Saunders, Bernhard Schölkopf, Matthias W. Seeger, Shai Shalev-Shwartz, John Shawe-Taylor, Yoram Singer, Alexander J. Smola, Sandor Szedmak, Ben Taskar, Ioannis Tsochantaridis, S.V.N Vishwanathan, Jason Weston

Keywords

Computer ScienceBiochemistry, Genetics and Molecular Biology

A training algorithm for optimal margin classifiers

11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more

A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.

On the algorithmic implementation of multiclass kernel-based vector machines

1,790 Citations2002Koby Crammer, Yoram Singer

This paper describes the algorithmic implementation of multiclass kernel-based vector machines using a generalized notion of the margin to multiclass problems, and describes an efficient fixed-point algorithm for solving the reduced optimization problems and proves its convergence.

Max-Margin Markov Networks

1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more

Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.

Lecture notes in computer scienceMachine Learning for Sequential Data: A Review

671 Citations2002Thomas G. Dietterich

This paper formalizes the principal learning tasks and describes the methods that have been developed within the machine learning research community for addressing these problems, including sliding window methods, recurrent sliding windows, hidden Markov models, conditional random fields, and graph transformer networks.

Hidden Markov support vector machines

469 Citations2003Yasemin Altün, Ioannis Tsochantaridis +1 more

This paper presents a novel discriminative learning technique for label sequences based on a combination of the two most successful learning algorithms, Support Vector Machines and Hidden Markov Models which it is called HM-SVMs and handles dependencies between neighboring labels using Viterbi decoding.

Expectation-propagation for the generative aspect model

442 Citations2002Thomas P. Minka, John Lafferty

Kernel Dependency Estimation

150 Citations2002Jason Weston, Olivier Chapelle +3 more

This work considers the learning problem of finding a dependency between a general class of objects and another, possibly different, generalclass of objects, made possible by employing similarity measures in both input and output spaces using kernel functions, thus embedding the objects into vector spaces.

View PDF

Efficient Training of Conditional Random Fields

128 Citations2002Hanna Wallach

This thesis explores a number of parameter estimation techniques for conditional random fields, a recently introduced probabilistic model for labelling and segmenting sequential data, and hypothesises that general numerical optimisation techniques result in improved performance over iterative scaling algorithms for training CRFs.