OC-space: a Unifying Perspective on Verification of Tree Ensembles

We study the problem of verifying whether certain properties such as robustness or fairness hold in an ensemble of decision trees. This problem is known to be NP-hard, with most research targeting a solution to a specific verification task. We explore the problem through the lens of an ensemble's OC-space: the set of all possible combinations of individual trees' predictions. This provides a unifying view that yields more a generic and flexible approach to verification. We show that a wide variety of existing verification tasks can be (1) framed as simple searches through OC-space, and (2) answered in time linear or quadratic in the size of the OC-space. Moreover, the search can be made more efficient by using spatial index structures. Interestingly, while the OC-space can grow exponentially with the ensemble's size, in practice it is often feasible to enumerate all output configurations. Empirically, we show that our generic approach can be faster than approaches targeting a single verification task.