Empirical support for Winnow and Weighted-Majority algorithms: Results on a calendar scheduling domain

被引:105
作者
Blum, A
机构
[1] School of Computer Science, Carnegie Mellon University, Pittsburgh
基金
美国国家科学基金会;
关键词
Winnow; Weighted-Majority; multiplicative algorithms;
D O I
10.1023/A:1007335615132
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper describes experimental results on using Winnow and Weighted-Majority based algorithms on a real-world calendar scheduling domain. These two algorithms have been highly studied in the theoretical machine learning literature. We show here that these algorithms can be quite competitive practically, outperforming the decision-tree approach currently in use in the Calendar Apprentice system in terms of both accuracy and speed. One of the contributions of this paper is a new variant on the Winnow algorithm (used in the experiments) that is especially suited to conditions with suing-valued classifications, and we give a theoretical analysis of its performance. In addition we show how Winnow can be applied to achieve a good accuracy/coverage tradeoff and explore issues that arise such as concept drift. We also provide an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
引用
收藏
页码:5 / 23
页数:19
相关论文
共 14 条
[1]  
[Anonymous], THESIS U C SANTA CRU
[2]  
[Anonymous], P 11 INT C MACH LEAR
[3]  
ARMSTRONG R, 1995, 1995 AAAI SPRING S I
[4]  
BLUM A, 1991, PROCEEDINGS OF THE FOURTH ANNUAL WORKSHOP ON COMPUTATIONAL LEARNING THEORY, P157
[5]   LEARNING BOOLEAN FUNCTIONS IN AN INFINITE ATTRIBUTE SPACE [J].
BLUM, A .
MACHINE LEARNING, 1992, 9 (04) :373-386
[6]  
CESABIANCHI N, 1993, 25TH P ANN ACM S THE, P382
[7]  
DENT L, 1992, P 1992 NAT C ART INT
[8]  
DESANTIS A, 1988, P 29 ANN IEEE S FDN, P110
[9]  
Feller W., 1968, INTRO PROBABILITY TH
[10]  
JOURDAN J, 1991, CMUCS91135 CARN MELL