A Proposal for More Powerful Learning Algorithms

摘要: Judd (1988) and Blum Rivest have recently proved that the loading problem for neural networks is NP complete. This makes it very unlikely any algorithm like backpropagation which varies weights on a network of fixed size topology will be able to learn in polynomial time. However, Valiant has proposed learning protocol (Valiant 1984), allows one sensibly consider generalization by algorithms with freedom add neurons synapses, as well simply adjusting weights. Within this context, standard circuit complexity arguments show such can solve time solved whatever. In sense, nets are universal learners, capable learnable class concepts.