The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
Abstract
Sample complexity results from computational learning theory, when applied to neural network learning for pattern classification problems, suggest that for good generalization performance the number of training examples should grow at least linearly with the number of adjustable parameters in the network. Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. For example, consider a two-layer feedforward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A and the input dimension is n. We show that the misclassification probability is no more than a certain error estimate (that is related to squared error on the training set) plus A/sup 3/ /spl radic/((log n)/m) (ignoring log A and log m factors), where m is the number of training patterns. This may explain the generalization performance of neural networks, particularly when the number of training examples is considerably smaller than the number of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training. The proof techniques appear to be useful for the analysis of other pattern classifiers: when the input domain is a totally bounded metric space, we use the same approach to give upper bounds on misclassification probability for classifiers with decision boundaries that are far from the training examples.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A decision-theoretic generalization of on-line learning and an application to boosting
Freund, Y., & Schapire, R. E. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1504 · Cited by 20,466
A training algorithm for optimal margin classifiers
Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992) · Proceedings of the fifth annual workshop on Computational learning theory · doi:10.1145/130385.130401 · Cited by 11,992
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
Introduction to the theory of neural computation
(1994) · Neural Networks · doi:10.1016/0893-6080(94)90014-0 · Cited by 6,401
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,852
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
Universal approximation bounds for superpositions of a sigmoidal function
Barron, A. R. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256500 · Cited by 2,804
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
Boosting the margin: a new explanation for the effectiveness of voting methods
Bartlett, P., Freund, Y., Lee, W. S., & Schapire, R. E. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691352 · Cited by 2,306
Self-citation
Cited by
Extreme learning machine: Theory and applications
Huang, G.-B., Zhu, Q.-Y., & Siew, C.-K. (2006) · Neurocomputing · doi:10.1016/j.neucom.2005.12.126 · Cited by 13,285
Kernel Methods for Pattern Analysis
Shawe-Taylor, J., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,587
Extreme Learning Machine for Regression and Multiclass Classification
Huang, G.-B., Zhou, H., Ding, X., & Zhang, R. (2012) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2011.2168604 · Cited by 5,550
Extreme learning machine: a new learning scheme of feedforward neural networks
Huang, G.-B., Zhu, Q.-Y., & Siew, C.-K. (2005) · 2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541) · doi:10.1109/ijcnn.2004.1380068 · Cited by 4,084
Understanding deep learning requires rethinking generalization
Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2016) · arXiv · doi:10.48550/arxiv.1611.03530 · Cited by 2,838
(1999) · doi:10.1162/089976600300015565 · Cited by 2,799
Improved boosting algorithms using confidence-rated predictions
Schapire, R. E., & Singer, Y. (1998) · Proceedings of the eleventh annual conference on Computational learning theory · doi:10.1145/279943.279960 · Cited by 2,547
Understanding deep learning (still) requires rethinking generalization
Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2021) · Communications of the ACM · doi:10.1145/3446776 · Cited by 2,400
Boosting the margin: a new explanation for the effectiveness of voting methods
Bartlett, P., Freund, Y., Lee, W. S., & Schapire, R. E. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691352 · Cited by 2,306
Self-citationThe Boosting Approach to Machine Learning: An Overview
Schapire, R. E. (2003) · Lecture Notes in Statistics · doi:10.1007/978-0-387-21579-2_9 · Cited by 2,003
Improved Boosting Algorithms Using Confidence-rated Predictions
Schapire, R. E., & Singer, Y. (1999) · Machine Learning · doi:10.1023/a:1007614523901 · Cited by 1,971
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Bartlett, P. L., & Mendelson, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44581-1_15 · Cited by 1,949
Self-citationExtreme learning machines: a survey
Huang, G.-B., Wang, D. H., & Lan, Y. (2011) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-011-0019-y · Cited by 1,914
Advances in Large-Margin Classifiers
(2000) · The MIT Press eBooks · doi:10.7551/mitpress/1113.001.0001 · Cited by 1,869
Reconciling modern machine-learning practice and the classical bias–variance trade-off
Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1903070116 · Cited by 1,595
Feature selection, L 1 vs. L 2 regularization, and rotational invariance
Ng, A. Y. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015435 · Cited by 1,572
Regularization Networks and Support Vector Machines
Evgeniou, T., Pontil, M., & Poggio, T. (2000) · Advances in Computational Mathematics · doi:10.1023/a:1018946025316 · Cited by 1,197
Convexity, Classification, and Risk Bounds
Bartlett, P. L., Jordan, M. I., & McAuliffe, J. D. (2006) · Journal of the American Statistical Association · doi:10.1198/016214505000000907 · Cited by 1,037
Self-citationAn Insight into Extreme Learning Machines: Random Neurons, Random Features and Kernels
Huang, G.-B. (2014) · Cognitive Computation · doi:10.1007/s12559-014-9255-2 · Cited by 957
Optimization for Machine Learning
(2011) · The MIT Press eBooks · doi:10.7551/mitpress/8996.001.0001 · Cited by 875
Optimization method based extreme learning machine for classification
Huang, G.-B., Ding, X., & Zhou, H. (2010) · Neurocomputing · doi:10.1016/j.neucom.2010.02.019 · Cited by 869
Evolutionary extreme learning machine
Zhu, Q.-Y., Qin, A. K., Suganthan, P. N., & Huang, G.-B. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.03.028 · Cited by 815
Learning capability and storage capacity of two-hidden-layer feedforward networks
Huang, G.-B. (2003) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2003.809401 · Cited by 810
On the Learnability and Design of Output Codes for Multiclass Problems
Crammer, K., & Singer, Y. (2002) · Machine Learning · doi:10.1023/a:1013637720281 · Cited by 650
A model of inductive bias learning
Baxter, J. (2000) · Journal of Artificial Intelligence Research · doi:10.1613/jair.731 · Cited by 582
Benign overfitting in linear regression
Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1907378117 · Cited by 547
Self-citationStructural risk minimization over data-dependent hierarchies
Shawe-Taylor, J., Bartlett, P. L., Williamson, R. C., & Anthony, M. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705570 · Cited by 527
Self-citationA mean field view of the landscape of two-layer neural networks
Mei, S., Montanari, A., & Nguyen, P.-M. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1806579115 · Cited by 500
Huang, G.-B. (2015) · Cognitive Computation · doi:10.1007/s12559-015-9333-0 · Cited by 471
Robust 3D Action Recognition with Random Occupancy Patterns
Wang, J., Liu, Z., Chorowski, J., Chen, Z., & Wu, Y. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33709-3_62 · Cited by 471
A comprehensive evaluation of random vector functional link networks
Zhang, L., & Suganthan, P. N. (2016) · Information Sciences · doi:10.1016/j.ins.2015.09.025 · Cited by 465
Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers
Koltchinskii, V., & Panchenko, D. (2002) · The Annals of Statistics · doi:10.1214/aos/1015362183 · Cited by 451
Concrete compressive strength using artificial neural networks
Asteris, P. G., & Mokos, V. G. (2020) · Neural Computing and Applications · doi:10.1007/s00521-019-04663-2 · Cited by 435
On the Generalization Ability of On-Line Learning Algorithms
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.833339 · Cited by 426
Margin based feature selection - theory and algorithms
Gilad-Bachrach, R., Navot, A., & Tishby, N. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015352 · Cited by 414
Learning the Kernel Matrix with Semi-Definite Programming
Lanckriet, G. R. G., Christianini, N., Bartlett, P. L., Ghaoui, L. E., & Jordan, M. I. (2002) · QUT ePrints (Queensland University of Technology) · doi:10.5555/1005332.1005334 · Cited by 386
Self-citationXu, H., & Mannor, S. (2012) · Machine Learning · doi:10.1007/s10994-011-5268-1 · Cited by 377
Gou, B., Xu, Y., & Feng, X. (2020) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2020.3014932 · Cited by 372
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/1532443041827916 · Cited by 363
Voting based extreme learning machine
Cao, J., Lin, Z., Huang, G.-B., & Liu, N. (2012) · Information Sciences · doi:10.1016/j.ins.2011.09.015 · Cited by 356
Local Receptive Fields Based Extreme Learning Machine
Huang, G.-B., Bai, Z., Kasun, L. L. C., & Vong, C. M. (2015) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2015.2405316 · Cited by 350
Local-Learning-Based Feature Selection for High-Dimensional Data Analysis
Sun, Y., Todorovic, S., & Goodison, S. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.190 · Cited by 347
Model Selection and Error Estimation
Bartlett, P. L., Boucheron, S., & Lugosi, G. (2002) · Machine Learning · doi:10.1023/a:1013999503812 · Cited by 297
Self-citationEpileptic EEG classification based on extreme learning machine and nonlinear features
Yuan, Q., Zhou, W., Li, S., & Cai, D. (2011) · Epilepsy Research · doi:10.1016/j.eplepsyres.2011.04.013 · Cited by 286
Self-Adaptive Evolutionary Extreme Learning Machine
Cao, J., Lin, Z., & Huang, G.-B. (2012) · Neural Processing Letters · doi:10.1007/s11063-012-9236-y · Cited by 286
Exploring Generalization in Deep Learning
Neyshabur, B., Bhojanapalli, S., McAllester, D., & Srebro, N. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.08947 · Cited by 284
Norm-Based Capacity Control in Neural Networks
Neyshabur, B., Tomioka, R., & Srebro, N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.00036 · Cited by 279
Extreme learning machine: RBF network case
Huang, G.-B., & Siew, C.-K. (2005) · ICARCV 2004 8th Control, Automation, Robotics and Vision Conference, 2004. · doi:10.1109/icarcv.2004.1468985 · Cited by 278
A study on effectiveness of extreme learning machine
Wang, Y., Cao, F., & Yuan, Y. (2011) · Neurocomputing · doi:10.1016/j.neucom.2010.11.030 · Cited by 269
Can threshold networks be trained directly?
Huang, G.-B., Zhu, Q.-Y., Mao, K. Z., Siew, C.-K., Saratchandran, P., & Sundararajan, N. (2006) · IEEE Transactions on Circuits and Systems II: Express Briefs · doi:10.1109/tcsii.2005.857540 · Cited by 266
Self-compacting concrete strength prediction using surrogate models
Asteris, P. G., & Kolovos, K. G. (2019) · Neural Computing and Applications · doi:10.1007/s00521-017-3007-7 · Cited by 265
CLASSIFICATION OF MENTAL TASKS FROM EEG SIGNALS USING EXTREME LEARNING MACHINE
LIANG, N.-Y., SARATCHANDRAN, P., HUANG, G.-B., & SUNDARARAJAN, N. (2006) · International Journal of Neural Systems · doi:10.1142/s0129065706000482 · Cited by 262
Song, Y., Crowcroft, J., & Zhang, J. (2012) · Journal of Neuroscience Methods · doi:10.1016/j.jneumeth.2012.07.003 · Cited by 252
Vocal and Facial Biomarkers of Depression based on Motor Incoordination and Timing
Williamson, J. R., Quatieri, T. F., Helfer, B. S., Ciccarelli, G., & Mehta, D. D. (2014) · Proceedings of the 4th International Workshop on Audio/Visual Emotion Challenge · doi:10.1145/2661806.2661809 · Cited by 209
Lu, S., Zhu, Z., Gorriz, J. M., Wang, S., & Zhang, Y. (2022) · International Journal of Intelligent Systems · doi:10.1002/int.22686 · Cited by 151
On the depth of deep neural networks: a theoretical view
Sun, S., Chen, W., Wang, L., Liu, X., & Liu, T.-Y. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10243 · Cited by 147
Cavaleri, L., Asteris, P. G., Psyllaki, P. P., Douvika, M. G., Skentou, A. D., & Vaxevanidis, N. M. (2019) · Applied Sciences · doi:10.3390/app9142788 · Cited by 72
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
Oymak, S., Fabian, Z., Li, M., & Soltanolkotabi, M. (2019) · arXiv · doi:10.48550/arxiv.1906.05392 · Cited by 44
From Data Quality to Model Quality: An Exploratory Study on Deep Learning
He, T., Yu, S., Wang, Z., Li, J., & Chen, Z. (2019) · Proceedings of the 11th Asia-Pacific Symposium on Internetware · doi:10.1145/3361242.3361260 · Cited by 24
Metadata
- Authors
- Bartlett, P. L.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1998-03
- Volume
- 44
- Issue
- 2
- Pages
- 525-536
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2099579348
- Cited by
- 1,166
- References
- 41
- FWCI
- 36.32
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.