Computational capabilities of restricted two-layered perceptrons

Avner Priel; Marcelo Blatt; Tal Grossmann; Eytan Domany; Ido Kanter

doi:10.1103/PhysRevE.50.577

Access by Xinjiang University

Computational capabilities of restricted two-layered perceptrons

Avner Priel, Marcelo Blatt, Tal Grossmann, and Eytan Domany

Ido Kanter

Electronics Department, The Weizmann Institute of Science, Rehovot 76100, Israel

Department of Physics, Bar Ilan University, 52900 Ramat Gan, Israel

PDF

Phys. Rev. E 50, 577 – Published 1 July, 1994

DOI: https://doi.org/10.1103/PhysRevE.50.577

Abstract

We study the extent to which fixing the second-layer weights reduces the capacity and generalization ability of a two-layer perceptron. Architectures with N inputs, K hidden units, and a single output are considered, with both overlapping and nonoverlapping receptive fields. We obtain from simulations one measure of the strength of a network—its critical capacity, $α_{c}$ . Using the ansatz $τ_{med}$ ∝( $α_{c}$ -α $)^{- 2}$ to describe the manner in which the median learning time diverges as $α_{c}$ is approached, we estimate $α_{c}$ in a manner that does not depend on arbitrary impatience parameters. The chir learning algorithm is used in our simulations. For K=3 and overlapping receptive fields we show that the general machine is equivalent to the committee machine with the same architecture. For K=5 and the same connectivity the general machine is the union of four distinct networks with fixed second layer weights, of which the committee machine is the one with the highest $α_{c}$ . Since the capacity of the union of a finite set of machines equals that of the strongest constituent, the capacity of the general machine with K=5 equals that of the committee machine. We were not able to prove this for general K , but believe that it does hold. We investigated the internal representations used by different machines, and found that high correlations between the hidden units and the output reduce the capacity. Finally we studied the Boolean functions that can be realized by networks with fixed second layer weights. We discovered that two different machines implement two completely distinct sets of Boolean functions.

References (30)

See J. Hertz, A. Krogh, and R. Palmer, Introduction to the Theory of Neural Computation (Addison Wesley, Redwood City, CA, 1991); D.E. Rumelhart, J.L. McClelland, and the PDP Research Group, Parallel Distributed Processing: Exploration in the Microstructure of Cognition (MIT Press, Cambridge, MA, 1986); R.P. Lippmann, IEEE Trans. Acoust. Speech. Signal 4, 4 (1987); B. Widrow and M.A. Lehr, Proc. IEEE Vol. 78, (9) 9 (1990); B. Widrow and R. Winter, Computer 21, 25 (1988).
T. Grossman, in Advances in Neural Information Processing Systems, II, edited by D. S. Touretzky (Morgan Kaufmann, San Mateo, CA, 1991), p. 516; T. Grossman, R. Meir and E. Domany, Complex Syst. 2, 555 (1988).
D. Nabutovsky, T. Grossman and E. Domany, Complex Syst. 4, 519 (1990); T. Grossman, in Proceedings of the 17th Convention of IEEE in Israel, Ramat Gan, edited by E. Zehev (IEEE, New York, 1991), pp. 195 198.
E. Eisenstein and I. Kanter, Europhys Lett. 21, 501 (1993).
J.S. Judd, in Proceedings of the First International Conference on Neural Networks, San Diego, CA, edited by M. Caudill and C. Butler (IEEE, New York, 1987).
T.M. Cover, IEEE Trans. Electron. Comput. 14, 326 (1965).
E. Gardner, J. Phys. A 21, 257 (1988); E. Gardner and B. Derrida, 21, 271 (1988).
G.J. Mitchison and R.M. Durbin, Biol. Cybern. 60, 345 (1989).
M. Mezard and S. Patarnello (unpublished).
E. Barkai, D. Hansel and I. Kanter, Phys. Rev. Lett. 65, 18 (1990).
E. Barkai and I. Kanter, Europhys. Lett. 14, 107 (1991).
M. Griniasty and T. Grossman, Phys. Rev. A 45, 8924 (1992).
E. Barkai, D. Hansel and H. Sompolinsky, Phys. Rev. A 45, 4146 (1992).
A. Engel, H. M. Kohler, F. Tschepke, H. Vollmayr and A. Zippelius, Phys. Rev. A 45, 7590 (1992).
N.J. Nilsson, Learning Machines (McGraw Hill, New York, 1965).
P.M. Lewis II and C.L. Coates, Threshold Logic (John Wiley & Sons, New York, 1967).
M.L. Dertouzos, IEEE Trans. Electron. Comput. EC 13, 519 (1964).
G. Boffetta, R. Monasson and R. Zecchina, J. Phys. A 26, L507 (1993).
$n_{dif}$ is at least 2 since if vecS in { vecS $_{dif}$ } then - vecS also belongs to it.
D. Hansel, G. Mato and C. Meunier, Europhys. Lett. 20, 471 (1992).
H. Schwarze and J. Hertz, Europhys. Lett. 20, 375 (1992).
Calculation of the generalization error is straightforward, using Eqs. ( refEg) and ( refNRF.P). All pairs of teacher student IR's are scanned, and assigned the correct probability. This is done using the symbolic computer language mathematica. It is easy to calculate $ε_{g}$ for the most general vecε = ( $ε_{1}$ , ldots,ε $_{K}$ ) for every NRF teacher student pair; implementing any possible Boolean function from the hidden units to the output.
M. Blatt and E. Vergini, Phys. Rev. Lett. 66, 1793 (1991).
I. Kanter and H. Sompolinsky, Phys. Rev. A 35, 380 (1987).
M. Blatt, E. Domany and I. Kanter (unpublished).
Although we actually use here only the Learn12 part of the algorithm since we train only one layer, we explain the whole process for completeness' sake.
The parameter $I_{23}$ is not used in our version since we train only the first layer weights.
Various versions of the algorithm differ in the manner this unit is chosen see below. In all versions, the minimal disturbance principle / operates here on the space of IR's rather than on the space of weights as in other algorithms that use this principle.
L.F. Abbott and Thomas B. Kepler, J. Phys. A 22, L711 (1989).
Note that taking ;β → ∞ / ; in Eq. ( refprob1) means that one always picks the unit with highest ``energy" (which has probability 1, unless a redundancy occurs).

[c1] See J. Hertz, A. Krogh, and R. Palmer, Introduction to the Theory of Neural Computation (Addison Wesley, Redwood City, CA, 1991); D.E. Rumelhart, J.L. McClelland, and the PDP Research Group, Parallel Distributed Processing: Exploration in the Microstructure of Cognition (MIT Press, Cambridge, MA, 1986); R.P. Lippmann, IEEE Trans. Acoust. Speech. Signal 4, 4 (1987); B. Widrow and M.A. Lehr, Proc. IEEE Vol. 78, (9) 9 (1990); B. Widrow and R. Winter, Computer 21, 25 (1988).

[c2] T. Grossman, in Advances in Neural Information Processing Systems, II, edited by D. S. Touretzky (Morgan Kaufmann, San Mateo, CA, 1991), p. 516; T. Grossman, R. Meir and E. Domany, Complex Syst. 2, 555 (1988).

[c3] D. Nabutovsky, T. Grossman and E. Domany, Complex Syst. 4, 519 (1990); T. Grossman, in Proceedings of the 17th Convention of IEEE in Israel, Ramat Gan, edited by E. Zehev (IEEE, New York, 1991), pp. 195 198.

[c4] E. Eisenstein and I. Kanter, Europhys Lett. 21, 501 (1993).

[c5] J.S. Judd, in Proceedings of the First International Conference on Neural Networks, San Diego, CA, edited by M. Caudill and C. Butler (IEEE, New York, 1987).

[c6] T.M. Cover, IEEE Trans. Electron. Comput. 14, 326 (1965).

[c7] E. Gardner, J. Phys. A 21, 257 (1988); E. Gardner and B. Derrida, 21, 271 (1988).

[c8] G.J. Mitchison and R.M. Durbin, Biol. Cybern. 60, 345 (1989).

[c9] M. Mezard and S. Patarnello (unpublished).

[c10] E. Barkai, D. Hansel and I. Kanter, Phys. Rev. Lett. 65, 18 (1990).

[c11] E. Barkai and I. Kanter, Europhys. Lett. 14, 107 (1991).

[c12] M. Griniasty and T. Grossman, Phys. Rev. A 45, 8924 (1992).

[c13] E. Barkai, D. Hansel and H. Sompolinsky, Phys. Rev. A 45, 4146 (1992).

[c14] A. Engel, H. M. Kohler, F. Tschepke, H. Vollmayr and A. Zippelius, Phys. Rev. A 45, 7590 (1992).

[c15] N.J. Nilsson, Learning Machines (McGraw Hill, New York, 1965).

[c16] P.M. Lewis II and C.L. Coates, Threshold Logic (John Wiley & Sons, New York, 1967).

[c17] M.L. Dertouzos, IEEE Trans. Electron. Comput. EC 13, 519 (1964).

[c18] G. Boffetta, R. Monasson and R. Zecchina, J. Phys. A 26, L507 (1993).

[c19] $n_{dif}$ is at least 2 since if vecS in { vecS $_{dif}$ } then - vecS also belongs to it.

[c20] D. Hansel, G. Mato and C. Meunier, Europhys. Lett. 20, 471 (1992).

[c21] H. Schwarze and J. Hertz, Europhys. Lett. 20, 375 (1992).

[c22] Calculation of the generalization error is straightforward, using Eqs. ( refEg) and ( refNRF.P). All pairs of teacher student IR's are scanned, and assigned the correct probability. This is done using the symbolic computer language mathematica. It is easy to calculate $ε_{g}$ for the most general vecε = ( $ε_{1}$ , ldots,ε $_{K}$ ) for every NRF teacher student pair; implementing any possible Boolean function from the hidden units to the output.

[c23] M. Blatt and E. Vergini, Phys. Rev. Lett. 66, 1793 (1991).

[c24] I. Kanter and H. Sompolinsky, Phys. Rev. A 35, 380 (1987).

[c25] M. Blatt, E. Domany and I. Kanter (unpublished).

[c26] Although we actually use here only the Learn12 part of the algorithm since we train only one layer, we explain the whole process for completeness' sake.

[c27] The parameter $I_{23}$ is not used in our version since we train only the first layer weights.

[c28] Various versions of the algorithm differ in the manner this unit is chosen see below. In all versions, the minimal disturbance principle / operates here on the space of IR's rather than on the space of weights as in other algorithms that use this principle.

[c29] L.F. Abbott and Thomas B. Kepler, J. Phys. A 22, L711 (1989).

[c30] Note that taking ;β → ∞ / ; in Eq. ( refprob1) means that one always picks the unit with highest ``energy" (which has probability 1, unless a redundancy occurs).

Physical Review E

Export citation

Export citation

Computational capabilities of restricted two-layered perceptrons

Abstract

References (30)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation