Learnability in Query and Restricted Distribution Models

我们将研究各种形式学习模型中函数类的可学习性。在Valiant PAC模型中，即使是简单的函数类的学习也有很多负面的结果。这项研究的目标之一是开发在其他学习模型中学习相对复杂的函数类的算法。一个相关的目标是确定其中一些学习模型的相对威力。还提出了研究函数类的可学习性、类的结构性质和涉及类的决策问题的复杂性之间的关系，以发现哪些函数类是可学习的，它们是通过什么方法学习的，以及它们的内在性质是什么使它们可以学习。

The learnability of classes of functions in various formal learning models will be studied. There have been many negative results on learning even simple classes of functions in the Valiant PAC model. One goal of this research is to develop algorithms for learning relatively complex classes of functions in other learning models. A related goal is to determine the relative power of some of these learning models. Also proposed is the study of the relation between learnability of a class of functions, structural properties of the class, and the complexity of decision problems involving the class, in order to discover which classes of functions are learnable, by what means they are learnable, and what inherent qualities make them learnable.