| Description |
In this project, two algorithms related to so-called local monotonicity
in probabilistic networks are implemented, tested, and benchmarked. The
algorithms compute:
- whether the values of the variables in a probabilistic network can be
ordered in such a way that the network as a whole is locally monotone in
distribution;
- an optimal ordering that maximizes the number of monotone arcs in
the network.
The first algorithm consists of a preprocessing phase (to minimize the
search space) and, when needed, a branching phase (to find a solution).
The second algorithm will be a branch-and-bound approach that leans
heavily on (a variant of) the first algorithm to calculate lower bounds.
The algorithms will be tested on a test set of probabilistic networks
that are often used for research purposes.
The algorithms are implemented in Java.
References:
- Kwisthout, J., Bodlaender, H.L., and Tel, G. Complexity Results for
Local Monotonicity in Probabilistic Networks, UU technical report, in
preperation.
- Van der Gaag, L.C., Bodlaender, H.L. and Feelders, A. Monotonicity in
Bayesian Networks, Proceedings of the UAI, 2004.
- Van der Gaag, L.C., Renooij, S., and Geenen, P.L. Lattices for
Studying Monotonicity of Bayesian Networks. Proceedings of PGM'06, 2006.
|
![[Dept. of Computer Science]](/icons/li-dsol.gif){kind=icon}