Models of Computation - Mathematics 352 - Fall 2009

For HW #23

1. Suppose we have a Hopfield Network with only four nodes, arranged in a 2 x 2 array. Suppose we impose the pattern with the top two nodes on, and the bottom two off.
   1. Draw a diagram showing all six connections between the nodes and the strength of each connection after the above pattern is imposed.
   2. Suppose we now "show" the pattern with all nodes off except the top left node to our network. Show that the network will recall the above pattern after one iteration, and further iterations will not change the pattern.
   3. Suppose we now show the network the pattern with all nodes on except the top left node. Show that the network will recall the complement of the above pattern after one iteration, and further iterations will not change the pattern. ("Complement" means "opposite", i.e., replace "on" with "off" and vice versa.)
   4. Suppose we now impose the pattern with the two left-hand side nodes on, and the two right-hand side nodes off (without clearing the first pattern imposed above). Give the strength of each connection.
   5. There is a way to simulate this 4-node network on the 10-node network at www.phy.syr.edu/courses/modules/MM/sim/hopfield.html .
      Figure out how, and then use this simulation to verify parts (b) and (c) above.
      Hint: If you try to use only the four nodes in the top left of the grid, it won't give you a correct simulation. Can you tell why?
   6. Suppose we now show the network the pattern with all nodes off except the top left node. What will happen after "clicking" Recall once? After clicking it twice? Thrice? Can you explain what's going on, and why?
      Hint: instead of doing calculations by hand, use the simulation mentioned above.
2. Suppose we have a Hopfield Network with n^2 nodes, arranged in an n by n array. Let P₁ and P₂ be two different n by n patterns. Let C₁ denote the set of all connection strengths that we'd get if we imposed P₁ alone on our network (without imposing P₂.) Let C₂ denote the set of all connection strengths that we'd get if we imposed P₂ alone on our network (without imposing P₁.) So, if we impose both P₁ and P₂ on our network, we get a set of connection strengths that is some "combination" of C₁ and C₂; let's  denote this "combination" of C₁ and C₂ by C.
   1. Is C the sum of C₁ and C₂? More precisely, is each connection strength in C the sum of the two corresponding strengths in C₁ and C₂? (If you find this too abstract, try it with a concrete example, say with the 2 x 2 network in the first problem, above).
   2. Let Q₁ be an n by n pattern that's very similar to P₁ but not to P₂. If we show Q₁ to our network (with P₁ and P₂ both already imposed on it) and click Recall enough times, the network will probably recall P₁. Can you explain why this happens even though C might be very different from C₁? (In other words, if only P₁ is imposed on the network, it's not too surprising that the network recalls P₁ when it's shown the pattern Q₁ which is similar to P₁; but why does this still work even after we "mess up" C₁ and change it into C?)
      Hint: (This hint is not easy to understand, but give it a try.) Let V(d, Q₁, C) denote the total input that any given node d would get from all the other nodes in Q₁ under C. Step 1: Show that V(d, Q₁, C) = V(d, Q₁, C₁) + V(d, Q₁, C₂). Step 2: Argue that V(d, Q₁, C₂) is probably small in magnitude (i.e., ignoring + and - signs) compared to V(d, Q₁, C₁).
   3. Suppose we impose P₂ on our network many times, but impose P₁ only once. Now if we show Q₁ to our network, do we still expect our network to recall P₁ rather than P₂? Try to think about this as hard as you can before you try it out on the Hopfield Network simulator (applet link appears above). Then explain why it's the way it is.
   4. Why is it that a Hopfield Network cannot memorize too many patterns? More precisely, what's wrong with the following line of reasoning:
      Suppose we impose a large number of patterns, P₁, P₂, ... , P_k,  on an n by n Hopfield Network (say k is larger than n^2). Let Q₁ be an n by n pattern that's very similar to P₁ but not to the other patterns. Let C_i be the connection strengths corresponding to P_i.  As in Part (b), for any given node d, we can expect V(d, Q₁, C_i) to be small for every i other than 1. Furthermore, probably for about half the i's, V(d, Q₁, C_i) is negative and for the other i's it's positive. So we can expect the sum V(d, Q₁, C₂) + ... + V(d, Q₁, C_k) to be small compared to V(d, Q₁, C₁). So when we show Q₁ to the net, P₁ should be recalled.
      Hint: If you flip a coin 100 times, you might expect 40%-60% heads with a high probability, i.e., about 10 away from "excatly half and half."  If you flip it 1,000,000 times, you can expect, with the same high probability as before, a ratio of heads to tails much closer to 1/2, say between 49.9% and 50.1%, i.e., 499,000-501,000 heads. But that means you can expect to be about 1000 away from "exactly half and half", which is much larger than being 10 away.
3. (Optional) For each of the following "phenomena" or "characteristics", do you think it applies to Hopfield Networks, to human memory, to both, or to neither? Give as much evidence or support as you can for your statements.
   1. Partial recall.
   2. Repetition (re-learning) leads to better recall.
   3. "Nice" or symmetrical patterns are easier to memorize/recall.
   4. Similar pictures are more likely to be confused during recall.
   5. Recognition is easier than recall (e.g., multiple choice is easier than coming up with the answer).
   6. Memory is not recorded locally, but is "spread out" all over the network.
   7. Having a sense of which memories are old vs. new (recorded long ago vs. recently).
   8. Complete recall may take several iterations (several attempts); or it may never be achieved.
   9. Please let me know if you think of other interesting characteristics I could list here!