Forward Filtering Backward Sampling

* Talked with Nando. Learned about FFBS: this allows one to sample from the joint distribution, not only from the marginals, in chains and trees. This is really important and has to be understood and implemented.

-> learn in depth FFBS

Tree Gibbs sampler ready for review

* More tests on the Tree Gibbs Sampler

* Spent some time on Design Changes

-> Talk to Nando to verify the work

Tree Gibbs Sampler and Gibbs Sampler agree!!

* A big milestone was reached today: after some more bugs were discovered and fixed, the Tree Gibbs Sampler seems to work (at least on a simple 10 nodes graph)! Hurray!

* I didn't have time to read some C++, but I spent time learning more about C++ debuggers (on Linux). DDD sucks, but seems to be the best; you have the option to stick the command tool to the top, which improves the situation (a bit). There are still many things that bother me. I tried the GPS debugger, which seems more modern but, at first glance, is completely worthless (you can't even break on a variable...)

* I developped some self made C++ practices:

* Try to avoid loops using integers, use iterators whenever you can, the type system is much more likely to catch errors!

* If you use more than one for loop in a function, give names to the looping variables, don't just use i, j, etc!

-> implement random graph generation for a single connected component

-> cosmetic changes...

-> speack with Nando and see what's up next

More debugging

* Cosmetic changes, implemented a lot of debugging functions (display_subgraph, etc...)

* Found and fixed the crucial bug affecting message passing (which was induced by yesterday's fix). MP and Simple Gibbs now agree for MRFs !

* Started referring to MRFs as "pairwise graphs" since an MRF isn't (apparently) restricted to pairwise potentials

* Still bugs in Tree Gibbs. I found a *major one*: we need to allow the Potential on the nodes to be SingleDiscrete and not Constant!! Or we should find a better way of implementing that...

* New ideas for a better interface in RandomVariable (less friends, implementation better encapsulated). We could use each sample as "prior knowledge". There is still the problem of translating that prior knowledge into probabilities (that would have to be a public function). Maybe I'll spend some time thinking about it.

-> correct the Tree Gibbs Sampler

-> implement a random graph creation algorithm, that creates connected graphs (use Boost algrithms)

-> if time allows, learn more about C++ (Parashift FAQ)

Debugging

* Implemented Boost random system, it is nice. It wasn't too difficult

* Found a critical bug in the message passing algorithm for MRFs (the messages were sent when they shouldn't). Fixed, but we still probably have bugs. Gibbs and message passing still don't agree...

* Cosmetic changes, almost every template is manually instantiated now, which is good. No more #include "xxx.cc" directives

-> continue debugging...

Tree Gibbs sampler finished

* finished the redesign of the RandomVariable class, it now has a lot of friends. Not ideal but I must concentrate on the implementation for now...

* as always, small cosmetic changes, template instantiations, etc...

* The executable is now 20 MB (!) in size! I don't understand how it can get that big...

* Everything is up and running, but I *feel* unknown bugs lurk in the code. We have big amounts of difference between Gibbs and tree Gibbs and we shouldn't... Some bug searching is now needed.

-> bug tracking, bug tracking, bug tracking

-> implement the Boost random number generator

Tree Gibbs Sampler running

* Bugs in Boost CVS fixed, now we have all that is needed (I think)

* Learned about friends, partial specializations of classes; you can't just partial specialize the member functions, if you haven't partial specialized the class (though these functions can be taken out of the partially specialized class definition).

* Manually instantiated the Node class

* Cosmetic changes thoughout the code

* Started redesigning the RandomVariable class / interface

* I have the tree gibbs sampler running entirely. Now need some comparisons to squash the remaining bugs...

-> finish the redesign of the RV class

-> finish completely at last the Tree Gibbs sampler

Bugs in Boost CVS

* Some bugs were sorted out, but there are still bugs in the bundled properties implementation for subgraphes. Request for fixes in boost-users

* Changes to the tree partition algorithm, related to memory control/ management. It now takes a subgraph as argument

* Cosmetic changes regarding *::vertex_bundled, etc... Boost CVS allowed the use of traits

* Continued to manually instantiate templates

-> finish the Tree Gibbs sampler (debug, etc...)

-> redesign the Random Variable implementation and interface

-> update to Boost CVS at UBC

Update to Boost CVS

* Started the implementation of Tree Gibbs sampler, updated to Boost CVS because I needed bundled properties with subgraphs.

* Problems with type_traits in Boost CVS, that's a showstopper

* Thought about the mpossible reimplementation of large parts of code to better encapsulate; need to redesign interfaces...

-> sort out the Boost issue to complete implementation

Tree Gibbs sampler

* Worked on the design of the Gibbs tree sampler

* We will use subgraphs, it is problematic that bundled properties are not implemented for them

-> implement Tree Gibbs Sampling

Read of Chapter 22

* started reading chapter 22 of Jordans on variational methods. Seems very interesting

-> finish reading of Chapter 22

Tree partition finished

* Finished writing and debugging the input C++ code with streams

* Finished debugging the tree partition algorithm. It works fine with a 5*5 MRF, and with the test graph written for the draft paper back in Russia.

* Cosmetic code changes, creation of new files, etc...

-> write a Rao Blackwell function (or generalized Gibbs sampler) to work with trees, in the pairwise potential case

Standard C++ Library: IO Streams

* spent the day essentially learning C++ streams. Many things to keep in mind:

* I/O and parsing in C++ is a tedious task!! Almost everything has to be done by hand. It can be very buggy code, hard to maintain...

* 2 basics levels of functionality: the >> operators are for very simple tasks and parsing, for common situations. But should you need to write complex or even non trivial I/O, you need to learn about member functions (get, getline, etc... and a ton of other things)

* It may thus be worth it to learn the Boost parsing library or the Boost regexp library

* Only practice can help remember the many issues associated with I/O streams, I think.

* the C++ parashift FAQ is really well documented, bookmarked it.

* Learnt about friends, inline functions should be declared in the implementation

* Headers are not meant to disallow access to your classes, it is first a tools for the programmer, not a security measure

* downloaded a C++ Standard Library book

* wrote a test function to read graph from a file using a simple language; needs to be finished and debugged

-> finish to debug the io code

-> write a random potential and / or random variable generator

-> previous goals of yesterday

Template Specialization

* tried explicit template instantiation. Seems to work fine, we should maybe do that throughout the code

* Learned a lot about C++. A templated function can't have partial specialization, nor can't it have default template arguments. A workaround is just to do partial specialization on a class that can be used as a function

* finished debugging tree partition. It is now able to produce the correct result in a simple test case

* BGL: be very careful about add_edge or remove_edge, it invalidates iterators

* Made make_random_graph truly generic

* cleaned up in the code (minor, mainly converting i++ to ++i)

-> continue to test tree partition on more complex cases, clean up code and comments

-> continue to work on genericity

-> reorganize current files, continue clean-up, maybe try to do explicit instantation everywhere

Template compilation, test of Tree Partitioning

* lots of things learned about template compilation. GCC is not yet optimal for this; one way out of the problem would be to implicitely instantiate the templates...

* C++ : learned about the for loops (seems funny to write that!!), and of the difference between ++i and i++. ++i is preferred.

* Tested and fixed lots of bugs about the tree partitioning. Much work still needs to be done

* Made make_random_graph generic

-> finish testing the tree partition, and make some generic changes

Tree partition implementation (end)

* Learned about typedefs in more detail; an iterator is a pointer so you can know the type it points to; fixed/improved things in the code.

* BGL: learned a lot about subgraphs, the root subgraph MUST be a subgraph. Mailed Boost-users with question about subgraphes

* First attempt at cleaning the code with respect to templates; learned about forward declaring a templated class; many linkers errors encountered, better understanding of tempalte instantiation and compiling

* Completed the first version of tree partitioning, needs testing.

-> pursue work on template compilation models

-> test the tree partition implementation

-> try to render things more generic (changing vecS to listS)

Tree partition implementation

* Learned about the subgraph feature of BGL. Seems OK, but we will definitely need bundled properties...

* Learned more about properties map (again). You can access them, in an adjacency list, with the get() function. It suddenly make more sense. I think I begin to have a good understanding of the BGL.

* Made a first attempt at an implementation of graph partitioning. It seems to have a backtrack size of 1 (the backtrack is not cleanly coded though). It should have all the functionality of the previous work, except the simplification of one and two connectivity (which is important).

-> finish the first implementation (shouldn't require long). Compile and test

-> review Gibbs sampler, and MP code (optimize, etc...)

-> still need to learn about (nested) typedefs

Tree partition design

* Learned more about BGL: interior properties effectively means they are contained by value inside the graph. External means they are not stored in the Graph.

* To be more generic, our MP (and probably Gibbs too) code should sometimes uses a vertex index map. As it is, it works only with a vector implementation for the adjacency list, which seems to contain a built-in map.

* Two bugs in the BGL, which could be a problem. remove_edge sometimes fail, and bundled properties are not implemented for subgraphs.

-> Mail the BGL list about how do you access the builtin index map for a vector

-> work on the implementation of graph partitioning

Last bugs fixed on Message Passing

* Fixed the bug discovered yesterday. Found a lot more (in the code implementing the sum product for a Potential node, and the code storing the product_messages by a Potential node).

* Gibbs sampler and MP code are at last probably bug free. At least, their results seem to converge at last...

* General clean-ups of a lot of stuff in the code.

* Thinking about the implementation of the graph partition algorithm

-> start implementing the graph partition algorithm

-> optimize the Gibbs sampler ( dont create and destruct the functors every time)