验证神经网络提取规则的正确性与完备性
Checking extracted rules in Neural Networks
- 从复杂性理论角度分析规则验证问题，针对ReLU和布尔网络
- 发现多数规则验证问题属于co-NP完全，计算难度高
- 揭示启发式规则提取结果的可信度风险，适合理论研究者
本文从复杂性理论视角研究神经网络提取规则的形式化验证问题。规则是描述网络输入空间大范围行为的全局性质或模式，通过算法从网络中提取以增进对模型内部机制的理解。本文聚焦三个核心问题：给定规则集是否适用于目标网络？规则集是否自洽无矛盾？规则集是否覆盖所有输入、具备完备性？尽管过去30年已有大量规则提取方法研究，但尚未有针对其验证的系统工作。许多提取方法依赖随机性启发式与过度近似，其结果可信度存疑。本文对带有ReLU激活函数的神经网络及布尔网络，研究多种规则类型的验证问题，证明这些问题可相互归约，并表明多数问题为co-NP完全，具有高计算复杂性。
原文摘要 · Abstract (English)
In this paper we investigate formal verification of extracted rules for Neural Networks under a complexity theoretic point of view. A rule is a global property or a pattern concerning a large portion of the input space of a network. These rules are algorithmically extracted from networks in an effort to better understand their inner way of working. Here, three problems will be in the focus: Does a given set of rules apply to a given network? Is a given set of rules consistent or do the rules contradict themselves? Is a given set of rules exhaustive in the sense that for every input the output is determined? Finding algorithms that extract such rules out of networks has been investigated over the last 30 years, however, to the author's current knowledge, no attempt in verification was made until now. A lot of attempts of extracting rules use heuristics involving randomness and over-approximation, so it might be beneficial to know whether knowledge obtained in that way can actually be trusted. We investigate the above questions for neural networks with ReLU-activation as well as for Boolean networks, each for several types of rules. We demonstrate how these problems can be reduced to each other and show that most of them are co-NP-complete.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。