Complexity of learning in artificial neural networks

DOI10.1016/S0304-3975(01)00167-0MaRDI QIDQ5958811zbMATH OpenOpenAlexFDO

Authors Andreas Engel

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(01)00167-0

zbMATH Keywords

algorithmic complexitylearning theoryneural networksstatistical mechanics

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Review text

Some basic issues in the statistical mechanics of learning from examples are reviewed. The approach of statistical physics is contrasted with the analysis of learning within the framework of mathematical statistics and the question of the algorithmic complexity of explicit learning prescriptions is addressed. Even in very simple learning scenarios, the typical properties of which can be analyzed in great quantitative detail by methods from statistical mechanics, the determination of a suitable hypothesis approximating the target rule may be an NP-complete problem. Some special learning setups are suggested as model systems for the comparison between the approaches of statistical mechanics and computer science to the theory of computationally hard problems.

Recommendations

• scientific article; zbMATH DE number 503283
• Statistical mechanics of learning
• scientific article; zbMATH DE number 1028240
• Estimates of Data Complexity in Neural-Network Learning
• scientific article; zbMATH DE number 5957227

Cites work

• A logical calculus of the ideas immanent in nervous activity
• A physicist's approach to number partitioning
• A theory of the learnable
• Approximation by superpositions of a sigmoidal function
• Computational limitations on learning from examples
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• scientific article; zbMATH DE number 4070373 (Why is no real title available?)
• scientific article; zbMATH DE number 4083016 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• On the Distribution of the Number of Successes in Independent Trials
• Self averaging and the space of interactions in neural networks
• Statistical mechanics methods and phase transitions in optimization problems
• Statistical mechanics of learning
• Vapnik-Chervonenkis bounds for generalization

Cited in

(13)

• Complexity and neural networks
• Statistical mechanics of learning
• On the complexity of computing and learning with multiplicative neural networks
• scientific article; zbMATH DE number 17222 (Why is no real title available?)
• scientific article; zbMATH DE number 67614 (Why is no real title available?)
• scientific article; zbMATH DE number 1304387 (Why is no real title available?)
• scientific article; zbMATH DE number 529748 (Why is no real title available?)
• scientific article; zbMATH DE number 1076428 (Why is no real title available?)
• scientific article; zbMATH DE number 2018620 (Why is no real title available?)
• scientific article; zbMATH DE number 940827 (Why is no real title available?)
• Statistical mechanics methods and phase transitions in optimization problems
• Self-regulated complexity in neural networks
• Learning from hints in neural networks

This page was built for publication: Complexity of learning in artificial neural networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958811)