N-bit parity neural networks: new solutions based on linear programming

Abstract

In this paper, the N-bit parity problem is solved with a neural network that allows direct connections between the input layer and the output layer. The activation function used in the hidden and output layer neurons is the threshold function. It is shown that this choice of activation function and network structure leads to several solutions for the 3-bit parity problem using linear programming. One of the solutions for the 3-bit parity problem is then generalized to obtain a solution for the N-bit parity problem using ⌊N/2⌋ hidden layer neurons. Compared to other existing solutions in the literature, the present solution is more systematic and simpler. Furthermore, the present solution can be simplified by using a single hidden layer neuron with a “staircase” type activation function instead of ⌊N/2⌋ hidden layer neurons. The present activation function is easier to implement in hardware than those in the literature for N-bit parity networks. We also review similarities and differences between the present results and those obtained in the literature.

Introduction

The XOR/parity problem has a long history in the study of neural networks. It is used in [6] as a basis for illustrating the limitations of the computational power of perceptrons. The parity mapping problem has since been recognized as one of the most popular benchmarks in evaluating neural network training algorithms [2]. The N-bit parity function is a mapping defined on 2^N distinct binary vectors that indicates whether the sum of the N components of a binary vector is odd or even. When N=2, the parity function is the exclusive-or (XOR) logic function. Let β=[β₁,β₂,…,β_N]^T be a vector in B^N where $\text{B}{}^{\mathrm{N}}\text{≜{β∈R}{}^{\mathrm{N}}\text{:}\text{β}{}_{\mathrm{k}}\text{=0}$ or 1 for k=1,2,…,N}. The mapping $\text{ψ}\text{:}\text{B}{}^{\mathrm{N}}\text{→B}{}^1$ is called the N-bit parity function if

$$\text{ψ(β)=}\text{1}\text{if}\text{∑}\text{k=1}\text{N}\text{β}{}_{\mathrm{k}}\text{is}\text{odd}\text{,}\text{0}\text{if}\text{∑}\text{k=1}\text{N}\text{β}{}_{\mathrm{k}}\text{is}\text{even}\text{.}$$

The parity mapping is considered difficult for neural network learning since changes in a single bit results in changes in the output.

It is previously thought that a standard feedforward neural network model requires N hidden layer neurons to solve the N-bit parity problem [7]. The network in [7] uses the sigmoidal transfer function,

$$\text{f(u)=}\text{1}\text{1+}\text{e}{}^{\mathrm{-u}}\text{,}$$

and is trained using the generalized delta rule. Although it is shown in [7] that the XOR function could be realized using a neural network with a single hidden layer neuron and direct connections between the input and output layers, no generalization utilizing such a structure is made for the parity function with N>2.

In [9], it is shown that standard feedforward neural networks can be used to solve the N-bit parity problem with ⌈(N+1)/2⌉ hidden layer neurons, where ⌈·⌉ stands for rounding towards +∞. Using the same network structure, a solution is proposed in [8] for the N-bit parity problem. The connection weights between the inputs and hidden layer neurons can be obtained trivially, while the connection weights between the hidden layer neurons and the output layer neuron can be obtained by solving a system of linear equations.

The implementation of the N-bit parity problem using a different network structure is proposed in [5]. The implementation leads to a neural network with an output y=u−2η, where

$$\text{η=}\text{∑}\text{j=1}\text{[N/2]}\text{1}\text{1+}\text{e}{}^{\mathrm{-40(u-2j+0.15)}}\text{,}$$

$\text{u=∑}{}_{\mathrm{i=1}}{}^{\mathrm{N}}\text{x}{}_{\mathrm{i}}$ and [·] indicates truncation to the nearest integer. The connection weights from the inputs x_i to u and from u to the hidden and output layer neurons are all equal to 1. It is also noted in [5] that the node u can be replaced by direct connections from the input nodes to the hidden and output nodes.

It is shown in [10] that using a standard feedforward neural network, the N-bit parity problem can be solved with just two hidden layer neurons. The activation function used in both hidden units is

$$\text{f(u)=}\text{1}\text{N}\text{u−}\text{cos}\text{(πu)}\text{απ}\text{,}$$

where the choice of α>1 ensures that the function is monotonically increasing. One of the hidden units has a constant bias of −1 while the other has zero bias. The output unit is a linear threshold unit with a constant bias of −1/N. All connection weights are equal to 1 except the weight from the first hidden unit to the output unit which is −1.

When direct connections between the input layer and the output layer are introduced, it is shown in [1], that the problem can be solved with a structure that requires only one hidden layer neuron. The activation function used in the hidden layer neuron is the continuously differentiable “step” function,

$$\text{f(u)=⌊u⌋+}\text{sin}{}^{\mathrm{K}}\text{π(u−⌊u⌋)}\text{2}\text{,}$$

where K>1 and ⌊·⌋ stands for rounding towards −∞.

In this paper, the N-bit parity problem is solved with a neural network that allows connections between the input layer and the output layer. The threshold transfer function is used in the hidden and output layer neurons. It is shown that a set of solutions for the 3-bit parity problem can be obtained using linear programming. One of these solutions is then generalized to obtain a solution for the N-bit parity problem using ⌊N/2⌋ hidden layer neurons. Furthermore, the present solution can be simplified by using a single hidden layer neuron with a “staircase” type activation function instead of ⌊N/2⌋ hidden layer neurons. The present paper makes contributions beyond that of [3] by solving the N-bit parity neural networks systematically using linear programming. We also note that there has been a recent follow-up to our letter [3] published in 1999 (see, e.g., [4]).