CEDAR Project Software

Cedar.Gdl General Distributive Law Java Library

Keywords

Abstract Java Library, Distributive Law, Junction Tree, Belief Propagation, Contraint Satisfaction

Synopsis

The Generalized Distributive Law (GDL) formulation and algorithm were proposed in 2000 by Srinivas Aji and Robert McEliece. The GDL is a parametric expression-evaluation optimization method that may be instantiated on any specific commutative semiring structure. It can be used to express various algorithms that have been independently designed in domains such as Information Theory, Digital Communications, Statistics, Artificial Intelligence, etc., … We describe the design and implementation of an abstract Java class library for the GDL carried out as part of the CEDAR project. This library is a generic API meant to be instantiated with specific computation structures. It provides a runnable specification of the GDL in terms of abstract operations of a commutative semiring—i.e., a set with an addition (＋) and a multiplication (×), the latter distributing over the former. This allows the generic efficient evaluation of expressions using a dynamic-programming two-way message-passing algorithm on an arborescent structure called a Junction Tree. We used our library to regenerate as running instances two algorithms described by Aji and McEliece: the Fast-Hadamard Transform (FHT) algorithm on any finite Abelian group, and Judea Pearl's Belief-Propagation Bayesian reasoner. We also used it to generate a new instance for Constraint Satisfaction.

Software

Technical References