A concept is a subset of a finite domain. We want to bind the number of questions that have to be asked in order to identify a concept that comes from a known concept class. These bounds depend on which kinds of questions can be asked. One can allow membership questions (“Is x in the concept?”) or equivalence questions (“Is C the concept?”). These are answered either affirmatively, or by a counter example. One can also allow both membership and equivalence questions.
Various kinds of dimension are used to organize the ingenious learning algorithms that have been used to establish various lower and upper bounds. Among other concepts, this paper describes how membership questions are related to yes-no tests, so some of these learning algorithms can be used to identify unknown items, for example, binary tests on a patient to determine his or her disease.
This tutorial on learning finite concepts is welcome; it fills a gap in the literature.