Model selection - Information criteria, part II

Submitted by Leo on Sat, 05/03/2008 - 00:57

Now for the hardcore information criteria part :) The first one can be found here.

The goal is still the same - pick a model $M$ to maximize the log-likelihood $ln p(D|M)$ of the data. This is given by $ln \int p(D | {\bf \theta} , M) p({\bf \theta} |M) d {\bf \theta}$ , where ${\bf \theta}$ is a $K$ -dimensional parameter vector. We can approximate the integral with a Laplace approximation, which is similar in idea to the previous post - the probability mass will be centered around the mode of the distribution. We can fit a normal distribution with the mode as mean, and variance approximated from Taylor expansion at the mode. Next 2 paragraphs can be skipped if you believe this :)

For example, to approximate a function $ln f({\bf z})$ that has a mode (and thus a local maximum) at ${\bf z_0}$ , we use the 2nd order Taylor:

$ln f({\bf z}) \simeq ln f({\bf z_0}) + \frac{1}{2} ({\bf z} - {\bf z_0})^T (\nabla \nabla ln f({\bf z_0})) ({\bf z} - {\bf z_0})$ (the first order term is 0 because of the local maximum)

Taking $A$ as the negative of the second derivative matrix, we get $f({\bf z}) \simeq f({\bf z_0}) \exp (- \frac{1}{2} ({\bf z} -{ \bf z_0})^T A ({\bf z} - {\bf z_0}))$ If we are looking for a probability distribution that is proportional to $f$ , we have ${\bf z_0}$ as the mean, $A^{-1}$ as the covariance matrix, and $\frac{ (2 \pi) ^ {\frac{K}{2}}}{| A | ^ {\frac{1}{2}}}$ as the normalizing coefficient - voila!

So we can fit a Gaussian to a function - back to information criteria. We'll fit a Gaussian to $ln \int p(D | {\bf \theta} , M) p({\bf \theta} |M) d {\bf \theta}$ at the mode (with the most likely parameter setting) ${\bf \theta_{MAP}}$ :

$ln p(D | M) \simeq ln \int p(D | {\bf \theta_{MAP}}, M) p({\bf \theta_{MAP}} | M) exp(-\frac{1}{2}({\bf \theta}-{\bf \theta_{MAP}})^T A ({\bf \theta}-{\bf \theta_{MAP}})) d {\bf \theta}=$
$= ln \left( p(D | {\bf \theta_{MAP}}, M)p({\bf \theta_{MAP}} | M) \frac{(2 \pi)^{\frac{K}{2}}}{|A|^{\frac{1}{2}}}\right) =$

$= ln p(D | {\bf \theta_{MAP}}, M) +ln p({\bf \theta_{MAP}} | M)- 0.5 ln |A| + Kc$

As before, the first term is the fit of the model to the data. The rest of the terms are the complexity penalty. The second term is small (if we assume a wide prior), and the last term scales with $K$ - the main penalty comes from $ln |A|$

To evaluate the determinant of the covariance matrix, we assume that it has full rank, and is due to $N$ iid data points. This means that $A$ is the sum of variances $A_n$ due to the data points, and since the data is iid, $A_i = A_j \forall i,j$ . So $ln|A| = ln |NA_1| = ln N^K |A_1| = K ln N + ln |A_1|$ . Again, last term is constant, so all in all we have
$ln p (D | M) \simeq ln p(D | {\bf \theta}_{MAP}, M) - 0.5 K ln N$

To recap, we estimated the probability of the data under the model, using the Laplace approximation to fit a Gaussian for the log-likelihood, and used some simplifying assumptions to arrive at the final form.

The end result is pretty much the Bayesian Information Criterion, and it penalizes model complexity more than AIC. Note that the constants in front are not arbitrary, since we never made any simplifications for them, and there's a 2:1 ratio. This one was for you Matti :)

Leo's blog

Login or register to post comments

typo

Submitted by Matias on Tue, 05/06/2008 - 21:40.

I assume there are typos here: "The a wide prior probability for the parameters, the second term is small, and the last term scales with - the main penalty comes from..."?

This second part went a little bit too hard core for me... I don't understand from this description what covariance matrix we're even talking about :) Can you expand or explain the beginning a little bit more as a comment, please.

If I understand anything from this, it is that the BIC doesn't make the assumption of the likelihood being a sharp peak at the MAP, whereas the BIC assumes a Gaussian to the likelihood function?

More on the Laplace approximation

Submitted by Leo on Tue, 05/06/2008 - 23:00.

Thanks for the typos and the feedback - in a large sense I'm writing these to think it through and remember it myself, so it may not be coherent :)

Instead of writing even more in the main text of the post - it's already really long - I'll just reply here.

For a Gaussian in 1 dimension, you have 2 numbers that describe it - mean and variance. In K dimensions, you have a vector $\bf \mu$ of length K for the mean, and a K x K matrix as $\Sigma$ a covariance matrix. The general form of the Gaussian is then given by

$p({\bf x} | {\bf \mu}, \Sigma) = \frac{1}{(2\pi)^{\frac{K}{2}}|\Sigma|^{\frac{1}{2}}} \exp\left(-\frac{1}{2} ({\bf x} - {\bf \mu})^T \Sigma^{-1} ({\bf x} - {\bf \mu}) \right)$

The cool part here is the if you know p is a probability distribution, and you know the exponent form, you can immediately deduce the rest - the covariance matrix must be the middle one, the mean must be the subtracted vector, and the normalizing coefficient must come out to the right value. And if you need to integrate over all possible x for the function exp(-0.5*(x-m)...), you know that will come to the inverse of the normalizing constant.

In the actual approximation, we take the same formula as in the example, and fit the function to it - the hairy integral over all the parameters comes down to just the inverse of the normalizing constant, and the rest is just assumptions and interpretation.

I'm happy to do it on the paper instead :)

As for what BIC does - you can just think of it as approximating the model evidence. It does not assume a Gaussian distribution, but tries to approximate it by one. In cases where you do have one mode that is not very skewed, this should give good results - but of course it's not always the case.

If you drop some assumptions, you can get better approximations for the tougher cases. But if you can afford to do it, you should do model selection in a fully Bayesian way instead of using these hacks :)

nag 2

Submitted by Matias on Tue, 05/06/2008 - 21:57.

Some more nagging: can you add a link to the first entry in this series?

PhD blog

User login

Navigation

Model selection - Information criteria, part II

typo

More on the Laplace approximation

nag 2