To apply the Bayes decision rule for minimum symbol error rate, we first compute the marginal Again, since the model is a second-order model, the sum over all possible POS tag strings g N 1 (with g m = g) can be computed efficiently using a suitable extension of the forward-backward algorithm (Bahl et al., 1974).
we obtain the decision rule for minimum symbol error at positions m = 1, ..., N : Here, after the the marginal probability p m (g, w N 1 ) has been computed, the task of finding the most probable POS tag at position m is computationally easy.