Partie1 Introduction générale.pdf

Machine learning (Apprentissage Artificiel) 3ème Année Filière Informatique 1 Cours_ML Chiraz JELASSI  SOMMAIRE Introduction au ML Chapitre 1: Les concepts de base du ML 1- Définitions 2-...

Machine learning (Apprentissage Artificiel) 3ème Année Filière Informatique 1 Cours_ML Chiraz JELASSI  SOMMAIRE Introduction au ML Chapitre 1: Les concepts de base du ML 1- Définitions 2- Architecture Chapitre 2: Les algorithmes du ML 1- Types d’apprentissage 1-1 Apprentissage supervisé 1-2 Apprentissage non supervisé 1-3 Apprentissage par renforcement 2- Données d’apprentissage 3-Espace des hypothèses d’apprentissage 4- Evaluation de l’apprentissage Chapitre 3: Prédiction de valeurs numériques avec régression 1- Prédiction par régression 2- Régression Linéaire Chapitre 4: Classification 1- Séparateurs à Vastes Marges SVM 2- Classification avec K-nearest neighbors 3- Arbre de décision Chapitre 5: Apprentissage non supervisé: Clustering: 1- Introduction et distances 2-K-moyennes (K-means) 3- Les réseaux de neurones 2 Cours_ML Chiraz JELASSI  Introduction: Métier de data scientist Lorsqu'on aborde la révolution du Big Data, la prédiction des comportements ou tout simplement la transformation numérique des entreprises, deux termes essentiels émergents : la science des données (ou data science en français) et l'apprentissage automatique (ou machine learning). Le métier de data scientist se généralise grâce à: l'explosion de la quantité de données l'amélioration des algorithmes de machine learning  l'augmentation de la puissance de calcul des ordinateurs Afin de déterminer si la science des données peut apporter de la valeur pour résoudre un problème donné, deux éléments essentiels sont requis : des données et une problématique clairement définie. 3 Cours_ML Chiraz JELASSI  Le cycle de travail du data scientist Données explorées Données Traitement brutes de Données collectées données nettoyées Modèles Et algorithmes Déploiement communiquer En des rapports Prise de Production de visualisation décision Du modèle 4 Cours_ML Chiraz JELASSI  Emplacement du Machine learning Statistique Reconnaissance des formes (Pattern recognition) Deep learning Fouille de données Intelligence (Data Mining) Artificielle Machine Base de learning données 5 Cours_ML Chiraz JELASSI  Machine learning Expérience Tâche Performance Données d’entrée Tâche Performance (DataSet)  Prédiction des prix  prix précis  Prix des maisons  catégorisation des images  images correctement  Images  Segmentation des clients stockées  transactions des clients  optimiser les flux d'utilisateurs  groupement cohérent  données de parcours  relevés d'indicateurs (KPI du cite web) Un programme informatique apprend de l'expérience E en ce qui concerne une tâche T et une mesure de performance P si sa performance sur T, mesurée par P, s'améliore avec E. Tom Mitchell-1998 6 Cours_ML Chiraz JELASSI  QUIZ Supposons que votre programme de messagerie électronique surveille les courriels que vous faites et détecte si les emails sont des Spam ou nom On veut déterminer la tâche T, la performance P et l’expérience E  Classifier les Emails Spam ou non  Avoir un DataSet de données labélisées en Spam et non Spam  Nombre des Emails correctement classés 7 Cours_ML Chiraz JELASSI  Machine learning: (quand ?) L’expertise humaine n’existe pas Les humains sont incapables d'expliquer leur expertise Le robot Curiosity sur la planète Mars Reconnaissance vocale Les solutions changent dans le temps Les solutions doivent être adaptées à des cas particuliers Routage d’un réseau Utilisation Biométrique 8 Cours_ML Chiraz JELASSI  Les données (Data) Ensemble de faits qui permet d'aboutir à une conclusion Données structurées Données semi- structurées Données non structurées 9 Cours_ML Chiraz JELASSI  Features (Caractéristiques)? Les données brutes sont souvent inexploitables. Dans la plupart des cas, il faut procéder à un prétraitement des données afin d’extraire les caractéristiques des données pertinentes pour la prise de décision autrement appelées caractéristiques (features).ou attributs. Les caractéristiques sont des éléments ou des dimensions de votre ensemble de données Exemple 10 Cours_ML Chiraz JELASSI  Modèle ? Une représentation mathématique des relations dans un ensemble de données peut être réalisée à l'aide de différentes techniques, telles que les graphiques, les matrices ou les modèles statistiques. Ces représentations permettent de capturer les liens et les dépendances entre les données, facilitant ainsi l'analyse et la compréhension des relations présentes dans l'ensemble de données. 11 Cours_ML Chiraz JELASSI  Modèle ? (suite) On peut voir le modèle comme une fonction notée f qui prend un échantillon en entrée, et qui renvoie une décision. Le machine learning (ou apprentissage automatique) est la création du modèle statistique associé aux données. Modélisez les données à l'aide du machine learning ? "Modéliser" représenter le comportement d'un phénomène afin de pouvoir aider à la résolution d'un problème concret. 12 Cours_ML Chiraz JELASSI  Modèle ? (suite) La modélisation consiste à définir trois espaces: Espace d'entrée  Quelles sont les informations pertinentes ?  Variables Espace de sortie  Que cherche-t-on à prédire ? Espace des hypothèses  Entrées –(calcul) Sorties  Quel (genre de) calcul? Dépend de la méthode d'apprentissage utilisée ! Régression linéaire : espace = ax + b Régression polynomiale nombre de paramètres = degré du polynôme Réseaux de neurones, SVM, Algo Gen, … … 13 Cours_ML Chiraz JELASSI  Modèle ? (suite) Exemple On veut prédire le prix du loyer d’une maison à partir du surface Voici des données récupérées à partir d’un site de location: Loyer mensuel (en €) surface (en m2) 1500 32 2120 65 2500 60 ….. ….. 14 Cours_ML Chiraz JELASSI  Modèle ? (suite) Exemple (suite) Loyer mensuel en fonction de la surface Augmentation relativement linéaire du loyer par rapport à la surface 15 Cours_ML Chiraz JELASSI  Modèle ? (suite) Exemple (suite) La modélisation du nuage de points est représenté par La droite de régression Notre modèle est représenté par La droite, auquel nous pouvons ajouter l'intervalle de confiance dans laquelle peut se trouver la droite 16 Cours_ML Chiraz JELASSI  Architecture du ML 17 Cours_ML Chiraz JELASSI  Architecture du ML (suite) Espace des données d’apprentissage: La définition de l’espace des données d’apprentissage suppose: 1- Une représentation des objets de l’apprentissage, 2- Le prétraitement des données 1. Représentation des objets d’apprentissage: nature des attributs:  Homogènes: tous du même type – Binaire: l’objet x est décrit par d attributs xi tq xi €{0,1}, x={x1, x2,……., xd}, x élément de X, si m est la taille de l’échantillon d’apprentissage, alors les données peuvent être représentées par une matrice binaire (m x d) – Nominal (ou catégoriel): les valeurs des attributs appartiennent à un ensemble fini et non ordonné, ex: couleurs d’un jeu de cartes, – Nominal totalement ordonné: nominal avec relation d’ordre total, généralement assimilable à un intervalle dans IR ou dans IN 18 Cours_ML Chiraz JELASSI  Architecture du ML (suite) Espace des données d’apprentissage: 1. Représentation des objets d’apprentissage: nature des attributs (suite): - Nominal arborescent: nominal avec une certaine hiérarchie naturelle entre les différentes valeurs mais pas d’ordre total, - Séquentiel nominal: nominal avec un ordre nécessaire (la séquence) , ex: un texte dans un langage naturel « le commandant Cousteau » et « tout commença dans l’eau », sont différents mais constitués exactement des mêmes lettres de l’alphabet (sans tenir compte des espaces, des accents, de la casse) 19 Cours_ML Chiraz JELASSI  Architecture du ML (suite) Espace des données d’apprentissage: 1. Représentation des objets d’apprentissage: nature des attributs (suite): - Séquentiel numérique: avec une séquence (temporelle par exemple), ex: problèmes du traitement du signal (analyse spectrale dans le temps)  Mixtes: type d’attribut non homogène – la plupart des méthodes d’apprentissage s’appliquent à des données décrites dans un espace de représentation homogène, – dans le cadre général, l’espace de représentation peut recourir à des attributs de natures différentes, ex: cas des oiseaux avec des attributs nominaux totalement ordonnés (taille) et d’autres nominaux (couleur), … 20 Cours_ML Chiraz JELASSI  Architecture du ML (suite) Espace des données d’apprentissage: 2. Prétraitement des données – le choix des attributs de description: différents choix sont possibles et peuvent influer sur le résultat, – le traitement du bruit: des erreurs ou des imperfections dans les données: bruits de description: par exemple des erreurs de mesure, bruits de classification: erreur dans la classification des exemples, absence de données: exemple des applications dans le domaine médical, – les données sont imprécises ou vagues: choix d’une représentation adaptée, par exemple: la logique floue, la logique de l’imprécis et/ou de l’incertain, … 21 Cours_ML Chiraz JELASSI  Algorithme du Machine learning Algorithme d’apprentissage: Déduire les paramètres du modèle à partir des données  Apprentissage supervisé  Apprentissage non supervisé  Apprentissage par renforcement Algorithme d'inférence: Déduire la prédiction d'un modèle 22 Cours_ML Chiraz JELASSI  Algorithme d’apprentissage L'algorithme d'apprentissage constitue la méthode avec laquelle le modèle statistique va se paramétrer à partir des données d’entrée. L’algorithme est choisi en fonction du type de tâche que l'on souhaite accomplir et du type de données dont on dispose. Quelques exemples d'algorithmes d’apprentissage:  La régression linéaire  k plus proches voisins (K-nn) k-nearest neighbor  Les machines à vecteurs de support Support Vector Machine (SVM)  Les réseaux de neurones Les forêts aléatoires random forests  etc. 23 Cours_ML Chiraz JELASSI  Apprentissage supervisé Exemples entrée-sortie (x1,y1), (x2,y2), … , (xn, yn) ALGORITHME H famille de modèles mathématiques D’APPRENTISSAGE hH Hyper-paramètres pour l’algorithme d’apprentissage Information 24 Cours_ML Chiraz JELASSI  Apprentissage supervisé (suite) Soit un ensemble fini d’exemples (x1,y1), (x2,y2), … , (xn, yn), où xid vecteurs d’entrée, et yis sorties désirées (fournies par le « superviseur »), trouver une fonction h qui « approxime et généralise au mieux » la fonction sous-jacente f telle que yi=f(xi)+bruit  but = minimiser erreur de généralisation Egen=  ||h(x)-f(x)||2 p(x)dx où p(x)=distrib. de proba de x) 25 Cours_ML Chiraz JELASSI  Apprentissage supervisé (suite) Exemple Entrées Sortie Nbre de Surface Code … Prix = Y Apprentissage chambre = A =B postal= C … supervisé Ῠ = h(A,B,C,…) 3 2104 31500 400 Modèle 3 1600 87220 330 mathématique 3 2400 45760 369 …. 4 3000 76540 540 Minimiser l’erreur entre Y et Ῠ 26 Cours_ML Chiraz JELASSI  Apprentissage supervisé (suite) En apprentissage supervisé, l'objectif est de construire des modèles capables de généraliser, c'est-à-dire d'effectuer de bonnes prédictions sur de nouvelles données. Il est important de noter que de bonnes performances sur l'ensemble d'apprentissage ne tiendront pas nécessairement compte que le modèle sera capable de généraliser correctement. L'objectif est donc de trouver un équilibre dans la complexité du modèle. Il doit être suffisamment complexe pour capturer la nature des données de manière précise, éviter ainsi le sous-apprentissage. Cependant, il ne doit pas être trop complexe pour éviter le sur-apprentissage, c'est-à-dire une situation où le modèle s'adapte de manière excessive aux données d'apprentissage spécifiques et perd sa capacité à généraliser correctement sur de nouvelles données. Trouver ce juste milieu est essentiel pour obtenir un modèle performant. Il est important de prendre en compte les limitations liées aux temps de calcul et aux ressources en mémoire ! 27 Cours_ML Chiraz JELASSI  Apprentissage supervisé (suite) Vecteurs caractéristiques (features vectors) Textes, images, son, documents, …. Algorithme d’apprentissage Étiquettes Vecteur caractéristique Nouveau étiquette Modèle texte, image, attendue prédictif son, document, …. 28 Cours_ML Chiraz JELASSI  Apprentissage supervisé (suite) L'apprentissage supervisé peut être divisé en deux catégories principales : la régression et la classification. Dans les deux cas, l'objectif est de construire un modèle capable de prédire une sortie en fonction d'une observation d'entrée. La différence réside dans le type de sortie: la régression traite des sorties numériques, tandis que la classification concerne des sorties catégoriques. 29 Cours_ML Chiraz JELASSI  Apprentissage supervisé (suite) Détection des emails SPAM Détection des maladies Reconnaissance des chiffres manuscrit Reconnaissance vocale 30 Cours_ML Chiraz JELASSI  Apprentissage Non supervisé Base d’exemples de type « entrée seule» : X= {x1, x2, … , xn} (xid, souvent avec d « grand ») hH telle que ALGORITHME H famille de critère J(h,X) D’APPRENTISSAGE soit vérifié ou modèles mathématiques optimisé [ chaque hH avec comportement y=h(x) ] Hyper-paramètres pour l’algorithme d’apprentissage Règles d’association Détection d’anomalie Clustering Reduction de dimension 31 Cours_ML Chiraz JELASSI  Apprentissage Non supervisé (suite) Vecteurs caractéristiques Textes, images, son, documents, …. Algorithme d’apprentissage Indice de vrai Vecteur caractéristique semblence Nouveau ou texte, image, Modèle identifiant de cluster son, document, ou …. Meilleure représentation 32 Cours_ML Chiraz JELASSI  Apprentissage Non supervisé (suite) Segmentation des clients Détection faciale Système de recommandation 33 Cours_ML Chiraz JELASSI  L’apprentissage par renforcement Situation s Environnement Renforcement r Action a a0 r1 a1 r2 a2 s0 s1 s2  t0 t1 t2 L’agent intelligent :  observe les conséquences de ses actions et en déduit la qualité de celles-ci à partir de ces observations.  Les décisions sont prises séquentiellement à des intervalles de temps discrets  Améliore ses actions futures 34 Cours_ML Chiraz JELASSI  L’apprentissage par renforcement(suite) Le principe de l’AR est d’apprendre une politique visant à maximiser la récompense globale de l’agent vis à vis d’un but à atteindre en considérant uniquement la récompense locale associée à chaque action. Chaque décision prise influe sur les décisions suivantes, l’apprentissage par renforcement peut être vu comme une méthode permettant de résoudre un problème de décision séquentielle. Les Processus Décisionnels de Markov (PDM) définissent le cadre formel de l’apprentissage par renforcement1. 1https://blog.octo.com/apprentissage-par-renforcement-de-la-theorie-a-la- pratique/ 35 Cours_ML Chiraz JELASSI  Le processus itérative d’apprentissage Hyper parameter Build Models Train (70%) Validation Feature Models results data engineering Test (30%) 36 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées  La qualité du modèle appris dépend de la qualité des données d’apprentissage,  On parle de données d’apprentissage non équilibrées pour la classification quand le nombre d’observations appartenant à une classe est significativement très inférieur à celui des observations appartenant aux autres classes: - identification de maladies rares, - identification de fraudes bancaires, - identification de clients qui risquent de migrer d’un opérateur vers un autre , - ………  Dans ces cas, le modèle prédictif généré par ML conventionnelle peut être biaisée et non précis, 37 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées  Les algorithmes de ML en général sont orientés vers l’amélioration de la précision par réduction de l’erreur, et ne prennent pas en considération la distribution entre les classes,  On parle de données non équilibrées si le concept à prédire appartient à la classe minoritaire parmi les données d’apprentissage: taux inférieure à 5% par rapport aux données des autres classes, Exemple: - On dispose de 1000 observations de patients, - Observations de patients atteints d’une maladie rare: 20 - Observations de patients sains non atteints de la maladie rare: 980 - Taux de la classe minoritaire: 20/ 1000 = 2%  Apprendre à partir de telles données fera que la classe minoritaire sera traitée comme bruit et sera ignorée dans le modèle généré !! 38 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées  Deux façons de résoudre ce problème: - Agir pour améliorer les algorithmes de classification - Agir pour obtenir un meilleur équilibrage des données d’apprentissage: - Accroitre le nombre d’exemples de la classe minoritaire, - Diminuer le nombre d’exemples des classes majoritaires,  Différentes techniques peuvent être utilisées: - Random Under-Sampling (sous échantillonnage aléatoire), - Random Over-Sampling (sur échantillonnage aléatoire), - Cluster-Based Over-Sampling (sur échantillonnage par le clustering), - Informed Over Sampling (sur échantillonnage informé): Synthetic Minority - Over-Sampling Technique SMOTE, 39 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées Random Under-Sampling (sous échantillonnage aléatoire): Le principe consiste à éliminer de façon aléatoire des observations de l’échantillon d’apprentissage appartenant aux classes majoritaires, jusqu’à ce que les données deviennent équilibrées entre les classes majoritaires et la classe minoritaire; Exemple: - Prendre 10% des observations de patients sains, soit 98 - Garder les observations de patients atteints, soit 20 - Total des observations à considérer: 98 + 20 = 118 - Taux des observations de la classe minoritaire: 20 / 118 = 17% Avantages: améliore le temps d’exécution et les besoins en mémoire quand on a à faire à un nombre important de donnés d’apprentissage, Inconvénients: possibilité de perte d’informations importantes pour la classification, les observations gardées de façon aléatoire peuvent être des observations biaisées et ne sont pas représentatives de la population, 40 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées Random Over-Sampling (sur échantillonnage aléatoire): Le principe consiste à faire croître le nombre d’observations de la classe minoritaire par réplication dans un ordre aléatoire, Exemple: - Réplication par 20 des observations de patients atteints, soit 20 x 20= 400 - Garder les observations de patients sain, soit 980 - Total des observations à considérer: 980 + 400 =1380 -Taux des observations de la classe minoritaire: 400 /1380 = 29% Avantages: pas de perte d’information, meilleure précision que le sous échantillonnage, Inconvénients: augmente les risques de sur apprentissage, 41 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées Cluster-Based Over-Sampling (sur échantillonnage par le clustering): Le principe consiste à: 1- rechercher des regroupements naturels au sein des données d’apprentissage en utilisant un algorithme de clustering ( par exemple Kmeans) 2- Ensuite, opérer un sur-échantillonnage de chaque cluster de sorte que tous les clusters de la même classe aient le même nombre d’observations, et toutes les classes aient la même taille, 42 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées Cluster-Based Over-Sampling (sur échantillonnage par le clustering): Exemple: 1- Clustering des observations donne: - Classe des patients sains: - Cluster1:150 observations, - Cluster2: 120 observations, - Cluster3: 230 observations, - Cluster4: 200 observations, - Cluster5: 170 observations, - Cluster6: 13O observations, - Classe des patients atteints: - Cluster1: 8 observations, - Cluster2: 12 observations, 43 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées Cluster-Based Over-Sampling (sur échantillonnage par le clustering): 2- sur-échantillonnage de chaque cluster Clustering des observations donne: - Classe des patients sains: - Cluster1:170 observations, - Cluster2: 170 observations, - Cluster3: 170 observations (sous échantillonnage), - Cluster4: 170 observations (sous échantillonnage), - Cluster5: 170 observations, - Cluster6: 17O observations, - Classe des patients atteints: - Cluster1: 250 observations, - Cluster2: 250 observations, - Taux des observations des patients atteints: 500 / (1020 + 500) = 33% 44 Cours_ML Chiraz JELASSI  Données d’apprentissage: Le traitement de données d’apprentissage non équilibrées Cluster-Based Over-Sampling (sur échantillonnage par le clustering): - Avantages: le clustering apporte une solution au déséquilibre entre les classes sans perte d’information, permet d’équilibrer à l’intérieur de la même classe, - Inconvénients: comme la plupart des techniques de sur échantillonnage, il y a risque de sur apprentissage, 45 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 46 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 47 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 48 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 49 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 50 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 51 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 52 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 53 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H 54 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’apprentissage de concepts La plupart des systèmes d'apprentissage visent à apprendre des concepts généraux à partir d'exemples spécifiques. Chaque concept peut être représenté soit par extension, c'est-à-dire le sous-ensemble d'exemples qu'il englobe, soit par intension, c'est-à-dire une fonction booléenne qui décrit l'appartenance au concept en fonction de certaines caractéristiques. Notations Une instance étant donné un ensemble d’attribut, chacun ayant un domaine de valeurs, une instance est une valorisation possible de cet ensemble d’attributs dans leurs domaines respectifs. La fonction concept, étant donné un ensemble d'instances X, est une fonction c(X) → {0,1} qui permet de déterminer l'appartenance d'une instance x X au concept en cours d'apprentissage. L'ensemble d'apprentissage est constitué d'un ensemble d'instances, accompagné de leurs valeurs d'appartenance au concept. 55 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’apprentissage de concepts (suite) L'espace d'hypothèses représente l'ensemble de toutes les hypothèses possibles pour décrire un domaine donné. Une hypothèse est définie comme une conjonction de contraintes sur la liste d'attributs :. Chaque contrainte peut être une valeur spécifique appartenant au domaine de l'attribut, ou bien elle peut prendre la valeur "?" ou "ϕ". La valeur "?" indique que l'attribut peut prendre n'importe quelle valeur, tandis que la valeur "ϕ" signifie que l'attribut ne peut prendre aucune valeur dans son domaine. 56 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’apprentissage de concepts (suite) Par exemple, la table 1.1 nous montre un ensemble d’apprentissage. Une instance est décrite par les attributs : {CIEL, TEMP, HUMI, VENT} définis respectivement sur les domaines suivants : D(CIEL) = {ensoleille, couvert, pluvieux}, D(TEMP ) = {élevé, moyenne, basse}, D(HUMI) = {forte, normale, moyenne}, D(VENT ) = {oui, non}. Cette table comporte deux exemples positifs (ayant c(x)=1) et deux exemples négatifs (avec c(x)=0). Une hypothèse possible serait h= qui couvre les deux exemples négatifs dans l’ensemble d’apprentissage. L’hypothèse < ?, ?, ?, ?> est appelée l’hypothèse la plus générale car elle représente tous les exemples possibles tandis que toute hypothèse contenant la valeur ϕ représente l’ensemble vide, autrement dit elle ne satisfait aucun exemple. 57 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’apprentissage de concepts (suite) Le schéma de description d'une tâche consiste en ce qui suit : étant donné un ensemble d'instances X, accompagné de la fonction cible c(X) → {0,1}, qui est l'ensemble d'apprentissage contenant des exemples positifs et négatifs, l'objectif est de déterminer une hypothèse h H, où H représente l'espace d'hypothèses possible, telle que h(x) = c(x) x X. En d'autres termes, l'hypothèse inférée doit classifier correctement les exemples positifs et rejeter les exemples négatifs. Ce type d'apprentissage fait partie de l'apprentissage par induction, qui est basé sur l'hypothèse suivante : une hypothèse construite à partir d'un ensemble d'exemples contenant des exemples suffisamment représentatifs du domaine devrait être en mesure de classifier de manière assez précise de nouveaux exemples. 58 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’apprentissage de concepts (suite) Relation d’ordre sur l’espace d’hypothèses La relation d’ordre partielle sur l’espace d’hypothèses nous permettra de trouver un treillis d’hypothèses consistantes. Cette relation est basée sur la relation PGE (Plus général ou Égal) qu’on définira ainsi : Soit hj,hk deux hypothèses  L’algorithme Find-S L’objectif de l’algorithme Find-S est de trouver l’hypothèse la plus spécifique qui satisfait tous les exemples positifs dans l’ensemble d’apprentissage. 59 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’algorithme Find-S 60 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’algorithme Find-S (suite) en appliquant Find-S sur les quatre exemples présenté au dessus L’inconvénient majeur de cet algorithme est qu’il ignore complètement les exemples négatifs. Par conséquence, il est possible d’avoir une hypothèse qui satisfait tous les exemples positifs mais qui ne rejette pas obligatoirement tous les exemples négatifs car aucune vérification n’est effectuée dans l’algorithme. Autrement dit, l’algorithme Find-S est incapable dans ce cas de retourner une hypothèse vide. D’un autre côté, Find-S trouve l’hypothèse la plus spécifique qui couvre les exemples positifs sachant qu’il peut exister d’autres hypothèses plus générales qui seront consistantes avec l’ensemble d’apprentissage. 61 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version Un espace de versions est une pratique utilisée en apprentissage supervisé pour induire des concepts généraux ou des règles à partir d'un ensemble contenant des exemples vérifiant la règle qu'on cherche à établir et des contre-exemples ne la vérifiant pas. L'espace de versions est l'ensemble des hypothèses cohérentes avec le jeu d'exemples. La technique des espace de versions a été proposée par Tom Mitchell en 1978. La construction de l’espace de version est basée sur la recherche des hypothèses consistantes avec l’ensemble d’apprentissage D dans H. Une hypothèse h est dite consistante avec un ensemble d’apprentissage donné ssi h(x) = c(x) pour chaque exemple (x,c(x)) dans D. L’espace de version est donné par 62 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) Nous définissons dans la suite la limite générale et la limite spécifique d’un espace d’hypothèses H par rapport à un ensemble d’apprentissage D, notés respectivement par G et S. Exemple: les rectangles représentent ici les hypothèses pour classer des points en 2D. Représentation des hypothèses de rectangles à partir d'exemples positifs (les croix vertes, qui doivent être à l'intérieur du rectangle) et négatifs (les ronds rouges, qui doivent être à l'extérieur du rectangle). Le rectangle GB est l'hypothèses la plus générale (en généralisant plus on couvrirait des exemples négatifs), et SB est la plus spécifique (en spécialisant plus on ne couvrirait plus certains exemples positifs). Les rectangles verts représentent d'autres hypothèses de l'espace de versions. 63 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) G est la limite générale c’est l’ensemble des hypothèses les plus générales qui seront consistantes avec D. Voici la formule: De même, S est la limite spécifique c’est l’ensemble des hypothèses les plus spécifiques qui seront consistantes avec D. Voici la formule: Théorème 64 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) L’algorithme Candidate-Elimination 65 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) L’algorithme Candidate-Elimination(suite) 66 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) L’algorithme Candidate-Elimination(suite) Exemple On veut déterminer les sports qu'une personne aime regarder. Les paramètres sont le sport, le type (équipe/individuel), le lieu (intérieur/extérieur), le niveau (national/mondial) et le jour. (football, équipe, extérieur, national, dimanche) est un exemple. L’espace des hypothèses est simples : Une hypothèse sur un paramètre exige soit une valeur précise (par exemple « équipe » pour le paramètre «Type»), soit n‘exige aucune valeur (toutes les valeurs sont bonnes), ce que l'ont note avec un point d'interrogation. Dans cet exemple simple on n'autorise pas les disjonctions (par exemple « il fait beau ou nuageux »). Exemple d'hypothèse qui n'accepte que les sports individuels : (?, individuel, ?, ?, ?). 67 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) L’algorithme Candidate-Elimination(suite) exp positif === changer S Exemple (suite) exp negatif == changer G 68 Cours_ML Chiraz JELASSI  Espace des hypothèses d’apprentissage: H L’espace de version (suite) L’algorithme Candidate-Elimination(suite) Exemple (suite) il faut tjs comparer au S ou G precedent des autres etapes et essayer d appliquer la nouvelle hypothese sur eux 69 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage Origines possibles des erreurs 70 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage Erreurs d’apprentissage h* : hypothèse optimale dans H. X: espace des exemples x h – h* : « variance » ou « erreur d'estimation ». H: espace des hypothèses h h* - f* : « biais »ou « erreur d'approximation ». F: espace des fonctions h – f* : erreur totale. cibles f 71 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Erreurs d’apprentissage(suite)  Biais(Erreur d’approximation) = erreur systématique commise par une méthode (indépendamment de l’échantillon) l’origine de l’erreur sont des hypothèses erronées dans l'algorithme d'apprentissage. Un biais élevé est dû à un algorithme qui manque de relations pertinentes entre les données en entrée et les sorties prévues (sous- apprentissage).  Variance (Erreur d’estimation) = erreur due à la variabilité du modèle (en fonction de l’échantillon) erreur due à la sensibilité aux petites variabilité de l’échantillon d'apprentissage. Une variance élevée peut causer un sur apprentissage, c'est-à-dire modéliser le bruit aléatoire des données d'apprentissage plutôt que les sorties prévues. modèle simple : fort biais et faible variance modèle complexe : faible biais et forte variance 72 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage On a recourt à des indicateurs de performance selon la méthode d’apprentissage et on vérifie le résultat par rapport aux exemples d’apprentissage (généralement 70% de la base des données des exemples) et par rapport aux exemples de Test (30% restant). 73 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Les meilleurs modèles sont les plus simples modèles qui couvrent bien les données d’apprentissage. Underfitting Overfitting 74 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Erreurs d’apprentissage: Compromis biais-variance 75 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire) Matrice de confusion - Prenons l’exemple d’un classifieur binaire, c’est-à-dire, qui prédit 2 classes notées classe 0 (ou classe négative) et classe 1 (ou classe positive). - Pour mesurer les performances de ce classifieur, il est d’usage de distinguer 4 types d’éléments classés pour la classe voulue: Vrai Positif VP (ou TP). Elément de la classe 1 correctement prédit Vrai Négatif VN (ou TN). Elément de la classe 0 correctement prédit Faux Positif FP (ou FP). Elément de la classe 1 mal prédit Faux Négatif FN (ou FN). Elément de la classe 0 mal prédit - Ces informations peuvent être rassemblées et visualisées sous forme de 76 tableau dansChiraz Cours_ML uneJELASSI matrice de confusion.  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire) - Matrice de confusion - un système de classification sera d'autant meilleur que sa matrice de confusion s'approchera d'une matrice diagonale. FP Erreur de type I Erreur de mauvaise classification Erreur de type II (Accuracy) = FP+FN/N+P FN Exemple alarme d’incendie FP (fausse alarme) erreur de type I FN (non détection) erreur de type II 77 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire) - Matrice de Confusion: Indicateurs de base Il est possible de calculer plusieurs indicateurs résumant la matrice de confusion. Si nous souhaitons rendre compte de la qualité de la prédiction sur la classe positive, on définit :  Précision (precision): Proportion d’éléments positifs bien classés par rapport aux éléments de la classe prédite positive : Quelle proportion d'identifications positives était effectivement correcte ? précision =1 si le modèle ne produisant aucun faux positif 78 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Exemple Soit un classifieur qui a classifié 100 tumeurs comme malignes (la classe positive) ou bénignes (la classe négative) : VP (1) FP (1) FN (8) VN (90) 79 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire)  TPR, Rappel (recall) sensibilité: Proportion d’éléments positifs bien classés par rapport au nombre d’éléments de la classe positive: La proportion de résultats positifs réels identifiée correctement un rappel = 1,0 si le modèle ne produisant aucun faux négatif.  F1-mesure (F1-score): Mesure de compromis entre précision et rappel : 80 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Exemple VP (1) FP (1) FN (8) VN (90) 81 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire) TNR, Spécificité (specificity): Proportion d’éléments négatifs bien classés par rapport au nombre d’éléments de la classe négative:  FPR, False Positive Rate: Proportion d’éléments de la classe négative classés positifs par rapport au nombre d’éléments de la classe négative: 82 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire) Il est possible de calculer tous ces indicateurs pour chaque classe La moyenne sur chaque classe de ces indicateurs donne des indicateurs globaux sur la qualité du classifieur 83 Cours_ML Chiraz JELASSI  Généralisation au problème multi-classe Matrice de confusion 84 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Indicateurs de performance pour les Classifieurs (Binaire) Utilisation des indicateurs: Machine Learning Standard: Erreur de mauvaise classification (accuracy) Médecine: rappel TPR et spécificité TNR Recherche d’information (retrieval information): Précision et Rappel, F1- score 85 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Exemple : Test Médical Soit un test Médical. Une étude conduite sur 4000 personnes, âgées de 40 ans et plus, visiblement en bonne santé. On leur a fait passer deux tests de dépistage du cancer: Un examen histologique lourd, qui doit être interprété par un médecin, et qui servira de vérité terrain. Un dépistage, c’est un examen plus simple, qui va être l’analyse de notre algorithme d’apprentissage. Voici les résultats : Cancer Pas de Total cancer Depistage + 190 210 400 Depistage - 10 3590 3600 Total 200 3800 4000 86 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Cancer Pas de Total cancer Depistage + 190 210 400 Depistage - 10 3590 3600 Total 200 3800 4000 quand le dépistage est négatif la probabilité de ne pas avoir de cancer est de 3590/3600 soit 99.7%, donc ce test est un bon outil de dépistage. Par contre, quand le dépistage est positif la probabilité d'avoir un cancer est de 190/400 = 47.5%, donc c’est un très mauvais outil de diagnostique. Il faut choisir la mesure la plus pertinente suivant la problématique à traiter. rappel = ? 95% Calculer: spécificité = ? 94.5 % précision = ? 47.5% 87 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Cas des prédictions non binaires (scores) Si l’algorithme de classification retourne un nombre réel, dans de nombreux cas (régression logistique, méthodes bayésiennes, réseaux de neurones…) Dans ce cas, pour rendre la prédiction binaire, il faut choisir un seuil : alors on prédit positif si le score retourné est supérieur à ce dernier, sinon on prédit négatif. Exemple On a 30 prédictions réalisées par un modèle de classification d'e-mails. Les cas situés à droite du seuil de classification sont classifiés comme "spam", tandis que ceux qui sont situés à gauche sont considérés comme "non spam". 88 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Évaluez un algorithme de classification qui retourne des scores Exemple ( suite) Pour calculer la précision on calcule le pourcentage d'e-mails identifiés comme spam ayant été classifiés correctement, c'est-à-dire le pourcentage de points situés à droite de la valeur de seuil représentés en vert sur la figure 89 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Évaluez un algorithme de classification qui retourne des scores Exemple ( suite)  Si on augmente le seuil Le nombre de faux positifs diminue, mais les faux négatifs augmentent. En conséquence, la précision augmente tandis que le rappel diminue : 90 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Évaluez un algorithme de classification qui retourne des scores Exemple ( suite) 91 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Évaluez un algorithme de classification qui retourne des scores Exemple ( suite) Si on diminue le seuil  Si on diminue le seuil Les faux positifs sont plus nombreux, et le nombre de faux négatifs diminue. En conséquence, la précision diminue tandis que le rappel augmente : 92 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Évaluez un algorithme de classification qui retourne des scores Courbe ROC (Received Operating Characteristic) avec un seuil t le résultat numérique donné sachant que la prédiction est positive si x > t, et la prédiction est négative si x < t, alors au fur et à mesure que t augmente: la spécificité augmente mais la sensibilité diminue. On peut dessiner l'évolution de la sensibilité (taux de vrais positifs) en fonction de 1 - spécificité (taux de faux positifs) quand on fait varier le seuil t avec La courbe ROC..  est un graphique représentant les performances d'un modèle pour tous les seuils de classification. Avec: la sensibilité est : TP / (TP + FN) = TP / P. la spécificité est : TN / (TN + FP) = TN / N. 93 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Évaluez un algorithme de classification qui retourne des scores Courbe ROC (Received Operating Characteristic) - La courbe est interprétée en fonction de l’aire sous la courbe (AUC: Aire Under curve). Plus elle se rapproche de 1, plus le classifieur est performant. 94 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Cas des Classifieurs Validation Croisée (Cross validation) à k plis: - En pratique, il est souvent difficile d’avoir suffisamment de données pour avoir des données d’apprentissage et des données de Test, dans ce cas on recoure à l’approche de la validation croisée, - il s’agit de choisir la part des exemples qui vont servir pour le Test , de ceux pour l’apprentissage et appliquer ceci plusieurs fois en modifiant la partie de Test sur laquelle on travaille, 95 Cours_ML Chiraz JELASSI  L’évaluation de l’apprentissage (suite) Validation Croisée (Cross validation) à k plis: 96 Cours_ML Chiraz JELASSI