Binary higher order neural networks for realizing Boolean functions

Minimal Sign Representation of Boolean Functions: Algorithms and Exact Results for Low Dimensions

Boolean functions (BFs) are central in many fields of engineering and mathematics, such as cryptography, circuit design, and combinatorics. Moreover, they provide a simple framework for studying neural computation mechanisms of the brain. Many representation schemes for BFs exist to satisfy the needs of the domain they are used in. In neural computation, it is of interest to know how many input lines a neuron would need to represent a given BF. A common BF representation to study this is the so-called polynomial sign representation where [Formula: see text] and 1 are associated with true and false, respectively. The polynomial is treated as a real-valued function and evaluated at its parameters, and the sign of the polynomial is then taken as the function value. The number of input lines for the modeled neuron is exactly the number of terms in the polynomial. This letter investigates the minimum number of terms, that is, the minimum threshold density, that is sufficient to represent a given BF and more generally aims to find the maximum over this quantity for all BFs in a given dimension. With this work, for the first time exact results for four- and five-variable BFs are obtained, and strong bounds for six-variable BFs are derived. In addition, some connections between the sign representation framework and bent functions are derived, which are generally studied for their desirable cryptographic properties.

Structure of indicator function classes with finite Vapnik-Chervonenkis dimensions

The Vapnik-Chervonenkis (VC) dimension is used to measure the complexity of a function class and plays an important role in a variety of fields, including artificial neural networks and machine learning. One major concern is the relationship between the VC dimension and inherent characteristics of the corresponding function class. According to Sauer's lemma, if the VC dimension of an indicator function class F is equal to D, the cardinality of the set F(S1(N)) will not be larger than Σ(d=0)(D)C(N)(d). Therefore, there naturally arises a question about the VC dimension of an indicator function class: what kinds of elements will be contained in the function class F if F has a finite VC dimension? In this brief, we answer the above question. First, we investigate the structure of the function class F when the cardinality of the set F(S1(N)) reaches the maximum value Σ(d=0)(D)C(N)(d). Based on the derived result, we then figure out what kinds of elements will be contained in F if F has a finite VC dimension.

Discretized-Vapnik-Chervonenkis dimension for analyzing complexity of real function classes

In this paper, we introduce the discretized-Vapnik-Chervonenkis (VC) dimension for studying the complexity of a real function class, and then analyze properties of real function classes and neural networks. We first prove that a countable traversal set is enough to achieve the VC dimension for a real function class, whereas its classical definition states that the traversal set is the output range of the function class. Based on this result, we propose the discretized-VC dimension defined by using a countable traversal set consisting of rational numbers in the range of a real function class. By using the discretized-VC dimension, we show that if a real function class has a finite VC dimension, only a finite traversal set is needed to achieve the VC dimension. We then point out that the real function classes, which have the infinite VC dimension, can be grouped into two categories: TYPE-A and TYPE-B. Subsequently, based on the obtained results, we discuss the relationship between the VC dimension of an indicator-output network and that of the real-output network, when both networks have the same structure except for the output activation functions. Finally, we present the risk bound based on the discretized-VC dimension for a real function class that has infinite VC dimension and is of TYPE-A. We prove that, with such a function class, the empirical risk minimization (ERM) principle for the function class is still consistent with overwhelming probability. This is a development of the existing knowledge that the ERM learning is consistent if and only if the function class has a finite VC dimension.

Sensitivity-based adaptive learning rules for binary feedforward neural networks

This paper proposes a set of adaptive learning rules for binary feedforward neural networks (BFNNs) by means of the sensitivity measure that is established to investigate the effect of a BFNN's weight variation on its output. The rules are based on three basic adaptive learning principles: the benefit principle, the minimal disturbance principle, and the burden-sharing principle. In order to follow the benefit principle and the minimal disturbance principle, a neuron selection rule and a weight adaptation rule are developed. Besides, a learning control rule is developed to follow the burden-sharing principle. The advantage of the rules is that they can effectively guide the BFNN's learning to conduct constructive adaptations and avoid destructive ones. With these rules, a sensitivity-based adaptive learning (SBALR) algorithm for BFNNs is presented. Experimental results on a number of benchmark data demonstrate that the SBALR algorithm has better learning performance than the Madaline rule II and backpropagation algorithms.