Learning Tractable Bayesian Networks

Resumen

Estamos en la era del aprendizaje automático y el descubrimiento automático de conocimientos a partir de datos se utiliza cada vez más para resolver problemas en nuestra vida diaria. Una clave para diseñar con éxito algoritmos inteligentes útiles es poder modelar la incertidumbre que está presente en el mundo real. Las redes bayesianas son una herramienta poderosa que modela la incertidumbre de acuerdo con la teoría de la probabilidad. Aunque la literatura contiene métodos que aprenden redes bayesianas a partir de conjuntos de datos con alta dimensionalidad, los métodos tradicionales no limitan la complejidad de inferencia de los modelos aprendidos, y a menudo producen modelos en los que la inferencia exacta es intratable. Esta tesis se centra en el aprendizaje de redes bayesianas tratables a partir de datos y contiene la siguientes cinco contribuciones: Primero, proponemos estrategias para aprender redes bayesianas en el espacio de órdenes de eliminación (i). De esta manera, podemos acotar de manera eficiente la complejidad de inferencia de las redes durante el proceso de aprendizaje. Esto es especialmente útil en problemas donde los datos están incompletos. En estos casos, el enfoque más común para aprender redes bayesianas es aplicar el algoritmo de esperanza-maximización estructural, que requiere realizar inferencia en cada iteración del proceso de aprendizaje. Aprovechando la reducida complejidad de inferencia de los modelos, proponemos un nuevo método con el propósito de garantizar la eficiencia del proceso de aprendizaje y a la vez mejorar el rendimiento del algoritmo original (ii). Además, estudiamos la complejidad de la clasificación multidimensional, una generalización de la clasificación multi-etiqueta, en redes bayesianas. Obtenemos cotas superiores para la complejidad del cómputo de las explicaciones más probables y de probabilidades marginales de las variables clase dado el valor de todas las variables predictoras (iii). Utilizamos estos límites para proponer estrategias eficientes para acotar la complejidad de los clasificadores multidimensionales basados en redes bayesianas durante el proceso de aprendizaje. Con el objetivo de mejorar el rendimiento de estos modelos, proponemos métodos para el aprendizaje discriminativo de clasificadores multidimensionales basados en redes bayesianas (iv). Finalmente, abordamos el problema de predecir la ausencia de ataques en pacientes con epilepsia en el lóbulo temporal tras someterse a cirugía (v). Para ello, utilizamos un clasificador multidimensional basados en redes bayesianas, que están especialmente diseñados para modelar las relaciones entre las variables clase, es decir, ausencia de ataques epilépticos uno, dos y cinco años después de la cirugía. ----------ABSTRACT---------- We are in the era of machine learning and the automatic discovery of knowledge from data is increasingly used to solve problems in our daily life. A key to successfully design useful intelligent algorithms is to be able to model the uncertainty that is present in the real world. Bayesian networks are a powerful tool that models uncertainty according to probability theory. Although the literature contains approaches that learn Bayesian networks from high dimensional datasets, traditional methods do not bound the inference complexity of the learned models, often producing models where exact inference is intractable. This thesis focuses on learning tractable Bayesian networks from data, and contains the following five contributions. First, we propose strategies for learning Bayesian networks in the space of elimination orders (i). In this manner, we can efficiently bound the inference complexity of the networks during the learning process. This is specially useful in problems where data is incomplete. In these cases, the most common approach to learn Bayesian networks is to apply the structural expectation-maximization algorithm, which requires performing inference at each iteration of the learning process. Taking advantage of the reduced inference complexity of the models, we propose a new method with the purpose of guaranteeing the efficiency of the learning process while improving the performance of the original algorithm (ii). Additionally, we study the complexity of multidimensional classification, a generalization of multilabel classification, in Bayesian networks. We provide upper bounds for the complexity of the most probable explanations and marginals of class variables conditioned to an instantiation of all predictor variables (iii). We use these bounds to propose efficient strategies for limiting the complexity of multidimensional Bayesian network classifiers during the learning process. With the objective of improving the performance of these models, we also propose methods for the discriminative learning of multidimensional Bayesian network classifiers (iv). Finally, we address the problem of predicting seizure freedom in patients that have undergone temporal lobe epilepsy surgery (v). For that, we use a multidimensional Bayesian network classifier, which is specially well fitted to model the relationships among the class variables, i.e., seizure freedom at one, two and five years after surgery.