Approximate Implication for Probabilistic Graphical Models.

Abstract: The graphical structure of Probabilistic Graphical Models (PGMs) represents the conditional independence (CI) relations that hold in the modeled distribution. The premise of all current systems-of-inference for deriving conditional independence relations in PGMs, is that the set of CIs used for the construction of the PGM hold exactly. In practice, algorithms for extracting the structure of PGMs from data discover approximate CIs that do not hold exactly in the distribution. In this work, we ask how the error in this set propagates to the inferred CIs read off the graphical structure. More precisely, what guarantee can we provide on the inferred CI when the set of CIs that entailed it hold only approximately? In this talk, I will describe new positive and negative results concerning this problem.

Based on: lmcs.episciences.org/8943 ; proceedings.mlr.press/v161/kenig21a.html ; arxiv.org/abs/2310.13942

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.