Training conditional random fields via gradient tree boosting

摘要: Conditional Random Fields (CRFs; Lafferty, McCallum, & Pereira, 2001) provide a flexible and powerful model for learning to assign labels elements of sequences in such applications as part-of-speech tagging, text-to-speech mapping, protein DNA sequence analysis, information extraction from web pages. However, existing algorithms are slow, particularly problems with large numbers potential input features. This paper describes new method training CRFs by applying Friedman's (1999) gradient tree boosting method. In boosting, the CRF functions represented weighted sums regression trees. Regression trees learned stage-wise optimizations similar Adaboost, but objective maximizing conditional likelihood P(Y|X) model. By growing trees, interactions among features introduced only needed, so although parameter space is potentially immense, search algorithm does not explicitly consider space. As result, scales linearly order Markov feature interactions, rather than exponentially like previous based on iterative scaling descent.