Conditional Random Fields (CRFs) is a useful technique toabel sequential data. Due to considering all label combinations of a sequence, CRFs'' training and testing are time consuming. In this work, we consider a Newton method for training CRFs because of its possible fast final convergence. The computational bottleneck is on the Hessian-vector product. We propose a novel dynamic programming technique to calculate it in polynomial time.
