Query learning models as a design tool for PAC models

Abstract

We show how query models can be used to get PACS and simple PAC learning results. First, we prove that any class learnable with membership and equivalence queries is also learnable  in the PACS model. Then, we propose and study two models of query learning in which there is a probability distribution on the instance space. One can get simple PAC learning results considering these models under the universal distribution. We give several applications.