Minmin Chen, Yixin Chen, Michael R. Brent
Conditional random field (CRF) is a popular graphical model for sequence labeling. The flexibility of CRF poses significant computational challenges for training. Using existing optimization packages often leads to long training time and unsatisfactory results. In this paper, we develop CRF-OPT, a general CRF training package, to improve the efficiency and quality for training CRFs. We propose two improved versions of the forward-backward algorithm that exploit redundancy and reduce the time by several orders of magnitudes. Further, we propose an exponential transformation that enforces sufficient step sizes for quasi-Newton methods. The technique improves the convergence quality, leading to better training results. We evaluate CRF-OPT on a gene prediction task on pathogenic DNA sequences, and show that it is faster and achieves better prediction accuracy than both the HMM models and the original CRF model without exponential transformation.
Subjects: 12. Machine Learning and Discovery; 9.2 Computational Complexity
Submitted: Apr 15, 2008