Complexity of Probabilistic Reasoning for Neurosymbolic Classification Techniques

Autor:	Ledaguenel, Arthur, Hudelot, Céline, Khouadjia, Mostepha
Rok vydání:	2024
Předmět:	Computer Science - Artificial Intelligence Computer Science - Computational Complexity Computer Science - Machine Learning Computer Science - Symbolic Computation
Druh dokumentu:	Working Paper
Popis:	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. A well known family of neurosymbolic techniques for informed classification use probabilistic reasoning to integrate this knowledge during learning, inference or both. Therefore, the asymptotic complexity of probabilistic reasoning is of cardinal importance to assess the scalability of such techniques. However, this topic is rarely tackled in the neurosymbolic literature, which can lead to a poor understanding of the limits of probabilistic neurosymbolic techniques. In this paper, we introduce a formalism for informed supervised classification tasks and techniques. We then build upon this formalism to define three abstract neurosymbolic techniques based on probabilistic reasoning. Finally, we show computational complexity results on several representation languages for prior knowledge commonly found in the neurosymbolic literature. Comment: 21 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2404.08404 Zobrazit plný text záznamu View this record from Arxiv