title: Bounds on the number of hidden neurons in three-layer binary neural networks.
abstract: This paper investigates an important problem concerning the complexity of three-layer binary neural networks (BNNs) with one hidden layer. The neuron in the studied BNNs employs a hard limiter activation function with only integer weights and an integer threshold. The studies are focused on implementations of arbitrary Boolean functions which map from [0, 1]n into [0, 1]. A deterministic algorithm called set covering algorithm (SCA) is proposed for the construction of a three-layer BNN to implement an arbitrary Boolean function. The SCA is based on a unit sphere covering (USC) of the Hamming space (HS) which is chosen in advance. It is proved that for the implementation of an arbitrary Boolean function of n-variables (n > or = 3) by using SCA, [3L/2] hidden neurons are necessary and sufficient, where L is the number of unit spheres contained in the chosen USC of the n-dimensional HS. It is shown that by using SCA, the number of hidden neurons required is much less than that by using a two-parallel hyperplane method. In order to indicate the potential ability of three-layer BNNs, a lower bound on the required number of hidden neurons which is derived by using the method of estimating the Vapnik-Chervonenkis (VC) dimension is also given.
authors.affiliation: Institute of Systems Science, Academia Sinica, Beijing 100080, People's Republic of China. zhzhza@btamail.net.cn
authors.forename: Zhaozhi
authors.initials: Z
authors.lastname: Zhang
authors.forename: Xiaomin
authors.initials: X
authors.lastname: Ma
authors.forename: Yixian
authors.initials: Y
authors.lastname: Yang
mesh_terms: D016571:Neural Networks, Computer; D009474:Neurons / Q000502:physiology