Méthodes combinatoires et modèles d'apprentissage

Méthodes combinatoires et

modèles d’apprentissage interprétables

Marie-José Huguet - Emmanuel Hébrard - Mohamed SialaJulien Ferry - Hao Hu

06/10/2021

Sommaire

1 Apprentissage supervisé

2 Optimisation Combinatoire

3 Focus 1 : Arbres de décision optimaux

4 Focus 2 : Apprentissage et équité

5 Conclusion

1 / 50

Sommaire





5 Conclusion

Apprentissage supervisé 2 / 50

Apprentissage supervisé

Principe

On dispose d’un ensemble de données annotées par une valeur ou une classe cible

Prédire la réponse pour la cible sur de nouvelles données après un processusd’entrainement et de test

Illustration

Données d’entrée : Images

Cible : classe de chaque image

Méthode d’apprentissage supervisé(entrainement et test)

Résultat : un modèle représentatif des donnéesd’entrée

Déploiement : exploitation de ce modèle sur denouvelles images pour prédire leur classe


Données

Jeux de DonnéesExemples utilisés pour l’entrainement et l’évaluation

Attributs (features) : caractéristiques numériques ou non associées à chaque exemple

Etiquettes (labels) : valeur ou classe cible associée à chaque exemple

Séparer les données

Ensemble d’entrainement (training set) : ensemble d’exemples utilisés pour la phased’entrainement

Ensemble de test (testing set) : ensemble d’exemples utilisés pour la phase d’évaluation

Ensemble de validation (validation set) : ensemble d’exemples (parfois) utilisés pendant laphase d’entrainement

Tous ces ensembles doivent être disjoints


Tâches d’apprentissage supervisé

ClassificationLes étiquettes (cibles) sont des valeurs discrètes

Classification binaire

Classification multi-classes

RégressionLes étiquettes (cibles) sont des valeurs continues : non considéré ici


Illustration

Jouer au tennis ?

Jeux de données tabulairesI Attributs : Ciel, Température,

Humidité, VentI Label : Jouer

EntrainementI modèle de classification binaireI données d’entrainement

TestI quelle classe pour (Soleil, 21.0,

95, Faible) ?I données de testI Capacité de généralisation du

modèle

Déployer le modèle sur denouvelles données


Performances d’un processus d’apprentissage

Qualité d’un apprentissage

Mesures : matrice de confusion

I Accuracy : TP+TNTP+TN+FP+FN

sous apprentissage : le modèle appris estéloigné des données

sur-apprentissage : le modèle se généralisemal sur les données de test

Validation croisée (k-cross validation) :I Partition du jeu de données en k sous

ensemblesI k − 1 pour l’entrainement ; 1 pour

l’évaluationI répéter pour toutes les permutations


Méthodes de classification supervisée

Nombreuses (depuis les années 80 ...) Composants d’optimisation

K plus proches voisins (k-NN)

méthodes de séparation linéaire ou non linéaire

réseaux de neurones (multi-couches, profonds)

règles de décision (arbre, liste, ensemble de décision)

méthodes d’ensemble (apprendre et combiner plusieurs modèles)

Enjeux (sélection)

Données massives : passage à l’échelle (réduction dimension, complexité algorithmes,calcul haute performance, infrastructures big data, coût)

Applications à fort impact sociétal : garanties théoriques (robustesse, certification),interprétabilité des décisions, biais dans les données et équité des décisions, respect de lavie privée, ...


Interprétabilité

Impacts des méthodes d’IA sur les individus

Applications sensibles pour les individus (justice, embauches, banque, médical,enseignement, ...)I Comprendre les décisions (accord / désaccord)I Comprendre le processus de décision

Interprétabilité : un élément clé pour IA de confiance

Processus de régulation / règlementation

Interprétabilité : capacité d’expliquer ou de présenter des décisions en termescompréhensibles pour un individu [Doshi-Velez and Kim, 2017]I proposer des modèles compréhensibles "par nature"I proposer des explications a posteriori

A décliner selon tâches, contextes, personnes ...


Modèles interprétables

Règles de décision

Familles de modèles considérés comme interprétables (avec taille limitée)I Arbres de décision (Decision Trees)I Listes de décision / de règles (Rule Lists)I Ensemble de décisions (Decision sets)

Illustration : Jeu de données Titanic

[Ignatiev 2021]


Interprétabilité

Compléments

Thématique ancienne en IA mais de nouveau foisonnante ...

Autres modèles interprétables non considérés ici

Débats : interprétabilité et performance des modèles; interprétabilité et explicabilité

Quelques référencesInterpretable Machine Learning: Fundamental Principles and 10 Grand Challenges. C. Rudin, C.Chen, Z. Chen, H. Huang, L. Semenova1, and C. Zhong, arXiv:2103.11251, 2021

Reasoning-Based Learning of Interpretable ML Models. A. Ignatiev , J. Marques-Silva, N.Narodytska and P. J. Stuckey, IJCAI 2021

Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and UseInterpretable Models Instead. C. Rudin, Nature Machine Intelligence, Vol 1, pp. 206-215, 2019

https://www.youtube.com/playlist?list=PLNeXFnYrCJnf7ZSBDRWbumv0uXuajPOBH


https://www.youtube.com/playlist?list=PLNeXFnYrCJnf7ZSBDRWbumv0uXuajPOBH

Sommaire





5 Conclusion

Optimisation Combinatoire 12 / 50

Problèmes d’optimisation combinatoire

FormalisationVariables : à valeurs discrètes

Contraintes : restreindre les combinaisons possibles de valeurs des variables

Objectif : optimiser une fonction des variables

But : trouver solution réalisable optimisant la fonction objectif

Caractéristiques

Ensemble fini de solutions maisexploration exhaustive irréalisable(temps de calcul)I Classes de complexité des problèmes

n sommets

(n−1)!2 solutions4 sommets : 3 solutions

10 sommets : 181440

25 sommets : 3.1023


Formalismes

Satisfiabilité Booléenne : SAT / MaxSat

Variables Booléennes ∈ {0, 1}Litéral : une variable ou sa négation (x , ¬x)Clause : une disjonction de litéraux C = (x1 ∨ ¬x2 ∨ x3)

Problème : une conjonction de clauses (C1 ∧ C2 . . .Cn)

SAT : existe-il une instanciation des variables telle que toutes les cluases sont satisfaites ?MaxSAT : version optimisation de SATI clauses strictes : doivent etre satisfaitesI clauses souples avec pondération : peuvent être satisfaitesI Maximiser la somme des poids des clauses souples satisfaites


Formalismes

Programmation Linéaire en Nombre Entiers - PLNE (ILP)

Variables : nombres entiers

Contraintes : combinaison linaire des variables

Objectif : combinaison linéaire des variables

Variante : variables 0-1

Variante : variablesmixtes (MILP)


Formalismes

Programmation par Contraintes - PPC (CP)

Variables : domaine finis (discrets)

Contraintes : quelconque

Objectif : oui / non

Graphe G = (X ,E), K > 0 couleurs

Variables : xi ∈ X : couleur prise par les sommets

Domaines : {1, . . .K} : couleurs possiblesContraintes : ∀(xi , xi ) ∈ E : xi 6= xj


Résolution de problèmes d’optimisation combinatoire

Principe

Explorer l’espace de recherche des solutionsI Obtenir une solution optimale (toutes, une solution réalisable, ...)I Taille de cet espace !

Défis des méthodes exactes :I Maitriser l’explosion combinatoire

Méthodes

Arbre de rechercheIngrédients :I DécompositionI Elagage : calcul de bornes, filtrageI Stratégies d’explorationI Apprentissage


Transition

ROC et Apprentissage

Combiner méthodes d’apprentissage et méthodes combinatoires → améliorer la résolutionde problèmes d’optimisation combinatoireI apprentissage supervisé, non supervisé, par renforcementI présentation Valentin Antuori

Proposer des méthodes combinatoires pour aborder certains enjeux dans la résolution deproblèmes d’apprentissage → améliorer la résolution de problèmes d’apprentissageI apprentissage superviséI présentations Julien Ferry, et la suite

Production scientifique importante de la communauté sur ces deux thématiques


Sommaire





5 Conclusion

Focus 1 : Arbres de décision optimaux 19 / 50

Principe

Attributs : {a, b, c, d} - Labels : e

n exemples, m attributs, 2k tests (k profondeur de l’arbre) : O(nm2k )Focus 1 : Arbres de décision optimaux 20 / 50

Approches

Types de méthodes

Heuristiques (CART, C4.5, ID3, ...) : déterminer un arbre "pertinent", limiter lataille/profondeur pour éviter le sur-apprentissageApproches MILP / MaxSat / CPI Arbres de taille/profondeur minimale classifiant tous les exemples (échantillonage) [Bessiere et

al. 2009], [Narodytska et al. 2018], [Avellaneda 2020],

I Arbres maximisant le nombre d’exemples bien classifiés avec contrainte taille/profondeur[Bertsimas and Shioda 2007], [Bertsimas and Dunn 2017], [Verwer and Zhiang 2019], [Hu et al.2020]

Algorithmes dédiésI Programmation dynamique (DL8) [Nijssen and Fromont 2007], (DL8.5) [Aglin et al 2020],I CP with AND/OR search [Verhaeghe et al. 2019],I Recherche arborescente en profondeur + principe séparation (DL8.5) [Demirovic, Hebrard, et.

al 2020]


Approche MaxSAT pour l’apprentissage d’arbres de décision

Article IJCAI 2020Stage M2 et Thèse Hao Hu - Mohamed Siala, Emmanuel Hébrard, MJH

Modèle SAT pour les arbres de décision

P(E ,N): Etant donné un ensemble d’exemples E , trouverun arbre binaire de décision pleina de taille N qui classifiecorrectement tous les exemples [Narodytska et al. 2018]

Difficultés en généralisation (sur-apprentissage)

Fixer le nombre de noeuds peut conduire à des arbresayant une profondeur élevée

atout noeud à 0 ou 2 fils



Contributions : Modèle MaxSAT pour les arbres de décision

P∗(E ,H): Etant donné un ensemble d’exemples E , trouver un arbre binaire de décisionplein qui maximise le nombre d’exemples bien classifiésI Taille N fixée : du modèle SAT au modèle MaxSATI Taille N fixée + Contrainte sur la profondeur d : modèle MaxSATI Contrainte sur la profondeur d → intervalle sur la taille : modèle MaxSAT

Contraintes Topologie Arbre de décision

Similaire au modèle SAT initial de la littératureI Contraintes sur la structure d’un arbre binaireI Contraintes pour associer les attributs aux noeuds internes et les classes aux feuilles

Contraintes strictes



Contraintes classification

Maximiser le nombre d’exemples positifs E+ et négatifs E− bien classifiés

Variable booléenne bq pour chaque exemple de E : bq = 1 iff eq est correctement classifié

Lier ces variables avec les contraintes du modèle SAT exprimant la classification de chaqueexemple (contraintes strictes) :

∀eq ∈ E+, bq → C+q ; ∀eq ∈ E−, bq → C−q

Définir toutes les variables bq comme des clauses souples (même poids)



Controler la profondeur/taille de l’arbre

Pour une profondeur d : le nombre de noeuds de l’arbre N ∈ [2d + 1, 2d − 1]

Chaque noeud i est à une seule profondeur

Si un noeud i est à une profondeur p, sesfils sont à une profondeur p + 1

Si la profondeur max est d , les noeuds à dsont des feuilles

Adapter les contraintes de topologie del’arbre et de classification pour considérerun nombre de noeuds variables (3, 5, ...)



Adaboost : apprentissage d’un ensemble d’arbres

Boosting : méthode séquentielle pour produire des arbres de décision en ajustant despondérations pour les exemples mal classifiés

Prédiction sur ensemble de test : combinaison des différentes prédictions de chaque arbre(vote pondéré)

Contribution : Intégration modèle MaxSAT dans Adaboost

intégration "directe" en pondérant les contraintes souples



Expérimentations

Comparaison modèle MaxSAT (DT-exact et DT-max), CART (heuristique) et DL8.5(méthode exacte)

Evaluer le taux de classification correcte avec profondeur identique d = {2, 3, 4} et mêmelimite en temps (15 minutes) et mémoire (16 Go)

Jeux de données : 15 issus de https://dtai.cs.kuleuven.be/CP4IM/datasets/

Validation croisée (5 folds), 10 graines aléatoires

Solver MaxSAT : Loandra


https://dtai.cs.kuleuven.be/CP4IM/datasets/


Résultats - Training accuracy

#s: nb exemples; #fb : nb attributs binaires; Opt : % optimalité; TO : time out; MO :memory out

Dataset #s/#fb d Training AccuracyDT(exact) DT(max) CART DL8.5

Acc Opt Time Acc Opt Time Acc Acc Time

australian 653/1242 87.00 12 866.79 87.00 12 883.78 86.68 87.01 0.063 87.83 0 TO 87.79 0 TO 86.88 89.00 6.964 88.44 0 TO 88.19 0 TO 89.04 MO MO

cancer 683/892 94.94 100 2.90 94.94 100 3.19 94.42 94.94 0.023 96.66 20 842.64 96.66 7 844.62 95.66 96.67 0.714 97.70 0 TO 97.39 0 TO 96.91 98.10 20.38

mushroom 8124/1122 96.90 100 89.89 96.90 100 132.94 92.71 96.90 0.093 99.73 0 TO 99.69 0 TO 96.55 99.90 4.944 100 100 354.33 99.99 96 388.80 99.92 100 28.65



Résultats - Testing accuracy

#s: nb exemples; #fb : nb attributs binaires; Opt : % optimalité; MO : memory out

Dataset #s / #fb d Testing AccuracyDT(ex) DT(max) CART DL8.5

australian 653/1242 84.72 84.89 86.59 84.813 84.92 85.31 84.99 85.334 85.00 85.31 85.44 MO

cancer 683/892 93.97 93.92 93.89 93.883 94.07 94.45 93.80 94.144 94.05 93.95 93.79 93.66

mushroom 8124/1122 96.90 96.90 92.71 96.903 99.97 99.66 96.53 99.904 100 99.98 99.90 100

Modèle MaxSAT : compétitif en prediction vs autres méthodes et moins de mémoire vsDL8.5



Résultats - Intégration avec AdaBoost

Comparaison MaxSat, Boosting (BS)

21 étapes d’apprentissage; sur échantillon de l’ensemble d’entrainement (0.8)

Extrait des résultats (15 jeux de données)

Dataset #s/#fb d Testing accuracy Training accuracyDT(max) BS DT(max) BS

australian 653/1242 87.12 87.20 86.56 89.983 87.88 87.54 87.33 89.664 87.88 87.88 88.48 90.21

car 1728/212 84.68 96.53 85.75 97.473 87.86 95.44 89.15 97.104 90.46 98.36 91.24 98.70

tic-tac-toe 958/272 68.91 77.14 70.98 80.393 74.61 94.69 76.86 95.964 76.74 94.49 81.31 95.80

Intérêt de l’intégration MaxSAT avec AdaBoost



BilanModèle MaxSAT pour maximiser l’accuracy tout en controlant la profondeur des arbres dedécision

Résultats compétitifs par rapport aux autres méthodes exactes

Intégration simple et efficace dans une méthode de type boostingLimitation pour des jeux de données de grande taille :I stratégie d’explorationI initialisation avec solution heuristique


Sommaire





5 Conclusion


Algorithme "any-time" pour les arbres de décision

Article (en cours) JMLR

Emmanuel Hébrard - Emir Demirovic et ...

Points de départ

Trouver un arbre binaire de décision maximisant le nombre d’exemples bien classifiés (etprodondeur/taille limitée)

Méthodes exactes (SAT, CP, MILP) : limites / passage à l’échelleMéthode exacte DL8.5 (programmation dynamique)I Séparation en sous arbres indépendantsI limites / occupation mémoire



Séparation en sous arbres (DL8.5)

Complexité : O(nmk) (vs O(nm2k ) arbres possibles)

Méthode très efficace / autres approches exactes

mais obtenir la première solution (premier arbre) est presque aussi couteux que résoudrel’ensemble du problème



Ingrédients : Branch and Bound et Programmation Dynamique

Combiner stratégie d’exploration, séparation des sous-arbres, évaluation de bornesI Première solution obtenue rapidement (similaire approche heuristique)I Ne pas re-explorer des sous arbres déjà connus (accuracy)

Anytime : à chaque pas de temps, retrourner le meilleur arbre

Complexité : identique à celle de DL8.5



Resultats



Resultats (max profondeur=10)



Synthèse

Amélioration significative de l’état de l’artI pour déterminer des arbres de décision optimauxI aussi performant que méthode heuristique pour obtenir le premier arbre

Arbres de décision optimaux obtenus : meilleur acuracy et/ou plus petit que les arbres dedécision heuristiques


Sommaire





5 Conclusion

Focus 2 : Apprentissage et équité 39 / 50

Liste de règles équitables

Article CIKM 2021et article arxiv 2019/2020 "Learning Fair Rule Lists"

Julien Ferry, Ulrich Aïvodji, Sébasten Gambs, Mohamed Siala, MJH

ContexteExistence de biais potentiellement discriminants dans les jeux de données

Proposer des modèles d’apprentissage ne reproduisant pas cette discrimination

Intégration de métriques d’équité dans le processus d’apprentissage



Métriques d’équité statistique

Principe : différents groupes d’individus ont la même valeur de mesureI Pas de différence de prédiction en fonction d’un groupe

En pratique : relaxation → différence d’au plus ε entre les groupesNombreuses métriques (s’appuyant sur matrice de confusion)I SP (statistical Parity) : même probabilité d’être prédit dans la classe postivive (Vrais et Faux

Positifs)I PP (Predictive Equality) : même taux de Faux PositifsI EOpp (Equal Opportunity) : même taux de Faux NégatifsI Travaux réalisés : prise en compte de 6 métriques



Liste de règles (Rule List - RL)

Premiers travaux [Rivest 1987]

Liste ordonnée "if-then"

RL : r = ({pk,k∈{1..K}}, {qk,k∈{1..K}}, q0)

I K règles : pk → qk avec pk antécédent et qk prédictionI prédiction par défaut q0



Méthode exacte pour Liste de règles

CORELS [Angelino 2018] : déterminer Liste de règles r minimisant misc(r , E) + λ.Kr

I misc(r , E) ∈ [0, 1] : erreur de classificationI Kr : taille de rI λ : paramètre de régularisation pour privilégier listes "courtes" et éviter sur-apprentissage

Branch and Bound :I exploration arbre des antécedents + bornes + structures de données efficaces + stratégies

d’exploration



Intégration métriques d’équité statistique

Extension bi-objectif via méthode ε-contrainteFairCORELS : déterminer r minimisant misc(r , E) + λ.Kr telle que unf(r , E) ≤ 1− εI unf() : mesure d’inéquité

Obtention de front de Pareto en faisant varier ε

Approche permettant de conserver la validité des calculs de bornes de CORELS

Extension via somme pondérée des objectifsI Minimiser (1− β) ∗ misc(r , E) + λ.Kr + β ∗ unf(r , E)I Obtention de Front de Pareto en faisant varier β

Les bornes de CORELS ne sont plus valides : relaxation



Expérimentations

Jeux de données :I Adult Income : 45 222 ; 69 antécédents; genre ; salaire ≥ 50KI COMPAS : 6167; 25 antécédents; origine ethnique ; récidivismeI Default Credit : 30 000 ; 90 antécédents; genre ; défaut de paiementI Bank Marketing : 45211; 179 antécédents; age ; souscription emprunt

Pré-processing : ensemble de règles capturant un seuil donné d’exemples

Cross validation : 5

λ = 10−3; 147 valeurs ε ; Taille maximale arbre de recherche : 25.105

Stratégie d’exploration en largeur + ordonné par fonction objectif



Résultats - Entrainement - Mesure d’équité = SP

Adult Income dataset

Default of Credit Card dataset

COMPAS dataset

Bank Marketing dataset



Résultats - Test - Mesure d’équité = SP

Adult Income dataset

Default of Credit Card dataset

COMPAS dataset

Bank Marketing dataset



RésultatsFronts de Pareto similaires sur autres métriques

Existence de compromis intéressants entre accuracy et équité

Comparaison autres approches

C-LR [Zafar 2019] - modèle interprétable

LAFTR [Madras 2018] - modèle boite noire

Résultats similaires sur autres jeuxde données et métriques

FairCORELS meilleur vs C-LR;compétitif vs LAFTR



Code en open source

GitHub : https://github.com/ferryjul/fairCORELS

Package Python : https://pypi.org/project/faircorels/

notebook de démonstration

BilanMéthode exacte pour obtenir des modèles interprétables offrant des compromis accuracyet équitéI Equité respectée sur l’ensemble d’entrainement mais pas en généralisation

Amélioration de l’efficacité de l’exploration de l’arbre de recherche :I Elagage/Guidage via des modèles PPC ou PLNE


https://github.com/ferryjul/fairCORELS

https://pypi.org/project/faircorels/

Conclusion

Autres présentations

Julien Ferry - Méthode heuristique pour le problème de généralisation de l’équité

Autres travaux (non présentés)

Towards Formal Fairness in Machine Learning - CP 2020I A. Ignatiev, M. C. Cooper, M. Siala, E. Hebrard and J. Marques-SilvaI Modèle équitable = non sensible à la valeur des attributs protégés

Conclusion 50 / 50

Documents

Méthodes combinatoires et modèles d'apprentissage