Menu
Could someone please give me a mathematical correct explanation why a Multilayer Perceptron can solve the XOR problem?
My interpretation of the perceptron is as follows:
A perceptron with two inputs 
and 
has following linear function and is hence able to solve linear separateable problems such as AND and OR.
is the basic step function.
The way I think of it is that I substitute the two parts within 
separated by the + sign as 
and 
and I get 
which is a line.
By applying the step function I get one of the the clusters in respect to the input. Which I interpret as one of the spaces separated by that line.
Because the function of an MLP is still linear, how do I interpret this in a mathematical way and more important: Why is it able to solve the XOR problem when it's still linear? Is it because its interpolating a polynomial?
416
The XOR problem with neural networks can be solved by using Multi-Layer Perceptrons or a neural network architecture with an input layer, hidden layer, and output layer. So during the forward propagation through the neural networks, the weights get updated to the corresponding layers and the XOR logic gets executed.
The XOr problem is that we need to build a Neural Network (a perceptron in our case) to produce the truth table related to the XOr logical operator. This is a binary classification problem. Hence, supervised learning is a better way to solve it. In this case, we will be using perceptrons.
Linearly separable data basically means that you can separate data with a point in 1D, a line in 2D, a plane in 3D and so on. A perceptron can only converge on linearly separable data. Therefore, it isn't capable of imitating the XOR function.
On the surface, XOR appears to be a very simple problem, however, Minksy and Papert (1969) showed that this was a big problem for neural network architectures of the 1960s, known as perceptrons.
You are looking for a mathematical explanation, so let's first take a look on how a perceptron works:
The input gets weighted and summed up. If it exceeds a threshold theta, 1 is returned, otherwise 0. In the XOR case x1 and x2 can be either 1 or 0 and you are searching for weights w1 and w2 as well as a threshold theta such that in case of x1 XOR x2:
w1*x1 + w2*x2 >= theta
OR
w1*x1 + w2*x2 - theta >= 0
First, you can see that the function is linear. This means that it defines a line. But when you look at the sample space, there is no line that can separate the positive from the negative cases.
Second, you can try it out. Take an arbitrary theta, let's say 0.5.
Case 1: x1 = 1, x2 = 0 => w1 needs to be > 0.5
Case 2: x1 = 0, x2 = 1 => w2 needs to be > 0.5
Case 3: x1 = 1, x2 = 1 => w1+w2 needs to be < 0.5 => impossible due to previous two cases
In general, with a perceptron you can only define functions that are linear separable, i.e. lines, planes, hyperplanes etc.
But for the XOR case you need two lines:
For each line, you need one hidden node and then combine things together while taking the negation into account.
You can see a solution here:
How to solve XOR problem with MLP neural network?
So the trick is not to get non-linear but rewrite XOR into something like:
x1 XOR x2 == NOT (x1 AND x2) AND (x1 OR x2)
51
Try plotting the sample space of an XOR function of two variables x1 and x2. The decision boundary seperating the positive(y=1) and negative examples(y=0) is clearly not a straight line but a non-linear decision boundary as follows:
Since, modelling a non-linear decision boundary cannot be done by a simple neural network consisting of only input and output layers. Hence, a hidden layer is required to model the non-linear decision boundary required. On the other hand, functions like AND, OR, NOT have linear decision boundary and hence can be modelled by simple input-output neural nets.
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
