论文标题
关于可能理论的可学习性
On the Learnability of Possibilistic Theories
论文作者
论文摘要
我们根据Angluin的精确学习模型研究了可能的理论的可学习性。我们考虑只有成员资格，仅等效性和两种查询的案例，才能由学习者提出。然后，我们表明，对于大量的问题，可以将经典逻辑的多项式时间可学习性结果转移到各自的可能性扩展中。特别是，从我们的结果来看，命题角理论的可能性扩展在多项式时期是可以学习的。由于精确模型中的多项式时间可学习性可以转移到经典的近似正确模型中，因此会员查询扩展了近似正确的模型，我们的工作还可以在此模型中建立此类结果。
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.
