The definition of MDL according to these slides is:

The minimum description length (MDL) criteria in machine learning says that the best description of the data is given by the model which compresses it the best. Put another way, learning a model for the data or predicting it is about capturing the regularities in the data and any regularity in the data can be used to compress it. Thus, the more we can compress a data, the more we have learnt about it and the better we can predict it.

MDL is also connected to Occam’s Razor used in machine learning which states that "other things being equal, a simpler explanation is better than a more complex one." In MDL, the simplicity (or rather complexity) of a model is interpreted as the length of the code obtained when that model is used to compress the data.

To put it in short according to MDL principle, we prefer predictors with relatively smaller description length (i.e can be described within a certain length) for a given description language (this definition is without delving into exact technical details as it is not necessary to the question).

Since MDL is dependent on the description language we use, can we say feature engineering can cause a change in the selection of the predictor? For example as this picture shows:

enter image description here

To me, it seems that, in the first picture, we will require a longer description length predictor in Cartesian coordinates, as compared to a predictor in polar co-ordinates (just a single discerning radius needs to be specified). So, to me, it seems feature engineering changed the selection of the predictor to a relatively simple one (in the sense that it will have a shorter description length). Thus feature engineering has changed the description length required for out predictor. Did I make any wrong assumptions? If so why?

  • $\begingroup$ You're completely right. For points in cartesian coordinates, your final model would require at least 3 parameters a,b,c since the equation of a circle is: $(x-a)^2+(y-b)^2=c^2$ while in polar coordinates you final model would require only one parameter since a vertical line $p=a$ is enough to separate the two classes. $\endgroup$ – Edoardo Guerriero Apr 10 at 0:39

I think the wrong assumption here is that you've forgotten the cost of encoding the new features!

MDL should be considered relative to the original or raw dataset. The idea is that you want to find an expression you could send to someone else that encodes the structure of the dataset in terms of the original variables. If you define new features, you need to send a description of those features along with your model.

To make this clearer, imagine you call me up on the phone, and we're both looking at your left hand image. You say to me 'Yeah, you just draw a line through it at $p=a$'. The natural question for me to ask is 'What's p?'. If you have to tell me what $p$ is, then it's part of the description length.

A circular model for your lefthand image does have a MDL for its decision boundary of something like $(x−a)^2+(y−b)^2=c$. However, the feature transformation you've selected has a description length of $p=(x-a)^2 + (y-b)^2$. It should be clear that the description lengths for the linear model through $p$ and the circular model through $x$ and $y$ are identical.

| improve this answer | |
  • $\begingroup$ The main thing I was trying to look into was what if I change the basis to cylindrical coordinates, or polar coordinates. I used to do this in electromagnetics to simplify the sum without incurring great cost of calculation. Does the problem here result in a tradeoff not so favourable? $\endgroup$ – DuttaA Apr 13 at 22:55
  • $\begingroup$ So here, we're interested in the size of the information you need to communicate to someone who's just looking at the original features. So if you have to say: "Transform to polar coordinates with center at (a,b), and then draw a line at c", that's really not any savings over saying "Draw a circle centered at (a,b) with radius c". See the issue? $\endgroup$ – John Doucette Apr 13 at 22:57
  • $\begingroup$ Hmmm...I get it, but is this an idea used commonly? Say I already know the decision boundary will be a certain algebraic basis, so I collect points in that algebraic basis i.e my original dataset is already feature engineered (compared to the Cartesian system). Does such universal basis exist? (the idea is somewhat similar to cross entropy loss, even though its not perfect, we know it works for a wide range of problems) $\endgroup$ – DuttaA Apr 13 at 23:01
  • $\begingroup$ If you know in advance that certain features are useful, then indeed, you could collect them. I would say MDL is useful when comparing two models that were developed for the same data. It is not useful if we compare two models developed on different representations of the same data, except insofar as we can say that one model learned the feature transforms that the other model got for free. $\endgroup$ – John Doucette Apr 13 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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