How to implement Back Propagation algorithm for the following input/output?

Question

I would like to implement a back propagation algorithm in python or C++ for the following input

[[11, 15], [22, 17]]
[[8, 11], [23, 19]]
[[9, 14], [25, 22]]
[[6, 9], [17, 13]]
[[2, 6], [29, 25]]
[[4, 8], [24, 20]]
[[11, 15], [27, 24]]
[[8, 11], [31, 26]]
[[3, 8], [25, 21]]
[[11, 15], [26, 22]]
[[15, 19], [22, 17]]
[[7, 11], [17, 13]]
[[19, 24], [14, 10]]

where the first tuple is my input and the second tuple is my output. Every implementation of the back propagation algorithm I searched over internet uses a classification procedure (either 1 or 0).

The given set of input/output is for developing a neural network for the game of Checkers. I guess it uses the same technique used for implementing Chess.

Is is possible to develop an algorithm for this? Please provide me some guidelines or implementation methods for carrying out this. OpenCV functions can be also used.

Answer 1

Here is how I would proceed.

Let's start by the classical problem of {-1,1} classification problem. f denotes your (neural) network. x is your input belonging to RxR. y_obs is your output belonging to {-1,1}.

u_j is the weights between x and z, z being intermediate output, j ranging from 1 to h and u_j being a R^2 array. w is the weights between z and y, y being the final output, w being a R^h array.

When you are feeding your network, you get f(x)=y belonging to R. Training a neural network consists in adding a criterion E(x,y_obs) on top of the network and try to minimize this criterion (for a binary classification problem, it can be to minimize (f(x)-y_obs)^2) by updating the weights in the network. Your prediction g(x) are given by sign(f(x)) at the end of the training.

Therefore to adapt the implementation you found on internet for your problem, create a neural network 2 x h x 2, h being the number of hidden units. Then, you need to locate the function criterion in the code and replace it by a suitable criterion, an 2d euclidean norm for example. You do not need to implement any prediction function g in that case, your problem isn't a classification problem

You may need to change the definition of the back-propagation implementation to update new weights. For the 1-dim output you have the following gradient to update w_j, j ranging from 1 to h (number of hidden units).

dE / dw_j = dE / dy * dy / dw_j
dE / du_jk = dE / dz_j * dz_j / du_jk 
           = dE / dy * dy / dz_j * dz_j / du_jk

(u_jk is the k-th component of u_j, k=1,2)

With the new situation you get :

y_1 and y_2 the components of y. w_1 and w_2 weights between z and y, w_1 and w_2 are R^h arrays.

dE / dw_1j = dE / dy_1 * dy_1 / dw_1j
dE / dw_2j = dE / dy_2 * dy_2 / dw_2j
dE / du_jk = dE / dz_j * dz_j / du_jk
           = dE / dy_1 * dy_1 / dz_j * dz_j / du_jk + dE / dy_2 * dy_2 / dz_j * dz_j / du_jk

all derivatives on the right being defined by your network.

The precision of the algorithm is very sensitive to the criterion, maybe there is more sophisticated solution than a norm. Testing will tell !

Answer 2

You could use general Back-propagation algorithm for it. There are many sources that explained details about it (for example its wikipedia page). But for better result I have a advice for you.

It's better to regulate your input and outputs. If you add some constant to each component of your input data and move their average over training data near to 0 it will help the network to learn your patterns faster and better.