Creating and sharing knowledge for telecommunications

Seminar - Complete MDL for Bayesian networks

on 19-07-2013


Alexandra M. Carvalho, PIAG-IT / IST-UTL

July 19, 2013, Friday, 16h15m.
(exceptionally in room QA02.1)

Abstract: A Bayesian network (BN) is a probabilistic graphical model that efficiently represents a joint probability distribution. It encodes specific conditional independence properties pertaining to the joint distribution via a directed acyclic graph. Learning unrestricted BNs given a sample consists in finding the BN that minimizes the relative entropy, also known as Kullback-Leibler (KL) divergence, between the distribution represented by the BN and the one induced by the observed frequency estimates (OFE). This problem is known to be NP-hard, therefore, optimal and efficient learning of BNs is restricted to tree-like structures. Using KL divergence for learning BNs tends to favor complete network structures since adding an edge never increases the KL divergence. This phenomenon leads to overfitting which is usually avoided by adding a complexity penalty. Common penalties include the minimum description length (MDL) and the stochastic complexity, which are computable upper bounds of the Kolmogorov complexity of a BN. The MDL version based on the integer universal coding has redundancies that can be explored to further compress it, obtaining what is called complete MDL. Although MDL for BNs has been derived, that is not the case for complete MDL. In this work we obtain the complete MDL expression for tree BNs, discuss its extension to other structures and compare it with other approaches in the context of learning BNs. Joint ongoing work with M. A. Figueiredo.

Room: QA02.1, Quimics

Support: SQIG/Instituto de Telecomunicações with support from FCT and FEDER namely by the FCT project PEst-OE/EEI/LA0008/2013.

More Information..