Skip to content

# Department of Computer Science and Information Systems

Search
Search our website:

# Time Symmetric Values in Adapting Markov Chains.

• Speaker: Dr Tom Westerdale, Birkbeck, University of London.
• Date: Wednesday, 27 May 2015 from 16:00 to 17:00
• Location: Room 151, Birkbeck Main Building

In adaptive rule based systems we often pretend that the Markov property holds even when it doesn’t.

In this talk we investigate what happens when it does hold, and leave more general discussion for another day. So this talk is preliminary, and confined to a special case. We highlight an important question that shows up even here, and we outline the answer that I believe I have discovered. So in this talk, a rule is simply a transition in a Markov chain state diagram. A rule firing sequence is simply a legal path through the state diagram. The transition probabilities determine the sequence probabilities much as allele probabilities determine string probabilities in string populations that are “Hardy-Weinberg”. There is a payoff associated with each state. Transitions have values in the same sense that alleles have values in populations. Adaptation in the Markov chain is like evolution in a string population, and the equations should map the one seamlessly to the other. But they don’t. If we use the usual definition of the value of a transition, and if we try to base adaptation on that value the way population evolution is based on allele value, then the equations become a total mess and nothing makes sense. I have been battling with this problem for a long time. As I hoped, it turns out that the answer is simply a change in attitude. If we treat Markov chain time symmetrically, if we treat the past the same as the future, if we ask what would happen if time went the other way, then we obtain a new definition of transition value, and the equations all come out right. Well, not in all cases, but even when they fail to come out right the failure is simple and makes sense. In the cases where the old definition worked, the new definition reduces (or rather changes) to the old one. In this talk I want to outline the proof of one particular lemma because I want to know if you can find anything wrong with it. In one sense, the lemma looks a bit magic. I can’t produce a direct proof, so my proof is round about. I will be introducing a fair amount of notation, both to state the issues and to give the proof, but if there is an error in the proof I think it will be a conceptual error, not a notational error. I think the equations are right. So please bring your counterexample generators with you, and when we get to that lemma please be super critical. If there is an error I would like to be told now, and to be told by friends. The old way of treating time assymmetrically creates a roadblock in comparisons of learning and evolution. For longer than I care to contemplate I have been trying to find detours around that roadblock. But last November I finally realized that treating time symmetrically simply removes the roadblock.