On the Learnability of Possibilistic Theories
This work provides theoretical learnability guarantees for possibilistic logic systems, which are important for AI applications involving uncertainty and incomplete information.
The paper investigates whether possibilistic theories can be learned from entailments using Angluin's exact learning model, showing that polynomial-time learnability results from classical logic transfer to possibilistic extensions for a large class of problems, including propositional Horn theories.
We investigate learnability of possibilistic theories from entailments in light of Angluin's exact learning model. We consider cases in which only membership, only equivalence, and both kinds of queries can be posed by the learner. We then show that, for a large class of problems, polynomial time learnability results for classical logic can be transferred to the respective possibilistic extension. In particular, it follows from our results that the possibilistic extension of propositional Horn theories is exactly learnable in polynomial time. As polynomial time learnability in the exact model is transferable to the classical probably approximately correct model extended with membership queries, our work also establishes such results in this model.