Misc changes
[libdai.git] / TODO
1 - Add comments in example.cpp, add documentation.
2 - Write documentation.
3 - Improve error handling.
4 - http://www.boost.org/development/requirements.html#Design_and_Programming
5
6 OPTIMIZATION:
7 - BipartiteGraph::isConnected should be optimized using boost::graph
8 - Can the FactorGraph constructors be optimized further?
9 - Cache second-order neighborhoods (delta's) in BipGraph?
10 - Replace VarSets by small_set<size_t> if appropriate, in order to minimize the use of findVar().
11 - A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should store a reference to it
12
13 IDEAS:
14 - Use "gcc -MM" to generate dependencies for targets.
15
16 - Use a PropertySet as output of a DAIAlg, instead of functions like maxDiff and Iterations().
17
18 - A FactorGraph and a RegionGraph are often equipped with
19 additional properties for nodes and edges. The code to initialize those
20 is often quite similar; maybe this can be abstracted to classes
21 like ExtFactorGraph and ExtRegionGraph (Ext stands for Extended), e.g.
22 template <typename NodeProperties, typename EdgeProperties>
23 class ExtFactorGraph : public FactorGraph {
24 public:
25 std::vector<NodeProperties> nodeProps;
26 std::vector<std::vector<EdgeProperties> > edgeProps;
27 // blabla
28 }
29 A disadvantage of this approach may be worse cachability.
30 A problem is if there are nog properties for nodes (type 1), nodes (type 2)
31 or edges. Maybe this can be solved using specializations, or using variadac
32 template arguments or something similar?
33 Idea: you could define a "class Empty {}", and add some code that checks for
34 the typeid, comparing it with Empty, and doing something special in that case
35 (e.g., not allocating memory).
36 The main disadvantage of this approach seems to be that it leads to even more
37 entanglement.
38
39 - Instead of polymorphism by inheritance,
40 use polymorphism by template parameterization. For example, the real reason
41 you introduced the complicated inheritance scheme was for functions like
42 Factor calcMarginal( const InferenceAlgorithm & obj, const VarSet & ns, bool reInit );
43 Now instead, you could use a template function:
44 template<typename InferenceAlgorithm>
45 Factor calcMarginal( const InferenceAlgorithm &obj, const VarSet &ns, bool reInit );
46 This would assume that InferenceAlgorithm supports certain methods, like
47 clone(), grm(), ......
48 Ideally, you would use concepts to define different classes of inference
49 algorithms with different capabilities, for example the ability to calculate logZ,
50 the ability to calculate marginals, the ability to calculate bounds, the ability
51 to calculate MAP states, etcetera. Then, use traits classes in order to be able to
52 query the capabilities of the model. For example, you would be able to query whether
53 the inference algorithm supports calculation of logZ.
54 Unfortunately, this is compile-time polymorphism, whereas tests/test needs runtime polymorphism.
55
56 - If you ever do a rewrite, make sure that the graphical properties are
57 not entangled with the probabilistic properties. E.g., a factor graph
58 really should be represented as a bipartite graph, with a separate array
59 of variable labels and dimensions, and a seperate array of (pointers to)
60 factor tables. In this way, each factor could be implemented differently,
61 e.g., we could have some sparse factors, some noisy-OR factors, some dense
62 factors, some arbitrary precision factors, etc. Or we could make more use
63 of templates to have a more generic factor graph. Maybe in the end,
64 HasA relations are better than IsA relations...
65 Also, the current setup is stupid: I wrote a new function that works
66 on FactorGraphs, and I had to write boiler plate code for it in graphicalmodel.h
67 and in regiongraph.h (which is stupid).
68
69 - Use Boost::uBLAS framework to deal with matrices, especially, with
70 2D sparse matrices. See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
71 and tests/errorbounds/errorbounds3
72
73 - Introduce naming scheme:
74 all Vars and VarSets should be named v_..., e.g. v_i instead of i
75 all Factors should be named f_..., e.g. f_I instead of I
76 all indices should be named _..., e.g. _k instead of k
77 all iterators should be named i_, e.g. i_i is an iterator to i
78 all const_iterators should be named ci_, e.g. ci_i is an iterator to i
79
80 - Improve weightedgraph or use Boost::Graph
81
82 - Iterations and maxDiff are only interesting for iterative inference
83 algorithms. Yet, tests/test wants to know these values in a generic
84 way. Maybe we have to think of some way (e.g. using a Properties object)
85 to return these values from run(). Then we can simply look whether a
86 InferenceAlgorithm supports these fields. What other results could
87 we return? Time. MaxDiff during initialization for LC methods.
88 Or maybe we could use some traits mechanism which we can ask whether the
89 object has _iterations and _maxdiff variables.
90
91 - Think about whether the cavity initialization belongs to init() or to run().
92
93 - Fix LCLin.
94
95 - setFactor and setFactors should only change Probs, not Factors.
96
97 - Simplify Properties framework: each Property should be a std::string.
98 Each DAIAlg should have its own _properties struct and handle conversion.
99
100 - Forwardport the Bart patch
101
102 - Another design question that needs to be answered: should a BP object own a
103 FactorGraph, or only store a reference to a FactorGraph (which can optimize
104 memory), or should it be a FactorGraph with additional variables and functions?
105 Probably, the first or second option would be the best. Since FactorGraphs are
106 assumed to be rather static, it would make sense to store *references* to
107 FactorGraphs inside AIAlgs. Or maybe some smart_ptr? It would make sense to
108 prevent unnecessary copying of FactorGraphs. Also, general marginalization
109 functions now copy a complete object. Instead, it would make more sense that
110 they construct a new object without copying the FactorGraph. Or they can be made
111 simply methods of the general InfAlg class.
112
113
114
115 DIFFICULT
116
117 - What to do in case of NANs?
118
119 - Bug: TreeEP::logZ() seems to be wrong (?).
120
121 - Kees' trick for preventing NANs in GBP updates: if quantity smaller than epsilon, replace by epsilon.
122
123
124 OPTIONAL
125
126 - Define a better fileformat for .fg files (maybe using XML)?
127
128 - Find a good multi-platform build system (GNU autotool? Boost JAM?)
129
130 - Another design question that needs to be answered: should a BP object own a
131 FactorGraph, or only store a reference to a FactorGraph (which can optimize
132 memory), or should it be a FactorGraph with additional variables and functions?
133 Probably, the first or second option would be the best. Since FactorGraphs are
134 assumed to be rather static, it would make sense to store *references* to
135 FactorGraphs inside AIAlgs. Or maybe some smart_ptr? It would make sense to
136 prevent unnecessary copying of FactorGraphs. Also, general marginalization
137 functions now copy a complete object. Instead, it would make more sense that
138 they construct a new object without copying the FactorGraph. Or they can be made
139 simply methods of the general InfAlg class.
140
141 - Forwardport the Bart/Max patch.
142
143 - Alternative implementation of undo factor changes: the only things that have to be
144 undone are setting a factor to all ones and setting a factor to a Kronecker delta. This
145 could also be implemented in the factor itself, which could maintain its state
146 (one/delta/full) and act accordingly.
147
148 - Think about the _fac2ind variable: a better implementation of this feature is
149 probably possible.
150
151 - Optimize GBP with precalculated indices.
152
153 - Optimize all indices as follows: keep a cache of all indices that have been
154 computed (use a hash). Then, instead of computing on the fly, use the precomputed
155 ones.
156
157 - Variable elimination should be implemented generically using a function
158 object that tells you which variable to delete.
159
160 - Improve general support for graphs and trees.
161
162 - Add support for sparse potentials.
163
164 - Optimize BP_SEQMAX (it should use a better data structure than a vector for the residuals).