A comparison of certain generalization bounds of learning machines for practical applications

• Autorzy: Klęsk P.
• Języki publikacji: EN

Abstrakty

EN

In statisticallearning bounds on generalization error and sample complexities are important elements. In the paper we compare several selected generalization bounds having in mind their practical applications. In particular; we state twa theorems which compare bounds derived via additive and multiplicative versions of Chemoff inequality. In experimental part we show (using a benchmark data set) how one can practically apply bounds and sample complexity.

Słowa kluczowe

EN

machine learning; statistical learning theory; generalization bounds; Chernoff inequality; Hoeffding inequality; sample complexity

PL

ograniczenia na uogólnianie; nierówność Chernoffa; złożoność próbkowa

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 4 (24)
• Strony: 35--45
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Klęsk P.

• West Pomeranian University of Technology, Szczecin Faculty of Computer Science and Information Technology

Bibliografia

• [1] V. Vapnik. Statistical Learning Theory: Injerence from Small Samples. Wilcy, Ncw York, USA, 1998.
• [2] V. Vapnik. The Nature of Statistical Learning Theory. Springer, USA, 1995.
• [3] M. Anthony, P. Bartlett, Neural Network Learning: Theoretical Foundations. Cambridge University Press, Edinburgh, UK, 1999.
• [4] A. Ng. Feature selection, LI vs. L2 regularization, and rotational invariance. Machine learning, ACM International Conference, vol. 69, 2004.
• [5] P. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525-536,1998.
• [6] T. Zhang. Covering Number Bounds of Certain Regularized Linear Function Classes. Journal of Machine Learning Research, 2:527-550, 2002.
• [7] V. Vapnik, A. Chervonenkis. On the uniform convergenee of relative frequeneies of events to theirprobabilities. Doklady Akademii Nauk, 181,1968.
• [8] N. Saucr. On the density of families of sets. Journal of Combinatorial Thoery, Series A, 13:145-147,1972.
• [9] S. Shelah. A combinatorial problem: Stability and oreder for models and theories in infinity languages. Pacific Journal of Mathematics, 41 :247-261, 1972.
• [10] P. Bartlett, S. Kulkami, S. Posner. Covering Numbers for Real-Valued Function Classes. IEEE Transactions on Information Theory, 43:1721-1724, 1997.
• [11] R. Kohavi. Scaling Up the Accuracy of Naive-Bayes Classifiers: a Decision-Tree Hybrid. Proceedings of the Second International Conferenee on Knowledge Discovery and Data Mining, 1996.