Prévision pac-bayésienne pour le modèle additif
sous contrainte de parcimonie
Benjamin Guedj 1 , Pierre Alquier 2 , Gérard Biau 1 et Éric Moulines 3
1LSTA, Université Pierre et Marie Curie – Paris VI
Boı̂te 158, Tour 15-25, 2ème étage
4 place Jussieu, 75252 Paris Cedex 05, France
benjamin.guedj@upmc.fr
gerard.biau@upmc.fr
2LPMA, Université Paris Diderot – Paris VII
Boı̂te 188, 175 rue du Chevaleret75013 Paris, France
alquier@math.jussieu.fr
3LTCI, Telecom ParisTech
37/39 rue Dareau, 75014 Paris, Francemoulines@telecom-paristech.frRésumé. Nous nous intéressons dans ce travail à la construction et à la mise enoeuvre d’une méthode de prévision dans le modèle additif, sous contrainte de parcimonie.
L’estimateur de Gibbs est au coeur de notre approche. Cet estimateur est construit à l’aided’une loi a priori favorisant les solutions parcimonieuses. Nous justifions notre démarche
en fournissant une inégalité oracle PAC-bayésienne originale et une implémentation faisantappel à des techniques MCMC récentes.
Mots-clés. Modèles additifs, régression, théorie PAC-bayésienne, parcimonie, inégalité
oracle, algorithmes MCMC.
Abstract. We adress the issue of prediction in high dimensional additive models,under a sparsity constraint. Our method strongly relies on the Gibbs estimator, whichoriginates from a prior distribution favoring sparse estimates. We provide the reader witha PAC-bayesian oracle inequality and an explicit implementation using recent MCMC
techniques.
Keywords. Additive models, regression, PAC-bayesian theory, sparsity, oracle inequality, MCMC algorithms.

11Introduction

Au cours des dernières années, de nombreuses méthodes d’estimation et de sélection devariables ont été proposées pour résoudre des problèmes de régression en grande dimension
sous contrainte de parcimonie. La méthode des moindres carrés avec une pénalité `1(LASSO) a de loin été la plus étudiée ; ses propriétés statistiques sont aujourd’hui bien
comprises. Plusieurs autres méthodes ont été introduites (Elastic net, Dantzig selector,etc.). Ces estimateurs sont obtenus comme solutions d’un problème convexe (ou linéaire),qui admettent des solutions numériquement efficaces. En particulier, Hastie, Tibshirani
et Friedman (2008), Meier, van de Geer et Bühlmann (2009) et Ravikumar, Rafferty, Liuet Wasserman (2009) présentent de telles stratégies pour le modèle additif qui est le cadrede ce travail.
Ces différentes procédures ont des propriétés statistiques intéressantes essentiellement
sous des conditions techniques restrictives. Ces conditions, dans un contexte de régressionlinéaire, impliquent typiquement que tous les sous-ensembles de régresseurs sont approximativement orthogonaux. Ces hypothèses sont relativement naturelles lorsque l’objectif
est de déterminer les variables significatives dans un ensemble de régresseurs. Elles le sontbeaucoup moins lorsque l’objectif est de construire des algorithmes de prévision.
D’un point de vue théorique, il existe des estimateurs optimaux pour la prévision qui
ne requièrent aucune hypothèse sur la matrice de régression. C’est le cas en particulier del’estimateur des moindres carrés sous la pénalité `0 . Toutefois, le calcul d’un tel estimateur
est un problème NP-difficile ; ce problème a suscité un grand nombre de recherches visantà construire des estimateurs ayant de bonnes propriétés théoriques pour la prévision tout
en restant numériquement implémentables.
Dans ce travail, nous nous intéressons à l’étude théorique et à la mise en oeuvre d’une
stratégie obéissant à ces considérations, pour le modèle additif. Le modèle additif est unavatar important de la statistique contemporaine, voir par exemple Friedman et Stuetzle(1981) et Hastie et Tibshirani (1990) pour une formalisation. Notre stratégie se décline
en trois axes.
• L’estimateur de Gibbs, qui dépend du choix d’une distribution a priori favorisantles estimateurs parcimonieux (voir Catoni (2004)).
• La théorie PAC-bayésienne, amorcée par Shawe-Taylor et Williamson (1997) etMcAllester (1999), et formalisée par Catoni (2007), nous fournit une inégalité oracle.
• L’algorithme Subspace Carlin & Chib, issu de Petralias et Dellaportas (2011), permet d’échantillonner efficacement des lois de grandes dimensions.
Ce travail s’inscrit dans le prolongement théorique et méthodologique de Alquier etBiau (2011).

22Notations

Nous considérons une collection Dn = {(X1 , Y1 ), . . . , (Xn , Yn )} de copies i.i.d. d’unevariable (X, Y ) à valeurs dans Rp × R, avec la notation Xi = (Xi1 , . . . , Xip ) pour touti ∈ {1, . . . , n}. Nous nous plaçons dans le paradigme p  n. Le modèle additif s’écrit?

Yi = Ψ (Xi ) + Wi =pX

Ψ?j (Xij ) + Wi ,(1)j=1où W = (W1 , . . . , Wn ) est une collection de bruits i.i.d., dont nous saurons contrôler lesdéviations des moments successifs. Rappelons que notre objectif est de construire une
stratégie d’estimation de Ψ? .
Hypothèse 1. Il existe deux constantes positives L et σ 2 telles que pour tout entierk ≥ 2 et tout i ∈ {1, . . . , n}, k!
E |W |k | X ≤ σ 2 Lk−2 .
2(2)Il est à noter que cette hypothèse est particulièrement faible : en particulier, elle est
satisfaite si W est un bruit gaussien.
La fonction de régression Ψ? se décompose additivement sur chacun des régresseurs.
La seconde hypothèse consistera à supposer que Ψ? est bornée (au sens du supremum).
Hypothèse 2. Il existe une constante C > max(1, σ) telle que kΨ? k∞ < C.
Enfin, nous adjoignons à ce modèle une contrainte de parcimonie, c’est-à-dire que noussupposons que la dimension effective p? de Ψ? est inférieure à p. En d’autres termes, ungrand nombre des Ψ?j sont identiquement nulles.
Nous sommes maintenant en mesure de détailler notre procédure d’estimation. Considérons un dictionnaire dePfonctions connu, noté {ϕk }Kk=1 , avec K un nombre entier connu.
Les estimateurs de Ψ? = pj=1 Ψ?j que nous envisagerons seront de la forme suivante :Ψ̂θ =pXΨ̂j =j=1p mjXXθ̂jk ϕk ,j=1 k=1où mj désigne, pour tout j ∈ {1, . . . , p}, l’ordre du développement de Ψ̂j dans le dictionnaire, et θ̂ est une matrice de taille p × K de nombres réels. Par conséquent, un modèlesera la donnée d’un sous-ensemble S de {1, . . . , p}, désignant les régresseurs actifs, et d’unvecteur mS de taille |S|, des ordres de développement dans le dictionnaire de chacun desestimateurs Ψ̂j . La contrainte de parcimonie nous poussera naturellement à sélectionnerdes estimateurs avec un ensemble S de petit cardinal.
3En lien avec la méthodologie bayésienne classique, nous définissons une loi a priori π, chargeant avec une plus grande probabilité les estimateurs parcimonieux. Plusprécisément,X α−|S|XP(3)
π(θ) ∝β − `∈S m` π(S,mS ) (θ),
p
S⊂{1,...,p}|S|

mS ∈{1,...,K}|S|où α, β > 0 sont des paramètres de pénalisation, et π(S,mS ) la distribution uniforme surla boule de rayon C dans le modèle (S, mS ). Pour un certain paramètre de températureδ > 0, nous considérons ensuite la loi a posteriori de Gibbs ρ̂δ définie comme suit :dρ̂δ(θ) = exp(−δRn (Ψ̂θ )),dπ(4)où Rn désigne le risque empirique.
Notre estimateur Ψ̂Gibbs est alors une réalisation d’une variable tirée suivant la loi ρ̂δ .

3Inégalité oracle PAC-bayésienne et implémentation

Nous présentons ici notre principal résultat théorique. Nous désignons par R le risquequadratique classique.
n. Pour tout réel ε ∈ ]0, 1[, avecThéorème. Soit w = 8C max(L, C) et δ = 2w
probabilité au moins 1 − 2ε,(|S| log(n) XR(Ψ̂Gibbs ) − R(Ψ? ) ≤ Ξ
infinf R(Ψ̂θ ) − R(Ψ? ) ++mjθS⊂{1,...,p}nn j∈Sm∈{1,...,K}|S| )
11+ log,nεoù Ξ est une constante positive ne dépendant que de σ, C, L, α et β.
Ce théorème admet l’interprétation suivante : le risque théorique de notre estimateur
est borné parle meilleur risque atteignable sur l’ensemble des modèles, plus un termelog(n) P|S|+ nj∈S mj dépendant de la taille du modèle.
nIl s’agit enfin d’échantillonner selon la loi ρ̂δ . Cette loi, de dimension très grande,représente une gageure pour les algorithmes MCMC classiques, pour lesquels la vitessede convergence chute drastiquement lorsque la dimension de la loi à échantillonner augmente. Nous proposons donc une version de l’algorithme Subspace Carlin & Chib, dontl’idée essentielle consiste à échantillonner, tout au long de la chaı̂ne, dans des voisinages
correctement choisis du modèle courant.
L’algorithme (codé à l’aide du logiciel R) ainsi que ses performances sur donnéessimulées et réelles seront présentés oralement.
4

Bibliographie[1] Alquier, P. and Biau, G. (2011), Sparse Single-Index Model, preprint. http://www.
lsta.upmc.fr/BIAU/ab.pdf[2] Catoni, O., Statistical Learning Theory and Stochastic Optimization, Lectures on Probability Theory and Statistics, École d’été de Probabilités de Saint-Flour XXXI, Springer,
2004.
[3] Catoni, O., PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, volume 56 of IMS Lecture Notes Monograph Series. Institute of Mathematical Statistics, 2007.
[4] Friedman, J. H. and Stuetzle, W. (1981), Projection Pursuit Regression, Journal of theAmerican Statistical Association, 76:817–823.
[5] Hastie, T. J. and Tibshirani, R. J., Generalized Additive Models, Chapman & Hall/CRC,
1990.
[6] Hastie, T. J., Tibshirani, R. J., and Friedman, J. H., The Elements of Statistical
Learning, 2nd Edition, Springer-Verlag, 2008.
[7] McAllester, D. (1999), Some PAC-Bayesian Theorems, COLT’98 Proceedings, Machine
Learning 37(3): 355-363.
[8] Meier, L., van de Geer, S. and Bühlmann, P. (2009), High-dimensional Additive Modeling, The Annals of Statistics, 37: 3779-3821.
[9] Petralias, A. and Dellaportas, P. (2011), An MCMC model search algorithm for regression problems, preprint. http://stat-athens.aueb.gr/~apet/model_choice_17_
website.pdf[10] R Development Core Team (2011), R: A language and environment for statisticalcomputing, R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-070, URL http://www.R-project.org/.
[11] Ravikumar, P., Lafferty, J., Liu, H. and Wasserman, L. (2009), Sparse Additive
Models, Journal of the Royal Statistical Society, Series B, 71(5):1009-1030.
[12] Shawe-Taylor, J. and Williamson, R. C. (1997), A PAC Analysis of a Bayes Estimator,
COLT’97 Proceedings.

5