title: Algorithms for Discovery of Multiple Markov Boundaries.
abstract: Algorithms for Markov boundary discovery from data constitute an important recent development in machine learning, primarily because they offer a principled solution to the variable/feature selection problem and give insight on local causal structure. Over the last decade many sound algorithms have been proposed to identify a single Markov boundary of the response variable. Even though faithful distributions and, more broadly, distributions that satisfy the intersection property always have a single Markov boundary, other distributions/data sets may have multiple Markov boundaries of the response variable. The latter distributions/data sets are common in practical data-analytic applications, and there are several reasons why it is important to induce multiple Markov boundaries from such data. However, there are currently no sound and efficient algorithms that can accomplish this task. This paper describes a family of algorithms TIE* that can discover all Markov boundaries in a distribution. The broad applicability as well as efficiency of the new algorithmic family is demonstrated in an extensive benchmarking study that involved comparison with 26 state-of-the-art algorithms/variants in 15 data sets from a diversity of application domains.
authors.affiliation: Center for Health Informatics and Bioinformatics, Department of Medicine New York University School of Medicine New York, NY 10016, USA ALEXANDER.STATNIKOV@MED.NYU.EDU NIKITA.LYTKIN@GMAIL.COM.
authors.forename: Alexander
authors.initials: A
authors.lastname: Statnikov
authors.affiliation: Center for Health Informatics and Bioinformatics, Department of Medicine New York University School of Medicine New York, NY 10016, USA ALEXANDER.STATNIKOV@MED.NYU.EDU NIKITA.LYTKIN@GMAIL.COM.
authors.forename: Nikita I
authors.initials: NI
authors.lastname: Lytkin
authors.affiliation: Department of Electronics and Informatics, Faculty of Applied Sciences Vrije Universiteit Brussel Pleinlaan 2, B-1050 Brussels, Belgium JAN.LEMEIRE@VUB.AC.BE.
authors.forename: Jan
authors.initials: J
authors.lastname: Lemeire
authors.affiliation: Center for Health Informatics and Bioinformatics, Department of Pathology New York University School of Medicine New York, NY 10016, USA CONSTANTIN.ALIFERIS@NYUMC.ORG.
authors.forename: Constantin F
authors.initials: CF
authors.lastname: Aliferis
keywords: Markov boundary discovery; information equivalence; variable/feature selection; violations of faithfulness