Quantifying Inductive Bias: AI Learning Algorithms and Valiant's Learning Framework

By David Haussler. 1988

How researchers see this paper

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

In Scaling & Learning Theory

Citations in the corpus

Deep Learning Scaling is Predictable, Empirically (2017, background): “Early theoretical work deﬁnes a framework for bounding generalization, but makes weak assumptions that cause the predicted generalization error to be very loose (Haussler (1988)).”
The Set Covering Machine (2003, methodology): “Therefore, Haussler (1988) has proposed to use this algorithm, on the remaining examples that are not used by the algorithm of Valiant, to reduce the number of features.”
A Survey of Methods for Scaling Up Inductive Algorithms (1999, background): “However, as Haussler points out, “by using a larger hypothesis space than is strictly necessary, it may be computationally easier to ﬁnd a consistent hypothesis : : : On the other hand, by using a larger hypothesis space : : : (more) examples will be required” (Haussler, 1988).”
Learning to Learn Using Gradient Descent (2001, background): “The use of previous learning experiences in inductive reasoning is known as “knowledge transfer” [4,1,14] or “inductive bias shifts” [15,6,12].”
Symplectic ODE-Net: Learning Hamiltonian Dynamics with Control (2019, methodology): “To learn underlying patterns from data and enable generalization beyond the training set, the learning approach incorporates appropriate inductive bias (Haussler, 1988; Baxter, 2000) by promoting representations which are simple in some sense.”
Occam's Two Razors: The Sharp and the Blunt (1998, background): “(In precise terms, higher-order model structures have a higher VC dimension (Haussler 1988); or, considering finiteprecision numbers, they literally contain more models.)”
On the Foundations of Noise-free Selective Classification (2010, background): “Theorem 35 (Haussler, 1988) Let F be any finite hypothesis class.”
A statistical approach to rule learning (2006, background): “It is well known that the greedy algorithm is a 1 + lnn approximation algorithm, that is, if the smallest consistent rule set contains s rules, then it generates at most s ∑n i=1 1 n ≤ s(1 + lnn) rules, where n is the number of positive instances (Vazirani, 2003; Haussler, 1988).”
Programming by Demonstration Using Version Space Algebra (2003, background): “PAClearningtheory(Valiant,1984;Haussler,1988;Kearns &Vazirani,1994)studiestheconditionsunderwhichareasonably-correctconceptcanbe learnedwithreasonableconﬁdence,orinotherwords,theconditionsunderwhichaconcept is probably approximately correct .”
Lower Bounds on Learning Decision Lists and Trees (1995, background): “The reduction from Set Covering to monomials is as follows [10].”