Scribd
Importer
38 vues3 pages

Examen Machine Learning M1 MINT 2017-2018

Ce document contient deux exercices portant sur le machine learning. Le premier exercice demande de calculer des erreurs empiriques pour différents algorithmes sur un jeu de données à deux dimensions. Le deuxième exercice pose des questions sur la classification binaire par des rectangles sur un autre jeu de données.

Transféré par

Selma Ben Sassi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
38 vues3 pages

Examen Machine Learning M1 MINT 2017-2018

Ce document contient deux exercices portant sur le machine learning. Le premier exercice demande de calculer des erreurs empiriques pour différents algorithmes sur un jeu de données à deux dimensions. Le deuxième exercice pose des questions sur la classification binaire par des rectangles sur un autre jeu de données.

Transféré par

Selma Ben Sassi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Année 2017-2018 M1 MINT

Introduction au Machine learning : examen

Exercice 1
On a observé les données suivantes : les features sont dans R2 et les labels sont dans {rouge, bleu}.

1. Donner les valeurs de l’erreur empirique associée à la perte 0/1 des classifieurs construits par
• l’algorithme des 1-plus proche voisins (1-NN)
• l’algorithme des 3-plus proche voisins (3-NN).
2. Où metteriez vous le premier “split” d’un arbre de décision ? (vous pouvez le dessiner sur la
figure)
3. A partir de quelle profondeur a-t-on un arbre d’erreur empirique nulle ?
4. Tracer l’hyperplan (ici la droite) associé à l’algorithme linear-SVM.

Exercice 2
On définit r⋆ comme le rectangle [l, r]×[b, t]. On considèrent des données Dn = {(Xi , Yi ), i = 1, . . . , n}
avec des couples features/label (Xi , Yi ) i.i.d., Xi ∈ R2 et Yi ∈ {1 = rouge, −1 = bleu} dont la loi
vérifie
P(Yi = 1|Xi ∈ r⋆ ) = 1
P(Yi = 1|Xi ∈/ r⋆ ) = 0
P(Xi ∈ r⋆ ) > ϵ pour un ϵ > 0 fixé .
On construit un classifieur en se restreignant à la classe des classifieurs indexés par des rectangles
{cr , r = [a, b] × [c, d], a < b, c < d} et définis par

c si x ∈ r
r (x)
=1
cr (x) = 0 si x ∈
/ r.

1
1. Quelle est l’erreur empirique (associée à la perte 0/1) du rectangle vert dessiné sur la figure 1
que l’on note ici r̂ ?

2. Soit un classifieur cr . On considère une nouvelle observation (X+ , Y+ ). Dans quelle zone du
plan doit être X+ pour que cette observation soit mal classée par le classifieur cr ?

3. On définit quatre rectangles rl⋆ , rt⋆ , rr⋆ , rb⋆ (l pour “left”, t pour “top”, r pour “right” et b pour
“bottom”), les rectangles rl⋆ , rt⋆ ont été représentés sur la figure 2. Chacun de ces rectangles
vérifie
P(X+ ∈ rk⋆ ) = ϵ/4 (k ∈ {l, t, r, b}).
Montrer que l’erreur de généralisation du classifieur crminus associé au rectangle (représenté sur
⋆
la figure 3) rminus = r⋆ \ ∪k∈{l,t,r,b} rk⋆ vérifie
∑
R(crminus
⋆ )≤ P(X+ ∈ rk⋆ ) = ϵ.
k∈{l,t,r,b}

4. On cherche maintenant à borner l’erreur de généralisation de cr̂ .


⋆
(a) Montrer que si rminus ⊂ r̂ alors R(crminus
⋆ ) ≥ R(cr̂ ).
(b) En déduire que
P (R(cr̂ ) > ϵ) ≤ P (rminus
⋆
̸⊂ r̂) .
(c) Montrer que (
∑ ϵ )n
P (rminus
⋆
̸⊂ r̂) ≤ P(r̂ ∩ rk⋆ = ∅) ≤ 4 1 − .
k∈{l,t,r,b}
4

(d) Que doit valoir n pour que le risque de cr̂ dépasse ϵ avec une probabilité inférieure à δ > 0.

2
3

Vous aimerez peut-être aussi