Bayesian nonparametrics for crowdsourcing

Supervised machine learning relies on a labeled training set, whose size is closely related to the achievable performance of any learning algorithm. Thanks to the progresses in ubiquitous computing, networks, and data acquisition and storage technologies, the availability of data is no longer a problem. Nowadays, we can easily gather massive unlabeled datasets in a short period of time. Traditionally, the labeling was performed by a small set of experts so as to control the quality and the consistency of the annotations. When dealing with large datasets this approach is no longer feasible and the labeling process becomes the bottleneck. Crowdsourcing has been proven to be an effective and efficient tool to annotate large datasets. By distributing the labeling process across a potentially unlimited pool of annotators, it allows building large labeled datasets in a short period of time at a low cost. However, this comes at the expenses of a variable quality of the annotations, i.e. we need to deal with a large set of annotators of possibly unknown and variable expertise. In this new setting, methods to combine the annotations to produce reliable estimates of the ground truth are necessary. In this thesis, we tackle the problem of aggregating the information coming from a set of different annotators in a multi-class classification setting. We assume that no information about the expertise of the annotators or the ground truth of the instances is available. In particular, we focus on the potential advantages of using Bayesian Nonparametric models to build interpretable solutions for crowdsourcing applications. Bayesian Nonparametric models are Bayesian models which set a prior probability on an infinite-dimensional parameter space. After seeing a finite training sample, the posterior probability ends up using a finite number of parameters. Therefore, the complexity of the model depends on the training set and we can infer it from the data, avoiding the use of expensive model selection algorithms. We focus our efforts on two specific problems. Firstly, we claim that considering the existence of clusters of annotators in this aggregation step can improve the overall performance of the system. This is especially important in early stages of crowdsourcing implementations, when the number of annotations is low. At this stage there is not enough information to accurately estimate the bias introduced by each annotator separately, so we have to resort to models that consider the statistical links among them. In addition, finding these clusters is interesting in itself, as knowing the behavior of the pool of annotators allows implementing efficient active learning strategies. Based on this, we propose in two new fully unsupervised models based on a Chinese Restaurant Process prior and a hierarchical structure that allows inferring these groups jointly with the ground truth and the properties of the annotators. The second problem is modeling inconsistent annotators. The performance of the annotators can be in-homogeneous across the instance space due to several factors like his past experience with similar cases. To capture this behavior, we proposed an algorithm that uses a Dirichlet Process Mixture model to divide the instance space in different areas across which the annotators are consistent. The algorithm allows us to infer the characteristics of each annotator in each of the identified areas, the ground truth of the training set, as well as building a classifier for test examples. In addition, it offers an interpretable solution allowing to better understanding the decision process undertaken by the annotators, and implement schemes to improve the overall performance of the system. We propose efficient approximate inference algorithms based on Markov Chain Monte Carlo sampling and variational inference, using auxiliary variables to deal with non-conjugacies when needed. Finally, we perform experiments, both on synthetic and real databases, to show the advantages of our models over state-of-the-art algorithms.Todo aprendizaje máquina supervisado descansa sobre un conjunto de entrenamiento etiquetado cuyo tamaño muestral está directamente relacionado con el rendimiento final del algoritmo. Gracias a los avances en computación ubicua, redes y tecnologías de adquisición y almacenamiento de datos, la disponibilidad de datos con que entrenar estos algoritmos ha dejado de ser un problema. Actualmente, podemos fácilmente reunir enormes conjuntos de datos no etiquetados en cortos periodos de tiempo. Tradicionalmente, el etiquetado de estos datos, era realizado por un pequeño conjunto de expertos a fin de controlar la calidad final y la consistencia de las anotaciones. Cuando nos enfrentamos a grandes conjuntos de datos, esta forma de proceder deja de ser factible, convirtiéndose el etiquetado en un cuello de botella. Crowdsourcing ha probado ser una herramienta efectiva y eficiente para anotar grandes conjuntos de datos en aprendizaje máquina. Mediante la distribución del proceso de etiquetado a un, potencialmente ilimitado, conjunto de anotadores, permite construir grandes conjuntos de datos etiquetados en un corto periodo de tiempo y a un bajo coste. Sin embargo, todo esto tiene como precio una pérdida sobre el control de la calidad de las anotaciones. Nos enfrentamos ahora a un gran conjunto de anotadores cuya experiencia es variable y desconocida. En este nuevo escenario, métodos de combinación de las anotaciones para dar lugar a estimaciones fiables de la etiqueta verdadera son necesarios. En esta tesis, abordamos el problema de agregar la información procedente de diferentes anotadores en un problema de clasificación multi-clase. Asumimos que no existe información disponible acerca de la experiencia de los anotadores o la etiqueta verdadera de las muestras. En concreto, nos centramos en las ventajas potenciales de usar modelos bayesianos no paramétricos para construir soluciones interpretables para aplicaciones de crowdsourcing. Los modelos bayesianos no paramétricos son modelos Bayesianos que definen una probabilidad a priori sobre un espacio de parámetros con infinitas dimensiones. Tras observar una muestra de entrenamiento finita, la probabilidad a posteriori termina usando un número finito de parámetros. Por tanto, la complejidad del modelo depende del conjunto de entrenamiento usado que es inferida a partir de los datos, evitando el uso de costosos algoritmos para selección de modelos. Nos centramos en dos problemas específicos. En primer lugar, defendemos que tener en cuenta la existencia de grupos de anotadores en la etapa de agregación, puede mejorar el rendimiento global del sistema. Esto es especialmente importante en fases tempranas de la implementación del sistema de crowdsourcing, cuando el número de anotaciones en bajo. En esta fase no hay suficiente información para estimar con precisión el sesgo introducido por cada anotador por separado, por lo que tenemos que recurrir a modelos que tengan en cuenta las dependencias estadísticas entre los distintos anotadores. Además, encontrar estos grupos de anotadores es un problema interesante por sí mismo, pues el conocer el comportamiento de nuestros anotadores nos permite implementar estrategias eficientes de aprendizaje activo. Basándonos en esta hipótesis, proponemos dos nuevos modelos no supervisados haciendo uso de un prior Chinese Restaurant Process y una estructura jerárquica que nos permite inferir los grupos de anotadores así como sus propiedades y las etiquetas verdaderas. El segundo problema es el modelado de anotadores inconsistentes. El rendimiento de los anotadores puede ser no homogéneo en el espacio muestral debido a diferentes factores tales como sus experiencias pasadas con casos similares. Para capturar este comportamiento, proponemos un algoritmo que usa un modelo Dirichlet Process Mixture con el objetivo de dividir el espacio muestral en diferentes áreas en las cuales los anotadores son consistentes. El algoritmo nos permite inferir las características de cada anotador en cada una de las áreas identificadas, las etiquetas verdaderas de nuestras muestras de entrenamiento, así como construir un clasificador para futuras muestras. Además, ofrece una solución interpretable permitiendo una mejor comprensión del proceso de decisión adoptado por los anotadores, así como implementar estrategias para mejorar el rendimiento global del sistema. Proponemos algoritmos de inferencia aproximada eficientes basados en muestreo Markov Chain Monte Carlo e inferencia variacional, usando variables auxiliares para lidiar con modelos de observación no conjugados cuando así se requiera. Finalmente, realizamos experimentos con bases de datos sintéticas y reales a fin de mostrar las ventajas de nuestros modelos con respecto al estado del arte.This work was partially supported by the "Formación de Profesorado Universitario" fellowship from the Spanish Ministry of Education (FPU AP2009-1513).Programa Oficial de Doctorado en Multimedia y ComunicacionesPresidente: Joaquín Míguez Arenas.- Secretario: Alberto Suárez González.- Vocal: Finale Doshi-Vele