Unbiased Measurement of Feature Importance in

Question

My questions are about some of the details in the appendix of the paper Unbiased Measurement of Feature Importance in Tree-Based Methods (on arXiv).

On p.13, it says:

1. Given that the test data is independent of the training data and the independence between $X_j$ and $y$, then in expectation, we should have $E(p'_{m,1} ) = E(p'_{l,1} ) = p'_{1}$, where $p'_{1}$ is the class 1 proportion evaluated on the test data.
2. (As previously defined in Eq. (7) on p.8) $\Delta'(\theta^*_m) = \omega_m H'(m) - ( \omega_l H'(l) + \omega_r H'(r) )$, where $\omega_{m,l,r}$ are the proportions of observations falling into each node $m, l, r$.

I do not see why the expected proportion of class 1 in the test set at each node should be equal to the global $p'_{1}$! After all, the tree was built with the goal of changing the class distributions at each split, which would also affect the test data. Further: since the definition of the modified impurity $H'(m) = 1- p_{m,1} p'_{m,1}- p_{m,2} p'_{m,2}$ contains a mixture of train and test data, it is not clear any longer how exactly the $\omega_{m,l,r}$ are defined ? Do we not need a test version $\omega'_{m,l,r}$?

Thanks,

Answer 1

You are totally right that "the tree was built with the goal of changing the class distributions at each split". However, the split was chosen based solely on the training data within the node which you want to split on. If you have an independent test data, and the feature $X_j$ (where split happens) is also independent of target $y$, the class proportion is invariant when evaluated on the test set.

This is exactly how the bias problem kicks in in the first place. The original split improvement measures on the training data, where the class distribution will change even if the feature has no predictive power for the target.

And I'm sorry for the confusion caused in terms of notation. Generally, symbols without a prime denotes quantities related to the training data. So in this case $\omega_m, \omega_l, \omega_r$ are for training data.

Answer 2

Just to follow up on Zhengze's reply: the test should work for any weighting on each side of the split since the change in impurity is zero in expectation. We've used training weights just because that's what is usually recorded when trees are built and it keeps us closer to the original variable importance measures. But we could also use test weights or average the two.