Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10 | Week 11 | Week 12 | Week 13 | Week 14 | Week 15 | Week 16
Well here we are, Pismo Beach and all the clams we can eat! Hey this doesn't look like Pismo Beach to me! I knew I should have taken that left turn at Albuquerque.
Pismo beach is where Bugs Bunny likes to spend his summer holidays, but sometimes getting there is a bit of pain. He instead usually winds up either in a mad scientist's castle, in a goldmine, or even in the middle of a Mexican bullring fight where he faces multiple challenges. In the midst of it all, he learns how to grab the bull by the horns and win the fight, making his holiday at Pismo Beach even more rewarding.
Sometimes when one takes a wrong turn while pursuing one destination, they wind up in a place they have never been before, possibly making a great discovery.
This summer, instead of heading off to Pismo Beach, I have decided to make a stop at the Reasoning and Learning Laboratory in which I am sure I will be facing many challenges and taking many wrong turns while conducting research. It is all in the name of the game.
Best described by Andrew Wiles, research is like "a journey through a dark unexplored mansion. You enter the first room of the mansion and it's completely dark. You stumble around bumping into the furniture, but gradually you learn where each piece of furniture is. Finally, after six months or so, you find the light switch, you turn it on, and suddenly it's all illuminated. You can see exactly where you were. Then you move into the next [dark] room...."
I will be looking forward to it! For starters, I better get on board with my reading on duality theory, a topic I will be studying with the rest of the duality team, Dorna Kashef, Prakash Panangaden, Joelle Pineau and Doina Precup.
Week 2: May 7 - May 11
This week focused on reading the papers assigned, and obtaining the big picture of the concept of a double dual machine. The papers deal with transition systems where the state is not completely visible to an outside viewer. Joelle gave a real-life example of what is meant by a sequence of observables that partly identify the state. Consider a robot travelling in a room. The robot feeds us back a sequence of images it scans. From the images, we are to figure out what the starting state of the robot was.
I began learning about duality for Kripke automata, which are basically regular automata enhanced with a notion of observation. The dual of this machine inverts the role of state and observation, and the dual of the dual (the double dual) flips the roles again, this time resulting in a machine that is a minimal representation of the original one. Pretty neat.
The other paper I am reading deals with various equivalence relations on states in a partially observable system. Some of these were covered in a course I took in theoretical computer science, but I am now obtaining a better understanding of how they link together.
Week 3: May 14 - May 18
The problem to be worked on is defined. Dorna and I will be studying exactly what equivalence holds between the states of a double dual machine, i.e., according to what equivalence relation are the states of the original machine collapsed? It was conjectured that the double dual's states must be related by a linear equivalence relation, namely trace equivalence. There is no existing proof of this, and we are not even really sure that it is trace equivalence. Is it bisimulation? e-equivalence? t-equivalence? None of the above? We will begin by using the process of elimination to figure it out.
Our problem stated formally: Let K" be the double dual of K. Let Sat: K --> K" be a mapping from the primal to the double dual. For any state s of K, we define Sat(s) = { [|t|] . s |= t } to be a state in K". If Sat(s1) = Sat(s2) then what equivalence relation holds between s1 and s2?
On a side note, I couldn't help but notice a paper entitled The Easiest Hardest Problem on Prakash's desk.
Ideas for the problem assigned were discussed during the duality group's weekly meeting. We have an answer to the problem for Kripke automata, both in the deterministic and nondeterministic cases. Our next task is to formulate an analogous question for POPAs (which I believe stands for Partially Observable Probabilistic Automata), and eventually for POMDPs, if possible. According to Prakash, this will require more thought than actually answering the question. In the paper The Duality of State and Observation, a mapping Sat: K --> K" from the primal to the double dual is defined for Kripke automata but it was not defined for POMDPs. We are to determine whether it is possible to define such a mapping, F: K --> K", for POPAs.
Joelle proposed that any POMDP can be transformed into a POPA and vice-versa. We will work on proving this.
Still no luck in formulating a map from the states of the primal to those of the double dual of a POPA machine. Dorna came up with an example of a POPA where the states of its dual become infinite, resulting in an infinite double dual machine. This threw us off because the double dual is supposed to be a "minimal" representation of the original machine. So if it is supposed to be minimal, then why does it become infinite? And how can we construct a map from a finite number of states to an infinite number of states? Maybe it does not make sense to look for a mapping from the states of the primal to the double dual in a POPA machine.
In any case, we will continue to study the structure of the double dual, and try to figure out what the double dual really represents.
Prakash proposed that although the double dual may become infinite, we should be able to find the original machine embedded in it. Also, an infinite double dual may still be minimal representation of the primal, but in a different sense. I am not sure what this means!
Upon presenting our results to Prakash Panangaden, we have concluded that it does not make sense to formulate a map from the primal to the double dual for a POPA machine, especially not when the double dual machine becomes infinite. We have noted that the original machine is indeed embedded in the double dual. The double dual captures the behaviour of the primal because formulas on the double dual, limited to the states of the original machine, define the same functions as they do on the original. We can clearly observe this in the example we have worked on. Note that the probability of observing R or B after taking x actions from states S1 or S2 is the same in both the original machine and the double dual machine.
Now that we have acquired sufficient background pertaining to the theory of double duals, we will move on to the purpose of their existence. We are particularly interested in how they can be applied to learning. This week, I am to read a paper entitled Looping Suffix Tree-Based Inference of Hidden State which will be discussed during next week's duality group meeting.
I have completed reading Isbell's paper on finite looping Prediction Suffix Trees (PSTs). Throughout the reading, I kept thinking about Predictive State Representations (PSRs), and was pleased to finally read that for deterministic environments, looping PSTs are actually PSRs. Isbell mentions that he hopes his work will provide a method for characterizing environments with non-deterministic hidden state as well. As we know, it is fairly difficult to plan and learn in these types of environments.
Theorem 1 of Isbell's paper states that any finite deterministic POMDP can be perfectly predicted by a finite loop PST, given a resolving history. As the double-dual representation of a machine always has deterministic transition structure and no hidden state, the first question that came to mind while reading the paper was whether the theorems can be reformulated for double dual machines.
As a result of Wednesday's meeting, it was decided I work on a few problems, namely:
1. to reformulate Theorem 1 for the case of Deterministic Automata with
Stochastic Observations (or at least play around with it)
2. to understand why the algorithm for learning a looping PST works and whether it can work for DASOs
3. to investigate whether resolving sequences always exist in DASOs.
The notion of minimality, even in an infinite state space, has been more clearly defined. Minimality implies that no two states behave alike and that there are no trivial states.
The cowriter of the paper PAC-Learning of Markov Models with Hidden State, Ricard Gavalda, dropped by our duality group meeting this week in order to introduce a method to render his learning algorithm more efficient. He proposed that instead of introducing &mu, the error threshold, as a parameter, we will allow the algorithm to learn the value of &mu .
Going back to my homework: in a DASO machine, (S,A,O,&delta:SxA &rarr S,&gamma:S &rarr Dist(O)), an experiment e is resolving if &exist t such that &forall s &isin S, < s|e|t > = < s|e >, where < s|e > = &sum < s|e|s' >. Now for the definition in English: an experiment e is resolving if there exists a state t such that e maps every state in the automaton to t. The question we ask is whether DASOs always have resolving sequences. I found an example of a DASO that has resolving sequences, and Ricard and Doina came up with an example involving a two-state DASO that pointed out that resolving sequences could not always be found. This led us to the conclusion that resolving sequences do not always exist in DASOs.
For my readers who requested images to enlighten them, here is one! This here is the two-state DASO I am still playing around with, where &gamma(R) = 0.8, &gamma(B) = 0.2 for state s_1, and &gamma(R) = 0.7, &gamma(B) = 0.3 for state s_2.
Tada, no resolving sequences! So how in dickensland can we know what state we are in if we are trying to learn the structure of this automaton?!
Anyway, my task for next week is to figure that out, as well as investigate whether the Looping Suffix Tree algorithm from Isbell's paper can be expressed in terms of experiments, tests and duals. This may be a direct translation.
Work is always harder to do when it follows a long weekend of partying. Nevertheless, I toughed it out and kept working on trying to express the Isbell algorithm in our language (in term of tests, duals, experiments). As I was trying this translation, I realized that I did not understand the Isbell algorithm all that well. And during the lab meeting, the rest of the duality group was a little perplexed by it as well. It is presented as though it is the simplest thing in the world, but we feel there may be crucial details missing!
We tried comparing it to the learning algorithm in the ECML paper which deals with the probabilistic case. I am not yet sure what to say about this... stay tuned, people.
Anyhow, the Isbell paper apparently does not provide an algorithm that finds the most succinct automaton, so my task is to find such an algorithm, not merely translate the Isbell algorithm.
This week, we reviewed what was discussed regarding the Isbell and ECML algorithms. Doina pointed out that we cannot exactly learn a DFA using the ECML algorithm because ECML assumes there is a probability distribution over the strings produced. We cannot just learn a compact representation of strings like the Isbell algorithm does. If we extend the Isbell algorithm to the stochastic case, it will be suitable for learning POMDPs, while the ECML algorithm is more suitable for learning HMMs. We have yet to generalize Isbell's algorithm to the stochastic case.
We are also exploring what the upper bound of the length of a sufficient history may be. Testing a few examples, we realized this could be very large.
Another open question is whether the looping PST that the Isbell algorithm learns is a representation of the double dual. We realized that the looping PST does not have the exact structure of the double dual, but that we may be able to extract the double dual from it. There is a lot of duplication in the PST representation, but we think that by collapsing identical states, we should end up with the double dual.
Now let us examine this Isbell algorithm a bit closer. While building the prediction tree, it says that if node x's transition set is deterministic, then continue, else check for loopability (i.e. whether this node is equivalent to any of its ancestors), else keep expanding(splitting) the node, as the history in question is not yet resolved. But what exactly is meant by "if x's transition set is deterministic, then continue"?.
I originally understood it as, "if x's transition set consists of unique actions, then continue". But then we started to think that it may be more complicated than that.
We began to work with prefixes to determine whether or not we must split the node. We compared the transition set of a node and a node + a prefix, and decided that if they did not match up, then we needed to split. We realized that, in some cases, it was not sufficient to only consider one-step prefixes. Click here for an example.
Anyway, after working with many examples, and banging my head as to what exactly this algorithm implied, I came to the conclusion that the whole concept is actually as easy as the paper portrays it to be. I realized that whenever the transition sets of x and x + a prefix did not match up, the original transition set of x did actually contain duplicate actions.. this sounds like gobbledeegook, let me give you an example: if transitions(x) = {a1, b0, b1, c1} where a,b,c are actions and 0,1 are observations, then this means that x's transition set is not deterministic! There are two possible destinations for a b action. (wow, what a discovery).
So, yes I was mighty confused as to why we needed to work with prefixes to determine determinism.
Until next meeting, I will be executing the PST algorithm on my example, as well as executing a split-merge algorithm, and then comparing the results. The split-merge apparently learns a more compact tree than the PST algorithm.
Top
Week 12: July 16 - July 20
Back to the drawing board. What I said last week may be true for the particular case Isbell's PST algorithm deals with, but it not general enough for all automata. Having duplicates in a transition set might not tell us anything. In other automata, we may never see anything like it. So, it is definitely not a general criteria for splitting a node.
Prepending actions may be beneficial. If you prepend and end up with more info, then you can better identify the state.
We still seek a learning algorithm for DASOs. We will transform the DFAs we have been working with to DASOs, play around with them, see if we can find an analogue of the Isbell algorithm, this time working with probability distributions.
Aside from that, Joelle came up with a merge-split algorithm we still need to formalize for the deterministic case. We conjecture that the algorithm will always produce something smaller than Isbell's PST algorithm.
Top
Week 13: July 23 - July 27
This week focused on familiarizing myself with some code written by Philipp Keller. He had implemented the ECML algorithm a couple of years ago. It took quite some time to understand what was going on since I never used C++ before and I didn't know much about GraphViz, but in the end I more or less figured out how to get everything to work, thanks to Joelle's help. I cannot say I understand the entire implementation quite yet, but I'll have to look at it again.
Joelle asked us to run some cases, particularly deterministic cases, and verify whether we would get a valid output. The algorithm is made specifically for the probabilistic case, but one can argue that the deterministic case is, in a sense, a case of the probabilistic case.
In addition, we are interested in implementing the PST algorithm. Our task is to modify the existing code in order to achieve this.
Top
Week 14: August 13 - August 17
Back to business. As there are only about two weeks left, I must start reviewing my work and preparing slides for my upcoming presentation.
In today's meeting, we discussed approximation. We went into some detail about possible metrics for DFAs. We want to know what it means to approximate in the deterministic sense. Language recognizers came to mind.
Consider the string metric defined as follows: Let L &isin &Sigma*, s,t &isin &Sigma*. The following is a metric for strings: d(s, t) := 2^(-n), where n is the smallest index s.t. s[n] &ne t[n]. This metric satisfies the super-strong triangle inequality, namely, d(x, y) &le man{d(x,y), d(y,z)}. Consequently, every triangle is isosceles, and spaces of this sort are always Stone spaces!
Anyway, now for the metric for languages. &Delta(L1, L2) = max.s &isin L1 min.t &isin L2 d(s,t).
Week 15: August 20 - August 24
This week was dedicated to preparing my presentation for the round of practice talks that were held on Thursday. Joelle gave me some pointers on how to structure my talk. She brought to my attention the common mistake of giving a talk in chronological order. To make it more interesting, one should start with a concrete example to deliver the big picture and motivate the audience, and then refine the topic by adding more details as one gets deeper into the presentation. Sounds good to me.
I valued the idea of having practice talks, as this enables one to receive feedback on the presentation prepared so far. I learned a lot about how I can improve the content of my talk, as well as the little details I should have paid more attention to.
On a comical note, I accidently said "flipatron" instead of flip automaton while speaking. In my opinion, flipatron sounds way cooler anyway. Someone even noted it was too cute an error to correct. *giggle*
Week 16: August 27 - August 31
The week of the SOCS Undergraduate Summer Research Symposium.... it was the moment we had all been waiting for! You know, free food! *cough* I mean, a chance to talk about all the wonderful research we have been doing throughout the summer!!
There were 17 presenters, all of which had fascinating projects to tell us about. I was kind of nervous about giving my speech beforehand, but once I got up there, all went smoothly. This time, I actually said flip automaton instead of flipatron. (Nevertheless, I still think flipatron sounds cooler, shh!).
Preparing for the symposium taught me how to structure a research talk and how to condense the material to fit a 15-minute time constraint. I will definitely benefit from these skills in the future!
But knowing how to structure a talk is only one of the many skills I acquired throughout my overall CDMP experience.
Working on a research problem has taught me how to think outside the box, read papers critically (just because it's written in latex, doesn't mean it's correct), and realize that results may not come right away, but that it is always beneficial to keep trying different approaches. Most of the times, one may not reach the set long-term goal, but may stumble upon interesting results that can hint towards it.
I would like to thank CDMP, NSERC, Joelle, Prakash, and Doina for having given me the wonderful opportunity of partaking in a research project over the summer.