# Are these two 2D datasets the same and can they be separated with the XOR NN?

I'm a very beginner in the neural network topic. So I ran into a problem.

I see on the online lectures:

Famous example of a simple non-linearly separable data set, the XOR problem (Minsky 1969) in the right figure. but what about the left ones? is it same?

Can we used XOR NN for separate both of them? (is it same or not 2D datasets)?

I means with general neuron like as McCulloch is it possible via 3 nodes excepts input? • The second data set seems rotated by 45°... they should be equivalent. Nov 28, 2020 at 22:14
• It has already been answered... what is the problem ? Nov 28, 2020 at 22:23

If you have a simple neural network which separates some data $$\{x_i\}$$, and it has a fully connected first layer with weight matrix $$W$$, and then you apply some invertible linear transform $$x' = Ax$$ to the data, then $$Wx = WA^{-1}x'$$, which is to say that if you use the weights $$WA^{-1}$$ on the transformed data, you'll get the same outputs.

If, as lcrmorin says in his/her comment, one set is essentially equivalent to the other, only rotated by 45°, then I agree with shimao's answer.

It is, however, not that clear from the figures whether this equivalence is given. It boils down to the question whether you can enclose one class in a convex area, so than no points from the other class are enclosed.

Concretely, for your datasets, this is equivalent to asking whether you can, in your left figure, draw two straight lines (blue (A) and orange (B)), so that all and only black triangles are between them: If yes, then the two sets (figure left and figure right) are equivalent and you can use the same network to classify both sets. In the right figure, it is obvious that all and only the red crosses are between the two lines. The area between the two lines is convex (for any two points from the area, all points on the straight line connecting them are also in the area). From the classification point of view, the two sets are equivalent, the one is basically a 45 degrees rotated version of the other.

However, if you cannot draw such two lines (notice how both lines touch both the triangles and the circles), then the left dataset is somewhat more complicated: Each class is non-convex, has to be split into multiple convex subclasses, which then need to be combined. The network will need one more layer to achieve this.

Why is it so? First, recall that each neuron implies a linear boundary: $$\textbf{w} \cdot \textbf{x} + b_0$$ is a linear function of the neuron inputs $$\textbf{x}$$, the weights $$\textbf{w}$$ and the bias $$b_0$$. The set of all $${\textbf{x}}$$ where this function is zero is, in 2D-case, a straight line. In a neuron, we typically pass the result of $$\textbf{w} \cdot \textbf{x} + b_0$$ through a non-linear activation function $$f(\cdot)$$. In case of classification, this is commonly some sigmoid function, but, for the discussion here, we can equally well assume it to be the step function: $$f(x) = 0$$ for $$x < 0$$ and $$1$$ otherwise.

Second, recall that you can construct boolean operators with such neurons. In the image below, the point (1, 1) is on one ("positive") side of the blue line (A), while all other points, (0, 0), (0, 1) and (1, 0) are on the other. If your neuron outputs 1 for the input (1, 1) and zero otherwise, you can consider it performing the logical "AND". Similarly, a neuron outputting zero for (0, 0) and one otherwise performs the logical "OR". And, a boolean "NOT" of some input $$x$$ is simply $$1-x$$. Now, the classification rule for your right dataset (below) is pretty simple: The class is "red crosses" if it is between the blue and the orange line, and "green circles" otherwise: You need only three neurons to implement it:

1. one to output 1 if the input is below (on the '+' side of) the blue line (A)
2. one to output 1 if the input is above (on the '+' side of) the orange line (B), and
3. one to perform the logical "AND" of (1) and (2).

That would be your "3 node NN".

However, for the left dataset, it is more complex: The class is "black triangles" IFF the input is (above the blue AND above the orange line) OR (below the blue AND below the orange line). You need five neurons to implement this:

1. one to output 1 if the input is above (on the '+' side of) the blue line (A),
2. one to output 1 if the input is above (on the '+' side of) the orange line (B),
3. one to perform the logical "AND" of (1) and (2),
4. one to perform the logical "AND" of (NOT 1) and (NOT 2), and
5. one to perform the logical "OR" of (3) and (4).

This would be your "2*2*1", "5 node NN".

In general, a three-layer perceptron, with each layer being sufficiently large, can perfectly represent any classification of the points:

• it the first, linear boundaries between subsets of the data are defined;
• in the second, these boundaries are combined by "AND" operators to form convex areas; and
• in the third, these convex areas are combined by "OR" operators to achieve arbitrarily-shaped classes.
• @MaryamPanahi I followed your link and read Martin Jansche's answer on Quora, posted today, but I don't know how do you want me to update my answer. Martin's answer is congruent with mine. Dec 7, 2020 at 20:21
• This answer is also congruent with mine at: datascience.stackexchange.com/questions/86000/… Jan 12, 2021 at 14:55