Exact Learning with Queries

学习理论关注的是在明确的可学性标准下对概念类进行严格的研究。目前的大多数研究都集中在扩展已知可学习的概念类的边界上。两种不同但相关的学习模型是可能近似正确（PAC）模型和具有等价性和成员查询的精确学习模型。这个项目的动机来自于最近在查询精确学习方面的研究结果，以及对有限数据进行推理的实际考虑。许多在密码学假设成立的情况下不能通过查询有效学习的概念类，在不考虑时间效率的模型中可能是完全可以学习的，但对有限数据的考虑是至关重要的。这样的模型是形式化的，并讨论了部分结果。这个项目的重点是重新研究自然概念类的可学习性，由于已知的负面结果而被忽视。在可能的情况下，根据精确和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.