A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniques

• URL: http://arxiv.org/abs/2404.08404v2
• Date: Thu, 23 Jan 2025 09:52:48 GMT
• Title: A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniques
• Authors: Arthur Ledaguenel, Céline Hudelot, Mostepha Khouadjia,
• Abstract summary: We develop a unified formalism for four probabilistic reasoning problems. Then, we compile several known and new tractability results into a single complexity map of probabilistic reasoning. We build on this complexity map to characterize the domains of scalability of several techniques.
• Score: 6.775534755081169
• License:
• Abstract: Neurosymbolic artificial intelligence is a growing field of research aiming to combine neural network learning capabilities with the reasoning abilities of symbolic systems. Informed multi-label classification is a sub-field of neurosymbolic AI which studies how to leverage prior knowledge to improve neural classification systems. Recently, a family of neurosymbolic techniques for informed classification based on probabilistic reasoning has gained significant traction. Unfortunately, depending on the language used to represent prior knowledge, solving certain probabilistic reasoning problems can become prohibitively hard when the number of classes increases. Therefore, the asymptotic complexity of probabilistic reasoning is of cardinal importance to assess the scalability of such techniques. In this paper, we develop a unified formalism for four probabilistic reasoning problems. Then, we compile several known and new tractability results into a single complexity map of probabilistic reasoning. We build on top of this complexity map to characterize the domains of scalability of several techniques. We hope this work will help neurosymbolic AI practitioners navigate the scalability landscape of probabilistic neurosymbolic techniques.

Related papers

• A Scalable Approach to Probabilistic Neuro-Symbolic Verification [14.558484523699748]
  Neuro-Symbolic Artificial Intelligence (NeSy AI) has emerged as a promising direction for integrating neural learning with symbolic reasoning. We address the problem of formally verifying the robustness of such NeSy probabilistic reasoning systems. We propose the first approach for approximate, relaxation-based verification of probabilistic NeSy systems.
  arXiv  Detail & Related papers  (2025-02-05T15:29:41Z)
• Compositional Generalization Across Distributional Shifts with Sparse Tree Operations [77.5742801509364]
  We introduce a unified neurosymbolic architecture called the Differentiable Tree Machine. We significantly increase the model's efficiency through the use of sparse vector representations of symbolic structures. We enable its application beyond the restricted set of tree2tree problems to the more general class of seq2seq problems.
  arXiv  Detail & Related papers  (2024-12-18T17:20:19Z)
• Formal Explanations for Neuro-Symbolic AI [28.358183683756028]
  This paper proposes a formal approach to explaining the decisions of neuro-symbolic systems. It first computes a formal explanation for the symbolic component of the system, which serves to identify a subset of the individual parts of neural information that needs to be explained. This is followed by explaining only those individual neural inputs, independently of each other, which facilitates succinctness of hierarchical formal explanations.
  arXiv  Detail & Related papers  (2024-10-18T07:08:31Z)
• Towards Efficient Neuro-Symbolic AI: From Workload Characterization to Hardware Architecture [22.274696991107206]
  Neuro-symbolic AI emerges as a promising paradigm, fusing neural and symbolic approaches to enhance interpretability, robustness, and trustworthiness. Recent neuro-symbolic systems have demonstrated great potential in collaborative human-AI scenarios with reasoning and cognitive capabilities. We first systematically categorize neuro-symbolic AI algorithms, and then experimentally evaluate and analyze them in terms of runtime, memory, computational operators, sparsity, and system characteristics.
  arXiv  Detail & Related papers  (2024-09-20T01:32:14Z)
• Improving Neural-based Classification with Logical Background Knowledge [0.0]
  We propose a new formalism for supervised multi-label classification with propositional background knowledge. We introduce a new neurosymbolic technique called semantic conditioning at inference. We discuss its theoritical and practical advantages over two other popular neurosymbolic techniques.
  arXiv  Detail & Related papers  (2024-02-20T14:01:26Z)
• Brain-Inspired Machine Intelligence: A Survey of Neurobiologically-Plausible Credit Assignment [65.268245109828]
  We examine algorithms for conducting credit assignment in artificial neural networks that are inspired or motivated by neurobiology. We organize the ever-growing set of brain-inspired learning schemes into six general families and consider these in the context of backpropagation of errors. The results of this review are meant to encourage future developments in neuro-mimetic systems and their constituent learning processes.
  arXiv  Detail & Related papers  (2023-12-01T05:20:57Z)
• Knowledge-based Analogical Reasoning in Neuro-symbolic Latent Spaces [20.260546238369205]
  We propose a framework that combines the pattern recognition abilities of neural networks with symbolic reasoning and background knowledge. We take inspiration from the 'neural algorithmic reasoning' approach [DeepMind 2020] and use problem-specific background knowledge. We test this on visual analogy problems in RAVENs Progressive Matrices, and achieve accuracy competitive with human performance.
  arXiv  Detail & Related papers  (2022-09-19T04:03:20Z)
• Neuro-Symbolic Learning of Answer Set Programs from Raw Data [54.56905063752427]
  Neuro-Symbolic AI aims to combine interpretability of symbolic techniques with the ability of deep learning to learn from raw data. We introduce Neuro-Symbolic Inductive Learner (NSIL), an approach that trains a general neural network to extract latent concepts from raw data. NSIL learns expressive knowledge, solves computationally complex problems, and achieves state-of-the-art performance in terms of accuracy and data efficiency.
  arXiv  Detail & Related papers  (2022-05-25T12:41:59Z)
• Neurocompositional computing: From the Central Paradox of Cognition to a new generation of AI systems [120.297940190903]
  Recent progress in AI has resulted from the use of limited forms of neurocompositional computing. New, deeper forms of neurocompositional computing create AI systems that are more robust, accurate, and comprehensible.
  arXiv  Detail & Related papers  (2022-05-02T18:00:10Z)
• The Causal Neural Connection: Expressiveness, Learnability, and Inference [125.57815987218756]
  An object called structural causal model (SCM) represents a collection of mechanisms and sources of random variation of the system under investigation. In this paper, we show that the causal hierarchy theorem (Thm. 1, Bareinboim et al., 2020) still holds for neural models. We introduce a special type of SCM called a neural causal model (NCM), and formalize a new type of inductive bias to encode structural constraints necessary for performing causal inferences.
  arXiv  Detail & Related papers  (2021-07-02T01:55:18Z)
• Neuro-symbolic Neurodegenerative Disease Modeling as Probabilistic Programmed Deep Kernels [93.58854458951431]
  We present a probabilistic programmed deep kernel learning approach to personalized, predictive modeling of neurodegenerative diseases. Our analysis considers a spectrum of neural and symbolic machine learning approaches. We run evaluations on the problem of Alzheimer's disease prediction, yielding results that surpass deep learning.
  arXiv  Detail & Related papers  (2020-09-16T15:16:03Z)

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.