Efficient learning of continuous neural networks

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. 1.A. Barton. Universal approximation bounds for supperpositions of a sigmoidal function. IEEE ~ransactions on Information Theory, 39(3):930-945, May 1993.
2. 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. 3.C. Darken, M. Donahue, L. Gurvits, and E. Sonta~. Rate of approximation results motivated by robust neural network learning. In Proc. Sizth Annual A CM Conference on Computational Learning Theory, 1993.
4. 4.H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing, 15(2):341- 363, May 1986.
5. 5.D. Haussler. Decision theoretic generalizations of the PAC model for neural nets and other lcarning applications. Information and Computation, (100):78-150, 1992.
6. 6.K. Hornik. Approximation capabilities of multilayer ~eedforward networks. Neural Networks, 4:251-257, 1991.
7. 7.M. Kearns and M. Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807- 873, August 1993.
8. 8.M. J. Kearns, 1%. E. Schapire, and L. M. Sellie. Toward efficient agnostic learning. In Proc. 5th A CM Workshop on Computational Learning Theory, pages 341- 352, 1992.
9. 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. 10.W. Maass. Bounds for the computational power and learning complexity of analog neural nets. In Proc. 25th STOC, pages 335-344, 1993.
11. 11.D. Pollard. Convergence of Stochastic Processes. Springcr Verlag, 1984.
12. 12.A. Schrljver. Theory of Linear and Integer Programming. Wiley, New-York, 1986.
13. 13.L. G. Valiant. Learning disjunctions of conjuntlons. In Proc. 9th International Joint Conference on Artificial Intelligence, pages 560-566, 1985.

Index Terms

• Computing methodologies

  • Machine learning

    • Machine learning approaches

      • Neural networks