Improving Binary Classifier Performance Through an Informed Sampling Approach and Imputation

Au cours des deux dernières décennies, des progrès importants dans le domaine de l'apprentissage automatique ont été réalisés grâce à des techniques d'échantillonnage. Relevons par exemple le renforcement (boosting), une technique qui assigne des poids aux observations pour améliorer l'entraînement du modèle, ainsi que la technique d'apprentissage actif qui utilise des données non étiquetées partielles pour décider dynamiquement quels cas sont les plus pertinents à demander à un oracle d'étiqueter. Cette thèse s'inscrit dans ces recherches et présente une nouvelle technique d'échantillonnage qui utilise l'entropie des données pour guider l'échantillonnage, un processus que nous appelons l'échantillonnage informé. L'idée centrale est que la fiabilité de l'estimation des paramètres d'un modèle peut dépendre de l'entropie des variables. Donc, l'adaptation du taux d'échantillonnage de variables basée sur leur entropie peut conduire à de meilleures estimations des paramètres. Dans une série d'articles, nous étudions cette hypothèse pour trois modèles de classification, notamment Régression Logistique (LR), le modèle bayes naïf (NB) et le modèle d'arbre bayes naif (TAN—Tree Augmented Naive Bayes), en prenant une tâche de classification binaire avec une fonction d'erreur 0-1. Les résultats démontrent que l'échantillonnage d'entropie élevée (taux d'échantillonnage plus élevé pour les variables d'entropie élevée) améliore systématiquement les performances de prédiction du classificateur TAN. Toutefois, pour les classificateurs NB et LR, les résultats ne sont pas concluants. Des améliorations sont obtenues pour seulement la moitié des 11 ensembles de données utilisées et souvent les améliorations proviennent de l'échantillonnage à entropie élevée, rarement de l'échantillonnage à entropie faible. Cette première expérience est reproduite dans une deuxième étude, cette fois en utilisant un contexte plus réaliste où l'entropie des variables est inconnue à priori, mais plutôt estimée avec des données initiales et où l'échantillonnage est ajusté à la volée avec les nouvelles estimation de l'entropie. Les résultats démontrent qu'avec l'utilisation d'un ensemble de données initial de 1% du nombre total des exemplaires, qui variait de quelques centaines à environ 1000, les gains obtenus de l'étude précédente persistent pour le modèle TAN avec une amélioration moyenne de 13% dans la réduction l'erreur quadratique. Pour la même taille des semences, des améliorations ont également été obtenues pour le classificateur naïf bayésien par un facteur de 8% de l'entropie faible au lieu d'échantillonnage d'entropie élevée. L'échantillonnage informé implique nécessairement des valeurs manquantes, et de nombreux classificateurs nécessitent soit l'imputation des valeurs manquantes, ou peuvent être améliorés par imputation. Par conséquent, l'imputation et l'échantillonnage informatif sont susceptibles d'être combinés dans la pratique. La question évidente est de savoir si les gains obtenus de chacun sont additifs ou s'ils se rapportent d'une manière plus complexe. Nous étudions dans un premier temps comment les méthodes d'imputation affectent la performance des classificateurs puis si la combinaison de techniques d'imputation avec l'échantillonnage informé apporte des gains qui se cumulent. Le gain de méthodes d'imputation sont d'abord étudiés isolément avec une analyse comparative de la performance de certains nouveaux algorithmes et d'autres algorithmes d'imputation bien connus avec l'objectif de déterminer dans quelle mesure le motif des améliorations est stable dans les classificateurs pour la classification binaire. Ici encore, les résultats montrent que les améliorations obtenues par des techniques d'imputation peuvent varier considérablement par modèle et aussi par taux de valeur manquante. Nous étudions également les améliorations le long d'une autre dimension qui est de savoir si le taux d'échantillonnage par enregistrement est stable ou varie. Des différences mineures, mais statistiquement significatives sont observées dans les résultats, montrant que cette dimension peut également affecter les performances du classificateur. Dans une dernière étude, nous étudions empiriquement si les gains obtenus de l'échantillonnage informé et de l'imputation sont additifs, ou s'ils se combinent d'une manière plus complexe. Les résultats montrent que les gains individuels de l'échantillonnage informé et d'imputation sont du même ordre de grandeur, mais en général, ils ne sont pas une simple somme des améliorations individuelles. Il faut noter aussi que, malgré les résultats encourageants pour certaines combinaisons d'échantillonnage informées et des algorithmes d'imputation, une analyse détaillée des résultats de l'ensemble de données individuelles révèle que ces combinaisons apportent rarement des performances supérieures aux algorithmes d'imputation ou à l'échantillonnage informé individuellement. Les résultats de nos études fournissent une démonstration de l'efficacité de l'échantillonnage informé pour améliorer les performances de classification binaire pour le modèle TAN, mais les résultats sont plus mitigés pour NB et LR. En outre, l'échantillonnage à entropie élevée se révèle être le régime le plus bénéfique.

Abstract

In the last two decades or so, some of the substantial advances in machine learning relate to sampling techniques. For example, boosting uses weighted sampling to improve model training, and active learning uses unlabeled data gathered so far to decide what are the most relevant data points to ask an oracle to label. This thesis introduces a novel sampling technique that uses features entropy to guide the sampling, a process we call informed sampling. The central idea is that the reliability of model parameter learning may be more sensitive to variables that have low, or high entropy. Therefore, adapting the sampling rate of variables based on their entropy may lead to better parameter estimates. In a series of papers, we first test this hypothesis for three classifier models, Logistic regression (LR), Naive Bayes (NB), and Tree Augmented Naive Bayes (TAN), and over a binary classification task with a 0-1 loss function. The results show that the high-entropy sampling (higher sampling rate for high entropy variables) systematically improves the prediction performance of the TAN classifier. However, for the NB and LR classifiers, the picture is more blurry. Improvements are obtained for only half of the 11 datasets used, and often the improvements come from high-entropy sampling, seldom from low-entropy sampling. This first experiment is replicated in a second study, this time using a more realistic context where the entropy of variables is unknown a priori, but instead is estimated with seed data and adjusted on the fly. Results showed that using a seed dataset of 1% of the total number of instances, which ranged from a few hundreds to around 1000, the improvements obtained from the former study hold for TAN with an average improvement of 13% in RMSE reduction. For the same seed size improvements were also obtained for the Naive Bayes classifier by a factor of 8% from low instead of high entropy sampling. Also, the pattern of improvements for LR was almost the same as obtained from the former study. Notwithstanding that classifier improvements can be obtained through informed sampling, but that the pattern of improvements varies across the informed sampling approach and the classifier model, we further investigate how the imputation methods affect this pattern. This question is of high importance because informed sampling necessarily implies missing values, and many classifiers either require the imputation of missing values, or can be improved by imputation. Therefore imputation and informative sampling are likely to be combined in practice. The obvious question is whether the gains obtained from each are additive or if they relate in a more complex manner. The gain from imputation methods are first studied in isolation with a comparative analysis of the performance of some new and some well known imputation algorithms, with the objective of determining to which extent the pattern of improvements is stable across classifiers for the binary classification and 0-1 loss function. Here too, results show that patterns of improvement of imputation algorithms can vary substantially per model and also per missing value rate. We also investigate the improvements along a different dimension which is whether the rate of sampling per record is stable or varies. Minor, but statistically significant differences are observed in the results, showing that this dimension can also affect classifier performance. In a final paper, first the levels of improvement from informed sampling are compared with those from a number of imputation techniques. Next, we empirically investigate whether the gains obtained from sampling and imputation are additive, or they combine in a more complex manner. The results show that the individual gains from informed sampling and imputation are within the same range and that combining high-entropy informed sampling with imputation brings significant gains to the classifiers' performance, but generally, not as a simple sum of the individual improvements. It is also noteworthy that despite the encouraging results for some combinations of informed sampling and imputation algorithms, detailed analysis of individual dataset results reveals that these combinations rarely bring classification performance above the top imputation algorithms or informed sampling by themselves. The results of our studies provide evidence of the effectiveness of informed sampling to improve the binary classification performance of the TAN model. Also, high-entropy sampling is shown to be the most preferable scheme to be conducted. This for example, in the context of Computerized Adaptive Testing, can be translated to favoring the highly uncertain questions (items of average difficulty). Variable number of items administered is another factor that should be taken into account when imputation is involved.