home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1989 / 01 / nnpatm.asc < prev    next >
Text File  |  1989-01-02  |  13KB  |  587 lines
  1. _USING NEURAL NETWORKS FOR PATTERN RECOGNITION_
  2.  
  3. by Todd King
  4.  
  5.  
  6. [LISTING ONE] 
  7.  
  8. #include <stdio.h>
  9. #define EXTERN extern
  10. #include "neural.h"
  11.  
  12. /*-- MAKE_MIND ---------------------------------------
  13.   Constructs a mental unit with the given number
  14.   of input, hidden and output neurons.
  15. ------------------------------------------------------*/
  16. make_mind(in, hid, out)
  17. int in;
  18. int hid;
  19. int out;
  20. {
  21.   if ( in > MAX_NEURONS  ||
  22.        hid > MAX_NEURONS ||
  23.        out > MAX_NEURONS ) return(0);
  24.   if (in < 1 || hid < 1 || out < 1 ) return(0);
  25.   Mind.n_input = in;
  26.   Mind.n_hidden = hid;
  27.   Mind.n_output = out;
  28.   set_cluster_fun(NULL, NULL);
  29.   set_all_weights(1.0);
  30.   set_act_fun(pass);
  31.   set_user_in_fun(prompted);
  32.   set_result_fun(print_binary_state);
  33.   strcpy(Prompt.string, "Input a value for neuron %d: ");
  34.   Prompt.count = 1;
  35.   return(1);
  36. }
  37.  
  38. /*-- ACTIVATE_MIND -----------------------------------------
  39.   Sets a mind in motion. Sequentially activating each neuron
  40. -----------------------------------------------------------*/
  41. activate_mind()
  42. {
  43.   int i;
  44.   float net_input;
  45.  
  46. /* Activate input layer */
  47.   Prompt.count = 1;
  48.   for (i = 0; i < Mind.n_input; i++)
  49.   {
  50.      Mind.i_layer[i].value = Mind.user_in_fun();
  51.   }
  52.  
  53. /* Activate hidden layer */
  54.   for (i= 0; i < Mind.n_hidden; i++)
  55.   {
  56.      net_input = weighted_sum(i, HIDDEN);
  57.      Mind.h_layer[i].value = Mind.act_fun(net_input);
  58.   }
  59.  
  60. /* Activate feedback/certainty function (if one is set) */
  61.   if ( Mind.certainty != NULL) Mind.cluster_fun(Mind.certainty);
  62.  
  63. /* Activate output layer */
  64.   for (i=0; i < Mind.n_output; i++)
  65.   {
  66.      net_input = weighted_sum(i, OUTPUT);
  67.      Mind.o_layer[i].value = Mind.act_fun(net_input);
  68.      Mind.result_fun(Mind.o_layer[i].value);
  69.   }
  70. }
  71.  
  72. /*-- SET_ALL_WEIGHTS --------------------------------------
  73.   Sets the weight of all connections between all neurons
  74.   in all layers to the given value
  75. ----------------------------------------------------------*/
  76. set_all_weights(value)
  77. float value;
  78. {
  79.   int i, j;
  80.  
  81. /* Weights between input and hidden */
  82.  
  83.   for(i = 0; i < Mind.n_input; i++)
  84.   {
  85.     for(j = 0; j < Mind.n_hidden; j++)
  86.     {
  87.       Input_to_hidden[i][j].weight = value;
  88.     }
  89.   }
  90.  
  91. /* Weights between hidden and output */
  92.  
  93.   for(i=0; i< Mind.n_hidden; i++)
  94.   {
  95.     for(j = 0; j < Mind.n_output; j++)
  96.     {
  97.       Hidden_to_output[i][j].weight = value;
  98.     }
  99.   }
  100. }
  101.  
  102. /*-- SET_WEIGHT -------------------------------------
  103.   Sets the weight between two neurons to a given value.
  104. ------------------------------------------------------*/
  105. set_weight(from, to, layer, value)
  106. int from;
  107. int to;
  108. int layer;
  109. float value;
  110. {
  111.    switch (layer)
  112.    {
  113.      case HIDDEN:
  114.        if (from > Mind.n_input) return;
  115.        if (to > Mind.n_hidden) return;
  116.        Input_to_hidden[from][to].weight = value;
  117.        break;
  118.      case OUTPUT:
  119.        if (from > Mind.n_hidden) return;
  120.        if (to > Mind.n_output) return;
  121.        Hidden_to_output[from][to].weight = value;
  122.        break;
  123.      default:
  124.        break;
  125.    }
  126.    return;
  127. }
  128.  
  129. /*-- WEIGHT_SUM --------------------------------------------
  130.   Calculates the weighted sum for a given neuron in a given
  131.   layer
  132. ----------------------------------------------------------*/
  133. float weighted_sum(this_neuron, this_layer)
  134. int this_neuron;
  135. int this_layer;
  136. {
  137.   int i;
  138.   float sum = 0.0;
  139.  
  140.   switch (this_layer)
  141.   {
  142.     case HIDDEN:
  143.       for (i = 0; i < Mind.n_input; i++)
  144.       {
  145.          sum += (Mind.i_layer[i].value * Input_to_hidden[i][this_neuron].weight);
  146.       }
  147.       break;
  148.     case OUTPUT:
  149.       for (i = 0; i < Mind.n_hidden; i++)
  150.       {
  151.         sum += (Mind.h_layer[i].value * Hidden_to_output[i][this_neuron].weight);
  152.       }
  153.       break;
  154.     default:
  155.       break;
  156.   }
  157.  
  158.   return (sum);
  159. }
  160.  
  161. /*-- PASS ----------------------------------------------
  162.   Returns the input value. A dummy activation function.
  163. --------------------------------------------------------*/
  164. float pass(value)
  165. float value;
  166. {
  167.   return (value);
  168. }
  169.  
  170. /*-- PROMPTED ---------------------------------------
  171.   Prompts the user for an input value and returns the
  172.   value. A user input function.
  173. -----------------------------------------------------*/
  174. float prompted()
  175. {
  176.   float value;
  177.  
  178.   printf(Prompt.string, Prompt.count++);
  179.   scanf("%f", &value);
  180.   return(value);
  181. }
  182.  
  183. /*-- PRINT_BINARY_STATE -------------------------------
  184.    Prints the output state of a neuron. If greater than
  185.    0.0 the value printed is "on", otherwise "off".
  186. ------------------------------------------------------*/
  187. float print_binary_state(value)
  188. float value;
  189. {
  190.   printf("The output gate is: ");
  191.  
  192.   if (value > 0.0) printf("ON.");
  193.   else printf("OFF.");
  194.  
  195.   printf("\n");
  196. }
  197.  
  198.  
  199.  
  200. [LISTING TWO] 
  201.  
  202. /* Linear network */
  203.  
  204. #define EXTERN
  205. #include "neural.h"
  206.  
  207. #define MEMBERS 5
  208.  
  209. float print_vote_state();
  210. #define plural(x)   (x == 1 ? "" : "s")
  211.  
  212. main()
  213. {
  214.   int i;
  215.  
  216.   make_mind(5,1,1);
  217.   set_result_fun(print_vote_state);
  218.   strcpy(Prompt.string, "Ballot for member %d: ");
  219.   for(i=0; i<MEMBERS; i++)
  220.   {
  221.     set_weight(i, 0, HIDDEN, (float)(i+1) );
  222.   }
  223.   printf("Ballot values: 1 = for, 0 = obstain, -1 = against\n\n");
  224.   activate_mind();
  225. }
  226.  
  227. float print_vote_state(value)
  228. float value;
  229. {
  230.   int votes;
  231.   printf("The vote is: ");
  232.  
  233.   votes = (int)value;
  234.   if (votes > 0)
  235.     printf("FOR, by %d vote%s", votes, plural(votes) );
  236.   else if (votes < 0)
  237.     printf("AGAINST, by %d vote%s", -votes, plural(-votes) );
  238.   else
  239.     printf("A TIE");
  240.  
  241.   printf(".\n");
  242. }
  243.  
  244.  
  245. [LISTING THREE] 
  246.  
  247. /* Simple linear threshold network.
  248.    Demonstates logic gates */
  249.  
  250. #define EXTERN
  251. #include "neural.h"
  252.  
  253. float linear_threshold();
  254.  
  255. main()
  256. {
  257.   int i;
  258.  
  259. /* OR gates work using the default weights (1.0) */
  260.  
  261.   strcpy(Prompt.string, "Logic state of gate %d: ");
  262.   printf("Logic values: 1, on; 0, off\n\n");
  263.  
  264.   printf("OR logic gate.\n");
  265.   printf("--------------\n\n");
  266.   make_mind(2, 1, 1);
  267.   activate_mind();
  268.  
  269. /* AND gates must have weights < 1.0 ( and > 0.0) */
  270.  
  271.   printf("\n");
  272.   printf("AND logic gate.\n");
  273.   printf("--------------\n\n");
  274.  
  275.   for(i = 0; i < 2; i++)
  276.   {
  277.     set_weight(i, 0, HIDDEN, 0.5);
  278.   }
  279.   activate_mind();
  280.  
  281. /* XOR gates are the most complicated */
  282.  
  283.   printf("\n");
  284.   printf("XOR logic gate.\n");
  285.   printf("--------------\n\n");
  286.   make_mind(2, 2, 1);
  287.   set_weight(0, 0, HIDDEN, 1.0);
  288.   set_weight(1, 0, HIDDEN, -1.0);
  289.   set_weight(0, 1, HIDDEN, -1.0);
  290.   set_weight(1, 1, HIDDEN, 1.0);
  291.   set_weight(0, 0, OUTPUT, 1.0);
  292.   set_weight(1, 0, OUTPUT, 1.0);
  293.   set_act_fun(linear_threshold);
  294.   activate_mind();
  295. }
  296.  
  297. /*-- LINEAR_THRESHOLD -------------------------------------
  298.   If the input value is greater than zero then it returns
  299.   1.0, otherwise it returns 0.0. A linear threshold
  300.   activation function.
  301. ----------------------------------------------------------*/
  302. float linear_threshold(value)
  303. float value;
  304. {
  305.   if (value > 0.0) return(1.0);
  306.   else return(0.0);
  307. }
  308.  
  309.  
  310.  
  311.  
  312. [LISTING FOUR] 
  313.  
  314. /*
  315.    Optical Character Recognition (OCR) neural network
  316.    This is a hybrid between a linear threshold, fully
  317.    interconnected network and a linear network. The
  318.    transition being at the hidden layer. A Feedback neuron
  319.    gaurantees a pattern match in the threshold layer.
  320. */
  321. #include <stdio.h>
  322. #define EXTERN
  323. #include "neural.h"
  324.  
  325. float percep();
  326. float print_ocr();
  327. float certainty_cluster();
  328.  
  329. float Certainty;
  330. FILE *Ocr_fptr;
  331.  
  332. main(argc, argv)
  333. int argc;
  334. char *argv[];
  335. {
  336.   int i;
  337.  
  338.   if(argc < 2)
  339.   {
  340.     printf("proper usage: ocr [<train_file> ...] [-test <test_file> ...]\n");
  341.     exit(-1);
  342.   }
  343.  
  344.   make_mind(35, 3, 1);
  345.   set_user_in_fun(percep);
  346.   set_result_fun(print_ocr);
  347.   set_cluster_fun(certainty_cluster, &Certainty);
  348.   set_all_weights(0.0);
  349.  
  350. /* Teach the network about the patterns */
  351.   i = 1;
  352.   while(strcmp(argv[i], "-test") != 0)
  353.   {
  354.      printf("Learning: %s\n", argv[i]);
  355.      if( i > Mind.n_hidden)
  356.      {
  357.        printf("Too many pattern groups for the given topology, aborting.\n");
  358.        exit(-1);
  359.      }
  360.      ocr_learn(argv[i], i - 1);
  361.      i++;
  362.       if(i >= argc)
  363.      {
  364.        printf("Nothing to test - exiting\n");
  365.        exit(-1);
  366.      }
  367.   }
  368.  
  369. /* Classify each pattern based on what the network knows */
  370.   i++;      /* Skip over "-test" deliniator */
  371.   while(i < argc)
  372.   {
  373.     printf("Testing %s\n", argv[i]);
  374.     if ((Ocr_fptr = fopen(argv[i], "r")) == NULL)
  375.     {
  376.       perror(argv[i]);
  377.       printf("Unable to open file, skipping pattern.\n");
  378.       i++;
  379.       continue;
  380.     }
  381.     activate_mind();
  382.     fclose(Ocr_fptr);
  383.     i++;
  384.   }
  385. }
  386.  
  387. /*-- PERCEP ------------------------------------------------
  388.   Returns the value of the next pixel every time its called.
  389.   The pixel state is determined from the contents of the
  390.   pre-opened file pointed to by 'Ocr_fptr'.
  391. ----------------------------------------------------------*/
  392. float percep()
  393. {
  394.   extern FILE *Ocr_fptr;
  395.   int pixel_value;
  396.  
  397.   fscanf(Ocr_fptr, "%1d", &pixel_value);
  398.   return( (float)pixel_value);
  399. }
  400.  
  401. /*-- PRINT_OCR -------------------------------------
  402.   Prints the character which the network determines
  403.   it to be. Also prints the certainty of the match.
  404. ------------------------------------------------------*/
  405. float print_ocr(value)
  406. float value;
  407. {
  408.   extern float Certainty;
  409.  
  410.   printf("The character is '%c' (%d).\n", (int)value, (int)value);
  411.   printf("with a certainty of %3.2f%.\n", Certainty);
  412. }
  413.  
  414. /*-- OCR_LEARN -----------------------------
  415.   Teach the network how to classify
  416.   a pattern.
  417. --------------------------------------------*/
  418. ocr_learn(filename, group_id)
  419. char filename[];
  420. int group_id;
  421. {
  422.   int i;
  423.   FILE *fptr;
  424.   int pixel_cnt = 0;
  425.   int pixel_value;
  426.   float dist_weight;
  427.   float output_value;
  428.  
  429.   if ((fptr = fopen(filename, "r")) == NULL)
  430.   {
  431.     perror(filename);
  432.     printf("Skipping pattern.\n");
  433.     return(0);
  434.   }
  435.  
  436. /* Determine the number of "on" pixels, hence fractional weight */
  437.   for(i=0; i < Mind.n_input; i++)
  438.   {
  439.     fscanf(fptr, "%1d", &pixel_value);
  440.     if(pixel_value == 1) pixel_cnt++;
  441.   }
  442.   dist_weight = 1.0/pixel_cnt;
  443.   rewind(fptr);
  444.  
  445.  /* Set fractional weight for each "on" connection */
  446.   for(i=0; i < Mind.n_input; i++)
  447.   {
  448.     fscanf(fptr, "%1d", &pixel_value);
  449.     if(pixel_value == 1) set_weight(i, group_id, HIDDEN, dist_weight);
  450.   }
  451.  
  452.  /* Now set weight for output value for this character */
  453.   fscanf(fptr, "%f", &output_value);
  454.   set_weight(group_id, 0, OUTPUT, output_value);
  455.  
  456.   fclose(fptr);
  457.   return(1);
  458. }
  459.  
  460. /*-- CERTAINTY_CLUSTER ------------------------------------
  461.    Performs a cluster function. It inhibits (sets to 0) all
  462.    neurons in the cluster except the one which is closest to
  463.    the value 1.0. This neuron is set to 1.0. The passed
  464.    variable is assigned the certainty to which the closest
  465.    neuron felt it matched the pattern
  466. ----------------------------------------------------------*/
  467. float certainty_cluster(certainty)
  468. float *certainty;
  469. {
  470.   int i;
  471.   float highest = 0.0;
  472.   int closest = -1;
  473.  
  474.   for(i=0; i<Mind.n_hidden; i++)
  475.   {
  476.     if(Mind.h_layer[i].value > highest)
  477.     {
  478.       closest = i;
  479.       highest = Mind.h_layer[i].value;
  480.     }
  481.   }
  482.   if(closest == -1) /* All are equally likely - choose the first */
  483.   {
  484.     closest = 0;
  485.   }
  486.  
  487.   *certainty = Mind.h_layer[closest].value * 100.0;
  488.  
  489. /*
  490.    Cause just enough feedback to the neuron which is closest
  491.    to being "on" so that it is "on". That is set it "on"
  492.    All others are given negative feedback to force them to
  493.    zero. (set them to zero).
  494. */
  495.   for( i = 0; i < Mind.n_hidden; i++)
  496.   {
  497.     if (i == closest) Mind.h_layer[i].value = 1.0;
  498.     else Mind.h_layer[i].value = 0.0;
  499.   }
  500. }
  501.  
  502.  
  503.  
  504.  
  505. [LISTING FIVE] 
  506.  
  507. #ifndef _NEURAL_
  508. #define _NERUAL_
  509.  
  510. #define MAX_NEURONS 35
  511.  
  512. #define HIDDEN  1
  513. #define OUTPUT  2
  514.  
  515. /* Type definition for neurons and neural networks */
  516.  
  517. typedef struct {
  518.   float value;
  519. } NEURON;
  520.  
  521. typedef struct {
  522.   int n_input;
  523.   int n_hidden;
  524.   int n_output;
  525.   float *certainty;
  526.   float (*cluster_fun)();
  527.   float (*act_fun)();
  528.   float (*user_in_fun)();
  529.   float (*result_fun)();
  530.   NEURON i_layer[MAX_NEURONS];
  531.   NEURON h_layer[MAX_NEURONS];
  532.   NEURON o_layer[MAX_NEURONS];
  533. } MIND;
  534.  
  535. typedef struct {
  536.   float weight;
  537. } WEIGHTS;
  538.  
  539. typedef struct
  540. {
  541.   char string[80];
  542.   int count;
  543. } PROMPT;
  544.  
  545. /* Global Variables */
  546.  
  547. EXTERN MIND Mind;
  548. EXTERN WEIGHTS Input_to_hidden[MAX_NEURONS][MAX_NEURONS];
  549. EXTERN WEIGHTS Hidden_to_output[MAX_NEURONS][MAX_NEURONS];
  550. EXTERN PROMPT Prompt;
  551.  
  552. /* Functions */
  553.  
  554. float weighted_sum();
  555. float pass();
  556. float prompted();
  557. float print_binary_state();
  558. float certainty_fun();
  559. int activate_mind();
  560.  
  561. /* Pseudo-functions */
  562.  
  563. #define set_act_fun(f)  Mind.act_fun = f
  564. #define set_user_in_fun(f)  Mind.user_in_fun = f
  565. #define set_back_prop_fun(f)    Mind.back_prop_fun = f
  566. #define set_result_fun(f)   Mind.result_fun = f
  567. #define set_cluster_fun(f, x)   Mind.cluster_fun = f; Mind.certainty = x
  568.  
  569. #endif
  570.  
  571.  
  572.  
  573. [LISTING SIX] 
  574.  
  575. Board:
  576.         board.c (neural.h)
  577.         neurlib.c (neural.h)
  578.  
  579. Logic:
  580.         logic.c (neural.h)
  581.         neurlib.c (neural.h)
  582.  
  583. OCR:
  584.         ocr.c (neural.h)
  585.         neurlib.c (neural.h)
  586.  
  587.