Title: Coresets for Dependency Networks,
Abstract: Many applications infer the structure of a probabilistic graphical model from
data to elucidate the relationships between variables. But how can we train
graphical models on a massive data set? In this paper, we show how to construct
coresets -compressed data sets which can be used as proxy for the original data
and have provably bounded worst case error- for Gaussian dependency networks
(DNs), i.e., cyclic directed graphical models over Gaussians, where the parents
of each variable are its Markov blanket. Specifically, we prove that Gaussian
DNs admit coresets of size independent of the size of the data set.
Unfortunately, this does not extend to DNs over members of the exponential
family in general. As we will prove, Poisson DNs do not admit small coresets.
Despite this worst-case result, we will provide an argument why our coreset
construction for DNs can still work well in practice on count data. To
corroborate our theoretical results, we empirically evaluated the resulting
Core DNs on real data sets. The results