Greetings, Daniel. Yes, a feedforward multilayer network can learn these problems. (I just gave it a try because I was not aware of theoretical claims about limitations on multi-layer perceptrons to do this.)

A strictly feedforward 3-layer neural network trained through backpropagation of error is able to solve both the 8-dimensional and 10-dimensional XOR problems. For example, to solve an 8-dimensional XOR problem, the architecture I used was an 8-20-1 with small, random normally distributed initial weights. More specifically, the network was as follows:

CREATE NUCLEI ("L1","L2","L3")

INSERT NEURON mock INTO "L1" QUANTITY 1 LABELED "BIAS"

INSERT NEURON mock INTO "L1" QUANTITY 8

INSERT NEURON sigmoid INTO "L2" QUANTITY 20

INSERT NEURON sigmoid INTO "L3" QUANTITY 1

PROJECT FULLY FROM NUCLEUS "L1" TO "L2" WEIGHTS N(0.01,0.1)

PROJECT FULLY FROM NUCLEUS "L2" TO "L3" WEIGHTS N(0.1,0.1)

PROJECT FULLY FROM NUCLEUS "L1 BIAS" TO "L3" WEIGHTS N(0.1,0.01)

Using a learning rate of 0.05 and 40,000 passes through the 256-item training set, the network achieved 100% correct performance.

Sincerely,

Patryk

Hello Patryk:

Very interesting. I assume you refer to classical discontinuous/sigmoid semilinear perceptron NNs.

You are right about theoretical feasibility. There is a general existence result: For any pair A, B of non-empty, finite, disjoint sets of n-vectors there are solutions, that is, perceptron NNs [feed-forward, semilinear, discontinuous threshold, binary valued, 3-layer] that assume value 1 on A and value 0 on B. In fact there are infinitely many solutions. For sigmoid thresholds there is a similar existence result.

However, actually calculating the architecture and weights, as you did, is a different matter.

About the calculations the following questions arise naturally and perhaps you know the answers.

1.- Here 'unit' stands for 'perceptron unit'. About the NNs, we may be using slightly different terminologies. The architecture you describe has two possible interpretations

* INTERPRETATION #1 *

FIRST LAYER: 20 units, each with 8 inputs

SECOND LAYER: 1 unit, with 20 inputs

THIRD LAYER: No third layer

* INTERPRETATION #2 *

FIRST LAYER: 8 units, each with 8 inputs

SECOND LAYER: 20 unit, each with with 8 inputs

THIRD LAYER: 1 unit, with 20 inputs

I use the terminology of #2, but it is far from universal. As a numerical example I am attaching a file that contains the weights of some 3-layer perceptron NN solving the same 8-dimensional XOR problem.

2.- How do you [or the algorithm you used] choose 20 perceptron units for one of the layers. Is the value 20 a random value or there is a specific rule that applied to the XOR data produces the 20?

3.- In general the problem to calculate a solution seems to be *learning time*. Do you obtain a solution in the first attempt? If so, this means that you do not have to try several architectures and several normally distributed initial weights, and run backpropagation on each, to get a 100% solution.

4.- Is the NN algorithm robust for the training data? This means that the algorithm gives you an explicit numerical value $\delta$ such that perturbing any of the vector data by less than $\delta$ (perturbed vectors are no longer binary) will not change the NN value.

5.- Is the algorithm or software a public domain one? If so, links will be appreciated. If the actual numerical values of the solution you calculated are available please send a link.

I implemented an extremely fast geometric algorithm. It works better the higher the dimension of the data vectors. For the 60-dim Sonar, Mines vs Rocks problems I recently posted numeric solutions in ResearchGate. As you will see, for the 8-dim XOR your 20 is small, compared to my solutions, so, your NN is more efficient. Since my program code file is very long and there is perhaps an undetected bug, I want to see other numerical solutions, better than mine, like yours seems to be, before opening again the C++ user interface.

Thanks very much for your interest and time, and for the relevant and substantial information you provided.

Most cordially

Daniel Crespin

Dear Daniel

As you may be already aware that in accordance with Cover's theorem, when we project low dimensional non-separable data to higher dimensions, then it is most likely possible to separate the classes. For example, 2 D XOR problem (0,0) -> 0, (1,1) ->0 and (1,0) ->1, (0,1) -> 1, by adding 0 to one class and 1 to another class will automatically separate the classes linearly. For example (0,0,0) and (1,1,0) will become linearly separable with patterns (1,0,1) and (0,1,1). You may try this trick directly for your n-dimensional XOR problem.

Hope this is helpful to give you different insight.

Namaste Venkatachalam:

Thanks for the insight. Cover theorem could be relevant, but it forces the introduction of other kinds of NNs, not perceptrons. Applying, say, the quadratic transformations appearing in Cover's original paper, we are taken outside and beyond the realm of classical, semilinear, feedforward, etc. perceptrons. Then the neural network architectures become more complicated, other transfer functions can be introduced and the number of weights [function parameters] to consider can grow considerably. Since classical perceptron NNs are equivalent to characterisic functions of polyhedra [=finite unions of convex cells, with convex cell=finite intersections of linear half spaces], the embeddings into higher dimensional spaces can in general be be avoided.

For the specific problem I posed, where perceptron NNs are wanted, Cover theorems do not seem to apply.

However, if you are willing to use NNs more complicated than perceptrons, still you can use backpropagation, especially if you have access to efficient software to do that. Then, Cover results provide some ideas to define these bigger architectures.

Namaste

Daniel Crespin

Wow Daniel What a Surprise to see you greeting me Namasthe. I agree with you. I did miss the point on perceptrons. My suggestion in my mail is that a simple tweaking in the data set by extending to higher dimensions, we can transform the problem from a non-linearly separable one to separable ones. Perceptrons will then be able to fit the separating plane very easily.

As you have rightly pointed out Use of Back-Propagation NN, RBF and other complex architectures are available to fit non-linear complex separating boundaries between classes. In fact in my PhD I devised a neural architectures using a Gate controlled by a signal outside demonstrating its power over difficult classification of image data.

BTW my Name is Chandrasekaran and Venkatachalam is my father's. Indian custom is to place father's name as your initial followed by the given name, My short name is Chase!

Good Day

Chase

Namaste Chase.

Separating data by introducing an additional coordinate and giving it different values according to the desired output will certainly result in new data that are easily separable by a linear inequality. Suppose then that, afterwards, further additional data are given, say to validate the NN, or as an attempt of pattern recognition. The question arises of what value will be given to the additional coordinate of the new data. Note that it is not known in advance to which of the two classes the new data belongs. For that reason it is not sufficient to add a new coordinate. A full mapping is needed from the lower dimensional space into the large dimensional one. But I suspect you already know all this, so let the comment just stand for the record.

Thanks for the explanation of name ordering. But I am now curious. "K. G. Ramanathan" is the name of a well known Indian mathematician. According to Wikipedia the full name is "Kollagunta Gopalaiyer Ramanathan". If the rule you mention applies in general, the given name is Ramanathan and "Kollagunta Gopalaiyer" are father or family names. Is that correct?

Namaste, with extra coordinate equal to most cordial and best regards,

Daniel Crespin

Dear Daniel

Spot on and Kollagunta is the birth place, GopalaIyer is his father's name and his given name is Ramanathan.

BTW, just to add a few more drops in terms of feature vector extension, I came with an idea many years back and got published in the conference proceedings held in Helsinki. The idea is simple. I extended every n dimensional vector by (say to n+1) by computing the n+1 element from the known n-elements. For example, I have assumed an Hypersphere of Radius R in n+1 dimensional space. the (n+1)th element is computed by subtracting from R^2 the sum of squares of all n-feature elements and then taking sqrt of the residue. R is chosen is sufficiently large to avoid any negative quantities. Experiments clearly showed improved classification performance. We may have to apply tricks of this sort. In fact, one can extend the vector n+i dimensional in a successive fashion with the appropriate choice of R_i's as we proceed. I am really enjoying this discussion as it brings forth all the umpteen number of experiments I did during my PhD in the years 91-96 in Univ of Melbourne Australia. Thanks for rekindling my passion.

Namasthe:

Chase

Hi all,

I was wondering if there has been any progress on coming up with a good architecture, initial parameter values, and learning rate for solving the XOR problem of n-dimensions. Patryk, I was able to replicate your result with my own Matlab code, but when I try to scale the problem up (to a 16-dimensional input, for example), I am having trouble getting even the training error rate to drop below 0.24.

I'm using a random sample of 80% of the data (binary sequences of integers ranging from 0 to 2^16 - 1) for training. I am using a three-layer feedforward network with 40 units in the hidden layer and am randomly choosing my initial weights and biases from a uniform distribution over [-0.3, 0.3]. I have tried various learning rates ranging from 1E-7 to 10 and up to 40000 epochs with minibatch size equal to the size of the entire training set, but I'm still not able to get my error to decrease beyond approximately 0.24.

Do you have any thoughts on why the error always seems to get stuck around this value and how generally one could choose the architecture, initial parameter values, and learning rate given the number of bits over which one wants to perform XOR?

Thank you,

Vivek