DataScience & IA PDF

Christophe Rodrigues z DataScience & IA z Plan du cours ▪ Les débuts de l'IA ▪ Règles d'associations ▪ A* z z Début de l'IA ▪ Reflexion de Turing (1950) : Comment évaluer si un ordinateur ou programme a u...

Christophe Rodrigues z DataScience & IA z Plan du cours ▪ Les débuts de l'IA ▪ Règles d'associations ▪ A* z z Début de l'IA ▪ Reflexion de Turing (1950) : Comment évaluer si un ordinateur ou programme a un comportement intelligent? ▪ Il propose le fameux test de Turing z Eliza - Premier agent conversationnel ▪ Weizenbaum (1964) système à base règles (ou grammaire) ▪ Agent psychiatre z Plus récemment... ▪ L'agent conversationnel Tay développé par Microsoft (2016) ▪ L'agent était disponible en ligne sur tweeter et tout le monde pouvait intéragir avec l'IA. Cet agent était doté de mécanisme d'apprentissage et apprenait de ces intéractions avec les utilisateurs. ▪ Très vite ( 2^40000 patterns possibles ▪ (pour info, il y a approximativement un peu plus de 2^25 étoiles dans l'univers) z Apriori ▪ Parcours en largeur des régles d'associations ▪ Commence par les règles constituées d'un item ▪ Puis deux, trois,…, jusqu'à la taille de l'alphabet (tous les différents items) ▪ Mécanisme d'élagage exploitant la structure de l'espace de recherche ▪ Monotonicité : un sur-ensemble ne peut être plus fréquent qu'un ensemble z z Pour aller plus loin ▪ APriori était le première solution proposée pour la découverte de règles d'associations. ▪ Depuis, beaucoup d'autres méthodes et de variantes ont été proposés. ▪ Le framework libre SPMF propose actuellement plus de 169 méthodes et capable de traiter des transactions et des règles de différentes sortes: ▪ http://www.philippe-fournier-viger.com/spmf/ z z A* recherche d'un chemin - Pathfinding ▪ Problème: Comment trouver un chemin entre deux points parmis tous les chemins possibles z z A* ▪ Proposé par Hart, Nilsson et Raphael en 1968 ▪ Contexte : améliorer les déplacements du robot Shakey ▪ Contrainte : trouver une bonne solution le plus vite possible (non nécessairement la meilleure de toutes) z ▪ Méthode la plus utilisée pour trouver le plus court chemin: ▪ L'algorithme de Dijkstra (1959) va parcourir le graphe en largeur "en aveugle" et finir par trouver le plus court de tous les chemins entre le nœud de départ et le nœud d'arriver. ▪ A* va être guidé par une information supplémentaire (heuristique) afin de s'orienter dans le graphe. L'heuristique la plus commune est la distance au but à vol d'oiseau. Cela fonctionne très bien sur les cartes/graphes classiques mais pas toujours... z Évaluation de l'intérêt d'un noeud ▪ Fonction de coût f au noeud n est décomposée en deux parties: ▪ f(n) = g(n) + h(n) ▪ Avec g(n) le coût cumulé entre le noeud de départ et le noeud courant n : "le passé" ▪ Avec h(n) le coût estimé du noeud courant n au noeud de destination : "le futur estimé" z Condition pour l'optimalité ▪ Il est possible de garantir l'optimalité d'une heuristique pour un problème donné. ▪ Pour être optimale l'heuristique doit être: ▪ admissible ▪ monotone z Condition pour l'optimalité ▪ Admissibilité ▪ Une heuristique est admissible si elle ne surestime jamais le coût pour atteindre le but (optimiste). ▪ Monotonicité ▪ h(n) ≤ c(n,n') + h(n') ▪ Forme d'inégalité triangulaire ▪ Exemple: distance à vol d'oiseau  z Noeud de départ : Click to add text Arad Noeud d'arrivée : Bucharest z