Column Generation in Machine Learning

Cette thèse explore l’intégration de la recherche opérationnelle et de l’apprentissage automatique, mettant l’accent sur l’augmentation de la précision et de la praticalité au sein des cadres d’apprentissage automatique (ML) grâce à l’intégration stratégique d’algorithmes de génération de colonnes. Malgré l’ubiquité des algorithmes ML dans les applications de reconnaissance de motifs, leur manque d’interprétabilité et leur dépendance aux heuristiques introduisent de l’imprécision, soulignant ainsi la nécessité de méthodologies plus affinées. Les objectifs de la recherche sont doubles : d’abord, examiner l’application de classificateurs basés sur la génération de colonnes dans le domaine du ML, et ensuite, résoudre les défis pragmatiques entravant l’intégration fluide de ces classificateurs dans des scénarios réels. L’exploration englobe le développement d’algorithmes de génération de colonnes pour des applications pratiques, l’amélioration des algorithmes heuristiques pour l’apprentissage d’arbres de classification, et le développement d’un cadre logiciel facilitant la mise en œuvre efficace de modèles ML basés sur la génération de colonnes. Nous présentons une revue exhaustive de la littérature (Chapitre 2) qui recense divers classificateurs basés sur la génération de colonnes en apprentissage automatique et propose des observations communes à ce domaine. Notre première contribution (Chapitre 3) étend l’application de la méthode de génération de colonnes pour générer des règles de décision booléennes à des situations du monde réel pour classer les NOTAM, abordant spécifiquement les défis posés par la classification multiclasse à travers la classification un-contre-tous. Nous introduisons une heuristique exploitant un solveur CP-SAT pour accélérer la génération de colonnes, ainsi qu’une méthode pour réduire l’espace de recherche dans le sous-problème. Dans notre contribution suivante (Chapitre 4), l’accent se déplace vers l’amélioration des heuristiques basées sur la génération de colonnes pour l’apprentissage d’arbres de classification. Des modifications substantielles au modèle de sous-problème sont présentées pour réduire significativement le nombre de sous-problèmes dans des instances de classification multiclasse. Le chapitre démontre l’utilisation de contraintes dépendantes des données dans le problème maître en tant que plans coupants, introduisant un modèle de séparation pour identifier les violations de contraintes dans la solution de la relaxation linéaire. De plus, une routine de prétraitement et d’initialisation est décrite pour réduire la taille du problème maître et des sous-problèmes, réduisant ainsi les temps d’entraînement. Notre prochaine contribution (Chapitre 5) dévoile un cadre logiciel conçu pour simplifier la conception et la mise en œuvre de modèles ML basés sur la génération de colonnes. Le cadre vise à fournir une implémentation efficace, flexible, bien documentée et en open source des composants communs utilisés dans divers classificateurs basés sur la génération de colonnes. Dans notre étude, nous découvrons un défi significatif au sein des classificateurs basés sur la génération de colonnes, comme discuté dans les Chapitres 3 et 4: une part substantielle du processus d’entraînement est consacrée à la résolution de sous-problèmes, ce qui entraîne un goulot d’étranglement dans l’efficacité globale. Ces sous-problèmes, composés de MIPs qui diffèrent principalement dans leur fonction objectif entre les itérations des génération de colonnes, sont résolus à partir de zéro. Cependant, dans le Chapitre 6, nous proposons des techniques innovantes pour exploiter les similarités inhérentes entre ces MIPs. Notre approche implique la réutilisation d’informations essentielles obtenues à partir de la résolution d’instances précédentes, conduisant à des améliorations substantielles dans les instances ultérieures de la séquence. Notre approche de réutilisation d’informations pour résoudre des MIPs similaires en séquence est reconnue pour son excellence dans la compétition computationnelle de l’atelier MIP 2023.

Abstract

This thesis delves into the convergence of operations research and machine learning (ML), emphasizing the augmentation of precision and practicality within ML frameworks through the strategic integration of column generation (CG) methodologies. Despite the ubiquity of ML algorithms in pattern recognition applications, they lack interpretability, and their reliance on heuristics introduces imprecision, underscoring the need for more refined methodologies. The research objectives are two-fold: first, to investigate the application of CG-based clas-sifiers in the ML domain, and second, to address the pragmatic challenges hindering the seamless integration of these classifiers into real-world scenarios. The exploration involves extending CG methodologies to pragmatic applications, refining heuristic algorithms for learning classification trees, and developing a software framework facilitating the efficient implementation of CG-based ML models. We present a comprehensive literature review (Chapter 2) that serves as the foundational exploration of various CG-based classifiers in ML, elucidating common observations in the field. Our first work (Chapter 3) extends the application of CG-based methods for generating boolean decision rules to real-world instances for classifying NOTAMs, specifically addressing challenges posed by multiclass classification through one-vs-rest classification. We introduce a heuristic leveraging a CP-SAT solver to expedite CG and a method to reduce the search space in the subproblem. In our next contribution (Chapter 4), the focus shifts to enhancing CG-based heuristics for learning classification trees. Substantial modifications to the subproblem model are presented to reduce the number of subproblems in multiclass classification instances significantly. The chapter demonstrates the use of data-dependent constraints in the master problem as cutting planes, introducing a separation model to identify violations of constraints in the LP relax-ation solution. Furthermore, a preprocessing and initialization routine is outlined to reduce the size of the master problem and subproblems, consequently reducing training times. Our next contribution (Chapter 5) unveils a software framework created to simplify the design and implementation of CG-based ML models. The framework aims to provide an efficient, flexible, well-documented, and open-sourced implementation of common components used in various CG-based classifiers. In our study, we uncover a significant challenge within CG-based classifiers, as discussed in Chapters 3 and 4: a substantial portion of the training process is devoted to resolving subproblems, leading to a bottleneck in the overall efficiency. These subproblems, consisting of MIPs that differ mainly in their objective function between CG iterations, are solved from scratch. However, in Chapter 6, we propose innovative techniques to exploit the inherent similarities among these MIPs. Our approach involves reusing essential information obtained from solving previous instances, leading to substantial improvements in later instances within the sequence. Our approach for reusing information to solve similar MIPs in sequence is recognized for its excellence in the computational competition of the MIP workshop 2023.