二进神经网络中关于线性可分结构的若干问题研究
|
摘要
二进神经网络是应用于布尔空间的神经网络,从产生至今已经取得了长足的发展,被广泛地应用于模式识别、人工智能、复杂逻辑综合、大规模集成电路设计等方面。然而二进神经网络理论中仍有许多方面不太成熟,限制了它向更深、更广领域的应用。本文主要针对二进神经网络理论中的线性可分结构所涉及的一些重要内容进行研究,主要研究工作摘要如下：
(1)阐述了线性可分结构系对网络规则提取的研究意义,对当前已知的线性可分结构系进行了分析与总结,指出未知的线性可分结构系的范围,为提出新的线性可分结构系指明了方向；另外对于神经网络实现n元奇偶校验问题以及二进神经网络学习算法做一综述,指出了目前存在着的和还需进一步解决的问题。
(2)定义了一种新的空间结构——汉明球突,指出其存在线性可分与线性不可分两种类型,并给出是否线性可分的简洁判别法。针对线性可分的汉明球突,建立与二进神经元等价判别法,并给出其逻辑表达式,因而增加了一类具有清晰逻辑意义的线性可分结构系；针对线性不可分的汉明球突判定问题,借助汉明球突在汉明图上的几何特性,采用真节点加权高度排序的方法,提出对于任意样本是否为汉明球突的判别法,相应地给出其逻辑表达,进而给出了一类线性不可分函数的逻辑表达。
(3)根据已有学习算法的不足,首次借助蚁群算法,针对样本连通性较高与样本连通性较差的情况分别提出两种基于蚁群算法的二进神经网络学习算法(HC-ABN与LC-ABN),并给出算法的收敛性分析。对于样本连通性较高的情况,通过对比试验可知,HC-ABN算法可以采用更简单的网络结构实现给定的布尔函数；对于样本连通性较差的情况,以奇偶校验问题为例,LC-ABN算法给出了经验上界,为进一步理论分析提供了方向。
(4)证明了对采用线性可分结构、单隐层并且每个隐层神经元只表达“与”关系、所有隐层神经元通过输出元形成“或”关系的二进神经网络,需2n-1个隐层神经元才可以实现n元奇偶校验问题,但在隐层引入抑制神经元后,仅需n个隐层神经元即可以实现,说明了抑制神经元在二进神经网络中的重要作用,并在汉明球与SP函数的基础上,给出了奇偶校验的逻辑表达式。
(5)扩展二进神经网络的应用范围,将其应用于系统的可靠性分析,借助论文提出的学习算法可以将系统功能与部件间的关系转化为二进神经网络,在证明了0/1分布的线性组合的分布函数表达式的基础上,得到系统的可靠性。
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.
(1)阐述了线性可分结构系对网络规则提取的研究意义,对当前已知的线性可分结构系进行了分析与总结,指出未知的线性可分结构系的范围,为提出新的线性可分结构系指明了方向；另外对于神经网络实现n元奇偶校验问题以及二进神经网络学习算法做一综述,指出了目前存在着的和还需进一步解决的问题。
(2)定义了一种新的空间结构——汉明球突,指出其存在线性可分与线性不可分两种类型,并给出是否线性可分的简洁判别法。针对线性可分的汉明球突,建立与二进神经元等价判别法,并给出其逻辑表达式,因而增加了一类具有清晰逻辑意义的线性可分结构系；针对线性不可分的汉明球突判定问题,借助汉明球突在汉明图上的几何特性,采用真节点加权高度排序的方法,提出对于任意样本是否为汉明球突的判别法,相应地给出其逻辑表达,进而给出了一类线性不可分函数的逻辑表达。
(3)根据已有学习算法的不足,首次借助蚁群算法,针对样本连通性较高与样本连通性较差的情况分别提出两种基于蚁群算法的二进神经网络学习算法(HC-ABN与LC-ABN),并给出算法的收敛性分析。对于样本连通性较高的情况,通过对比试验可知,HC-ABN算法可以采用更简单的网络结构实现给定的布尔函数；对于样本连通性较差的情况,以奇偶校验问题为例,LC-ABN算法给出了经验上界,为进一步理论分析提供了方向。
(4)证明了对采用线性可分结构、单隐层并且每个隐层神经元只表达“与”关系、所有隐层神经元通过输出元形成“或”关系的二进神经网络,需2n-1个隐层神经元才可以实现n元奇偶校验问题,但在隐层引入抑制神经元后,仅需n个隐层神经元即可以实现,说明了抑制神经元在二进神经网络中的重要作用,并在汉明球与SP函数的基础上,给出了奇偶校验的逻辑表达式。
(5)扩展二进神经网络的应用范围,将其应用于系统的可靠性分析,借助论文提出的学习算法可以将系统功能与部件间的关系转化为二进神经网络,在证明了0/1分布的线性组合的分布函数表达式的基础上,得到系统的可靠性。
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.
引文
[1]McCulloch W, Pitts W. A logical calculus of the ideas imminent in nervous activity[J]. Bulletin of Mathematical Biophysics,1943,5:115-133
[2]Hebb D O. The Organization of Behaviour[M]. New York:Wiley,1949
[3]Rosenblatt F. The perceptron:a probabilistic model for information storage and organization in the brain[J]. Psychological Reviews,1958,65(6):386-408
[4]Widrow B, Hoff M. Adaptive switching circuit, IRE WESCON Convention record:part 4. Computers:Man-machine Systems [M]. Los Angeles, the Institute of Radio En,1960
[5]Minsky M, Papert S. Perceptrons[M]. Cambridge, MA:MIT Press,1969
[6]Kohonen T. Correlation matrix memories[J]. IEEE Transaction on Computers,1972,21: 353-359
[7]Grossberg S. Adaptive pattern classification and universal recoding:Ⅰ. parallel development and coding of neural feature detectors[J]. Biological Cybernetics,1972,23:121-134
[8]Hopfield J. Neural networks and physical systems with emergent collective computational abilities[J]. Proeeeding Nation Academy Science USA,1982,79(8):2554-2558
[9]Hopfield J. Neurons with graded response have collective computational properties like those of two-stage neurons[J]. Proeeeding Nation Academy Science USA,1984,81(10):3088-3092
[10]Tank D, Hopfield J. Simple neural optimization networks:An A/D converter, signal decision circuit and a linear programming circuit[J]. IEEE Transactions on Circuits and Systems I, 1986,33(5):533-541
[11]Rumelhart D, Hinton G, Williams R. Learning representations by back propagating errors[J]. Nature,1986,323(9):533-536
[12]Funahashi K. On the approximate realization of continuous mappings by neural networks[J]. Neural Networks,1989(2):182-192
[13]Cybenko G. Approximation by superpositions of a sigmoidal function[J]. Mathematics of Control, Signals and Systems,1989(2):303-314
[14]Jagesh V.Shah, Chi-Sang Poon. Linear independence of internal representations in multilayer perceptrons[J]. IEEE Trans. on Neural Networks,1999,10(1):10-18
[15]Hornik K. Approximation capability of multilayer feedforward networks[J]. Neural Networks, 1991(4):251-257
[16]Stinchocombe M, White H. Universal approximation using feedfoward networks with non-sgmoidal hidden layers activation function[C]. Proceedings of 1989 International Joint Conference on Neural Networks,1989(1):613-617
[17]张军英,许进.二进前向人工神经网络——理论与应用[M].西安：西安电子科技大学出版社,2001
[18]陆阳.二进神经网络规则提取方法研究[D].合肥：合肥工业大学,2002
[19]焦李成.神经网络系统理论[M].西安：西安电子科技大学出版社,1990
[20]陆阳,韩江洪,张维勇.二进神经网络逻辑关系判据及等价性规则提取[J].模式识别与人工智能,2001,14(2)：171-176
[21]陆阳,魏臻,高隽,韩江洪.二进神经网络中汉明球的逻辑意义及一般判别方法[J].计算机研究与发展,2002,3(1)：79-86
[22]Lu Yang, Han Jianghong, Wei Zhen. A general judging and constructing method of SP functions in binary neural networks[J]. Acta Automatica Sinica,2003,29(2):234-241
[23]陆阳,韩江洪,张维勇.二进神经网络中笛卡尔球的研究[J].模式识别与人工智能,2004,17(3)：368-373
[24]杨娟,陆阳,黄振谨,王强.二进神经网络中的汉明球突及其线性可分性[J].自动化学报,2011,37(6)：737-745
[25]Chen Fang-yue, Chen Guan-rong, He Guolong, Xu Xiubin, He Qin-bin. Universal perceptron and DNA-like learning algorithm for binary neural networks:LSBF and PBF implementations[J]. IEEE Transaction on Neural Network,2009,20(10):1645-1658
[26]Chua L O. Visions of Nonlinear Science in the 21st Century in CNN:A Paradigm for Complexity[M]. Singapore:World Scientific,1999
[27]Kim J H, Park S. The geometrical learning of binary neural networks[J]. IEEE Transaction on Neural Networks,1995,6(1):237-247
[28]陆阳,韩江洪,高隽.二进神经网络隐元数目最小上届研究[J].模式识别与人工智能,2000,1(3)：254-257
[29]Chen Fang-yue, He Guo-long, Chen Guan-rong. Realization of Boolean functions via CNN mathematical theory, LSBF and template design[J]. IEEE Transactions on Circuits and Systems,2006,53(10):2203-2213
[30]Branislav Hruz. Unateness Test of a Boolean Function and Two General Synthesis Methods Using Threshold Logic Elements[J]. IEEE Transactions on Computers,1969, C18(2):122-131
[31]袁曾任.人工神经元及其应用[M].北京：清华大学出版社,1999
[32]Fangyue Chen. Realization and bifurcation of Boolean functions via cellular neural networks[J]. International Journal of Bifurcation and Chaos,2005,15(7):2109-2129
[33]Fangyue Chen, Guolong He. Realization of Boolean functions via CNN with von Neumann neighbourhoods[J]. International Journal of Bifurcation and Chaos,2006,16(5):1389-1403
[34]Bo Mi, Xiaofeng Liao, Chuandong Li. Identification and realization of linearly separable Boolean functions via cellular neural networks[J]. International Journal of Bifurcation and Chaos,2008,18(11):3299-3308
[35]马晓敏,杨义先,章照止.一种新的阈值函数的分析框架及有关结论[J].计算机学报,2000,23(3)：225-230
[36]Wegener I. The Complexity of Boolean Function[M]. New York:Wiley,1987
[37]Counse K R, Fung E L, Chua L A. Efficient implementation of neighbourhood logic for cellular automata via the cellular neural network universal machine[J]. IEEE Transactions on Circuits System,1997,44(4):355-361
[38]Nemes L, Chua L O, Rolka T. Implementation of arbitrary Boolean function on a CNN universal machine[J]. International Journal of Circuit Theory and Applications,1998,26(6): 593-610
[39]Harykin S. Neural Networks:A Comprehensive Foundation(Second Edition)[M]. New Jersey: Prentice Hall,1998
[40]Negnevitsky M. Artificial Intelligence:A Guide to Intelligence Systems(Second Edition)[M]. New Jersey:Addision Wesley,2004
[41]Hassoun M H. Fundamentals of Artificial Neural Networks[M]. Massachusetts:The MIT Press,1995
[42]Gray D L, Michel A N. A training algorithm for binary feedforward neural networks[J]. IEEE Transactions on Neural Network,1992,3(2):176-194
[43]Chen Fang-yue, Chen Guan-rong, He Qingbin. On CNN universal perceptron[C]. Proceedings of 2010 International Workshop on Cellular Nanoscale Networks and Their Applications(CNNA).2010:1-6
[44]Chen Fang-Yue, Chen Guan-Rong, He Qin-Bin. Universal perceptron and DNA-like learning algorithm of binary neural networks:Non-LSBF decomposition[J]. IEEE Transaction on Neural Networks, under review
[45]Atsushi Yamamoto, Toshimichi Saito. An improved expand-and-truncate learning[C]. Proceedings of 1997 IEEE International Conference on Neural Networks,1997:1111-1116
[46]马晓敏,杨义先,章照止.二进神经网络学习算法研究[J].计算机学报,1999,22(9)：931-935
[47]Ma Xiaomin, Yang Yixian, Zhang Zhaozhi. Constructive learning of binary neural networks and its application to nonlinear register synthesisfC]. Proceedings of 2001 International Conference on Neural Information(ICONIP'01),2001,1:90-95
[48]Di Wang, N.S.Chaudhari. A multi-core learning algorithm for binary neural networks[C]. Proceedings of 2003 International Joint Conference on Neural Networks,2003,1:450-455
[49]Di Wang, Narendra S. Chaudhari. Binary neural network training algorithms based on linear sequential learning[J]. International Journal of Neural Systems,2003,13(5):333-351
[50]Di Wang, Narendra S. Chaudhari. An approach for construction of Boolean neural networks based on geometrical expansion[J]. Neurocomputing,2004,57:455-461
[51]Di Wang, Narendra S. Chaudhari, Jagdish C.Patra. A constructive unsupervised learning algorithm for clustering binary patterns[C]. Proceedings of 2004 International Joint Conference on Neural Networks,2004,2:1381-1385
[52]Di Wang, Narendra S. Chaudhari. A fast modified constructive-covering algorithm for binary multi-layer neural networks[J]. Neurocomputing,2006,70(1-3):445-461
[53]Setiono, R.On the solution of the parity problem by a single hidden layer feedforward neural network[J]. Neurocomputing,1997,16(3):225-235
[54]D.G.Stork, J.D.Allen. How to solve the N-bit parity problem with two hidden units[J]. Neural Networks,1992,5:923-926
[55]Brown D.A. N-bit parity networks[J]. Neural Networks,1993,6:607-608
[56]Minor J.M. Parity with two layer feedforward nets[J]. Neural Networks,1993,6:705-707
[57]Myron E.Hohil, Derong Liu, Stanley H.Smith. Solving the N-bit parity problem using neural networks[J]. Neural Networks,1999,12:1321-1323
[58]Fung H.K., L.K. Li. Minimal feedforward parity networks using threshold gates[J]. Neural Computation,2001,13(2):319-326
[59]Zhaozhi Zhang, Xiaomin Ma, Yixian Yang. Bounds on the number of hidden neurons in three-layer binary neural networks[J]. Neural Networks,2003,16:995-1002
[60]Erhan Oztop. An upper bound on the minimum number of monomials required to separate dichotomies of{-1, 1}n[J]. Neural Computation,2006,18(12):3119-3138
[61]Erhan Oztop. Sign-representation of Boolean functions using a small number of monomials[J]. Neural Networks,2009,22(7):938-948
[62]Chao Zhang, Jie Yang, Wei Wu. Binary higher order neural networks for realizing Boolean functions[J]. IEEE Transaction on Neural Networks,2011,22(5):701-713
[63]Lu Yang, Yang Juan, Wang Qiang, Huang Zhenjin. The upper bound of the minimal number of hidden nodes in parity problem by neural networks[J]. Science China Information Sciences,2012,55(7):1579-1587
[64]华强,郑启伦.二进神经网络的汉明图学习算法[J].计算机学报,2001,24(11)：1250-1255
[65]Thuan Q. Huynh, James A.Reggia. Guiding hidden layer representations for improved rule extraction from neural networks[J]. IEEE Transactions on Neural Networks,2011,22(2): 264-275
[66]J.Diederich, A.B.Tickle, S.Geva. Quo Vadis. Relaibale and Practical rule extraction from Neural Networks[J]. Advances in Machine Learning I, Studies in Computational Intelligence, 2010,262:479-490
[67]周志华,陈世福.神经网络规则抽取[J].计算机研究与发展.2002,39(4)：398405
[68]周志华,何佳州,尹旭日.一种基于统计的神经网络规则提取方法[J].软件学报,2001,12(2)：263-269
[69]陈果.一种基于功能性观点的神经网络规则提取方法[J].模式识别与人工智能,2008,21(6)：787-793
[70]R.Setiono. Extracting M-of-N rules from trained neural networks[J]. IEEE Transactions on Neural Networks,2001,11:306-512
[71]S.Bader, S.Holldobler, B.Mayer-Eichberger. Extracting propositional rules from feed-forward neural networks:a new decompositional approach[C]. Proceedings of the IJCAI-07 Workshop on Neural-Symbolic Learning and Reasoning, NeSy'07,2007:1-6
[72]S.Bader. Extracing Propositional rules from feed-forward neural network by means of binary decision diagrams[C]. Proceedings of the 2009 International Workshop on Neural-Symbolic Learning and Reasoning,2009:22-27
[73]Darbari. Rule extraction from trained ANN:A Survey[R]. Institute of Artificial Intelligence, Dept. of Computer Science, TU Dresden, Germany Tech. report 2001
[74]Norbert Tsopze, Engelbert Mephu Nguifo, Gilbert Tindo. Towards a generalization of decompositional approach of rule extraction from multilayer artificial neural network[C]. Proceedings of 2011 International Joint Conference on Neural Networks,2011:1562-1569
[75]Changbing Tang, Fangyue Chen, Xiang Li. Perceptron implementation of Triple-Valued logic operations[J]. IEEE Transaction on Circuits and Systems-II:Express Brief,2011,58(9): 590-594
[76]吕伟锋,林弥,孙玲玲.基于复数权神经元的布尔函数稳健学习算法[J].电子学报,2011,39(11)：2708-2712
[77]Naredra S. Chaudhari, Aruna Tiwari. Binary Neural Network classifier and it's bound for the number of hidden layer neurons[C]. Proceedings of 2010 International conference on Control Automation Robotics and Vision,2010:1-10
[78]Di Wang. Fast constructive-covering algorithm for neural networks and its implement in classification[J]. Applied Soft Computing,2008,8:166-173
[79]Masanori Shimada, Toshimichi Satio. A GA-based learning algorithm for binary neural networks[J]. IEICE Trans. Fundamentals.2002, E85-A(11):2544-2546
[80]Tatsuya Hirane, Tetsuya Toryu, Hidehiro Nakano, Arata Miyauchi. Analysis for Characteristics of GA-Based Learning Method of Binary Neural Networks[J]. ICANN,2005, LNCS 3696,323-329
[81]马晓敏,杨义先,章照止.一个新的二进神经网络学习算法及布尔函数优化实现[J].电子学报,1999,27(12)：110-112
[82]Takashi Yamamich, Toshimichi Saito, Hiroyuki Torkai. Genetic learning of digital three-layer perceptrons for implementation of binary neural cellular automata[C]. Proceedings of 2006 IEEE Congress on Evolutionary Computation,2006:2952-2957
[83]Shutaro Kabeya, Tohru Abe, Toshimichi Saito. A GA-based flexible learning algorithm with error tolerance for digital binary neural networks[C]. Proceedings of 2009 International Joint Conference on Neural Networks,2009:1476-1480
[84]高尚,杨静宇.群智能算法及其应用[M].北京：中国水利水电出版社,2006
[85]Dorigo M, Maniezzo V, Colorni A. The ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B,1996,26(1):29-41
[86]Dorgo M, Gambardella L M. Ant colony system:A cooperative learning approach to the travelling salesman problem[J]. IEEE Transactions on Evolutionary Computation,1997,1(1): 53-66
[87]Gambardella L M, Taillard E D, Dorigo M. Ant colonies for the quadratic assignment problem[J]. Journal of the Operational Research Society,1999,50(2):167-176
[88]Ventresca M, Ombuki B. Ant colony optimization for job shop scheduling problem[C]. Proceedings of the Eighth IASTED International Conference on Artificial Intelligence and Soft Computing,2004,28-34
[89]Zhou P, Li X P, Zhang H F. An ant colony algorithm for job shop scheduling problem[C]. Proceedings of 2004 World Congress on Intelligence Control and Automation(WCICA),2004: 2899-2903
[90]Yu Y X, Zhang X R. Optimization algorithm for multiple choice knapsack problem based on ant colony system[J]. Computer Engineering,2003,29(20):75
[91]Parra H R, Dimopculos N. On the performance of the ant colony system for solving the multidimensional knapsack problem[C]. Proceedings of 2003 IEEE Pacific RIM Conference on Communications, Computers and Signal Processing,2003:338-341
[92]张军英,梁军利,保铮.强混叠模式下基于神经元捕获／抑制原理的分类器设计[J].电子学报,2006,34(12)：2154-2160
[93]Eduardo Masato Iyoda, Hajime Nobuhara, Kaoru Hirota. A Solution for the N-bit Parity Problem Using a Single Translated Multiplicative Neuron[J]. Neural Processing Letters,2003, 18:213-218
[94]Shen Yuanjun, Wang Bingwen. A fast learning algorithm of neural network with tunable activation function[J]. Science in China Ser.F Information Sciences,2004:47(1):126-136
[95]Marek Grochowski, Wlodzislaw Duch. Learning Highly Non-separable Boolean Functions Using Constructive Feedforward Neural Network[J]. Artificial neural networks-ICANN, 2007:180-89
[96]E.Lavtrtsky. On the exact solution of the Parity-N problem using ordered neural networks[J]. Neural Networks,2000,13:643-649
[97]Bodgan M. Wilamowski, David Hunter, Aleksander Malinowski. Solving Parity-N Problems with Feedforward Neural Networks[J]. Neural Networks,2003,4:2546-2551
[98]Derong Liu, Myron E.Hohil, Stanley H.Smith. N-bit parity neural networks:new solutions based on linear programming[J]. Neurocomputing,2002,48:477-488
[99]Claudio Moraga. Design of Neural Networks[J]. Lecture Notes in Computer Science,2007, 4692:26-33
[100]Wlodzislaw Duch. K-Separability[J]. Lecture Notes in Computer Science,2006,4131: 188-197
[101]Huang S C, Huang Y F. Bonnds on the Number of Hidden Neurons in Multilayer Perceptrons[J]. IEEE Trans on Neural Networks,1991,2(1):47-55
[102]Tohru Abe, Toshimichi Saito. An Approach to Prediction of Spatio-Temporal Patterns based on Binary Neural Networks and Cellular Automata[C]. Proceedings of 2008 International Joint Conference on Neural Networks,2008:2494-2499
[103]田华,陈森林,张军英.前向神经网络的分类能力的实验研究[J].微电子学与计算机,2004,21(7)：99-101
[104]刘文举.关于三层前馈神经网络隐层构建问题的研究[J].计算机研究与发展,2004,41(4)：524-530
[105]S. Harding, J.F.Miller, W.Banzhaf. Selfmodifying Cartesian genetic programming:parity[C]. Proceedings of 2009 conference on Congress on Evolutionary Computation,2009:285-292
[106]Laprie J C. Dependability:Basic Concepts and Terminology[M]. Vienna:Springer-Verlag, 1990
[107]Mitchell C, Stavridou V. Mathematics of Dependable Systems[M]. Oxford:Clarendon Press, 1995
[108]曹晋华,程侃.可靠性数学引论[M].北京：高等教育出版社,2005
[109]G. Chaudhuri, K.Hu, N. Afshar. A new approach to system reliability[J]. IEEE Transactions on reliability,2001,50:75-84
[110]Min-Sheng Lin. An O(k2log(n)) Algorithm for computing the reliability of consecutive-k-out-of-n:F systems[J]. IEEE Transactions on reliability,2004,53:3-6
[111]Suprasad V. Amari, Ming J. Zuo, Glenn Dill. A fast and robust reliability evaluation algorithm for generalized multi-state k-out-of-n system[J]. IEEE Transactions on reliability,2009,58: 88-97
[112]Amir Azaron, Hideki Katagiri, Masatoshi Sakawa, Mohammad Modarres. Reliability function of a class of time-dependent systems with standby redundancy [J]. European Journal of Operational Research,2005,164:378-386
[113]Igor Aizenberg. Solving the XOR and parity N problems using a single universal binary neuron[J]. Soft Computing,2007,22(3):215-222
[2]Hebb D O. The Organization of Behaviour[M]. New York:Wiley,1949
[3]Rosenblatt F. The perceptron:a probabilistic model for information storage and organization in the brain[J]. Psychological Reviews,1958,65(6):386-408
[4]Widrow B, Hoff M. Adaptive switching circuit, IRE WESCON Convention record:part 4. Computers:Man-machine Systems [M]. Los Angeles, the Institute of Radio En,1960
[5]Minsky M, Papert S. Perceptrons[M]. Cambridge, MA:MIT Press,1969
[6]Kohonen T. Correlation matrix memories[J]. IEEE Transaction on Computers,1972,21: 353-359
[7]Grossberg S. Adaptive pattern classification and universal recoding:Ⅰ. parallel development and coding of neural feature detectors[J]. Biological Cybernetics,1972,23:121-134
[8]Hopfield J. Neural networks and physical systems with emergent collective computational abilities[J]. Proeeeding Nation Academy Science USA,1982,79(8):2554-2558
[9]Hopfield J. Neurons with graded response have collective computational properties like those of two-stage neurons[J]. Proeeeding Nation Academy Science USA,1984,81(10):3088-3092
[10]Tank D, Hopfield J. Simple neural optimization networks:An A/D converter, signal decision circuit and a linear programming circuit[J]. IEEE Transactions on Circuits and Systems I, 1986,33(5):533-541
[11]Rumelhart D, Hinton G, Williams R. Learning representations by back propagating errors[J]. Nature,1986,323(9):533-536
[12]Funahashi K. On the approximate realization of continuous mappings by neural networks[J]. Neural Networks,1989(2):182-192
[13]Cybenko G. Approximation by superpositions of a sigmoidal function[J]. Mathematics of Control, Signals and Systems,1989(2):303-314
[14]Jagesh V.Shah, Chi-Sang Poon. Linear independence of internal representations in multilayer perceptrons[J]. IEEE Trans. on Neural Networks,1999,10(1):10-18
[15]Hornik K. Approximation capability of multilayer feedforward networks[J]. Neural Networks, 1991(4):251-257
[16]Stinchocombe M, White H. Universal approximation using feedfoward networks with non-sgmoidal hidden layers activation function[C]. Proceedings of 1989 International Joint Conference on Neural Networks,1989(1):613-617
[17]张军英,许进.二进前向人工神经网络——理论与应用[M].西安：西安电子科技大学出版社,2001
[18]陆阳.二进神经网络规则提取方法研究[D].合肥：合肥工业大学,2002
[19]焦李成.神经网络系统理论[M].西安：西安电子科技大学出版社,1990
[20]陆阳,韩江洪,张维勇.二进神经网络逻辑关系判据及等价性规则提取[J].模式识别与人工智能,2001,14(2)：171-176
[21]陆阳,魏臻,高隽,韩江洪.二进神经网络中汉明球的逻辑意义及一般判别方法[J].计算机研究与发展,2002,3(1)：79-86
[22]Lu Yang, Han Jianghong, Wei Zhen. A general judging and constructing method of SP functions in binary neural networks[J]. Acta Automatica Sinica,2003,29(2):234-241
[23]陆阳,韩江洪,张维勇.二进神经网络中笛卡尔球的研究[J].模式识别与人工智能,2004,17(3)：368-373
[24]杨娟,陆阳,黄振谨,王强.二进神经网络中的汉明球突及其线性可分性[J].自动化学报,2011,37(6)：737-745
[25]Chen Fang-yue, Chen Guan-rong, He Guolong, Xu Xiubin, He Qin-bin. Universal perceptron and DNA-like learning algorithm for binary neural networks:LSBF and PBF implementations[J]. IEEE Transaction on Neural Network,2009,20(10):1645-1658
[26]Chua L O. Visions of Nonlinear Science in the 21st Century in CNN:A Paradigm for Complexity[M]. Singapore:World Scientific,1999
[27]Kim J H, Park S. The geometrical learning of binary neural networks[J]. IEEE Transaction on Neural Networks,1995,6(1):237-247
[28]陆阳,韩江洪,高隽.二进神经网络隐元数目最小上届研究[J].模式识别与人工智能,2000,1(3)：254-257
[29]Chen Fang-yue, He Guo-long, Chen Guan-rong. Realization of Boolean functions via CNN mathematical theory, LSBF and template design[J]. IEEE Transactions on Circuits and Systems,2006,53(10):2203-2213
[30]Branislav Hruz. Unateness Test of a Boolean Function and Two General Synthesis Methods Using Threshold Logic Elements[J]. IEEE Transactions on Computers,1969, C18(2):122-131
[31]袁曾任.人工神经元及其应用[M].北京：清华大学出版社,1999
[32]Fangyue Chen. Realization and bifurcation of Boolean functions via cellular neural networks[J]. International Journal of Bifurcation and Chaos,2005,15(7):2109-2129
[33]Fangyue Chen, Guolong He. Realization of Boolean functions via CNN with von Neumann neighbourhoods[J]. International Journal of Bifurcation and Chaos,2006,16(5):1389-1403
[34]Bo Mi, Xiaofeng Liao, Chuandong Li. Identification and realization of linearly separable Boolean functions via cellular neural networks[J]. International Journal of Bifurcation and Chaos,2008,18(11):3299-3308
[35]马晓敏,杨义先,章照止.一种新的阈值函数的分析框架及有关结论[J].计算机学报,2000,23(3)：225-230
[36]Wegener I. The Complexity of Boolean Function[M]. New York:Wiley,1987
[37]Counse K R, Fung E L, Chua L A. Efficient implementation of neighbourhood logic for cellular automata via the cellular neural network universal machine[J]. IEEE Transactions on Circuits System,1997,44(4):355-361
[38]Nemes L, Chua L O, Rolka T. Implementation of arbitrary Boolean function on a CNN universal machine[J]. International Journal of Circuit Theory and Applications,1998,26(6): 593-610
[39]Harykin S. Neural Networks:A Comprehensive Foundation(Second Edition)[M]. New Jersey: Prentice Hall,1998
[40]Negnevitsky M. Artificial Intelligence:A Guide to Intelligence Systems(Second Edition)[M]. New Jersey:Addision Wesley,2004
[41]Hassoun M H. Fundamentals of Artificial Neural Networks[M]. Massachusetts:The MIT Press,1995
[42]Gray D L, Michel A N. A training algorithm for binary feedforward neural networks[J]. IEEE Transactions on Neural Network,1992,3(2):176-194
[43]Chen Fang-yue, Chen Guan-rong, He Qingbin. On CNN universal perceptron[C]. Proceedings of 2010 International Workshop on Cellular Nanoscale Networks and Their Applications(CNNA).2010:1-6
[44]Chen Fang-Yue, Chen Guan-Rong, He Qin-Bin. Universal perceptron and DNA-like learning algorithm of binary neural networks:Non-LSBF decomposition[J]. IEEE Transaction on Neural Networks, under review
[45]Atsushi Yamamoto, Toshimichi Saito. An improved expand-and-truncate learning[C]. Proceedings of 1997 IEEE International Conference on Neural Networks,1997:1111-1116
[46]马晓敏,杨义先,章照止.二进神经网络学习算法研究[J].计算机学报,1999,22(9)：931-935
[47]Ma Xiaomin, Yang Yixian, Zhang Zhaozhi. Constructive learning of binary neural networks and its application to nonlinear register synthesisfC]. Proceedings of 2001 International Conference on Neural Information(ICONIP'01),2001,1:90-95
[48]Di Wang, N.S.Chaudhari. A multi-core learning algorithm for binary neural networks[C]. Proceedings of 2003 International Joint Conference on Neural Networks,2003,1:450-455
[49]Di Wang, Narendra S. Chaudhari. Binary neural network training algorithms based on linear sequential learning[J]. International Journal of Neural Systems,2003,13(5):333-351
[50]Di Wang, Narendra S. Chaudhari. An approach for construction of Boolean neural networks based on geometrical expansion[J]. Neurocomputing,2004,57:455-461
[51]Di Wang, Narendra S. Chaudhari, Jagdish C.Patra. A constructive unsupervised learning algorithm for clustering binary patterns[C]. Proceedings of 2004 International Joint Conference on Neural Networks,2004,2:1381-1385
[52]Di Wang, Narendra S. Chaudhari. A fast modified constructive-covering algorithm for binary multi-layer neural networks[J]. Neurocomputing,2006,70(1-3):445-461
[53]Setiono, R.On the solution of the parity problem by a single hidden layer feedforward neural network[J]. Neurocomputing,1997,16(3):225-235
[54]D.G.Stork, J.D.Allen. How to solve the N-bit parity problem with two hidden units[J]. Neural Networks,1992,5:923-926
[55]Brown D.A. N-bit parity networks[J]. Neural Networks,1993,6:607-608
[56]Minor J.M. Parity with two layer feedforward nets[J]. Neural Networks,1993,6:705-707
[57]Myron E.Hohil, Derong Liu, Stanley H.Smith. Solving the N-bit parity problem using neural networks[J]. Neural Networks,1999,12:1321-1323
[58]Fung H.K., L.K. Li. Minimal feedforward parity networks using threshold gates[J]. Neural Computation,2001,13(2):319-326
[59]Zhaozhi Zhang, Xiaomin Ma, Yixian Yang. Bounds on the number of hidden neurons in three-layer binary neural networks[J]. Neural Networks,2003,16:995-1002
[60]Erhan Oztop. An upper bound on the minimum number of monomials required to separate dichotomies of{-1, 1}n[J]. Neural Computation,2006,18(12):3119-3138
[61]Erhan Oztop. Sign-representation of Boolean functions using a small number of monomials[J]. Neural Networks,2009,22(7):938-948
[62]Chao Zhang, Jie Yang, Wei Wu. Binary higher order neural networks for realizing Boolean functions[J]. IEEE Transaction on Neural Networks,2011,22(5):701-713
[63]Lu Yang, Yang Juan, Wang Qiang, Huang Zhenjin. The upper bound of the minimal number of hidden nodes in parity problem by neural networks[J]. Science China Information Sciences,2012,55(7):1579-1587
[64]华强,郑启伦.二进神经网络的汉明图学习算法[J].计算机学报,2001,24(11)：1250-1255
[65]Thuan Q. Huynh, James A.Reggia. Guiding hidden layer representations for improved rule extraction from neural networks[J]. IEEE Transactions on Neural Networks,2011,22(2): 264-275
[66]J.Diederich, A.B.Tickle, S.Geva. Quo Vadis. Relaibale and Practical rule extraction from Neural Networks[J]. Advances in Machine Learning I, Studies in Computational Intelligence, 2010,262:479-490
[67]周志华,陈世福.神经网络规则抽取[J].计算机研究与发展.2002,39(4)：398405
[68]周志华,何佳州,尹旭日.一种基于统计的神经网络规则提取方法[J].软件学报,2001,12(2)：263-269
[69]陈果.一种基于功能性观点的神经网络规则提取方法[J].模式识别与人工智能,2008,21(6)：787-793
[70]R.Setiono. Extracting M-of-N rules from trained neural networks[J]. IEEE Transactions on Neural Networks,2001,11:306-512
[71]S.Bader, S.Holldobler, B.Mayer-Eichberger. Extracting propositional rules from feed-forward neural networks:a new decompositional approach[C]. Proceedings of the IJCAI-07 Workshop on Neural-Symbolic Learning and Reasoning, NeSy'07,2007:1-6
[72]S.Bader. Extracing Propositional rules from feed-forward neural network by means of binary decision diagrams[C]. Proceedings of the 2009 International Workshop on Neural-Symbolic Learning and Reasoning,2009:22-27
[73]Darbari. Rule extraction from trained ANN:A Survey[R]. Institute of Artificial Intelligence, Dept. of Computer Science, TU Dresden, Germany Tech. report 2001
[74]Norbert Tsopze, Engelbert Mephu Nguifo, Gilbert Tindo. Towards a generalization of decompositional approach of rule extraction from multilayer artificial neural network[C]. Proceedings of 2011 International Joint Conference on Neural Networks,2011:1562-1569
[75]Changbing Tang, Fangyue Chen, Xiang Li. Perceptron implementation of Triple-Valued logic operations[J]. IEEE Transaction on Circuits and Systems-II:Express Brief,2011,58(9): 590-594
[76]吕伟锋,林弥,孙玲玲.基于复数权神经元的布尔函数稳健学习算法[J].电子学报,2011,39(11)：2708-2712
[77]Naredra S. Chaudhari, Aruna Tiwari. Binary Neural Network classifier and it's bound for the number of hidden layer neurons[C]. Proceedings of 2010 International conference on Control Automation Robotics and Vision,2010:1-10
[78]Di Wang. Fast constructive-covering algorithm for neural networks and its implement in classification[J]. Applied Soft Computing,2008,8:166-173
[79]Masanori Shimada, Toshimichi Satio. A GA-based learning algorithm for binary neural networks[J]. IEICE Trans. Fundamentals.2002, E85-A(11):2544-2546
[80]Tatsuya Hirane, Tetsuya Toryu, Hidehiro Nakano, Arata Miyauchi. Analysis for Characteristics of GA-Based Learning Method of Binary Neural Networks[J]. ICANN,2005, LNCS 3696,323-329
[81]马晓敏,杨义先,章照止.一个新的二进神经网络学习算法及布尔函数优化实现[J].电子学报,1999,27(12)：110-112
[82]Takashi Yamamich, Toshimichi Saito, Hiroyuki Torkai. Genetic learning of digital three-layer perceptrons for implementation of binary neural cellular automata[C]. Proceedings of 2006 IEEE Congress on Evolutionary Computation,2006:2952-2957
[83]Shutaro Kabeya, Tohru Abe, Toshimichi Saito. A GA-based flexible learning algorithm with error tolerance for digital binary neural networks[C]. Proceedings of 2009 International Joint Conference on Neural Networks,2009:1476-1480
[84]高尚,杨静宇.群智能算法及其应用[M].北京：中国水利水电出版社,2006
[85]Dorigo M, Maniezzo V, Colorni A. The ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B,1996,26(1):29-41
[86]Dorgo M, Gambardella L M. Ant colony system:A cooperative learning approach to the travelling salesman problem[J]. IEEE Transactions on Evolutionary Computation,1997,1(1): 53-66
[87]Gambardella L M, Taillard E D, Dorigo M. Ant colonies for the quadratic assignment problem[J]. Journal of the Operational Research Society,1999,50(2):167-176
[88]Ventresca M, Ombuki B. Ant colony optimization for job shop scheduling problem[C]. Proceedings of the Eighth IASTED International Conference on Artificial Intelligence and Soft Computing,2004,28-34
[89]Zhou P, Li X P, Zhang H F. An ant colony algorithm for job shop scheduling problem[C]. Proceedings of 2004 World Congress on Intelligence Control and Automation(WCICA),2004: 2899-2903
[90]Yu Y X, Zhang X R. Optimization algorithm for multiple choice knapsack problem based on ant colony system[J]. Computer Engineering,2003,29(20):75
[91]Parra H R, Dimopculos N. On the performance of the ant colony system for solving the multidimensional knapsack problem[C]. Proceedings of 2003 IEEE Pacific RIM Conference on Communications, Computers and Signal Processing,2003:338-341
[92]张军英,梁军利,保铮.强混叠模式下基于神经元捕获／抑制原理的分类器设计[J].电子学报,2006,34(12)：2154-2160
[93]Eduardo Masato Iyoda, Hajime Nobuhara, Kaoru Hirota. A Solution for the N-bit Parity Problem Using a Single Translated Multiplicative Neuron[J]. Neural Processing Letters,2003, 18:213-218
[94]Shen Yuanjun, Wang Bingwen. A fast learning algorithm of neural network with tunable activation function[J]. Science in China Ser.F Information Sciences,2004:47(1):126-136
[95]Marek Grochowski, Wlodzislaw Duch. Learning Highly Non-separable Boolean Functions Using Constructive Feedforward Neural Network[J]. Artificial neural networks-ICANN, 2007:180-89
[96]E.Lavtrtsky. On the exact solution of the Parity-N problem using ordered neural networks[J]. Neural Networks,2000,13:643-649
[97]Bodgan M. Wilamowski, David Hunter, Aleksander Malinowski. Solving Parity-N Problems with Feedforward Neural Networks[J]. Neural Networks,2003,4:2546-2551
[98]Derong Liu, Myron E.Hohil, Stanley H.Smith. N-bit parity neural networks:new solutions based on linear programming[J]. Neurocomputing,2002,48:477-488
[99]Claudio Moraga. Design of Neural Networks[J]. Lecture Notes in Computer Science,2007, 4692:26-33
[100]Wlodzislaw Duch. K-Separability[J]. Lecture Notes in Computer Science,2006,4131: 188-197
[101]Huang S C, Huang Y F. Bonnds on the Number of Hidden Neurons in Multilayer Perceptrons[J]. IEEE Trans on Neural Networks,1991,2(1):47-55
[102]Tohru Abe, Toshimichi Saito. An Approach to Prediction of Spatio-Temporal Patterns based on Binary Neural Networks and Cellular Automata[C]. Proceedings of 2008 International Joint Conference on Neural Networks,2008:2494-2499
[103]田华,陈森林,张军英.前向神经网络的分类能力的实验研究[J].微电子学与计算机,2004,21(7)：99-101
[104]刘文举.关于三层前馈神经网络隐层构建问题的研究[J].计算机研究与发展,2004,41(4)：524-530
[105]S. Harding, J.F.Miller, W.Banzhaf. Selfmodifying Cartesian genetic programming:parity[C]. Proceedings of 2009 conference on Congress on Evolutionary Computation,2009:285-292
[106]Laprie J C. Dependability:Basic Concepts and Terminology[M]. Vienna:Springer-Verlag, 1990
[107]Mitchell C, Stavridou V. Mathematics of Dependable Systems[M]. Oxford:Clarendon Press, 1995
[108]曹晋华,程侃.可靠性数学引论[M].北京：高等教育出版社,2005
[109]G. Chaudhuri, K.Hu, N. Afshar. A new approach to system reliability[J]. IEEE Transactions on reliability,2001,50:75-84
[110]Min-Sheng Lin. An O(k2log(n)) Algorithm for computing the reliability of consecutive-k-out-of-n:F systems[J]. IEEE Transactions on reliability,2004,53:3-6
[111]Suprasad V. Amari, Ming J. Zuo, Glenn Dill. A fast and robust reliability evaluation algorithm for generalized multi-state k-out-of-n system[J]. IEEE Transactions on reliability,2009,58: 88-97
[112]Amir Azaron, Hideki Katagiri, Masatoshi Sakawa, Mohammad Modarres. Reliability function of a class of time-dependent systems with standby redundancy [J]. European Journal of Operational Research,2005,164:378-386
[113]Igor Aizenberg. Solving the XOR and parity N problems using a single universal binary neuron[J]. Soft Computing,2007,22(3):215-222