/************************************************************ 
;   Backpropagation with momentum                           * 
;   by Andres Perez-Uribe                                   *
;   HEIG-VD March/2008                                      * 
;                                                           *
;   Original version:                                       *
;   C code by A. Perez-Uribe                                *
;   Universidad del Valle, Cali, Colombia                   *
;   sep/93                                                  *
;                                                           *
;   Email : andres DOT perez-uribe AT heig-vd.ch            * 
;           REDS Institute @ HEIG-VD                        *
;           University of Applied Sciences of Western       *
;           Switzerland (HES-SO)                            *
;************************************************************

   References :
   -  G. Hinton, "How neural networks learn from experience",
      Scientific American, sep 1992.
   -  P. Werbos,  "The Roots of Backpropagation: From ordered derivatives 
      to Neural Neworks and Political Forecasting", John Wiley and Sons, 
      New York, 1994

    Compile : javac Bkprop.java
    Run : java Bkprop

    There is no guarantee that the code will do what you
    expect or that it is error free. It is simply meant
    to provide a useful way to experiment with the
    Backpropagation learning algorithm.

    Update Oct 7/99...thanks to Stephane Pouyet <pouyet@nist.gov>
    
    Last update March/2007 ... change of variable names for the sake of clarity
    The original names came from Hinton's paper.  

    First Java adaptation by Christophe Scalfo, HEIG-VD, September/2007
    Second Java version by Andres Perez-Uribe, HEIG-VD, March/2008
*/

import java.io.*;

public class Bkprop {
    final String trainfile = "digits.txt";
    final String testfile = "digits.txt";
    final int INPUTS = 35;    /* number if inputs */
    final int HIDDEN = 5;     /* number of hidden units */
    final int OUTPUTS = 10;    /* number of outputs */
    final double EPSILON = 0.1;  /* maximum Mean Square Error to stop training */
    final int NUMTRAIN = 18;    /* number of training patterns */
    final int NUMTEST = 18; /* number of test patterns */

    /* synaptic weights */
    private double[][] inhiddw = new double[INPUTS][HIDDEN];
    private double[][] hidoutw = new double[HIDDEN][OUTPUTS];

    /* delta_weights memorization for Backprop with momentum */
    private double[][] deltaihw = new double[INPUTS][HIDDEN];
    private double[][] deltahow = new double[HIDDEN][OUTPUTS];

    /* input, hidden and output vector values */
    private double[] x= new double[INPUTS];
    private double[] y= new double[HIDDEN];
    private double[] z= new double[OUTPUTS];
	
    //Sigmoid activation function
    public double sigm(double x){
	return 1/(1 + Math.exp(-x));
    }

    //Derivative of the sigmoid activation function 
    public double dxsigm(double y){
	return (y)*(1-y);
    }

    /* training patterns */
    private double[][] patterns = new double[NUMTRAIN][INPUTS];
    /* desired outputs */
    private double[][]   desout= new double[NUMTRAIN][OUTPUTS];
    /* delta error of the hidden neurons */
    private double[] ehid = new double[HIDDEN];
    /* delta error of the output neurons */
    private double[] eout = new double[OUTPUTS];
    /* learned patterns */
    private boolean[] lrnpatr = new boolean[NUMTRAIN];
    /* squared mean error */
    private double[] sme = new double[NUMTRAIN];
  
    private double delta = 0.5;     /* learning rate */
    private double alfa = 0.1;      /* momentum */
    private double[][] matrizin = new double[NUMTEST][INPUTS];
    private int output;
       
    //Loading a training database
    public void read_data(){
	BufferedReader lecteurAvecBuffer = null;
	String ligne;
	String[] trame;

	try
	    {
	    	lecteurAvecBuffer = new BufferedReader(new FileReader(trainfile));
	    }
	catch(FileNotFoundException exc)
	    {
	    	System.out.println("Error loading the training database");
	    }
	try
	    {
	    	for(int i =0; i<NUMTRAIN; i++){
		    ligne = lecteurAvecBuffer.readLine();
		    trame = ligne.split(",");
		    System.out.println(ligne);

		    /* input patterns */
		    for(int j=0;j<trame.length-2;j++){
			patterns[i][j] = Double.parseDouble(trame[j]);
		    }
		    /* desired outputs */
		    output = Integer.parseInt(trame[trame.length-1]);
		    for(int k=0; k<OUTPUTS; k++){
			if(output == k) desout[i][k]=1.0;
			else desout[i][k]=0.0;
		    }
		}	
		lecteurAvecBuffer.close();
	    }
	catch (IOException e)
	    {
	    	System.out.println("Error loading the training database");
	    }		
    }

    /* initialization */
    public void init()
    {
	int i,j;
	double randomvalue;
	read_data();

	/* weight initialization */
	for(i=0;i<INPUTS;i++)
	    for(j=0;j<HIDDEN;j++) {
		randomvalue = Math.random();
		inhiddw[i][j] =  -0.5 + randomvalue;
		deltaihw[i][j] = 0;
	    }

	for(i=0;i<HIDDEN;i++)
	    for(j=0;j<OUTPUTS;j++) {
		randomvalue = Math.random();
		hidoutw[i][j] =  -0.5 + randomvalue;
		deltahow[i][j] = 0;
	    }

	for(i=0;i<NUMTRAIN;i++)
	    lrnpatr[i] = false;
    }

    // Neural network training
    void training()
    {
	int i,j,t,rep;           
	boolean l;
	float somme = 0;
	int iterations = 0;
	System.out.println("\nTRAINING\n");
	i=0; j=0;
	do {
	    do {
		// select a random training pattern: i = (int)(NUMTRAIN*rnd), where 0<rnd<1 
		i = (int)(NUMTRAIN*Math.random());
		iterations++;
		if(iterations % 100 == 0) 
		    System.out.println(iterations);
		if(i==NUMTRAIN)
		    i--;
	    } while(lrnpatr[i]);
	    j++;
	    netanswer(patterns[i]);  
	    backprop(i);
	    error();
	    l = true;
	    somme = 0;

	    /* test if a given pattern is properly recognized */
	    for(t=0;t<NUMTRAIN;t++) {
		lrnpatr[t] = sme[t] < EPSILON;
		l = l && lrnpatr[t];
	    }
	} while(!l);


	System.out.println("\n\n End of training\n");
	System.out.println(iterations+"\n");
    }

    /* copute the outputs of he neural network */
    void netanswer(double[] afer)
    {
	int i,j;
	double totin;
	for(i=0;i<INPUTS;i++)
	    x[i] = afer[i];
	for(j=0;j<HIDDEN;j++) {
	    totin = 0;
	    for(i=0;i<INPUTS;i++) 
		totin = totin + x[i]*inhiddw[i][j];
	    y[j] = sigm(totin);
	}
	for(j=0;j<OUTPUTS;j++) {
	    totin = 0;
	    for(i=0;i<HIDDEN;i++)
		totin = totin + y[i]*hidoutw[i][j];
	    z[j] = sigm(totin);
	}

    }

    double se(double[] a,double[] b,int SIZE)   /* Error measure */
    {
	int i;
	double e=0;

	for(i=0;i<SIZE;i++)
	    e = e + (a[i] - b[i])*(a[i] - b[i]);
	e = 0.5 * e;
	return e;
    }

    void betaout(int patternnum)   /* error of the output neurons */
    {
	int k;
	for(k=0;k<OUTPUTS;k++)
	    eout[k] = 0;

	for(k=0;k<OUTPUTS;k++)
	    eout[k] = (z[k] - desout[patternnum][k])*(z[k]*(1.0 - z[k]));
    }

    void betahid()   /* error of the hidden neurons */
    {
	int j,k;
	for(j=0;j<HIDDEN;j++)
	    ehid[j] = 0;

	for(j=0;j<HIDDEN;j++) 
	    for(k=0;k<OUTPUTS;k++)
		ehid[j] = ehid[j] + hidoutw[j][k]*(y[j]*(1-y[j])*eout[k]);
    }

    /* Backpropagation of the error and weight update */
    void backprop(int patternnum)
    {
	int i,j,k;
	double temp;

	betaout(patternnum); 
	betahid();
	 
	for(j=0;j<HIDDEN;j++)
	    for(k=0;k<OUTPUTS;k++) {
		temp = -delta*y[j]*eout[k];
		hidoutw[j][k] = hidoutw[j][k] + temp + alfa*deltahow[j][k];
		deltahow[j][k] = temp;
	    }

	for(i=0;i<INPUTS;i++)
	    for(j=0;j<HIDDEN;j++) {
		temp = -delta*x[i]*ehid[j];
		inhiddw[i][j] = inhiddw[i][j] + temp + alfa*deltaihw[i][j];
		deltaihw[i][j] = temp;
	    }
    }   

    /* Output error */
    void error()
    {
	int i;

	for(i=0;i<NUMTRAIN;i++) {
	    netanswer(patterns[i]);
	    sme[i]=se(desout[i],z,OUTPUTS);
	}
    }

    /* Test of the trained neural network */
    void test()
    {
	BufferedReader lecteurAvecBuffer = null;
	String ligne;
	String[] trame;

	try
	    {
	    	lecteurAvecBuffer = new BufferedReader(new FileReader(testfile));
	    }
	catch(FileNotFoundException exc)
	    {
	    	System.out.println("Error reading the test database");
	    }

	try
	    {
		for(int i = 0; i<18; i++){
		    ligne = lecteurAvecBuffer.readLine();
		    trame = ligne.split(",");
		    //System.out.println(ligne);
		    for(int j=0;j<trame.length-1;j++){
			matrizin[i][j] = Double.parseDouble(trame[j]);
		    }
		    /* present a test pattern and compute the neural network output */
		    netanswer(matrizin[i]);
		    System.out.print(i+": ");
		    for(int j=0;j<OUTPUTS;j++){
			/* show the outputs with an activation larger than 0.6 */
			if(z[j] > 0.6)
			    System.out.print("Out["+j+"]="+z[j]+",");
		    }
		    System.out.print("\n");
		}
		lecteurAvecBuffer.close();
	    }
	catch (IOException e)
	    {
	    	System.out.println("Error reading the test database");
	    }	
    }

    /* main program */
    public static void main(String[] args)
    {
	Bkprop exec = new Bkprop();
	exec.init();
	exec.training();
	exec.test(); 
    }
}