TreePII: Efficient Computation of Higher-Order Probabilistic Interaction Indices in Tree Ensembles

While higher-order interaction indices offer deep insights into the synergies and redundancies within tree ensembles, their exact computation is hindered by combinatorial bottlenecks. Recent advancements efficiently compute symmetric interactions, but struggle to scale for asymmetric Probabilistic Interaction Indices (PIIs), which are crucial for advanced tasks such as incorporating feature hierarchy structures. To bridge this gap, we introduce TreePII, a novel algorithm that computes exact, any-order PIIs by integrating the partial derivatives of multilinear extension using interpolatory quadrature. TreePII effectively bypasses traditional computational hurdles, demonstrating both theoretical and empirical improvements over existing baselines and opening new avenues for scalable analysis of tree ensembles.