Extending the Valiant Learning Model

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