The complexity of learning according to two models of a drifting environment
Published 24 July 1998Open access
Philip M. Long
Citations35
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Article Free Access Share on The complexity of learning according to two models of a drifting environment Author: Philip M. Long ISCS Department, National University of Singapore, Singapore 119260, Republic of Singapore ISCS Department, National University of Singapore, Singapore 119260, Republic of SingaporeView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 116–125https://doi.org/10.1145/279943.279968Online:24 July 1998Publication History 6citation214DownloadsMetricsTotal Citations6Total Downloads214Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Keywords
Computer Science
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Information and ComputationDecision theoretic generalizations of the PAC model for neural net and other learning applications
871 Citations1992David Haussler
Theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H are given, and it is shown how this implies learnability with bounded sample size, disregarding computational complexity.
Journal of Combinatorial Theory Series AOn the density of families of sets
866 Citations1972N. Sauer
This paper will answer the question in the affirmative by determining the exact upper bound of T if T is a family of subsets of some infinite set S then either there exists to each number n a set A ⊂ S with |A| = n such that |T ∩ A| = 2n or there exists some number N such that •A| c for each A⩾ N and some constant c.
Project Euclid (Cornell University)Empirical Processes: Theory and Applications
711 Citations1990David Pollard
Machine LearningTracking the Best Expert
566 Citations1998Mark Herbster, Manfred K. Warmuth
The generalization allows the sequence to be partitioned into segments, and the goal is to bound the additional loss of the algorithm over the sum of the losses of the best experts for each segment to model situations in which the examples change and different experts are best for certain segments of the sequence of examples.
Mathematics and its applications. Soviet seriesε-Entropy and ε-Capacity of Sets In Functional Spaces
513 Citations1993V. М. Tikhomirov
Pacific Journal of MathematicsA combinatorial problem; stability and order for models and theories in infinitary languages
496 Citations1972Saharon Shelah
The Annals of ProbabilitySharper Bounds for Gaussian and Empirical Processes
488 Citations1994Michel Talagrand
Toward efficient agnostic learning
347 Citations1992Michael Kearns, Robert E. Schapire +1 more
Journal of Combinatorial Theory Series ASphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension
296 Citations1995David Haussler
It is shown that M(k/n,V) >= (cn/(k+d)log(n/k) for some constant c so that any two distinct vectors in W differ on at least k indices.
Information and ComputationPredicting {0, 1}-Functions on Randomly Drawn Points
152 Citations1994David Haussler, N. Littlestone +1 more
Machine LearningToward efficient agnostic learning
150 Citations1994Michael Kearns, Robert E. Schapire +1 more
An investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions is initiated, providing an initial outline of the possibilities for agnostic learning.
Machine LearningTracking Drifting Concepts By Minimizing Disagreements
146 Citations1994David P. Helmbold, Philip M. Long
neural information processing systemsLearning Time-varying Concepts
69 Citations1990Anthony Kuh, Thomas Petsche +1 more
This work has extended formal definitions of concepts and learning to provide a framework in which an algorithm can track a concept as it evolves over time, and derived some PAC-style sample complexity results that determine, for example, when tracking is feasible.
Learning with a slowly changing distribution
53 Citations1992Peter L. Bartlett
An upper bound on &Ugr; is given that ensures learning is possible from a finite number of examples, to ensure that some learning algorithm can produce an acceptably small probability of misclassification.
General bounds on the number of examples needed for learning probabilistic concepts
51 Citations1993Hans Ulrich Simon
A new method for designing learning algorithms: dynamic partitioning of the domain by use of splitting trees is introduced and it can be shown that the resulting lower bounds for learning ND are tight to within a logarithmic factor.
Lecture notes in computer scienceLearning under persistent drift
37 Citations1997Yoav Freund, Yishay Mansour
This paper shows in this case how to use a simple weighting scheme to estimate the error of an hypothesis, and using this estimate, to minimize theerror of the prediction.
Tracking the best regressor
33 Citations1998Mark Herbster, Manfred K. Warmuth
This paper develops the methodology for lifting known static bounds to the shifting case and obtains bounds when the comparison class consists of linear neurons (linear combinations of experts).
Journal of Computer and System SciencesGeneral Bounds on the Number of Examples Needed for Learning Probabilistic Concepts
31 Citations1996Hans Ulrich Simon
Learning switching concepts
29 Citations1992Avrim Blum, Prasad Chalasani
This work considers learning in situations where the function used to classify examples may switch back and forth between a small number of different concepts during the course of learning, and describes a randomized query algorithm for such adversarial switches between two monotone disjunctions.
Information and ComputationOn the Complexity of Learning from Drifting Distributions
27 Citations1997Rakesh Barve, Philip M. Long
Learning changing concepts by exploiting the structure of change
24 Citations1996Peter L. Bartlett, Shai Ben-David +1 more
Learning to model sequences generated by switching distributions
16 Citations1995Yoav Freund, Dana Ron
An efficient algorithm for solving the switching distributions learning problem is given and conditions under which the algorithm is guaranteed to work with high probability are shown.
Information and ComputationOn the Jacopini Technique
15 Citations1997Jan Kuper
The concept of proof-replaceability is introduced by which the structure of the Jacopini technique is simplified considerably, and a general theorem concerning the consistency of extensions of the $\lambda\mu$-calculus of a certain form is proved.
IEEE Transactions on Signal ProcessingComparison of tracking algorithms for single layer threshold networks in the presence of random drift
10 Citations1997Anthony Kuh
Results show that the perceptron tracker and the LMS tracker can work well in slowly changing nonstationary environments and that the bounds are tight when /spl gamma/ is small and the number of inputs n is large.
Neural NetworksPerformance Bounds for Single Layer Threshold Networks when Tracking a Drifting Adversary
8 Citations1997Xiaodong Tian, Anthony Kuh
Upper bounds for the generalization error of three tracking algorithms when confronted with a worst case adversary are found, respectively 2gamma/cos(gammapi),2gamman/, and gamma(2n + 2.5) where n is the number of inputs.
Semantic complexity of classes of relational queries and query independent data partitioning
8 Citations1991Shaibal Roy
A measure of the semantic complexity of classes of selection queries in relational databases is introduced and certain probabilistic bounds hitherto provable only for individual queries are extended to an entire class of queries.
On the sample complexity of learning functions with bounded variation
1 Citations1998Philip M. Long
It is shown that the class 3nv of [0, l]-valued functions with total variation at most 1 can be agnostically learned with respect to the absolute loss in polynomial time from 0 (5 log +) examples, matching a known lower bound to within a constant factor.