random forest - summarize two features in one without losing information

Question

I am training a random forest on a dataset including both categorical and numerical features. In particular I have a binary feature, call it $x_1$, which has $0$ or $1$ as possible outcomes. I also have a feature, call it $x_2$, which has integer values $1, 2, 3, 4, 5$ as possible outcomes.

The training set is not very large and when training I have overfitting (perfect score on training set, 75% accuracy on test set), thus I want to reduce the number of features.

My question is: does it make sense to replace $x_1$ and $x_2$ by a new feature, call it $x_3$, defined by $$ x_3 = x_1 + 2^{-x_2} \quad ? $$ In this way I seem to have the best of both worlds: I have reduced the number of features by one (thus, in principle, reducing overfitting) and at the same time I didn't lose any information, because: if a training sample has $x_1=0$, it will have $x_3$ between $2^{-5}$ and $1/2$; if on the other hand $x_1=1$, it will have $x_3$ between $1+2^{-5}$ and $3/2$. The two subsets stay well detached one from the other and the random forest in principle should be able to discriminate between them.

This seems to me too good to be true. Does this procedure can really reduce overfitting without reducing the "power" of the model?

Answer 1

No, you can not reduce overfitting without reducing the information your algorithm can use, this is the whole point of overfitting! You can pick an algorithm that uses less information (more bias, less variance), or provide better information to your algorithm (less noise makes it harder to fit the noise).

While you indeed reduced the number of features, you did not change the information the algorithm had access to, the number of possible splits points for the tree. It is as able as before to isolate points. But you have introduced structure in your data that might not exists.

Consider the reverse: when a feature has differents levels, say $x \in \{1,2,3\}$, the fact that $3>2>1$ should be relevant, for exemple in the price of an object. If it is not, for exemple if $1,2,3$ are tokens for countries of origin (without clear ordering), then you should split your feature into three distinct binary features, $a_{x = 1}, b_{x = 2}, c_{x = 3}$. This does not increase the number of possible split points, but it makes the splits more meaningful. $\text{price} < 3$ is meaningful, but $\text{country_index} < 3$ is not and the second one makes it harder to learn what the data has to say.

If you want to reduce overfitting, using random forests, you can

• Increase the number of trees you grow
• Grow shallower trees
• Reduce the number of features that are tried for each split

And acting on your features, you can

• Use dimensionality reduction (PCA, SVD, ...) to extract the most meaningful information, and try to discard noise.

Answer 2

There's a proof by contradiction here.

Suppose you have any number of predictors, $x_1, x_2, x_3, \ldots$, of any type, but encoded in some scheme as integers. Apply the following mapping, which is similar to yours

• For the feature $x_1$, map the level $n$ to $2^n$.
• For the feature $x_2$, map the level $n$ to $3^n$
• For the feature $x_3$, map the level $n$ to $5^n$

and so on. Each feature $x_i$ has it's levels mapped to $(\text{i'th prime})^{\text{level}}$.

Now use these individual mappings to map the entire feature space to one dimension as

$$ (x_1 = n_1, x_2 = n_2, x_3 = n_3, \ldots) \rightarrow 2^{n_1} 3^{n_2} 5^{n_3} \cdots$$

By the prime factorization theorem, each possible point in the feature space is sent to a unique point on the number-line (i.e. no two get mapped to the same integer). So, in fact, any number of features can have their dimension "reduced" to one by this scheme.

The issue with this is that the mapping is very, very complex. All the individual dimensions get mixed together into one in an extremely unintuitive way. So, while in naturally occurring situations, the number of dimensions is an effective proxy for the "complexity" of the model, in this case it is not. All the complexity is hidden in how the features are embedded in one dimensional space.

Answer 3

This approach probably won't solve your problem. Your algorithm will still overfit your new predictor, except you also lose the ability to make neat, ordinal splits on $x_1$ or $x_2$ (in that if there is a valid relationship $x_1$ and $x_2$ and your response, splitting on it is now harder).

Better would be to control the model complexity via the hyperparameters to your randomforest algorithm, such as the number of trees, the number of nodes, the bagging fraction, etc.