Theoretical studies on Bayesian network classifiers

Abstract

En las últimas décadas, el aprendizaje automático ha adquirido importancia como una de las herramientas fundamentales en inteligencia artificial. El incremento en la disponibilidad de datos y capacidad computacional disponible a bajo coste han contribuido a extender los métodos de aprendizaje automático en casi todas las ramas de la tecnología. Mientras que gran parte de la investigación se centra en el desarrollo de nuevos algoritmos y métodos para tratar diferentes problemas, es ampliamente reconocido que el análisis formal y los resultados teóricos son necesarios para entender los algoritmos empleado, sus limitaciones y sus capacidades. El trabajo desarrollado en esta tesis se centra en éste último aspecto de la investigación en aprendizaje automático. Estudiamos los clasificadores con redes Bayesianas y en general clasificadores generativos basados en modelos gráficos probabilísticos. Los modelos gráficos probabilísticos han sido y siguen siendo ampliamente estudiados en estadística y en esta tesis los analizamos en el contexto de uno de los problemas más representativos en aprendizaje automático, la clasificación binaria. Nuestro resultado principal es la descripción, tanto para redes Bayesianas como para modelos de Markov no dirigidos, de las implicaciones de las independencias condicionadas en las funciones de decisión asociadas. En particular, describimos las familias de funciones discriminantes asociadas con las familias de clasificadores con redes Bayesianas más utilizados. Construimos polinomios que interpolan las funciones discriminantes inducidas, describiendo así las funciones de decisión. Gracias a la representación polinomial de las funciones discriminantes somos capaces de acotar el número de decisiones representables por clasificadores con redes Bayesianas. Extendemos estos resultados a clasificadores en cadena para problemas multi etiqueta, analizando su capacidad expresiva asumiendo que los modelos están basados en redes Bayesianas. Por último, describimos un método algebraico y geométrico para estudiar funciones discriminantes de clasificadores generativos bajo propiedades de Markov generales. El método empleado extiende los resultados obtenido en el caso de las redes Bayesianas y describe un marco formal, basado en diferencias finitas, para estudiar las funciones discriminantes de clasificadores generativos. ----------ABSTRACT---------- Machine learning, as one of the fundamental tools of artificial intelligence, has acquired growing importance in the last decades. The increasing availability of large amounts of data and more computational processing power available at a low price have contributed to the spread of machine learning methods in almost all branches of technology. While a great part of the current research focuses on the creation of new algorithms and methods to tackle different problems, it is widely recognized that formal analysis and theoretical results are necessary to really understand the algorithms employed, their limitations and their capabilities. The work developed in the present thesis is focused on this last aspect of the research in machine learning. We study Bayesian network classifiers and in general generative classifiers based on probabilistic graphical models. Probabilistic graphical models are widely studied in the statistic literature and in this thesis we analyze them in the context of one of the most basic problem in machine learning, binary classification. Our main result is a description of the implications, for the induced decision functions, of the conditional independence statements holding in the probability model. We will state results both for a wide class of Bayesian network classifiers and for undirected Markov network classifiers. In particular, we describe the classes of discrimination functions associated with some of the most used Bayesian network classifiers over categorical predictors variables. We obtain polynomials interpolating the induced discrimination functions, and thus representing the corresponding decision functions. Thanks to this characterization we are able to bound the number of decisions representable by Bayesian network classifiers with given structures. We extend the binary classification results to chain multi-label classifiers, analyzing their expressive power when Bayesian network are used as base models. Finally, we describe an algebraic and geometric approach to study discrimination functions of generative classifiers under general Markov properties. The given approach extends the results for Bayesian network classifiers and introduces an elegant framework, based on finite differences, to study discrimination functions of generative classifiers.