MENU

電気通信大学大学院情報理工学研究科
情報・ネットワーク工学専攻
English

OptimalTriangulation

Chao Li and Maomi Ueno

OptimalTriangulation is a JAVA software package that implements several triangulation algorithms for Bayesian networks, as described in [1, 2, 3]. The software can be reused and redistributed except for commercial purposes.

The elimination algorithm is used for searching a optimal triangulation. Ottosen and Vomlel (2012) has developed the search framework for this problem, and proposed several algorithms for solving it. Their algorithm search a optimal order in the space of all elimination orders, which has n!(n is the number of variables in the Bayesian network). However, we observed and proved that there are many equivalent orders in the search space and then we proposed a pivot vertex pruning [1] and a pivot clique pruning [3]to avoid the duplicated search. We also proposed a fast dynamic clique algorithm for further improvement the efficiency of the optimal triangulation algorithm [2]. The dynamic clique algorithm also be applied in other context, including protein structure discovery, fuzzy clustering, etc.

Download package(updated: October 27, 2017): source_file

  1. C. Li, M. Ueno, A depth-first search algorithm for optimal triangulation of bayesian network, in: Proceedings of the Sixth European Workshop on Probabilistic Graphical Models, 2012.
  2. C. Li, M. Ueno, A fast clique maintenance algorithm for optimal triangulation of bayesian networks, in: Proceedings of the second Workshop on Advanced Methodologies for Bayesian Networks, 2015.
  3. C. Li, M. Ueno, An extended depth-first search algorithm for optimal triangulation of Bayesian networks, In International Journal of Approximate Reasoning, Volume 80, 2017
ENGLISH