×

A review of combinatorial problems arising in feedforward neural network design. (English) Zbl 0801.68148

Summary: The paper is primarily oriented towards discrete mathematics and emphasizes the occurrence of combinatorial problems in the area of artificial neural networks. The focus is on feedforward networks of binary units and their use as associative memories. Exact and heuristic algorithms for designing networks with single or multiple layers are discussed and complexity results related to the learning problems are reviewed. Several methods do only vary the parameters of networks whose topology has been chosen a priori while others build the networks during the training process. Valiant’s learning from examples model which formalizes the problem of generalization is presented and open questions are mentioned.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
92B20 Neural networks for/in biological studies, artificial life and related topics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E.; Korst, J., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley New York · Zbl 0674.90059
[2] Abu-Mostafa, Y. S., The Vapnik-Chervonenkis dimension: Information versus complexity in learning, Neural Comput., 1, 3, 312-317 (1989)
[3] Abu-Mostafa, Y. S., Learning from hints in neural networks, J. Complexity, 6, 192-198 (1990) · Zbl 0694.68057
[4] Abu-Mostafa, Y. S.; St. Jacques, J.-M., Information capacity of the Hopfield model, IEEE Trans. Inform. Theory IT-31, 461-464 (1985) · Zbl 0571.94030
[5] Albert, A., Regression and the Moore-Penrose Pseudoinverse (1972), Academic Press: Academic Press New York · Zbl 0253.62030
[6] Al-Mashouq, K. A.; Reed, I. S., Including hints in training neural nets, Neural Comput., 3, 418-427 (1991)
[7] Amit, D. J., Modeling Brain Function: The World of Attractor Neural Networks (1989), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0709.92001
[8] Angeniol, B.; de la Croix Vaubois, G.; le Texier, J.-Y., Self-organizing feature maps and the travelling salesman problem, Neural Networks, 1, 289-293 (1988)
[9] Amaldi, E., Problèmes d’Apprentissage dans les Réseaux de Neurones, Diploma Project (1988), Swiss Federal Institute of Technology: Swiss Federal Institute of Technology Lausanne
[10] Amaldi, E.; Nicolis, S., Stability-capacity diagram of a neural network with Ising bonds, J. Physique, 50, 2333-2345 (1989)
[11] Amaldi, E., On the Complexity of Training Perceptrons, (Kohonen, T.; etal., Artificial Neural Networks (1991), North-Holland: North-Holland Amsterdam), 55-60, Proc. ICANN-91
[12] Amaldi, E.; Mayoraz, E.; Hertz, A.; de Werra, D., Apprentissage dans les Réseaux de Hopfield, (Proc. Internat. Conf. on Artificial Neural Networks, EPF-Lausanne, Switzerland (1989), Presses Polytechniques Romandes), 77-85
[13] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 277-284 (1987) · Zbl 0611.05022
[14] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete Appl. Math., 23, 11-24 (1989) · Zbl 0666.68067
[15] Baum, E. B., Complete representations for learning from examples, (Abu-Mostafa, Y. S., Complexity in Information Theory (1988), Springer: Springer Berlin)
[16] Baum, E. B., A proposal for more powerful learning algorithms, Neural Comput., 1, 2, 201-207 (1989)
[17] Baum, E. B., The perceptron algorithm is fast for nonmalicious distributions, Neural Comput., 2, 22, 248-260 (1990)
[18] Baum, E. B.; Haussler, D., What size net gives valid generalization?, Neural Comput., 1, 1, 151-160 (1989)
[19] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[20] Blum, A.; Rivest, R., Training a 3-node neural network is NP-complete, (Haussler, D.; Pitt, L., Proc. 1st Workshop on Computational Learning Theory (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 9-18
[21] A. Blum and R. Rivest, Training a 3-node neural network is NP-complete, to appear in Neural Networks.; A. Blum and R. Rivest, Training a 3-node neural network is NP-complete, to appear in Neural Networks.
[22] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K., Learnability and the Vapnik-Chervonenkis dimension, J. ACM, 36, 929-965 (1989) · Zbl 0697.68079
[23] Blumer, A.; Littlestone, N., Learning faster than promised by the Vapnik-Chervonenkis dimension, Discrete Appl. Math., 24, 47-53 (1989) · Zbl 0678.68084
[24] Bruck, J., Harmonic analysis of polynomial threshold functions, SIAM J. Discrete Math., 3, 168-177 (1990) · Zbl 0695.94022
[25] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 14, 444-466 (1965) · Zbl 0469.65037
[26] Cover, T. M., Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition, IEEE Trans. Electronic Comput., 14, 326-334 (1965) · Zbl 0152.18206
[27] Cybenko, G., Approximation by superpositions of a sigmoidal function, Math. Control Signals Systems, 2, 303-314 (1989) · Zbl 0679.94019
[28] Duda, R. O.; Hart, P. E., Pattern Classification and Scene Analysis (1973), Wiley: Wiley New York · Zbl 0277.68056
[29] Durbin, R.; Willshaw, D. J., An analogue approach to the travelling salesman problem using an elastic net method, Nature, 326, 689-691 (1987)
[30] Fiechter, C.-N., A parallel tabu search algorithm for large traveling salesman problems, Research Report ORWP90/01 (1990), Department of Mathematics, Swiss Federal Institute of Technology: Department of Mathematics, Swiss Federal Institute of Technology Lausanne · Zbl 0938.68942
[31] Fontanari, J. F.; Meir, R., Evolving a learning algorithm for the binary perceptron, Network: Comput. Neural Systems, 2, 353-359 (1991)
[32] Frean, M., The upstart algorithm: A method for constructing and training feedforward neural networks, Neural Comput., 2, 198-209 (1990)
[33] Gallant, S. I., A connectionist learning algorithm with provable generalization and scaling bounds, Neural Networks, 3, 191-201 (1990)
[34] Gallant, S. I., Perceptron-based learning algorithms, IEEE Trans. Neural Networks, 1, 179-191 (1990)
[35] Garey, M. R.; Johson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[36] Glover, F., Tabu search - Part II, ORSA J. Comput., 2, 1, 4-32 (1990) · Zbl 0771.90084
[37] Goles, E.; Martínez, S., Neural and Automata Networks: Dynamical Behavior and Applications (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1103.37302
[38] Grossman, T., The CHIR algorithm: A generalization for multiple-output and multi-layered networks, Complex Systems, 3, 407-419 (1989)
[39] Grossman, T.; Meir, R.; Domany, E., Learning by choice of internal representations, Complex Systems, 2, 555 (1988) · Zbl 0667.68094
[40] Hertz, J.; Krogh, A.; Palmer, G., Introduction to the Theory of Neural Computation (1991), Addison-Wesley: Addison-Wesley Redwood City, CA
[41] Hopfield, J. J., Neural networks and physical systems with emergent collective computational abilities, Proc. Natl. Acad. Sci. USA, 79, 2554-2558 (1982) · Zbl 1369.92007
[42] Hopfield, J. J.; Tank, D. W., Neural computation of decisions in optimization problems, Biol. Cybernetics, 52, 141-152 (1985) · Zbl 0572.68041
[43] Judd, J. S., Complexity of connectionist learning with various node functions, Tech. Rept. 87-60 (1987), Univ. of Massachusetts: Univ. of Massachusetts Amherst, MA
[44] Judd, J. S., On the complexity of loading shallow neural networks, J. Complexity, 4, 177-192 (1988) · Zbl 0648.68086
[45] Judd, J. S., Neural Network Design and the Complexity of Learning (1990), MIT Press: MIT Press Cambridge, MA
[46] Kamgar-Parsi, B.; Kamgar-Parsi, B., On problem solving with Hopfield neural networks, Biol. Cybernetics, 62, 415-423 (1990) · Zbl 0687.68031
[47] Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[48] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671 (1983) · Zbl 1225.90162
[49] Kohonen, T., Self-Organization and Associative Memory, ((1988), Springer: Springer New York) · Zbl 0659.68100
[50] Krauth, W.; Mézard, M., Learning algorithms with optimal stability in neural networks, J. Phys. A: Math. Gen., 20, 247-259 (1987)
[51] Krauth, W.; Mézard, M., Storage capacity of memory, networks with binary couplings, J. Phys. France, 50, 3057-3066 (1989)
[52] Krauth, W.; Opper, M., Critical storage capacity of the \(J\) = ± 1 neural network, J. Phys. A: Math. Gen., 22, 519 (1989)
[53] LeCum, Y.; Boser, B.; Denker, J. S.; Henderson, D.; Howard, R. E.; Hubbard, W.; Jackel, L. D., Back-propagation applied to handwritten zip code recognition, Neural Comput., 1, 541-551 (1989)
[54] Lippmann, R. P., An introduction to computing with neural nets, IEE ASSP Magazine (April 1987)
[55] Marchand, M.; Golea, M.; Ruján, P., A convergence theorem for sequential learning in two-layer perceptrons, Europhys. Lett., 11, 487-492 (1990)
[56] Mayoraz, E., Benchmark of some learning algorithms for single layer and Hopfield networks, Complex Systems, 4, 477-490 (1990) · Zbl 0729.68076
[57] McCulloch, W. S.; Pitts, W., A logical calculus of the ideas immanent in nervous activity, Bull. Math. Biophys., 5, 115-133 (1943) · Zbl 0063.03860
[58] Mézard, M.; Nadal, J.-P., Learning in feedforward layered networks: the tiling algorithm, J. Phys. A: Math. Gen., 22, 2191-2203 (1989)
[59] Minsky, M. L.; Papert, S., Perceptrons: An Introduction to Computational Geometry (1988), MIT Press: MIT Press Cambridge MA, Expanded edition · Zbl 0197.43702
[60] Muroga, S., Threshold Logic and Its Applications (1971), Wiley: Wiley New York · Zbl 0243.94014
[61] Nadal, J.-P., Study of a growth algorithm for a feedforward network, Int. J. Neural Systems, 1, 1, 55-59 (1989)
[62] P. Peretto, An introduction to the modeling of neural networks, in press.; P. Peretto, An introduction to the modeling of neural networks, in press. · Zbl 0770.92008
[63] Pérez Vicente, C. J.; Carrabina, J.; Valderrama, E., Learning algorithm for feedforward neural networks with discrete synapses, (Prieto, A., Lecture Notes in Computer Science 540 (1991), Springer: Springer Berlin), 144-152, Proc. IWANN’91, Grenade
[64] Peterson, C.; Södeberg, B., A new method for mapping optimization problems onto neural networks, Int. J. Neural Systems, 1, 3-22 (1989)
[65] Rosenblatt, R., Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms (1962), Spartan Books: Spartan Books New York · Zbl 0143.43504
[66] Rumelhart, D. E.; Hinton, G. E.; Williams, R. J., Learning representations by back-propagating errors, Nature, 323, 533-536 (1986) · Zbl 1369.68284
[67] Saad, D.; Marom, E., Learning by choice of internal representations: An energy minimization approach Complex Systems, 4, 107-118 (1990) · Zbl 0713.68045
[68] Sauer, N., On the density of families of sets, J. Combin. Theory (A), 13, 145-147 (1972) · Zbl 0248.05005
[69] Sejnowski, T. J.; Rosenberg, C. R., Parallel networks that learn to pronounce english text, Complex Systems, 1, 145-168 (1987) · Zbl 0655.68107
[70] Shawe-Taylor, J.; Anthony, M., Sample sizes for multiple-output threshold networks, Network, 2, 107-117 (1991) · Zbl 0724.68076
[71] Telgen, J., On relaxation methods for systems of linear inequalities, Eur. J. Oper. Res., 9, 184-189 (1982) · Zbl 0476.65041
[72] Tesauro, G.; He, Y.; Ahmad, S., Asymptotic convergence of back-propagation, Neural Comput., 1, 382-391 (1989)
[73] Valiant, L. G., A theory of the learnable, Comm. ACM, 27, 1134-1142 (1984) · Zbl 0587.68077
[74] Vapnik, V. N.; Chervonenkis, A. Y., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264-280 (1971) · Zbl 0247.60005
[75] Vapnik, V. N., Estimation of Dependences Based on Empirical Data (1982), Springer: Springer New York · Zbl 0499.62005
[76] Venkatesh, S. S., Directed drift: A new linear threshold algorithm for learning binary weights on-line, Presented at the Workshop on Neural Networks for Computing (April 1989), Snowbird: Snowbird Utah
[77] Venkatesh, S. S.; Baldi, P., Programmed interactions in higher-order neural networks: Maximum capacity, J. Complexity, 7, 316-337 (1991) · Zbl 0738.68066
[78] Wenocur, R. S.; Dudley, R. M., Some special Vapnik—Chervonenkis classes, Discrete Math., 33, 313-318 (1981) · Zbl 0459.60008
[79] Werbos, P., Beyond regression: New tools for prediction and analysis in the behavioral sciences, Ph.D. Thesis (1974), Harvard University
[80] de Werra, D.; Hertz, A., Tabu search techniques: A tutorial and an application to neural networks, OR Spektrum, 11, 131-141 (1989) · Zbl 0672.90089
[81] Widrow, B.; Hoff, M. E., Adaptative switching circuits 1960 IRE WESCON Convention Record, 4, 96-104 (1960)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.