Using Markov Blankets For Structural Learning Of Chain Graphs

Chain graphs were introduced in middle eighties of the last century for de-scription of conditional independence structures. The class of chain graphs involves both directed acyclic graphs (DAGs) and undirected graphs (UGs) as special cases, but is not limited to them. However, undirected graphs and directed acyclic graphs were popularly used to represent the probabilistic conditional independence struc-tures, and chain graphs received less attention in the past. But more and more researchers have interests in chain graph as they get more knowledge about this class of graphical models, and chain graph will go on to be an interesting field.Among a large number of research questions about graphical models, structural learning has caused extensive discussion, and it is same to chain graphs. There are mainly two kinds of methods for structural learning:constraint-based methods and score-based methods.Lauritzen summarized the most important researches done about structural learning in the last century, but most of these works are about DAGs and UGs. As far as I know, there is a few of algorithms about structural learning of chain graphs and I think it is an important reason for the less applications of chain graphs. As a result, I provide a new algorithm to learn the structure of chain graphs.In this paper, I propose two algorithms. One of them is a new algorithm for discovering the Markov blankets of vertices in chain graphs. The other one is an algorithm for structural learning of chain graphs based on the Markov blankets. Markov blanket is a set of vertices which is given to make the target vertex and the remaining vertices to be conditional independent. The Markov blankets can be used for causal discovery, feature subset selection, and structure learning of chain graphs. Our algorithm is based on the boundary and children of a target vertex, and it learns the Markov blankets from the training data directly without learning the whole structure of a chain graph first which lays foundation to the second algorithm. In the second algorithm, we first recover the skeleton by removing the spurious edges, and then orient the complex arrows. At last, we obtain the corresponding largest chain graph by applying three special rules iteratively. This method is more efficient as we only perform the conditional independence tests among vertices and members of their Markov blankets. We study the correctness of the algorithms under the faithfulness condition and give examples to illustrate the process of our algorithms.