On the Learnability of Possibilistic Theories
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1870-1876. https://doi.org/10.24963/ijcai.2020/259
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 (PAC) model extended with membership queries, our work also establishes such results in this model.
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Machine Learning: Learning Theory
Uncertainty in AI: Uncertainty Representations