发现决策树集成模型中的输入扰动敏感问题，影响AI决策可靠性。
Glitches in Decision Tree Ensemble Models
- 定义并检测输入空间中输出剧烈震荡的'漏洞'（glitches）
- 证明检测漏洞在深度4的树集合中为NP完全问题
- 提出基于MILP的算法，在真实数据集上有效搜索漏洞
许多关键决策任务已交由机器学习模型处理，确保其决策可信、可靠且对相似输入输出一致至关重要。本文识别出一种新型不可靠行为——‘漏洞’（glitches），可能严重损害具有陡峭决策边界的AI模型可靠性。大致而言，漏洞是输入空间中极小邻域，在其中模型输出会随输入微小变化而剧烈振荡。我们给出了漏洞的形式化定义，并利用文献中的经典模型与数据集证明其普遍存在，且通常指示模型在该区域存在潜在不一致性。随后，我们针对广泛应用的梯度提升决策树（GBDT）模型开展漏洞的算法搜索。证明了在树集合中检测漏洞的问题，即使对于深度为4的树也属于NP完全问题。所提出的漏洞搜索算法采用MILP编码，其在文献中广泛使用的多个GBDT基准测试中展现出有效性与计算可行性。
原文摘要 · Abstract (English)
Many critical decision-making tasks are now delegated to machine-learned models, and it is imperative that their decisions are trustworthy and reliable, and their outputs are consistent across similar inputs. We identify a new source of unreliable behaviors-called glitches-which may significantly impair the reliability of AI models having steep decision boundaries. Roughly speaking, glitches are small neighborhoods in the input space where the model's output abruptly oscillates with respect to small changes in the input. We provide a formal definition of glitches, and use well-known models and datasets from the literature to demonstrate that they have widespread existence and argue they usually indicate potential model inconsistencies in the neighborhood of where they are found. We proceed to the algorithmic search of glitches for widely used gradient-boosted decision tree (GBDT) models. We prove that the problem of detecting glitches is NP-complete for tree ensembles, already for trees of depth 4. Our glitch-search algorithm for GBDT models uses an MILP encoding of the problem, and its effectiveness and computational feasibility are demonstrated on a set of widely used GBDT benchmarks taken from the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。