Some things you can try:
Oversample your target classes. Insert duplicate records of your other three classes to augment your training dataset
Undersample the negative responses. Instead of including all instances of other in your training data, only use a small portion.
Bootstrap undersample the negative responses. This is probably your most robust option ...
One method that I have used with success is resampling the data. I run bootstraps by taking N samples from each class where N is the size of the class with the smallest samples. The N samples are chosen randomly without replacement. Then I split each resampled class into a training and test set (say 70-30 split) and run my classifier. For each boot strap I ...
Expanding on my comment: the answer is clearer when you realize that you can't ignore the observed variables. They affect each model differently. As it turns out, the MEMM is not I-equivalent to the linear-chain CRF and HMM.
As a recap, the HMM looks like this:
y1 -> y2 -> y3 -> ... -> yn
| | | |
v v v v