Local structured learning for feature selection and causal discovery

In machine learning, structured learning and prediction is an active area of research that involves learning and predicting several structurally related variables, in contrary to the traditional single variable learning and prediction. Probabilistic graphical model (PGM) is a dominant approach for structured learning problems. By modeling random variables as nodes and their interaction as directed edges, directed PGM such as Bayesian Networks (BNs) can capture the structure information among variables. Using such a structure, BN has been successfully used in a wide variety of applications including bioinformatics, natural language processing, and computer vision. For this research, we present methods for local structure learning and prediction with respect to one target variable, in terms of Markov Blankets (MB), within BNs. Compared to global structure learning, local structure learning can significantly scale up and improve structure learning efficiency. It can also lead to significant savings in computational costs if we are only interest in the structure relationships for one or a few specific target variables.;In this thesis, we introduce new methods to improve both the efficiency and accuracy of the existing local structure learning methods. Specifically, to improve the time efficiency of state-of-the-art methods, we first propose a constraint-based Simultaneous Markov Blanket Discovery (STMB) algorithm that exploits a newly discovered co-existence property among the local variables to remove the widely-used symmetry constraint. To improve accuracy, we introduce the Hybrid Markov Blanket (HMB) algorithm that combines STMB with a score-based search method to more accurately find the parent-and-child set within the local structure. Lastly, we develop a purely score-based algorithm, score-based Simultaneous Markov Blanket Discovery (S2TMB), and its more efficient variants to simultaneously improve the accuracy and efficiency of score-based MB discovery algorithms. We theoretically prove these algorithms' soundness and completeness, and analyze their improved complexities. Experiments on both synthetic and standard datasets show the superior performance of these methods to the existing local structure discovery methods.;To demonstrate the effectiveness of our local structure learning algorithms, we apply them to feature selection, resulting in a structured feature selection approach using MBs. We first theoretically prove that the optimality and advantages of structured feature selection over the traditional information-theoretic feature selection methods. Specifically, we show that the proposed structured feature selection method returns the minimal feature set that retains the maximal mutual information to the target node and also gives the lowest Bayes classification error. We then demonstrate the proposed structured feature selection method's performance on benchmark machine learning and computer vision datasets.;We further extend the local structure learning to local Causal Discovery. Besides performing learning and prediction, causal discovery can also facilitate data understanding and allow data manipulation and counterfactual inference. We utilize Reichenbach's Common Cause Principle to capture the causality and propose a new causal discovery algorithm, Causal Markov Blanket (CMB) discovery. CMB builds on the identified local structure and determines the exact causal relationships among local variables by tracking their conditional independence changes. We theoretically and empirically demonstrate the advantages of our local causal discovery approach over these existing causal discovery algorithms.;Lastly, we investigate MB discovery under the presence of latent variables with respect to a target variable. Together with observed variables, latent variables can provide a more compact representation of variables, lead to the discovery of hidden factors, and have been used in many applications. To efficiently identify the local latent variables, we propose MB learning with latent variables with a constrained structure expectation-maximization algorithm (LMB-CSEM). LMB-CSEM employs a divide-and-conquer strategy to identify the latent variables and their relationships to the observed variables. In addition, to apply the proposed LMB-CSEM to feature selection and discovery applications where the feature size can be large, we introduce a random subspace method to scale up LMB-CSEM. We demonstrate that the latent MB features determined by LMB-CSEM outperform the selected features determined by existing MB discovery algorithms without considering latent variables on benchmark feature selection and computer vision datasets.