Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Intelligence Artificielle NFP106 Année 2012-2013 http://deptinfo.cnam.fr Appren

Intelligence Artificielle NFP106 Année 2012-2013 http://deptinfo.cnam.fr Apprentissage ! F.-Y. Villemin ! 2! © F.-Y. Villemin 2012! Plan ! Apprentissage ! Induction ! Règles d'inférence inductive ! Apprentissage de concepts ! Espace de versions ! Arbres de décision ! ID3 ! Analogie 3! © F.-Y. Villemin 2012! Apprentissage Trois grandes approches d’apprentissage (Luger) ! Symbolique : Logique, Réseaux Bayésiens*, Chaînes cachées de Markov*, Processus de décision de Markov* ! Connexionniste* : réseaux de neurones ! Génétique* : algorithmes génétiques, programmation génétique Il peut y avoir d’autres classification (Russel & Norvig) Trois grands modes d’apprentissage (Luger) ! Supervisé : Par un humain Par trace d’explication* ! Non supervisé* ! Par renforcement* : Signal venant de l’environnement * Non traité dans le cours 4! © F.-Y. Villemin 2012! Apprentissage Deux grandes catégories d’apprentissage : ! Par induction ! Par analogie Apprentissage symbolique supervisé : ! Induction de concept simple ! Espace de versions ! ID3 (arbres de décision) ! Apprentissage par explication* ! Apprentissage par démonstration*… Apprentissage par renforcement (R. Sutton & A. Barto "Reinforcement Learning: An introduction" MIT Press, 1998) : ! Apprendre une stratégie pour maximiser une valeur numérique (récompense) ! Formalisé par les processus de décision de Markov 5! © F.-Y. Villemin 2012! Apprentissage Logique : (1) |= P! (2) |= P ! Q! (3) |= Q Déduction : (1) + (2) " (3) " modus ponens Abduction : (3) + (2) " (1) " diagnostic Induction : (1) + (3) " (2) " apprentissage 6! © F.-Y. Villemin 2012! Concepts Concept # représentation mentale abstraite qui nous permet de catégoriser des objets de l'environnement ! Abstrait : ne représente pas d'objet spécifique concret ! Unité fondamentale de la connaissance, joue un rôle central dans la cognition Catégorie # regroupement concret d'objets représentant le concept Un concept permet de catégoriser Apprentissage d'un concept C à partir d'exemples (# instances xi du concept) : Apprentissage! H ! C! hypothèse !x1, …,xn! échantillon d’apprentissage X 7! © F.-Y. Villemin 2012! Induction Processus de dérivation de sentences plus générales à partir de sentences établies pour certains cas spécifiques, par application d'un ensemble de règles d'inférence inductive ! Théorie du domaine Th! ! Ensemble F = {f1, f2, …, fn} de faits à généraliser $ généralisations consistantes G ! !Th |≠ f (f % F) faits non redondants ! !Th |≠ G conclusion inconnue ! !Th & F |≠ G consistance ! !Th & {G} |= f (f % F) généralisation $!Condition Th & F |= G en général pas satisfaite #!généralisations G pas nécessairement vraies dans tous les modèles de Th & F! 8! © F.-Y. Villemin 2012! Règles d'inférence inductive Acquisition de concept : A partir de sentences de la forme F : "p ! S" "l'élément caractérisé par p est une instance du concept décrit par S" obtenir une sentence (généralisée) de la forme G : "P ! S" "tout élément caractérisé par P est une instance du concept décrit par S" Pour généraliser F en G, faut inférer des assertions généralisées P vérifiant "p ! P" Symbole |< pour annoter les règles d'inférence qui non nécessairement adéquates P(x/a), P(x/b), P(x/c)…! |<————————————————————————— généralisation standard (1) 'x p(x)! 9! © F.-Y. Villemin 2012! Règles d'inférence inductive !! P ( Q ! S! |<——————————————— ! restriction de conjonction (2) P ! S! P ! S! |<——————————————— extension de disjonction (3) ! P ) Q ! S! ! P (a) ! S! |<—————————— remplacement de constantes par des variables (4) !!P (a/x) ! S! !P (x,…, x,…) ! S |<——————————————— ajout de variables (5) !P (x,…, y,…) ! S 10! © F.-Y. Villemin 2012! Règles d'inférence inductive P1 ! S, P1 ! P2! |<——————————————— affaiblissement d’impliquants (6) !!!P2 ! S (6)!Variante de (2) !!P(x) ( x%{a1,…, an}! S! |<———————————————————— extension des domaines de variables (7) P(x) ( x%{a1,…, an, an+1} ! S Variantes pour domaines linéaires (8), pour domaine à structure d'arbre!(9) P (x/a) ! S, P (x/b) ! S, a<b ! S! |<————————————————————————— fermeture d’intervalles! (8) P(x) ( x% [a, b] ! S P(v1)! S, P(v2) ! S, v1 isa v, v2 isa v! |<————————————————————————— montée d’un arbre (9) ! !P(v) ! S !! 11! © F.-Y. Villemin 2012! Apprentissage de concepts Exemple classique (Patrick Winston, 1975) ! Apprentissage (supervisé) de concepts dans un monde de blocs ! On souhaite apprendre le concept d'"arche" à partir d'exemples et contre-exemples ! Le programme ajoute à la base des concepts celui d'"arche" ! L'ordre des exemples déterminé par le professeur 12! © F.-Y. Villemin 2012! Exemples d'arches : Un “near-miss” diffère d'un exemple par une seule différence importante Quelques "near misses" : Apprentissage de concepts 13! © F.-Y. Villemin 2012! L'arche A et sa description structurelle : Apprentissage de concepts B! C! D ! A C D Bloc Bloc est-composé-de est-un B est-sur Bloc à-gauche-de ¬ au-contact est-un à-droite-de est-composé-de est-composé-de 14! © F.-Y. Villemin 2012! L'arche E et sa description structurelle : Apprentissage de concepts Bloc F ! G! H ! E G H Bloc est-composé-de est-un F est-sur à-gauche-de ¬ au-contact est-un à-droite-de est-composé-de est-composé-de Pyramide 15! © F.-Y. Villemin 2012! Heuristiques utilisées par P. Winston : ! Arc obligatoire ! Arc interdit ! Arc supprimé ! Montée d’un arbre ! Extension des domaines de variables ! Fermeture d’intervalles! Apprentissage de concepts 16! © F.-Y. Villemin 2012! Apprentissage de concepts Algorithme ARCH de P. Winston (1975) : e % Exemple /* 1er exemple positif*/! H:= *; généraliser(H, e); /* Hypothèse H */! !Pour chaque e % Exemple! Si e = "contre-exemple" alors spécialiser(H, e);! Si e = "exemple" alors généraliser(H, e);! ! Procédure généraliser(H, e)! Comparer Exemple e Hypothèse H;! Pour chaque d différence entre e et H :! Si e a un lien sur des classes différentes alors! Si les classes font partie de la taxinomie alors utiliser l'heuristique "montée d’un arbre";! If les classes forment ensemble exhaustif alors utiliser l'heuristique "lien supprimé";! !sinon alors utiliser l'heuristique "extension des domaines de variables";! Si e a un lien manquant dans H alors utiliser l'heuristique "lien supprimé";! Si e a des valeurs différentes numériques alors utiliser l'heuristique "fermeture d'intervalles"; !! ! Procédure spécialiser(H, e)! !Comparer Exemple e Hypothèse H;! !Trouver d différence unique la "plus importante" entre e et H;! Si d n'est pas identifiable alors ignorer e;! Si e a un lien manquant dans H alors utiliser l'heuristique "lien interdit"; ! Si H a un lien manquant dans e alors utiliser l'heuristique "lien obligatoire";! 17! © F.-Y. Villemin 2012! Concept d'arche appris : Apprentissage de concepts Bloc Arche Y Z Bloc est-composé-de est-un X est-sur à-gauche-de ¬ au-contact est-un à-droite-de est-composé-de est-composé-de Bloc ) Pyramide 18! © F.-Y. Villemin 2012! Espace de versions Un espace de versions, du à T. Mitchell (1978) (versions space) est l'ensemble des généralisations et spécialisations des exemples # l’ensemble de concepts consistants avec les exemples Les algorithmes d’apprentissage de type "espace de versions" consistent à réduire l’ensemble des versions au fur et à mesure que des exemples sont fournis Trois types d’algorithmes : ! Du spécifique au général ! Du général au spécifique ! Dans les deux sens : élimination de candidats 19! © F.-Y. Villemin 2012! Espace de versions Caractéristiques des algorithmes "espace de versions" : ! Langage de représentation des concepts ! Entrées : " Exemples (instances) positifs d’un concept " Exemples (instances) négatifs d’un concept " Opérations de généralisation " Opérations de spécialisation ! Principe : " Recherche heuristique incrémentale dans l’espace de versions du concept qui généralise le mieux les exemples ! Sortie : " Définition du concept qui englobe tous les exemples positifs et exclut tous les exemples négatifs 20! © F.-Y. Villemin 2012! Espace de versions Un problème de cartes : Le but de ce problème est d’apprendre un concept C de main dans un jeu de carte (poker, annonces au bridge...) à partir d’un ensemble d’ exemples E et de contre-exemples N de ce concept Chaque concept de main est caractérisé par un certain nombre de cartes (5 au poker, 13 au bridge...) Un espace de versions pour un exemple est un treillis dont le maximum est le concept indéfini "ANY" est le minimum est l’exemple et les nœuds intermédiaire sont des concepts plus généraux que ceux qui leur sont inférieurs dans le treillis et moins généraux que ceux qui leur sont supérieurs dans le treillis 21! © F.-Y. Villemin 2012! Espace de versions Le langage utilisé pour décrire les concepts est : ! n pour "noir" (avec p pour "pique" et t pour "trèfle") ! r pour "rouge" (avec c pour cœur et d pour "carreau") ! f pour une figure (avec a pour "as", k pour "roi", q pour "dame", v pour "valet") ! # pour un nombre (2 à 10) D’autre part Ø désigne "rien" Une carte est représentée par une paire (valeur, couleur) avec : ! "valeur" : # soit un nombre # soit # # soit une figure (a, k, q, v) # soit f # soit Ø ! "couleur" : # soit c # soit uploads/Philosophie/ apprentissage-12.pdf