On the Learnability of Possibilistic Theories
Abstract
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.
Cite
Text
Persia and Ozaki. "On the Learnability of Possibilistic Theories." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/259Markdown
[Persia and Ozaki. "On the Learnability of Possibilistic Theories." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/persia2020ijcai-learnability/) doi:10.24963/IJCAI.2020/259BibTeX
@inproceedings{persia2020ijcai-learnability,
title = {{On the Learnability of Possibilistic Theories}},
author = {Persia, Cosimo and Ozaki, Ana},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1870-1876},
doi = {10.24963/IJCAI.2020/259},
url = {https://mlanthology.org/ijcai/2020/persia2020ijcai-learnability/}
}