The upper bound of the minimal number of hidden neurons for the parity problem in binary neural networks

Binary neural networks (BNNs) have important value in many application areas.They adopt linearly separable structures,which are simple and easy to implement by hardware.For a BNN with single hidden layer,the problem of how to determine the upper bound of the number of hidden neurons has not been solved well and truly.This paper defines a special structure called most isolated samples (MIS) in the Boolean space.We prove that at least 2 n 1 hidden neurons are needed to express the MIS logical relationship in the Boolean space if the hidden neurons of a BNN and its output neuron form a structure of AND/OR logic.Then the paper points out that the n -bit parity problem is just equivalent to the MIS structure.Furthermore,by proposing a new concept of restraining neuron and using it in the hidden layer,we can reduce the number of hidden neurons to n .This result explains the important role of restraining neurons in some cases.Finally,on the basis of Hamming sphere and SP function,both the restraining neuron and the n -bit parity problem are given a clear logical meaning,and can be described by a series of logical expressions.