Remerciez-le!

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

Mondher Bouden Maître assistant Semestre 5 2017 FONDEMENTS DE L’INTELLIGENCE AR

Mondher Bouden Maître assistant Semestre 5 2017 FONDEMENTS DE L’INTELLIGENCE ARTIFICIELLE LICENCE FONDAMENTALE EN SCIENCES DE L'INFORMATIQUE (LFSI3) FONDEMENTS DE L’INTELLIGENCE ARTIFICIELLELICENCE FONDAMENTALE EN SCIENCES DE L'INFORMATIQUE (LFSI3) Apprentissage Automatique Introduction • L’apprentissage automatique étudie les méthodes permettant à un agent de construire de nouvelle connaissances à partir de son expérience. Nous pouvons distinguer trois classes générales de problème d’apprentissage selon les types d’informations dont dispose l’agent : – Apprentissage supervisé. – Apprentissage non-supervisé. – Apprentissage par renforcement. 2 Apprentissage supervisé • Objectif: – Apprendre à classer des instances à partir d’un ensemble d’exemples qui sont étiquetés par leurs classes (par un expert humain). • Apprendre une fonction f à partir d’un ensemble d’exemples de paires (x, f(x)). • Exemple: – La reconnaissance visuelle des chiffres : On présente à l’agent un ensemble de chiffres manuscrits (étiquetté par les nombres qu’ils représentent) et il doit apprendre à identifier les différents chiffres. • Algorithmes utilisés: – Réseaux de neurones, – Arbres de décision, etc. 3 Apprentissage non supervisé • L’inconvénient majeur de l’apprentissage supervisé est que les données doivent être étiquetées. • Cependant, dans le monde réel, les données ne le sont généralement pas, donc l’étiquetage doit se faire à la main, ce qui requiert un temps considérable de la part d’un expert humain. • En apprentissage non supervisé, nous ne recevons que les données brutes, et l’objectif est de trouver des points communs de ces données. 4 Apprentissage non supervisé • Les applications possibles de l’apprentissage non supervisé sont très nombreuses car aujourd’hui nous disposons de plus en plus de données et la difficulté est d’analyser ces données et d’en extraire les informations intéressantes. • On peut par exemple utiliser l’apprentissage non supervisé dans la séismologie pour trouver les zones à risque pour les tremblements de terre ou bien dans le marketing pour analyser les comportements des consommateurs. • Algorithmes utilisés: – Kmoyennes – La méthode des sommes pondérées de gaussiennes, etc. 5 Apprentissage par renforcement • L’agent dans ce cas doit apprendre à bien agir dans son environnement afin de maximiser sa récompense. • À chaque instant, l’agent peut percevoir (complètement ou partiellement) son environnement et choisit ensuite une action à exécuter. • Après chaque action, il reçoit une récompense (qui peut être positif, négatif, ou zéro). • À partir de ce feedback et de ses perceptions, l’agent doit apprendre un comportement qui l’amène à obtenir le plus de récompense possible. 6 Apprentissage par renforcement • Exemples: – Apprendre à jouer aux échecs (la récompense serait de 0 si le jeu n’est pas fini ou si c’est un match nul, +1 si l’agent gagne, et −1 pour une perte). – Apprendre à un robot à se déplacer plus vite (ici nous pourrions donner une récompense positive chaque fois le robot couvre une certaine distance). • L’apprentissage par renforcement a été utilisé avec succès sur de nombreux problèmes et en particulier pour apprendre aux robots des mouvements physiques complexes. • Algorithme utilisé: – Algorithmes de différence temporelle, etc. • Programme Td-Gammon (qui joue au backgammon) 7 Apprentissage Automatique • Ces trois types d’apprentissage sont complémentaires, et le choix de la bonne méthode d’apprentissage dépend du problème en question. • Si nous voulons faire apprendre à un agent une tâche spécifique dont nous pouvons fournir des exemples, l’apprentissage supervisé serait un bon choix. • S’il s’agit d’apprendre un comportement compliqué, l’apprentissage par renforcement serait probablement plus approprié. • Si nous n’avons pas d’objectif clair, nous choisirons l’apprentissage non-supervisé pour découvrir des régularités dans un ensemble de données. 8 Méthode des arbres de décision • Nous allons introduire la méthode des arbres de décision qui est l’un des algorithmes les plus populaires pour l’apprentissage supervisé. • Cette méthode consiste en la construction d’un arbre de décision à partir d’un ensemble d’exemples. • Cet arbre est ensuite utilisé pour classer de nouvelles instances. – L’avantage principal de cette approche est sa simplicité : – Les arbres de décision sont facilement interprétables par des humains, ce qui n’est pas le cas par exemple pour les réseaux de neurones. 9 Méthode des arbres de décision • Commençons d’abord par une définition plus formelle de l’apprentissage supervisé. • En entrée, nous recevons un multi-ensemble1 d’exemples: – E  A1x ...xAn x C qui sont décrits par un certain nombre d’attributs A1, ...,An, C, dont le dernier est l’attribut cible. – Chaque attribut A a un domaine dom(A) de valeurs possibles. 10 1Un multi-ensemble est semblable à un ensemble, sauf que des éléments peuvent apparaître plusieurs fois. {a, b, a} serait donc un exemple d’un multi-ensemble qui n’est pas un ensemble. Méthode des arbres de décision • En général, les domaines pourraient avoir une infinité de valeurs, mais pour simplifier, nous ne considérons que les attributs avec les domaines finis. • En sortie, nous devrons fournir une fonction: – f : A1x...xAn C – Qui dit comment classer tous les éléments de A1 x ... x An. • Bien entendu, certaines fonctions sont plus satisfaisantes que d’autres. Idéalement, nous aimerions trouver la fonction f qui donne la bonne réponse pour toutes les éléments de A1 x ... x An. 11 Méthode des arbres de décision • Considérons maintenant un exemple concret. Dans cet exemple, nous cherchons à détecter si un mail est un spam ou non. Nous disposons des données suivantes : 12 Méthode des arbres de décision Ici nous avons quatre attributs: • Auteur – Si l’auteur du mail est connu ou non. On peut considéré un auteur comme connu s’il a été par exemple le destinataire d’un mail de la messagerie ou si l’adresse de l’auteur se trouve dans le carnet d’adresses. • MotClés – Si le message contient l’un d’un ensemble de mots associé aux spams. 13 Méthode des arbres de décision Ici nous avons quatre attributs: • HTML – Si le mail contient un lien html • Majuscule – Si le message contient des mots en majuscules ou non. • Plus l’attribut cible Spam. • Les domaines des attributs sont : – dom(Auteur)= {connu, inconnu} – dom(MotClés)= {oui, non}, – dom(HTML)= {oui, non}, – dom(Majuscule)={oui, non} – dom(Spam)= {oui, non}. 14 Méthode des arbres de décision • Cette figure montre un arbre de décision qui permet de bien classer les données dans notre exemple. • Comme dans tous les arbres de décision: – Les nœuds non-terminaux sont étiquetés par des attributs (non-cibles). – Les arcs sont étiquetés par une valeur dans le domaine de l’attribut associé au nœud parent. – Chaque feuille de l’arbre prend une valeur dans le domaine de l’attribut cible. 15 Méthode des arbres de décision • Un arbre de décision définit la valeur de l’attribut cible pour chaque instance possible. • Pour trouver la valeur d’une instance spécifique, il suffit de parcourir l’arbre en choisissant l’arc qui correspond à l’instance en question jusqu’à arriver à une feuille dont l’étiquette donne la classe de l’instance. 16 Méthode des arbres de décision Exemple: • L’instance (inconnu, non, oui, oui). • Nous commençons à la racine qui correspond à l’attribut Auteur. • Comme notre instance prend la valeur inconnu pour l’attribut Auteur, nous suivons l’arc droit. Puis comme le prochain attribut est Majuscule et notre instance a la valeur non pour Majuscule, nous prenons l’arc gauche. • Nous sommes maintenant à un nœud qui correspond à l’attribut HTML, donc nous choisissons l’arc droit (dont la valeur est oui) et nous trouvons une feuille marquée oui. L’instance (inconnu, non, oui, oui) est donc classée comme un mail spam par notre arbre de décision. 17 Méthode des arbres de décision • À chaque ensemble d’exemples correspond plusieurs arbres de décisions. • Comment donc savoir si un certain arbre de décision est un bon choix pour un ensemble de données ? • Un premier critère est le taux de couverture de l’arbre. – i.e. le pourcentage des exemples qui sont bien classés par l’arbre. • L’importance de ce critère devrait être évident car les exemples dont nous disposons sont nos seules informations sur la fonction à apprendre. • Nous voulons donc que notre arbre capte les informations dans ces exemples. 18 Méthode des arbres de décision • Considérons maintenant l’arbre de décision suivant qui semble être un peu plus compliqué que le premier. Cet arbre a exactement le même taux de couverture (100%) que le premier. 19 Méthode des arbres de décision • Nous avons tendance à dire que ce deuxième arbre est moins satisfaisant que le premier. Ceci laisse à croire que ce n’est pas que le taux de couverture qui compte mais aussi la simplicité de l’arbre (qui peut être mesuré par le nombre de nœuds non-terminaux). 20 Méthode des arbres de décision • On préfère les arbres simples car: – Il sont beaucoup plus faciles à comprendre, ce qui n’est pas négligeable vu que l’interprétabilité des arbres de décision est l’un des avantages principaux de cette approche. – Les arbres simples avec des taux de couverture raisonnables donnent souvent de meilleurs résultats sur des instances nouvelles que les arbres complexes qui couvrent uploads/Management/ apprentissage-automatique.pdf