Empirical support for Winnow and Weighted-Majority based algorithms: results on a calendar scheduling domain
Elsevier eBooksPublished 1 January 1995
Avrim Blum
Citations73
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.
TL;DR
A new variant on the Winnow algorithm is created that is especially suited to conditions with string-valued classifications, and an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
Abstract
In this paper we describe experimental results using Winnow and Weighted-Majority based algorithms (two algorithms highly studied in the theoretical machine learning literature) on a calendar scheduling domain. We show that these algorithms can be quite competitive practically, outperforming the ID3-based approach currently in use by the Calendar Apprentice system in terms of both accuracy and speed, on a large dataset. In addition we show how Winnow can be applied to achieve a good accuracy/coverage tradeoff and we explore issues that arise such as concept drift. We also provide a theoretical analysis of the Winnow variant that we use (which is one especially suited to conditions with string-valued classifications) and an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
Keywords
Computer ScienceDecision Sciences
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
Machine LearningLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
1,376 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
Elsevier eBooksGreedy Attribute Selection
541 Citations1994Rich Caruana, Dayne Freitag
Experiments suggest hillclimbing in attribute space can yield substantial improvements in generalization performance, and a caching scheme is presented that makes attribute hillClimbing more practical computationally.
Machine LearningLearning quickly when irrelevant attributes abound: A new linear-threshold algorithm
501 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
WebWatcher: A Learning Apprentice for the World Wide Web
496 Citations1995R. Armstrong, Dayne Freitag +2 more
An information seeking assistant for the world wide web, called WebWatcher, interactively helps users locate desired information by employing learned knowledge about which hyperlinks are likely to lead to the target information.
Communications of the ACMExperience with a learning personal assistant
410 Citations1994Tom M. Mitchell, Rich Caruana +3 more
The design of one particular learning assistant is described: a calendar manager, called CAP (Calendar APprentice), that learns user scheduling preferences from experience and suggests that machine learning methods may play an important role in future personal software assistants.
Mistake bounds and logarithmic linear-threshold learning algorithms
184 Citations1990N. Littlestone
An analysis that shows that a straightforward transformation applied to mistake bounded algorithms, consisting of adding a hypothesis testing phase, produces algorithms that have asymptotically optimal PAC-learning bounds for certain target classes.
Communications of the ACMHow good is good enough?
157 Citations1994W. R. Collins, Keith Miller +2 more
A personal learning apprentice
154 Citations1992Lisa Dent, Jesús G. Boticario +3 more
The organization of CAP, its performance in initial field tests, and more general lessons learned from this effort about learning apprentice systems are described.
How to use expert advice
132 Citations1993Nicolò Cesa‐Bianchi, Yoav Freund +4 more
This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called `experts', and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently known in this context.
Learning probabilistic prediction functions
94 Citations1988Alfredo De Santis, George Markowsky +1 more
The question of how to learn rules, when those rules make probabilistic statements about the future, is considered and two results related to these distinct goals are given.
Machine LearningLearning Boolean Functions in an Infinite Attribute Space
86 Citations1992Avrim Blum
A theoretical model for learning Boolean functions in domains having a large, potentially infinite number of attributes allows an algorithm to employ a rich vocabulary to describe the objects it encounters in the world without necessarily incurring time and space penalties so long as each individual object is relatively simple.
Elsevier eBooksRedundant Noisy Attributes, Attribute Errors, and Linear-threshold Learning Using Winnow
52 Citations1991N. Littlestone
This work studies the performance of the linear-threshold algorithm, Winnow, in the presence of attribute errors in the data available for learning, and examines probabilistic mistake bounds that can be obtained by making stronger assumptions about the instances seen by the learner in models of noisy redundant information.
Machine LearningLearning boolean functions in an infinite attribute space
30 Citations1992Avrim Blum
A theoretical model for learning Boolean functions in domains having a large, potentially infinite number of attributes allows an algorithm to employ a rich vocabulary to describe the objects it encounters in the world without necessarily incurring time and space penalties so long as each individual object is relatively simple.
Elsevier eBooksInterfaces That Learn: A Learning Apprentice for Calendar Management
19 Citations1993Jean Jourdan, Lisa Dent +3 more
This chapter discusses an approach to solve the problem of developing and maintaining the knowledge base by constructing systems that learn from their users by constructing learning apprentice systems.
Conference on Learning TheoryLearning in the presence of finitely or infinitely many irrelevant attributes
17 Citations1991Avrim Blum, Lisa Hellerstein +1 more
Elsevier eBooksLearning in the Presence of Finitely or Infinitely Many Irrelevant Attributes
14 Citations1991Avrim Blum, Lisa Hellerstein +1 more