Constrained Forward-Backward Algorithm

See: Forward-Backward Algorithm, Linear-Chain CRFs, CFB Algorithm.

References

(Banko & Etzioni, 2008) ⇒ Michele Banko, and Oren Etzioni. (2008). “The Tradeoffs Between Open and Traditional Relation Extraction.” In: Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL 2008).
- QUOTE: To obtain the probability at each position of a linear-chain CRF, the constrained forward-backward technique described in (Culotta and McCallum, 2004) is used.

(Culotta & McCallum, 2004) ⇒ Aron Culotta, and Andrew McCallum. (2004). “Confidence Estimation for Information Extraction.” In: Proceedings of HLT-NAACL (NAACL 2004).
- A specialization of Forward-Backward, termed Constrained Forward-Backward (CFB), returns exactly this probability.
  Because CRFs are conditional models, Viterbi finds the most likely state sequence given an observation sequence, defined as [math]\displaystyle{ s^* = \operatorname{argmax}_S p_\Lambda (\bf{s}|\bf{o}) }[/math]. To avoid an exponential-time search over all possible settings of [math]\displaystyle{ s }[/math], Viterbi stores the probability of the most likely path at time [math]\displaystyle{ t }[/math] that accounts for the first [math]\displaystyle{ t }[/math] observations and ends in state [math]\displaystyle{ s_i }[/math]. Following traditional notation, we define this probability to be [math]\displaystyle{ \delta_t(s_i) }[/math], where [math]\displaystyle{ \delta_0(s_i) }[/math] is the probability of starting in each state [math]\displaystyle{ s_i }[/math], and the recursive formula is [math]\displaystyle{ \delta_{t+1}(s_i) = \underset{s'}{\operatorname{max}} \biggl[ \delta_t(s') \biggl( \sum_k \lambda_k f_k(s',s_i,o,t) \biggr) \biggr] }[/math] (2) terminating in [math]\displaystyle{ s^* = \underset{s_1 \le s_i \le s_N}{\operatorname{argmax}} [\delta_T(S_i)] }[/math].