Arrow Research search

Author name cluster

David Haussler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

NeurIPS Conference 1998 Conference Paper

Exploiting Generative Models in Discriminative Classifiers

  • Tommi Jaakkola
  • David Haussler

Generative probability models such as hidden ~larkov models pro(cid: 173) vide a principled way of treating missing information and dealing with variable length sequences. On the other hand, discriminative methods such as support vector machines enable us to construct flexible decision boundaries and often result in classification per(cid: 173) formance superior to that of the model based approaches. An ideal classifier should combine these two complementary approaches. In this paper, we develop a natural way of achieving this combina(cid: 173) tion by deriving kernel functions for use in discriminative methods such as support vector machines from generative probability mod(cid: 173) els. We provide a theoretical justification for this combination as well as demonstrate a substantial improvement in the classification performance in the context of D~A and protein sequence analysis.

PDF Details

FOCS Conference 1993 Conference Paper

Scale-sensitive Dimensions, Uniform Convergence, and Learnability

  • Noga Alon
  • Shai Ben-David
  • Nicolò Cesa-Bianchi
  • David Haussler

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Gliveako-Cantelli classes. In this paper we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class. >

Details

I&C Journal 1992 Journal Article

Decision theoretic generalizations of the PAC model for neural net and other learning applications

  • David Haussler

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 ∈ X and an outcome y ∈ Y, and tries to find a decision rule h: X → A, where h ∈ H, that specifies the appropriate action a ∈ 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 × 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 decision rule 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 Vapnik and Pollard's work, and a notion of capacity and metric dimension for classes of functions that map into a bounded metric space.

Details DOI

I&C Journal 1991 Journal Article

Equivalence of models for polynomial learnability

  • David Haussler
  • Michael Kearns
  • Nick Littlestone
  • Manfred K. Warmuth

In this paper we consider several variants of Valiant's learnability model that have appeared in the literature. We give conditions under which these models are equivalent in terms of the polynomially learnable concept classes they define. These equivalences allow comparisons of most of the existing theorems in Valiant-style learnability and show that several simplifying assumptions on polynomial learning algorithms can be made without loss of generality. We also give a useful reduction of learning problems to the problem of finding consistent hypotheses, and give comparisons and equivalences between Valiant's model and the prediction learning models of Haussler, Littlestone, and Warmuth (in “29th Annual IEEE Symposium on Foundations of Computer Science, ” 1988).

Details DOI

NeurIPS Conference 1991 Conference Paper

Unsupervised learning of distributions on binary vectors using two layer networks

  • Yoav Freund
  • David Haussler

We study a particular type of Boltzmann machine with a bipartite graph structure called a harmo(cid: 173) nium. Our interest is in using such a machine to model a probability distribution on binary input vectors. We analyze the class of probability distributions that can be modeled by such machines. showing that for each n ~ 1 this class includes arbitrarily good appwximations to any distribution on the set of all n-vectors of binary inputs. We then present two learning algorithms for these machines. . The first learning algorithm is the standard gradient ascent heuristic for computing maximum likelihood estimates for the parameters (i. e. weights and thresholds) of the modeL Here we give a closed form for this gradient that is significantly easier to compute than the corresponding gradient for the general Boltzmann machine. The second learning algorithm is a greedy method that creates the hidden units and computes their weights one at a time. This method is a variant of the standard method for projection pursuit density estimation. We give experimental results for these learning methods on synthetic data and natural data from the domain of handwritten digits.

PDF Details

I&C Journal 1989 Journal Article

A general lower bound on the number of examples needed for learning

  • Andrzej Ehrenfeucht
  • David Haussler
  • Michael Kearns
  • Leslie Valiant

We prove a lower bound of Ω((1/ɛ)ln(1/δ)+VCdim(C)/ɛ) on the number of random examples required for distribution-free learning of a concept class C, where VCdim(C) is the Vapnik-Chervonenkis dimension and ɛ and δ are the accuracy and confidence parameters. This improves the previous best lower bound of Ω((1/ɛ)ln(1/δ)+VCdim(C)) and comes close to the known general upper bound of O((1/ɛ)ln(1/δ)+(VCdim(C)/ɛ)ln(1/ɛ)) for consistent algorithms. We show that for many interesting concept classes, including kCNF and kDNF, our bound is actually tight to within a constant factor.

Details DOI

FOCS Conference 1989 Conference Paper

Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results

  • David Haussler

The probably approximately correct (PAC) model of learning from examples is generalized. The problem of learning functions from a set X into a set Y is considered, assuming only that the examples are generated by independent draws according to an unknown probability measure on X*Y. The learner's goal is to find a function in a given hypothesis space of functions from X into Y that on average give Y values that are close to those observed in random examples. The discrepancy is measured by a bounded real-valued loss function. The average loss is called the error of the hypothesis. A theorem on the uniform convergence of empirical error estimates to true error rates is given for certain hypothesis spaces, and it is shown how this implies learnability. A generalized notion of VC dimension that applies to classes of real-valued functions and a notion of capacity for classes of functions that map into a bounded metric space are given. These measures are used to bound the rate of convergence of empirical error estimates to true error rates, giving bounds on the sample size needed for learning using hypotheses in these classes. As an application, a distribution-independent uniform convergence result for certain classes of functions computed by feedforward neural nets is obtained. Distribution-specific uniform convergence results for classes of functions that are uniformly continuous on average are also obtained. >

Details

I&C Journal 1989 Journal Article

Learning decision trees from random examples

  • Andrzej Ehrenfeucht
  • David Haussler

We define the rank of a decision tree and show that for any fixed r, the class of all decision trees of rank at most r on n Boolean variables is learnable from random examples in time polynomial in n and linear in 1/ɛ and log(1/δ), where ɛ is the accuracy parameter and δ is the confidence parameter. Using a suitable encoding of variables, Rivest's polynomial learnability result for decision lists can be interpreted as a special case of this result for rank 1. As another corollary, we show that decision trees on n Boolean variables of size polynomial in n are learnable from random examples in time linear in n O(logn), 1/ɛ, and log(1/δ). As a third corollary, we show that Boolean functions that have polynomial size DNF expressions for both their positive and their negative instances are learnable from random examples in time linear in n O((logn)2), 1/ɛ, and log(1/δ).

Details DOI

FOCS Conference 1988 Conference Paper

Predicting {0, 1}-Functions on Randomly Drawn Points (Extended Abstract)

  • David Haussler
  • Nick Littlestone
  • Manfred K. Warmuth

The authors consider the problem of predicting (0, 1)-valued functions on R/sup n/ and smaller domains, based on their values on randomly drawn points. Their model is related to L. G. Valiant's learnability model (1984), but does not require the hypotheses used for prediction to be represented in any specified form. The authors first disregard computational complexity and show how to construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions. These prediction strategies use the 1-inclusion graph structure from N. Alon et al. 's work on geometric range queries (1987) to minimize the probability of incorrect prediction. They then turn to computationally efficient algorithms. For indicator functions of axis-parallel rectangles and halfspaces in R/sup n/, they demonstrate how their techniques can be applied to construct computational efficient prediction strategies that are optimal to within a constant factor. They compare the general performance of prediction strategies derived by their method to those derived from existing methods in Valiant's learnability theory. >

Details

AIJ Journal 1988 Journal Article

Quantifying inductive bias: AI learning algorithms and Valiant's learning framework

  • David Haussler

We show that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant. Our measure of bias is based on the growth function introduced by Vapnik and Chervonenkis, and on the Vapnik-Chervonenkis dimension. We measure some common language biases, including restriction to conjunctive concepts, conjunctive concepts with internal disjunction, k-DNF and k-CNF concepts. We also measure certain types of bias that result from a preference for simpler hypotheses. Using these bias measurements we analyze the performance of the classical learning algorithm for conjunctive concepts from the perspective of Valiant's learning framework. We then augment this algorithm with a hypothesis simplification routine that uses a greedy heuristic and show how this improves learning performance on simpler target concepts. Improved learning algorithms are also developed for conjunctive concepts with internal disjunction, k-DNF and k-CNF concepts. We show that all our algorithms are within a logarithmic factor of optimal in terms of the number of examples they require to achieve a given level of learning performance in the Valiant framework. Our results hold for arbitrary attribute-based instance spaces defined by either tree-structured or linear attributes.

Details DOI

NeurIPS Conference 1988 Conference Paper

What Size Net Gives Valid Generalization?

  • Eric Baum
  • David Haussler

We address the question of when a network can be expected to generalize from m random training examples chosen from some ar(cid: 173) bitrary probability distribution, assuming that future test examples are drawn from the same distribution. Among our results are the following bounds on appropriate sample vs. network size. Assume o O( ~log~) random exam(cid: 173) ples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 - t of the examples are correctly classified, then one has confi(cid: 173) dence approaching certainty that the network will correctly classify a fraction 1 - £ of future test examples drawn from the same dis(cid: 173) tribution. Conversely, for fully-connected feedforward nets with one hidden layer, any learning algorithm using fewer than O( '! ') random training examples will, for some distributions of examples consistent with an appropriate weight choice, fail at least some fixed fraction of the time to find a weight choice that will correctly classify more than a 1 - £ fraction of the future test examples.

PDF Details

TCS Journal 1987 Journal Article

Applications of an infinite square-free co-CFL

  • Michael G. Main
  • Walter Bucher
  • David Haussler

We disprove several conjectures about context-free languages. The proofs use the set of all strings which are not prefixes of Thue's infinite square-free sequence. This is a context-free language with an infinite square-free complement.

Details DOI

AAAI Conference 1987 Conference Paper

Learning Conjunctive Concepts in Structural Domains

  • David Haussler

We study the problem of learning conjunctive concepts from examples on structural domains like the blocks world. This class of concepts is formally defined and it is shown that even for samples in which each example (positive or negative) is a two-object scene it is NF-complete to determine if there is any concept in this class that is consistent with the sample. We demonstrate how this result affects the feasibility of Mitchell’s version space approach and how it shows that it is unlikely that this class of concepts is polynomially learnable from random examples in the sense of Valiant. On the other hand, we show that this class is polynomially learnable if we allow a larger hypothesis space. This result holds for any fixed number of objects per scene, but the algorithm is not practical unless the number of objects per scene is very small. We also show that heuristic methods for learning from larger scenes are likely to give an accurate hypothesis if they produce a simple hypothesis consistent with a large enough random sample.

PDF Details

AAAI Conference 1986 Conference Paper

Quantifying the Inductive Bias in Concept Learning (extended abstract)

  • David Haussler

We show that the notion of bias in inductive concept learning can be quantified in a way that directly relates to learning performance, and that this quantitative theory of bias can provide guidance in the design of effective learning algorithms. We apply this idea by measuring some common language biases, including restriction to conjunctive concepts and conjunctive concepts with internal disjunction, and, P uided by these measurements, develop learning algorithms or these classes of concepts that have provably good convergence properties.

PDF Details
v2026.09.13