Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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:
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:
