Research On Some Problems Of Linearly Separable Structures In Binary Neural Networks

Binary neural networks (BNN), which is applied in Boolean space, has made considerable development so far, and has been widely used in many domains such as pattern recognition, artificial intelligence, complexity of logic synthesis, and LSI design, etc.. However, the BNN theory still has many immature aspects, which prevent it from applying to deeper and wider areas. In this dissertation, the research works are carried out to resolve some important problems of the linearly separable structures in the BNN theory, and are summarized as follows:(1) As the beginning of the studies, this dissertation describes the significance of the linearly separable structure for extracting rules from network, analyzes and summarizes the current known linearly separable structure, and points out the range of the unknown linearly separable structure. As a result, these preliminary works lay foundation for proposing the new linearly separable structure. Moreover, as for realizing the n-bit parity problem using neural network and the learning algorithms in BNN, the surveys are given and the existing problems are also pointed out simultaneously.(2) This dissertation defines a new structure called Hamming Sphere Dimple, and points out that Hamming Sphere Dimple contains linearly separable and nonlinearly separable structure, and provides a simple judgment method for linear separability. For linearly separable Hamming Sphere Dimple, the necessary and sufficient condition for the equivalence is established between the linearly separable Hamming Sphere Dimple and the binary neuron, and the logical expression is also given. As a result, a class of linearly separable structure with a clear logical meaning is added in BNN. In addition, for nonlinearly separable Hamming Sphere Dimple, according to the feature of Hamming Sphere Dimple with Hamming-Graph, this dissertation proposes an algorithm for judging whether a Boolean function is linearly or nonlinearly separable Hamming Sphere Dimple by sorting the weighted height of the true nodes, and gives its logical expression. Fortunately, the logical expression of a class of nonlinearly separable function is obtained.(3) Based on the ant colony algorithm, this dissertation, for the first time, provides two learning algorithms (HC-ABN and LC-ABN) of BNN for the connectivity of the sample to overcome the deficiency of existing learning algorithms, and gives the convergence analysis for the two algorithms. On one hand, for the sample with higher connectivity, it is shown by comparison tests that the HC-ABN algorithm is able to use a simple network to realize a given Boolean function. On the other hand, for the sample with poor connectivity, the LC-ABN algorithm, taking the n-bit parity problem as an example, gives the experience upper bound and also provides the direction for further theory analysis.(4) This dissertation proves that, using a BNN with single hidden layer adopts linearly separable structure and both its hidden neurons and output neuron form a structure of AND/OR logic, 2n-1neurons are required to implement n-bit parity problem. Furthermore, by proposing a new concept of restraining neuron and using it in the hidden layer, the number of hidden neurons is reduced to n. This result illuminates the important role of restraining neurons in BNN. In addition, on the basis of Hamming sphere and SP function, the logical expressions of the n-bit parity problem is given.(5) The dissertation extends the application of BNN to system reliability analysis. By using the learning algorithm, the relationship between system function and components can be converted to a BNN. After proving the expression of the distribution function of linear combination of0/1distribution, the reliability of the system is obtained.