For clarity, we define the local factors as: Note that we can ignore the subscript t at Ψ 2 t (y t−1 = j, y t = i) by defining an HMM-like model, that is, transition matrix Ψ 2 j,i is independent of t. As exact inference, we use the forward-backward procedure to calculate marginals .
time complexity is O(t |Y| 2 ) for exact inference (i.e., forward-backward and Viterbi algorithm) of linear-chain CRFs (Lafferty et al., 2001).