24
$\begingroup$

How can we compare complexity of two models with the same number of parameters?

Edit 09/19: To clarify, model complexity is a measure of how hard it is to learn from limited data. When two models fit existing data equally well, a model with lower complexity will give lower error on future data. When approximations are used, this may technically not always be true, but that's OK if it tends to be true in practice. Various approximations give different complexity measures

Improve this question
$\endgroup$
12
  • $\begingroup$ can you give more information about what attributes are available about the models? $\endgroup$
    – shabbychef
    Commented Sep 18, 2010 at 20:42
  • $\begingroup$ This is kind of an open question, so my question would be -- what kind of attributes do I need to be able to measure complexity? At the most basic level, a probability model is a set of probability distributions, and I fit the model to data by picking the best fitting member $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 18, 2010 at 21:32
  • 3
    $\begingroup$ What, precisely, is "complexity"? (This is not a flippant question!) In the absence of a formal definition, we cannot hope to make valid comparisons of something. $\endgroup$
    – whuber ♦
    Commented Sep 19, 2010 at 13:30
  • $\begingroup$ That's what I'm asking essentially $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 19, 2010 at 17:49
  • 2
    $\begingroup$ But can't you at least give us a hint as to what aspect of a model you're trying to capture in the word "complexity"? Without that, this question is just to ambiguous to admit one reasonable answer. $\endgroup$
    – whuber ♦
    Commented Sep 19, 2010 at 18:14

7 Answers 7

Reset to default
13
$\begingroup$

Besides the various measures of Minimum Description Length (e.g., normalized maximum likelihood, Fisher Information approximation), there are two other methods worth to mention:

  1. Parametric Bootstrap. It's a lot easier to implement than the demanding MDL measures. A nice paper is by Wagenmaker and colleagues:
    Wagenmakers, E.-J., Ratcliff, R., Gomez, P., & Iverson, G. J. (2004). Assessing model mimicry using the parametric bootstrap. Journal of Mathematical Psychology, 48, 28-50.
    The abstract:

    We present a general sampling procedure to quantify model mimicry, defined as the ability of a model to account for data generated by a competing model. This sampling procedure, called the parametric bootstrap cross-fitting method (PBCM; cf. Williams (J. R. Statist. Soc. B 32 (1970) 350; Biometrics 26 (1970) 23)), generates distributions of differences in goodness-of-fit expected under each of the competing models. In the data informed version of the PBCM, the generating models have specific parameter values obtained by fitting the experimental data under consideration. The data informed difference distributions can be compared to the observed difference in goodness-of-fit to allow a quantification of model adequacy. In the data uninformed version of the PBCM, the generating models have a relatively broad range of parameter values based on prior knowledge. Application of both the data informed and the data uninformed PBCM is illustrated with several examples.

    Update: Assessing model mimicry in plain English. You take one of the two competing models and randomly pick a set of parameters for that model (either data informed or not). Then, you produce data from this model with the picked set of parameters. Next, you let both models fit the produced data and check which of the two candidate models gives the better fit. If both models are equally flexible or complex, the model from which you produced the data should give a better fit. However, if the other model is more complex, it could give a better fit, although the data was produced from the other model. You repeat this several times with both models (i.e., let both models produce data and look which of the two fits better). The model that "overfits" the data produced by the other model is the more complex one.

  2. Cross-Validation: It is also quite easy to implement. See the answers to this question. However, note that the issue with it is that the choice among the sample-cutting rule (leave-one-out, K-fold, etc) is an unprincipled one.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't really understand "model mimicry", but cross-validation seems to just postpone the task of assessing complexity. If you use data to pick your parameters and your model as in cross-validation, the relevant question becomes how estimate the amount of data needed for this "meta"-fitter to perform well $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 20, 2010 at 17:09
  • $\begingroup$ @Yaroslaw: I don't really understand your issue with cross-validation, but to be honest I am no expert there. However, I would really like to make a point for measuring model mimicry. Therefore, see my updated answer. $\endgroup$
    – Henrik
    Commented Sep 21, 2010 at 8:46
6
$\begingroup$

I think it would depend on the actual model fitting procedure. For a generally applicable measure, you might consider Generalized Degrees of Freedom described in Ye 1998 -- essentially the sensitivity of change of model estimates to perturbation of observations -- which works quite well as a measure of model complexity.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hm...the paper is all about regression, I wonder if this can be used for discrete probability estimation. Also, I don't really understand the motivation he gives for it -- gdf is a degree of sensitivity of parameters to small changes in data, but why is it important? I could choose a different parameterization where small changes in parameters in original parameterization correspond to large changes in the new parameterization, so it'll seem more sensitive to data, but it's the same model $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 18, 2010 at 22:07
  • $\begingroup$ Yaroslav:> *I could choose a different parameterization where small changes in parameters in original parameterization correspond to large changes in the new parameterization, so it'll seem more sensitive to data * can you give an example (involving an affine equivariant estimator)? Thanks, $\endgroup$
    – user603
    Commented Sep 18, 2010 at 22:24
  • 1
    $\begingroup$ DoF in linear regression work out to the trace of the hat matrix or the sum of sensitivities -- so the motivation/concept aren't all that far out. Tibshirani & Knight proposed Covariance Inflation Criterion which looks at covariances of model estimates instead of sensitivities. GDF seems to have been applied in a number of model procedures like cart and wavelet thresholding (Ye's paper on adaptive model selection has more details), and in ensemble methods to control for complexity, but I don't know of any discrete estimation cases. Might be worth trying ... $\endgroup$
    – ars
    Commented Sep 18, 2010 at 23:11
  • $\begingroup$ Don't know about "affine equivariant estimators", but suppose we rely on maximum likelihood estimator instead. Let q=f(p) where f is some bijection. Let p0,q0 represent MLE estimate in corresponding parameterization. p0,q0 are going to have different asymptotic variances, but in terms of modeling data, they are equivalent. So the question comes down to -- in which parameterization is the sensitivity of parameters representative of expected risk? $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 18, 2010 at 23:15
6
$\begingroup$

Minimum Description Length (MDL) and Minimum Message Length (MML) are certainly worth checking out.

As far as MDL is concerned, a simple paper that illustrates the Normalized Maximum Likelihood (NML) procedure as well as the asymptotic approximation is:

S. de Rooij & P. Grünwald. An empirical study of minimum description length model selection with infinite parametric complexity. Journal of Mathematical Psychology, 2006, 50, 180-192

Here, they look at the model complexity of a Geometric vs. a Poisson distribution. An excellent (free) tutorial on MDL can be found here.

Alternatively, a paper on the complexity of the exponential distribution examined with both MML and MDL can be found here. Unfortunately, there is no up-to-date tutorial on MML, but the book is an excellent reference, and highly recommended.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I've read that paper and it seems like Stochastic Complexity fixes the problem of not being able to distinguish between models of same dimensions, but introduces a problem of sometimes not being able to distinguish between models of different dimensions. Geometric distribution is assigned infinite complexity, surely not what we'd expect for such a simple model! $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 20, 2010 at 6:45
  • $\begingroup$ Very good point about infinite stochastic complexity (SC). Solutions to the problem of infinite SC exist, but are not very elegant; Rissanen's renormalization works well in linear models, but is not easy to do for the Poisson/Geometric problem. The MML (or SMML) encoding of Poisson/Geometric data is fine though. $\endgroup$
    – emakalic
    Commented Sep 20, 2010 at 7:07
5
$\begingroup$

Minimum Description Length may be an avenue worth pursuing.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Just a quick note: minimum description length is very powerful and useful, but it can take ages to obtain results, especially when using normalized maximum likelihood withslighltty larger datasets. I once took 10 days running FORTRAN code to get it for just one model $\endgroup$
    – Dave Kellen
    Commented Sep 20, 2010 at 9:02
3
$\begingroup$

By "model complexity" one usually means the richness of the model space. Note that this definition does not depend on data. For linear models, the richness of the model space is trivially measured with the diminution of the space. This is what some authors call the "degrees of freedom" (although historically, the degrees-of-freedom was reserved for the difference between the model space and the sample space). For non linear models, quantifying the richness of the space is less trivial. The Generalized Degrees of Freedom (see ars's reply) is such a measure. It is indeed very general and can be used for any "weird" model space such as trees, KNN, and the likes. The VC dimension is another measure.

As mentioned above, this definition of "complexity" is data independent. So two models with the same number of parameters will typically have the same "complexity".

Improve this answer
$\endgroup$
1
$\begingroup$

From Yaroslav's comments to Henrik's answer:

but cross-validation seems to just postpone the task of assessing complexity. If you use data to pick your parameters and your model as in cross-validation, the relevant question becomes how estimate the amount of data needed for this "meta"-fitter to perform well

I wonder whether this is not in itself informative. You perform several $k$-fold CV with varying $k$ (say along a grid) and look which model performs better as $k$ increases. More specifically: I wonder whether any differentiation among the two model in there $CV(k)$ performance as a function of $k$ can be taken as evidence that this model (the one whose relative performance decreases less when $k$ increases) would be the less complex one.

You could even give a 'significance' flavor to this since the result of the procedure is directly in terms (units) of difference in out of sample forecasting error.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ I would agree that Cross Validation solves the problem of measuring model complexity. Maybe I'm asking the wrong question, because a practical question is the sample complexity of the fitting procedure. Cross-validated learner would try different models and pick the one with lowest cross validation error. Now the question is -- is this learner more likely to overfit than one that fits a single model by maximum likelihood? $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 21, 2010 at 18:30
  • $\begingroup$ Yaroslav Bulatov:> yes but you can use ML only to compare nested models. Insofar as you specified (in your question) mentioned models with the same number of parameters, then they cannot be nested. $\endgroup$
    – user603
    Commented Sep 21, 2010 at 18:39
  • $\begingroup$ Another issue is that cross-validation doesn't add to our understanding of model complexity. Measures like AIC/BIC make it clear that lots of parameters encourage overfitting. Now the question becomes -- what aspects of the model besides dimension increase capacity to overfit? $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 21, 2010 at 21:56
  • $\begingroup$ Yaroslav:> Again, very good point. $\endgroup$
    – user603
    Commented Sep 21, 2010 at 22:28
  • $\begingroup$ If overfitting is the tendency of a model fitting procedure to fit noise in addition to signal, then we can look at a given procedure to see where such tendencies could arise. Perhaps due to a lack of imagination or knowledge, while considering a few different procedures, I couldn't boil this down to something that can't be restated as "number of parameters" (or "effective number of parameters"). We could flip this on its head and ask: all else equal, what happens when we introduce noise to our data? Then we arrive at measures such as Ye's GDF. $\endgroup$
    – ars
    Commented Sep 23, 2010 at 23:22
0
$\begingroup$

What about the information criterion for model comparison? See e.g. http://en.wikipedia.org/wiki/Akaike_information_criterion

Model complexity is here the number of parameters of the model.

Improve this answer
$\endgroup$
2
  • $\begingroup$ AIC is not a measure of model complexity. $\endgroup$
    – Sven Hohenstein
    Commented Dec 16, 2012 at 14:19
  • 1
    $\begingroup$ @SvenHohenstein, from his last sentence, I gather that he isn't suggesting that the AIC itself, is a measure of model complexity. Brause42, note that the question specifically asks about models w/ the same number of parameters. Thus, the AIC will reduce to SSE or deviance, or whatever. $\endgroup$
    – gung - Reinstate Monica
    Commented Dec 16, 2012 at 14:37

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.