Project-Based Learning
- PDF / 2,533,176 Bytes
- 196 Pages / 547.087 x 737.008 pts Page_size
- 39 Downloads / 182 Views
Synonyms Probably approximately correct theory; Statistical learning theory
Definition The Probably Approximately Correct (PAC) learning theory, first proposed by L. Valiant (Valiant 1984), is a statistical framework for learning a task using a set of training data. In its simplest form and for a typical modeling task, the PAC learning theory attempts to relate the accuracy and statistical confidence of the model to the number of training examples used. Next, a more detailed formulation of the PAC learning is provided. For learning an unknown function f: X ! [0 1] in F, where F is a family of functions, an algorithm A is used to form a hypothesis or model hn: X ! [0 1]. The function hn is an approximation of f formed by A using n training examples. Then, in order to assess the quality of the learning/approximation process, it is desirable to ensure with the statistical confidence of 1 d that the true distance between f and hn over the entire space, i.e. dp(f, hn) is less than the accuracy factor of e, i.e. sup Pr dp ðf ; hn Þ e ð1 dÞ ð1Þ f eF
In Eq. 1 P is the probability distribution of the data. If for any e, a d can be found such that the above inequality is satisfied, the conditions for PAC learning are satisfied. Equation 1 describes the logic behind the naming of this theory; if the above equation is satisfied for some small e and d, then it is highly “probable” that hn provides a “correct approximation” of f.
Theoretical Background The typical outcome of the PAC learning formulation of a learning task is an equality that provides either of the following: (a) Bounds on the number of training examples in order to provide pre-specified levels of accuracy or statistical confidence over the resulting model. (b) Given a fixed number of training examples, the possible trade-off between the accuracy and the statistical confidence of the learning process. (c) When comparing a set of different learning tasks, the relative complexity of these learning tasks. Such a comparison can be made assuming the same values of both accuracy and statistical confidence, and regarding the number of training examples as the complexity factor. The complexity factor is referred to as “sample complexity.” It has to be mentioned that there is no guarantee that a function f in F is even learnable in the PAC learning sense. The literature of PAC learning theory in the last few decades provides a variety of learning tasks that are PAC learnable and also some that are not PAC learnable. Furthermore, among those learning tasks that are PAC learning, the sample complexity for the algorithm used for the learning task can be very different (Vidyasagar); some algorithms applied for the same learning task can result to much higher sample complexity than others. Moreover, using the same algorithm for learning of an unknown function belonging to another family of functions results to different levels of sample complexity. While some of the original learning tasks addressed by the PAC learning were families of Boolean functions and deci
Data Loading...
