Constrained optimization for validation-guided conditional random field learning

Minmin Chen, Yixin Chen, Michael R. Brent, Aaron E. Tenney

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Conditional random fields(CRFs) are a class of undirected graphical models which have been widely used for classifying and labeling sequence data. The training of CRFs is typically formulated as an unconstrained optimization problem that maximizes the conditional likelihood. However, maximum likelihood training is prone to overfitting. To address this issue, we propose a novel constrained nonlinear optimization formulation in which the prediction accuracy of cross-validation sets are included as constraints. Instead of requiring multiple passes of training, the constrained formulation allows the cross-validation be handled in one pass of constrained optimization. The new formulation is discontinuous, and classical Lagrangian based constraint handling methods are not applicable. A new constrained optimization algorithm based on the recently proposed extended saddle point theory is developed to learn the constrained CRF model. Experimental results on gene and stock-price prediction tasks show that the constrained formulation is able to significantly improve the generalization ability of CRF training.

Original languageEnglish
Title of host publicationKDD '09
Subtitle of host publicationProceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Pages189-197
Number of pages9
DOIs
StatePublished - 2009
Event15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09 - Paris, France
Duration: Jun 28 2009Jul 1 2009

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09
Country/TerritoryFrance
CityParis
Period06/28/0907/1/09

Keywords

  • Conditional random fields
  • Constrained optimization
  • Cross validation
  • Extended saddle points

Fingerprint

Dive into the research topics of 'Constrained optimization for validation-guided conditional random field learning'. Together they form a unique fingerprint.

Cite this