Bayesian Non Parametric Machine Learning, a comprehensive approach

Abstract

Cuando se trata de clasificar cosas los seres humanos lo hacemos bastante bien. Somos capaces de discernir en segundos si un objeto está caliente o frio, si una acción es peligrosa o segura, etc. Es algo que hacemos a menudo y de forma muy eficiente. Sin embargo, hacer que los ordenadores sean capaces de realizar estas tareas siempre se ha antojado bastante complicado. Instruir a un ordenador para que, sin intervención humana, tome decisiones basándose en su conocimiento previo es uno de los grandes objetivos de los algoritmos de Machine Learning. Durante la segunda mitad del siglo XX, con el avance de la informática, se crearon nuevos algoritmos de clasificación para dar solución a los problemas comunes de la época. A grandes rasgos, podemos distinguir 2 tipos de problemas de clasificación: el aprendizaje supervisado, en el que tenemos pares entrada-salida del sistema y el aprendizaje no supervisado, en la que únicamente conocemos los datos de entrada. Cabe destacar que el aprendizaje no supervisado, comúnmente llamado clustering en los problemas de clasificación, suele ser más complejo que su contraparte supervisada. Esto se debe al desconocimiento, a priori, del número de agrupaciones o clases que existen en el sistema. Imaginemos un caso concreto, ¿Cuantos grupos podemos encontrar si deseamos clasificar gente en función de sus gustos musicales? Gente a la que le gusta el rock, el folk, el pop, gente a la que solo le gusta un determinado grupo musical, gente a la que le encanta la música de los 80, etc. Las combinaciones son infinitas. Por ello, uno de los parámetros que debemos de establecer normalmente en los algoritmos de clusterización más tradicionales es el número de clases que deseamos. Esto crea un problema adicional, como en el ejemplo anterior, en algunos casos no es posible conocer con anterioridad el número de elementos que compone un sistema. Es por ello que, durante el siglo XXI se ha estado trabajando en modelos y algoritmos que no necesitan conocer el número de agrupaciones de antemano. Estos modelos van a ir proponiendo diferentes soluciones, con una cantidad variable de clases. Las herramientas necesarias para poder emplear los modelos no parámetricos son complejas y difíciles de desentrañar a primera vista. Entre ellas, podemos encontrar: el proceso de Dirichlet (DP), el proceso del restaurante chino (CRP) y el muestreador de Gibbs (un tipo de muestreador basado en las cadenas de Markov). Es por ello que, durante este trabajo, realizaremos una introducción detallada de cada una de ellas, en las que explicaremos qué son y para que se van a utilizar. Posteriormente, las emplearemos conjuntamente para diseñar un algoritmo que nos permita proponer, de manera dinámica, un número de agrupaciones variable para ajustar nuestros datos. En lugar de determinar mediante el modelo el número de agrupaciones, dejaremos que sean los datos los que determinen la cantidad de ellas que mejor los explican. El objetivo no es obtener un número de agrupaciones determinado si no, más bien, una estimación de la función masa de probabilidad de su cantidad. La cual podremos marginalizar posteriormente para obtener un resultado en conjunto. Seguidamente, describiremos empleando UML y propondremos una implementación en Matlab® de este algoritmo tratando de sea lo más eficiente posible que finalmente pondremos en práctica con modelos de mezclas infinitas de gaussianas pero que podremos emplear con cualquier distribución de probabilidad de nuestros datos a través de una interfaz estandarizada. Por último, detallaremos algunos ejemplos para explicar el funcionamiento de este algoritmo.

When the task is classifying things, we, humans, do it fairly well. We can determine within seconds whether an object is hot or cold, if an action is dangerous or safe, etc. We do it very often and very efficiently. But, to instruct computers in doing these tasks has always been quite complex. To make a computer make decisions based upon its previous knowledge, without human intervention, is one of the main goals of Machine Learning algorithms. During the second half of the 20th century, as computers improved, new algorithms were developed to solve ordinary problems. At first sight, we can distinguish between 2 types of classification problems: supervised learning, in which input-output samples exist for our system and unsupervised learning, in which we only know the input data. Remark that, unsupervised learning, commonly called clustering for classification problems, is rather more complex than its supervised counterpart. This is due to the a priori uncertainty on the number of classes that compose the system. For example, how many groups can we find if we are classifying people according to its musical likes? There are people who like rock music, people who like pop music, people who only likes one artist, people devoted to the 80’s music, etc. The possible combinations are endless. For so, one of the parameters that we usually have to configure in the most traditional clusterization algorithms is the number of classes we are looking for. This creates an additional problem: as in the previous example, in some cases, it is not possible to know beforehand the number of elements that compose a system. Due to this limitation, during the 21st century, people have worked on models and algorithms that do not require to set the number of clusters. These models are going to propose iteratively different solutions, with a variable amount of groups. Tools required to make use of this non-parametric models are complex and difficult to work out at a glance. Among them, we can find: The Dirichlet process (DP), the Chinese restaurant process (CRP), and the Gibbs Sampler (a type of sampler based on Markov Chains). This is the reason why, during this work, we will make a detailed introduction on each of these tools, in which we will explain briefly what they are and how are we going to use them. Later on, we will use all of them to design an algorithm that will allow us to propose, dynamically, a variable number of clusters to fit our data. Instead of determining, throughout the model the number of classes, we will let the data define the amount of them that better fits it. The objective is not to obtain a given number of clusters but rather, to get an estimation of the probability mass function for this quantity. We could later marginalize it to obtain a joint result. Next, using UML we will describe and we will propose an implementation of this algorithm using Matlab®, trying to make it as efficient as possible. Finally, we will put it into practice with infinite Gaussians mixture models. Although, we can use it with every probability distribution for our data through a standardized interface. At last, but not least, we will detail some examples to explain how does the algorithm work.