Data Science & IA CMO5_CSP PDF

Christophe Rodrigues z DataScience & IA z Plan du cours ▪ IA et Deep Learning, une révolution? ▪ Rappels et relations entre les algorithmes déjà abordés ▪ Problèmes de satisfaction de contraintes (CSP)  z Turc mécaniqu...

Christophe Rodrigues z DataScience & IA z Plan du cours ▪ IA et Deep Learning, une révolution? ▪ Rappels et relations entre les algorithmes déjà abordés ▪ Problèmes de satisfaction de contraintes (CSP)  z Turc mécanique ▪ Automate capable de jouer aux échecs et de gagner contre des joueurs humains ▪ présenté pour la première fois en 1770. ▪ Superbe IA ▪ Superbe Escroquerie z  z Rappels et relations entre méthodes abordées ▪ Algorithmes évolutionnaires (ou génétiques) ▪ Découverte de règles d'association (pattern mining) ▪ A* ▪ Problèmes de satisfaction de contraintes  Problèmes z de satisfaction de contraintes CSP par l'exemple: 3 couleurs possibles, aucun voisin ne doit avoir la même z Définitions ▪ X un ensemble de variables : {X1,…,Xn} ▪ D un ensemble de domaines : {D1,…,Dn} (un pour chaque variable X) ▪ Avec Di = {v1,…,vn} pour Xi ▪ C un ensemble de contraintes spécifiant des combinaisons de valeurs. Chaque contrainte Ci est une paire: ▪ Avec porté un tuple de variables participant à la contrainte Ci ▪ Avec relation définissant les valeurs possibles de ces variables z Définitions ▪ Une relation peut être définie de deux façons, par extension et par intension: ▪ Exemple: soit les variables X1 et X2 ayant le même domaine {A,B}, la contrainte imposant qu'elles soient différentes devient alors: ▪ Par extension: ▪ Par intension: z Définitions ▪ Afin de résoudre un CSP, il est nécessaire d'affecter des valeurs aux variables en respectant les contraintes. ▪ Une affectation qui ne viole aucune contrainte est dite cohérente. ▪ Une affectation est dite complète si chaque variable est affectée. ▪ La solution d'un CSP est une affectation cohérente et complète. z Différents types de contraintes ▪ Contrainte Unaire : contrainte sur une seule variable ▪ Exemple : ▪ Contrainte Binaire : contrainte sur deux variables ▪ Exemple : SA ≠ NSW ▪ Contrainte Ternaire : ▪ Exemple : entre(X,Y, Z) ▪ Contrainte Globale (avec un nombre arbitraire de variables): ▪ Exemple: tousDifférents(SA, WA, NT, Q, NSW, V) z Retour à l'exemple (3 couleurs possibles) Click to add text Click to add text Click to add text X=?, D=? z Retour à l'exemple Click to add text Click to add text Click to add text X = {WA, NT, Q, NSW, V, SA, T} z Retour à l'exemple ≠ Click to add text Click to add text Click to add text X = {WA, NT, Q, NSW, V, SA, T} D = {rouge, vert, bleu} C = {SA ≠ WA, SA ≠ NT, SA ≠ Q, SA ≠ NSW, SA ≠ V, WA ≠ NT, NT ≠ Q, Q ≠ NSW, NSW ≠ V} z Pourquoi formuler un problème sous forme d'un CSP? ▪ 1) Répresentation naturelle/direct pour beaucoup de problèmes ▪ Exemple: le problème des 8 reines déjà abordé ▪ Pas besoin de développer une solution ad hoc, il suffit de formaliser les variables et contraintes et de demander au solveur de trouver une solution. ▪ 2) L'élagage du CSP peut le rendre plus puissant qu'une méthode cherchant dans l'espace d'états car il est possible d'éliminer rapidement de larges fractions de l'espace  z Exemple d'élagage par CSP ▪ Une fois {SA = bleu} fixé au sait qu'aucun des voisins ne peut prendre la couleur bleu. ▪ Sans prise en compte de cette information il y a: 3⁵ = 243 affectations possibles pour les 5 voisins de SA ▪ Avec prise en compte de cette information il n'y a plus que 2⁵=32 possibilités! ▪ SOIT UNE REDUCTION DE 87% DE L'ESPACE DE RECHERCHE  z Backtracking Search (parcours en profondeur) z Exemple de parcours par Backtrack z Heuristiques possibles ▪ L'ordre dans lequel les variables sont choisies influence la recherche: ▪ MRV : Minimum Remaining values : on privilégiera la variable avec le moins de valeurs possibles restantes ▪ Degré : on privilégiera la variable impliquée dans le plus de contraintes ▪ Valeurs moins contraintes : on choisira une valeur laissant plus de possibilités pour les variables suivantes z Forward Checking z Min-Conficts  z Exemple du nombre d'itérations par méthode Backtracking Forward Checking Min Conflicts 100-reines 40 000 000 40 000 000 4 000 états USA 1 000 000 2 000 64