Sorbonne Université 2 mars 2020
2MA100 – Devoir Maison 1
Les exercices de ce devoir maison noté sur 20 points doivent être rendus au choix au format Notebook (.ipynb) ou Script (.py) en un ou plusieurs fichiers au plus tard le 13 mars 2020 à 23h59 sur moodle.
Attention Plagiat.
Les devoirs maisons doivent être codés et rendus de manière individuelle. A titre d’information, voici une définition du plagiat adaptée du Memento de l’Université de Genève :
Le plagiat consiste à insérer, dans un travail académique, des formulations, des phrases, des passages, des morceaux de code, des images, de même que des idées ou analyses repris de travaux d’autres auteurs, en les faisant passer pour siens.
En particulier, le copier-coller à partir de sources trouvées sur Internet ou sur des travaux d’autres étudiant·es sans citer les sources est considéré comme du plagiat et implique une note zéro. Le plagiat constitue également une tentative de tricherie sanctionnée par le règlement de l’université. La solution est d’indiquer dans vos devoirs tout de ce qui ne vient pas de vous en mentionnant les sources (page Internet, livres, autre étudiant·e,…). Tout les fichiers rendus seront analysés automatiquement avec un logiciel de détection des similarités (entre étudiant·es et depuis Internet).
Exercice 1 : Nombre d’or
√
On s’intéresse ici à une approximation du nombre d’or, φ = 1 + 5 . 2
On définit tout d’abord la suite (Fn)n0 par F0 = F1 = 1 et Fn = Fn−1 +Fn−2 pour n ≥ 2. On a alors le résultat suivant,
lim Fn+1 =φ. n→+∞ Fn
a) Écrire une fonction Fibo(epsilon) qui, à ε précision donnée, renvoie le plus petit entier n tel Fn+1
On souligne également que φ est l’unique solution positive de l’équation x2 − x − 1 = 0.
b) Écrire une nouvelle fonction Newton(epsilon, x0) qui, à ε précision donnée, renvoie le plus petit entier k tel que |φ − xk| < ε où xk est déterminé par la méthode de Newton appliquée à f(x) = x2 − x − 1 dont on rappelle le principe :
xk+1=xk−f(xk), k≥0. f′(xk)
En pratique on choisira x0 = 3.
c) Pour ε = 10−i et i ∈ {2, 4, 6, 8} comparer le nombre d’itérations nécessaire entre les deux stratégies proposées pour approximer φ à précision donnée. Quelle stratégie vous semble la plus efficace ?
d) Et qu’en est-il si on initialise la méthode de Newton par x0 = 0 ?
queφ− F <ε. n
1
Exercice 2 : Matrice de Vandermonde
Soitp,n∈N∗ etx:=(x1,...,xp)∈Rp,onintroduitlamatriceV(x,n)définitpar: 1 x1 x2 ··· xn−1 xn
111 1 x2 x2 ··· xn−1 xn
222 . . . .. . .
V(x,n)=. . . . . . . 1 xp−1 x2 ··· xn−1 xn
p−1 p−1 p−1 1 x x2 ··· xn−1 xn
pppp
a) Écrire une fonction qui construit la matrice V (x, n) élément par élément à l’aide d’une double boucle.
b) Après avoir établi une relation permettant d’écrire la k-ième colonne de V (x, n) uniquement en fonction de x et de k, écrire une seconde fonction qui construit la matrice V (x, n) colonne par colonne à l’aide de cette relation.
c) Après avoir établi une relation entre la k-ième colonne de V (x, n), sa (k − 1)-ième colonne et le vecteur x, écrire une troisième fonction qui construit la matrice V (x, n) colonne par colonne à l’aide de cette relation.
d) Comparer les temps d’exécution de ces trois fonctions pour n = 150, p = 100 et x généré aléatoirement.
2
Exercice 3 : Reconnaissance de chiffres manuscrits
Le but de cet exercice est d’écrire un programme de classification d’image de chiffres manuscrits. Ceci fut l’une des premières applications industrielles du machine learning à la lecture automatique des chèques ou des codes postaux.
Les instructions suivantes permettent de charger un jeu de données de chiffres manuscrits numérisés disponible dans le package scikit-learn (nom d’import sklearn) :
from sklearn.datasets import load_digits
digits = load_digits()
X, y = digits.data, digits.target
Ainsi X est un tableau Numpy qui contient de nombreux exemples de chiffres manuscrits numérisées en image de 8x8 pixels stockés sous la forme de tableau de 64 nombres entiers stockés en flottants. La variable y contient l’entier entre 0 et 9 correspondant au chiffre numérisé. On parle de label.
a) Quelle commande Python permet de connaître les dimensions de X et y et ainsi de connaître le nombre d’exemples contenus dans la base de données ?
b) Afficher à l’aide de la commande print les données contenus dans X associées à l’indice idx=12 ? Il s’agit donc de la douzième ligne du tableau X.
c) À l’aide des fonctions reshape de Numpy et imshow de Matplotlib afficher l’image d’indice idx=12. Il est possible d’utiliser l’argument cmap=’gray’ dans l’appel de imshow pour afficher le résultat en niveau de gris. Quel chiffre est ainsi codé ?
Pour chacune des classes de chiffre (de 0 à 9), on souhaite calculer son centroïde, i.e. la représentation “moyenne” d’une classe.
d) Comment définir les sous-tableaux de X et de y correspondant à tous les chiffres 0 numérisés ? e) Pour l’ensemble des 0 de la question précédente, calculer pour chaque pixel la valeur moyenne,
afin de définir le “zéro moyen”.
f) Pour l’ensemble des chiffres de 0 à 9 tracer sur une même ligne (à l’aide de la fonction subplot de Matplotlib et en initialisant la figure avec plt.figure(figsize=(20,2))) l’image moyenne associée :
Finalement, nous allons implémenter notre propre classifieur : pour une nouvelle image de chiffre numérisé, on prédit la classe dont le chiffre moyen est le plus proche. Pour cela on partage notre jeu de données en deux parties de tailles semblables : la première partie servira de données d’entraînement (X_train et y_train) ; la seconde partie servira de données de tests (X_test et y_test).
g) Définir les variables : X_train, y_train, X_test et y_test.
h) Pour chaque chiffre de l’ensemble d’entraînement, calculer les centroïdes (i.e. les chiffres
moyens) des classes de 0 à 9. On notera la variable contenant l’ensemble des moyennes centroids_train. i) Pour chaque chiffre de l’ensemble de test (X_test), calculer le centroïde appartenant à
centroids_train le plus proche (dans la norme euclidienne).
j) Finalement, évaluer si le chiffre ainsi obtenu correspond au vrai chiffre en utilisant y_test et
en déduire une estimation du pourcentage de bonnes prédictions sur l’ensemble de test.
mean 0 mean 1 mean 2 mean 3 mean 4 mean 5 mean 6 mean 7 mean 8 mean 9
3