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.