[Dept. of Computer Science]

Experimentation Project ACS


Title Local Monotonicity in Probabilistic Networks
Student Jesper Nederlof
Supervisor Johan Kwisthout
ECTS 7.5
Related Course(s) Probabilistic Networks
Description In this project, two algorithms related to so-called local monotonicity in probabilistic networks are implemented, tested, and benchmarked. The algorithms compute:
  1. 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;
  2. 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.
Special Note