University of Washington, Bothell

CSS 485: Introduction to Artificial Neural Networks
Fall 2002
Homework Assignment 4: Hopfield Networks and Perceptrons

Assigned: Wednesday, November 20, 2002
Due: Monday, December 2, 2002 (start of class)

1. Let's say we want to build an ANN that can distinguish between bananas and pineapples, based on three sensor measurements: shape (round=1, elliptical=-1), texture (smooth=1, rough=-1), and weight (heavier than a pound=1, lighter=-1). The prototypical banana and pineapple would be:

   
   

   $$\mathbf{p}_1 = \left[\begin{array}{c}-1 1 -1\end{array}\right] \mathrm{(Banana)}$$

   $$\mathbf{p}_2 = \left[\begin{array}{c}-1 -1 1\end{array}\right] \mathrm{(Pineapple)}$$

   
   

   (a)

   How many possible input patterns are there?

   (b)

   Design a Hopfield network to recognize these patterns.

   (c)

   Design a perceptron to classify these two fruits, outputting a -1 for bananas and a 1 for pineapples. Train your network using only the above two patterns as the training set and analyze the results as indicated below. Repeat the procedure, this time adding an additional pattern (a heavy banana). Does your result change?

   In both cases, compute the weight matrix by hand. Demonstrate (again, using pencil and paper) that the network can properly classify the prototype patterns. Try ``corrupted'' patterns (e.g., misshapen bananas, light pineapples) and see what the output is.

   Next, implement the two networks using your favorite programming language and verify that you get the same results. I suggest that you write at least two functions: one that implements the computation of each network, taking as input the network input and the weights/biases, and one that implements the learning rule, taking as input the training set and returning the resultant weights/biases when training is complete.

2. In this problem, you are asked to use your debugged code to implement a pattern recognition problem using a Hopfield network. This will be a character recognition problem, with input patterns being:
   $$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert}\hlin... ...-0.5mm]{3mm}{3mm}& \rule[-0.5mm]{3mm}{3mm}\ \hline \end{array}$$
   These represent the digits $\{0, 1, 2\}$ displayed on a $6 \times 5$ grid. You will convert these to 1-D vectors by representing each white square by a -1 and each black square by a 1. You will then concatenate the columns to create the vectors. So, for example, the prototype pattern vector for a one is:
   $$\mathbf{p}_1 = [ \begin{array}{r r r r r r r r r r r r r r r r c ... ... -1 & -1 & 1 & 1 & 1 & \cdots & -1 & -1 \end{array}]\ensuremath{^{\mathsf{T}}}$$

   Use your code to compute the Hopfield weight matrix to store these three pattern. Verify the operation of the network for ``clean'' input. Next, investigate the network's ability to retrieve ``damaged'' patterns. Do this in two ways:

   (a)

   Produce ``occluded'' patterns, in which some of the 1's have been replaced by -1. For simplicity's sake, occlude entire rows of the patterns. See if your network can recall the patterns with one row occluded, two rows occluded, etc. How much occlusion can the network reliably tolerate?

   (b)

   Produce ``noisy'' patterns, in which $n$ elements of a pattern are ``flipped'' (1 changed to -1; -1 to 1). Select the elements to flip randomly, and run multiple trials for each value of $n$ and each pattern. For each value of $n$, you should get a single value which is the fraction of noisy patterns which were correctly recalled. Plot that fraction versus $n$.

3. Repeat the preceding character recognition problem using a perceptron. Your network should have three outputs, with each corresponding to one of the three characters. In other words, the outputs for the three patterns should be:
   $$\mathbf{t}_0 = [\begin{array}{rrr}1 & -1 & -1\end{array}]\ensurem... ...hbf{t}_2 = [\begin{array}{rrr}-1 & -1 & 1\end{array}]\ensuremath{^{\mathsf{T}}}$$