Exercice 1   Une épreuve est le résultat d'une expérience aléatoire. On note W l'ensemble de toutes les épreuves possibles et w une épreuve ou événement élémentaire. Un événement aléatoire est un événement dont la réalisation ou la non réalisation dépend du résultat d'une expérience aléatoire. Un événement aléatoire sera représenté par l'ensemble des événements élémentaires qui le réalisent. Les opérations logiques sur les événements vont correspondre aux opérations ensemblistes. Considérons, par exemple le lancer de deux dés. On a W={1,...,6}². L'événement A défini par : ``amener un total au moins égal à 10'' est A={(x,y)| x+y³ 10}. Soit l'événement B : ``amener deux dés identiques''. On a alors AÇ B ={(5,5), (6,6)}. Les correspondances entre formalismes peuvent être résumées dans le tableau suivant :



Nous nous limitons au cas où W est dénombrable. Une probabilité sur W est une application P de W dans [0,1] telle que la somme des probabilités des événements élémentaires est égale à 1. On peut montrer les résultats suivants :

• soit (A_i)_{iÎ I} une famille d'événements deux à deux incompatibles, P(È_{iÎ I} A_i) = å_{iÎ I} P(A_i),
• P(A)=å_{w Î A} P(w),
• P(AÈ B) = P(A) + P(B) - P(AÇ B),
• P(A) = 1-P(A),
• si A Í B, P(A) £ P(B).

Soit (W,P) un espace de probabilités et A un événement de probabilité non nulle, la probabilité conditionnelle P(B/A) d'un événement B sachant A est définie par : P(B/A)=P(AÇ B)/ P(A). Démontrez que :

• P(./A) est une probabilité sur W et sur A,
• P(A / B) = (P(A) × P(B/A))/ P(B) (formule de Bayes),
• soit (A_i)_i=1ⁿ un système exhaustif, P(B)= å_i=1ⁿ P(B/A_i)P(A_i).

Deux événements sont indépendants si ils vérifient les conditions équivalentes suivantes :

1. P(B/A)=P(B)
2. P(A/B)=P(A)
3. P(A Ç B)=P(A)P(B)

Exercice 2   Soit une population P d'individus qui consiste en un échantillon composé d'ouvriers, de médecins et d'employés des télécoms. On décrit les individus par un attribut logique repondeur qui vaut vrai si l'individu possède un répondeur téléphonique et faux sinon. L'espace de description est donc égal à l'ensemble {repondeur, repondeur}. On souhaite répartir les individus en trois classes ouvrier, medecin et telecom. On dispose des informations suivantes :



Une première règle possible pour le choix de la fonction de classement C pourrait être : ``attribuer à chaque description la classe majoritaire'', c'est-à-dire celle pour laquelle P(k) est maximum ; c'est la règle majoritaire. Une seconde règle consiste à raisonner ainsi : ``si j'observe d, je choisis la classe pour laquelle cette observation est la plus probable'', c'est-à-dire celle pour laquelle P(d/k) est maximum. C'est la règle dite du maximum de vraisemblance. Une troisième règle (règle de Bayes) consiste à attribuer à une description d la classe k qui maximise la probabilité P(k/d) qu'un élément ayant d pour description soit de classe k. La quantité P(k/d) peut être estimée en utilisant la formule de Bayes, il suffit donc de choisir la classe k qui maximise le produit P(d/k)P(k).

Décrire sur cet exemple les trois fonctions C_majoritaire, C_{vraisemblance}, C_Bayes.

On peut définir la probabilité d'erreur d'une fonction de classement de la façon suivante : soit C une fonction de classement, l'erreur E(d) (ou probabilité d'erreur) pour une description d est la probabilité qu'un élément de la population P de description d soit mal classé par C, l'erreur E(C) d'une fonction de classement est la moyenne pondérée des erreurs sur les descriptions d. Calculer les erreurs pour les trois procédures de classification trouvées précédemment.

Exercice 3   On dispose d'une population P constituée d'un ensemble de pièces qui sont équitables, biaisées avec une probabilité 1/3 pour Face, ou encore biaisées avec une probabilité de 1/4 pour Face. Une expérience consiste à jeter une pièce 20 fois de suite. Au vu du résultat d'une telle expérience, on souhaite classifier la pièce. On considère donc les trois classes {1,2,3} qui correspondent à une probabilité de Face égale à respectivement 1/2, 1/3 et 1/4. On fera l'hypothèse a priori que les classes sont équiprobables. Une description est un mot de l'ensemble {P,F}²⁰, où P correspond à Pile et F à Face. Une procédure de classification doit associer à un mot de cet ensemble une classe. Soit la description Trouver les formules de calcul des trois quantités P(1/d), P(2/d) et P(3/d). Comment d serait-elle classifiée si on utilise la règle de décision de Bayes ? On décide de prolonger cette expérience, on relance cette même pièce 20 fois. Indiquer un choix à faire sur les probabilités a priori qui serait plus intéressant que l'hypothèse initiale d'équiprobabilité.

Exercice 4   La population P est un ensemble de champignons. Il y a deux classes {1,2} où 1 est la classe des champignons vénéneux. Le langage de description est constitué de l'attribut binaire volve. On dispose des informations suivantes :

classe k	1 : vénéneux	2 : comestible
P(k)	0.05	0.95
P(volve/k)	0.9	0.2

1. 
   
   Je ramasse les champignons si la règle de Bayes les classifie dans la classe des comestibles. Est-ce que je ramasse les champignons ayant une volve ? Appliqueriez-vous cette règle si vous alliez ramasser des champignons ?
2. On définit un coût pour tout couple de classes (k,i) noté cout(k,i). On définit alors le coût moyen de l'affectation à la classe k d'une description d de D par :

   coutMoyen(k/d)=

   å iÎ {1,...,c}

   cout(k,i) × P(i/d).

   
   La règle de décision du coût minimum est : Choisir C_coutmin qui à toute description d associe la classe k qui minimise coutMoyen(k/d).
   
   On définit sur notre exemple les coûts suivants :
   cout(1,1)=cout(2,2)=0 ,  cout(1,2)=2 ,  cout(2,1)=¥.
   J'utilise la règle du coût minimum. Est-ce que je ramasse les champignons ayant une volve ?

Exercice 5   On considère un problème de classification binaire, l'espace de description D étant constitué de deux descripteurs également binaires. On suppose que la répartition des descriptions dans chaque classe est conforme au tableau suivant :

d	00	01	10	11
classe 1	80	10	10	0
classe 2	0	5	15	80

On suppose que l'on ne dispose d'aucune information sur les poids respectifs des classes. Le problème de la classification ne pose aucun problème pour les descriptions 00 et 11. Mais que doit-on faire si l'on observe 01 ou 10 ?

La méthode du minimax consiste à introduire le paramètre p=Pr(classe 1), à calculer pour chaque valeur de p la règle de décision issue de la règle de Bayes. Pour chacune de ces règles, on calcule son erreur maximale. On choisit alors la règle qui minimise cette erreur maximale (d'où <<minimax >>).

Quelle est la règle de décision définie par cette procédure pour l'exemple ci-dessus ?

Exercice 6   On considère deux attributs pour déterminer la nationalité d'un individu. L'attribut taille qui peut prendre les valeurs grand ou petit, l'attribut couleur des cheveux qui peut prendre les valeurs brun ou blond. Les nationalités possibles sont français et suédois.

On suppose que les populations françaises et suédoises se répartissent selon le tableau suivant :

	petit, brun	petit, blond	grand, brun	grand, blond
Suédois	10	20	30	40
Français	25	25	25	25

1. Dans une assemblée comprenant 60% de suédois et 40% de français, décrire
   1. la règle de décision majoritaire
   2. la règle du maximum de vraisemblance
   3. la règle de Bayes
2. Calculez les probabilités d'erreur de chacune de ces règles
3. On suppose maintenant que l'on ne connaît plus les proportions respectives des suédois et des français. On note p la proportion des suédois (p Î [0,1]).
   1. Décrire, selon les valeurs possibles de p , les règles de Bayes correspondantes.
   2. Parmi les 5 règles que vous aurez détaillées à la question précédente, choisir celle qui dans le pire des cas, possède la probabilité d'erreur minimale.

Exercice 7   La population consiste en un ensemble de patients. Ces patients doivent être répartis en deux classes, la classe M (pour malade) et la classe S (pour sain). Les individus sont décrits à l'aide de deux attributs logiques T et C. L'attribut T a la valeur vrai lorsque la tension artérielle d'un patient est anormale et l'attribut C a la valeur vrai lorsque le taux de cholestérol d'un patient est anormal. On suppose que la population est un espace probabilisé et on note P la loi de probabilité. Nous allons utiliser l'approche Bayésienne classique pour classer les patients au vu de leurs descriptions. Les probabilités suivantes sont connues :

Dans ce tableau P(k) représente la probabilité qu'un élément de la population soit de classe k, P(T/k) représente la probabilité qu'un élément de classe k ait une tension artérielle anormale (T vaut vrai) et P(C/k) représente la probabilité qu'un élément de classe k ait un taux de cholestérol anormal (C vaut vrai).

Pour pouvoir calculer les probabilités nécessaires à l'application de la règle de Bayes, nous allons faire l'hypothèse supplémentaire suivante : les deux attributs sont indépendants. Cette hypothèse permet, par exemple, d'écrire que P(CÇ T / S) = P(C / S)× P( T / S).

1. Déterminer la procédure de classification C_Bayes en utilisant la règle de décision de Bayes. La donner sous forme d'un arbre de décision.
   
   
2. Soient les procédures de classification C₁ et C₂ associées aux arbres de décision t₁=S et t₂=T(M,S). Calculer les erreurs au sens de la probabilité d'erreur pour C₁, C₂ et C_Bayes.
   
   
3. Plutôt que de chercher à minimiser l'erreur au sens de la probabilité d'erreur, on peut introduire des coûts pour les mauvaises classifications. On définit un coût pour tout couple de classes (k,i) noté cout(k,i). On définit alors le coût moyen de l'affectation à la classe k d'une description d de D par :

   coutMoyen(k/d)=

   å iÎ {1,...,c}

   cout(k,i) × P(i/d).

   
   La règle de décision du coût minimum est : Choisir C_coutmin qui à toute description d associe la classe k qui minimise coutMoyen(k/d).
   
   On définit sur notre exemple les coûts suivants :
   cout(S,S)=cout(M,M)=0,   cout(S,M)=2,   cout(M,S)=1.
   Déterminer C_coutmin et la donner sous forme d'un arbre de décision.

Exercice 8   Programmer le classifieur naïf de Bayes à partir de données structurées. On utilisera les conventions du logiciel C4.5 : le programme prendra en entrée deux fichiers d'extensions data et names ; le fichier d'extension data contient autant de lignes que d'exemples, les valeurs d'attribut sont séparées par des virgules, le dernier attribut est la classe ; le fichier d'extension names contient sur la première ligne terminée par un point les valeurs possibles des classes, puis une ligne par attribut formée du nom de l'attribut, le symbole :, la liste des valeurs pour cet attribut, terminée par un point. Le résultat sera un fichier d'extension bayes contenant toutes les estimations nécessaires. Enfin, un programme naivebayes prenant en entrée une description et les fichiers utiles permettra de classer la description avec le classifieur naïf.

Exercice 9   On dispose d'un corpus de textes classés : par exemple, des courriers électroniques classés dans des dossiers, des textes de journaux classés par thème. On souhaite classer un texte en utilisant les informations du corpus. Une méthode possible est d'utiliser le classifieur de Bayes naïf. Il nous faut, auparavant, préciser le langage de description, le mode d'estimation des probabilités.

À partir du corpus de textes, on constitue le vocabulaire V qui est l'ensemble de tous les mots apparaissant dans le corpus. Le langage de description est alors l'ensemble de tous les textes possibles sur ce vocabulaire V. Par souci de simplification, un texte sera condensé en un << sac de mots >> qui est l'ensemble, avec répétition, des mots du texte. On a oublié la notion de position dans le texte et la notion relative de position d'un mot par rapport à un autre. Soit {1,...,c} l'ensemble des classes, soit t un texte (un sac de mots) à classer, le classifieur naïf de Bayes s'écrit :


L'estimation P^{^}(k) est faite par : où Card(T(k)) est le nombre de textes de classe k et Card(T) le nombre total de textes. On estime P(m/k) par : où m,T(k) est le nombre d'occurrences du mot m de V dans l'ensemble des textes de classe k et T(k) le nombre total d'occurrences de mots dans l'ensemble des textes de classe k.

Il suffit alors d'utiliser l'équation ?? pour classer un texte t. On est cependant confronté au problème suivant : si le texte t à classer contient un mot m n'apparaissant dans aucun document de classe k, la quantité P^{^}(m/k) vaut alors 0, de même que la quantité Õ_{m Î t Ç V} P^{^}(m/k) × P^{^}(k). Le classifieur de Bayes ne pourra lui attribuer la classe k, même si, par ailleurs, le texte t contient d'autres mots très fréquents dans les textes de classe k. Pour éviter ce biais, on modifie l'estimateur utilisé par : Enfin, revenons sur le choix du vocabulaire V. Plusieurs choix sont possibles:

• V est l'ensemble des mots de la langue (environ 50 000 mots en anglais) ;
• V est l'ensemble des mots du corpus d'apprentissage ;
• V est l'ensemble des mots du corpus d'apprentissage dont on retire
  1. les mots les plus fréquents qui sont souvent des mots peu signifiants pour la classification : et, le, la, ...
  2. les mots rares
• un algorithme détermine V en calculant l'ensemble des mots pertinents pour la classification (en général, en utilisant des critères basés sur le contenu en information tels que l'entropie).

Pour conclure, l'algorithme d'apprentissage pour le classifieur de Bayes naïf consiste en un calcul du dictionnaire V et en un calcul des estimations :

Phase d'apprentissage pour Bayes naïf

donnée : un ensemble T de textes classés dans des classes 1, ..., c

1. calculer le vocabulaire V à partir de T

2. pour toute classe k, calculer P^(k) en utilisant l'équation ??

3. pour toute classe k et tout mot m de V, calculer P^(m/k) en utilisant l'équation ??

Et la classification d'un texte t se fait par l'algorithme suivant :

classifieur de Bayes naïf

donnée : V, les estimations P^(k) et P^(m/k) pour tout m et tout k

entrée : un texte t

pour toute classe k, calculer Õm Î t Ç V P^(m/k) × P^(k)

sortie : la classe k qui maximise le calcul précédent

Illustration : Le but est de classer des phrases dans deux classes, selon leur thème: la radio ou la télévision. Étant donné l'échantillon :

Exemples de la classe TV :

Le programme TV n'est pas intéressant. La TV m'ennuie.

Les enfants aiment la TV

On reçoit la TV par onde radio

Exemples de la classe Radio :

Il est intéressant d'écouter la radio

Sur les ondes, les programmes pour enfants sont rares

Les enfants vont écouter la radio ; c'est rare!

et le vocabulaire pour mettre en oeuvre cette procédure de classification étant :V= TV, programme, intéressant, enfants, radio, onde, écouter, rare. Comment serait classée la phrase : J'ai vu la radio de mes poumons à la TV! ?

Exercice 10   Programmer le classifieur naïf de Bayes à partir de textes. On permettra à l'utilisateur de définir des seuils de fréquence pour la constitution du vocabulaire V. Pour constituer des bases d'exemples, vous n'avez que l'embarras du choix. Prenez par exemple des news issues de différents groupes ou recherchez sur le web la base d'exemples REUTERS.

Exercice 11   Soit l'échantillon qui correspond à un ensemble de conditions météorologiques qui permettent (P pour Positif) ou pas (N pour Négatif) la pratique du Golf :

num	Outlook	Temperature	Humidity	Windy	Class
1	sunny	81	78	false	N
2	sunny	80	90	true	N
3	overcast	83	80	false	P
4	rain	75	96	false	P
5	rain	69	75	false	P
6	rain	64	70	true	N
7	overcast	65	65	true	P
8	sunny	72	83	false	N
9	sunny	68	72	false	P
10	rain	71	74	false	P
11	sunny	75	69	true	P
12	overcast	70	77	true	P
13	overcast	85	70	false	P
14	rain	73	82	true	N

Soit les arbres de décision :

t₁=P,

t₂=Humidity(N,P),

t₃=Outlook(Humidity(N,P),P,Windy(N,P)), où les arcs sont étiquetés dans l'ordre par sunny, overcast et rain pour l'attribut Outlook, par >75 et £ 75 pour l'attribut Humidity, par true et false pour l'attribut Windy.

1. Montrer que t₃ est un arbre parfait.
2. Calculer l'erreur apparente sur l'échantillon pour les trois arbres.

Exercice 12   Soit l'échantillon suivant :

no	P1	P2	P3	Classe
1	0	V	N	A
2	1	V	I	A
3	0	F	O	B
4	1	V	N	A
5	1	V	O	A
6	1	F	N	A
7	0	F	O	B
8	0	V	I	A
9	0	F	N	B
10	1	V	I	B
11	1	F	O	A
12	1	F	I	A
13	0	V	O	B

1. Soit l'ensemble d'apprentissage constitué des exemples {1,...,9}. Construire l'arbre de décision parfait t₁ en choisissant les attributs dans l'ordre P3, P2, P1.
2. Même question avec t₂ en utilisant l'ordre P1, P2, P3.
3. Peut-on trouver un arbre de décision parfait si on considère l'ensemble d'apprentissage constitué des exemples {1,...,10} ?
4. Soit l'ensemble d'apprentissage constitué des exemples {1,...,9} et l'ensemble Test constitué des exemples {11,12,13}. Soit les arbres t₃=A et t₄=P1(B,A). Calculer l' erreur apparente sur l'ensemble d'apprentissage, l'erreur apparente sur l'ensemble Test et l'erreur apparente sur l'échantillon complet pour chacun des arbres t₁, ..., t₄.

Exercice 13   On dispose d'un échantillon de 200 patients. On sait que 100 sont malades et 100 sont bien portants. On dispose des informations suivantes :

	gorge irritée	gorge non irritée
température < 37,5	(6 bp,37 m)	(91 bp,1 m)
température ³ 37,5	(2 bp,21 m)	(1 bp,41 m)

et on considère l'arbre de décision suivant :

temperature<37.5 = oui
    gorge irritée = oui : malade
    gorge irritée = non : bien portant
temperature<37.5 = non : malade

1. Calculer, pour l'arbre donné en figure 1, les quantités : i(e), i(1), i(2), i(11), et i(12) avec la fonction de Gini.
2. Calculer, pour l'arbre donné en figure 1, les quantités : i(e), i(1), i(2), i(11), et i(12) avec la fonction entropie.
3. On considère l'arbre vide, on a le choix entre l'attribut ``Température £ 37,5'' et l'attribut ``gorge irritée''. Lequel choisit-on si on choisit l'attribut qui maximise le Gain ?

Exercice 14   On reprend l'exemple de l'exercice ??. On suppose que les attributs Temperature et Humidity ont été discrétisés par un expert de la façon suivante : les températures inférieures ou égales à 70 (cool), celles supérieures à 70 et inférieures ou égales à 80 (mild), celles supérieures à 80 (hot) ; le taux d'humidité inférieur ou égal à 75 (normal) et supérieur à 75 (high). On initialise l'arbre à l'arbre réduit à la seule feuille P. On utilise la fonction entropie. Récursivement on remplace une feuille de l'arbre par le test qui maximise le gain. Construire l'arbre de décision associé à notre échantillon.

Quelles méthodes pourraient être envisagées pour que l'algorithme discrétise automatiquement les attributs Temperature et Humidity ?

Exercice 15   Même exercice en considérant que num est un descripteur. Quel problème rencontre-t-on ? L'utilisation de la fonction GainRatio permet-elle de résoudre le problème ?

Exercice 16   On dispose d'un échantillon de 200 individus. On sait que 100 sont de classe 1 et 100 sont de classe 2. Le langage de représentation utilise deux attributs binaires A et B. On dispose des informations suivantes :

	A vrai	A faux
B vrai	(0,50)	(50,0)
B faux	(50,0)	(0,50)

Appliquer l'algorithme de base avec la fonction entropie, quel problème rencontre-t-on ? Doit-on s'arrêter ? Choisir un attribut et poursuivre la construction de l'arbre, que remarque-t-on ?

Supposons maintenant que le langage de description contienne non seulement les attributs A et B mais aussi d'autres attributs C, ..., Z. Que va-t-on obtenir en appliquant l'algorithme de base ? Pourrait-on remédier à cette situation ?

Exercice 17   Une banque dispose des informations suivantes sur un ensemble de clients:





L'attribut ternaire M décrit la moyenne des montants sur le compte client. Le second attribut ternaire A donne la tranche d'âge du client. Le troisième attribut ternaire R décrit la localité de résidence du client. Le dernier attribut binaire E a la valeur oui si le client a un niveau d'études supérieures. La classe associée à chacun de ces clients correspond au contenu de la colonne I. La classe oui correspond à un client qui effectue une consultation de ses comptes bancaires en utilisant Internet.

1. Utiliser le classifieur naïf de Bayes sur l'ensemble test T donné ci-après.
2. Construire l'arbre de décision en utilisant la fonction gain basée sur l'entropie. Calculer les performances sur l'ensemble test T.

Exercice 18   On considère un espace de description comprenant les trois attributs forme, taille et couleur prenant respectivement les valeurs rond et carré, petit et grand, bleu, blanc et rouge. L'attribut cible est binaire de valeurs oui et non.

Les données disponibles sont les suivantes (le ? correspond à une valeur manquante) :

Valeur majoritaire de l'attribut

On remplace les valeurs manquantes par la valeur majoritaire prise par cet attribut sur l'échantillon complet. Quelle valeur associe-t-on sur notre échantillon ? Peut-on trouver un arbre de décision parfait ? Appliquer l'algorithme de construction d'arbre de décision en utilisant l'entropie pour le calcul du gain. On décide qu'un noeud est terminal, i.e. d'attribuer une feuille, lorsqu'il y a au plus un exemple mal classé associé à ce noeud. Vous détaillerez les calculs pour le test à choisir en racine de l'arbre.

Valeur majoritaire de l'attribut par classe

Étant donné un exemple avec une valeur manquante, on remplace la valeur manquante par la valeur majoritaire prise par l'attribut correspondant pour les exemples de l'échantillon appartenant à la même classe. Quelles valeurs associe-t-on sur notre échantillon ? Peut-on trouver un arbre de décision parfait ? Quel arbre obtient-on en appliquant l'algorithme basé sur l'entropie ?

Méthode utilisée par C45

Cette méthode consiste à ne plus attribuer une valeur à l'attribut mais une probabilité pour chacune des valeurs possibles. Ces probabilités sont estimées par les fréquences des valeurs possibles de cet attribut pour l'échantillon associé à une position p de l'arbre en construction. Par exemple, à la racine, la probabilité que l'attribut taille ait la valeur petit est de 3/8 car il y a 8 exemples pour lesquels la valeur de l'attibut taille est connue et 3 ont la valeur petit. Quelles seraient les modifications à apporter à l'algorithme ?

Exercice 19   On considère les données suivantes :

1. On suppose que les individus sont décrits par le seul attribut poids. On suppose également que les probabilités peuvent être estimées à l'aide des fréquences calculées à partir du tableau de données. Reproduire et compléter le tableau suivant :
   

   	classe k
   Estimations	0	1
   P(k)
   P(léger/k)
   P(moyen/k)
   P(lourd/k)

   
   Décrire les procédures de classification associées à la règle majoritaire, à la règle du maximum de vraisemblance et à la règle de Bayes.
   
   
2. On suppose maintenant que les individus sont décrits à l'aide des quatre attributs cheveux, taille, poids et crème solaire. Construire l'arbre de décision produit par l'algorithme d'apprentissage par arbre de décision en utilisant la fonction Entropie et la fonction gain associée. Détailler les calculs pour le choix de la racine.
3. Déduire de l'arbre trouvé à la question précédente un système à base de règles. Montrer qu'une condition d'une des règles peut être supprimée tout en conservant la cohérence avec les données. Le système obtenu peut-il s'écrire sous forme d'un arbre de décision ?

Exercice 20   On dispose d'une pièce biaisée. On appelle p la probabilité qu'elle tombe sur pile. On lance cette pièce n fois. On obtient r piles. L'expérience de lancer n fois cette pièce peut être réalisée à souhait. On s'attend à obtenir différentes valeurs de r. Soit R la variable aléatoire de valeur le nombre r de piles obtenu en n lancers. On s'intéresse à la probabilité d'obtenir R=0 Pile en n lancers, à la probabilité d'obtenir R=1 Piles en n lancers, ..., à la probabilité d'obtenir R=n Piles en n lancers.

1. Soit p=1/4 et n=3, expliciter les quantités Pr(R=0), Pr(R=1), Pr(R=2) et Pr(R=3).
2. Soit p et n quelconques, expliciter Pr(R=r) en fonction de p et n. Une telle loi est la loi binomiale de paramètres n et p
3. On dispose de tables pour calculer les valeurs. Par exemple, pour p=1/4 et n=13, les probabilités obtenues arrondies à deux décimales sont :
   
   

   0	1	2	3	4	5	6	7	8	9,13
   0,02	0,11	0,20	0,25	0,21	0,13	0,06	0,01	0,01	0

   
   Faîtes une représentation graphique. Quelle est la probabilité d'obtenir un nombre de piles inférieur ou égal à 5 en 13 lancers avec une pièce de proba 1/4 pour pile ?
   
   
4. Vous lancez 20 fois une pièce dont la probabilité d'obtenir pile est 1/4, combien de piles vous attendez vous à obtenir ? Cette notion est capturée par la notion d'espérance mathématique (<< expected value >> en anglais). L'espérance mathématique d'une variable aléatoire discrète X est définie par :

   E(X)=S

   w Î W

   X(w) P(w)

   L'espérance d'une loi binomiale X de paramètres n et p est E(X)=np
   
   
5. Vous lancez 20 fois une pièce dont la probabilité d'obtenir pile est 1/4, vous vous attendez à obtenir 5 piles mais êtes conscients que des variations entre le nombre de piles obtenu et le nombre attendu sont possibles. La variance et l'écart-type vont permettre de mesurer ceci. La variance d'une variable aléatoire discrète X est définie par :
   V(X)=E((X-E(X))²)
   et représente l'erreur quadratique attendue entre valeur observée et valeur attendue. L'écart-type est la racine carrée de la variance :
   s(X)=s_X=V(X)
   La variance d'une loi binomiale X de paramètres n et p est V(X)=np(1-p) et l'écart-type est s_X=np(1-p). Calculez espérance mathématique, variance et écart-type dans les cas suivants :
   • p=1/4 et n=20 ;
     
     
   • p=1/4 et n=40 ;
   • p=1/4 et n=100 ;
   • p=1/4 et n=400.

Exercice 21   problème de l'estimation de l'erreur Nous sommes dans un univers U, une loi de probabilité fixée mais inconnue existe sur U, on a une cible f, le système d'apprentissage a fourni une hypothèse h d'un ensemble d'hypothèses H. On dispose également d'un ensemble test T de n exemples tiré selon la loi de probabilité sur l'univers indépendamment de h (et donc de l'ensemble d'apprentissage). On souhaite estimer l'erreur réelle de h qui est la probabilité que h et f diffèrent sur un exemple tiré avec la probabilité sur U.

1. T contient n=100 exemples, h fait r=25 erreurs, quelle est votre estimation de l'erreur réelle ? T contient n=500 exemples, h fait r=130 erreurs, quelle est votre estimation de l'erreur réelle ? À laquelle de ces deux estimations faîtes vous le plus confiance ? Le but de ce travail est de préciser et de quantifier votre << bon sens >>.
2. soit p=e(h) l'erreur réelle de h. Soit X la variable aléatoire qui a pour valeur le nombre d'exemples mal classifiés lorsque l'on tire un ensemble test T de n exemples. Montrer que X suit une loi binomiale.
3. soit r le nombre d'erreurs sur T. L'erreur estimée est r/n. Cette estimation r/n de p donne-t-elle en moyenne la bonne estimation ? Pour cela, on définit : Le biais d'estimation d'un estimateur Y de p est la quantité E(Y)-p. Si ce biais est 0, on dit que Y est un estimateur sans biais de p. Soit Y la variable aléatoire de valeur l'erreur estimée r/n. Montrer que Y est un estimateur sans biais de p. Note : Cet estimateur est sans biais car nous avons fait des hypothèses d'indépendance entre T et h.
4. On s'intéresse maintenant à la variance et l'écart-type de cet estimateur. En utilisant le fait que X est une loi binomiale, variance et écart-type pour une loi binomiale, le fait que n est constant, on obtient que la variance de l'erreur estimée est V(Y)=p(1-p)/n et que l'écart-type de l'erreur estimée est s_Y=p(1-p)/n. Ne connaissant pas p, nous le remplaçons par sa valeur estimée r/n, nous obtenons une estimation de l'écart-type pour l'erreur estimée :

   sY ~	r/n(1-r/n) n

   Calculez l'erreur estimée et l'écart-type dans les cas suivants :
   
   
   • n=20 et r=4 ;
   • n=100 et r=25 ;
   • n=200 et r=48 ;
   • n=500 et r=130.
   
   
5. L'inégalité de Bienaymé-Tchebychev valable pour toute variable aléatoire X d'espérance E(X) et d'écart-type s_X s'énonce :

   Pr(|X-E(X)|£ k sX) ³ 1-

   1 k2

   pour k³ 1

   
   Utilisez cette inégalité pour déterminer le nombre d'exemples à tirer pour que l'erreur estimée ne s'écarte pas de plus de 5% de l'erreur réelle avec une confiance de 99%. On utilisera le fait que s_Y £ 1/n. Même question avec pas de plus de 5% de l'erreur réelle avec une confiance de 96%. Interprétez l'inégalité lorsque l'on fait tendre le nombre d'exemples vers l'infini.
   
   

Exercice 22   Nous avons un moyen d'estimer l'erreur. Une façon usuelle de quantifier la précision associée à une estimation consiste à définir un intervalle dans lequel on espère trouver la valeur réelle ainsi que la probabilité que la valeur réelle soit dans cet intervalle. Un intervalle de confiance à N% pour un paramètre p est un intervalle qui avec une probabilité de N% contient p. Le but fixé est de déterminer des intervalles de confiance pour l'erreur réelle p=e(h). Tout d'abord, nous connaissons la loi binomiale qui gouverne l'erreur estimée r/n et donc l'espérance de cette loi (p) et l'écart-type (voir exercice précédent). Par conséquent, pour trouver un intervalle de confiance à 95% de l'erreur réelle, il suffit de trouver un intervalle de centre p qui contient r/n avec une probabilité supérieure ou égale à 95% ou de façon équivalente un intervalle de centre r/n qui contient p avec une probabilité supérieure ou égale à 95%. Pour une valeur donnée de N, comment calculer la taille d'un tel intervalle ? Les calculs étant trop difficiles pour une loi binomiale, nous allons utiliser des approximations par une loi normale.

La loi normale est un exemple de loi continue. La loi normale de paramètres m et s est définie par la densité de probabilité : L'espérance d'une loi normale de paramètres m et s est m et son écart-type est s. Construire la représentation graphique de la fonction de densité de la loi normale de paramètres 0 et 1. Le théorème central limite permet d'affirmer que, pour n assez grand, on peut approximer une loi binomiale par une loi normale de même espérance et de même écart-type.

Pour une loi normale, il existe des tables permettant de calculer le rayon des intervalles de confiance. En effet, si X suit une loi normale d'espérance m et d'écart-type s, alors la valeur mesurée x de X appartient avec une probabilité de N% à l'intervalle [m-z_N s,m+z_N s] ou de façon équivalente, m appartient avec une probabilité de N% à l'intervalle [x-z_N s,x+z_N s] où z_N peut être déterminé à l'aide des tables suivantes :


En conclusion, en utilisant l'approximation faite dans le calcul de l'écart-type et en supposant n assez grand pour admettre l'approximation de la loi binomiale par une loi normale, nous obtenons le résultat suivant : avec une probabilité de N%, l'erreur réelle de h appartient à l'intervalle
Nous allons utiliser ces résultats pour les questions suivantes :

1. Déterminez les intervalles de confiance dans les cas suivants :
   • n=100, r=25 et N=90 ;
   • n=100, r=25 et N=95 ;
   • n=200, r=48 et N=95 ;
   • n=500, r=130 et N=95.
2. On sait que l'erreur est inférieure à 40%. On souhaite déterminer une approximation de l'erreur réelle à 0.05 près avec une confiance de 95%. Combien d'exemples faut-il tirer ? Même question avec une confiance de 98%.
3. Dans certains cas, seule une borne supérieure sur l'erreur réelle est souhaitée. Déterminer l'intervalle de confiance pour n=100, r=25 et N=90 ; quelle est la confiance pour l'intervalle [0,b] où b est la borne supérieure de l'intervalle trouvé précédemment ? Déterminez les intervalles de confiance de la forme [0,b] dans les cas suivants :
   • n=100, r=25 et N=90 ;
   • n=100, r=25 et N=99 ;
   • n=200, r=48 et N=95 ;
   • n=500, r=130 et N=97,5.

Nous avons donc démontré que la loi qui gouverne le problème de l'estimation de l'erreur sur un ensemble test suit une loi binomiale. Nous pouvons alors calculer des intervalles de confiance pour l'erreur réelle. Pour cela, nous avons effectué les deux approximations suivantes :

• Remplacer l'erreur réelle par l'erreur estimée dans le calcul de l'écart-type,
• Approximer la loi binomiale par une loi normale. Cette approximation n'a de sens que lorsque : n³ 30 et np(1-p) ³ 5.

Pour des problèmes pour lesquels les échantillons disponibles ne permettent pas de découper en apprentissage et test, on utilise des techniques telles que la validation croisée. D'autres problèmes intéressants n'ont pas été traités ici tels que :

• Pour un même problème, deux systèmes d'apprentissage (par exemple l'un utilise les arbres de décision et l'autre un réseau de neurones) produisent deux hypothèses. comment comparer les deux hypothèses ? Voir exercice ??.
• Comment comparer deux systèmes d'apprentissage ?

Exercice 23  

1. On réalise une expérience dont le résultat dépend d'une épreuve aléatoire. On observe les données suivantes :
   
   0,0,1,2,0,0,0,0,1,3,13,0,0,0,2,0,0,0,0,1.
   
   Que peut-on dire ?
2. On poursuit l'expérience, on observe les données suivantes :
   
   2,0,0,1,0,0,1,3,40,0,1,1,0,0,0,0,0,0,1,1.
   
   Que peut-on dire ?
3. Sachant que P(n) = 6/p² × 1/(n+1)² et que X(n)=n+1, déterminer l'espérance mathématique de X.

Exercice 24   On souhaite dans cet exercice comparer des hypothèses générées par différents systèmes d'apprentissage pour un même problème. La table permettant de calculer, à l'aide de la loi normale, les intervalles de confiance est :

1. Pour un problème d'apprentissage, à l'aide d'un générateur de réseaux de neurones, on a généré une hypothèse h₁. On estime l'erreur réelle pour cette hypothèse à l'aide d'un échantillon test S₁ de taille n₁=200. Cette hypothèse fait r₁=60 erreurs sur l'échantillon test. Déterminer un intervalle de confiance à 95% centré autour de l'erreur estimée. Déterminer un intervalle de confiance à 95% de la forme [0,b].
2. Pour le même problème d'apprentissage, à l'aide d'un générateur d'arbres de décision, on a généré une hypothèse h₂. On estime l'erreur réelle pour cette hypothèse à l'aide d'un échantillon test S₂ de taille n₂=500. Cette hypothèse fait r₂=125 erreurs sur l'échantillon test. Déterminer un intervalle de confiance à 95% centré autour de l'erreur estimée. Déterminer un intervalle de confiance à 95% de la forme [0,b].
3. On souhaite comparer les hypothèses h₁ et h₂. On appelle p₁ l'erreur réelle de h₁ et p₁^{^} l'erreur estimée de h₁ sur S₁. De même, on appelle p₂ l'erreur réelle de h₂ et p₂^{^} l'erreur estimée de h₂ sur S₂. On considère alors la quantité d=p₁ - p₂ et son estimateur d^{^}= p₁^{^}-p₂^{^}. On suppose que les échantillons S₁ et S₂ sont indépendants. On peut alors montrer que d^{^} est un estimateur non biaisé de d (i.e. son espérance est d) et que d^{^} peut être approximée, sous les hypothèses usuelles, par une loi normale de variance la somme des variances de p₁^{^} et p₂^{^}. On rappelle que la variance pour p₁^{^} peut être approximée par r₁/n₁(1-r₁/n₁)/n₁. Calculer une approximation de la variance et de l'écart type de d^{^}. Calculer un intervalle de confiance à 95% centré autour de d^{^} pour la différence d entre les erreurs réelles.
4. Déterminer la probabilité que h₁ soit meilleure que h₂, soit encore la probabilité que d>0.

Exercice 25   Une méthode d'élagage peu orthodoxe La méthode classique d'apprentissage par arbres de décision consiste à construire un arbre à l'aide d'un échantillon d'apprentissage puis à l'élaguer à l'aide d'un échantillon test. L'idée sous-jacente est que la phase d'élagage doit permettre d'améliorer l'erreur réelle et que seul l'échantillon test permet de l'estimer de manière à peu près fiable.

Mais cette idée ne vaut que si l'on dispose de suffisamment d'exemples pour la première phase : un arbre dont l'erreur est catastrophique ne donnera jamais de bons résultats, quelque soit l'élagage qu'on lui fera subir !

Une idée récurrente consiste à apprendre avec tous les exemples disponibles et à élaguer avec ces mêmes exemples. Mais cette idée ne peut fonctionner qu'à condition de ne pas se baser sur l'erreur apparente calculée sur l'ensemble d'apprentissage pour estimer l'erreur réelle.

Quinlan propose la méthode suivante dans C4.5 :

On introduit un paramètre de confiance CF (par défaut, ce paramètre vaut 25%). Pour chaque feuille de l'arbre, notons N le nombre d'exemples qu'elle couvre et E le nombre d'erreurs de classification qu'elle induit dans l'échantillon. Soit p la probabilité pour qu'un nouvel exemple soit mal classé par cette feuille. La quantité E/N est donc un estimateur de p. Pour tenir compte du fait que l'arbre construit n'est pas indépendant des données, nous allons supposer que cet estimateur est très optimiste.

Plus précisément, soit E_p une variable aléatoire de loi binomiale de paramètres (N,p). C'est-à-dire que
Nous posons p(E,N) = max{p | Pr(E_p £ E) ³ CF}. Nous prendrons p(E,N) comme valeur estimée de l'erreur réelle pour cette feuille.

Exemple :

supposons qu'une feuille couvre N=4 exemples et supposons qu'elle induise une erreur (E=1). On prend CF=25%. On a :
Pour cet exemple, on trouve p ~ 0,54. Autrement dit, on estime par ce procédé l'erreur réelle pour cette feuille à 54% (au lieu des 25% fournis par l'erreur apparente).

Le reste est plus classique : on calcule l'erreur réelle estimée d'un arbre en faisant une somme pondérée des erreurs réelles estimées de ses fils.

Par exemple, si un noeud A a trois fils A1, A2 et A3, si le nombre d'exemples couverts par chacun de ces fils est respectivement de N1, N2 et N3, et si les erreurs réelles estimées pour chacun de ces fils sont e1, e2 et e3 alors l'erreur réelle estimée de A sera de (N1e1+N2e2+N3e3)/(N1+N2+N3).

Pour élaguer un arbre, on applique l'algorithme suivant :


Tant qu'il existe un sous-arbre que l'on peut remplacer par une feuille sans faire croître l'erreur réelle estimée alors élaguer ce sous-arbre.

Application :

On considère un espace de description comprenant deux attributs adoption et education pouvant prendre chacun trois valeurs : y, n et u. On suppose que l'attribut cible est binaire et que ses valeurs sont A et B.

On considère l'arbre suivant :

adoption = y : A (0;151)
adoption = u : A (0;1)
adoption = n :
   education = n : A (0;6)
   education = y : A (0;9)
   education = u : B (0;1)

Chacun des couples (0 ; 151), ..., est de la forme (E;N).

On donne p(0;6)=0,206 ; p(0;9)=0,143 ; p(0;1)=0,750 ; p(1;16)=0,159 ; p(0;151)=0,009 ; p(1;168)=0,016.

1. Calculez l'erreur réelle estimée pour l'arbre

   
   adoption = n :
      education = n : A (0;6)
      education = y : A (0;9)
      education = u : B (0;1)
   

2. Calculez l'erreur réelle estimée pour l'arbre complet
3. Peut-on élaguer le sous-arbre de racine adoption = n
4. Peut-on remplacer l'arbre entier par une feuille ?
5. Après élagage, quelle est l'erreur réelle estimée ?

Exercice 26   Simuler l'algorithme d'apprentissage par correction d'erreur du perceptron linéaire à seuil de la fonction booléenne OU pour différentes valeurs d'initialisation du vecteur de poids (voir exemple ??) : on prendra, par exemple, les valeurs suivantes :

• w₀ =0 ; w₁ =0 ; w₂ = 0,
• w₀ =1 ; w₁ =1 ; w₂ = 1,
• w₀ =1 ; w₁ =-1 ; w₂ = 1.

Exercice 27   Même exercice avec la fonction ET.

Exercice 28   Même exercice avec la fonction XOR. Faîtes les remarques qui s'imposent !

Exercice 29   Reprendre l'exemple ?? avec le même échantillon d'entrée S et les valeurs initiales : w₀ =0 ; w₁ =0 ; w₂ = 0. Simuler ensuite l'apprentissage en considérant l'échantillon S È {((3,1),0)}.

Exercice 30   Implémenter l'algorithme de Widrow Hoff pour une cellule à 2 entrées. Tester cet algorithme sur les données de l'exemple ??. Vous étudierez le nombre d'itérations nécessaires. Vous essaierez différentes valeurs du paramètre e.

Exercice 31   Implémenter l'algorithme du gradient pour une cellule à 2 entrées. Choisir une fonction linéaire de deux variables et un échantillon d'apprentissage. Comparer les deux algorithmes, en particulier, la vitesse de convergence.

Exercice 32   Choisir une fonction linéaire de deux variables et un échantillon d'apprentissage de 100 exemples. Apporter du bruit de classification en changeant la classe de 10 exemples. Étudier le comportement de l'algorithme de Widrow Hoff.

Exercice 33  

Une classe C désigne un sous-ensemble de {0,1}ⁿ. On dit qu'une classe C est reconnaissable par perceptron s'il existe un perceptron tel que

1. Démontrer que les classes suivantes sont reconnaissables par perceptron.
   
   
   1. C est l'ensemble des vecteurs dont au moins m entrées sont à 1.
   2. C est l'ensemble des vecteurs dont au plus m entrées sont à 1.
   3. C est l'ensemble des vecteurs tels qu'il y ait plus d'entrées à 1 dans la partie droite de la rétine que dans la partie gauche (on suppose que la rétine est linéaire et que la partie droite (resp. gauche) est formée des entrées x_i telles que i > n/2 (resp. i £ n/2)).
   
   
2. Une méthode pour montrer que deux classes ne sont pas linéairement séparables : trouver p exemples x^®₁, ..., x^®_p de la première et p exemples y^®₁, ..., y^®_p de la seconde tels que å_i x^®_i = å_i y^®_i. Montrer que cette méthode est correcte. Doit-on supposer que les exemples choisis dans chacune des deux classes sont distincts ? Pourquoi ?
   
   
3. Montrer que les classes suivantes ne sont pas reconnaissables par perceptron.
   
   
   1. C est l'ensemble des vecteurs tels que les entrées à 1 (s'il en existe) sont contigues. On suppose que n³4 et que la rétine est linéaire. C est donc la classe des figures connexes.
      
      
   2. C est l'ensemble des vecteurs symétriques par rapport au centre de la rétine (on suppose encore que la rétine est linéaire et que n > 2).
      
      
   3. C est l'ensemble des vecteurs dont m entrées exactement sont égales à 1 (avec 1 £ m < n).

Exercice 34  

On considère des descriptions qui sont des couples (X,Y) où X et Y sont des réels positifs. Le problème est un problème de classification binaire. On dispose d'un échantillon qui sera représenté graphiquement par des points labellés par un + pour les exemples positifs, par un - pour les exemples négatifs.

1. Soit l'échantillon donné par l'exemple 1 de la figure ci-dessous. Déterminer un arbre décision binaire qui classifie correctement cet échantillon. Les tests qui labellent les noeuds de décision seront de la forme X<m avec m entier (ou Y<m). Peut-on trouver un perceptron à entrées réelles pour classifier cet échantillon ?
   
   
2. Même question avec l'exemple 2.
   
   
3. Quelle critique peut-on faire aux arbres de décision au vu du second exemple ? Comment pourrait-on essayer d'y remédier ? Quelle critique peut-on faire aux perceptrons au vu du premier exemple ? Construire un réseau de neurones à couches cachées qui calcule la fonction de classification correspondant à l'arbre de décision trouvé en 1 (le procédé de construction doit pouvoir se généraliser).

---

Figure 4.1 : Exemples

---

Exercice 35   Le modèle de perceptron étudié par Rosenblatt, Minski et Papert est un peu plus compliqué que celui qui a été présenté dans le cours. Ces auteurs supposent qu'entre la rétine (les cellules d'entrées) et la cellule de décision (cellule de sortie) se trouvent un certain nombre de cellules d'association. Ces cellules intermédiaires effectuent un traitement préliminaire sur certaines cellules de la rétine et transmettent le résultat de ce traitement à la cellule de décision. Les sorties des cellules d'association constituent une nouvelle rétine qui représentent les entrées de la cellule de décision.

Les cellules d'association peuvent calculer a priori n'importe quelle fonction booléenne. Mais si l'on ne restreint pas les traitements qu'elles peuvent effectuer, le modèle du perceptron perd tout son intérêt puisque toute fonction booléenne est disponible directement. Une manière naturelle de restreindre les cellules d'association est de considérer qu'elles ne peuvent dépendre que d'un petit nombre de cellules de la rétine. On peut par exemple supposer que les cellules d'association ne peuvent dépendre que d'au plus d cellules de la rétine (perceptron à ``domaine borné'') ou, dans un contexte géométrique, qu'elles ne peuvent dépendre que de cellules de la rétine au plus distantes de d (perceptron à ``diamètre limité''). Plus précisément, dans le cas d'une rétine rectangulaire, on définira la distance de deux cellules définies par leurs numéros de lignes et de colonnes par d((l,c),(l',c')) = |l-l'|+|c-c'|.

---

Figure 4.2 : Un perceptron à domaine borné (d=2) qui reconnaît si une cellule et une seule est active

---

1. On suppose dans les questions ci-dessous que la rétine est linéaire.
   1. Montrer qu'un perceptron à domaine borné (avec d=2) peut reconnaître des figures symétriques par rapport au centre de la rétine.
      
      
   2. Montrer qu'un perceptron à diamètre limité (avec d=1) peut reconnaître des figures connexes.
      
      
   3. Montrer qu'un perceptron à domaine borné (avec d=2) peut reconnaître les entrées possédant exactement m cellules actives. On pourra s'inspirer de l'exemple ci-dessus.
   
   Cette extension semble intéressante puisque des fonctions ``naturelles'' qui ne sont pas calculables dans le modèle de base le deviennent avec cette variante. Malheureusement, on peut montrer que le gain n'est pas aussi important que les résultats précédents pourraient le laisser espérer.
   
   
2. Montrer qu'aucun perceptron à diamètre limité ne peut reconnaître les figures connexes (c'est-à-dire dont les entrées à 1 forment un seul morceau) sur une rétine rectangulaire.
   
   Indication : Supposer qu'un perceptron à diamètre limité d peut reconnaître les figures connexes et considèrer, sur une rétine rectangulaire de dimension au moins 5x(d+2), les quatre figures suivantes (où les entrées à 1 sont figurées en noir) :
   
   

   ---

   
   
   

   Figure 4.3 : Aucun perceptron à diamètre limité ne peut apprendre la connexité

   
   

   ---

Exercice 36  

• Montrer qu'il existe un perceptron qui différencie les chiffres pairs des chiffres impairs lorsqu'ils sont écrits sur une rétine à 7 leds (voir exemple ??).
• On veut apprendre à distinguer la classe des chiffres représentés par un système de 7 leds (allumés ou éteints) de la classe des non-chiffres. Est-ce possible avec un perceptron ?

Exercice 37   Soit la fonction booléenne définie par :


Déterminez un perceptron linéaire à seuil pour chacun des trois monômes de f, puis déterminez un PMC calculant f.

Exercice 38   démontrez le théorème ??.

Exercice 39   La fonction parité sur n variables x₁,...,x_n est définie par : la fonction vaut 1 si le nombre d'entrées à 1 est pair.

1. La fonction parité est-elle calculable par un perceptron linéaire à seuil ?
2. On considère maintenant le modèle du perceptron multi couches (PMC) où le neurone élémentaire est un perceptron linéaire à seuil. Donner la forme normale disjonctive de la fonction parité pour n=3 et n=4. Proposer une méthode qui permet de définir un PMC pour la fonction parité en utilisant la forme normale disjonctive de la fonction. Donner le PMC obtenu pour n=3. Donner le nombre de couches et le nombre de neurones (en fonction de n) par couche obtenu par cette méthode pour la fonction parité.
3. Déterminer un PMC à une couche cachée calculant la fonction parité en vous basant sur l'indication suivante : faire en sorte que la i-ème cellule de la couche cachée retourne 1 si au moins i cellules de la rétine sont à 1. Donnez le PMC obtenu pour n=3. Donner le nombre de couches et le nombre de neurones (en fonction de n) par couche obtenu par cette méthode et comparer avec la méthode précédente.

Exercice 40   Pour un problème de classification, il a été décidé d'utiliser des réseaux de neurones. Il a été choisi d'utiliser une architecture multi couches avec une couche cachée et l'algorithme de rétropropagation du gradient. Il a été décidé de comparer les résultats sur les trois choix suivants :

• deux neurones dans la couche cachée,
• quatre neurones dans la couche cachée,
• six neurones dans la couche cachée.

L'échantillon d'apprentissage A contient 1000 exemples, l'échantillon test T contient 500 exemples. Avec la première architecture, on a produit un PMC h₁, avec la seconde un PMC h₂ et avec la troisième un PMC h₃. Les performances d'un classifieur h sur un ensemble S sont données par un tableau de la forme:

où a est le nombre d'éléments de classe 0 qui sont classés 0 par h, b est le nombre d'éléments de classe 1 qui sont classés 0 par h, c est le nombre d'éléments de classe 0 qui sont classés 1 par h et d est le nombre d'éléments de classe 1 qui sont classés 1 par h.

1. En utilisant les tableaux de performance donnés en fin d'énoncé, déterminer l'erreur sur l'ensemble d'apprentissage A et l'erreur réelle estimée sur T pour chacun des trois PMC h₁, h₂ et h₃.
2. En utilisant la table permettant de calculer les intervalles de confiance, déterminer les intervalles de confiance à 95% centrés autour de l'erreur estimée pour chacun des trois PMC. Déterminer les intervalles de confiance à 95% de la forme [0,b] pour chacun des trois PMC.
3. Laquelle des trois architectures vous semble la mieux adaptée au problème ? Comment expliquer les résultats obtenus pour les erreurs réelles et estimées pour les trois architectures ?

Exercice 41   Ecrire l'algorithme de rétropropagation du gradient dans un langage de programmation

Exercice 42   Modifier l'algorithme de rétropropagation du gradient pour considérer le cas de cellules élémentaires utilisant la fonction th à la place de la fonction sigmoïde.

Exercice 43   On utilise la fonction sigmoïde. On souhaite pénaliser les poids élevés. Pour cela, on modifie la fonction d'erreur en introduisant un terme qui pénalise les poids élevés. On utilise donc la fonction E définie par : Modifier l'algorithme de rétropropagation du gradient en conséquence.

Exercice 44   Les chiffres sont souvent représentés sur les écrans par une combinaison de 7 leds (Light Emiting Diode) qui peuvent être allumés ou éteints. Nous associons à chacun de ces leds un attribut binaire en posant qu'il prend la valeur 1 si le led correspondant est allumé et 0 s'il est éteint.

---

Figure 4.4 : Représentation des chiffres par 7 leds

---

La population est l'ensemble des 10 chiffres P = {0,1,2,3,4,5,6,7,8,9}, l'ensemble des descriptions est le sous ensemble de D= {0,1}⁷ qui correspond aux descriptions des chiffres de P. Nous nous intéressons au problème de classification des chiffres selon qu'ils sont premiers ou non. Les deux classes sont donc les ensembles de descriptions associés aux deux ensembles P={2,3,5,7} et P = {0,1,4,6,8,9}. La classe des chiffres premiers sera notée P ou 1, l'autre classe sera notée P ou 0.

Règles de choix des fonctions de classement

On suppose que chaque chiffre est décrit par le seul led l₄. Décrire les procédures de classification associées à la règle majoritaire, à la règle du maximum de vraisemblance et à la règle de Bayes. Calculez les erreurs réelles associées aux trois procédures trouvées.

Apprentissage par arbres de décision

1. On suppose que les chiffres sont décrits par les sept leds. Construire l'arbre de décision produit par l'algorithme d'apprentissage par arbre de décision en utilisant la fonction Entropie et la fonction gain associée. Vous ne détaillez que les calculs dignes d'intérêt. On poursuit les calculs jusqu'à obtenir un arbre parfait.
   
   
2. On suppose que le led l₁ tombe en panne (sa valeur est donc 0 pour tous les chiffres). Comment l'arbre précédent classe t-il les 10 chiffres ? Quelle est l'erreur (réelle) de ce classement.

Apprentissage par réseaux de neurones

1. A partir de l'arbre de décision trouvé précédemment , construire un réseau de neurones multicouches qui classifie les chiffres premiers.
2. Déterminer un perceptron à trois entrées correspondant aux leds l₁, l₂ et l₆ qui classifie les chiffres premiers.
3. Existe-t-il un perceptron à 7 entrées (les valeurs des 7 leds) qui soit capable de classifier d'une part les entrées correspondant à des chiffres, d'autre part celles qui ne correspondent pas à des chiffres ?