PAC learning of concept classes through the boundaries of their items

AbstractWe present a new perspective for investigating the probably approximate correct (PAC) learnability of classes of concepts. We focus on special sets of points for characterizing the concepts within their class. This gives rise to a general notion of boundary of a concept, which holds even in discrete spaces, and to a special probability measuring technique. This technique is applied (i) to narrow the gap between the minimum and maximum sample sizes necessary to learn even under a more stringent learnability definition, and (ii) to get self-explanatory indices of the complexity of the learning task. These indices can be roughly estimated during the learning process and appear very useful in the treatment of nonsymbolic procedures, e.g. in the context of neutral networks