Exact Learning with Queries

学习理论关注的是在既定的可学习标准下对概念类进行严格的研究。目前的大多数研究都集中在拓展已知可学习的概念类的边界上。两种不同但相关的学习模型是可能近似正确(PAC)模型和带有等价和成员查询的精确学习模型。该项目的动机来自于最近在通过查询进行准确学习方面的结果，以及对可用于推理的有限数据的实际考虑。如果密码假设成立，则不能通过查询有效学习的许多概念类可能在放松了对时间效率的考虑，但将有限数据的考虑放在首位的模型中是完全可以学习的。这样的模型是形式化的，并讨论了部分结果。本课题致力于重新研究自然概念类的可学性，这些概念类由于已知的负面结果而被忽视。在可能的情况下，根据Exact和PAC准则开发有效的学习算法。

Learning theory is concerned with the rigorous study of concept classes under well- established criteria for learnability. Most of the current research focuses on expanding the frontiers of the concept classes known to be learnable. Two different but related models for learning are the probably approximately correct (PAC) model and the exact learning model with equivalence and membership queries. This project derives its motivation from recent results in exact learning with queries and from practical considerations of limited data available for inference. Many concept classes which are not efficiently learnable with queries if cryptographic assumptions hold are possibly exactly learnable in a model where considerations of time-efficiency are relaxed, but considerations of limited data are made paramount. Such a model is formalized along with a discussion of partial results. This project concentrates on the reinvestigation of the learnability of natural concept classes which have been neglected in view of known negative results. Where possible, efficient learning algorithms are developed according to both exact and PAC criteria.