Complexity of Probabilistic Reasoning for Neurosymbolic Classification
  Techniques
Arthur Ledaguenel Céline Hudelot Mostepha Khouadjia
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.