Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

4 Parameter estimation for CRFs

1. How did Lafferty et al. train CRFs?
   By maximizing conditional log-likelihood with improved iterative scaling variants. Algorithm S adds a global “slack” feature making the total feature count constant; Algorithm T tracks partial feature totals per sequence and converges faster when lengths vary. Expectations come from forward–backward vectors \(\alpha_i = \alpha_{i-1} M_i\), \(\beta_i = M_{i+1} \beta_{i+1}\).
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §4
2. Why can Algorithm S converge slowly?
   Its slack constant \(S\) is proportional to the longest training sequence length, so each iteration takes very small steps.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §4
3. How costly is one CRF training iteration?
   Roughly as costly in time and space as one Baum–Welch iteration for HMMs, because expectations are computed with forward–backward recursions over the chain.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §4