chap02.concepts_apprentissage.pdf

Apprentissage supervisé 1 Principe de l’apprentissage supervisé Les algorithmes d’apprentissage supervisé procèdent comme suit: On fournit à l’algorithme des données d’entrainement: D= 𝑥 (1) , 𝑦 (1) , 𝑥 (2) , 𝑦 (2) , ⋯ , (𝑥 (𝑁) , 𝑦 (𝑁) ) On appelle...

Apprentissage supervisé 1 Principe de l’apprentissage supervisé Les algorithmes d’apprentissage supervisé procèdent comme suit: On fournit à l’algorithme des données d’entrainement: D= 𝑥 (1) , 𝑦 (1) , 𝑥 (2) , 𝑦 (2) , ⋯ , (𝑥 (𝑁) , 𝑦 (𝑁) ) On appelle 𝑥 (𝑖) l’entrée et 𝑦 (𝑖) la cible du i-ième exemple. Un élément de D est appelé exemple d’apprentissage ou une instance de données. 2 Principe de l’apprentissage supervisé L’algorithme retourne un «programme» capable de se généraliser à de nouvelles données: On note le «programme» généré par l’algorithme d’apprentissage f(x). On appelle f(x) un modèle ou une hypothèse. On utilise souvent un ensemble de test Dtest pour mesurer la performance du modèle f(x). 3 Exemple motivation Des cellules cancéreuses sont prises de tumeurs de cancer du sein avant la chirurgie et elles sont photographiées. Les tumeurs sont excisées. Les patients sont suivis pour voir s’il y a récurrence du cancer. On mesure le temps avant que la récurrence du cancer ou que le patient est déclaré sans la maladie. 4 Exemple motivation On utilise 30 caractéristiques par tumeur. Deux variables sont prédites:  Résultat ( R: récurrence, N: non-récurrence).  Temps (Jusqu’a récurrence, pour R, et en santé, pour N). L’ensemble de données est représenté par une matrice X : X 5 Exemple motivation Les colonnes sont appelées variables d’entrée, attributs ou caractéristiques. Le résultat et le temps (que nous essayons de prédire) sont appelés les variables résultats ou les cibles. Une ligne du tableau est appelée un exemple d’entrainement ou instance. Le tableau en entier est appelé l’ensemble d’entrainement. 6 Types de prédiction Le problème de prédiction des résultats de la maladie est appelé une classification. Le problème de prédiction du temps est appelé régression. 7 Types de prédiction (suite) Un exemple d’entrainement à la forme 𝑥 (𝑖) , 𝑦 (𝑖) , où: 𝑥 (𝑖) = 𝑥1 (𝑖) , 𝑥2 (𝑖) , ⋯ , 𝑥𝐷 (𝑖) 𝐷 est le nombre d’attributs (dans notre cas 30). L’ensemble d’entrée D contient 𝑁 exemples. On dénote par X l’espace des variables d’entrées (ex. ℝD) On dénote par Y l’espace des variables de sortie (ex. ℝ) 8 Apprentissage supervisé Ayant un ensemble de données D ⊂ X × Y, trouver une fonction : 𝑓: X → Y Telle que 𝑓 est un bon prédicteur de la valeur de 𝑦. La fonction 𝑓 est appelée une hypothèse. Les problèmes sont classés par type de domaine de sortie:  Si Y= ℝ, on parle alors de régression.  Si Y est un ensemble discret fini, on parle de classification.  Si Y a 2 éléments, on parle de classification binaire. 9 Apprentissage supervisé Les étapes pour résoudre un problème d’apprentissage supervisé. A. Définir les variables d’entrée et de sortie. B. Définir le codage des variables d’entrée et de sortie (X et Y). C. Choisir la classe d’hypothèse/représentations H. D. Trouver l’hypothèse f la plus optimale pour la prédication. 10 Apprentissage supervisé pour la régression 11 Principe de la régression Exemple: (régression linéaire) Espace de données Échantillon 12 Régression linéaire Exemple: supposons une hypothèse de régression linéaire. 𝑦 = 𝑓 𝑥 = 𝑤0 + 𝑤1𝑥1 + ⋯ où 𝑥 = (𝑥1 , 𝑥2 , … , 𝑥𝐷 ). Les 𝑤𝑑 sont appelés des paramètres ou des poids. Pour simplifier la notation, ajouter un attribut 𝑥0 = 1. 𝐷 𝑦=𝑓 𝑥 = 𝑤𝑑 𝑥𝑑 = 𝐰𝑇𝑥 𝑑=0 où 𝐰 et 𝑥 sont des vecteurs de dimension 𝐷 + 1. 13 14 Régression linéaire Comment prendre les paramètres 𝐰 ? 𝐰 doit rendre f(x) très proche des valeurs des y. On doit alors définir une fonction d’erreur ou de perte pour mesurer combien notre prédiction est loin des «vraies» valeurs. On prend 𝐰 qui minimise la fonction d’erreur. Exemple: erreur des moindres carrés. 15 Erreur des moindres carrés Principe Essayer de rendre f(x) très proche des valeurs des y dans tous les exemples d’apprentissage dans D. Définir une fonction d’erreur par la somme: 1 𝑁 2 𝐸(𝐰) = 𝑓 𝑥 (𝑖) − 𝑦 (𝑖) 2 𝑖=1 Choisir 𝐰 qui minimise la fonction d’erreur 𝐸(𝐰)?. 16 17 Erreur des moindres carrés Sur notre exemple (Un peu d’algèbre!) 𝜕𝐸(𝐰) 𝜕 1 𝑁 2 = 𝑓 𝑥 (𝑖) −𝑦 (𝑖) 𝜕𝑤𝑑 𝜕𝑤𝑑 2 𝑖=1 1 𝑁 𝜕 (𝑖) (𝑖) =2 𝑓 𝑥 −𝑦 𝑓 𝑥 (𝑖) − 𝑦 (𝑖) 2 𝑖=1 𝜕𝑤𝑑 𝑁 𝜕 𝐷 (𝑖) = 𝑓 𝑥 (𝑖) − 𝑦 (𝑖) 𝑤𝑑 𝑥𝑑 − 𝑦 (𝑖) 𝑖=1 𝜕𝑤𝑑 𝑑=0 𝑁 (𝑖) = 𝑓 𝑥 (𝑖) − 𝑦 (𝑖) 𝑥𝑑 𝑖=1 18 19 20 Notation matricielle On a: 𝛻𝐸(𝐰) = 𝛻( 𝐗𝐰 − 𝐲 𝑇(𝐗𝐰 − 𝐲)) = 2𝐗𝑇(𝐗𝐰 − 𝒚) (formule de Taylor) = 2𝐗𝑇𝐗𝐰 − 2𝐗𝑇𝒚 En posant la dérivée égale à zéro, on obtient: 2𝐗𝑇𝐗𝐰 − 2𝐗𝑇𝒚 = 0 ⇒ 𝐗𝑇𝐗𝐰 = 𝐗𝑇𝒚 ⇒ 𝐰 = 𝐗 𝑇𝐗 −1 𝐗𝑇𝒚 L’inverse de XTX existe si les colonnes de X sont linéairement indépendantes. 21 Exemple 𝐗= 𝐲= 𝐗𝑇 𝐗 = 22  Exemple 𝐗𝑇 𝐲 = 𝐰 = 𝐗𝑇𝐗 −1 𝐗𝑇𝒚 23 Exemple La meilleure ligne est égale alors à: 𝑦 = 1.6𝑥 + 1.05 24 Fonctions d’ordre supérieur 𝐗𝑇 𝐗 25 Fonctions d’ordre supérieur Soit x une variable d’entrée unidimensionnelle 𝐷 = 1. Si nous voulons appliquer un polynôme d’ordre supérieur aux données d’apprentissage, on aura: Exemple: 𝑓 𝑥 = 𝑤0 + 𝑤1 𝑥 + 𝑤2 𝑥 2 Pour un polynôme d’ordre 𝑚, on aura: (1) 𝑚 (1) 2 𝑥 ⋯ 𝑥 𝑥 (1) 1 (2) 𝑚 (2) 2 𝐗= 𝑥 𝑥 𝑥 (2) 1 ⋮ ⋱ ⋮ 𝑚 𝑥 (𝑁) ⋯ 𝑥 (𝑁) 2 𝑥 (𝑁) 1 Résoudre le problème: 𝐗𝑇𝐰 ≈ 𝒚 26 Fonctions d’ordre supérieur Pour notre exemple, une régression quadratique (m=2) aura la forme: 𝐗 𝐲 27 Fonctions d’ordre supérieur 𝐗𝑇𝐗 = 𝐗𝑇 𝐲 = 28 Fonctions d’ordre supérieur 𝐰 = 𝐗𝑇𝐗 −1 𝐗𝑇𝒚 29 Fonctions d’ordre supérieur 30 Overfitting Est un important problème pour les techniques d’apprentissage! On peut trouver une hypothèse qui fait une bonne prédiction pour des données d’entrainement, mais qui ne se généralise pas bien pour le reste des données. Dans le reste du cours, nous verrons des méthodes pour atténuer le problème d’overfitting. 31 Théorie de la décision pour la classification 32 Principe Soit un problème de classification à K classes {C1,…,CK}. Une fonction discriminante a le rôle de prendre une entrée 𝑥 et de lui assigner une classe parmi K classes existantes. Soit 𝑥 un vecteur d’entrée ayant une valeur cible y, et notre but est de prédire y ayant la donnée d’entrée 𝑥. Exemple: 𝑥 : image de rayon-X. 𝑦 : présence/non-présence d’une certaine maladie (ex. cancer, sclérose, etc.) qui forment les classes C1 et C2. 33 Théorie de la décision La théorie des probabilités permet de quantifier et manipuler l’incertitude dans les expériences aléatoires. Elle peut aider aussi à la prise des décisions dans des situations impliquant l’incertitude sur les résultats. On peut choisir par exemple le codage suivant: 1 𝑠𝑖 𝑥 (𝑖) ∈ 𝐶1 𝑦 (𝑖) = 0 𝑠𝑖 𝑥 (𝑖) ∈ 𝐶2 34 Théorie de la décision Le problème revient alors à déterminer la probabilité p(𝑥,𝐶𝑘 ) qui donnera une description complète de la situation. Lorsqu’on obtient l’image rayon-X 𝑥 pour un nouveau malade, on doit décider à quelle classe il appartient. La probabilité d’une classe 𝐶𝑘 est donnée par p(𝐶𝑘 | 𝑥). Cette probabilité est formulée par: 𝑝 𝑥 𝐶𝑘 𝑝(𝐶𝑘 ) 𝑝(𝐶𝑘 |𝑥) = 𝑝(𝑥) 35 Théorie de la décision On peut interpréter 𝑝(𝐶𝑘 ) comme étant la probabilité a priori pour observer la classe 𝐶𝑘. Le terme 𝑝(𝐶𝑘 |𝑥) correspond à la probabilité a posteriori. Intuitivement, l’erreur de classification est minimisée en assignant 𝑥 à la classe ayant la plus grande probabilité a posteriori. La règle minimisant l’erreur de classification va diviser l’espace des données D en K régions {R1, R2, …, RK} appelées régions de décisions. 36 37 Minimiser l’erreur de classification Une erreur est produite lorsqu’une donnée appartenant à C1 est assignée à C2 et vice-versa. La probabilité d’occurrence d’erreur est donnée par: 𝑝 𝑒𝑟𝑟𝑒𝑢𝑟 = 𝑝 𝑥 ∈ 𝑅1 𝐶2 + 𝑝 𝑥 ∈ 𝑅2 𝐶1 = 𝑝(𝑥, 𝐶2) 𝑑𝑥 + 𝑝(𝑥, 𝐶1) 𝑑𝑥 𝑅1 𝑅2 Pour minimiser l’erreur de classification, la règle de décision doit assigner chaque donnée 𝑥 en minimisant 𝑝 𝑒𝑟𝑟𝑒𝑢𝑟. 38 39 Minimiser l’erreur de classification En ayant 𝑝 𝑥, 𝐶1 = 𝑝(𝐶1|𝑥) 𝑝(𝑥), et 𝑝(𝑥) est un facteur commun entre les deux classes, le minimum sera obtenu en assignant la donnée 𝑥 à la classe ayant le plus grand 𝑝(𝐶𝑘 |𝑥). 40 Modèles linéaires pour la classification 41 Introduction Pour la classification, on possède K classes {C1, C2, …, CK}. Dans la plupart des scenarios, les classes sont disjointes. L’espace d’entrée est alors divisé en régions séparées par des frontières (ou surface) de décision. Dans cette partie du cours, nous considérons les modèles linéaires pour la classification, c.-à-d., la frontière de décision est une fonction linéaire de la variable d’entrée 𝑥. La frontière linéaire est définie dans l’espace à (𝐷 − 1) dimensions dans l’espace de données à 𝐷 dimensions. 42 Modèle linéaire de classification Une fonction discriminante a le rôle de prendre une entrée 𝑥 et de lui assigner une classe parmi K classes existantes. Un classificateur linéaire utilise une frontière de décision linaire pour assigner les classes aux données. Soit D la dimension de 𝑥 :  Pour D = 2, la frontière sera une droite.  Pour D = 3, la frontière sera un plan.  Pour D > 3, la frontière sera appelée hyperplan. 43 Exemple de frontières de décision linéaires Pour D = 2, D=3 44 Frontière de décision linéaire Les classes qui peuvent être séparées par des frontières de décision linéaires sont dites linéairement séparable. Rappelons que pour le problème de régression, la variable cible y a une valeur réelle. Pour la classification, on peut utiliser plusieurs manière pour représenter la variable cible y. Soit y=1 pour la classe C1 et y=0 pour la classe C2. Pour K > 2, on peut utiliser un codage avec un vecteur 𝐲 = (𝑦1 , … , 𝑦𝐾 ) où, si 𝐱 ∈ 𝐶𝑘 , alors 𝑦𝑘 = 1 et 𝑦𝑗 = 0, ∀𝑗 ≠ 𝑘. 45 Frontière de décision linéaire Exemple de codage avec un vecteur: Pour K > 2, on peut utiliser un codage avec un vecteur 𝐲 = (𝒚𝟏 , … , 𝒚𝑲 ) où, si 𝐱 ∈ 𝑪𝒌 , alors 𝒚𝒌 = 𝟏 et 𝒚𝒋 = 𝟎, ∀𝒋 ≠ 𝒌. Exemple : si K = 5 alors Donnée (𝒙) Classe Codage (𝒚) 𝐶1 𝟏, 𝟎, 𝟎, 𝟎, 𝟎 𝐶2 𝟎, 𝟏, 𝟎, 𝟎, 𝟎 𝐶3 𝟎, 𝟎, 𝟏, 𝟎, 𝟎 𝐶4 𝟎, 𝟎, 𝟎, 𝟏, 𝟎 𝐶5 𝟎, 𝟎, 𝟎, 𝟎, 𝟏 46 Frontière de décision linéaire Dans le modèle de régression linéaire, la prédiction de y se fait par une fonction de la forme: 𝑓 𝑥 = 𝐰𝑇𝑥 + 𝑤0. Pour la classification, on voudrait prédire les étiquettes de classes (class labels), ou plus généralement les probabilités a posteriori des classes dans l’intervalle [0,1]. On peut généraliser le modèle linéaire de régression pour la classification en ayant une fonction linéaire de 𝐰 qu’on transforme avec une fonction non-linéaire: 𝑓 𝑥 = 𝑔(𝐰𝑇𝑥 + 𝑤0) 47 Frontière de décision linéaire On appelle 𝑔 𝑥 une fonction d’activation. Son inverse est appelé une fonction de lien en statistique. Pour ce modèle, les surfaces de décision correspondent aux valeurs 𝑓 𝑥 = constante, de telle sorte que 𝒘𝑻𝒙 + 𝒘𝟎 = 𝐜𝐨𝐧𝐬𝐭𝐚𝐧𝐭𝐞. Le modèles reposant sur l’équation précédentes s’appellent des modèles linéaires généralisés. Notons, qu’à cause de la fonction non-linéaire 𝑔 𝑥 , ces modèles ne sont pas linéaires des paramètres w. 48 49 Cas de classification binaire (K = 2) La représentation la plus simple d’une fonction discriminante est obtenue en prenant une fonction linéaire du vecteur d’entrée 𝑥: 𝑓 𝐱 = 𝐰𝑇𝑥 + 𝑤0 Le vecteur 𝑥 sera assigné à la classe C1 si 𝑓 𝑥 ≥ 0 et à la classe C2 dans le cas contraire. Si deux points 𝑥 (𝑖) et 𝑥 (𝑗) appartiennent à la frontière de décision, alors: 𝐰𝑇(𝑥 (𝑖) − 𝑥 (𝑗) ) = 0. Donc, le vecteur 𝐰 est orthogonale à la frontière. 50 Cas de classification binaire (K = 2) Soit un problème de classification à 2 classes (classification binaire). Dans le cas de d = 2, on a la géométrie suivante: 𝑓(𝑥) > 0 𝑓 𝑥 =0 𝑓 𝑥 2) Une des façons de construire un classificateur à K classes est de combiner plusieurs classificateurs binaires. Soit (K-1) classificateurs binaires chacun séparant une des classes 𝐶𝑘 , k = 1,…, K-1 (classification un-versus-tous). Régions ambiguë 54 Cas de classification multiple (K > 2) Une autre alternative est de construire K(K-1)/2 classificateurs binaires, un pour chaque deux classes (classification un- versus-un). Régions ambiguë 55 Cas de classification multiple (K > 2) On peut éviter ces difficultés en considérant un classificateur comprenant K fonctions linéaires discriminantes de la forme: 𝑓𝑘 (𝑥) = 𝐰𝑘 𝑇𝑥 + 𝑤𝑘0 On assigne 𝑥 pour une classe 𝐶𝑘 si 𝑓𝑘 𝑥 > 𝑓𝑗 𝑥 , ∀𝑗 ≠ 𝑘. La frontiere de decision entre la classe Ck et Cj est donnée par la relation 𝑓𝑘 𝑥 = 𝑓𝑗 𝑥 , qui correspond à: 𝐰𝑘 − 𝐰𝑗 𝑇𝑥 = 𝑤𝑘0 − 𝑤𝑗0 56 Cas de classification multiple (K > 2) R𝑗 R𝑖 R𝑘 𝑥 (𝑏) 𝑥 𝑥 (𝑎) On peut démontrer dans ce cas que les régions de décisions sont connexes et convexes. 57 Classification par les moindres carrées Comme on a fait pour la régression, on augmente d’abord la matrice de données 𝐗 d’une colonne égale à 1. On définit pour chaque donnée 𝑥 (𝑖) un vecteur colonne 𝑦 (𝑖) = 𝑦1 (𝑖) , 𝑦2 (𝑖) , ⋯ , 𝑦𝐾 (𝑖) T et une matrice 𝐘 dont la i-ième ligne (𝑖) 𝑇 contient 𝑦. Soit la matrice 𝐖 dont la k-ième colonne contient 𝐰𝑘. L’erreur des moindres carrées est alors donnée par: 1 𝐸(𝐖) = 𝑇𝑟 𝐗𝐖 − 𝐘 𝑇(𝐗𝐖 − 𝐘) 2 58 59 Classification par les moindres carrées En calculant la dérivée de 𝐸 par rapport à 𝐖, on obtient: 𝐖 = (𝐗𝑇𝐗)−1 𝐗𝑇𝐘 = 𝐗 ′ 𝐘 On appelle 𝐗 ′ le pseudo-inverse de la matrice 𝐗. La fonction discriminante 𝐟 est alors donnée par: 𝐟(𝐱) = 𝐖𝑇𝐱 = 𝐘𝑇( 𝐗 ′ )𝑇 𝐱 Notons que les éléments de 𝐟 auront la somme égale à 1. Mais les entrées de 𝐟 ne sont pas pour autant des probabilités. 60 Classification par les moindres carrées Moindres carrés. Exemples: Régression logistique. 61 Classification par les moindres carrées Moindres carrés Régression logistique 62 Classification par les moindres carrées La méthode des moindre carrés donne une solution exacte pour la classification. Cependant, elle a des limitations:  Elle fonctionne bien quand les classes sont séparables et les données des classes suivent des lois Gaussiennes.  Elle n’est pas robuste aux données aberrantes (outliers) qui perturbent la frontière de décision.  Par la suite, on verra une meilleure classification avec la régression logistique. 63 Références 1. M. S. Allili. Techniques d’apprentissage automatique (Cours de 2e cycle). Université du Québec en Outaouais (UQO), Québec, Canada. Hivers 2015. 2. S. Rogers et M Girolami. A first Course in machine learning, CRC press, 2012. 3. C. Bishop. Pattern Recognition and Machine learning. Springer 2006. 4. R. Duda, P. Storck et D. Hart. Pattern Classification. Prentice Hall, 2002. 64