发现神经网络解逻辑题的关键概念，可用来改进算法并还原其原理。
Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks
- 通过主成分分析提取网络隐含的求解概念
- 发现模型学习到人类启发式中的'支持'概念，且可压缩为最小表示
- 适用于理解与优化图神经网络类算法，适合算法研究者
可解释人工智能方法通常聚焦于识别图像或文本分类任务中的关键输入特征或抽象概念。然而，在组合优化等算法任务中，这些概念不仅依赖输入，还取决于网络的当前状态，如图神经网络（GNN）的情况。本文研究了训练用于求解布尔可满足性（SAT）问题的现有GNN模型的概念学习。分析表明，该模型学习到了与人类设计的SAT启发式匹配的关键概念，尤其是‘支持’（support）概念。我们证明这些概念编码在嵌入协方差矩阵的前几个主成分（PCs）中，实现了无监督发现。利用稀疏PCA，我们验证了这些概念的最小性，并展示了通过简化GNN可实现教学。本框架有两个直接应用：(a) 改进经典WalkSAT算法的收敛速度；(b) 基于发现的概念对黑箱GNN进行逆向工程，重写为白盒教科书级算法。结果表明，概念学习在理解与提升组合优化类神经网络方面具有潜力。
原文摘要 · Abstract (English)
Explainable AI (XAI) methods typically focus on identifying essential input features or more abstract concepts for tasks like image or text classification. However, for algorithmic tasks like combinatorial optimization, these concepts may depend not only on the input but also on the current state of the network, like in the graph neural networks (GNN) case. This work studies concept learning for an existing GNN model trained to solve Boolean satisfiability (SAT). \textcolor{black}{Our analysis reveals that the model learns key concepts matching those guiding human-designed SAT heuristics, particularly the notion of 'support.' We demonstrate that these concepts are encoded in the top principal components (PCs) of the embedding's covariance matrix, allowing for unsupervised discovery. Using sparse PCA, we establish the minimality of these concepts and show their teachability through a simplified GNN. Two direct applications of our framework are (a) We improve the convergence time of the classical WalkSAT algorithm and (b) We use the discovered concepts to "reverse-engineer" the black-box GNN and rewrite it as a white-box textbook algorithm. Our results highlight the potential of concept learning in understanding and enhancing algorithmic neural networks for combinatorial optimization tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。