I am intrigued by the concept of a Maximum Entropy Markov Model (MEMM), and I am thinking of using it for a Part of Speech (POS) tagger. At the moment, I am using a conventional Maximum Entropy (ME) classifier to tag each individual word. This uses a number of features, including the preceding two tags.
MEMMs use the Viterbi algorithm to find the optimum path through the Markov Chain (ie. to find a complete optimum set of tags for the sentence rather than individual optimums for each word). Reading about it, this appears to be have a wonderful elegance and simplicity. However, each stage only relies on the "results" of the previous stage (i.e. as per a Markov Chain).
However, my ME model uses the previous two stages (i.e. the tags for the preceding two words). It seems I have two possible approaches:
As with a conventional Viterbi implementation, use a set of paths stored according to one (the previous) stage. My ME classifier would use this and a 'frozen' stage before this (frozen into the path under consideration) to produce the transfer function.
Or I write the algorithm to keep track of two stages. This is more complicated and would no longer be a true Markov Model because each transfer function (i.e. from the ME Model) would depend on the preceding two stages and not one stage.
It strikes me that the second will be more accurate, although it will be more complicated.
I have yet to find any examples of this during my literature search. Has it been tried? Did the two stage approach give an improvement to the overall accuracy?