BP_dual replicates a large part of the functionality of BP; would it not be more efficient to adapt BP instead?

Author: Frederik Eaton

Cache second-order neighborhoods in BipartiteGraph.

Member dai::CBP::runRecurse (InfAlg *bp, Real orig_logZ, std::vector< size_t > clamped_vars_list, size_t &num_leaves, size_t &choose_count, Real &sum_level, Real &lz_out, std::vector< Factor > &beliefs_out)

dai::CBP::runRecurse() could be implemented more efficiently with a nesting version of backupFactors/restoreFactors

Class dai::DAIAlg< GRM >

A DAIAlg should not inherit from a FactorGraph or RegionGraph, but should store a reference to the graphical model object. This prevents needless copying of (possibly large) data structures. Disadvantage: the caller must not change the graphical model between calls to the inference algorithm (maybe a smart_ptr or some locking mechanism would help here?).

Class dai::FactorGraph

Alternative implementation of undo factor changes: the only things that have to be undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This could also be implemented in the TFactor itself, which could maintain its state (ones/delta/full) and act accordingly. Update: it seems that the proposed functionality would not be enough for CBP, for which it would make more sense to add more levels of backup/restore.

Class dai::IndexFor

Optimize all indices as follows: keep a cache of all (or only relatively small) indices that have been computed (use a hash). Then, instead of computing on the fly, use the precomputed ones. Here the labels of the variables don't matter, but the ranges of the variables do.

Class dai::InfAlg

General marginalization functions like calcMarginal() now copy a complete InfAlg object. Instead, it would make more sense that they construct a new object without copying the FactorGraph or RegionGraph. Or they can simply be made methods of the general InfAlg class.

Use a PropertySet as output of an InfAlg, instead of functions like maxDiff() and Iterations().

Class dai::RegionGraph

Generalize the definition of region graphs to the one given in [YFW05], i.e., replace the current implementation which uses a BipartiteGraph with one that uses a DAG.

The outer regions are products of factors; right now, this product is constantly cached: changing one factor results in an update of all relevant outer regions. This may not be the most efficient approach; an alternative would be to only precompute the factor products at the start of an inference algorithm - e.g., in init(). This has the additional advantage that FactorGraph e can offer write access to its factors.

Class dai::State

Make the State class a more prominent part of libDAI (and document it clearly, explaining the concept of state); add more optimized variants of the State class like IndexFor (e.g. for TFactor<>::slice()).

File doc.h

Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming

Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html

Disentangle structures. In particular, ensure that graphical properties are not entangled with probabilistic properties. For example, a FactorGraph contains several components:

a BipartiteGraph
an array of variable labels
an array of variable state space sizes
an array of pointers to factor value vectors In this way, each factor could be implemented differently, e.g., we could have some sparse factors, some noisy-OR factors, some dense factors, some arbitrary precision factors, etcetera.

Use boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices. See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm However: I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.

File hak.h

Implement more general region graphs and corresponding Generalized Belief Propagation updates as described in [YFW05].