Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We describe an efficient algorithm for learning from examples a class of feedforward neural networks with real inputs and outputs in a real-value generalization of the Probably Approximately Correct (PAC) model. These networks can approximate an arbitrary function with an arbitrary precision. The learning algorithm can accommodate a fairly general worst-case noise model. The main improvement over previous work is that the running time of the algorithm grows only polynomially as the size of the target network increases (there is still an exponential dependence on the dimension of the input space, however). The main computational tool is an iterative “loading” algorithm which adds new hidden units to the hypothesis network sequentially. This avoids the difficult problem of optimizing the weights of all units simultaneously.

REFERENCES

• 1: A. Barton. Universal approximation bounds for supperpositions of a sigmoidal function. IEEE ~ransactions on Information Theory, 39(3):930-945, May 1993.
• 2: C. Darken, M. Donahue, L. Ourvits, and E. Sontag. Rate of approximation results for neural network learning. Technical Report 93-07, Siemens Res. Corp., Princeton, NJ, 1993.
• 3: Christian Darken , Michael Donahue , Leonid Gurvits , Eduardo Sontag, Rate of approximation results motivated by robust neural network learning, Proceedings of the sixth annual conference on Computational learning theory, p.303-309, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168357]
• 4: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 5: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 6: Kurt Hornik, Approximation capabilities of multilayer feedforward networks, Neural Networks, v.4 n.2, p.251-257, 1991 [doi>10.1016/0893-6080(91)90009-T]
• 7: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• 8: Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
• 9: W. Maass. Agnostic PAC-learning of functions on analog neural nets. In Proc. 7th Annual IEEE Conference on Neural Information Processing Systems, 1993.
• 10: Wolfgang Maass, Bounds for the computational power and learning complexity of analog neural nets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.335-344, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167193]
• 11: D. Pollard. Convergence of Stochastic Processes. Springcr Verlag, 1984.
• 12: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 13: L. G. Valiant. Learning disjunctions of conjuntlons. In Proc. 9th International Joint Conference on Artificial Intelligence, pages 560-566, 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Algorithms, Theory, Verification