Mutual conditional independence and its applications to model selection in Markov networks
- PDF / 669,177 Bytes
- 22 Pages / 439.642 x 666.49 pts Page_size
- 99 Downloads / 141 Views
Mutual conditional independence and its applications to model selection in Markov networks Niharika Gauraha1 · Swapan K. Parui2
© The Author(s) 2020
Abstract The fundamental concepts underlying Markov networks are the conditional independence and the set of rules called Markov properties that translate conditional independence constraints into graphs. We introduce the concept of mutual conditional independence in an independent set of a Markov network, and we prove its equivalence to the Markov properties under certain regularity conditions. This extends the notion of similarity between separation in graph and conditional independence in probability to similarity between the mutual separation in graph and the mutual conditional independence in probability. Model selection in graphical models remains a challenging task due to the large search space. We show that mutual conditional independence property can be exploited to reduce the search space. We present a new forward model selection algorithm for graphical log-linear models using mutual conditional independence. We illustrate our algorithm with a real data set example. We show that for sparse models the size of the search space can be reduced from O(n3 ) to O(n2 ) using our proposed forward selection method rather than the classical forward selection method. We also envision that this property can be leveraged for model selection and inference in different types of graphical models. Keywords Markov networks · Mutual conditional independence · Graphical models · Graphical log-linear models · Forward model selection Mathematics Subject Classification (2010) 97K99 · 00A69 · 97R99
Niharika Gauraha
[email protected] Swapan K. Parui [email protected] 1
Division of Computational Science and Technology, KTH Royal Institute of Technology, Stockholm, Sweden
2
Computer Vision and Pattern Recognition Unit, Indian Statistical Institute, 203 B.T. Road, Kolkata, India
N. Gauraha, S.K. Parui
1 Introduction A Markov network is a way of specifying conditional independence constraints between components of a multivariate distribution. Markov properties are the set of rules that determine how conditional independence constraints are translated into a graph (see [11] and [10]). The three Markov properties usually considered for Markov networks are pairwise, local and the global Markov properties. These Markov properties are equivalent to one another for positive probability distributions, see [12]. We introduce the concept of mutual conditional independence for an independent set of a Markov network. We derive an alternative formulation for the three Markov properties (local, pairwise and global) using mutual conditional independence. This alternative formulation is then used to prove the equivalence between mutual conditional independence property (MCIP) and Markov properties, under positive probability distribution assumption. This extends the notion of similarity between separation in graph and conditional independence in probability to similarity between the mutual s
Data Loading...
