home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / ddjmag / ddj8901.arc / NNFIL.ASC < prev    next >
Text File  |  1989-01-02  |  10KB  |  287 lines
  1. _NEURAL NETS AND NOISE FILTERING_
  2.  
  3. by Casey Klimasauskas
  4.  
  5.  
  6.  
  7. [LISTIN╟ ONE]
  8.  
  9. /* (backprop.c)  Back-propagation XOR example */
  10.  
  11. #include <stdio.h>
  12.  
  13. /************************************************************************
  14.  *  Back-propagation Exclusive OR Program                               *    
  15.  ************************************************************************
  16.  Written by Casimir C. Klimasauskas.  No copyright or other
  17.  proprietary rights reserved.
  18.    This program was compiled and tested using DataLight "C" version 3.14
  19.    as follows: DLC -ms backprop.c
  20.    NOTE:  the structure "_conn" uses an index for the PE source.  This was
  21.    done (rather than a pointer to the processing element itself) to get
  22.    around certain problems with handling circular references in structure
  23.    definitions.
  24.  */
  25.  
  26. #define MAXCONN     5           /* maximum number of conn */
  27.  
  28. typedef struct _conn {          /* connection to a PE */
  29.     int          PESource;      /* index of PE source */
  30.     float        ConnWt;        /* connection Wt */
  31.     float        LastDelta;     /* last weight change */
  32. } CONN;
  33.  
  34. typedef struct _pe {            /* processing element */
  35.     float        Output;        /* PE output */
  36.     float        Error;         /* Accumulated error */
  37.     CONN         Conns[MAXCONN+1];  /* connections */
  38. } PE;
  39.  
  40. /************************************************************************
  41.  *      Network Topology                                                *
  42.  ************************************************************************
  43.    The following diagram shows how the processing elements have been
  44.    connected to solve the exclusive "OR" problem.  This is taken from
  45.    Volume 1 of "Parallel Distributed Processing" by Rummelhart and
  46.    McClelland.
  47.  
  48.      +--------------------- PE5
  49.      |                     / | \
  50.      |                   /   |  \
  51.      +-----------------/----PE4  \
  52.      |                 |  /    \  |
  53.      |                 | /      \ |
  54.      |                 |/        \|
  55.     PE1 - bias        PE2        PE3
  56.  
  57. */
  58. static PE pe1 = { 1.0, 0 };                               /* bias */
  59. static PE pe2 = { 0 };                                    /* inputs */
  60. static PE pe3 = { 0 };
  61. static PE pe4 = { 0, 0,  1,0,0,  2,0,0,  3,0,0 };         /* hidden */
  62. static PE pe5 = { 0, 0,  1,0,0,  2,0,0,  3,0,0,  4,0,0 }; /* output */
  63.  
  64. /* --- Processing Elements (for reference by number) ---- */
  65. static PE *PEList[] = { (PE *)0, &pe1, &pe2, &pe3, &pe4, &pe5 };
  66.  
  67. /* --- Layer definitions --- */
  68. static PE *LayIn[]  = { &pe2, &pe3, (PE *)0 };  /* input layer list */
  69. static PE *LayMid[] = { &pe4, (PE *)0 };        /* hidden layer list */
  70. static PE *LayOut[] = { &pe5, (PE *)0 };        /* output layer list */
  71.  
  72. /* --- Network List --- */
  73. static PE **LayList[] = { &LayIn[0], &LayMid[0], &LayOut[0], (PE **)0 };
  74.  
  75. /************************************************************************
  76.  *  Sigmoid() - Compute the sigmoid of a value                          *
  77.  ************************************************************************
  78.  */
  79. double sigmoid( x )
  80.     double   x;
  81.     {
  82.     double   r;         /* result */
  83.     extern double exp();
  84.  
  85.     /* check special limiting cases to prevent overflow */
  86.     if ( x < -10. ) r = 0.0;
  87.     else if ( x > 10. ) r = 1.0;
  88.     else        r = 1.0 / (1.0 + exp( -x ));
  89.  
  90.     return( r );
  91.     }
  92.  
  93. /************************************************************************
  94.  *  RRand() - Compute a random number in a range                        *
  95.  ************************************************************************
  96.  */
  97. double RRand( low, high )
  98.     double low, high;          /* low / high limits */
  99.     {
  100.     double r;               /* return result */
  101.     extern int rand();          /* random number generator */
  102.  
  103.     r = (rand() / 32767.) * (high - low) + low;
  104.  
  105.     return( r );
  106.     }
  107.  
  108. /************************************************************************
  109.  *  RandWts()  - randomize all of the weights in a network              *
  110.  ************************************************************************
  111.  */
  112. void RandWts( low, high, LLp )
  113.     double    low, high;        /* low / high limits for random */
  114.     PE         ***LLp;          /* layer list pointer */
  115.     {
  116.     PE      **PePP; /* PE Pointer */
  117.     PE       *PeP;  /* PE itself */
  118.     CONN     *WtP;  /* connection Pointer */
  119.  
  120.     for( ; (PePP = *LLp) != (PE **)0; LLp++ )       /* layer loop */
  121.     for( ; (PeP = *PePP) != (PE *)0; PePP++ )       /* PE loop */
  122.         for( WtP = &PeP->Conns[0]; WtP->PESource != 0; WtP++ )
  123.         {
  124.         WtP->ConnWt = RRand( low, high );
  125.         WtP->LastDelta = 0.0;
  126.         }
  127.     return;
  128.     }
  129.  
  130. /************************************************************************
  131.  *  Recall() - Recall information from the network                      *
  132.  ************************************************************************
  133.  */
  134. void Recall( ov, iv, LLp, rcf )
  135.     double   *ov;           /* output vector */
  136.     double   *iv;           /* input vector */
  137.     PE     ***LLp;          /* layer list pointer */
  138.     int       rcf;          /* "recall" mode flag (0=learn) */
  139.     {
  140.     PE      **PePP;         /* PE Pointer */
  141.     PE      **LastPP;       /* last non-zero PE list pointer */
  142.     PE       *PeP;          /* PE itself */
  143.     CONN     *WtP;          /* connection Pointer */
  144.     double    sum;          /* weighted sum */
  145.  
  146.    /* copy the input vector to the inputs of the network */
  147.     for( PePP = *LLp++; (PeP = *PePP) != (PE *)0; PePP++ )
  148.     PeP->Output = *iv++;
  149.  
  150.    /* compute the weighted sum and transform it */
  151.     for( ; (PePP = *LLp) != (PE **)0; LLp++ )       /* layer loop */
  152.     {
  153.     LastPP = PePP;
  154.     for( ; (PeP = *PePP) != (PE *)0; PePP++ )   /* PE's in a layer */
  155.         {
  156.         /* weighted sum of the inputs */
  157.         sum = 0;
  158.         for( WtP = &PeP->Conns[0]; WtP->PESource != 0; WtP++ )
  159.         sum += WtP->ConnWt * PEList[ WtP->PESource ]->Output;
  160.  
  161.         /* transform it using a sigmoidal transfer function */
  162.         PeP->Output = sigmoid( sum );
  163.  
  164.         /* if "learn" mode, set the error to zero */
  165.         if ( rcf == 0 ) PeP->Error  = 0.0;      /* (for learning) */
  166.         }
  167.     }
  168.  
  169. /* copy the results to the output array */
  170. if ( rcf != 0 )     /* only if not learning */
  171.     {
  172.     for( ; (PeP = *LastPP) != (PE *)0; LastPP++ )
  173.         *ov++ = PeP->Output;
  174.     }
  175.     return;
  176.     }
  177.  
  178. /************************************************************************
  179.  *  Learn() - "learn" an association                                    *
  180.  ************************************************************************
  181.  */
  182. double Learn( ov, iv, LLp, alpha, eta )
  183.     double   *ov;           /* output vector */
  184.     double   *iv;           /* input vector */
  185.     PE     ***LLp;          /* layer list pointer */
  186.     double    alpha;        /* learning rate */
  187.     double    eta;          /* momentum */
  188.     {
  189.     double    MAErr;        /* Maximum Absolute error */
  190.     double    rv;           /* work value */
  191.     double    SigErr;       /* back-propagated error */
  192.     PE     ***ALp;          /* alternate layer pointer */
  193.     PE      **PePP;         /* PE Pointer */
  194.     PE      **LastPP;       /* last non-zero PE list pointer */
  195.     PE       *PeP;          /* PE itself */
  196.     CONN     *WtP;          /* connection Pointer */
  197.     extern double fabs();      /* absolute value */
  198.  
  199.     Recall( ov, iv, LLp, 0 );           /* perform a recall */
  200.  
  201.     /* find the output layer */
  202.     for( ALp = LLp; ALp[1] != (PE **)0; ALp++ )
  203.     ;
  204.  
  205.     /* compute the square error in the output */
  206.     for( MAErr = 0.0, PePP = *ALp; (PeP = *PePP) != (PE *)0; PePP++ )
  207.     {
  208.     rv = *ov++ - PeP->Output;       /* output Error */
  209.     PeP->Error = rv;
  210.     if ( fabs(rv) > MAErr ) MAErr = fabs(rv);
  211.     }
  212.  
  213.     /* back-propagate the error & update the weights */
  214.     for( ; ALp > LLp; ALp-- )           /* layer loop */
  215.     {
  216.     PePP = *ALp;
  217.     for( ; (PeP = *PePP) != (PE *)0; PePP++ )   /* PE's in a layer */
  218.         {
  219.         /* compute the error prior to the sigmoid function */
  220.         SigErr = PeP->Output * (1.0 - PeP->Output) * PeP->Error;
  221.  
  222.         /* back-propagate the errors & adjust weights */
  223.         for( WtP = &PeP->Conns[0]; WtP->PESource != 0; WtP++ )
  224.         {
  225.         PEList[ WtP->PESource ]->Error +=
  226.             WtP->ConnWt * SigErr;
  227.         rv = alpha * PEList[ WtP->PESource ]->Output * SigErr +
  228.             eta * WtP->LastDelta;
  229.         WtP->ConnWt += rv;
  230.         WtP->LastDelta = rv;
  231.         }
  232.         }
  233.     }
  234.     return( MAErr );
  235.     }
  236.  
  237. /************************************************************************
  238.  *  Main() - main driver routine to train the network                   *
  239.  ************************************************************************
  240.  */
  241. static double iv1[] = { 0.0, 0.0 }; static double ov1[] = { 0.0 };
  242. static double iv2[] = { 1.0, 0.0 }; static double ov2[] = { 1.0 };
  243. static double iv3[] = { 0.0, 1.0 }; static double ov3[] = { 1.0 };
  244. static double iv4[] = { 1.0, 1.0 }; static double ov4[] = { 0.0 };
  245.  
  246. static double *ivp[] = { &iv1[0], &iv2[0], &iv3[0], &iv4[0] };
  247. static double *ovp[] = { &ov1[0], &ov2[0], &ov3[0], &ov4[0] };
  248.  
  249. main()
  250.     {
  251.     int      wx;        /* work index */
  252.     int      x;     /* index into samples array */
  253.     double   r;     /* work value */
  254.     double   MAErr;     /* maximum Absolute error */
  255.     double   wo[sizeof(ivp)/sizeof(*ivp)];
  256.  
  257.     /* randomize the weights in the network */
  258.     RandWts( -1.0, 1.0, &LayList[0] );
  259.  
  260.     MAErr = 0.0;
  261.     for( wx = 0; ; wx++ )
  262.     {
  263.     x = wx % (sizeof(ivp)/sizeof(*ivp));
  264.     if ( x == 0 && wx != 0 )
  265.         {
  266.         if ( (wx % 100) == 0 )
  267.         printf( "Presentation %4d, Maximum Absolute Error = %.5f\n",
  268.             wx, MAErr );
  269.         if ( MAErr < .1 ) break;
  270.         MAErr = 0.0;
  271.         }
  272.  
  273.     r = Learn( ovp[x], ivp[x], &LayList[0], 0.9, 0.5 );
  274.     if ( r > MAErr ) MAErr = r;
  275.     }
  276.  
  277.     /* test the network */
  278.     for( wx = 0; wx < (sizeof(ivp)/sizeof(*ivp)); wx++ )
  279.     {
  280.     Recall( wo, ivp[wx], &LayList[0], 1 );      /* perform a recall */
  281.     printf( "Input: %.2f %.2f -> %.2f\n", ivp[wx][0], ivp[wx][1], wo[0] );
  282.     }
  283.  
  284.     return;
  285.     }
  286.  
  287.