Committees and XOR

The XOR data set of Fig.5.2 cannot be solved by a single unit because it is not linearly separable. It can however easily be solved by three units sharing input from points in the plane and one unit receiving its input from the first three. The diagram for the net is shown in Fig.5.6. It is called a committee, terminology due to Nilsson, because the last unit can be thought of as taking the votes of the three preceding units and adding them up. This will give the majority opinion since each vote is $\pm 1$.

 

Figure 5.6: A committee of model neurons.

This committee is referred to in the literature as a `three layer net; you might count only two layers, the square boxes being inputs not processing elements, but the traditions of the literature are against you. The fact that the literature appears to have been written by people who couldn't tell the difference between an input and a processing element may depress you somewhat, but look on the bright side. It can't really be a difficult subject.

Now we work through the points one at a time and trace the behaviour through the net. It is recommended that you do this with a pen and paper to check my arithmetic, which is very shaky.

Suppose we input the point (0,0) to the net. The first unit outputs +1, the second and the third -1. The fourth unit in the third layer simply sums these and outputs the sign of the result which is -1. If we input the point (1,1) then the first unit outputs -1, the second +1 and the third -1 again, so the last unit again outputs -1.

If we input (1,0) then the first unit outputs +1, the second unit outputs +1 and the third unit outputs -1 again. So the majority vote sum of these numbers is +1. Similarly if we input (0,1), the first two units output +1, the third outputs -1 and the last unit outputs +1. So with the interpretation +1 means TRUE and -1 means FALSE, the network implements the logical function XOR.

So a committee of three units can do what a single unit cannot. The question which should spring to the mind of even the most intellectually numb is, how did I get the numbers above?

The answer is that I drew a simple diagram of lines and read off the coefficients of the lines. The picture I drew was that of Fig.5.7, and I simply surrounded the positive points with some positive lines. In fact the negative line is only there as a courtesy; it seemed easier to have an odd number of voters to ensure that there can't be any ties as a general principle.

 

Figure 5.7: A committee solving XOR.