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.

神经符号人工智能是一个不断发展的研究领域，旨在将神经网络学习能力与符号系统的推理能力相结合。知情多标签分类是神经符号人工智能的一个子领域，研究如何利用先前知识改进神经分类系统。该论文介绍了一个信息驱动的监督分类任务和技术的形式化描述，并基于概率推理构建了三种抽象的神经符号技术。最后，展示了神经符号文献中常见的先前知识的多种表示语言的计算复杂度结果。