# Unbiased Measurement of Feature Importance in

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,

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.
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.
• Thanks for the quick and helpful answer. Allow me to ask back 1. I understand that within a node the split on the test data shuold not change the expectation: $E(p'_{m,1} ) = E(p'_{l,1} ) E(p'_{r,1} )$ but because of previous informative splits the class proportion should not be equal to $p'_{1}$!? In any case, you only need the first equality for the proof.. 2. I understand that $\omega_{m,l,r}$ denotes the training set proportion but would you not need to somehow use $\omega'_{m,l,r}$ as well since your new impurity mixes train and test data ? Thanks again Feb 12, 2020 at 12:29
• I missed an = in the previous comment (cannot edit any more): $E(p'_{m,1} ) = E(p'_{l,1} ) = E(p'_{r,1} )$ Feb 12, 2020 at 13:07
• Hi Markus, I see your point here. I guess it‘s due to the confusion caused in the notation. I use $p_1'$ to denote the class proportion in that given node, which has nothing to do with any of its parent node. Yes previous informative splits will definitely change class proportion, but the whole proof is focused on the current node and its two children. Basically Lemma 1 and 3 in some sense are "local" result which applies to the current node and split only. Hope this helps. Feb 12, 2020 at 20:57