Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/compsrcs/misc/volume07/art1

Internet Message Format | 1991-08-27 | 10.4 KB

From decwrl!ucbvax!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!allbery Sun Jun  4 14:44:40 PDT 1989
Article 902 of comp.sources.misc:
Path: decwrl!ucbvax!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!allbery
From: [e-mail] (Brandon S. Allbery - comp.sources.misc)
Newsgroups: comp.sources.misc
Subject: v07i013: ART1 Simulator
Message-ID: <[e-mail]>
Date: 4 Jun 89 01:49:00 GMT
Sender: [e-mail]
Reply-To: [e-mail] (Jagath SamaraBandu)
Organization: SUNY/Buffalo Computer Science
Lines: 410
Approved: [e-mail] (Brandon S. Allbery - comp.sources.misc)

Posting-number: Volume 7, Issue 13
Submitted-by: [e-mail]
Archive-name: art1

[Why does stuff from cs.buffalo.edu come from "[e-mail]"?  ++bsa]

This is a short program which simulates ART1 neural network, proposed by
Grossberg and Carpenter. The algorithm is taken directly from an article in
87 IEEE ASSP magazine by Lippman. (which btw is an excellent article).

Please send me any bug reports/fixes. I'm not that keen on improving this,
but if there are any suggestions, I'll try to include them.

Jagath
PS:Any comments, brickbats and flowers are welcome. (Even if it is about the
programming style)

-------------------cut-------here----------------------------------------------
# This is a shell archive.  Remove anything before this line, then
# unpack it by saving it in a file and typing "sh file".  (Files
# unpacked will be owned by you and have default permissions.)
#
# This archive contains:
# art1.c art1.data art1.tex

echo x - art1.c
sed -e 's/^X//' > "art1.c" << '//E*O*F art1.c//'
X/* Simiulation of ART-1 Neural network (Ref: Lippman 87)
X   Written by Jagath Samarabandu <[e-mail]>
X   To compile, type cc art1.c -o art1  */
X
X#include <stdio.h>
X
X#define N      25   /* No. of nodes in F1 */
X#define M      10   /* No. of nodes in F2 */
X
Xinitialize(top_down,bot_up,n,m) /* initialize the LTM traces */
X     double top_down[],bot_up[]; /* top down and bot. up LTM traces */
X     int n,m;                   /* No. of nodes in F1 and F2 */
X{
X  int i;
X  double t;
X
X  t = 1.0/(1.0+n);
X  for (i=0;i<n*m;i++) {
X    top_down[i] = 1.0; bot_up[i] = t;
X  }
X}
X
Xcompute_matching_scores(mu,bot_up,input,n,m) /* calculate matching scores */
X     double mu[],bot_up[],input[];            /* mu - matching score */
X     int n,m;                                /* No. of F1 and F2 nodes */
X{
X  int i,j;
X
X  for (j=0; j<m; j++)
X    for (i=0, mu[j]=0.0; i<n; i++)
X      mu[j] += bot_up[i*m+j]*input[i];
X}
X
Xdouble vigilance(top_down,input,jmax,n,m) /* returns |T.X|/|X| */
X     double top_down[],input[];
X     int n,m,jmax;
X{
X  int i;
X  double x,t;
X
X  for (i=0,x=0.0; i<n; i++)
X    x += input[i];
X  for (i=0,t=0.0; i<n; i++)
X    t += top_down[i*m+jmax]*input[i];
X  return(t/x);
X}
X
Xint find_max(array,len) /* find the max of array and return the index */
X     double array[];
X     int len;
X{
X  int j,jmax;
X
X  for (j=0,jmax=0; j<len; j++)
X    if (array[j]>array[jmax])
X      jmax = j;
X  return (jmax);
X}
X
Xadapt_LTM(top_down,bot_up, input,jmax,n,m) /* change top down and bot.up LTM */
X     double top_down[],bot_up[],input[];
X     int n,m,jmax;
X{
X  int i,ij;
X  double sum,t;
X
X  for (i=0,sum=0.5; i<n; i++)
X    sum += top_down[i*m+jmax]*input[i];
X
X  for (i=0,ij=jmax; i<n; i++,ij += m) {
X    t = top_down[ij]*input[i];
X    bot_up[ij] = t/sum;
X    top_down[ij] = t;
X  }
X}
X
Xload_data(d,max,n,fname) /* load data from file */
X     int d[],max,n;
X     char *fname[];
X{
X  FILE *fp;
X  int n_pat,n_var,i,j;
X
X  if (!(fp=fopen(fname,"r"))) exit(perror(fname));
X  fscanf(fp,"%d %d\n",&n_pat,&n_var);
X  if (n_pat>max) {
X    printf("Warning! only %2d patterns out of %d are read\n",max,n_pat);
X    n_pat = max;
X  }
X  if (n_var!=n)
X    exit(printf("wrong pattern size: should be %2d. was %2d\n",n,n_var));
X
X  for (i=0;j<n_pat;i++)
X    for (j=0;j<n_var;j++)
X      fscanf(fp,"%d",&d[i*n+j]);
X  fclose(fp);
X}
X
Xdisplay(in,top_down,x,y,m) /* display input and top down weights */
X     double in[],top_down[];
X     int x,y,m;
X{
X  int i,ix,iy,j;
X
X  for (iy=0,i=0; iy<y; iy++){
X    for (ix=0,i=iy*y; ix<x; ix++,i++)
X      printf("%c",(in[i]>0.5)?'#':' ');
X    printf(" | ");
X    for (j=0; j<m; j++) {
X      for (ix=0,i=iy*y; ix<x; ix++,i++)
X    printf("%c",(top_down[i*m+j]>0.5)?'#':' ');
X      printf(" ");
X    }
X    printf("\n");
X  }
X  printf("\n");
X}
X/*****************  main routine starts here  *******************************/
X
Xint data[20][N]={
X#include "art1.data"
X};
X
Xmain(argc,argv)
X     int argc;
X     char *argv[];
X{
X  double t[N][M],b[N][M],x[N],mu[M],rho;
X  int max_j,i,j,n_pat,ok,seq[M];
X
X  if (argc>1)
X    n_pat = load_data(data,20,N,argv[1]);
X  else n_pat=20;
X  initialize(t,b,N,M);
X  printf("Vigilance threshold: "); scanf("%lf",&rho);
X  printf("\nSimulation of ART1 network with vigilance Threshold = %3.1lf\n\n",rho);
X
X  do {
X    for (i=0; i<n_pat; i++) {
X      for (j=0; j<N; j++)
X    x[j] = (double)data[i][j];
X      compute_matching_scores(mu,b,x,N,M);
X      bzero((char *)seq,M*sizeof(int)); j=1;
X      do {
X    max_j = find_max(mu,M); seq[max_j] = j++;
X    if (vigilance(t,x,max_j,N,M)>rho) {
X      adapt_LTM(t,b,x,max_j,N,M);
X      seq[max_j] = -1;
X      break;
X    }
X    else
X      mu[max_j] = 0.0;
X      } while (1);
X      printf("IN:%2d    ",i);
X      for (j=0;j<M; j++) {
X    if (seq[j]>0)
X      printf("%1d     ",seq[j]);
X    else if (seq[j]==0)
X      printf("      ");
X    else {
X      printf("R\n"); break;
X    }
X      }
X      display(x,t,5,5,M);
X    }
X    printf("Another round? (1-yes): "); scanf("%d",&ok);
X  } while (ok);
X}
//E*O*F art1.c//

echo x - art1.data
sed -e 's/^X//' > "art1.data" << '//E*O*F art1.data//'
X/* art1 data file - 20x25 */
X
X{1,1,1,1,1,
X 1,0,0,0,1,
X 1,1,1,1,1,
X 1,0,0,0,1,
X 1,0,0,0,1,},
X
X{1,1,1,1,0,
X 1,0,0,0,1,
X 1,1,1,1,0,
X 1,0,0,0,1,
X 1,1,1,1,0,},
X
X{1,1,1,1,1,
X 1,0,0,0,0,
X 1,0,0,0,0,
X 1,0,0,0,0,
X 1,1,1,1,1,},
X
X{1,1,1,1,0,
X 1,0,0,0,1,
X 1,0,0,0,1,
X 1,0,0,0,1,
X 1,1,1,1,0,},
X
X{1,1,1,1,1,
X 1,0,0,0,0,
X 1,1,1,1,1,
X 1,0,0,0,0,
X 1,1,1,1,1,},
X
X{1,1,1,1,1,
X 1,0,0,0,0,
X 1,1,1,1,1,
X 1,0,0,0,0,
X 1,0,0,0,0,},
X
X{1,1,1,1,1,
X 1,0,0,0,0,
X 1,0,1,1,1,
X 1,0,0,0,1,
X 1,1,1,1,1,},
X
X{1,0,0,0,1,
X 1,0,0,0,1,
X 1,1,1,1,1,
X 1,0,0,0,1,
X 1,0,0,0,1,},
X
X{1,1,1,1,1,
X 0,0,1,0,0,
X 0,0,1,0,0,
X 0,0,1,0,0,
X 1,1,1,1,1,},
X
X{1,1,1,1,1,
X 0,0,1,0,0,
X 0,0,1,0,0,
X 0,0,1,0,0,
X 1,1,1,0,0,},
X
X{1,0,0,0,1,
X 1,0,0,1,0,
X 1,1,1,0,0,
X 1,0,0,1,0,
X 1,0,0,0,1,},
X
X{1,0,0,0,0,
X 1,0,0,0,0,
X 1,0,0,0,0,
X 1,0,0,0,0,
X 1,1,1,1,1,},
X
X{1,0,0,0,1,
X 1,1,0,1,1,
X 1,0,1,0,1,
X 1,0,0,0,1,
X 1,0,0,0,1,},
X
X{1,0,0,0,1,
X 1,1,0,0,1,
X 1,0,1,0,1,
X 1,0,0,1,1,
X 1,0,0,0,1,},
X
X{1,1,1,1,1,
X 1,0,0,0,1,
X 1,0,0,0,1,
X 1,0,0,0,1,
X 1,1,1,1,1,},
X
X{1,1,1,1,1,
X 1,0,0,0,1,
X 1,1,1,1,1,
X 1,0,0,0,0,
X 1,0,0,0,0,},
X
X{1,1,1,1,1,
X 1,0,0,0,1,
X 1,0,1,0,1,
X 1,0,0,1,1,
X 1,1,1,1,1,},
X
X{1,1,1,1,1,
X 1,0,0,0,1,
X 1,1,1,1,1,
X 1,0,0,1,0,
X 1,0,0,0,1,},
X
X{1,1,1,1,1,
X 1,0,0,0,0,
X 1,1,1,1,1,
X 0,0,0,0,1,
X 1,1,1,1,1,},
X
X{1,1,1,1,1,
X 0,0,1,0,0,
X 0,0,1,0,0,
X 0,0,1,0,0,
X 0,0,1,0,0,},
//E*O*F art1.data//

echo x - art1.tex
sed -e 's/^X//' > "art1.tex" << '//E*O*F art1.tex//'
X\font\ninerm=cmr9 \font\rm=cmr8 \font\serif=amss10
X\magnification=1200
X\parskip 10pt plus 1pt
X\parindent 0pt
X\nopagenumbers
X\null\vskip-46pt
X\hbox to 6.5truein {\bf March 1989 \hfil Project Documentation and source code
X - ECE 551}
X\vfill
X\centerline{\bf PROJECT: Simulation of ART1 Neural Network}
X\vskip .25in
X\centerline{by}
X\centerline{Jagath K. Samarabandu <[e-mail]>}
X\vfill
X\line {\bf Dept. of Electrical and Computer Engineering \hfil SUNY at Buffalo}
X\eject
X{\ninerm\bf \underbar{System Description}}\vskip 0.25in
XThe program simulates a neural network using the Adaptive Resonance Theory
Xproposed by Carpenter and Grossberg. [Carpenter 86]. The network forms clusters
Xand is trained without supervision.
X
XFollowing algorithm is used in the program [Lippman 87].
X
X{\bf Step 1. Initialization}\hfil\break
X
X$$\eqalign{t_{ij}(0) &= 1 \cr
Xb_{ij}(0) &= {1 \over 1 + N }}$$
X$$0 \le i \le N-1$$
X$$0 \le j \le M-1$$\rm
Xset $\rho$,\qquad$ 0 \le \rho \le 1$\hfil\break
X
Xwhere \hfil\break $b_{ij}(t)$ - bottom up LTM traces\hfil\break
X$t_{ij}(t)$ - top down LTM traces\hfil\break
Xbetween input node $i$ and output node $j$. The fraction $\rho$ is the vigilance threshold\hfil\break
X
X{\bf Step 2. Apply New Input \hfil\break
XStep 3. Compute Matching Scores }\hfil\break
X$$ \mu_j = \sum_{i=0}^{N-1} b_{ij}(t)X_i, \qquad 0 \le j \le M-1 $$
Xwhere $\mu_j$ is the output of output node $j$ and $X_i$ is the input element
X$i$.\hfil\break
X{\bf Step 4. Select best matching Exemplar}\hfil\break
X$$\mu_j^* = \displaystyle \max_j\left\{{\mu_j}\right\}$$
X
X{\bf Step 5. Vigilance test}\hfil\break
X$$\Vert X \Vert = \sum_{i=0}^{N-1} X_i$$
X$$\Vert T \cdot X\Vert = \sum_{i=0}^{N-1} t_{ij}\cdot X_i$$
XIF ${{\Vert T\cdot X\Vert}\over\Vert X\Vert}>\rho$ THEN GOTO STEP 6\hfil\break
X
X{\bf Step 6. Disable best matching Exemplar}\hfil\break
XThe output of the bes matching node is selected in {\bf step 4} is temporarily
Xset to zero and no longer takes part in the maximization of {\bf step 4}. Then
Xgo to {\bf Step 3}\hfil\break
X
X{\bf Step 7. Adapt Best Matching Exemplar}\hfil\break
X$$t_{ij^*}(t+1) = t_{ij^*}(t)X_i$$
X$$b_{ij^*}(t+1) = {{t_{ij^*}(i)X_i}\over 0.5+\sum_{i=0}^{N-1}t_{ij^*}(t)X_i}$$
X
X{\bf Step 8. repeat by Going to Step 2}\hfil\break
X(First enable any nodes disabled in step 6)
X\vskip 0.25in{\ninerm\bf \underbar{Testing}}\hfil\break\vskip.25in
XThe system was tested using 20 patterns representing letters A to T, each of
Xwhich is a 5x5 matrix. Results of the program when $\rho = 0.5$ and $\rho = 0.8$
Xare shown below. Numbers above the LTM patterns shows the iteration at which
Xthat node was selected and the letter 'R' indicates the point at which reset
Xocurred.
X
XFrom the output, it can be seen that trained LTM traces agree with that of Grossberg's data.
X\vfil
X\eject\end
X
//E*O*F art1.tex//

echo Possible errors detected by \'wc\' [hopefully none]:
temp=/tmp/shar$$
trap "rm -f $temp; exit" 0 1 2 3 15
cat > $temp <<\!!!
     168     456    3905 art1.c
     121     107    1289 art1.data
      70     393    2789 art1.tex
     359     956    7983 total
!!!
wc  art1.c art1.data art1.tex | sed 's=[^ ]*/==' | diff -b $temp -
exit 0

Jagath K. Samarabandu (716)-834-7386        [e-mail]
269, Winspear Ave.,Buffalo,NY14215        [e-mail]