Dans ce long TP, on va revenir sur le calcul propositionnel et mettre en œuvre l'algorithme ID3 pour deviner des formules.

Génération de formules¶

On considère le type de formules suivant :

type bool_expr =
    Var of int
    | And of bool_expr * bool_expr
    | Or of bool_expr * bool_expr
    | Not of bool_expr

Les variables sont des entiers entre \(0\) et \(n-1\), ce qui va permettre de représenter directement une valuation booléenne par un bool array de longueur \(n\).

Question 1. Écrire une fonction

val eval : bool_expr -> bool array -> bool

telle que eval e values évalue l'expression e en considérant que la variable i a la valeur values.(i).

Note : on supposera le tableau suffisamment long pour contenir toutes les variables présentes dans e.

Pour générer une expression aléatoirement, on reprend le principe déjà vu sur les arbres binaires avec un algorithme de génération récursif d'une formule à \(n\) nœuds internes :

si \(n = 0\), on génère une feuille avec un numéro de variable aléatoire ;
sinon, on produit un des trois types de nœuds avec probabilité \(1/3\) :
- pour le nœud unaire, on se contente de générer une expression de taille \(n-1\) ;
- pour les nœuds binaires, on choisit \(k \in \range{0}{n-1}\) aléatoirement et on génère une sous-expression à gauche de \(k\) nœuds et à droite de \(n-1-k\) nœuds.

Question 2. Écrire une fonction

val random_expr : int -> int -> bool_expr

telle que random_expr n vars génère ainsi une expression aléatoire à \(n\) nœuds internes et dont les variables sont < vars.

Pour effectuer des tests, on va également générer des valuations aléatoires.

Question 3. Écrire une fonction

val random_test : int -> bool array

telle que random_test vars renvoie un tableau de booléens aléatoires de taille vars.

On considère le type

type samples = (bool array * bool) list

Question 4. En déduire une fonction

val gen_samples : bool_expr -> int -> int -> samples

telle que gen_samples e vars nsamples génère aléatoirement nsamples tests composés de couples (values, b) où b est la valeur de vérité de l'expression e pour la valuation donnée par values.

Arbres de décision¶

On considère le type suivant pour les arbres de décision :

type decision_tree =
    Node of int * decision_tree * decision_tree
    | Leaf of bool

Un nœud Node(i,t_yes,t_no) représente un choix sur la valeur de vérité de la variable i. Si la variable i est vraie, on continue dans t_yes, sinon dans t_no.

Question 5. Écrire une fonction

val eval_tree : decision_tree -> bool array -> bool

telle que eval_tree t values renvoie la valeur de vérité de l'arbre de décision t pour une valuation donnée par values.

Algorithme ID3¶

On va implémenter maintenant l'algorithme ID3 vu en cours pour déduire un arbre de décision de valeurs telles que renvoyées par gen_samples. Ici, les attributs sont les variables et il y a deux classes, true et false.

Question 6. Écrire une fonction

val majority : samples -> bool

qui renvoie la valeur de vérité majoritaire des tests donnés en entrée.

On rappelle que cette valeur est la seconde composante des couples. En cas d'égalité, on pourra prendre une valeur fixée comme true ou une valeur aléatoire.

Question 7. Écrire des fonctions

val b : float -> float
val entropy : samples -> float
val gain : samples -> int -> float

calculant respectivement la valeur \(B(p) = -p \log_2 p - (1-p) \log_2 (1-p)\), en prenant garde aux cas \(0\) et \(1\) qui ne seront pas forcément atteints exactement avec des float, la valeur de l'entropie \(H(S)\) et le gain \(G(S,i)\) de la variable \(i\) vue comme attribut.

Note : on pourra utiliser Float.log2.

Question 8. Écrire une fonction

val id3_rec : samples -> samples -> int list -> decision_tree

telle que id3_rec s prec_s free, où :

s est l'ensemble courant des tests ;
prec_s est l'ensemble de tests du nœud parent, qui sert à choisir la valeur de la feuille quand s est vide ;
free est la liste des variables non encore utilisées comme attributs ;

renvoie l'arbre de décision associé par l'algorithme ID3.

Question 9. En déduire une fonction d'interface réduite

val id3 : samples -> int -> decision_tree

telle que id3 s vars renvoie un arbre de décision pour les tests s sur vars variables.

Mesure de performance¶

Pour mesurer les performances de l'algorithme ID3, on propose la stratégie suivante :

on génère une expression e à vars variables ;
pour k allant de 0 à N-1 donné :
- on génère k tests ;
- on construit l'arbre de décision associé par ID3 ;
- on génère toutes les valuations possibles de vars variables ;
- on calcule la proportion de valuations pour lesquelles l'arbre de décision renvoie la même valeur que e ;
on réalise un graphe des taux de succès en fonction de k.

Remarque : vous pouvez factoriser en générant les valuations une fois pour tous les \(k\) ; ça complique un peu les types, c'est pour ça que je ne l'ai pas fait ci-dessous. Libre à vous d'optimiser !

Question 10. Écrire une fonction

val enumerate_liste_values : int -> bool list list

telle que enumerate_liste_values vars renvoie la liste des valuations, données sous forme de listes de booléens, pour vars variables.

Remarque : le fait d'avoir des listes va permettre de réaliser simplement une énumération récursive.

Question 11. En déduire une fonction

val enumerate_values : int -> bool array list

qui les renvoie sous la forme de tableaux de booléens.

Question 12. Écrire une fonction

val performance : bool_expr -> decision_tree -> int -> float

telle que performance e t vars calcule le taux de correspondance entre une expression et un arbre de décision sur l'ensemble des valuations de vars variables.

Question 13. En déduire une fonction

val test : int -> int -> int -> float array

telle que l'appel test size vars max_samples applique la stratégie de tests précédente pour une formule de size nœuds sur les variables < vars et en ayant k tests pour k allant de 0 à max_samples - 1. On renverra les résultats sous la forme d'un tableau.

Question 14. On pourra réaliser des graphes pour mesurer l'impact du nombre de tests sur la performance.

Remarque

Par exemple, pour des formules à \(10\) nœuds sur \(8\) variables, la correction obtient un taux de succès qui passe d'environ \(50\,\%\) sans test à \(80\,\%\)–\(95\,\%\) dès une dizaine de tests, puis progresse lentement. Les valeurs varient beaucoup d'une formule à l'autre.

Passer des arbres de décision aux formules et réciproquement¶

Il est possible de passer d'un arbre de décision à une formule et réciproquement.

Question 15. Écrire deux fonctions effectuant ces conversions.