Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP, les autres candidats effectuant simultanément la composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.
Arbres de classification d'arbres
Le sujet comporte 12 pages.
Vue d'ensemble du sujet.
Ce sujet porte sur la réalisation d'arbres d'identification des plantes basés sur des observations morphologiques. À partir d'une base de connaissance botaniste, il s'agit de réaliser un arbre dont les feuilles sont des diagnostics (typiquement des noms d'espèce) et les nœuds des caractères morphologiques (par exemple la couleur des fleurs). Un nœud a autant de fils que le caractère a de valeurs possibles (jaune, bleue, etc.).
Étant donnée une base de connaissance, il s'agit de construire un arbre dont la hauteur moyenne est la plus petite possible, ce qui revient à minimiser le nombre moyen d'observations nécessaires pour identifier une plante. La difficulté revient donc à choisir à chaque étape le caractère le plus discriminant, c'est-à-dire celui qui va le mieux séparer l'espace de recherche.
Pour tenir compte de la diversité au sein d'une espèce, nous adoptons une approche probabiliste basée sur un raisonnement bayésien : la valeur d'un caractère morphologique pour une espèce donnée sera probabiliste. Par exemple, la couleur des fleurs d'une certaine espèce pourra être bleue ou jaune, avec certaines probabilités.
La partie I introduit les éléments de raisonnement bayésien nécessaires à la construction des arbres. La partie II propose une approche par énumération pour générer un arbre qui minimise la hauteur moyenne. La partie III propose une heuristique basée sur l'entropie de Shannon pour éviter la construction de tous les arbres. La partie IV revient sur le calcul exact en proposant une optimisation permettant de réduire l'espace de recherche. Les parties III et IV sont indépendantes l'une de l'autre. Enfin, la partie V propose une approche logique pour étendre la notion de caractère. Cette dernière partie ne dépend que de la première.
Rappels de probabilités
Une mesure sur un ensemble fini est une fonction . Sa masse est la quantité . Une mesure de masse 1 est appelée une distribution de probabilité, ou simplement distribution. On note l'ensemble des distributions sur l'ensemble fini . Pour , la dirac en , notée , est la distribution qui associe à le poids 1 , et zéro à tous les autres éléments. Étant donnés une famille de distributions et des poids tels que 1 , on note la distribution telle que pour tout .
Si est un ensemble, on notera l'ensemble de ses parties.
Rappels d'OCaml
Dans le reste du sujet, on pourra utiliser les fonctions suivantes de la bibliothèque standard OCaml pour les listes:
List.hd [ ] renvoie , et List.hd [] lève une exception.
List.tl [ ] renvoie [ ], et List.tl [] lève une exception.
List. length 1 renvoie la longueur (nombre d'éléments) de la liste 1.
List.init renvoie la liste [ ] pour positif.
List.assoc renvoie le premier tel que s'il existe, et lève l'exception Not_found sinon.
List.find renvoie le premier tel que true s'il existe, et lève l'exception Not_found sinon.
List.map renvoie [ ].
List.filter renvoie la liste des éléments e de tels que true, dans l'ordre.
List.concat renvoie , la concaténation des listes .
List.concatmap renvoie List.concat (List.map ).
List.fold_left renvoie où pour .
Pour les tableaux, on pourra utiliser les fonctions suivantes:
Array. length a renvoie la longueur (nombre d'éléments) du tableau a.
Array.init f renvoie le tableau [|f pour n positif.
Array.of_list renvoie le tableau [| .
On rappelle enfin que la fonction float loat est disponible en OCaml pour calculer un logarithme naturel.
Partie I : Description probabiliste des plantes
On se donne un nombre de caractères . Un caractère sera un entier . Pour chaque caractère , on se donne un ensemble fini de valeurs possibles pour ce caractère.
Pour nos exemples, nous prendrons et deux valeurs pour chaque caractère : représentera le nombre de pétales des fleurs, et bleu, blanc représentera leur couleur.
Nous utiliserons une représentation probabiliste des espèces pour modéliser la variabilité intraespèce, ainsi que la variabilité des interprétations lors des observations : on peut trouver au sein d'une même espèce des individus à fleurs bleues et d'autres à fleurs blanches; par ailleurs, une couleur bleue très claire pourra être interprétée comme bleue ou blanche en fonction de l'observateur. Ainsi, chaque espèce sera décrite par des valeurs possibles pour chaque caractère, organisées en distributions de probabilité : une espèce est un -uplet où . Intuitivement, représente la probabilité que la valeur soit observée pour le caractère chez un individu de l'espèce. On suppose donné un ensemble fini d'espèces .
Dans nos exemples, sera composé des trois espèces suivantes, décrites en utilisant des diracs :
On définit l'ensemble suivant, dont les éléments modélisent des individus, décrits par leur espèce et les valeurs de leurs caractères :
On considèrera l'espace probabilisable ( ) obtenu en munissant de la tribu discrète. On utilisera plusieurs lois de probabilité sur cet espace, définies en fonction d'un état : intuitivement, l'état indiquera la probabilité d'observer chaque espèce. La loi de probabilité induite par un état est définie comme l'unique loi satisfaisant l'équation suivante pour tout
On notera la variable aléatoire qui à associe . Pour chaque caractère , on notera la variable aléatoire qui à associe . On pourra ainsi écrire, par exemple, , qui représente (dans l'état ) la probabilité (conditionnelle) que le caractère prenne la valeur chez un individu de l'espèce .
Préliminaires probabilistes. On établit tout d'abord quelques résultats élémentaires sur lesquels s'appuiera notre méthode de classification.
Question 1. On considère l'état gaillet : , myosotis : , lin : sur les espèces de notre exemple. Quelle est la probabilité blanc) d'observer des fleurs blanches dans cet état? Pour chaque espèce , que vaut la probabilité blanc) d'observer un individu de l'espèce sachant que celui-ci a des fleurs blanches? Aucune justification n'est attendue.
Question 2. Étant donnés un état , une espèce , un caractère et une valeur , exprimer simplement les probabilités et , ainsi que quand elle est bien définie. Les réponses devront être justifiées.
Question 3. Étant donnés un état , un caractère , une valeur et une espèce , exprimer . Sous quelle condition cette probabilité est-elle bien définie?
Pour un état , un caractère et une valeur , on définit l'état mis à jour comme la distribution qui à chaque espèce associe .
Question 4. Pour un état , deux caractères et des valeur et , montrer que quand ces probabilités sont bien définies.
Le résultat précédent nous indique que, si l'on souhaite évaluer dans un état la probabilité d'observer une certaine espèce sachant que et , il nous suffit de calculer une probabilité conditionnée seulement par mais dans l'état . En allant plus loin, si l'on pose et , on a . On admettra que ce résultat se généralise à un nombre arbitraire d'observations. Ainsi, il est possible de procéder à la reconnaissance de plantes en calculant des états mis à jours par des observations successives, jusqu'à atteindre un état de la forme ou ne plus pouvoir faire de nouvelle observation.
Choix des représentations pour le code. Un caractère sera naturellement représenté par un entier OCaml. On représentera aussi les valeurs par des entiers, en supposant que chaque est de la forme , ce qui revient à numéroter les valeurs possibles. On pose ainsi :
type caractere = int
type valeur = int
On suppose donnés le nombre de valeurs pour chaque caractère sous la forme d'un tableau :
val num : int array (* num. (i) = k_i, i.e., }\mp@subsup{V}{-}{}i={0,1,\ldots,num.(i)-1}*
Enfin, on considèrera que la liste des caractères est définie en variable globale à partir du tableau num :
let caracteres : caractere list = List.init (Array.length num) (fun i -> i)
Pour notre exemple avec deux caractères, on aura ainsi :
(* Nombre de valeurs possibles pour le nombre de pétales et pour leur couleur *)
let num = [|2; 2|]
(* Nombre de pétales *)
let nb_petales : caractere = 0
let quatre, cinq = 0, 1
(* Couleur *)
let couleur_petales : caractere = 1
let bleu, blanc = 0, 1
Une mesure sur sera représentée par une liste de couples ( ) avec et , sans doublons. En particulier, les éléments de poids nuls ne sont pas inclus dans la liste, et l'ordre n'a pas d'importance.
type 'x mesure = ('x * float) list
let dirac v = [(v, 1.)]
Enfin, on codera comme suit les espèces et états :
type espece = { name: string; mesures: valeur mesure array }
type etat = espece mesure
Pour notre exemple, on aura ainsi :
let myosotis : espece =
{ name = "myosotis";
mesures = [| dirac cinq; [(bleu, 0.8);(blanc, 0.2)] |] }
let lin : espece =
{ name = "lin";
mesures = [| dirac cinq; dirac bleu |] }
let gaillet : espece =
{ name = "gaillet";
mesures = [| dirac quatre; dirac blanc |] }
let sigma0 : etat = [(gaillet, 0.5);(myosotis, 0.3);(lin, 0.2)]
La première renvoie le poids d'un élément selon une mesure donnée. La seconde renvoie la somme d'une mesure pondérée par une fonction , définie par . La troisième repondère une mesure sur par une fonction : le poids de passe de à .
Question 6. Écrire deux fonctions
val proba_espece : espece -> caractere -> valeur -> float
val proba_etat : etat -> caractere -> valeur -> float
où proba_espece i renvoie la probabilité et proba_etat renvoie .
Question 7. Écrire une fonction
val reponse : etat -> caractere -> valeur -> etat
qui, étant donnés un état , un caractère et une valeur , renvoie l'état si celui-ci est bien défini, et lève une exception sinon.
Partie II : Arbre optimal
Dans cette seconde partie, on définit la notion d'arbre de décision, et on s'intéresse au calcul d'un arbre de décision optimal en un certain sens. On introduit les types de données suivants pour coder nos arbres :
type noeud = {caractere: caractere; enfants: (float * arbre) array}
and arbre =
| Noeud of noeud (* On pose une question sur un caractère. *)
| Feuille of etat (* On a atteint une feuille, on donne l'état. *)
| Impossible (* On a atteint une feuille impossible :
aucune espèce ne correspond aux réponses données. *)
Les valeurs de type arbre ne représentent pas toutes des arbres de décision. Une valeur de type arbre est un arbre de décision pour un ensemble de caractères et un état lorsque :
L'arbre n'est pas Impossible.
Si est de la forme Feuille , alors et (au moins) l'une des deux conditions suivantes est satisfaite :
est une distribution dirac (il n'y a plus qu'une seule espèce possible);
(il n'y a plus de caractère disponible pour discriminer).
Si est de la forme Noeud {caractere=i;enfants=e} alors i est un élément de , e est un tableau à num. (i) éléments, et pour chaque valeur possible num. (i), e. (v) est de la forme ( ) avec :
si , alors est Impossible;
sinon, est un arbre de décision pour l'ensemble de caractères et l'état .
Dans le contexte de l'exemple de la partie I, on représente graphiquement ci-dessous un arbre de décision pour l'ensemble complet de caractères et l'état de la question 1 (pour des valeurs de et non précisées) :
Les nœuds sont étiquetés par des caractères et les feuilles par des états; la notation est utilisée pour représenter les cas impossibles où aucune espèce ne peut correspondre aux valeurs observées. Chaque arc est étiqueté par la valeur du caractère correspondant à l'enfant ainsi que la probabilité que cette valeur soit observée.
On définit la hauteur moyenne d'un arbre , notée , comme suit :
Si est de la forme Feuille ou Impossible, alors .
Si est de la forme Noeud {caractere=i;enfants=e}, et si l'on note ( ) = e. ( ), alors :
La hauteur moyenne correspond au nombre moyen de questions avant d'atteindre une feuille. Sur l'exemple précédent, la hauteur moyenne est de deux.
Question 8. Sur l'exemple de la question 1, énumérer tous les arbres de décision possibles pour les caractères et l'état , et donner leur hauteur moyenne - pour l'arbre déjà représenté ci-dessus, on pourra se contenter de préciser les valeurs de et . Quel est l'arbre de décision avec la hauteur moyenne minimale?
Dans la suite de cette partie, on se propose de calculer naïvement un arbre de décision de hauteur moyenne minimale. On dira qu'un arbre est optimal pour et quand c'est un arbre de décision pour et tel que est minimale parmi les hauteurs moyennes de tous les arbres de décision pour et . Dans un contexte où et sont clairs, on dira simplement que est optimal.
Question 9. Écrire une fonction
val choix_possibles : 'x list array -> 'x array list
qui renvoie la liste des tableaux obtenus en choisissant un élément dans chaque liste du tableau d'entrée. Par exemple :
Question 10. Écrire une fonction qui, étant donné un état initial , renvoie la liste de tous les arbres de décision possibles pour et l'ensemble de tous les caractères :
val enumere : etat -> arbre list
On rappelle que l'ensemble de tous les caractères est représenté par la liste caracteres déclarée en variable globale.
Question 11. Écrire une fonction
val argmin : 'x list -> ('x -> float) -> 'x
telle que argmin l f renvoie un élément de l qui minimise f, si la liste est non-vide. En déduire une fonction qui, étant donné un état initial , renvoie un arbre de décision optimal pour et l'ensemble de tous les caractères :
val arbre_optimal : etat -> arbre
Partie III : Algorithme glouton
Afin d'éviter l'énumération de tous les arbres de décision dans l'algorithme de la partie précédente, on cherche un algorithme glouton : l'idée générale est de décider localement du caractère à choisir en fonction de l'état courant, plutôt que d'envisager tous les choix possibles. Pour cela, on décide de prendre le caractère qui minimise l'entropie moyenne. Avant de définir cette quantité, on introduit l'entropie simple d'une distribution , qui est donnée par :
Question 12. Soit un ensemble de cardinal . Donner (en justifiant) les valeurs minimale et maximale de sur en fonction de , ainsi que des distributions les atteignant.
Étant donnés un caractère et un état , on définit l'entropie moyenne de dans l'état , notée , comme l'espérance des entropies sur les distributions obtenues en faisant une observation sur le caractère :
Question 13. Écrire une fonction qui renvoie l'entropie moyenne d'un caractère dans un état donné :
val score_caractere : etat -> caractere -> float
Question 14. Écrire une fonction qui calcule un arbre de décision en suivant l'algorithme glouton qui construit l'arbre en choisissant à la racine le caractère minimisant l'entropie moyenne, et procède récursivement de la même façon pour les sous-arbres :
val glouton : etat -> arbre
On se propose maintenant de montrer que l'algorithme glouton n'est pas optimal. On considère une situation avec deux caractères, oui, non , et trois espèces et :
On considère enfin l'état initial suivant :
L'espèce est donc plus rare que les espèces et qui sont plus communes.
Question 15. Dessiner les arbres de décision possibles pour l'état et les caractères , et déterminer l'arbre de décision optimal.
Question 16. Calculer les entropies moyennes et . Que peut-on en conclure? On admettra que .
Partie IV : Optimisation de l'algorithme naïf
On cherche à optimiser l'algorithme naïf de la partie II en évitant certains calculs inutiles. Pour permettre cela, on commence par changer la méthode de recherche d'un arbre optimal, en évitant de construire la liste de tous les arbres de décision possibles. La nouvelle méthode s'appuiera sur la fonction arbre_optimal_avec_oracle donnée en Figure 1. Le but de cette fonction est, étant donnés un état et une liste de caractères , de renvoyer où est un arbre optimal pour et . Il faut bien noter que cette fonction n'est pas récursive, mais qu'elle dispose d'un argument supplémentaire oracle dont les appels pourront correspondre à des appels récursifs : il s'agit de récursion ouverte.
Question 17. Donner des hypothèses (pré-conditions) aussi précises que possible sur les arguments , et oracle de la fonction arbre_optimal_avec_oracle, sous lesquelles la fonction termine toujours et renvoie bien où est un arbre optimal pour et . On veillera à répondre à cette question après avoir réfléchi aux deux suivantes, où il faudra démontrer puis exploiter la correction de la fonction par rapport à la spécification énoncée ici.
Question 18. Démontrer que la fonction satisfait bien cette spécification, en veillant notamment à énoncer clairement l'invariant de boucle.
Question 19. Écrire une fonction, récursive cette fois-ci, et basée sur arbre_optimal_avec_oracle, qui renvoie un arbre de décision optimal pour un état et une liste de caractères donnés :
val arbre_optimal : etat -> caractere list -> arbre * float
Donner sa spécification et montrer qu'elle la satisfait.
Question 20. On cherche maintenant à optimiser notre algorithme en interrompant la génération d'un arbre dès que son score dépasse celui de l'arbre_optimal courant. Pour cela, écrire une nouvelle fonction
val arbre_optimal_opt : etat -> caractere list -> float -> (arbre * float) option
qui prend un paramètre supplémentaire représentant le score à ne pas dépasser, et renvoie None si tous les arbres de décision possibles sont de hauteur moyenne supérieure au score maximal, ou bien un arbre optimal de hauteur moyenne inférieure s'il en existe un. La preuve de correction n'est pas demandée.
let arbre_optimal_avec_oracle
(oracle : etat -> caractere list -> arbre * float)
(etat : etat)
(caracteres : caractere list) : arbre * float =
if caracteres = [] then
(Feuille etat, 0.)
else
let caracteres_a_tester = ref caracteres in
let score_optimal = ref infinity in
let arbre_optimal = ref None in
while !caracteres_a_tester <> [] do
let caractere = List.hd !caracteres_a_tester in
let score_total = ref 1. in
let enfants : (float * arbre) array =
Array.init num.(caractere) (fun valeur ->
let p_valeur = proba_etat etat caractere valeur in
let sous_arbre, score_sous_arbre =
if p_valeur = 0. then Impossible,0. else
let etat' = reponse etat caractere valeur in
let caracteres_restants =
List.filter (fun c -> c <> caractere) caracteres
in
oracle etat' caracteres_restants
in
score_total := !score_total +. p_valeur *. score_sous_arbre;
(p_valeur, sous_arbre))
in
if !score_total < !score_optimal then
(arbre_optimal := Some (Noeud {caractere=caractere;enfants=enfants});
score_optimal := !score_total);
caracteres_a_tester := List.tl !caracteres_a_tester
done;
match !arbre_optimal with
| Some a -> a, !score_optimal
| None -> assert false
Figure 1 - Fonction arbre_optimal_avec_oracle.
Partie V : Observations complexes et formules logiques
Pour aller plus loin, on se propose de représenter des observations complexes sous forme de formules logiques construites à partir des caractères, par exemple "la fleur est bleue et a cinq pétales". La syntaxe de cette logique est la suivante :
Cela signifie que l'ensemble des formules est le plus petit ensemble contenant les formules atomiques de la forme où et , et que si sont des formules pour , alors la conjonction et la disjonction sont aussi des formules. Une formule signifie intuitivement que le caractère prend une valeur dans l'ensemble . On définit la formule (la formule fausse) comme la disjonction vide, et T (la formule vraie) comme la conjonction vide.
Par exemple, avec les ensembles et de l'exemple utilisé en partie bleu est une formule, correspondant à l'énoncé "la fleur est bleue et a cinq pétales". Ou encore, si est une formule, correspondant à l'énoncé contradictoire "le caractère vaut 1 , et il vaut 2 ou 3 ".
On définit la taille d'une formule , notée , comme suit :
Dans un premier temps, nous définissons quand une situation certaine (dite déterministe) satisfait une certaine formule. On appelle modèles déterministes les éléments de . On notera pour signifier que est un tel modèle, et dans ce cas on notera la -ème composante de , ce qui revient à dire que . On définit une relation de satisfaction entre les modèles déterministes et les formules, notée , comme suit :
On étend ensuite cette relation de satisfaction au cadre probabiliste de la manière suivante. Un modèle probabiliste est un élément de . Un tel modèle associe une distribution de probabilité plutôt qu'une valeur déterminée à chaque caractère. On remarquera que cette modélisation suppose que les valeurs de deux caractères distincts sont probabilistes mais indépendantes l'une de l'autre. Étant donnés une formule et un modèle probabiliste ( ), on définit la probabilité que satisfasse , notée , ainsi :
Question 21. Pour deux formules et , montrer l'équivalence entre ces deux propositions :
Pour tout modèle déterministe si et seulement si .
Pour tout modèle probabiliste .
On dira que et sont équivalentes, noté , quand l'une ou l'autre des propositions précédentes est vraie.
Dans les questions qui suivent, on reprend le codage OCaml des distributions, et on représente directement les formules via le type suivant :
type formule =
| Feuille of caractere * valeur list
| Conjonction of formule list
| Disjonction of formule list
On supposera de plus que les listes codant les ensembles de valeurs dans les formules atomiques sont sans doublons. On codera les modèles déterministes (resp. probabilistes) par des tableaux de valeurs (resp. distributions). On notera enfin K le cardinal maximal des :
Question 22. On considère l'algorithme qui, étant donnés un modèle probabiliste et une formule , calcule en suivant naïvement sa définition. Quelle est la complexité temporelle de cet algorithme, en fonction de et ? Un programme OCaml détaillé n'est pas demandé, mais on veillera à en décrire les aspects nécessaires pour justifier l'analyse de complexité.
Dans la suite, nous allons élaborer une méthode de calcul de dont la complexité ne dépend pas de . Cette méthode s'appuie sur des formes particulières de formules. Une clause est une conjonction de formules atomiques concernant des caractères différents. En reprenant les exemples précédents, bleu est une clause mais pas .
Question 23. Décrire un algorithme qui, étant donnés un modèle probabiliste et une clause , calcule avec une complexité qui ne dépend que de K et , mais pas de . Justifier la correction de l'algorithme et son analyse de complexité. Il n'est pas nécessaire de donner un programme OCaml détaillé.
Question 24. Étant données deux clauses et , montrer que est équivalente à une clause que l'on notera .
Question 25. Montrer que pour toute formule il existe et des clauses telles que .
Question 26. Décrire un algorithme qui, étant donnés un modèle probabiliste et une formule , calcule avec une complexité temporelle (potentiellement non-polynomiale) qui ne dépend que de K et mais pas de .
En pratique, un tel algorithme est utile car on va avoir des modèles avec de nombreux caractères mais un nombre de valeurs possibles restreint pour chaque caractère, et l'on s'intéressera à des formules de taille limitée.
Fin du sujet.
X ENS Option Informatique MP MPI 2025 - Version Web LaTeX | WikiPrépa | WikiPrépa
