home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d1xx / d160 / neuralnets.lha / NeuralNets / Bpsim.c < prev    next >
C/C++ Source or Header  |  1988-10-02  |  18KB  |  584 lines
  1. /*
  2.  * See bottom for address of author.
  3.  *
  4.  * title:       bpsim.c
  5.  * author:      Josiah C. Hoskins
  6.  * date:        June 1987
  7.  *
  8.  * purpose:     backpropagation learning rule neural net simulator
  9.  *              for the tabula rasa Little Red Riding Hood example
  10.  *
  11.  * description: Bpsim provides an implementation of a neural network
  12.  *              containing a single hidden layer which uses the
  13.  *              generalized backpropagation delta rule for learning.
  14.  *              A simple user interface is supplied for experimenting
  15.  *              with a neural network solution to the Little Red Riding
  16.  *              Hood example described in the text.
  17.  *
  18.  *              In addition, bpsim contains some useful building blocks
  19.  *              for further experimentation with single layer neural
  20.  *              networks. The data structure which describes the general
  21.  *              processing unit allows one to easily investigate different
  22.  *              activation (output) and/or error functions. The utility
  23.  *              function create_link can be used to create links between
  24.  *              any two units by supplying your own create_in_out_links
  25.  *              function. The flexibility of creating units and links
  26.  *              to your specifications allows one to modify the code
  27.  *              to tune the network architecture to problems of interest.
  28.  *
  29.  *              There are some parameters that perhaps need some
  30.  *              explanation. You will notice that the target values are
  31.  *              either 0.1 or 0.9 (corresponding to the binary values
  32.  *              0 or 1). With the sigmoidal function used in out_f the
  33.  *              weights become very large if 0 and 1 are used as targets.
  34.  *              The ON_TOLERANCE value is used as a criteria for an output
  35.  *              value to be considered "on", i.e., close enough to the
  36.  *              target of 0.9 to be considered 1. The learning_rate and
  37.  *              momentum variables may be changed to vary the rate of
  38.  *              learning, however, in general they each should be less
  39.  *              than 1.0.
  40.  *
  41.  *              Bpsim has been compiled using CI-C86 version 2.30 on an
  42.  *              IBM-PC and the Sun C compiler on a Sun 3/160.
  43.  *
  44.  *              Note to compile and link on U*IX machines use:
  45.  *                      cc -o bpsim bpsim.c -lm
  46.  *
  47.  *              For other machines remember to link in the math library.
  48.  *
  49.  * status:      This program may be freely used, modified, and distributed
  50.  *              except for commercial purposes.
  51.  *
  52.  * Copyright (c) 1987   Josiah C. Hoskins
  53.  */
  54.  /* Modified to function properly under Turbo C by replacing malloc(...)
  55.     with calloc(...,1). Thanks to Pavel Rozalski who detected the error.
  56.     He assumed that Turbo C's "malloc" doesn't automatically set pointers
  57.     to NULL - and he was right!
  58.     Thomas Muhr, Berlin April, 1988
  59.  */
  60.  
  61. #include <math.h>
  62. #include <stdio.h>
  63. #include <ctype.h>
  64.  
  65. #define BUFSIZ          512
  66.  
  67. #define FALSE           0
  68. #define TRUE            !FALSE
  69. #define NUM_IN          6       /* number of input units */
  70. #define NUM_HID         3       /* number of hidden units */
  71. #define NUM_OUT         7       /* number of output units */
  72. #define TOTAL           (NUM_IN + NUM_HID + NUM_OUT)
  73. #define BIAS_UID        (TOTAL) /* threshold unit */
  74.  
  75. /* macros to provide indexes for processing units */
  76. #define IN_UID(X)       (X)
  77. #define HID_UID(X)      (NUM_IN + X)
  78. #define OUT_UID(X)      (NUM_IN + NUM_HID + X)
  79. #define TARGET_INDEX(X) (X - (NUM_IN + NUM_HID))
  80.  
  81. #define WOLF_PATTERN    0
  82. #define GRANDMA_PATTERN 1
  83. #define WOODCUT_PATTERN 2
  84. #define PATTERNS        3       /* number of input patterns */
  85. #define ERROR_TOLERANCE 0.01
  86. #define ON_TOLERANCE    0.8     /* a unit's output is on if > ON_TOLERENCE */
  87. #define NOTIFY          10      /* iterations per dot notification */
  88. #define DEFAULT_ITER    250
  89.  
  90. struct unit {                   /* general processing unit */
  91.   int    uid;                   /* integer uniquely identifying each unit */
  92.   char   *label;
  93.   double output;                /* activation level */
  94.   double (*unit_out_f)();       /* note output fcn == activation fcn*/
  95.   double delta;                 /* delta for unit */
  96.   double (*unit_delta_f)();     /* ptr to function to calc delta */
  97.   struct link *inlinks;         /* for propagation */
  98.   struct link *outlinks;        /* for back propagation */
  99. } *pu[TOTAL+1];                 /* one extra for the bias unit */
  100.  
  101. struct link {                   /* link between two processing units */
  102.   char   *label;
  103.   double weight;                /* connection or link weight */
  104.   double data;                  /* used to hold the change in weights */
  105.   int    from_unit;             /* uid of from unit */
  106.   int    to_unit;               /* uid of to unit */
  107.   struct link *next_inlink;
  108.   struct link *next_outlink;
  109. };
  110.  
  111. int     iterations = DEFAULT_ITER;
  112. double  learning_rate = 0.2;
  113. double  momentum = 0.9;
  114. double  pattern_err[PATTERNS];
  115.  
  116. /*
  117.  * Input Patterns
  118.  * {Big Ears, Big Eyes, Big Teeth, Kindly, Wrinkled, Handsome}
  119.  *   unit 0    unit 1     unit 2   unit 3   unit 4    unit 5
  120.  */
  121. double  input_pat[PATTERNS+1][NUM_IN] = {
  122.   {1.0, 1.0, 1.0, 0.0, 0.0, 0.0},       /* Wolf */
  123.   {0.0, 1.0, 0.0, 1.0, 1.0, 0.0},       /* Grandma */
  124.   {1.0, 0.0, 0.0, 1.0, 0.0, 1.0},       /* Woodcutter */
  125.   {0.0, 0.0, 0.0, 0.0, 0.0, 0.0},       /* Used for Recognize Mode */
  126. };
  127.  
  128. /*
  129.  * Target Patterns
  130.  * {Scream, Run Away, Look for Woodcutter, Approach, Kiss on Cheek,
  131.  *      Offer Food, Flirt with}
  132.  */
  133. double  target_pat[PATTERNS][NUM_OUT] = {
  134.   {0.9, 0.9, 0.9, 0.1, 0.1, 0.1, 0.1},  /* response to Wolf */
  135.   {0.1, 0.1, 0.1, 0.9, 0.9, 0.9, 0.1},  /* response to Grandma */
  136.   {0.1, 0.1, 0.1, 0.9, 0.1, 0.9, 0.9},  /* response to Woodcutter */
  137. };
  138.  
  139. /*
  140.  * function declarations
  141.  */
  142. void    print_header();
  143. char    get_command();
  144. double  out_f(), delta_f_out(), delta_f_hid(), random(), pattern_error();
  145.  
  146.  
  147. main()
  148. {
  149.   char   ch;
  150.   extern struct unit *pu[];
  151.  
  152.   print_header();
  153.   create_processing_units(pu);
  154.   create_in_out_links(pu);
  155.   for (;;) {
  156.     ch = get_command("\nEnter Command (Learn, Recognize, Quit) => ");
  157.     switch (ch) {
  158.     case 'l':
  159.     case 'L':
  160.       printf("\n\tLEARN MODE\n\n");
  161.       learn(pu);
  162.       break;
  163.     case 'r':
  164.     case 'R':
  165.       printf("\n\tRECOGNIZE MODE\n\n");
  166.       recognize(pu);
  167.       break;
  168.     case 'q':
  169.     case 'Q':
  170.       exit(1);
  171.       break;
  172.     default:
  173.       fprintf(stderr, "Invalid Command\n");
  174.       break;
  175.     }
  176.   }
  177. }
  178.  
  179.  
  180. void
  181. print_header()
  182. {
  183.   printf("%s%s%s",
  184.          "\n\tBPSIM -- Back Propagation Learning Rule Neural Net Simulator\n",
  185.          "\t\t for the tabula rasa Little Red Riding Hood example.\n\n",
  186.          "\t\t Written by Josiah C. Hoskins\n");
  187. }
  188.  
  189.  
  190. /*
  191.  * create input, hidden, output units (and threshold or bias unit)
  192.  */
  193. create_processing_units(pu)
  194. struct  unit *pu[];
  195. {
  196.   int   id;                     /* processing unit index */
  197.   struct unit *create_unit();
  198.  
  199.   for (id = IN_UID(0); id < IN_UID(NUM_IN); id++)
  200.     pu[id] = create_unit(id, "input", 0.0, NULL, 0.0, NULL);
  201.   for (id = HID_UID(0); id < HID_UID(NUM_HID); id++)
  202.     pu[id] = create_unit(id, "hidden", 0.0, out_f, 0.0, delta_f_hid);
  203.   for (id = OUT_UID(0); id < OUT_UID(NUM_OUT); id++)
  204.     pu[id] = create_unit(id, "output", 0.0, out_f, 0.0, delta_f_out);
  205.   pu[BIAS_UID] = create_unit(BIAS_UID, "bias", 1.0, NULL, 0.0, NULL);
  206. }
  207.  
  208.  
  209. /*
  210.  * create links - fully connected for each layer
  211.  *                note: the bias unit has one link to ea hid and out unit
  212.  */
  213. create_in_out_links(pu)
  214. struct  unit *pu[];
  215. {
  216.   int   i, j;           /* i == to and j == from unit id's */
  217.   struct link *create_link();
  218.  
  219.   /* fully connected units */
  220.   for (i = HID_UID(0); i < HID_UID(NUM_HID); i++) { /* links to hidden */
  221.     pu[BIAS_UID]->outlinks =
  222.       pu[i]->inlinks = create_link(pu[i]->inlinks, i,
  223.                                    pu[BIAS_UID]->outlinks, BIAS_UID,
  224.                                    (char *)NULL,
  225.                                    random(), 0.0);
  226.     for (j = IN_UID(0); j < IN_UID(NUM_IN); j++) /* from input units */
  227.       pu[j]->outlinks =
  228.         pu[i]->inlinks = create_link(pu[i]->inlinks, i, pu[j]->outlinks, j,
  229.                                      (char *)NULL, random(), 0.0);
  230.   }
  231.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) {     /* links to output */
  232.     pu[BIAS_UID]->outlinks =
  233.             pu[i]->inlinks = create_link(pu[i]->inlinks, i,
  234.                                          pu[BIAS_UID]->outlinks, BIAS_UID,
  235.                                          (char *)NULL, random(), 0.0);
  236.     for (j = HID_UID(0); j < HID_UID(NUM_HID); j++) /* from hidden units */
  237.       pu[j]->outlinks =
  238.         pu[i]->inlinks = create_link(pu[i]->inlinks, i, pu[j]->outlinks, j,
  239.                                      (char *)NULL, random(), 0.0);
  240.   }
  241. }
  242.  
  243.  
  244. /*
  245.  * return a random number bet 0.0 and 1.0
  246.  */
  247. double
  248. random()
  249. {
  250.   return((rand() % 32727) / 32737.0);
  251. }
  252.  
  253.  
  254. /*
  255.  * the next two functions are general utility functions to create units
  256.  * and create links
  257.  */
  258. struct unit *
  259. create_unit(uid, label, output, out_f, delta, delta_f)
  260. int  uid;
  261. char *label;
  262. double   output, delta;
  263. double   (*out_f)(), (*delta_f)();
  264. {
  265.   struct unit  *unitptr;
  266.  
  267. /*
  268.   if (!(unitptr = (struct unit *)malloc(sizeof(struct unit)))) {
  269. TURBO C doesnt automatically set pointers to NULL - so use calloc(...,1) */
  270.   if (!(unitptr = (struct unit *)calloc(sizeof(struct unit),1))) {
  271.     fprintf(stderr, "create_unit: not enough memory\n");
  272.     exit(1);
  273.   }
  274.   /* initialize unit data */
  275.   unitptr->uid = uid;
  276.   unitptr->label = label;
  277.   unitptr->output = output;
  278.   unitptr->unit_out_f = out_f;  /* ptr to output fcn */
  279.   unitptr->delta = delta;
  280.   unitptr->unit_delta_f = delta_f;
  281.   return (unitptr);
  282. }
  283.  
  284.  
  285. struct link *
  286. create_link(start_inlist, to_uid, start_outlist, from_uid, label, wt, data)
  287. struct  link *start_inlist, *start_outlist;
  288. int     to_uid, from_uid;
  289. char *  label;
  290. double  wt, data;
  291. {
  292.   struct link  *linkptr;
  293.  
  294. /*  if (!(linkptr = (struct link *)malloc(sizeof(struct link)))) { */
  295.   if (!(linkptr = (struct link *)calloc(sizeof(struct link),1))) {
  296.     fprintf(stderr, "create_link: not enough memory\n");
  297.     exit(1);
  298.   }
  299.   /* initialize link data */
  300.   linkptr->label = label;
  301.   linkptr->from_unit = from_uid;
  302.   linkptr->to_unit = to_uid;
  303.   linkptr->weight = wt;
  304.   linkptr->data = data;
  305.   linkptr->next_inlink = start_inlist;
  306.   linkptr->next_outlink = start_outlist;
  307.   return(linkptr);
  308. }
  309.  
  310.  
  311. char
  312. get_command(s)
  313. char    *s;
  314. {
  315.   char  command[BUFSIZ];
  316.  
  317.   fputs(s, stdout);
  318.   fflush(stdin); fflush(stdout);
  319.   (void)fgets(command, BUFSIZ, stdin);
  320.   return((command[0]));         /* return 1st letter of command */
  321. }
  322.  
  323.  
  324. learn(pu)
  325. struct unit *pu[];
  326. {
  327.   register i, temp;
  328.   char   tempstr[BUFSIZ];
  329.   extern int    iterations;
  330.   extern double learning_rate, momentum;
  331.   static char prompt[] = "Enter # iterations (default is 250) => ";
  332.   static char quote1[] = "Perhaps, Little Red Riding Hood ";
  333.   static char quote2[] = "should do more learning.\n";
  334.  
  335.   printf(prompt);
  336.   fflush(stdin); fflush(stdout);
  337.   gets(tempstr);
  338.   if (temp = atoi(tempstr))
  339.     iterations = temp;
  340.  
  341.   printf("\nLearning ");
  342.   for (i = 0; i < iterations; i++) {
  343.     if ((i % NOTIFY) == 0) {
  344.       printf(".");
  345.       fflush(stdout);
  346.     }
  347.     bp_learn(pu, (i == iterations-2 || i == iterations-1 || i == iterations));
  348.   }
  349.   printf(" Done\n\n");
  350.   printf("Error for Wolf pattern = \t%lf\n", pattern_err[0]);
  351.   printf("Error for Grandma pattern = \t%lf\n", pattern_err[1]);
  352.   printf("Error for Woodcutter pattern = \t%lf\n", pattern_err[2]);
  353.   if (pattern_err[WOLF_PATTERN] > ERROR_TOLERANCE) {
  354.     printf("\nI don't know the Wolf very well.\n%s%s", quote1, quote2);
  355.   } else if (pattern_err[GRANDMA_PATTERN] > ERROR_TOLERANCE) {
  356.     printf("\nI don't know Grandma very well.\n%s%s", quote1, quote2);
  357.   } else if (pattern_err[WOODCUT_PATTERN] > ERROR_TOLERANCE) {
  358.     printf("\nI don't know Mr. Woodcutter very well.\n%s%s", quote1, quote2);
  359.   } else {
  360.     printf("\nI feel pretty smart, now.\n");
  361.   }
  362. }
  363.  
  364.  
  365. /*
  366.  * back propagation learning
  367.  */
  368. bp_learn(pu, save_error)
  369. struct unit *pu[];
  370. int    save_error;
  371. {
  372.   static int count = 0;
  373.   static int pattern = 0;
  374.   extern double pattern_err[PATTERNS];
  375.  
  376.   init_input_units(pu, pattern); /* initialize input pattern to learn */
  377.   propagate(pu);                 /* calc outputs to check versus targets */
  378.   if (save_error)
  379.     pattern_err[pattern] = pattern_error(pattern, pu);
  380.   bp_adjust_weights(pattern, pu);
  381.   if (pattern < PATTERNS - 1)
  382.     pattern++;
  383.   else
  384.       pattern = 0;
  385.   count++;
  386. }
  387.  
  388.  
  389. /*
  390.  * initialize the input units with a specific input pattern to learn
  391.  */
  392. init_input_units(pu, pattern)
  393. struct unit *pu[];
  394. int    pattern;
  395. {
  396.   int   id;
  397.  
  398.   for (id = IN_UID(0); id < IN_UID(NUM_IN); id++)
  399.     pu[id]->output = input_pat[pattern][id];
  400. }
  401.  
  402.  
  403. /*
  404.  * calculate the activation level of each unit
  405.  */
  406. propagate(pu)
  407. struct unit *pu[];
  408. {
  409.   int   id;
  410.  
  411.   for (id = HID_UID(0); id < HID_UID(NUM_HID); id++)
  412.     (*(pu[id]->unit_out_f))(pu[id], pu);
  413.   for (id = OUT_UID(0); id < OUT_UID(NUM_OUT); id++)
  414.     (*(pu[id]->unit_out_f))(pu[id], pu);
  415. }
  416.  
  417.  
  418. /*
  419.  * function to calculate the activation or output of units
  420.  */
  421. double
  422. out_f(pu_ptr, pu)
  423. struct unit *pu_ptr, *pu[];
  424. {
  425.   double sum = 0.0, exp();
  426.   struct link *tmp_ptr;
  427.  
  428.   tmp_ptr = pu_ptr->inlinks;
  429.   while (tmp_ptr) {
  430.     /* sum up (outputs from inlinks times weights on the inlinks) */
  431.     sum += pu[tmp_ptr->from_unit]->output * tmp_ptr->weight;
  432.     tmp_ptr = tmp_ptr->next_inlink;
  433.   }
  434.   pu_ptr->output = 1.0/(1.0 + exp(-sum));
  435. }
  436.  
  437.  
  438. /*
  439.  * half of the sum of the squares of the errors of the
  440.  * output versus target values
  441.  */
  442. double
  443. pattern_error(pat_num, pu)
  444. int     pat_num;        /* pattern number */
  445. struct  unit *pu[];
  446. {
  447.   int           i;
  448.   double        temp, sum = 0.0;
  449.  
  450.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) {
  451.     temp = target_pat[pat_num][TARGET_INDEX(i)] - pu[i]->output;
  452.     sum += temp * temp;
  453.   }
  454.   return (sum/2.0);
  455. }
  456.  
  457.  
  458. bp_adjust_weights(pat_num, pu)
  459. int     pat_num;        /* pattern number */
  460. struct  unit *pu[];
  461. {
  462.   int           i;              /* processing units id */
  463.   double        temp1, temp2, delta, error_sum;
  464.   struct link   *inlink_ptr, *outlink_ptr;
  465.  
  466.   /* calc deltas */
  467.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) /* for each output unit */
  468.     (*(pu[i]->unit_delta_f))(pu, i, pat_num); /* calc delta */
  469.   for (i = HID_UID(0); i < HID_UID(NUM_HID); i++) /* for each hidden unit */
  470.     (*(pu[i]->unit_delta_f))(pu, i);      /* calc delta */
  471.   /* calculate weights */
  472.   for (i = OUT_UID(0); i < OUT_UID(NUM_OUT); i++) {     /* for output units */
  473.     inlink_ptr = pu[i]->inlinks;
  474.     while (inlink_ptr) {        /* for each inlink to output unit */
  475.       temp1 = learning_rate * pu[i]->delta *
  476.         pu[inlink_ptr->from_unit]->output;
  477.       temp2 = momentum * inlink_ptr->data;
  478.       inlink_ptr->data = temp1 + temp2; /* new delta weight */
  479.       inlink_ptr->weight += inlink_ptr->data;   /* new weight */
  480.       inlink_ptr = inlink_ptr->next_inlink;
  481.     }
  482.   }
  483.   for (i = HID_UID(0); i < HID_UID(NUM_HID); i++) { /* for ea hid unit */
  484.     inlink_ptr = pu[i]->inlinks;
  485.     while (inlink_ptr) {        /* for each inlink to output unit */
  486.       temp1 = learning_rate * pu[i]->delta *
  487.         pu[inlink_ptr->from_unit]->output;
  488.       temp2 = momentum * inlink_ptr->data;
  489.       inlink_ptr->data = temp1 + temp2; /* new delta weight */
  490.       inlink_ptr->weight += inlink_ptr->data;   /* new weight */
  491.         inlink_ptr = inlink_ptr->next_inlink;
  492.     }
  493.   }
  494. }
  495.  
  496.  
  497. /*
  498.  * calculate the delta for an output unit
  499.  */
  500. double
  501. delta_f_out(pu, uid, pat_num)
  502. struct unit *pu[];
  503. int    uid, pat_num;
  504. {
  505.   double        temp1, temp2, delta;
  506.  
  507.   /* calc deltas */
  508.   temp1 = (target_pat[pat_num][TARGET_INDEX(uid)] - pu[uid]->output);
  509.   temp2 = (1.0 - pu[uid]->output);
  510.   delta = temp1 * pu[uid]->output * temp2; /* calc delta */
  511.   pu[uid]->delta = delta; /* store delta to pass on */
  512. }
  513.  
  514.  
  515. /*
  516.  * calculate the delta for a hidden unit
  517.  */
  518. double
  519. delta_f_hid(pu, uid)
  520. struct unit *pu[];
  521. int    uid;
  522. {
  523.   double        temp1, temp2, delta, error_sum;
  524.   struct link   *inlink_ptr, *outlink_ptr;
  525.  
  526.   outlink_ptr = pu[uid]->outlinks;
  527.   error_sum = 0.0;
  528.   while (outlink_ptr) {
  529.     error_sum += pu[outlink_ptr->to_unit]->delta * outlink_ptr->weight;
  530.     outlink_ptr = outlink_ptr->next_outlink;
  531.   }
  532.   delta = pu[uid]->output * (1.0 - pu[uid]->output) * error_sum;
  533.   pu[uid]->delta = delta;
  534. }
  535.  
  536.  
  537. recognize(pu)
  538. struct unit *pu[];
  539. {
  540.   int    i;
  541.   char   tempstr[BUFSIZ];
  542.   static char *p[] = {"Big Ears?", "Big Eyes?", "Big Teeth?",
  543.                       "Kindly?\t", "Wrinkled?", "Handsome?"};
  544.  
  545.   for (i = 0; i < NUM_IN; i++) {
  546.     printf("%s\t(y/n) ", p[i]);
  547.     fflush(stdin); fflush(stdout);
  548.     fgets(tempstr, BUFSIZ, stdin);
  549.     if (tempstr[0] == 'Y' || tempstr[0] == 'y')
  550.       input_pat[PATTERNS][i] = 1.0;
  551.     else
  552.       input_pat[PATTERNS][i] = 0.0;
  553.   }
  554.   init_input_units(pu, PATTERNS);
  555.   propagate(pu);
  556.   print_behaviour(pu);
  557. }
  558.  
  559.  
  560. print_behaviour(pu)
  561. struct unit *pu[];
  562. {
  563.   int   id, count = 0;
  564.   static char *behaviour[] = {
  565.     "Screams", "Runs Away", "Looks for Woodcutter", "Approaches",
  566.     "Kisses on Cheek", "Offers Food", "Flirts with Woodcutter" };
  567.  
  568.   printf("\nLittle Red Riding Hood: \n");
  569.   for (id = OUT_UID(0); id < OUT_UID(NUM_OUT); id++){ /* links to out units */
  570.     if (pu[id]->output > ON_TOLERANCE)
  571.       printf("\t%s\n", behaviour[count]);
  572.     count++;
  573.   }
  574.   printf("\n");
  575. }
  576.  
  577. /*
  578. ! Thomas Muhr    Knowledge-Based Systems Dept. Technical University of Berlin !
  579. ! BITNET/EARN:   muhrth@db0tui11.bitnet                                       !
  580. ! UUCP:          morus@netmbx.UUCP (Please don't use from outside Germany)    !
  581. ! BTX:           030874162  Tel.: (Germany 0049) (Berlin 030) 87 41 62        !
  582. */
  583.  
  584.