# Problem with getting neural network learned to calculate XOR

I am learning about neural networks. I found a course on Coursera about machine learning https://www.coursera.org/course/ml . What I am trying to implement is a neural network to calculate logical XOR.

I am using network with input layer, 1 hidden layer and output layer. They have 2, 2, 1 neurons respectively (also first 2 layers has bias neurons). I have written this small program in Octave. I am observing such results: firstly cost function J has some value which is near some number (about 0.7). This continues for some random time, then suddenly cost function gives a rush to zero, and network gives right results.

As you can see I'm trying to implement backpropagation algorithm with gradient descent using formulas from that Andrew Ng's course.

The problem is that cost function doesn't decrease every step of gradient descent. By the way, examples with logical AND and logical OR worked great.

I tried to add more training data, as far as I can see, that doesn't change anything.

Question is: What can I change to make gradient descent converge fast (to make it not stuck)?

Slides from lecture about backpropagation: https://d396qusza40orc.cloudfront.net/ml/docs/slides/Lecture9.pdf

m = 4; %number of examples
X = [0 0; 1 0; 0 1; 1 1];
Y = [1; 0; 0; 1];

eps = 0.01;

Theta1 = rand(2, 3) * 2 * eps - eps;
Theta2 = rand(1, 3) * 2 * eps - eps;

function [ans] = sigmoid(z)
ans = 1.0 / (1.0 + exp(-z));
end

alpha = 0.0001;

while J > 0.001,

J = 0;

for i = 1:m
%forward propagation
a1 = [1 X(i, :)]';
z2 = Theta1 * a1;
a2 = [1 sigmoid(z2)]';
z3 = Theta2 * a2;
a3 = sigmoid(z3);

%update cost function
J += Y(i) * log(a3) + (1.0 - Y(i)) * log(1.0 - a3);

%backward propagation
delta3 = a3 - Y(i);
delta2 = ((Theta2' * delta3) .* (a2 .* (1 - a2)))(2:end);

end

J /= -m;

%Updating theta
Theta1 -= alpha / m * Theta1_grad;
Theta2 -= alpha / m * Theta2_grad;

disp(J);
end

%output on training data
for i = 1:m
a1 = [1 X(i, :)]';
z2 = Theta1 * a1;
a2 = [1 sigmoid(z2)]';
z3 = Theta2 * a2;
a3 = sigmoid(z3);

disp('a3 = ');
disp(a3);
end

• immediately - means that you want train you network in one iteration (epoch)? – itdxer Jan 28 '15 at 19:55
• I meant fast actually, I'd better edit the post a bit. – justanothercoder Jan 28 '15 at 20:00

There are a lot of technicians to optimize your learning like Momentum, RPROP and other. More infromation you can check at paper Yann LeCunn - Efficient BackProp. Also there are a lot of heuristic method for learning, for example you can use random weights from the "standard normal" distribution or make you learning rate different for layers or even for every synapse.

Also, you can find some technics which can train your network weights without learning iterations (but it's not a GD). For this issues you need computtion of inverse matrix or pseudo-inverse matrix. XOR is not linear separateble problem so you can't do it in classic Linear Algebra way, you must change you data set space in some way, for example you can use Radial Basis Functions (RBF).

• By the way, is it true, that on such network as in my code, cost function has local minimum? – justanothercoder Jan 28 '15 at 20:58
• Sorry, I not really understand your question. Can you explain it in different way? – itdxer Jan 28 '15 at 21:13
• So your function can contains one or many minimums, the problem that you not sure that you in local or global minimum, but you will find one of them, GD is converge to it if you use correct parameters in network. Hope I understand your question right. – itdxer Jan 28 '15 at 21:15
• Obviously, I want to find the best minimum - global. Actually, there is a way to get out of local minimum: to move in random direction. I think I'll try it. – justanothercoder Jan 28 '15 at 21:31
• For global minimum optimization en.wikipedia.org/wiki/Simulated_annealing – itdxer Jan 28 '15 at 21:51