ABSTRACT

The classical stochastic approximation methods are shown to yield algorithms to solve several formulations of the concept learning problem defined on the domain [0, l]d, Under some smoothness conditions on the probability measure functions, simple algorithms to solve some Probably and Approximately Correct (PAC) learning problems are proposed based on wavelet networks. Conditions for the asymptotic convergence of these algorithms as well as conditions on the sizes of the samples re­ quired to ensure the error bounds are derived using martingale inequalities. This chapter describes a framework for concept learning using wavelet networks,

The problem of inferring concepts, which are treated as abstract sets, from randomly generated positive and negative examples of the concept has been the focus of considerable research in the area of pattern recognition and machine learning. The paradigm of Probably and Approximately Correct (PAC) concept learn­ ing has attracted considerable attention over the past years since the pioneering works of Valiant [264], This paradigm is also in­

timately related to the method of empirical risk minimization and its application to the pattern recognition problem exten­ sively studied by Vapnik [265], Several basic results in PAC learning are existential in nature: informally, one of the main results states that any hypothesis that minimizes the empiri­ cal error, based on a sufficiently large sample, will approximate the underlying concept with a high probability. The problem of computing such a hypothesis could be of varying complexity; however, algorithms that can handle significant classes of such computing problems will be of both practical and theoretical interest. In this chapter, we illustrate that classical stochastic approximation algorithms can be used to solve an important class of PAC learning problems, where the hypotheses can be approximated by wavelet networks and the class of underlying probability measures satisfies some mild smoothness properties.