3
$\begingroup$

I was wondering if anyone knew how the feature interaction strength is calculated in the catboost package. The documentation https://catboost.ai/docs/concepts/output-data_feature-analysis_feature-interaction-strength.html#output-data_feature-analysis_feature-interaction-strength__per-feature-interaction-strength does not explain exactly how it is calculated.

$\endgroup$
3
$\begingroup$

Feature interaction strength is stated here as: $\text{feature_strength} = \sum_{leaf s} | \sum_{f_1=f_2} \text{Leaf_Value} - \sum_{f_1!=f_2} \text{Leaf_Value} |$.

Decoding this: The value of the feature interaction strength for each pair of features $f_1$ and $f_2$ reflects the sum of absolute differences (after being summed across all trees) between the leaves of the tree containing the interaction $f_1:f_2$ and the leaves of the tree not containing the interaction of features $f_1:f_2$. Notice that this definition of feature interaction does not work if we have "stumps". At least one tree-learner of the ensemble is required to have at least two different features in its respective splits; if not, the term $\sum_{f_1=f_2} \text{Leaf_Value}$ will evaluate to NA.

The above mentioned methodology is a straightforward way of measuring interaction but unfortunately, none of the Catboost reference papers mentions anything formal on feature interactions (at the time of writing this answer). For a more authoritative/formal treatment of feature interactions in GBMs, I would strongly looking into the concept of $H$-statistic as proposed by Friedman and Popescu (2008) Predictive Learning via Rule Ensembles. This work takes the concept of partial dependency plots (from Friendman's earlier work (2001) Greedy function approximation: a gradient boosting machine) and generalises it. In short, it quantifies the change that the PDP of feature $x_j$ has when feature $x_i$ was included or not in the construction of $x_j$ PDP. Notice that the $H$-statistic becomes quickly quite expensive to evaluate as we really have to compute marginal distributions across numerous features-pairs. The Catboost approach should be extremely faster in comparison.

$\endgroup$
8
  • $\begingroup$ This was very helpful. Thank you. I was reading the documentation and it states that oblivious trees are used, meaning the same variable and split is used at every level of the tree. Therefore, I don't fully understand how we can look at the differences between the leaves within a tree, seeing as they would all have that interaction present. I have one other question. What exactly do you mean by "the differences between the leaves of a tree" ? $\endgroup$ – Niamh Belton Mar 10 '19 at 16:05
  • $\begingroup$ The difference between the values at the leaves of a tree. $\endgroup$ – usεr11852 Mar 10 '19 at 23:42
  • $\begingroup$ It’s still not clear to me. My interpretation of the formula would be, that it is the sum of absolute differences over all leafs with/without the interaction (globally, not per tree). Why do you think it is within a tree? $\endgroup$ – Peter Jul 4 '19 at 15:26
  • $\begingroup$ Apologies but as Catboost (once more) changed its documentation, so I cannot refer to you directly to a passage. That said, the formula shown is only applicable within a tree as it clearly does not contain any tree indices. In practice, Catboost, might made the summation (or a summation like procedure) across trees but that was not documented. $\endgroup$ – usεr11852 Jul 4 '19 at 16:27
  • $\begingroup$ Ok. Thanks, seams I need to follow the UTSL paradigm. $\endgroup$ – Peter Jul 5 '19 at 6:55

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.