Elliot's PBNT

2005-10-07T18:51:00.000-07:00

I thought I was back the last time I posted in early September. But as luck would have it, my honors thesis just wouldn't come out like i was hoping, and i ended up stuck knee deep in some data trying to get out any indication that we actually recorded the brain signals we think we recorded.

To the point... I have finally been able to spend some time back on good ol pbnt and I pretty much have an unrolled jtree algorithm done. The only thing left to do is handle how the dbn access the evidence properly. I will regrettably be gone for the weekend though, so there will not be any forward motion on this until mid next week.

As always I will keep all interested posted.

2005-09-09T14:12:00.000-07:00

After a rather long hiatus, I am back. I spent the last week or so getting ready for some research related deadlines and finishing a lot of administrative stuff associate with releasing 0.1 of PBNT. It is officially out now, so please go and download it, test it, use it, let me know what you think of it.

I am finally back to moving forward with adding support for DBNs. I am starting with a Jtree unrolled inference algorithm. I am a little hung up on how to differentiate between one time slice and another in terms of their internal representation.

As always I will keep you all posted.

2005-08-27T17:42:00.000-07:00

I have been continuing to clean the code more and more. I added a number of operators to the potential class. So now many of the operations in junction tree resemble more closely their actual equations. For example in absorb within pass message, it now is only a couple of lines. One line to divide the old sepset from the new and another line to multiply the clique by the sepset. This has greatly cleaned up my code.

I also have fully integrated the idea of having nodes be sets not lists within graphs and within neighbor, parent, and child fields. To match this, the evidence of an inference engine had to become a dictionary mapping nodes to their values. I also created a new generate index method for potentials that takes a list of nodes instead of a list of axes, and it then converts the node list into a corresponding axis list given the order of the nodes within the potential.

I have a little more to do to make this consistent throughout the code. The enumeration engine is working, but i have not completely fixed the jtree engine.

2005-08-22T15:44:00.000-07:00

With the code cleanup finished I have started working on implementing DBNs. I have already gotten great comments and feedback from Duncan and James. Duncan had a suggestion that I have tied my graph classes to my tables too closely. I really think he has hit it on the nose. I am currently studying his table classes in order to see if I can glean some clever ways given his code as to how to adapt my implementation of tables in order to take this idea into account.

Basically, I am going to look to change all node and graph classes to maintain only sets of parents, neighbors, children, etc. The tables will maintain an ordered list of the nodes (essentially I will keep all of them in topological order). In my case, there will be one difference. I am planning on implementing many of the things that Duncan has, but I want to incorporate these changes into my Distributions module. It seems to me that to define a table along a set of variables inherently makes it more of a distribution than a plain table (though in Duncan's case he uses tables for other things so I suppose it makes sense for him).

On the DBN front, I am starting first with the JTree inference algorithm. Specifically, I am planning on using Kevin Murphy's Interface algorithm as presented in his thesis. After that I am going to move onto the jtree construction, which should be rather simple. According to Kevin Murphy's thesis, the structure of the jtree can be the exact same as in the static case, except that one needs to guarantee that the backward and forward interfaces are each in a clique. To do this one has only to make sure that all nodes within these interfaces are connected in moral graph. After that the goal will be to create the DBN structure itself. I have been thinking about what this last structure might look like and so far I have not come up with anything I really like. This is why I am putting it off until the end. I think that in the creation of the rest of the code, I will be using the DBN class a decent amount, which I am hoping gives me some clues as to the most advantageous design. As of now, I am imagining something along the lines of a list of nodes that specify what a single slice looks like (this class is going to have the requirement, for now, that all slices have to have the same structure) and then another list of the backward interface nodes and another for the forward. But what might work better, would be to really have the DBN class be just a list of nodes as in the static case. Then use a new type of temporal node which maintains a list of intra slice parents / children and a different set of lists of inter slice parents / children.

As I implement this, I will also try to be incorporating the changes to my Distributions module, so that that does not have to wait for the DBNs to be done.

2005-08-19T17:32:00.000-07:00

The code cleanup is finally done, almost a week later than i thought it would be. I am actually very happy with the cleanup. The problem however is i have introduced a bug in the way i handle indexing the arrays. This is unbelievably frustrating. I thought I had finally figured out the slices, but it just seems that while they index the correct locations, and therefore work for a set statement, when doing a select statement, they return the desired arguments, but the array is not shaped correctly. A return value that should be 3 long is instead (1,3,1), and so when I use that value in a multiplication or something akin to that, I get all kinds of weird answers.

I think my plan is going to be to pass in the indices and axes as arguments to the [] notation, and then handle all of the slicing behind the scenes, that way i can fully abstract the method of slicing and the underlying array implementation from the rest of my code. This single problem has probably cost me more than 2 weeks worth of work. Ahhhhh!

Hope everyone has a great weekend.

2005-08-16T20:45:00.000-07:00

The code cleanup is now almost done. I finished the graph.py module. So officially I have cleaned the code, but since I started with InferenceEngine, and I have now made changes to method names in the Graph and Node modules, I have to go back through the InferenceEngine. This is going to wait for tomorrow, but it shouldn't take long.

2005-08-15T18:33:00.000-07:00

The code cleanup is going well. I have to go through the graph code and the distribution code, and then i should be done. So hopefully this will all happen tonight, but it could be tomorrow before I am done.

So far the code cleanup has really helped clarify things in my head. The distribution code is going to change the most, i am going to properly divide up the plain distributions from the conditional distributions and the potentials.

2005-08-12T19:32:00.000-07:00

I have decided to put the DBN development on hold and review the code that I have for a day or two. I am going to start by commenting the code, which I want to use to help remind me the essence of exactly what each piece of code is supposed to do. At the same time, I am going to make superficial changes to the code to bring it in line with Python Style Guide lines. After that is done, I am going to start actually redoing the structure of the code in order to improve the structure and simplicity of the code. This last part probably wont happen until Monday.

2005-08-11T01:27:00.000-07:00

Started reorganizing modules at James' suggestion. For example, all of the different types of nodes (BayesNode, DirectedNode, etc) are located within one large module Node.py. I am not quite finished doing this, and then the next step is to reorganize all of the files themselves into a different directory structure.

On the code front, I finished a very rudimentary version of EM. My current version computes the distribution of the missing data values and then fills in the missing values by sampling from this distribution. I find this solution to be algorithmically and conceptually simple, however it is not the best way to implement EM. Doing this means that the likelihood of "all" the evidence is never computed, instead the likelihood of each evidence case is computed separately. It will work for now...

I have moved onto DBNs. I have found Kevin Murphy's Thesis to be priceless so far. It looks like I am going to be able to salvage much of my JunctionTreeEngine code from the static case. I think I can make it work for the DBN (actually specifically on HMMs for now) without too much adaptation, therefore I decided to make it a child of the original JunctionTreeEngine class. This may prove a bad idea because it doesn't exactly make sense that a DBN case would be a child of a static case. But I am going to leave it for now and when I come back through the code I might separate them completely, or create a new abstract parent class and have them both inherit from that (after relocating the code that they would want to share into the parent class).

2005-08-09T11:52:00.000-07:00

MCMC is now passing all tests. It is still not totally clear if it is perfect or not yet though. Though it passes all of the tests most of the time, occasionally it misses some of them. I have been comparing it to Kevin Murphy's matlab toolbox. Since it is an approximate inference algorithm, I think the problem is that it is just using a different random number generator than matlab, and hence is giving slightly different answers. I will come back to it and test it more exhaustively when I have built more complex models.

I have a version of update parameters working. I have been working on EM. I am most of the way toward EM, though I ran into a small snag using non MCMC algorithms as the underlying inference, and I wanted to wait until I had a chance to discuss this problem with a real statistician. In the mean time I am moving on to dynamic bayes nets.

My goal with DBNs is to start by implementing a raw enumerative engine first, which just does a raw unrolling of the DBN during inference. I will subsequently move on to a more efficient approach.

2005-08-04T15:24:00.000-07:00

MCMC still needs to be tested more exhaustively, but it is currently passing basic sanity checks. EM is not far off either. Then it will be time to move on to DBNs. I desparately need to cleanup my code both style wise and to optimize it some. But i am going to put this off until i have finished more of the package and more of the code is reasonably stable.

2005-08-02T17:51:00.000-07:00

wooo hooooo!!! I finally figured out what was wrong with my jtree algorithm nothing! Turns out that I wasn't comparing the output to the right answer. It wasn't a total loss though in the process I cleaned up some code and fixed some bugs that were a problem but weren't affecting this particular test case.

mcmc is not far from done, but I left the code at home and I am at the lab so it will wait for tonight. Now it is on to learning.

2005-08-02T11:16:00.000-07:00

I am really stuck on some bug. I have traced pretty carefully and nothing seems to be wrong, yet it isn't giving me the right answer. I am going to shift gears and get MCMC done. I have already spent way too much time on jtree as is. I plan to come back to it at the end of the day or early tomorrow when I have a fresh head about the problem.

2005-08-02T09:57:00.000-07:00

Fixed some bugs in collectEvidence, so now jtree is truly working with no evidence on all of the nodes in the water network. Evidence is mostly implemented, but i still have some bugs to track down. Will keep everyone updated

2005-07-29T14:06:00.000-07:00

I finally finished a very basic version of the junction tree algorithm. I still need to add evidence handline, which I am doing right now. Essentially it is done, but I have some debugging to do since it is not passing all of the tests.

2005-07-27T16:36:00.000-07:00

Well, after becoming increasingly unsatisfied with the cleanliness of my code. I decided to drastically change my representation of graphs. For a graph is just a list of nodes. A DAG is just a topologically sorted list of nodes.

A "node" has a list of neighbors. a "directednode" has a list of parents. It took very little actually to make these changes. Mostly it changed the way i create a network. The changes had minimal effects on the rest of my inference code because i maintained all of the same functions in the BayesNet class but redefined them to work with the new structure. It does mean that now that style is probably not ideal in terms of efficiency. Because the inference code was designed to work on a graph centric view of the way to do things. Meaning that if you wanted the parents of a node you would say bnet.parents(node), which you can still do, but now in order to do that, the graph has to find the node in its node list and then returns node.parents. Which means it takes linear time to do it, when it should be a constant time operation.

I plan to go back and redesign the code to work more properly with this new representation.

These changes greatly cleaned up my JunctionTree inference code and got me back on track there. hopefully meaning i will finish it sometime tonight and let me move on to MCMC and EM.

-E

2005-07-26T12:59:00.000-07:00

oh yeah, almost forgot, James you would be proud, the tests for Junction Tree are already written, even though the algorithm itself is not!

-E

2005-07-26T12:57:00.000-07:00

I have been plodding away at the Junction Tree algorithm for a couple of days now. It is taking me much longer than i would like. However, I finally finished the triangulation part last night. Now i just have to build the join tree and define how to compute the marginal over it.

-E

2005-07-24T19:56:00.000-07:00

I am finally back.

It was a wonderful trip, I highly recommend going to Ukraine as soon as possible. There were few travelers, and that greatly added to the experience. That wont be true for long. I especially loved Lviv which felt like Prague 25 years ago, but a little smaller (at least I have been told). But I am glad to be home and able to start fully testing some of the code I have been writing.

I have a basic enumeration inference engine, Discrete Distribution, Bayes Net class all built and tested. The enumeration engine might need a little more work at some point, because of the way it is designed I kinda had to use a hack to get it to compute the probability of a variable that is already specified in the evidence. But I am going to leave it for now. The answers also seem to be slightly off due to the precision of floating point numbers. I am looking into alternative representations, but I am going to leave it for now.

I was going to move on to the variable elimination algorithm, but I think I am going to implement junction tree inference first. My goal is to have a barebones package working as soon as possible, and the junction tree inference algorithm will ultimately be more useful than the variable elimination algorithm.

Then after that it is on to EM...

That is all for now. Feel free to leave me a comment or note on this page.

2005-07-14T10:23:00.000-07:00

Still traveling, but getting some work done as I move. Quick disclaimer on my progress, everything that is implemented is largely untested and rough.

With that said, I have implemented enumeration, which really is more for testing and debugging other algorithms. But it is still nice to have it done. I also have decided to follow Kevin Murhpy's lead and use the "engine" style implementation for inference. This basically means that I created a class for inference which takes a bayes net as input and creates a new "engine" object using the specified inference algorithm. I found the main advantage here was going to be during learning. It would allow the user to first specify an inference algorithm and then run any learning method they wanted. This way I wont have to implement a learning algorithm for each inference method.

My next step is variable elimination, which is almost done, then MCMC, and then EM. After EM is done I will have a rudimentary package that does all of the basics, inference / learning. Woohooo!

2005-07-11T01:33:00.000-07:00

There had been a bit of a hiatus in my posting, for several reasons which i wont mention here. But I have decided to stick with blogger.com and so the blogs should be coming more frequently now.

I have posted my SoC proposal at http://dynevor.hopto.org/twiki/bin/view/Main/SoC.

Since then i have decided to make some changes. First, I am going to go for a more Python based approach. Originally i was going to focus on wrapping the Intel PNL libraries, and now i am going to make this a python implementation from the ground up, and then go back through later and reimplement python code with C code to speed things up.

I am currently traveling, so i am been spending most of my time reading and thinking about the details of my design. I am opting for the relatively standard method of inference whereby i decompose the bayes net to a join tree and perform inference on the converted tree rather than directly on the bayes net.

This has taken a little bit of reading, because as i realized most of my classes at berkeley we did not worry too much about the efficiency of implementation but more about the theory of the inference. And as such our implementations were to apply the inference algorithms more directly to the bayes net. In the case of Approximate inference we sampled the network directly, and in the case of exact inference we did a topological sort and then computed the marginals in a top down manner.

I am planning to represent the graphs as an adjacency matrix. The discrete distributions as a table. Then i am also going to have a class to represent "potentials" however, in the simple discrete distribution case, the potentials will be the same as the distribution itself, so there will not be any need to convert from a distribution to a potential. I have decided to focus on discrete stuff first and get a working package with only discrete distributions, simple exact inference using enumeration. Then i am going to add learning, and then start going back through and adding further distributions, and inference algorithms.

My plan is to have a very basic version of this working by August 1st, which gives me a month to add distributions, algorithms, and structural learning.

I am trying (even while i am traveling) to have a 1 week cycle, however, i can't fully test my stuff as i travel (i am only using a pocket pc version of python), so i am implementing but with little testing. So probably what i am going to aim to do is spend the rest of the trip implementing a skeleton for the basic structure, and then when i get home on July 18, I will start testing the skeleton and fixing, with the aim to be done by August 1st, and then have a true 1 week cycle from there on out.

2005-07-11T01:30:00.000-07:00

Hello World, testing...

Hello World update

2005-06-28T16:28:00.000-07:00

This is my first blog on my Google Summer of Code project. I am going to be creating a Python Bayes Net Toolbox. I will post shortly (ie the next day or so) a condensed version of my proposal. I welcome comments and suggestions on the toolbox design. I certainly have some ideas of my own, but nothing is totally finalized and I always love to hear others' thoughts.

I would like to thank Google for this wonderful idea and the Python Software Foundation for participating. Most importantly I would like to thank the individuals who have already spent time advising me and working on the SoC program as a whole, which includes Chris and Greg at Google and James of the Python Software Foundation. As I always I am where I am because of the constant guidance and support everyone in the Ivrylab at UC Berkeley.

Stay tuned for more project specifics...