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.