Apprentissage et Optimisation Combinatoire

L’équipe s’est intéressée à l’apprentissage automatique au travers des possibles relations et synergies avec l’optimisation combinatoire. Parmi celles-ci, une piste classique est l’apprentissage d’heuristiques d’exploration de l’arbre de recherche. Nous avons obtenu des résultats prometteurs en utilisant des modèles simples, appris par renforcement et en utilisant ces modèles dans le cadre de recherche arborescente de Monte-Carlo pour divers problèmes industriels. Nous avons également obtenu des résultats en utilisant des modèles plus complexes, tels que les réseaux neuronaux graphiques sur des problèmes industriels complexes, e.g., avec de nombreuses contraintes et niveaux de décision, et impliquant un aspect stochastique A contrario, l’optimisation combinatoire peut être un outil précieux pour l’apprentissage automatique, en particulier pour la synthèse de modèles d’apprentissage supervisé intrinsèquement interprétables tels que des modèles d’arbres de décision ou de règles de décision. Nous avons contribué à ce domaine selon plusieurs axes : Nous avons proposé deux algorithmes exacts pour le calcul d’arbres de décisions, Murtree et Blossom, tous deux disponibles en sources ouvertes, qui ont significativement amélioré l’état de l’art. Nous avons amélioré et généralisé les méthodes reposant sur la satisfiabilité booléenne et en particulier sur l’exploitation de solveurs MaxSAT pour les arbres et les diagrammes de décision. Et finalement, nous avons étudié l’hybridation de ces modèles interprétables avec des modèles complexes de type boîte noire. D’autre part, le corpus de modèles et méthodes issus de la RO et de la PPC nous ont permis de prendre en compte deux aspects importants dans le contexte de l’IA Responsable : Le premier de ces aspects est l’équité des modèles d’apprentissage. Nous avons proposé des méthodes pour la construction de modèles dépourvus de biais (selon certains critères statistiques connus), et en particulier une méthode pour éviter l'écueil connu dans ce domaine d’un gain en équité qui décroît ou disparaît sur les données inédites. Nous avons également montré qu’aucun critère d’équité ne peut respecter un ensemble d’axiomes simples, s’il ne se résume pas à ignorer les attributs sensibles. Le deuxième aspect concerne les enjeux de vie privée en apprentissage supervisé. Nous avons proposé des modèles d’attaque utilisant la programmation par contraintes pour reconstruire des jeux de données produits par différents modèles interprétables, et nous avons étudié comment évaluer la qualité des reconstructions de jeux de données produites par divers modèles interprétables.Nous avons aussi montré les tensions entre ces deux aspects, en particulier en montrant comment les informations sur l'équité des modèles peuvent être exploitées par un adversaire pour améliorer sa reconstruction des attributs sensibles des données d'apprentissage

---