Michael Shadlen: Turing's enigma solution and the neurobiology of decision making
I'm a little late writing this one up, but last Thursday I went to my first Computer Science department seminar at UW. It's a bit misleading to stress that though, because it was actually someone from the physiology and biophysics department giving a talk that was partly a neuroscience primer for computer science people. The main part of the talk was about modelling probabilistic decision making, and I'll describe that part below the cut.
The talk presented a "diffusion to bound" model of decision making, which Turing used in cracking the Enigma code and Shadlen and colleagues use in analysing neuroscience experiments. The model uses chemical diffusion in 1 dimension as an analogy for a stochastic decision-making process.
The model
In the chemical system, in the absence of any outside influence, diffusion of the chemical is governed by a symmetrical gaussian function, so if there are symmetrical bounds (symmetrical in terms of their distance from where the chemical starts) then each bound has an equal chance of being reached first by the chemical. It's easy to visualise this as a random walk starting from exactly halfway between two bounds, and with the first bound to be touched representing the "decision" that the system will make.
To apply this to decision problems, all that is necessary is to shift the gaussian function that determines whether each diffusion step will be towards the upper or lower bound. For the neurological model, the offset represents the clarity of information that the decision maker has. For code-breaking, it represents the probability of two hypotheses, given some information from the messages to be decoded.
Neurobiology application
Shadlen's group do experiments with monkeys which are fairly analogous to some of the work my lab have done with artificial agents. A monkey is presented with a visual stimulus that contains moving dots, and based on the predominant direction of the dots' moving, the monkey must look in one of two places after the stimulus disappears. Rather like my advisor's experiments with stimuli that can be placed on a continuum between two categories (diamonds and circles in those experiments), these stimuli can either be 'pure' motion in one direction, or a blend in which a proportion of dots move in the desired direction. This allows the researchers to tune how clear a signal the subject receives in a precise manner, which in turn can be fed into the model.
By tuning some scaling parameters, the model can be made to fit the decision speed of real monkeys, which provides some validation. More impressively, however, once this fitting has been done the model predicts the probability that a monkey will look in a particular direction, given a stimulus of any given level of clarity. So the model does appear to be capturing something of the relationship between information and decision making in these experiments.
Shadlen also presented some readings from individual neurons, showing that it is possible to look at the firing rate of certain neurons over time, and use that to predict what decision the monkey is about to make. Basically the rate starts to increase with the presentation of any stimulus, but after a few hundred milliseconds there's a bifurcation, at which point a continued increase in firing rate is diagnostic that the monkey will do whatever that particular neuron is associated with, and a decrease indicates that it won't perform that particular behaviour.
I'm wondering if I can apply similar analysis techniques to the controllers of my agents. Most of the tasks I look at involve decision-making based on some kind of quantifiable input, and one big advantage of working in simulations is that it's trivial for me to record all the activity of every neuron. It is far from trivial to actually get any sense out of this data though, so ideas like this are useful food for thought.
Cryptography application
The problem to which Turing applied a similar model was deciding whether two messages had been encoded by machines with the same settings, which is an essential first step in decoding the messages.
Turing's technique was to compare the two messages letter-by-letter. If they were encoded differently, then the distribution of letters would be effectively random, so the chance of any given letter from message A matching a given letter from message B is 1 in 26. However, if the two messages had been encoded in the same way, then the uneven distribution of letters in natural languages increases the probability that any pairing of letters will match each other, apparently to 1 in 13. Thus every matching pair gives partial information about the probability that the two messages were encoded the same way, but there is no piece of evidence that straightforwardly tells the cryptographer whether or not they were.
Turing dealt with this by using the status of letter pairs as either matching or not as input to a diffusion to bound model. Each matching letter pair moves the model towards the bound that represents rejection of the null hypothesis, and each non-matching pair moves the model towards acceptance of the null hypothesis. Changing the size of the steps (they can't be symmetric because even if the two messages are from the same code the majority of letter pairs won't match) determines the model's thresholds for making either decision, and setting the size of the gap between bounds allows the user to decide how much information is needed before a decision is made. Apparently this model allowed for a reliable determination of whether or not two messages came from the same code.
Comments