Introduction à la Science des Données et l'IA

Introduction à la Science des Données et l'IA

• Christophe Rodrigues est le conférencier.
• Le cours traite de la science des données et de l'intelligence artificielle (IA).

Plan du cours

• IA et apprentissage profond, une révolution ?
• Rappels et relations entre les algorithmes déjà étudiés,
• Problèmes de satisfaction de contraintes (CSP).

Le 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.
• Représenté comme un exemple d'IA avancée à l'époque, mais finalement une supercherie.

Apprentissage profond (Deep Learning)

• Le succès des techniques d'apprentissage profond est attribuable à la conjonction de grands ensembles de données, d'un matériel informatique évolutif et d'un logiciel de haut niveau.
• Les données de haute qualité sont essentielles.
• Des logiciels spécifiques sont nécessaires : théano, CUDA, TensorFlow.
• Le matériel informatique doit être puissant.
• Les abstractions de haut niveau dans les données sont modelées à travers multiples transformations non linéaires.

Rappels et relations entre les méthodes abordées

• Algorithmes évolutionnaires (génétiques)
• Découverte des règles d'association (pattern mining)
• Méthode A*
• Problèmes de satisfaction de contraintes (CSP).

Exemple de Satisfaction de contraintes (CSP)

• Problème de 3 couleurs : il est impossible que 2 régions adjacents aient la même couleur.
• L'Australie est représentée sur un graphe.
• Chaque région doit avoir l'une des 3 couleurs.
• Aucune région voisine ne peut avoir la même couleur.

Définitions

• X : ensemble des variables (exemple X1, ..., Xn)
• D : ensemble des domaines (ex: D1, ..., Dn)(un par chaque variable X)
• Di : {v1, ..., vn} pour chaque variable Xi
• C : ensemble de contraintes : spécifie des combinaisons de valeurs. Chaque contrainte Ci est une paire : < porté, relation >
• porté : tuple de variables participant à la contrainte Ci
• relation : définit les valeurs possibles de ces variables.

Types de relations :

• Par extension
• Par intension

Définition de la résolution de CSP

• Affecter des valeurs aux variables en respectant les contraintes.
• Une affectation cohérente ne viole aucune contrainte.
• Une affectation complète impliquer que chaque variable est affectée.
• La solution est une affectation cohérente et complète.

Différents types de contraintes

• Contraintes unaire (Exemple: SA ≠ vert)
• Contraintes binaire (Exemple: SA ≠ NSW)
• Contraintes ternaire (Exemple: entre(X, Y, Z))
• Contraintes globales (Exemple: tousDifférents(SA, WA, NT, Q, NSW, V))

Retour à l'exemple (3 couleurs)

• X = {WA, NT, Q, NSW, V, SA, T}
• D = {rouge, vert, bleu}
• C : ensemble de contraintes (SA ≠ WA, SA ≠ NT, etc.)

Pourquoi formuler un problème sous forme de CSP ?

• Représentation naturelle pour de nombreux problèmes.
• Simplicité de la formulation des variables et contraintes.
• Élagage puissant pour réduire l'espace de recherche.

Exemple d'élagage par CSP

• Fixer une valeur pour une variable réduit l'espace de recherche.
• Réduction de l'espace de recherche de 87%.

Recherche par Retour en arrière (Backtracking)

• Algorithme qui explore l'espace des solutions en profondeur.
• Fonction BACKTRACKING-SEARCH : retourne une solution ou indique une échec.
• Fonction BACKTRACK: prend l'affectation et le CSP en entrée.

Heuristiques possibles lors de la recherche

• Minimum Restant de valeurs (MRV): choix de la variable avec le moins de valeurs possibles.
• Degré : choix de la variable impliquée dans le plus de contraintes
• Valeurs moins contraintes: un choix qui laisse plus d'options pour les variables suivantes.

Vérification en avant (Forward Checking)

• Fonction qui affecte une valeur à une variable afin de limiter les valeurs possibles des variables suivantes.

Minimiser les conflits

• Algorithme qui sélectionne une variable conflictuelle, teste les valeurs possibles et choisit celle qui minimise les conflits avec les autres variables.
• Fonction MIN-CONFLICTS : retourne une solution ou une indication de l'échec.
• Le nombre de pas est le nombre maximum d'étapes autorisées avant de renoncer.

Exemple du nombre d'itérations par méthode (CSP)

• Pour le problème des 100-reines, comparaison de la performance des différentes méthodes.