Matrices (8 points)

On considère la matrice $A_n = \begin{pmatrix} 1 & 1 & ... & 1\\ 0 & 1 & ... & 1\\ 0 & 0 & ... & 1 \end{pmatrix}$ dont tous les termes sous-diagonaux sont nuls, tous les autres valant 1.

Par exemple, $A_3 = \begin{pmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{pmatrix}$ et $A_4 = \begin{pmatrix} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\0 & 0 & 0 & 1 \end{pmatrix}$

  1. Justifiez l'inversibilité de $A_n$ (pour tout $n$). (1 point)

$det(A_n) = 1^n = 1 \neq 0$, donc $A_n$ est inversible.

  1. Calculer $A_2^{-1}$ puis $A_3^{-1}$ (2 points)

$A_2 = \begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$. On applique la formule $A_2^{-1} = \frac{1}{det(A_2)} t(Com(A_2))$ avec $det(A_2) = 1$ : $A_2^{-1} = \begin{pmatrix}1 & -1\\ 0 & 1\end{pmatrix}$

$A_3 = \begin{pmatrix}1 & 1 & 1\\ 0 & 1 & 1\\0 & 0 & 1\end{pmatrix}$. Appliquons pour changer la méthode du système : $A_3 X = Y$. $$\begin{align*} x_1 + x_2 + x_3 &= y_1\\ x_2 + x_3 &= y_2\\ x_3 &= y_3 \end{align*}$$ On remplace $x_3$ puis $x_2$ : $$\begin{align*} x_1 &= y_1 - y_2 + (y_3 - y_3)\\ x_2 &= y_2 - y_3\\ x_3 &= y_3 \end{align*}$$ Donc $A_3^{-1} = \begin{pmatrix}1 & -1 & 0\\0 & 1 & -1\\0 & 0 & 1\end{pmatrix}$.

  1. En déduire une hypothèse sur la forme générale de $A_n^{-1}$, et vérifiez la. (2 points)

Hypothèse : des '1' sur la diagonale, des '-1' sur la sur-diagonale, et des zéros partout ailleurs. Vérification : pour $n > 3$, la $i^{eme}$ ligne de $A_n$ (notée ici $L_i$) multipliée par la $j^{eme}$ colonne de $B_n$ (suivant l'hypothèse ; notons la $C_j$) vaut 0 si $j < i$ car tous les coefficients de $L_i$ sont nuls jusqu'à l'indice $i - 1$ inclus, et tous ceux de $C_j$ sont nuls à partir de l'indice $j$ (inclus). De même le produit est nul si $j > i$ car il vaut alors $1 \times 1 + 1 \times -1$. Enfin pour $i = j$, le produit vaut simplement $1 \times 1 = 1$.

  1. Déterminez l'ensemble des vecteurs propres non nuls de $A_n$. (3 points)

$A_n X = \lambda X$ s'écrit $$\begin{align*} \sum_{i=1}^{n} x_i &= \lambda x_1\\ \sum_{i=2}^{n} x_i &= \lambda x_2\\ \dots &= \dots\\ x_{n-1} + x_n &= \lambda x_{n-1}\\ x_n &= \lambda x_n \end{align*}$$

Si $\lambda = 0$, alors $A_n$ étant inversible il n'y a pas de vecteur propre non nul associé (l'unique solution étant $0$).

Si $\lambda \notin \{0, 1\}$, alors la dernière équation mène à $x_n = 0$, puis en remontant les lignes (récurrence immédiate) tous les $x_i$ sont nuls.

Il ne reste donc plus qu'à regarder le cas $\lambda = 1$ :
(Un coup d'oeil au polynôme caractéristique permettrait d'arriver tout de suite ici). $$\begin{align*} \sum_{i=1}^{n} x_i &= x_1\\ \sum_{i=2}^{n} x_i &= x_2\\ \dots &= \dots\\ x_{n-1} + x_n &= x_{n-1}\\ x_n &= x_n \end{align*}$$

L'avant-dernière équation mène à $x_n = 0$. L'avant-avant-dernière sera similaire et mènera à $x_{n-1} = 0$. La ligne $i-1$ annulant $x_i$, on en déduit par récurrence immédiate que tous les $x_i$ sont nuls sauf le premier.

Conclusion : l'ensemble des vecteurs propres non nuls = $\texttt{Vect}(1, 0, \dots, 0)$.

Chaînes de Markov (8 points)

Un joueur d'échecs occasionnel installe sur son téléphone un programme pour jouer dans les transports. Ce programme dispose de 4 niveaux (numérotés de 1 à 4). On suppose que si le niveau réel du joueur est $n \in [1, 4]$, la probabilité qu'il gagne contre le niveau $m$ vaut $\frac{n}{n + m}$. On s'intéresse au nombre de parties jouées en moyenne avant de battre le niveau 4, sachant que le joueur passe au niveau supérieur quand il gagne et revient au précédent quand il perd (pas de parties nulles).

Rappel : ce temps moyen s'écrit $t = N c$ où $N = (I - Q)^{-1}$ avec $Q$ la matrice des états transients, et $c$ vecteur colonne ne contenant que des $1$.

  1. Modélisez la situation par une chaîne de Markov, en supposant $n = 2$. (1 point)

Il y a quatre états, un état correspondant au niveau de la partie en cours. Si on joue contre le niveau $x$ alors on passe à $x+1$ si on gagne, et $x-1$ après une défaite. On obtient la matrice suivante.

$$P = \begin{pmatrix} 1/3 & 2/3 & 0 & 0\\ 1/2 & 0 & 1/2 & 0\\ 0 & 3/5 & 0 & 2/5\\ 0 & 0 & 2/3 & 1/3 \end{pmatrix}$$
  1. La chaîne est-elle irréductible (ergodique) ? Apériodique (régulière) ? Justifiez. (1.5 point)

Irréductible : oui car on peut atteindre tous les niveaux quel que soit notre niveau de départ (il suffit de gagner et/ou perdre jusqu'à y arriver). Apériodique : oui car on trouve un chemin de longueur 3 entre chaque paire d'états (2 1 2 3, 2 3 4 4 etc). Plus simple : le PGCD vaut clairement 1 pour les niveaux 1 et 4. Concernant les deux autres, on trouve donc un chemin de longueur 2, et un de longueur 3 :
2 -> 1 -> 1 -> 2 et 3 -> 4 -> 4 -> 3. PGCD(2, 3) = 1, donc ça marche aussi.

  1. Calculez la distribution stationnaire $w$ telle que $w P = w$. Vérifiez la cohérence du résultat. (1.5 point)

Système $\begin{align*}1/3 w_1 + 1/2 w_2 &= w_1\\2/3 w_1 + 3/5 w_3 &= w_2\\1/2 w_2 + 2/3 w_4 &= w_3\\2/5 w_3 + 1/3 w_4 &= w_4\end{align*}$

On remplace $w_1$ et $w_4$ à l'aide des première et dernière relations, obtenant $w_1 = 3/4 w_2$, $w_4 = 3/5 w_3$ et $1/2 w_2 = 3/5 w_3$.
Le système se réécrit alors $\begin{align*} w_2 &= 4/3 w_1\\ w_3 &= 5/6 w_2\\ w_4 &= 3/5 w_3 \end{align*}$

Donc le vecteur non normalisé est $(1, 4/3, 20/18, 60/90) = (1, 4/3, 10/9, 2/3)$, et finalement $w \simeq (0.24, 0.32, 0.27, 0.16)$. On passe logiquement plus de temps à jouer contre notre vrai niveau, et nettement moins à jouer contre le niveau 4.

  1. Supposant qu'il commence au niveau 1, calculez le nombre moyen de parties jouées avant d'arriver au niveau 4. (3 points)

On considère l'état 4 comme absorbant. La matrice $Q$ s'écrit $$Q = \begin{pmatrix} 1/3 & 2/3 & 0\\ 1/2 & 0 & 1/2\\ 0 & 3/5 & 0 \end{pmatrix}$$ Il suffit alors d'inverser $I - Q = \begin{pmatrix}2/3 & -2/3 & 0\\-1/2 & 1 & -1/2\\0 & -3/5 & 1\end{pmatrix}$.

La présence des zéros incite à utiliser l'algorithme du pivot de Gauss : on effectue $L_2 \leftarrow L_2 + 3/4 L_1$ puis $L_3 \leftarrow L_3 + 6/5 L_2$, obtenant $$\begin{pmatrix} 2/3 & -2/3 & 0\\ 0 & 1/2 & -1/2\\ 0 & 0 & 2/5 \end{pmatrix}$$ On multiplie alors la troisième ligne par 5/2, la deuxième par 2 et la première par 3/2, pour arriver à

$$\begin{pmatrix} 1 & -1 & 0\\ 0 & 1 & -1\\ 0 & 0 & 1 \end{pmatrix}$$

Enfin, on fait $L_2 \leftarrow L_2 + L_3$ puis $L_1 \leftarrow L_1 + L_2$. Ces opérations reportées sur la matrice identité donnent au final (en fait la deuxième ligne suffit) : $$N = \begin{pmatrix} 21/4 & 5 & 5/2\\ 15/4 & 5 & 5/2\\ 9/4 & 3 & 5/2 \end{pmatrix}$$ On calcule alors $N_2 \times (1, 1, 1) = 11.25$. Il faut donc en moyenne un peu plus de 11 parties pour jouer contre le niveau 4 (avec une chance sur trois de gagner).

  1. Proposez une amélioration permettant de modéliser aussi l'évolution du niveau du joueur.
    Est-ce toujours une chaîne de Markov homogène telle qu'étudiée en cours ? (1 point)

Il suffirait par exemple d'ajuster le niveau $n$ du joueur après chaque partie. On peut garder la formule $\frac{n}{n + m}$ donnant la probabilité de victoire (en établissant des bornes pour le calcul, par exemple minimum 0 maximum 5). $n$ dépend maintenant du temps : la chaîne n'est plus homogène.

L'ajustement après chaque partie dépend à la fois du résultat et des niveaux relatifs. On pourrait dire que l'on perd 0.25 en perdant contre un niveau inférieur, 0.1 en perdant contre notre niveau, et 0.05 en perdant contre un niveau supérieur ; et inversement pour les victoires : 0.25 contre plus fort, 0.1 contre le même niveau et 0.05 contre plus faible. Bien sûr ceci n'est qu'une approximation grossière d'un vrai algorithme de classement.

Arbres de décision (8 points)

Un joggeur décide chaque midi s'il va courir en fonction de quatre critères : la météo, la température, la vitesse du vent et son retard au boulot.

Construire un arbre de décision binaire selon la méthode vue en cours en utilisant l'indice de Gini :
$I_G = 1 - \sum_{k=1}^{K} p_k^2$, avec $p_k$ proportion de la classe $k$ dans les données du noeud courant.
Détaillez les étapes [calculatrice], et dessinez l'arbre. (7 points)

Température Vitesse (du vent) Météo Retard (au boulot) Courir ?
15.2 10 soleil non oui
12.0 15 nuages non oui
10.0 10 pluie oui non
5.5 35 nuages non non
30.0 15 soleil oui non
7.0 25 pluie non non
18.0 12 pluie non oui
18.0 13 nuages oui oui
20.5 30 soleil non oui
20.0 20 pluie oui non

Remarques préliminaires : l'algorithme soustrait de l'indice de Gini du parent la somme pondérée des indices de Gini des enfants, afin d'obtenir une quantité à maximiser. Cela revient à calculer les sommes des carrés des probabilités, et de maximiser leur somme pondérée. On ne calculera donc que cette dernière, notée $S$. Ensuite, il y a exactement autant de "oui" que de "non" : ces modalités jouent donc des rôles symétriques.

On commence par regarder la variable température. Il faut d'abord trier les valeurs : 5.5, 7, 10, 12, 15.2, 2 x 18, 20, 20.5, 30. Les lignes 5.5, 7 et 10 se terminent toutes les trois par "ne pas courir", il n'y a donc aucune raison de couper avant.

$S_{10}^{T} = 3/10 + 7/10 ( (5/7)^2 + (2/7)^2 ) \simeq 0.71$

Ensuite, 12, 15.2 et 18 (deux fois) correspondent à un "oui" : il n'y a donc aucune raison de séparer ces valeurs.

$S_{18}^{T} = 3/10 \alpha + 7/10 ( (3/7)^2 + (4/7)^2 )$
$\alpha < 1$ car la composition du noeud résultant n'est pas homogène. La composition de l'autre noeud est moins pur que lors du dernier calcul (4 et 3 au lieu de 5 et 2). Il n'y a donc même pas besoin de calculer pour conclure $S_18 < S_10$.

Regardons ensuite la vitesse du vent : on range les valeurs par ordre croissant, 10 (x 2), 12, 13, 15 (x 2), 20, 25, 30, 35. Garder 10, 10, 12 revient à $S_18$ (composition du noeud enfant = oui, non, oui + symétrie). On ajoute donc 13, puis on teste la (nouvelle) coupure :

$S_{13}^{V} = 4/10 ( (1/4)^2 + (3/4)^2 ) + 6/10 ( (2/6)^2 + (4/6)^2 ) \simeq 0.58$

Ajouter 15 aboutit à une situation où on a "non non oui non" de l'autre côté, donc le résultat serait le même. Si l'on ajoute 20 alors il faut ajouter aussi 25 (même modalité de réponse), obtenant un nouveau calcul forcément mauvais puisque les répartitions sont alors les pires possibles : "non oui" d'un côté et "4 x non, 4 x oui" de l'autre. Il n'est donc pas nécessaire de l'effectuer.

Regardons maintenant la météo : il y a trois divisions envisageables, selon que l'on isole soleil, nuages ou pluie (les deux autres modalités se trouvant regroupées).

$S_{soleil} = S_{nuages} = S_{18}^{T}$ (cf. compositions des noeuds).
$S_{pluie} = S_{13}^{V}$ (cf. composition des noeuds).

Donc un découpage selon la météo n'est pas assez intéressant. Finalement, $S_{retard} = S_{13}^{V}$ également ("non non oui non").

Première coupe donc = "température $\leq$ 11" versus "température > 11" (11 : choix arbitraire entre 10 et 12).

On continue dans le sous-ensemble "température > 11" à 7 éléments. Attention la symétrie oui/non est désormais perdue.

Regardons d'abord la température : 12, 15.2 et 2 x 18 correspondent toutes quatre à un "oui". On ne les sépare donc pas, et on calcule

$S_{18}^{T} = 4/7 + 3/7 ( (1/3)^2 + (2/3)^2 ) \simeq 0.81$

Ajouter un élément mènerait à une situation pire (perte d'homogénéité de chaque côté). Pas besoin donc d'effectuer le calcul. De même si on coupe encore plus loin. Enfin, isoler "température = 30" mène certes à un noeud homogène mais de cardinal inférieur à celui de $S_{18}^{T}$.

Regardons ensuite la vitesse du vent : 10, 12, 13, 15 (x 2), 20, 30. 10, 12, 13 = 3 x oui, donc $S_{13}^{V} < S_{18}^{T}$ ci-dessus. Ajouter 15 implique d'ajouter deux lignes (même vitesse de vent), se retrouvant avec deux noeuds moins purs que pour $S_{13}^{V}$.

Ensuite, concernant la météo :

$S_{soleil} = 3/7 ( (1/3)^2 + (2/3)^2 ) + 4/7 ( (3/4)^2 + (1/4)^2 ) \simeq 0.60$
$S_{nuages} = 2/7 + 5/7 ( (3/5)^2 + (2/5)^2 ) \simeq 0.66$
$S_{pluie} < S_{nuages}$ (cf. composition des noeuds).

Et enfin, $S_{retard} = S_{18}^{T}$ (même répartition résultante).

Seconde coupe donc = "retard oui / non" (choix arbitraire)

Terminons rapidement avec les trois individus du dernier noeud impur : deux choix possibles, température > 19 (valeur arbitraire) ou soleil vs. nuages+pluie. On obtient finalement l'arbre
température $\leq$ 11 : non
température > 11 :
  retard non : oui
  retard oui :
    température $\leq$ 19 ou soleil : non
    température > 19 ou nuages ou pluie : oui

(#BonSensRequired) Vous paraît-il judicieux d'élaguer cet arbre ? Pourquoi ? (1 point).

La bonne réponse dépend du chemin choisi.

Sur le choix ci-dessus : oui, car l'arbre dit en résumé que si la température dépasse les 19 degrés (ou qu'il pleut !) et qu'on n'est pas en retard au boulot alors on ira courir. On imagine cependant que des températures trop élevées (ou des pluies trop fortes) seront en général dissuasives. Il vaut mieux donc revenir d'un pas en arrière, obtenant un arbre plus conforme à l'intuition.

Supposons maintenant qu'on ait choisi deux coupes successives sur la température. Il y a alors deux alternatives pour la dernière division : sur la vitesse du vent, auquel cas la bonne réponse est encore oui (on va courir s'il souffle fort ?!) ; et sur la variable "Retard", menant à "je suis en retard => je ne vais pas courir" et inversement. Cette fois c'est tout à fait cohérent : on n'élague pas.

Analyse en Composantes Principales (8 points)

Dans cet exercice on utilise un jeu de données indiquant la qualité de divers vins (blancs) en fonction de leurs caractéristiques physico-chimiques. La qualité (dernière colonne) est une note de 0 à 10. Autres variables :

Indication : les variables 6, 7 et 10 correspondent à des additifs (conservateurs), a priori sans bonnes propriétés gustatives.

1] Décrivez ce que fait la ligne de code ci-dessous. (1 point)

Calcul de l'ACP sur le jeu de données, en excluant la 12eme variable (quality) $-$ quantitative $-$ considérée comme supplémentaire, sans affichage du graphe. L'ACP détermine un système d'axes deux à deux orthogonaux maximisant itérativement l'inertie projetée.

2] Qu'est-ce qui est affiché par le code ci-dessous ?
Combien d'axes doit-on garder (au minimum) pour conserver 80% d'inertie ? (1.5 points)

On lit les valeurs propres (inerties le long de chaque axe) à gauche, cette inertie exprimée en pourcentages au milieu, et l'inertie cumulée à droite (toujours en pourcentages). Il faut garder au moins 6 axes pour expliquer plus de 80% d'inertie.

3] Commentez le résultat du code ci-dessous. (2 points)

Le "trou" observé sur le graphe de gauche correspond essentiellement aux 4398 individus les moins bien projetés : $\cos^2$ inférieur à environ 0.75 d'après le graphe suivant. Ceux-ci sont en général (très) proches de l'origine. C'est cohérent car l'inertie totale dans ce plan étant de l'ordre de 45%, il reste beaucoup d'information à expliquer dans les autres plans ACP. Beaucoup d'individus seront bien projetés avec des coordonnées non nulles sur d'autres plans, l'angle formé avec celui-ci étant proche de $\pi / 2$.

4] Commentez les graphes ci-dessous. (3.5 points)

Plan 1-2 : le pH est logiquement inversement corrélé à fixed.acidity. Les corrélations inverses avec les deux autres variables "acides" sont cependant plutôt faibles d'après le tableau des corrélations. La densité s'oppose au degré d'alcool, comme vérifié dans le tableau (et dans un cours de chimie ou via Wikipedia : l'alcool est nettement moins dense que l'eau - prise comme référence). Cette densité est fortement corrélée au taux de sucres résiduels. Ensuite, on observe logiquement une nette corrélation entre free.sulfur.dioxide et total.sulfur.dioxid, vérifiée sur le tableau car free.sulfur.dioxide n'est pas très bien représentée. Enfin, la qualité semble être liée au degré d'alcool, comme vérifié dans le tableau. Cette corrélation n'est pas très forte car d'autres facteurs entrent heureusement en jeu.

Signification des axes : 1 = degré d'alcool, 2 = acidité.

Plan 3-4 : la plupart des variables sont trop mal représentées pour conclure quelque chose. On note tout de même que la qualité semble augmenter avec le taux de dioxyde de soufre libre, contredisant l'indication donnée. Cette corrélation est cependant très légère d'après le tableau. (Voir exercice suivant). Ce taux de soufre semble négativement corrélé avec l'acidité volatile et les chlorures : ce serait difficilement explicable ; le tableau indique en effet une abscence de corrélation. De même pour l'opposition sulfates / sucres résiduels.

Signification des axes difficile à établir sans plus d'informations (axe 4 = chlorures ?).

Analyse factorielle des Correspondances (8 points)

On reprend le jeu de données de l'exercice précédent, en se focalisant sur les variables "quality" et "free.sulfur.dioxide".

  1. On donne le tableau des effectifs théoriques en cas d'indépendance.
    Expliquez comment celui-ci a été obtenu. (2 points)
quality \ free.sulfur.dioxide high low medium
average 695.5 1471.5 1488
excellent 34.2 72.5 73.3
good 167.5 354.3 358.2
poor 34.8 73.7 74.5

On commence par diviser toutes les valeurs du tableau des effectifs observés par $n = 4898$ (nombre total d'individus). On calcule ensuite les marges ligne et colonne en sommant respectivement les colonnes puis les lignes. On effectue alors le produit des marges colonne $\times$ ligne pour trouver la matrice des proportions théoriques, qu'il suffit de remultiplier par $n$.

Méthode alternative : calculer directement les marges, puis multiplier marge colonne $\times$ marge ligne, et enfin tout diviser par $n$.

  1. Calculer la distance du $\chi^2$ avec le tableau réel ci-dessous. [calculatrice].
    Combien y a-t-il de degrés de liberté, et pourquoi ? (2 points)

On calcule la somme des douze termes $(t_i - n_i)^2 / t_i$. $\chi^2 = (695.5 - 789)^2 / 695.5 + (1471.5 - 1430)^2 / 1471.5 + \dots \simeq 142.8$.
Il y a 6 degrés de liberté : concernant l'effectif théorique, les valeurs sur une ligne ou colonne sont liées car leur somme est fixée (par les effectifs observés). On a donc (3-1) * (4-1) degrés de liberté au total.

  1. En déduire l'inertie totale du nuage des profils ligne ou colonne.
    Vérifiez à l'aide du dernier affichage ci-dessous. (1 point)

D'après la relation $\chi^2 = n \Phi^2$, on en déduit $\Phi^2 \simeq 142.8 / 4898 = 0.029$. Cette valeur correspond bien à la somme de la première colonne donnée par "res.CA$eig" ci-après : 0.0163 + 0.0127.

  1. Commentez les résultats de l'AFC affichés ici. (3 points)

Le profil ligne le plus proche de l'effectif théorique est "average" (en terme de proportions) car il se trouve représenté le plus proche de l'origine. Il est aussi légèrement du côté de la modalité "high", ce qui est assez cohérent ; en effet cet additif masquant le goût du vin, son abus (relatif) mène logiquement à un vin "standard" sans grand intérêt.

Ensuite, le profil ligne "poor" est loin de l'origine : il est en effet loin du profil théorique en cas d'indépendance. Il est du côté d'une faible teneur en dioxyde de soufre libre : le goût du vin n'étant alors pas masqué, le mauvais goût du vin prend le dessus. Les vins excellents sont quant à eux dans la direction de la modalité "medium", mais il semble difficile d'expliquer pourquoi. Les vins bons et excellents sont logiquement assez proches sur le graphe.

Enfin, les valeurs propres affichées sont très faibles ($\ll 1$), indiquant un très léger écart à l'indépendance : on est loin d'une association exclusive entre lignes et colonnes.

Lu dans une copie (je n'y avais pas songé) : l'axe 1 semble représenter la qualité du vin tandis que le second axe correspondrait à peu près au taux de dioxyde de soufre.