A convergent algorithm for a cascade network of multiplexed dual output discrete perceptrons for linearly nonseparable classification

In this paper a new discrete perceptron model is introduced. The model forms a cascade structure and it is capable of realizing an arbitrary classification task designed by a constructive learning algorithm. The main idea is to copy a discrete perceptron neuron's output to have a complementary dual output for the neuron, and then to select, by using a multiplexer, the true output, which might be 0 or 1 depending on the given input. Hence, the problem of realization of the desired output is transformed into the realization of the selector signal of the multiplexer. In the next step, the selector signal is taken as the desired output signal for the remaining part of the network. The repeated applications of the procedure render the problem into a linearly separable one and eliminate the necessity of using the selector signal in the last step of the algorithm. The proposed modification to the discrete perceptron brings universality with the expense of getting just a slight modification in hardware implementation.

A convergent algorithm for a cascade network of multiplexed dual output discrete perceptrons for linearly nonseparable classification

In this paper a new discrete perceptron model is introduced. The model forms a cascade structure and it is capable of realizing an arbitrary classification task designed by a constructive learning algorithm. The main idea is to copy a discrete perceptron neuron's output to have a complementary dual output for the neuron, and then to select, by using a multiplexer, the true output, which might be 0 or 1 depending on the given input. Hence, the problem of realization of the desired output is transformed into the realization of the selector signal of the multiplexer. In the next step, the selector signal is taken as the desired output signal for the remaining part of the network. The repeated applications of the procedure render the problem into a linearly separable one and eliminate the necessity of using the selector signal in the last step of the algorithm. The proposed modification to the discrete perceptron brings universality with the expense of getting just a slight modification in hardware implementation.

___

  • J. Anlauf, M. Biehl, “The AdaTron: An adaptive perceptron algorithm”, Europhysics Letters, Vol. 10, pp. 687–692, 19 V. P. Roychowdhury, K. Y. Siu, T. Kailath, “Classification of linearly nonseparable patterns by linear threshold elements”, IEEE Trans. on Neural Networks, Vol. 6, pp. 318–331, 1995.
  • M. Muselli, “On convergence properties of pocket algorithm”, IEEE Trans. on Neural Networks, Vol. 8, pp. 623–629, 19 M. Marchand, M. Golea, P. Ruj´ an, “A convergence theorem for sequential learning in two-layer perceptrons”, Europhys. Lett., Vol. 11, pp. 487–492, 1990.
  • S. Young, T. Downs, “CARVE—a constructive algorithm for real-valued examples”, IEEE Trans. on Neural Networks, Vol. 9, pp. 1180–1190, 1998.
  • G. Martinelli, F. M. Mascioli, G. Bei, “Cascade neural network for binary mapping”, IEEE Trans. on Neural Networks, Vol. 4, pp. 148–150, 1993.
  • G. Martinelli, F. M. Mascioli, “Cascade perceptron”, Electronics Letters, Vol. 28, pp. 947–949, 1992. ˙I. Gen¸ c, C. G¨ uzeli¸s, “Discrete perceptron with input dependent threshold value”, in Conference on Signal Processing and its Appl., Vol. 1, pp. 36–41, Ankara–Turkey, (In Turkish), 1998.
  • M. do Carmo Nicoletti, J. R. Bertin, L. Franco, J. M. Jerez, “Constructive neural network algorithms for feedforward architectures suitable for classification tasks”, in Constructive Neural Networks, editors L. Fanco, D. A. Elizondo, J. M. Jeres, pp. 1–23, Berlin, Springer-Verlag, 2009.
  • W. Qinruo, Y. Bo, X. Yun, L. Bingru, “The hardware structure design of perceptron with FPGA implementation”, in IEEE Int. Conf on Systems, Man and Cybernetics, Vol. 1, pp. 762–767, 2003.
  • S. S ¸ahin, Y. Becerikli, S. Yazıcı, “Learning internal representations by error propagation”, in Neural Information Processing: 13th Int. Conf. ICONIP’06, editors I. King, J. Wang, L.-W. Chan, D. Wang, pp. 1105 – 1112, SpringerVerlag, 2006.
  • D. Ferrer, R. Gonz` alez, R. Fleitas, J. P. Acle, R. Canetti, “NeuroFPGA – Implementing artificial neural networks on programmable logic devices”, in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition Designers˘ g Forum (DATE˘ g04), 2004.
  • Y. Maeda, M. Wakamura, “Simultaneous perturbation learning rule for recurrent neural networks and its FPGA implementation”, IEEE Trans. on Neural Networks, Vol. 16, pp. 1664–1672, 2005.
  • O. Cadenas, G. Megson, D. Jones, “A new organization for a perceptron-based branch predictor and its FPGA implementation”, in Proceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design, 2005.
  • S. Vitabile, V. Conti, F. Gennaro, F. Sorbello, “Efficient MLP digital implementation on FPGA”, in Proceedings of the 2005 8th Euromicro conference on Digital System Design (DSD˘ g05), 2005.
  • J. Liu, D. Liang, “A survey of FPGA-based hardware implementation of ANNs”, in Proceedings of ICNN&B International Conference on Neural Networks and Brain, pp. 915–918, 2005.
  • ˙I. C. G¨oknar, M. Yıldız, S. Minaei, E. Deniz, “Neural CMOS-integrated circuit and its application to data classification”, IEEE Trans. on Neural Networks and Learning Systems, Vol. 23, pp. 717–724, 2012. D. A. Elizondo, J. O. de Lazcano-Lobato, R. Birkenhead, “Choice effect of linear separability testing methods on constructive neural network algorithms: An empirical study”, Expert Systems with Applications, Vol. 38, pp. 2330–2346, 2011.
  • M. Rosen-Zvi, I. Kanter, “Training a perceptron in a discrete weight space”, Physical Review E, Vol. 64, pp. 046109–1–9, 2001.
  • M. Frean, “A “thermal” perceptron learning rule”, Neural Computation, Vol. 4, pp. 946–957, 1992. J. L. Subirats, L. Franco, J. M. Jerez, “C-Mantec: A novel constructive neural network algorithm incorporating competition between neurons”, Neural Networks, Vol. 26, pp. 130–140, 2012.
  • M. M´ ezard, J.-P. Nadal, “Learning in feedforward layered networks: The tiling algorithm”, J. Phys. A: Math. Gen., Vol. 22, pp. 2191–2203, 1989.
  • P. Rujan, M. Marchand, “Learning by minimizing resources in neural networks”, Complex Syst., Vol. 3, pp. 229–241, 19 D. Rumelhart, G. Hinton, R. Williams, “Learning internal representations by error propagation”, in Parallel Distributer Processing: Exploration in the Microstructure of Cognition, editors D. Rumelhart, J. McClelland, chap. 3, 1986.
  • A. Wieland, “Two spirals”, Posted to ’connectionists’ mailing list, http://www.ibiblio.org/pub/academic/computerscience/neural-n etworks/programs/bench/two-spirals”, current as of June 2012.
  • S. Fahlman, C. Lebiere, “The cascade-correlation learning architecture”, in Advances in Neural Inform. Processing Syst. (NIPS), editor D. Touretzky, Vol. 2, pp. 524–532, San Mateo, CA, 1989.
  • Altera Corp., Quartus II Development Software Handbook, Vol. 1–5, California, Altera, 2007.