ABSTRACT
This chapter discusses computational strategies to compute exact marginal distributions for any distribution within the family of distributions of a graphical model, all based only on properties of the graph itself. It aims to develop strategies that produce an algorithm valid for all distributions in a graphical model, rather than being valid only for one particular distribution. The chapter focuses on discrete-valued probability distributions. If the distribution is jointly Gaussian but many of the marginalization steps become much more efficient since they can be performed by efficient matrix operations. The chapter describes a message-passing algorithm that can produce exact marginal distributions for the maximal cliques of a graph that is triangulated and has been converted into a junction tree. A junction tree is not just an interesting graph-theoretic alternative representation of a triangulated graph, but it also yields a data structure useful to compute exact marginals.
