home *** CD-ROM | disk | FTP | other *** search
/ Collection of Education / collectionofeducationcarat1997.iso / COMPUSCI / NETSTUFF.ZIP / HAMX.C < prev    next >
C/C++ Source or Header  |  1991-02-27  |  8KB  |  416 lines
  1. /* modified for interactive input patterns - Marilyn Nelson, Feb. 1991 */
  2.  
  3. /* ham.c
  4.  * c version of the hamming net
  5.  * david leasure
  6.  * 9/25/87
  7.  *
  8.  * this routine is a hamming classification network
  9.  * described in IEEE ASSP April 1987 by Richard P. Lippmann pg. 9
  10.  * correcting for a presumed bug in the presented routine
  11.  * the bug is the value set for THETA by Lippmann. When THETA is
  12.  * N / 2 it so overwhelms the outputs from the lower net that only 0
  13.  * activation values are passed up from the threshold function.
  14.  * I have chosen to set epsilon to 1 / 2M and to not have an upper
  15.  * limit on the threshold function so no saturation occurs
  16.  *
  17.  * the program is somewhat inefficient because of the use of
  18.  * data storage for maxnet (t[k,l] in lippman's) and for output[t,M]
  19.  * but they could be useful in a simulator of this network which allowed
  20.  * things to be fiddled with.
  21.  * the code could be improved by not encoding the size and values
  22.  * of the node matrices directly, too, reading them instead from files
  23.  * and/or a user interface.
  24.  *
  25.  * if you improve the code, please send me the diff's
  26.  * david e. leasure
  27.  * ihnp4!homxc!del or del@homxc.att.com
  28.  *
  29.  */
  30.  
  31. /* EMACS_MODES: tabstop=4 c */
  32.  
  33. #include <stdio.h>
  34. #include <ctype.h>
  35.  
  36. /* number of bits per exemplar (7x5) */
  37. #define N 35
  38.  
  39. /*number of exemplars */
  40. #define M 10
  41.  
  42. /* presentation (r,c) */
  43. #define rows 7
  44. #define cols 5
  45.  
  46. /* define maximum number of iterations before convergence */
  47. #define MAX_ITERATION 20
  48.  
  49. /* define the exemplary training data */
  50. /* should be replaced later with a read routine */
  51.  
  52. static int exemplars[M][N] = {
  53. /* 0 */
  54. -1,1,1,1,-1,
  55. 1,-1,-1,-1,1,
  56. 1,-1,-1,-1,1,
  57. 1,-1,-1,-1,1,
  58. 1,-1,-1,-1,1,
  59. 1,-1,-1,-1,1,
  60. -1,1,1,1,-1,
  61. /* 1 */
  62. -1,-1,-1,-1,1,
  63. -1,-1,-1,1,1,
  64. -1,-1,-1,-1,1,
  65. -1,-1,-1,-1,1,
  66. -1,-1,-1,-1,1,
  67. -1,-1,-1,-1,1,
  68. -1,-1,-1,-1,1,
  69. /* 2 */
  70. -1,1,1,1,-1,
  71. 1,-1,-1,-1,1,
  72. -1,-1,-1,-1,1,
  73. -1,-1,-1,1,-1,
  74. -1,-1,1,-1,-1,
  75. -1,1,-1,-1,-1,
  76. 1,1,1,1,1,
  77. /* 3 */
  78. 1,1,1,1,1,
  79. -1,-1,-1,1,-1,
  80. -1,-1,1,-1,-1,
  81. -1,1,1,1,-1,
  82. -1,-1,-1,-1,1,
  83. 1,-1,-1,-1,1,
  84. -1,1,1,1,-1,
  85. /* 4 */
  86. -1,-1,-1,1,-1,
  87. -1,-1,1,1,-1,
  88. -1,1,-1,1,-1,
  89. 1,-1,-1,1,-1,
  90. 1,1,1,1,1,
  91. -1,-1,-1,1,-1,
  92. -1,-1,-1,1,-1,
  93. /* 5 */
  94. 1,1,1,1,1,
  95. 1,-1,-1,-1,-1,
  96. 1,1,1,1,-1,
  97. -1,-1,-1,-1,1,
  98. -1,-1,-1,-1,1,
  99. 1,-1,-1,-1,1,
  100. -1,1,1,1,-1,
  101. /* 6 */
  102. -1,-1,1,1,-1,
  103. -1,1,-1,-1,-1,
  104. 1,-1,-1,-1,-1,
  105. 1,1,1,1,-1,
  106. 1,-1,-1,-1,1,
  107. 1,-1,-1,-1,1,
  108. -1,1,1,1,-1,
  109. /* 7 */
  110. 1,1,1,1,1,
  111. -1,-1,-1,-1,1,
  112. -1,-1,-1,1,-1,
  113. -1,-1,-1,1,-1,
  114. -1,-1,1,-1,-1,
  115. -1,-1,1,-1,-1,
  116. -1,-1,1,-1,-1,
  117. /* 8 */
  118. -1,1,1,1,-1,
  119. 1,-1,-1,-1,1,
  120. 1,-1,-1,-1,1,
  121. -1,1,1,1,-1,
  122. 1,-1,-1,-1,1,
  123. 1,-1,-1,-1,1,
  124. -1,1,1,1,-1,
  125. /* 9 */
  126. -1,1,1,1,-1,
  127. 1,-1,-1,-1,1,
  128. 1,-1,-1,-1,1,
  129. -1,1,1,1,1,
  130. -1,-1,-1,-1,1,
  131. -1,-1,-1,1,-1,
  132. -1,1,1,-1,-1};
  133.  
  134. static float w[N][M];           /* weights of lower subnet */
  135. static float maxnet[M][M];      /* weights of maxnet */
  136. /* input pattern */
  137. static int x[N];
  138.  
  139. /* input vector */
  140. static output[MAX_ITERATION][M]; /* output at time t matrix */
  141.  
  142. #define THETA  0.0 /* N / 2.0 */
  143. #define EPSILON 1.0 / (2.0 * M)
  144.  
  145. /* INIT_LOWER 
  146.  * initialize the weight matrix for the lower network
  147.  */
  148. void init_lower()
  149. {
  150.     int i, j;
  151.  
  152.     for (i=0; i<N; i++) {
  153.         for (j=0; j<M; j++) {
  154.  
  155.         w[i][j] = exemplars[j][i]/2.0;
  156.         }
  157.     }
  158. }
  159.  
  160. /* INIT_UPPER
  161.  * init the weight matrix for the upper maxnet
  162.  */
  163. void init_upper()
  164. {
  165.     int k, l;
  166.  
  167.     for (k=0; k<M; k++) {
  168.         for (l=0; l<M; l++) {
  169.             if (k==l)
  170.                 maxnet[k][l] = 1.0;
  171.             else
  172.                 maxnet[k][l] =  -1.0 / 20.0;
  173.         }
  174.     }
  175. }
  176.  
  177.  
  178. /* INIT_SUM 
  179.  * the code to perform the summation of the weight/input value products
  180.  * for each output, i.e. (sum(i=0..N-1) w[i][j]*x[i]) - THETA
  181. */
  182. float init_sum(j)
  183.     int j;
  184. {
  185.     int i;
  186.     float sum;
  187.  
  188.     sum = 0;
  189.     for (i=0; i<N; i++) {
  190.         sum = sum + (w[i][j] * x[i]);
  191.     }
  192.     return(sum - THETA);
  193. }
  194.  
  195. /* CONVERGE_SUM(J,T)
  196.  * perform the sum for the maxnet output calculation
  197.  * i.e., output[j](t) - epsilon * sum(k<>j where j,k=0..M)output[k](t)
  198.  */
  199. float converge_sum(j,t)
  200.     int j,t;
  201. {
  202.     int k, sum;
  203.  
  204.     sum = 0;
  205.     for (k=0; k<M; k++)
  206.         if (k != j)     sum = sum + output[t][k];
  207.     sum = output[t][j] - EPSILON * sum;
  208.     return(sum);
  209. }
  210.  
  211. /* F_THRESH(ALPHA)
  212.  * implement a simple threshold logic nonlinearity
  213.  * I have chosen not to give it a saturation cutoff
  214.  */
  215. float f_thresh(alpha)
  216.     float alpha;
  217. {
  218.     if (alpha <= 0.0)
  219.         return(0.0);
  220.     else
  221.         return(alpha);
  222. }
  223.  
  224. /* INIT_UNKNOWN()
  225.  * apply the input to the lower net and derive state 0 of the maxnet
  226.  */
  227. void init_unknown()
  228. {
  229.     int j;
  230.  
  231.     for (j=0; j<M; j++) {
  232.         output[0][j] = f_thresh(init_sum(j));
  233.     }
  234. }
  235.  
  236. /* CONVERGE()
  237.  * perform up to MAX_ITERATIONs of the convergence function
  238.  * answer found when only one of the maxnet outputs is high
  239.  * that output indexes the exemplars for the correct pattern
  240.  */
  241. int converge()
  242. {
  243.     int t, count, j, winner;
  244.  
  245.     count = 2; /* prime the pump */
  246.     winner = -1; /* start with "no winner" */
  247.  
  248.     for (t=1; t<MAX_ITERATION && count>1; t++) {
  249.         count = 0;
  250.         for (j=0; j<M; j++) {
  251.             if ((output[t][j] = f_thresh(converge_sum(j,t - 1))) > 0) {
  252.                 winner = j;
  253.                 count++;
  254.             }
  255.         }
  256.     }
  257.     if (count != 1)
  258.         winner = -1; /* error condition not supposed to occur */
  259.     return(winner);
  260. }
  261.  
  262. /* SHOW_EXEMPLAR(EX)
  263.  * print the exemplar(ex) using .'s for -1 and *'s for +1
  264.  * break the lines so the pattern is correctly seen
  265.  */
  266. void show_exemplar(ex)
  267.     int ex[];
  268. {
  269.     int c, i;
  270.  
  271.     c = 0;
  272.     for (i=0; i<N; i++) {
  273.         if (ex[i] < 0) {
  274.             printf(".");
  275.         }
  276.         else {
  277.             printf("*");
  278.         }
  279.         if (++c == cols) {
  280.             printf("\n");
  281.             c = 0;
  282.         }
  283.     }
  284.     printf("\n");
  285. }
  286.  
  287. /*  SHOW_EXEMPLARS()
  288.  *  show all the exemplars
  289.  */
  290. void show_exemplars()
  291. {
  292.     int j;
  293.     char p; /* throw away char--for screen control only */
  294.  
  295.     for (j=0; j<M; j++) {
  296.         printf("Exemplar %d:\n",j);
  297.         show_exemplar(&exemplars[j][0]);
  298.         if (((j+1)%2)==0 && j != 9)
  299.         {
  300.            printf("\n\n\nPress ENTER for next exemplar...");
  301.            scanf("%c", &p);
  302.            printf("\n\n\n\n");
  303.         }
  304.     }
  305.     printf("\n");
  306. }
  307.  
  308. void get_sample() /* routine added to enter patterns interactively */
  309. {
  310.     int i,j;
  311.     char temp[6];
  312.  
  313.     printf("\nPlease enter 5x7 sample for hamming net...\n");
  314.     printf("   enter \"*\" to turn bit on; \".\" to turn bit off...\n");
  315.     printf("   For example, enter the string \".***.\" \n\n");
  316.  
  317.     for (i=0;i<rows;i++)
  318.     {
  319.        printf("\nEnter pattern for row %d: ",i+1);
  320.        scanf("%5s", temp);
  321.        temp[5]='\0';
  322.        for (j=0;j<cols;j++)
  323.        {
  324.          if (temp[j]=='*') x[5*i+j]=1;
  325.          else x[5*i+j]=-1; /* default sets bit to -1 */
  326.        }
  327.     }
  328. }
  329.  
  330. void save_sample() /* routine added to save created examples */
  331. {
  332.     int i,stat;
  333.     FILE *fp, *fopen();
  334.     char save[20];
  335.  
  336.     printf("\nWould you like to save your example? (Y/N): ");
  337.     scanf("%1s", save );
  338.     if (save[0]=='Y' || save[0]=='y')
  339.     {
  340.        printf("\nEnter filename for saving: ");
  341.        scanf("%s", save);
  342.        if (fp = fopen(save, "w"))
  343.        {
  344.           for (i=0; i<rows*cols; i++)
  345.           {
  346.          stat = fprintf(fp, "%d%c", x[i], ' ');
  347.          if (stat < 1)
  348.          {
  349.             printf("\nBad write, exit without saving\n");
  350.             exit(0);
  351.          }
  352.           }
  353.           fclose(fp);
  354.        }
  355.        else printf("\nCould not open file %s\n", save);
  356.     }
  357. }
  358.  
  359.  
  360. void read_file(char *filename)
  361. {
  362.     int i,stat;
  363.     FILE *fp;
  364.  
  365.     fp = fopen(filename, "r");
  366.     if (!fp)
  367.     {
  368.        printf("\nFailed to open file %s\n", filename);
  369.        exit(0);
  370.     }
  371.     else
  372.     {
  373.        for (i=0; i<rows*cols; i++)
  374.        {
  375.            stat = fscanf(fp,"%d", &x[i]);
  376.            if (stat != 1) printf("\nBad read for element %d\n",i);
  377.        }
  378.        fclose (fp);
  379.     }
  380. }
  381.  
  382.  
  383. main(int argc, char *argv[])
  384. {
  385.     int winner;
  386.  
  387.     printf("Hamming Neural Net Example\n\n");
  388.  
  389.     if (argc > 1) /* filename passed in */
  390.       read_file(*++argv);
  391.     else  /* no filename passed in */
  392.        {
  393.           show_exemplars();
  394.           get_sample();
  395.        }
  396.  
  397.     init_lower();    
  398.     init_upper();   
  399.     init_unknown();
  400.     winner = converge();
  401.     if (winner >= 0) {
  402.         printf("The winner is %d.\n", winner);
  403.         printf("\nInput pattern:\n");
  404.         show_exemplar(&x[0]);
  405.         printf("\n\nExemplar:\n");
  406.         show_exempla