Adaptive and Self-Confident On-Line Learning Algorithms
作者： Peter Auer , Claudio Gentile
DOI:
关键词: Unsupervised learning 、 Computational learning theory 、 Algorithm 、 Stability (learning theory) 、 Ensemble learning 、 Instance-based learning 、 Computer science 、 Mathematical optimization 、 Empirical risk minimization 、 Learning classifier system 、 Semi-supervised learning
摘要: Most of the performance bounds for on-line learning algorithms are proven assuming a constant rate. To optimize these bounds, rate must be tuned based on quantities that generally unknown, as they depend whole sequence examples. In this paper we show essentially same optimized can obtained when adaptively tune their rates examples in progressively revealed. Our adaptive apply to wide class algorithms, including p-norm generalized linear regression and Weighted Majority with absolute loss. We emphasize our tunings radically different from previous techniques, such so-called doubling trick. Whereas trick restarts algorithm several times using each run, methods save information by changing value very smoothly. fact, over finite set experts analysis provides better leading than
unileoben.ac.at参考文章(33)
Yair Al Censor, Stavros A. Zenios, Parallel Optimization: Theory, Algorithms, and Applications ,(1997)
Jyrki Kivinen, Manfred K. Warmuth, Averaging Expert Predictions european conference on computational learning theory. pp. 153- 167 ,(1999) , 10.1007/3-540-49097-3_13
Katy S. Azoury, M. K. Warmuth, Relative loss bounds for on-line density estimation with the exponential family of distributions uncertainty in artificial intelligence. ,vol. 43, pp. 31- 40 ,(1999) , 10.1023/A:1010896012157
B. WIDROW, M. E. HOFF, Adaptive switching circuits Neurocomputing: foundations of research. pp. 123- 134 ,(1988) , 10.21236/AD0241531
J. Kivinen, M. K. Warmuth, Relative Loss Bounds for Multidimensional Regression Problems neural information processing systems. ,vol. 45, pp. 287- 293 ,(1997) , 10.1023/A:1017938623079
Nicolo Cesa-Bianchi, Manfred K. Warmuth, Philip M. Long, WORST-CASE QUADRATIC LOSS BOUNDS FOR ON-LINE PREDICTION OF LINEAR FUNCTIONS BY GRADIENT DESCENT University of California at Santa Cruz. ,(1993)
Peter Auer, Manfred K. Warmuth, Tracking the Best Disjunction Machine Learning. ,vol. 32, pp. 127- 150 ,(1998) , 10.1023/A:1007472513967
Claudio Gentile, A new approximate maximal margin classification algorithm Journal of Machine Learning Research. ,vol. 2, pp. 213- 242 ,(2002)
Mark Herbster, Manfred K. Warmuth, Tracking the Best Expert Machine Learning. ,vol. 32, pp. 151- 178 ,(1998) , 10.1023/A:1007424614876
Adam J. Grove, Nick Littlestone, Dale Schuurmans, General convergence results for linear discriminant updates Proceedings of the tenth annual conference on Computational learning theory - COLT '97. pp. 171- 183 ,(1997) , 10.1145/267460.267493