为有限自动机的判断结果提供最小化解释，揭示关键输入字符。
A Formal Framework for the Explanation of Finite Automata Decisions
- 基于输入字符构造最小解释集，定位影响判定的关键特征。
- 可精确找出使输入被拒绝所需的最少字符修改。
- 适用于复杂自动机的可解释性分析，适合关注模型透明度的研究者。
有限自动机（FA）是计算机科学、语言学、生物学、电气工程和人工智能等领域中广泛应用的基本计算抽象。给定一个输入字符串，FA 会将其映射到有限结果集中的一个结果，例如“接受”或“拒绝”。然而，当结果产生时，人们常追问：为什么？又如何修改输入使其不再被接受？尽管自动机本身可视为行为解释，但其结构可能极为复杂，难以直接理解。本文研究如何基于输入字符串的字符来解释 FA 对特定输入的决策。核心目标是寻找最小解释：哪些输入字符共同决定了最终结果？需要做出怎样的最小改动才能改变结果？我们提出一种高效算法，能够识别任意给定输入下所有最小解释。该方法能提供无偏的因果解释，明确指出影响结果的关键输入特征。实验表明，该方法在复杂场景下仍具备良好可扩展性。
原文摘要 · Abstract (English)
Finite automata (FA) are a fundamental computational abstraction that is widely used in practice for various tasks in computer science, linguistics, biology, electrical engineering, and artificial intelligence. Given an input word, an FA maps the word to a result, in the simple case "accept" or "reject", but in general to one of a finite set of results. A question that then arises is: why? Another question is: how can we modify the input word so that it is no longer accepted? One may think that the automaton itself is an adequate explanation of its behaviour, but automata can be very complex and difficult to make sense of directly. In this work, we investigate how to explain the behaviour of an FA on an input word in terms of the word's characters. In particular, we are interested in minimal explanations: what is the minimal set of input characters that explains the result, and what are the minimal changes needed to alter the result? In this paper, we propose an efficient method to determine all minimal explanations for the behaviour of an FA on a particular word. This allows us to give unbiased explanations about which input features are responsible for the result. Experiments show that our approach scales well, even when the underlying problem is challenging.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。