Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- ArticleJuly 1994
Lower bounds on the VC-dimension of smoothly parametrized function classes
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 362–367https://doi.org/10.1145/180139.181179We examine the relationship between the VC-dimension and the number of parameters of a smoothly parametrized function class. We show that the VC-dimension of such a function class is at least k if there exists a k-dimensional differentiable manifold in ...
- ArticleJuly 1994
Generalization in partially connected layered neural networks
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 356–361https://doi.org/10.1145/180139.181178We study the learning from examples in a partially connected single layer perceptron and a two-layer network. Partially connected student networks learn from fully connected teacher networks. We study the generalization in the annealed approximation. We ...
- ArticleJuly 1994
Efficient learning of continuous neural networks
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 348–355https://doi.org/10.1145/180139.181177We describe an efficient algorithm for learning from examples a class of feedforward neural networks with real inputs and outputs in a real-value generalization of the Probably Approximately Correct (PAC) model. These networks can approximate an ...
- ArticleJuly 1994
Learning linear threshold functions in the presence of classification noise
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 340–347https://doi.org/10.1145/180139.181176I show that the linear threshold functions are polynomially learnable in the presence of classification noise, i.e., polynomial in n, 1/ε, 1/δ, and 1/σ, where n is the number of Boolean attributes, ε and δ are the usual accuracy and confidence ...
- ArticleJuly 1994
Learning from a consistently ignorant teacher
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 328–339https://doi.org/10.1145/180139.181170One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire ...
-
- ArticleJuly 1994
Exploiting random walks for learning
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 318–327https://doi.org/10.1145/180139.181167In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. ...
- ArticleJuly 1994
On learning arithmetic read-once formulas with exponentiation (extended abstract)
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 311–317https://doi.org/10.1145/180139.181163A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, subtraction, multiplication, division and exponentiation to an ...
- ArticleJuly 1994
Fat-shattering and the learnability of real-valued functions
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 299–310https://doi.org/10.1145/180139.181158We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide characterizations of the learnability of a real-valued ...
- ArticleJuly 1994
On the intrinsic complexity of language identification
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 278–286https://doi.org/10.1145/180139.181150A new investigation of the complexity of language identification is undertaken using the notion of reduction from recursion theory and complexity theory. The approach, referred to as the intrinsic complexity of language identification, employs notions ...
- ArticleJuly 1994
The strength of noninclusions for teams of finite learners (extended abstract)
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 268–277https://doi.org/10.1145/180139.181144In team learning one considers a set of n learning machines and requires that m out of n must be successful. Comparing the power of different teams of learning machines is a major topic of inductive inference. It is centered around the “inclusion ...
- ArticleJuly 1994
The representation of recursive languages and its impact on the efficiency of learning
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 256–267https://doi.org/10.1145/180139.181139In the present paper we study the learnability of the enumerable families L of uniformly recursive languages in dependence on the number of allowed mind changes, i.e., with respect to a well-studied measure of efficiency. We distinguish between exact ...
- ArticleJuly 1994
Learning one-dimensional geometric patterns under one-sided random misclassification noise
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 246–255https://doi.org/10.1145/180139.181131Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is ...
- ArticleJuly 1994
Learning with queries but incomplete information (extended abstract)
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 237–245https://doi.org/10.1145/180139.181128We investigate learning with membership and equivalence queries assuming that the information provided to the learner is incomplete. By incomplete we mean that some of the membership queries may be answered by “I don't know.” This model is a worst-case ...
- ArticleJuly 1994
Geometrical concept learning and convex polytopes
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 228–236https://doi.org/10.1145/180139.181124We consider exact identification of geometrical objects over the domain {0,1,…,n−1}d, d≥1 fixed. We give efficient implementations of the general incremental scheme “identify the target concept by constructing its convex hull” for learning convex ...
- ArticleJuly 1994
On learning counting functions with queries
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 218–227https://doi.org/10.1145/180139.181116We investigate the problem of learning disjunctions of counting functions, generalizations of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted ...
- ArticleJuly 1994
An optimal parallel algorithm for learning DFA
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 208–217https://doi.org/10.1145/180139.181110Sequential algorithms given by Alguin (1987) and Schapire (1992) learn deterministic finite automata (dfa) exactly from Membership and Equivalence queries. These algorithms are feasible, in the sense that they take time polynomial in n and m, where n is ...
- ArticleJuly 1994
Learning unions of boxes with membership and equivalence queries
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 198–207https://doi.org/10.1145/180139.181102We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where there are n discrete values that each ...
- ArticleJuly 1994
Approximate methods for sequential decision making using expert advice
COLT '94: Proceedings of the seventh annual conference on Computational learning theoryPages 183–189https://doi.org/10.1145/180139.181097We consider a game theoretic approach for sequentially choosing decisions by combining the suggestions of a fixed number of experts. Since the optimal decision making strategy is often computationally expensive, we present a methodology for obtaining ...