Extending the Valiant Learning Model

Abstract

Valiant's formal model of concept learning has received some attention because of its strong performance guarantees. However, it has rarely been used in practice, in part because the known learnable concept classes are too restricted. Here I suggest two ways to avoid this problem. One explores the power gained by allowing the learner to experiment with its environment to some degree, rather than just passively view examples of the concept to be learned. It is shown that for a special case, no power is gained in the standard model, but a slightly different model does engender differences. The question of whether learning by experimentation is equivalent to learning from examples in the general case is an important open problem; if they are equivalent, the suitability of the Valiant model for capturing the function of experiments in science is called into question. The second extension considers a measure of the proximity of two concept classes, called density, that is defined to mesh with the learning model. It is shown that a concept close to the concept to be learned can be determined by viewing only a polynomial number of examples. Density also has wider applicability as a measure of the appropriateness of bias.