17 Estimateurs à noyau et \(k\) plus proches voisins

Exercice 1 (Questions de cours)  

  1. A
  2. B
  3. A

Exercice 2 (Estimateur de Nadaraya-Watson) Il suffit de dériver la quantité à minimiser par rapport à \(\beta_1\) et la valeur de \(\beta_1\) qui annule cette dérivée : \[-2\sum_{i=1}^n(y_i-\beta_1)p_i(x)=0\quad\Longleftrightarrow \quad\widehat\beta_1(x)=\frac{\sum_{i=1}^ny_ip_i(x)}{\sum_{i=1}^np_i(x)}.\]

Exercice 3 (Polynômes locaux)  

Exercice 4 (Estimateur à noyau uniforme dans \(\mathbb R^p\))  

  1. En annulant la dérivée par rapport à \(a\), on obtient \[\widehat m(x)=\frac{\sum_{i=1}^ny_iK\left(\frac{\|x_i-x\|}{h}\right)}{\sum_{i=1}^nK\left(\frac{\|x_i-x\|}{h}\right)}.\]

  2. On a \[\mathop{\mathrm{V}}[\widehat m(x)]= \frac{\sigma^2}{\sum_{i=1}^nK\left(\frac{\|x_i-x\|}{h}\right)}\] et \[\mathbf E[\widehat m(x)]-m(x)=\frac{\sum_{i=1}^n(m(x_i)-m(x))K\left(\frac{\|x_i-x\|}{h}\right)}{\sum_{i=1}^nK\left(\frac{\|x_i-x\|}{h}\right)}.\]

  3. On a maintenant \(|m(x_i)-m(x)|\leq L\|x_i-x\|\). Or \[K\left(\frac{\|x_i-x\|}{h}\right)\] est non nul si et seulement si \(\|x_i-x\|\leq h\). Donc pour tout \(i=1,\dots,n\) \[L\|x_i-x\|K\left(\frac{\|x_i-x\|}{h}\right)\leq Lh K\left(\frac{\|x_i-x\|}{h}\right).\] D’où le résultat.

  4. On a \[\mathop{\mathrm{V}}[\widehat m(x)]= \frac{\sigma^2}{\sum_{i=1}^nK\left(\frac{\|x_i-x\|}{h}\right)}=\frac{\sigma^2}{\sum_{i=1}^n\mathbf 1_{B_h}(x_i-x)}.\] Or \[\sum_{i=1}^n\mathbf 1_{B_h}(x_i-x)\geq C_1n\textrm{Vol}(B_h)\geq C_1\gamma_dnh^d\] où \(\gamma_d=\pi^{d/2}/\Gamma(d/2+1)\). On a donc \[\mathop{\mathrm{V}}[\widehat m(x)]\leq \frac{\sigma^2}{C_1\gamma_dnh^d}=\frac{C_2\sigma^2}{nh^d}\] avec \(C_2=1/(C_1\gamma_d)\).

  5. On déduit \[\mathbf E[(\widehat m(x)-m(x))^2]\leq L^2h^2+\frac{C_2\sigma^2}{nh^d}.\]

  6. Soit \(M(h)\) le majorant ci-dessus. On a \[M(h)'=2hL^2-\frac{C_2\sigma^2d}{n}h^{-d-1}.\] La dérivée s’annule pour \[h_{opt}=\frac{2L^2}{C_2\sigma^2d}n^{-\frac{1}{d+2}}.\] Lorsque \(h=h_{opt}\) l’erreur quadratique vérifie \[\mathbf E[(\hat m(x)-m(x))^2]=\mathrm{O}\left(n^{-\frac{2}{d+2}}\right).\] La vitesse diminue lorsque la dimension \(d\) augmente, c’est le fléau de la dimension.

Exercice 5 (Vitesse de la régression univariée en design equi-espacé)  

  1. \(\widehat\beta\) minimise \(\sum_{i=1}^n(Y_i-\beta x_i)^2\). On a donc \[\widehat\beta=\frac{\sum_{i=1}^nx_iY_i}{\sum_{i=1}^nx_i^2}.\]

  2. On déduit \[\mathbf E[\widehat\beta]=\beta\quad\textrm{et}\quad\mathop{\mathrm{V}}(\widehat\beta)=\frac{\sigma^2}{\sum_{i=1}^nx_i^2}.\]

  3. Comme \[\sum_{i=1}^nx_i^2=\frac{(n+1)(2n+1)}{6n},\] on obtient le résultat demandé.

Exercice 6 (Critère LOO)  

  1. On désigne par \(\widehat F_h\) le vecteur \((\widehat f_h(x_i),i=1,\dots,n)\), \(\widehat F_k\) le vecteur \((\widehat f_k(x_i),i=1,\dots,n)\) et \(\mathbb Y=(y_1,\dots,y_n)\). On voit facilement que \[\widehat F_h=S_h\mathbb Y\quad\text{et}\quad \widehat F_k=S_k\mathbb Y\] où \(S_h\) et \(S_k\) sont des matrices \(n\times n\) dont le terme général est défini par \[S_{ij,h}=\frac{K((x_i-x_j)/h)}{\sum_l K((x_i-x_l)/h)} \quad\text{et}\quad S_{ij,k}= \left\{ \begin{array}{ll} 1/k&\text{ si $x_j$ est parmi les $k$-ppv de $x_i$} \\ 0 & \text{ sinon}. \end{array} \right.\]

  2. Pour simplifier on note \(K_{ij}=K((x_i-x_j)/h)\) On a \[\widehat f_h^i(x_i)=\frac{\sum_{j\neq i}K_{ij}y_j}{\sum_{j\neq i}K_{ij}}.\] Par conséquent \[\widehat f_h^i(x_i)\left[\sum_{j=1}^nK_{ij}-K_{ii}\right]=\sum_{j\neq i}K_{ij}y_j.\] On obtient le résultat demandé en divisant tout \(\sum_{j=1}^nK_{ij}\). Pour l’estimateur de plus proches voisins, on remarque que, si on enlève la \(i\)ème observation alors l’estimateur des \(k\) plus proches voisins de \(x_i\) s’obtient à partir ce celui des \(k+1\) plus proches voisins avec la \(i\)ème observation de la façon suivante : \[\widehat f_k^i(x_i)=\frac{k+1}{k}\sum_{j\neq i}S_{ij,k+1}y_j.\] On obtient le résultat demandé on observant que \(S_{ii,k+1}=1/(k+1)\) et donc \[\frac{1}{1-S_{ii,k+1}}=\frac{k+1}{k}.\]

  3. On obtient pour l’estimateur à noyau \[\begin{align*} LOO(\widehat f_h)= & \frac{1}{n}\sum_{i=1}^n\left(y_i-\widehat f_h^i(x_i)\right)^2 \\ = & \frac{1}{n}\sum_{i=1}^n\left(\frac{y_i-S_{ii,h}y_i-\sum_{j\neq i}S_{ij,h}y_{j}}{1-S_{ii,h}}\right)^2 \\ = & \frac{1}{n}\sum_{i=1}^n\left(\frac{y_i-\widehat f_h(x_i)}{1-S_{ii,h}}\right)^2. \end{align*}\] Le calcul est similaire pour l’estimateur des plus proches voisins.

Exercice 7 (Caret et kppv) On importe les données et on ne garde que les deux variables demandées :

ozone <- read.table("../donnees/ozone.txt",header=TRUE,sep=";")
df <- ozone[,c("O3","T12")]

On construit la grille de plus proches voisins candidats :

grille <- data.frame(k=1:40)

On indique à caret qu’on veut faire de la validation croisée 10 blocs :

library(caret)
ctrl <- trainControl(method="cv")

On lance la validation croisée avec la fonction train :

set.seed(1234)
sel.k <- train(O3~.,data=df,method="knn",trControl=ctrl,tuneGrid=grille)
sel.k
k-Nearest Neighbors 

50 samples
 1 predictor

No pre-processing
Resampling: Cross-Validated (10 fold) 
Summary of sample sizes: 44, 46, 45, 44, 45, 45, ... 
Resampling results across tuning parameters:

  k   RMSE      Rsquared   MAE     
   1  25.39941  0.2777479  21.83800
   2  20.89184  0.3784027  17.05972
   3  17.81455  0.5039548  14.88541
   4  16.49216  0.5636676  14.01838
   5  16.75867  0.5579746  14.33716
   6  16.76845  0.5384320  13.92737
   7  16.11270  0.5792998  13.77474
   8  15.96855  0.5992164  13.64931
   9  16.48290  0.5679445  14.13226
  10  16.89146  0.5572318  14.62217
  11  17.14669  0.5541549  14.68934
  12  17.69184  0.5469553  15.27732
  13  17.41791  0.5668045  15.10278
  14  17.53775  0.5484378  15.17445
  15  17.61846  0.5669393  15.35179
  16  17.89693  0.5550383  15.60799
  17  18.08559  0.5579067  15.72184
  18  18.25932  0.5655324  15.89826
  19  18.84244  0.5402343  16.27675
  20  19.08747  0.5429639  16.30312
  21  19.44070  0.5266746  16.57676
  22  19.66410  0.5196443  16.65315
  23  19.69539  0.5339187  16.60436
  24  19.94851  0.5245251  16.73931
  25  20.04650  0.5072557  16.78093
  26  20.14871  0.5013264  16.78305
  27  20.28257  0.5036138  16.89089
  28  20.45060  0.4988594  16.89900
  29  20.54389  0.5105147  16.92002
  30  20.79567  0.5080200  17.12472
  31  20.96099  0.5014461  17.25705
  32  21.14524  0.4891512  17.23304
  33  21.38173  0.4875148  17.38980
  34  21.59260  0.4810615  17.43883
  35  21.83266  0.4707654  17.67392
  36  22.06004  0.4448406  17.74640
  37  22.34462  0.4236828  17.95419
  38  22.54304  0.3999950  18.11507
  39  22.61034  0.4147744  18.15091
  40  22.68049  0.4296545  18.23871

RMSE was used to select the optimal model using the smallest value.
The final value used for the model was k = 8.

On sélectionnera

sel.k$bestTune
  k
8 8

plus proches voisins.