Verifying Glitches in Decision Tree Ensembles
Satyankar Chandra, Harsh Chaurasia, Ashutosh Gupta, Kaushik Mallik, Krishna Shankaranarayanan, Namrita Varshney
Decision tree ensembles are widely used for tabular prediction tasks in judiciary, healthcare, banking, etc. We show that the piecewise-constant structure of these models can create narrow local oscillations, leading the ensemble score to sharply drop and then rise (a downward spike), or sharply rise and then drop (an upward spike), over a small change in a single feature. We call such patterns glitches. A glitch is not, by definition, an error. Rather, it is a formally checkable audit target requiring inspection. Formally, glitches are witnessed by ordered input triples in which a small monotonic change in a single input feature causes the output to first change in one direction and then revert in the opposite direction. Through a substantial experimental study, we show that glitches have widespread existence in even the state-of-the-art models performing various critical tasks. Our findings also indicate that glitches enrich and extend existing notions like robustness and monotonicity, providing us a more refined tool to isolate anomalies for inspection. On the theoretical side, we prove that deciding whether a decision tree ensemble contains a glitch is NP-complete, even for bounded-depth trees. We then present a mixed-integer linear programming encoding for the global and local glitch verification problems, and implement our algorithm in a verifier for gradient-boosted decision trees. Experiments show our verifier can scale to realistic model sizes from the literature.
尚无 AI 解读，展示原文摘要