Ensembles of Quantifiers

Abstract

Durante los últimos años hemos asistido a un crecimiento exponencial de los datos disponibles. Una consecuencia en la comunidad del aprendizaje automático ha sido identificar nuevas tareas, como son los problemas que requieren obtener estimaciones agregadas para conjuntos de ejemplos, en lugar de realizar predicciones individuales para cada uno de ellos. La motivación detrás de esta idea es que, a medida que los volúmenes de datos crecen, es menos importante centrarse en los individuos, que en cómo esos individuos se comportan colectivamente. El objetivo, por ejemplo, puede ser dar respuesta a preguntas como ¿Cuántos clientes están satisfechos con nuestro nuevo producto? La cuantificación es una de esas nuevas tareas de aprendizaje que necesitan producir predicciones agregadas. Su objetivo es estimar el número de casos que pertenecen a cada clase, es decir, predecir la distribución de las clases en el conjunto. El aspecto clave es que los datos usados para entrenar los cuantificadores pueden tener una distribución substancialmente diferente respecto a las muestras de test. El método más intuitivo para cuantificar es simplemente clasificar y contar los ejemplos que pertenecen a cada clase. Sin embargo, la literatura prueba que este enfoque puede ser mejorado. El concepto de cambio en la distribución es crucial para entender los principios de la cuantificación y las propuestas de esta tesis. Un cambio en la distribución de los datos ocurre cuando la probabilidad conjunta de la descripción de los ejemplos y sus salidas varía entre entrenamiento y test, PT(x,y) ≠ PD(x,y). Dependiendo del problema, es posible especificar de antemano que componentes de P(x,y) cambian y cuales pueden ser constantes. En cuantificación, la distribución de las clases, P(y), cambia por definición, y se asume que P(x|y) es constante. Nuestra hipótesis principal es que existe una conexión entre los problemas con cambios en la distribución y las propiedades de los ensembles, como es la diversidad, que ayuda a obtener mejores meta-modelos. La diversidad se puede introducir generando una muestra de entrenamiento distinta para cada modelo. Este punto conecta la cuantificación con los ensembles. Siguiendo esa idea, analizamos como hipótesis que los ensembles pueden ser apropiados en problemas que (i) tienen cambios en la distribución y (ii) esos cambios se pueden caracterizar. La principal propuesta de esta tesis está basada en generar diferentes muestras de entrenamiento, cada una de ellas representando un cambio esperado en la distribución. Cuando una nueva muestra debe ser cuantificada, es probable que el meta-modelo contenga algún modelo que haya sido entrenado con una distribución de clases similar. En primer lugar nos centramos en la cuantificación binaria, proponiendo los llamados EoQ (Ensembles of Quantifiers) y nuestros experimentos demuestran que los EoQ tienen más precisión que cuantificadores individuales, incluso cuando las estrategias de combinación usadas son triviales. Además, la tesis propone medidas de selección diseñadas para cuantificación. La idea es seleccionar los mejores modelos del ensemble en lugar de agregar todos ellos. Por ejemplo, para dar más importancia a los modelos cuya distribución de entrenamiento se parece más a la de la muestra a predecir. Se introducen tres nuevas medidas de selección y dos de ellas permiten realizar una selección dinámica. Los experimentos prueban que estas estrategias de selección superan en muchos casos a las estrategias tradicionales, como promediar las salidas de todos los modelos o seleccionarlos de acuerdo a su precisión. Por último, se aplicaron los EoQ, junto con las medidas de selección propuestas, a un problema real, la cuantificación de sentimientos, en el que se estima la distribución de comentarios como positivos, neutrales y negativos. Se emplearon las cuatro últimas competiciones de SemEval y los EoQ resultaron tan efectivos como en otros problemas, combinando alta precisión y estabilidad. RESUMEN (en inglés) During the last years we are assisting to an exponential growth of data availability. One of the consequences within the machine learning community is the identification of a new useful learning task: to produce aggregated estimations for a full sample rather than giving a specific prediction for each instance. The motivation behind this is that, as the data volume increases, the less important is to focus on individuals, but on how these individuals behave together as a group. The goal is to answer questions like “How many consumers are satisfied with our new product?” Quantification learning is one of the prototypical methods based on giving sample level predictions. Its objective is to accurately estimate the number of cases belonging to each class (or class distribution) in a test set, using a training set that may have a substantially different distribution. At a first sight, the most intuitive way to quantification is to count the predictions of a classifier over a test set. This method has already been proved to perform poorly, since it does not considerate distribution changes. The concept of distribution shift is crucial to understand both quantification learning and our proposals in this thesis. Distribution shift occurs when the joint distribution of inputs and outputs changes between the training and testing phase, PT(x,y) ≠ PD(x,y). Depending on each concrete problem, it is possible to specify in advance which components in P(x,y) are expected to change, and which ones may remain constant. As for quantification, class distribution, P(y), changes by problem definition, and it is assumed that P(x|y) remains constant. We have realized that these distribution shift characteristics are closely related to some properties of ensemble learning; diversity is one of such key factors contributing to a good performing ensemble. Usually, diversity is introduced by generating different training samples for each model. This connects distribution shift problems and ensemble learning: each model can be trained with a different data distribution. Following this idea, this work analyzes the hypothesis that ensembles may be especially appropriate in problems that: (i) suffer from distribution changes, (ii) it is possible to characterize those changes beforehand. Our main proposal is based on generating different training samples, with each one representing an expected distribution change. When a new test set is to be quantified, the ensemble is likely to contain some models trained with a similar class distribution. We have focused on binary quantification, and proposed EoQ (Ensembles of Quantifiers). Experimental results show that EoQ outperform the original counterpart algorithms, even when trivial aggregation rules are used. Our next contribution is to improve EoQ by designing ensemble selection measures particularly devised for quantification. The idea is to select some potentially good ensemble models instead of aggregating all of them. For example, it would be possible to give more importance to those weak quantifiers whose training distribution is closer to the test sample distribution. We have proposed three quantification based selection measures and two of them are defined for dynamic ensemble selection. The experiments demonstrate that, in many cases, these selection functions outperform straightforward approaches, like averaging all models and using quantification accuracy to prune the ensemble. The last contribution of this thesis is to evaluate the effectiveness of EoQ, together with the proposed selection measures, in a real-world application. We have studied the usage of a decomposition approach based on EoQ for a multi-class sentiment quantification task, where each comment is labeled as positive, negative or neutral. The last four SemEval competitions have been used as benchmarks, and we have found that ensembles behave as good as in other learning problems, combining robustness, stability and a competitive performance.