Problem with getting neural network learned to calculate XOR

Question

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;

Theta1_grad = zeros(size(Theta1));
Theta2_grad = zeros(size(Theta2));

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);

        Theta1_grad += delta2 * a1';
        Theta2_grad += delta3 * a2';
    end

    J /= -m;

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

    disp(J);
    disp(Theta1_grad);
    disp(Theta2_grad);
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

Answer 1

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).