Agrégation 2023 - Épreuve 3b¶
Sujet
Corrigé partiel du sujet de l'épreuve 3b (fondements de l'informatique) de l'agrégation externe d'informatique, session 2023. L'énoncé n'est pas reproduit ici : il faut le consulter à côté de ce corrigé. Les questions sont numérotées comme dans l'énoncé ; certaines ne sont pas (encore) corrigées.
Partie I. Le cas d'un neurone à seuil¶
Fonctions booléennes linéaires à seuil¶
Question 1.
Corrigé
On remarque tout de suite que \(x_1 + \dots + x_n\) est le nombre de \(x_i\) égaux à 1 car ils sont dans \(\mathbb{B} = \{ 0, 1\}\).
a. \(x_1 + \dots + x_n \ge 1 \iff \exists i, x_i = 1 \iff OR(x_1,\dots,x_n) = 1\).
b. \(-x \ge 0 \iff x \le 0 \iff x = 0 \iff NOT_1(x) = 1\).
c. \(x_1 + \dots + x_n \ge n/2\) si et seulement si il y a au moins \(n/2\) \(x_i\) égaux à 1 et donc si et seulement si \(MAJORITY(x_1, \dots, x_n) = 1\).
Question 2.
Corrigé
Par l'absurde, s'il existe \(\alpha, \beta, h\) tels que \(\alpha x + \beta y \ge h \iff XOR(x, y) = 1\), alors, comme \(XOR(0,1) = XOR(1,0) = 1\), on aura \(\alpha \ge h\) et \(\beta \ge h\), ainsi \(\alpha + \beta \ge 2h\).
Ici, il faut raisonner selon le signe de \(h\) : si \(h \ge 0\), alors \(2h \ge h\), on en déduit \(\alpha+\beta \ge h\) et donc \(XOR(1,1) = 1\).
Si \(h < 0\), alors \(0 \times \alpha + 0 \times \beta = 0 \ge h\) et donc \(XOR(0,0) = 1\).
Dans les deux cas, on aboutit à une contradiction.
Question 3.
Corrigé
C'est ici une généralisation de l'argument précédent. On suppose \(n \ge 2\).
Supposons, par l'absurde, qu'il existe \(\alpha_1, \dots, \alpha_n, h\) tels que \(\alpha_1 x_1 + \dots + \alpha_n x_n \ge h \iff PARITY_n(x_1, \dots, x_n) = 1\).
Comme \(PARITY_n(0, \dots, 0) = 1\), on a \(0 \ge h\).
Mais comme \(PARITY_n(x_1,\dots, x_n) = 0\) dans le cas où seul \(x_i = 1\), on a \(\alpha_i < h\).
Ainsi \(\alpha_1 + \alpha_2 < 2h \le h\) car \(h \le 0\), donc la fonction à seuil vaut 0 en \((1,1,0,\dots,0)\), alors que \(PARITY_n(1,1,0,\dots,0) = 1\).
Contradiction.
Cas de domaines bornés¶
Les questions 4 à 8 ne sont pas corrigées.
Apprentissage d'un neurone à seuil¶
Remarque
Dans cette partie on manipule des ensembles finis d'éléments de \(D^n\), il y a donc un double indiçage.
On va donc noter \(\underline{x_i}\) les éléments indicés de \(D^n\) pour bien marquer le double indiçage \(\underline{x_i}_j\).
Question 9.
Corrigé
Soit \(X = \{ (\underline{x_1},y_1), \dots, (\underline{x_N},y_N) \}\) un jeu d'exemples où les \(\underline{x_i} \in D^n\).
On va poser \(\varphi(\underline{x_i}) = (\underline{x_i}_1,\dots,\underline{x_i}_n,-1)\) et on considère \(X' = \enscomp{ (\varphi(x),y) }{(x,y) \in X}\).
Soit \(G\) solution du problème exact d'apprentissage à seuil nul sur \(X'\).
On pose \(F : D^n \rightarrow \mathbb{B}\) définie par \(F(a_1, \dots, a_n) = G(a_1, \dots, a_n, -1)\).
Pour tout élément \((\underline{x}, y) \in X\), on a donc \(F(\underline{x}) = G(\varphi(\underline{x})) = y\).
Par définition de \(G\), il existe \((w_1, \dots, w_n, h)\) tels que \(F(a_1, \dots, a_n) = G(a_1,\dots,a_n,-1) = 1 \iff w_1 a_1 + \dots + w_n a_n - h \ge 0 \iff w_1 a_1 + \dots + w_n a_n \ge h\).
On a donc résolu le problème exact d'apprentissage à seuil en dimension \(n\).
Question 10.
Corrigé
i) On va considérer ici une fonction linéaire à seuil nul \(H\) sur \([-1,1]^n\) et établir quelques résultats. On considère que les poids sont \((w_1, \dots, w_n)\) et on considère \((a_1, \dots, a_n) \in [-1,1]^n\).
Tout d'abord un résultat propre aux fonctions linéaires à seuil nul : si \(\sum w_i a_i = 0\) on a forcément \(H(a_1, \dots, a_n) = H(-a_1, \dots, -a_n) = 1\).
Si \(\sum_i w_i a_i \neq 0\), on a :
Ainsi, dans tous les cas, si \(H(a_1,\dots,a_n) = 0\) alors \(H(-a_1, \dots, -a_n) = 1\).
ii) Soit \(X = \{ (\underline{x_1},y_1), \dots, (\underline{x_N},y_N) \}\) un jeu d'exemples où les \(\underline{x_i} \in D^n\).
On reprend les notations de la question précédente, on pose
Soit \(H\) solution du problème exact d'apprentissage à seuil nul sur \(X''\) qui est en dimension \(n+1\) sur le domaine \([-1,1]\).
On pose \(F : D^n \rightarrow \mathbb{B}\) définie par \(F(a_1, \dots, a_n) = H(a_1, \dots, a_n, -1)\).
Par définition de \(H\), il existe \((w_1, \dots, w_n, h)\) tels que \(F(a_1, \dots, a_n) = H(a_1,\dots,a_n,-1) = 1 \iff w_1 a_1 + \dots + w_n a_n - h \ge 0 \iff w_1 a_1 + \dots + w_n a_n \ge h\).
Reste à montrer que \(F\) satisfait les exemples \(X\).
Soit \((\underline{x}, y) \in X\).
Si on a \(y = 1\), alors \(H(-\varphi(\underline{x})) = 0\) et donc \(F(\underline{x}) = H(\varphi(\underline{x})) = 1 = y\) par le i).
Si on a \(y = 0\), alors \(F(\underline{x}) = H(\varphi(\underline{x})) = 0 = y\).
Dans tous les cas \(F(\underline{x}) = y\) donc \(F\) est solution au problème d'apprentissage à seuil.
Question 11.
Corrigé
Note : il est inutile de passer la dimension en paramètre vu que c'est la longueur commune des vecteurs (on suppose qu'il y a au moins un exemple).
type vecteur = float array
let vectorize op v1 v2 =
let n = Array.length v1 in
Array.init n (fun i -> op v1.(i) v2.(i))
let difference = vectorize (-.)
let produit_scalaire v1 v2 =
vectorize ( *.) v1 v2
|> Array.fold_left (+.) 0.
let apprentissage exemples =
let n = Array.length exemples.(0) in
let w = Array.make n 0. in
let rec epoque () =
let modifie = ref false in
Array.iter
(fun x -> if produit_scalaire w x >= 0.
then begin
modifie := true;
Array.blit (difference w x) 0 w 0 n
end) exemples;
if !modifie
then epoque ()
in
epoque ();
Array.append w [|0.|]
Par exemple, sur les exemples [| [|-1.; -1.; 1.|]; [|1.; 0.; -1.|];
[|0.; 1.; -1.|]; [|0.; 0.; -1.|] |], la fonction renvoie [|2.; 3.; 4.; 0.|].
Question 12.
Corrigé
Par condition d'arrêt (une époque sans modification), le vecteur \((w_1, \dots, w_n, 0)\) renvoyé vérifie \(\sum w_i x_i < 0\) pour chaque exemple \((x,0)\) donc si \(F\) est la fonction associée, on a \(F(x) = 0\) et on a bien une solution au problème.
Question 13.
Corrigé
Soit \((v_1, \dots, v_n, 0)\) une représentation \(n\)-séparable de \(F\).
On a donc :
- \(F(x_1, \dots, x_n) = 0 \iff \sum_i v_i x_i < 0 \iff \sum_i v_i x_i \le -n\) ;
- en particulier \(\forall (x,0) \in X, \sum_i v_i x_i \le -n\).
On considère pour un candidat représentation \(w\) : \(d(v,w) = ||v-w||^2 = \sum_i (v_i - w_i)^2\).
Soit \(w\) la valeur à une époque et \((x,0) \in X\) un exemple pour lequel on a l'erreur \(\sum_i w_i x_i \ge 0\).
On va poser \(w' = w - x\).
On a
Or, \(x \in D^n\) donc \(||x||^2 \le n\) et \(\sum_i w_i x_i \ge 0\), donc \(d(v,w) - d(v,w') \ge n > 0\). Ainsi la distance diminue d'au moins \(n\) à chaque modification ; comme elle est positive et vaut \(||v||^2\) au départ, il y a au plus \(||v||^2 / n\) modifications. Une époque sans modification arrête la boucle, donc la boucle s'arrête.
Question 14.
Corrigé
On note \(\mu\) la masse de \(v\) pour ne pas avoir de confusion avec les poids \(w\). Chaque \(|v_i|\) est au plus \(\mu\), donc \(||v||^2 \le n \mu^2\).
On a \(x \cdot v \le -1\) car \(v\) est 1-séparable.
On reprend les calculs précédents. On a donc \(w' \cdot v = w \cdot v - x \cdot v \ge w \cdot v + 1\). Comme au départ \(w = \vec{0}\), après \(M\) erreurs, on a donc \(w \cdot v \ge M\).
On a également \(||w'||^2 = ||w - x||^2 = ||w||^2 - 2 (w \cdot x) + ||x||^2\). Or, \(||x||^2 \le n\) et \(-(w \cdot x) \le 0\), ainsi \(||w'||^2 \le ||w||^2 + n\) : la norme au carré des poids augmente au maximum de \(n\) à chaque erreur. Après \(M\) erreurs, on a donc \(||w|| \le \sqrt{nM}\).
Or, par l'inégalité de Cauchy-Schwarz, \(w \cdot v \le ||w|| \, ||v|| \le \sqrt{nM} \sqrt{n} \mu = n \mu \sqrt{M}\). Donc \(M \le n \mu \sqrt{M}\) et ainsi \(M \le n^2 \mu^2\), donc \(M = O(n^2 \mu^2)\).
Chaque époque, sauf la dernière, comporte au moins une erreur : il y a donc au plus \(M + 1\) époques. Une époque coûte \(O(nN)\) calculs pour les tests de produits scalaires sur les \(N\) exemples et \(O(n)\) par modification de \(w\). Au total, on est ainsi en \(O(n^3 \mu^2 N)\).
D'un neurone à seuil à un réseau de neurones¶
Question 15.
Corrigé
Ce circuit est de profondeur 2.
- Couche 0 : \(x_1, x_2, x_3\)
- Couche 1 : \(NOT_1\) de gauche, \(OR_2\) et \(AND_2\)
- Couche 2 : \(NOT_1\) en bas
Des circuits booléens aux réseaux de neurones à seuil¶
Question 16.
Corrigé
type sommet = int
type seuil = float
type poids = float
type reseau_adjacence = ((sommet * poids) list * seuil) array
let creer n = Array.make n ([], 0.)
let teste_arc r x y =
fst r.(x) |> List.map fst |> List.mem y
let ajoute_arc r x y w =
let l, t = r.(x) in
r.(x) <- ((y,w) :: l, t)
Question 17.
Corrigé
Chacune des portes logiques utilisées admet une représentation entière avec des poids égaux à \(1\) ou \(-1\) (question 1), donc de poids unitaires. Il suffit alors de remplacer les portes par les neurones associés.
On préserve ainsi la structure du réseau, a fortiori sa profondeur et sa taille.
Question 18.
Corrigé
Il suffit de rajouter un neurone identité pour rendre les connexions plus profondes.