3
$\begingroup$

Let's say we have some sequence $y_1 \ldots y_n$. By definition, a 2nd order Markov model can capture more information from the sequence than a first or zeroth order Markov model. What I'm interested in, however, is if the first order model can capture some information that the second order model can't.

The reason I ask is the following. I have a procedure where, given a sequence with certain annotations, I learn a second order model from that sequence and use it to make predictions. These predictions are then used as input to the same procedure, and the process continues until the predictions don't change.

It turns out, however, that if I first do the above process using a first order model for several iterations, then use that output as an input for the same process with a second order model, I get even better results.

If I also add a zeroth order model before that, I get even better results.

My intuition tells me that the lower order models somehow filter out noise (i.e. false correlations that the second order model might capture), but I can't seem to find a good reason as to why this would happen.

Any suggestions? To those interested, the specific application is gene-start prediction.

$\endgroup$
2
  • 1
    $\begingroup$ What do you mean by "use that output"? I can think of several alternatives... $\endgroup$
    – jbowman
    Commented Sep 29, 2014 at 23:12
  • $\begingroup$ @Just, maybe you can describe the estimation procedure of the models more explicitly, eg, is it optimization-based? Is this a hidden Markov model? $\endgroup$
    – Andrew M
    Commented Sep 30, 2014 at 8:33

2 Answers 2

2
$\begingroup$

This is a typical overfitting situation. Your 2nd order class model contains the 1st order model, so in theory it should do better, but due to the finiteness of your training data, you are getting 'noisy' parameters that should have been zeros. This happens all the time, and the usual solution is to regularize the model (unless you are already doing so).

$\endgroup$
1
  • $\begingroup$ Note that I still run the second order model in the second case. The only difference is that I start off using a first order model and move on to a second order. If overfitting occurs, shouldn't both cases express it in the same way? Both ultimately use second order models. $\endgroup$
    – Just
    Commented Sep 29, 2014 at 19:58
1
$\begingroup$

The answer will be clearer if we address the two parts of your question separately.

The first is whether a first order model is capable of capturing information that a second order model cannot. The answer to this is, demonstrably, no, since we can write any first order model as a (degenerate) second order model.

The second, somewhat subtler issue is about performance of an estimated model. The more complex a model, the more noise will affect the estimates. Indeed, even a simpler, wrong, model* can outperform a more complex, correct model. For example parameter estimates of a simpler model may have substantially lower variance, which may be more than enough to overcome the greater bias (i.e. there's a bias-variance tradeoff). This would mean that in (say) mean-square-error terms, a simple model can outperform a complex one, even though the complex one subsumes the simple one within it.

* (even one known a priori to be wrong may nevertheless be a better choice, from a prediction point of view)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.