|
Two different neural network connections which can emulate exclusive OR (XOR) gates1
Module 200: An Introduction to Neural Networks
|
|
Two different neural network connections which can emulate exclusive OR (XOR) gates1
UNIT 2
Contents:
A simple artificial neuron in C++
Networks of artificial neurons
The Perceptron
Laboratory workbook exercises
References
A simple artificial neuron in C++
How do artificial neurons learn?
In the last Unit we examined the mathematical
model which defines the main characteristics of an artificial neuron. This
model was static. Its response to input data could only be changed by the
user changing the values of the weights. In this Unit we will look at a program
for an artificial neuron which has the ability to 'learn' new functions by
amending its own weights. It does this by comparing its actual output for
a set of particular inputs with the 'correct' output as defined by the programmer.
Within discussion of artificial neural networks, this process is called supervised
learning. If the output is incorrect the neuron makes repeated changes to
the weights until it achieves a set of weights which produce the correct output.
For example, a neuron with two binary inputs could learn how to behave as
an AND gate by comparing its output for all combinations of inputs with the
truth table for an AND gate and then making alterations to the values of
its input weights until it consistently produces the output of an AND gate.
The C++ program
We will examine the activation function, summation function, and the weight
amendment mechanism for a simple program representing an artificial neuron.
We will also look at the method by which the neuron compares its output with
the correct output. The neuron we will examine has two binary inputs and is
being trained to emulate an AND gate.
Weights, summation function,
threshold value, activation function
You can see that all the major characteristics of the mathematical model
we have studied are contained in the following program extract. In fact, the
weighting of the inputs, the summation function, and the threshold value are
all contained in the first line of code. The remainder of the extract represents
the activation function which determines the output of the neuron.
//summation function, threshold value (> 1),
//activation function
if ((weight_a * input_a) + (weight_b * input_b) > 1)
actual_output = 1;
else
actual_output = 0;
Weight adjustment
The next extract shows
the method which is used amend the neuron's input weights if its output is
incorrect. You can see that an almost identical procedure is applied to each
of the two input weights. We will divide this procedure into simple stages
for convenience of explanation. Firstly, the difference between the correct
output and the actual output is calculated: (correct_output - actual_output).
Secondly, this difference is multiplied by the product of what is called
the learning rate (1 in this case) and the value of the relevant input:
1 * input_a. The learning rate determines the rate at which the input weights
are successively adjusted. In this case it is set a relatively high value
- in reality it is likely to be a small value such as 0.05. Finally, the
value of the original weight is adjusted by adding to it the result of the
previous calculations: weight_a + (1 * input_a *(correct_output - actual_output)).
//adjust weights if actual output incorrect
if (actual_output != correct_output)
{
weight_a = weight_a + (1 * input_a *(correct_output - actual_output));
weight_b = weight_b + (1 * input_b
*(correct_output - actual_output));
}
'Correct output'
As you can see, the
program uses a variable 'correct_output' to represent the output the neuron
should achieve. This is defined as the output of an AND gate for the relevant
inputs. The appropriate sections of the program are shown below.
//enter the input data in an AND gate
int input[]={input_a, input_b};
and_func(input);
//define correct output as output of AND gate
correct_output = and_func(input);
AND gate
In the program, a C++
function with two input parameters is used to define the operation of the
AND gate. The function definition is given below.
// AND function (takes 2 inputs)
int and_func(int inputs[])
{
if(inputs[0] && inputs[1])
return 1;
else
return 0;
}
Exercise
The extracts shown
above are taken from the 'logicgts.cpp' program in the Unit 2 part of the
Datafiles section of this CD-ROM. Copy the program
and run it on your C++ compiler. The program asks the user to enter training
data during the AND gate learning process. Although the neuron represented
by the program is currently set up to emulate an AND gate, the program contains
functions defining the operations of OR and exclusive OR (XOR) gates. Once
you are familiar with the program, amend the code and train the neuron to
emulate an OR or XOR gate. Note the result of the training process for an
XOR gate. Why do you think the neuron functions in this way?
Experiment with the working applets
of artificial neurons which can emulate AND, OR and NOT gates which can be
found on the 'Introduction to Neural Networks' site
of the Middle East Technical University, Turkey:
http://www.ii.metu.edu.tr/~ion526/demo/chapter1/section1.2/index.html
Networks of artificial neurons
Why use networks?
As you
will have noticed from the last exercise, it is not possible to train a single
artificial neuron of the type we have devised to act as an XOR gate. This
problem can be solved by using layers of artificial neurons connected in
varying patterns, such as those shown in the illustration at the beginning
of this Unit. To understand why an XOR gate must be implemented in this way
we need to identify why a single neuron cannot behave as such a gate.
OR and XOR gates and inequalities
The truth tables for
a logical OR gate and an XOR gate are shown below.
OR XOR
Inputs Outputs Inputs Outputs
0 1 1 0 1 1
1 0 1 1 0 1
0 0 0 0 0 0
1 1 1 1 1 0
The following trace
tables show the inputs, weights, threshold value, and outputs for a single
neuron of the type we have previously defined acting as an OR gate. They
also show the inequalities which the weights and the threshold value must
satisfy in order for the neuron to function as an OR gate. You will see that
the values chosen for the weights and the threshold actually do satisfy the
inequalities. You may wish to refresh your knowledge of the mathematics of
simple linear inequalities at this point.
OR GATE
Inputs Weights Threshold Value (TV)
Output Inequalities
0 1 2 2 >1 1
W2
> TV
1 0 2 2 >1 1
W1 > TV
0 0 2 2 >1 0
TV > 0
1 1 2 2 >1 1
W1+W2 > TV
The next trace table shows the inputs, output, and the inequalities which
the weights and the threshold value must satisfy in order for the same neuron
to function as an XOR gate.
XOR GATE
Inputs Weights Threshold Value (TV)
Output Inequalities
0 1 ? ? ? 1
W2 > TV
1 0 ? ? ? 1
W1 > TV
0 0 ? ? ? 0
TV > 0
1 1 ? ? ? 0
W1+W2 < TV
You can see that
the first and second inequalities in the XOR gate cannot be satisfied without
contradicting the fourth inequality. If both weight 1 and weight 2 are greater
than the threshold value it is impossible for their sum to be less than the
threshold value.
In Unit 3 we will develop a network, made up of the simple neurons we have
devised, which
can emulate an XOR gate.
Artificial neural networks made up of one input layer and
one output layer of the simple neurons we have devised are known as perceptrons.
The illustration below shows the pattern of interconnections between the
artificial neurons in the input and output layers of a perceptron.
Diagram showing the
connections between neurons in a Perceptron2
It is important to realise that even this simple two-layer
network made up of eight neurons is able to carry out quite sophisticated
functions. As we have seen, neural networks have this ability for two main
reasons. Firstly, each neuron is an independent information processing system
which is capable of adjusting its own operation. Secondly, the pattern of
interconnections between neurons creates an inter-related system. We will
look further at both these features of neural networks in the next Unit.
Exercise
There is an example of a single-layer perceptron in the Unit 2 part of the
Datafiles section of this CD-ROM. Copy the four
files which make up the program and use them to create a project named 'perceptron_1'
on your C++ compiler. The program allows you to train the perceptron to emulate
an OR gate and an AND gate. Unlike the program we used earlier in this Unit,
the perceptron program generates its own input data. It will do so until
it successfully emulates the chosen gate for all possible inputs. During
the learning process, the perceptron will display the adjustments which are
being made to the input weights. The program also allows you to attempt to
train the perceptron to emulate an XOR gate. As a single-layer perceptron,
it is not capable of emulating an XOR gate. In Unit 3 we will increase the
number of inputs to the perceptron and investigate the complex
functions which can be carried out by even a single-layer of artificial
neurons.
Before
going on to the next Unit you should complete the Laboratory Workbook exercises
set out below.
Laboratory workbook exercises
The Laboratory workbook exercises for this Unit are contained in the Unit 2 chapter of the workbook.
References
1. Illustration of two artificial neural networks which can emulate XOR gates taken from Middle East Technical University, Turkey, 'Introduction to Neural Networks':
http://www.ii.metu.edu.tr/~ion526/demo/chapter1/section1.3/figure1_9e.html
2. Illustration of a Perceptron taken from an MSc thesis 'An investigation into the use of maximum likelihood classifiers, decision trees, neural networks and conditional probabilistic networks for mapping and predicting salinity' by Fiona Evans:
http://www.cmis.csiro.au/Fiona.Evans/personal/msc/html/chapter6.html
Page updated 19.5.03