Mapping of categorical features into binary indicator features I am currently reading an introductory machine learning book by Daumé (ch. 03, p. 30) and when discussing the mapping of categorical features with "n" possible values into "n" binary indicator features, the following question is proposed:


  Is it a good idea to map a categorical feature with n values to log2(n) binary features?


Why wouldn't that be the case, seeing as how much resources could be spared by working with fewer features? Does this approach depend on the model that is being used?
Compactifying the data like this saves space in memory, but it adds false relationships that one-hot encoding doesn't.

Let's consider a categorical feature with levels A, B, C, D, that you decide to encode as 00, 01, 10, 11 respectively.

In a linear model, you only get three parameters (a constant and one for each new feature); you can fit "the right" parameters to hit A, B, and C, but then fixing those parameters determines what happens on D, and may be a very poor fit there.  (You're now assuming essentially that (B-A)+(C-A)=D-A.)

In k-NN, the distance between any two levels in the one-hot encoding is the same, 1.  In this encoding, the distance between A and B is 1, but the distance between A and D is $\sqrt{2}$.

In SVM, the set {A,D} is not separable from {B,C}.  With one-hot encoding, everything is separable.

In a tree model, using the raw categorical allows the tree to split any subset of the levels against the rest; using this binary encoding forces the tree to split (AB|CD) or (AC|BD) [missing (AD|BC)]; using one-hot encoding forces the tree to split (A|BCD) or (B|ACD) or (C|ABD) or (D|ABC).  The tree can split differently subsequently and eventually recover an arbitrary split, but a greedily built tree might never accomplish that.

Notice in particular that in these last three models, we've made A and D "more different" from each other than we might have reason to believe.  And in this small example, the catches were fairly small/few, but as the dimension increases these tend to become more exaggerated.

Now, it may still be the case that it's worth doing, but these are some things to consider.