Oblivious PAC Learning of Concept Hierarchies

In this paper we introduce a new formal model of learning that extends the probably approximately correct (PAC) model to the study of learning inclusion hierarchies of concepts from random examples. From many separately learned hypothesis concepts, we wish to reconstruct any inclusions that hold among the corresponding target concepts.