Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications

By David Haussler. 1992

We describe a generalization of the PAC learning model that is based on statistical decision theory. In this model the learner receives randomly drawn examples, each example consisting of an instance x in X and an outcome y in Y , and tries to find a hypothesis h : X --< A , where h in H , that specifies the appropriate action a in A to take for each instance x , in order to minimize the expectation of a loss l(y,a). Here X, Y, and A are arbitrary sets, l is a real-valued function, and examples are generated according to an arbitrary joint distribution on X times Y . Special cases include the problem of learning a function from X into Y , the problem of learning the conditional probability distribution on Y given X (regression), and the problem of learning a distribution on X (density estimation). We give theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H , and show how this implies learnability with bounded sample size, disregarding computational complexity. As an application, we give distribution-independent upper bounds on the sample size needed for learning with feedforward neural networks. Our theorems use a generalized notion of VC dimension that applies to classes of real-valued functions, adapted from Pollard''s work, and a notion of *capacity* and *metric dimension* for classes of functions that map into a bounded metric space. (Supersedes 89-30 and 90-52.) [Also in "Information and Computation", Vol. 100, No.1, September 1992]

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Wireless Network Intelligence at the Edge (2018, background): “All terms in (8) depend on the NN’s hypothesis h ∈ H with the entire hypothesis space H [132].”
A Model of Inductive Bias Learning (2000, methodology): “The bound onm in Theorem 8 states thatmn should beO(nk +W ), or proportional to the total number of parameters in the network, a result we would expect from6 (Haussler, 1992).”
Local Rademacher complexities (2005, methodology): “results of Vapnik and Chervonenkis based on weighting [35] are restricted to classes of nonnegative functions. Also, most previous results, such as those of Pollard [28], van de Geer [32] or Haussler [13], give complexity terms that involve “global” measures of complexity of the class, such as cover”
Calibration for the (Computationally-Identifiable) Masses (2017, background): “We show a strong connection between the complexity of learning a multicalibrated predictor and agnostic learning [Hau92, KSS94].”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “Given hypothesis class H ⊂ X → Y , its Natarajan dimension Ndim ( H ) is deﬁned as the maximum cardinality of a set A ⊆ X that satisﬁes the following: there exists Deﬁnition 7 (Pseudo dimension [Haussler, 1992]) .”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “In this study, we adopt the stronger notion of learnability considered in Shalev-Shwartz et al. (2010), which is a direct generalization of PAC-learnability (Valiant, 1984) and agnostic PAC-learnability (Kearns et al., 1992) to the General Learning Setting as studied by Haussler (1992).”
Training Mixture Models at Scale via Coresets (2017, methodology): “Approximation algorithms in computational geometry often make use of random sampling, feature extraction, and ε-samples (Haussler, 1992).”
The Racing Algorithm: Model Selection for Lazy Learners (1997, background): “This is clearly a worst case assumption, and most PAC bounds are made tighter by leveraging this point (Haussler 1992).”
ESTIMATING THE APPROXIMATION ERROR IN LEARNING THEORY (2003, background): “…is de(cid:12)ned as E ( f R ) and is equal to The approximation error decreases as R becomes larger, and The sample error of a function Thus, the error X ( f z − f (cid:26) ) 2 can be decomposed as The sample error has been extensively investigated in statistical learning theory [3 ; 6 ; 9 ; 12].”
Neural Networks for Control (1993, background): “Other results on finiteness of learning, but from a more statistical viewpoint (nonlinear regression, estimation of joint densities), are given in [17], where metric entropy estimates are obtained for networks with bounded weights.”
Reliably Learning the ReLU in Polynomial Time (2016, background): “The first is the standard agnostic learning model [14, 20] and the second is a generalization of the reliable agnostic learning framework [18].”
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity (2014, methodology): “In this work we consider learning in PAC [Valiant, 1984] and agnostic [Haussler, 1992, Kearns et al., 1994] learning models by differentially-private algorithms.”
Scalable Training of Mixture Models via Coresets (2011, background): “Approximation algorithms in computational geometry often make use of random sampling, feature extraction, and -samples [20].”
Is your dataset big enough? Sample size requirements when using artificial neural networks for discrete choice analysis (2018, methodology): “…mathematical framework for studying data requirements, they have led to hardly any application in practice due to the prohibitive di ﬃ culty of mean-ingfully quantifying the VC dimension for complex learning models such as ANNs (Anthony and Bartlett, 2009; Blumer et al., 1989; Haussler, 1992a).”
Learning with Annotation Noise (2009, background): “…annotation noise as defined here is qualitatively different from more malicious types of noise analyzed in the agnostic learning framework (Kearns and Li, 1988; Haussler, 1992; Kearns et al., 1994), where an adver- sary can not only choose the placement of the hard cases, but also their labels.”
Understanding Machine Learning: From Theory to Algorithms (2014, background): “The relation to the definition of PAC learnability is due to Blumer, Ehrenfeucht, Haussler & Warmuth (1989). Several generalizations of the VC-dimension have been proposed.”