arXiv:2607.06407cs.AI2026-07

提出可统一表达多种解释的声明式查询语言,让模型解释更规范高效。

ExplAIner: A Declarative Query Language for Explaining Classification Models

论文配图:ExplAIner: A Declarative Query Language for Explaining Classification Models
图 1 · 摘自论文原文
  • 基于FOIL扩展词汇与分层结构,支持多种解释类型
  • 复杂度可控:固定查询仅需有限次调用SAT求解器
  • 适合形式化XAI研究者,尤其关注模型解释的自动化计算

XAI领域已有大量解释查询与评分方法。从数据管理视角看,这些多样化的解释概念亟需一种声明式查询语言来统一表达、组合与分析。本文针对布尔模型构建此类框架。首先回顾了用于黑箱模型的可解释性查询语言FOIL,发现其存在两大根本缺陷:无法表达基于最优性的核心解释查询,且在决策树上的评估问题属于多项式层级中每一层的难解问题。随后提出ExplAIner,基于FOIL扩展词汇并采用分层结构,能表达包括溯因、对比、特征与距离在内的广泛解释概念。证明了在每类布尔模型中,只要基本谓词可多项式评估,则ExplAIner中任意查询的评估问题属于布尔层级。该性质对确定性与可分解布尔电路成立。最后引入Opt-FOIL,即以优化为导向的ExplAIner片段,用于计算在严格偏序下最小化的解释,并证明其评估问题在相同可处理假设下属于$\mathrm{FP}^{\mathrm{NP}}$。这一复杂度结果带来直接算法意义:固定ExplAIner查询只需固定次数调用SAT求解器,而Opt-FOIL中定义的解释可经多项式次数调用求解。这在形式化XAI中尤为关键,因SAT求解器已被成功用于多类机器学习模型的解释计算。

原文摘要 · Abstract (English)

The XAI community has studied a wide range of queries and scores for explaining predictions of ML models. From a data management perspective, this proliferation of explanation notions calls for declarative query languages in which such notions can be specified, combined, and analyzed uniformly. In this paper, we develop such a framework for Boolean models. We first revisit FOIL, an interpretability query language for black-box models, and show that it has two fundamental limitations: it cannot express central optimality-based explanation queries, and its evaluation problem over decision trees is hard for every level of the polynomial hierarchy. We then introduce ExplAIner, a query language based on FOIL with an extended vocabulary and a layered structure. We show that ExplAIner can express a broad family of explanation notions, including abductive, contrastive, feature-based, and distance-based queries. We also prove that the evaluation problem for each query in ExplAIner belongs to the Boolean hierarchy over every class of Boolean models for which some basic predicates can be evaluated in polynomial time. In particular, that property holds for deterministic and decomposable Boolean circuits. Finally, we introduce Opt-FOIL, an optimization-oriented fragment of ExplAIner for computing explanations that are minimal with respect to strict partial orders, and prove that its evaluation problem is in $\mathrm{FP}^{\mathrm{NP}}$ under the same tractability assumptions. These complexity results have a direct algorithmic consequence: a fixed ExplAIner query can be evaluated with a fixed number of calls to a SAT solver, while a notion of explanation specified in Opt-FOIL can be computed with a polynomial number of such calls. This is particularly relevant in formal XAI, where SAT solvers have been successfully used to compute explanations for several classes of ML models.

可解释性查询语言形式化推理SAT求解

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。