Several changes by Giuseppe Passino
[libdai.git] / TODO
diff --git a/TODO b/TODO
index a660621..d389239 100644 (file)
--- a/TODO
+++ b/TODO
-IMPORTANT
+TODO:
 
-- Find out which methods need connected factor graphs (at least TreeEP and JunctionTree).
+- Improve documentation.
 
-- Forwardport the Bart patch
+- Adapt http://www.boost.org/development/requirements.html#Design_and_Programming
 
-- Get rid of multiple inheritance
+- Use "gcc -MM" to generate dependencies for targets.
+  Maybe even better: switch to cmake (see http://lwn.net/Articles/188693/)
+  cross-platform build system.
 
-- Introduce a namespace libDAI
 
-- Investigate the performance penalty from the use of Properties map
+OPTIMIZATION:
 
-- Another design question that needs to be answered: should a BP object own a
-  FactorGraph, or only store a reference to a FactorGraph (which can optimize
-  memory), or should it be a FactorGraph with additional variables and functions?
-  Probably, the first or second option would be the best. Since FactorGraphs are
-  assumed to be rather static, it would make sense to store *references* to
-  FactorGraphs inside AIAlgs. Or maybe some smart_ptr? It would make sense to 
-  prevent unnecessary copying of FactorGraphs. Also, general marginalization 
-  functions now copy a complete object. Instead, it would make more sense that
-  they construct a new object without copying the FactorGraph. Or they can be made
-  simply methods of the general InfAlg class.
+- BipartiteGraph::isConnected should be optimized using boost::graph
 
+- Replace VarSets by smallSet<size_t> where appropriate, in order to minimize the use of findVar().
 
-DIFFICULT
+- A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should
+  store a reference to it.  This prevents needless copying of (possibly large)
+  data structures. Disadvantage: the caller must not change the data structure
+  between calls. (Maybe a smart_ptr would help here?)
+  Also, general marginalization functions now copy a complete object. Instead, it
+  would make more sense that they construct a new object without copying the
+  FactorGraph. Or they can simply be made methods of the general InfAlg class.
 
-- Bug: TreeEP sometimes returns NANs.
 
-- Bug: TreeEP::logZ() seems to be wrong (?).
+IDEAS WORTH EXPLORING:
 
-- Bug: strange things happen for at least JTree and TreeEP if the factor graph is not connected.
-  Should be fixed by finding out which methods demand connected factor graphs and these
-  methods should check whether the supplied factor graph is connected.
+- Use a PropertySet as output of a DAIAlg, instead of functions like maxDiff and Iterations().
 
-- Kees' trick for preventing NANs in GBP updates:  if quantity smaller than epsilon, replace by epsilon.
+- Cache second-order neighborhoods (delta's) in BipGraph?
 
-- Bug: MF_SEQRANDOM does not work on alarm2.fg (normalization error: Z = 0)
+- If you ever do a rewrite, make sure that the graphical properties are not
+  entangled with the probabilistic properties. E.g., a factor graph really
+  should be represented as a bipartite graph, with a separate array of variable
+  labels and dimensions, and a seperate array of (pointers to) factor tables. 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, etc. Or we could make more use of templates to have a more
+  generic factor graph. 
 
+- 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
+  and tests/errorbounds/errorbounds3
 
-OPTIONAL
+- Introduce naming scheme:
+  all Vars and VarSets should be named v_..., e.g. v_i instead of i
+  all Factors should be named f_..., e.g. f_I instead of I
+  all indices should be named _..., e.g. _k instead of k
+  all iterators should be named i_, e.g. i_i is an iterator to i
+  all const_iterators should be named ci_, e.g. ci_i is an iterator to i
 
-- Restore brute force EXACT method.
+- Define a better fileformat for .fg files (maybe using XML)?
 
 - Alternative implementation of undo factor changes: the only things that have to be
-undone are setting a factor to all ones and setting a factor to a Kronecker delta. This
-could also be implemented in the factor itself, which could maintain its state 
-(one/delta/full) and act accordingly.
+  undone are setting a factor to all ones and setting a factor to a Kronecker delta. This
+  could also be implemented in the factor itself, which could maintain its state 
+  (one/delta/full) and act accordingly.
 
-- Regression test could be enhanced by 
-  * reporting number of iterations
-  * reporting all single node marginal errors
-
-- Think about the _fac2ind variable: a better implementation of this feature is
-probably possible.
-
-- Changed() methods?
-
-- It might be an idea to forbid modification of the structure of a factor graph
-  (except in constructors). Then we could do away with Regenerate and similar methods.
-
-- Think about whether using the L-1 norm as a distance measure between new and
-  old messages/beliefs would be better, since || P(x_A, x_B) - Q(x_A, xB) ||_1 < epsilon
-  implies that || P(x_A) - Q(x_A) ||_1 < epsilon. However, for a product of messages
-  we have the weaker || P1(x_A) P2(x_A) - Q1(x_A) Q2(x_A) ||_1 < 2 epsilon if
-  || P1(x_A) - Q1(x_A) ||_1 < epsilon AND || P2(x_A) - Q1(x_A) ||_1 < epsilon...
-
-- Implement damping.
+- Think about the RegionGraph::fac2OR variable: a better implementation of this feature is
+  probably possible.
 
 - Optimize GBP with precalculated indices.
 
+- Optimize all indices as follows: keep a cache of all indices that have been
+  computed (use a hash). Then, instead of computing on the fly, use the precomputed ones.
+
 - Variable elimination should be implemented generically using a function
   object that tells you which variable to delete.
 
 - Improve general support for graphs and trees.
 
-- What to do in case of divide-by-zero? For HUGIN, the correct way to handle
-  this is to define x/0 = 0. For other methods, this may not be the case...
-  Maybe a good solution would be to make different flavours of Prob which differ
-  in the way that they handle zeroes (two issues here: normalization of an all-zero
-  factor, which appears to be a sign that something is wrong, and division-by-zero
-  in operator/, operator/= and inverse(), which is probably harmless and can be fixed
-  by defining x/0 = 0. I think it is harmless because usually it occurs by calculating
-  some marginal _in the absence of some factor_ as an intermediate step. Afterwards,
-  this factor is always multiplied in again, which sets any value on these positions
-  to zero. Another difference would be how to deal with underflows: GBP often has 
-  numbers that converge to zero, but instead this gives an underflow. A solution is
-  to set everything smaller than some epsilon to zero. Finally, one could decide to
-  add support for sparse potentials. Oh, and whether it can handle negative entries.
+- Add support for sparse potentials.
 
 - Optimize BP_SEQMAX (it should use a better data structure than a vector for the residuals).
-  Also it does strange things in case of negative potentials.
 
-- Investigate the possibility to calculate logZ *during* the inference algorithm
-  by keeping track of all normalizations.
 
-- Write documentation.
+BAD IDEAS:
+
+- A FactorGraph and a RegionGraph are often equipped with
+  additional properties for nodes and edges. The code to initialize those
+  is often quite similar; maybe this can be abstracted to classes
+  like ExtFactorGraph and ExtRegionGraph (Ext stands for Extended), e.g.
+  template <typename NodeProperties, typename EdgeProperties>
+  class ExtFactorGraph : public FactorGraph {
+       public:
+               std::vector<NodeProperties>               nodeProps;
+               std::vector<std::vector<EdgeProperties> > edgeProps;
+       // blabla
+  }
+  A disadvantage of this approach may be worse cachability.
+  A problem is if there are nog properties for nodes (type 1), nodes (type 2)
+  or edges. Maybe this can be solved using specializations, or using variadac
+  template arguments or something similar?
+  Idea: you could define a "class Empty {}", and add some code that checks for
+  the typeid, comparing it with Empty, and doing something special in that case 
+  (e.g., not allocating memory).
+  The main disadvantage of this approach seems to be that it leads to even more
+  entanglement.
+
+- Instead of polymorphism by inheritance, use polymorphism by template
+  parameterization. For example, the real reason you introduced the complicated
+  inheritance scheme was for functions like
+      Factor calcMarginal( const InferenceAlgorithm & obj, const VarSet & ns, bool reInit );
+  Now instead, you could use a template function:
+      template<typename InferenceAlgorithm>
+      Factor calcMarginal( const InferenceAlgorithm &obj, const VarSet &ns, bool reInit );
+  This would assume that InferenceAlgorithm supports certain methods, like
+  clone(), grm(), ......  Ideally, you would use concepts to define different
+  classes of inference algorithms with different capabilities, for example the
+  ability to calculate logZ, the ability to calculate marginals, the ability to
+  calculate bounds, the ability to calculate MAP states, etcetera. Then, use
+  traits classes in order to be able to query the capabilities of the model. For
+  example, you would be able to query whether the inference algorithm supports
+  calculation of logZ.  Unfortunately, this is compile-time polymorphism, whereas
+  tests/test needs runtime polymorphism.