Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks

• URL: http://arxiv.org/abs/2412.11205v1
• Date: Sun, 15 Dec 2024 14:37:56 GMT
• Title: Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks
• Authors: Elad Shohama, Hadar Cohena, Khalil Wattada, Havana Rikab, Dan Vilenchik,
• Abstract summary: We study concept learning for an existing graph neural networks (GNN) model trained to solve Boolean satisfiability (SAT) Our analysis reveals that the model learns key concepts matching those guiding human-designed SATs, particularly the notion of'support' We use the discovered concepts to "reverse-engineer" the black-box GNN and rewrite it as a white-box textbook algorithm.
• Score: 2.102973349909511
• License:
• Abstract: 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.

Related papers

• NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms [7.542220697870245]
  This study explores the intersection of neural networks and classical robotics algorithms through the Neural Algorithmic Reasoning framework. We propose a Graph Neural Network (GNN)-based learning framework, NAR-*ICP, which learns the intermediate algorithmic steps of classical ICP-based pointcloud registration algorithms. We evaluate our approach across diverse datasets, from real-world to synthetic, demonstrating its flexibility in handling complex and noisy inputs.
  arXiv  Detail & Related papers  (2024-10-14T19:33:46Z)
• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• Aligning Knowledge Graphs Provided by Humans and Generated from Neural Networks in Specific Tasks [5.791414814676125]
  This paper develops an innovative method that enables neural networks to generate and utilize knowledge graphs. Our approach eschews traditional dependencies on or word embedding models, mining concepts from neural networks and directly aligning them with human knowledge. Experiments show that our method consistently captures network-generated concepts that align closely with human knowledge and can even uncover new, useful concepts not previously identified by humans.
  arXiv  Detail & Related papers  (2024-04-23T20:33:17Z)
• Reasoning Algorithmically in Graph Neural Networks [1.8130068086063336]
  We aim to integrate the structured and rule-based reasoning of algorithms with adaptive learning capabilities of neural networks. This dissertation provides theoretical and practical contributions to this area of research.
  arXiv  Detail & Related papers  (2024-02-21T12:16:51Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Graph Neural Networks are Dynamic Programmers [0.0]
  Graph neural networks (GNNs) are claimed to align with dynamic programming (DP) Here we show, using methods from theory and abstract algebra, that there exists an intricate connection between GNNs and DP.
  arXiv  Detail & Related papers  (2022-03-29T13:27:28Z)
• Concept Embeddings for Fuzzy Logic Verification of Deep Neural Networks in Perception Tasks [1.2246649738388387]
  We present a simple, yet effective, approach to verify whether a trained convolutional neural network (CNN) respects specified symbolic background knowledge. The knowledge may consist of any fuzzy predicate logic rules. We show that this approach benefits from fuzziness and calibrating the concept outputs.
  arXiv  Detail & Related papers  (2022-01-03T10:35:47Z)
• Learning Structures for Deep Neural Networks [99.8331363309895]
  We propose to adopt the efficient coding principle, rooted in information theory and developed in computational neuroscience. We show that sparse coding can effectively maximize the entropy of the output signals. Our experiments on a public image classification dataset demonstrate that using the structure learned from scratch by our proposed algorithm, one can achieve a classification accuracy comparable to the best expert-designed structure.
  arXiv  Detail & Related papers  (2021-05-27T12:27:24Z)
• Reinforcement Learning with External Knowledge by using Logical Neural Networks [67.46162586940905]
  A recent neuro-symbolic framework called the Logical Neural Networks (LNNs) can simultaneously provide key-properties of both neural networks and symbolic logic. We propose an integrated method that enables model-free reinforcement learning from external knowledge sources.
  arXiv  Detail & Related papers  (2021-03-03T12:34:59Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.