Théorie statistique de l'apprentissage [19, 7, 33 16]

Sous cette rubrique, je place le travail en « théorie statistique de l'apprentissage » proprement dite, et le travail sur l'estimation d'ordre qui relève aussi de la théorie de l'information.

Ce qu'on appelle, à la suite de Vapnik [66], la théorie statistique de l'apprentissage, reprend certains des thèmes classiques de la statistique [9]. La théorie de l'apprentissage aborde en effet les problèmes de régression, d'estimation de densité, mais elle se définit d'abord autour des problèmes de classification. Ces problèmes sont généralement abordés comme des problèmes de \" minimisation de contraste\". La perspective est le plus souvent minimax. L'objectif n'est pas d'estimer correctement les paramètres qui sous-tendent la production des données, mais plus qu'ailleurs, la minimisation de l'erreur de prédiction (mal classer une donnée, mal prédire la valeur d'un signal, déclencher une fausse-alarme). Un autre trait distinctif de la théorie de Vapnik est l'accent mis sur les résultats non-asymptotiques (inégalités stochastiques plutôt que théorèmes limites) et la recherche de solutions effectives aux problèmes d'optimisation posés par les statistiques (les problèmes naïvement posés s'avèrent souvent NP-difficiles en classification).

Précisons quelques aspects du problème de la classification. Dans la suite, X désigne l'espace dans lequel sont décrits les exemples. Dans le cas le plus simple, les exemples sont étiquetés par 0 ou 1. On suppose que les données à classer sont produites par des tirages aléatoires sur l'espace X×{0,1}. L'estimateur doit à partir d'un échantillon

Dn:=(⟨Xi,Yi⟩)in

XiX et Yi∈{0,1}, proposer un fonction de décision f telle que le risque effectif:

L(f):=P{f(X)≠Y}=E[|f(X) - Y|],

soit aussi petit que possible. Si la distribution des couples ⟨X,Y⟩ était connue, le classifieur Bayésien, noté f, ferait l'affaire. Mais cette distribution n'est pas connue en général. L'estimateur recherche en fait f dans une (très) grande bibliothèque F de fonctions de X vers {0,1} en optimisant un critère empirique dépendant des données, par exemple le risque de classification empirique:

Ln(f):=frac (1, n)∑ni=1|f(Xi) - Yi|.

Jusqu'au milieu des années 90, et encore aujourd'hui, la théorie de l'apprentissage s'est surtout concentrée sur le comportement de M-estimateurs.

Dans la suite, (f)^ désigne un élément de F qui minimise le risque empirique. Trois questions se posent:

  1. le contrôle de L (( f ) ^ ) - L n (( f ) ^ ),
  2. le contrôle de l'excès de risque: L (( f ) ^ ) - L ( f ),
  3. la difficulté calculatoire du calcul de ( f ) ^ .

En classification, les modèles vérifient rarement les propriétés de régularité postulées dans les livres de statistique. La minimisation du risque de classification empirique est analysée grâce à des techniques de processus empiriques.

Suprema et modules de continuités de processus empiriques.

Pour contrôler les quantités (1) et (2), on est ammené à étudier le supremum du processus empirique indexé par F:

Zn:=sup fF[L(f) - Ln(f)],

de plus l'excès de risque est majoré par

Wn=L((f)^) - Ln((f)^) - L(f) + Ln((f)^)

qui est l'incrément du processus empirique indexé par F entre f et (f)^.

Le comportement de Zn et de Wn, dans des perspectives asymptotiques ou non, a été caractérisé grâce à la théorie des processus empiriques. Sous des hypothèses assez générales sqrt (n)Zn se comporte à la limite comme le supremum d'un pont Brownien généralisé, et l'espérance de sqrt (n)Zn est contrôlée par des arguments de chaînage. Les déviations de Zn sont contrôlées par des inégalités de concentration.

Pour décrire l'évolution de E[sqrt (n)Zn], notons N(F,Dn,ε) le nombre minimal N de fonctions f1fN de X dans {0,1} qu'il faut utiliser pour que pour tout f de F, il existe j∈{1…N} vérifiant

infrac (1, n)|f(Xi) - fj(Xi)|≤ε.

L'ε-entropie de la classe F sur l'échantillon Dn est notée

log N(F,Dn,ε) ,

(1)

(lorsque ε<frac (1, 2n), on retrouve l'entropie de Vapnik-Chervonenkis). Les techniques de chaînage permettent alors de montrer que, :

E[sqrt (n)Zn]≤CE[∫10sqrt (log N(F,Dn,ε))dε],

(2)

C est une constante universelle. L'intégrale d'entropie peut alors être reliée à des quantités plus parlantes comme la dimension de Vapnik-Cervonenkis ou la fat-shattering-dimension.

Pour estimer L((f)^) - Ln((f)^), il s'avère utile d'estimer Zn. C'est l'objet premier dans la théorie de Vapnik [66, 30]. Si les travaux initiaux de Vapnik et Chervonenkis avaient montré l'intérêt des inégalités exponentielles pour les suprema de processus empiriques, depuis, la compréhension du phénomène de \" concentration de la mesure\" [46] a permis d'établir de veritables généralisations des inégalités de Bernstein/Bennett pour Zn, [61, 45, 51, 57, 22] Comprendre le comportement de Zn s'avère même suffisant pour caractériser l'excès de risque dans les situations les plus défavorables, c'est à dire lorsque la fonction de régression E[YX] est trop proche de 1/2 sur une partie trop importante du domaine [69, 70].

Mais l'un des traits originaux des problèmes de classification tient à la relation extrèmement flexible qui existe entre excès de risque et variance des incréments du processus empirique (ceci reflète la difficulté de la construction de compromis biais/variance dans les problèmes de classification). On peut parfois disposer de relations de la forme

V a r(Ln(f) - Ln(f))≤frac (c, n)(L(f) - L(f))κ

avec κ=1 dans le cas le plus favorable, et κ proche de 0, voire nul dans les cas les plus défavorables [49, 51, 63]. Dans le cas où κ=1, les problèmes de classifications ressemblent aux problèmes de régression, et on dispose en plus d'une condition de bornitude du contraste. On est donc à même d'adapter la procédure de Huber (\" peeling device\", voir [64, 65, 49, 52]), et de montrer que l'excès de risque décroit rapidement (en 1/n).

Pour majorer Wn et donc l'excès de risque dans les cas les plus favorables, il faut en fait estimer le \" module de continuité\" du processus empirique centré en f. Plus précisément, il faut chercher à estimer la solution de l'équation sqrt (n2=ϕ(σ) où ϕ est une fonction qui vérifie:

ϕ(σ)≥1/sqrt (n)E[supfF,E[|f - f|]≤σ2(L(f) - Ln(f) - L(f) - Ln(f))] .

Jusqu'à la fin des années 1990, la plupart des travaux théoriques sur ces questions comportaient pour les praticiens deux inconvénients. Soit ils cherchaient à produire des résultats universels, ne dépendant que de F et pas de la distribution des données. Ils fournissaient alors des bornes pessimistes, régardées comme des curiosités par les praticiens (voir par exemple [36] (p. 212)). Soit ces travaux cherchaient à produire des résultats dédiés à une distribution spécifique des données. Ces derniers résultats reflètaient mieux l'expérience des praticiens mais s'avèraient difficiles à exploiter, car la distribution des données est rarement connue en pratique. Cette situation est assez frustrante car une bonne connaissance de l'excès de risque et de L((f)^) - Ln((f)^) s'avèrent très désirables.

Questions de sélection de modèles En classification comme dans les autres problèmes d'inférence, une simple classe paramétrique de fonctions peut s'avérer insuffisante pour traiter une large gamme de problèmes. Bien qu'il n'existe pas de théorie de l'approximation pour les ensembles comme il existe une théorie de l'approximation pour les classes de fonctions [29], on a pris l'habitude de poser des problèmes de sélection de modèles en classification. On dispose alors d'une collection de modèles Fk avec kN, et d'une collection d'estimateurs (f)^k.

Au moins, deux perspectives sont à considérer (les questions d'adaptivité sont amplement discutées dans [6]):

  1. on peut chercher pour chaque échantillon Dn, à sélectionner une hypothèse (f)~ presque aussi bonne que la meilleure des hypothèses ((f)^k)k issues de notre collection de modèles, c'est-à-dire disposer avec une grande probabilité, de garanties de la forme:

    L((f)~)≤C minkL((f)^k) + εn ,

    C est une constante raisonnable et εn une quantité qui tend vers 0 quand n croît (idealement comme 1/n).

  2. on peut chercher à approcher le comportement d'un estimateur qui aurait été informé par un \" oracle\" du fait que k constituait le meilleur compromis possible, et chercher ainsi à minimiser l'excès de risque :

    E[L((f)~) - L(f)]≤C(E[L((f)^k) - L(f)]) + ε.

Lorsque on vise le premier type d'inégalités, on cherche à estimer

mink[Ln((f)^k) + (L((f)^k) - Ln((f)^k))]

Il est donc pertinent de chercher à contrôler uniformément (en k) les quantités (L((f)^k) - Ln((f)^k)).

Lorsqu'on vise le second type d'inégalités, on cherche à estimer l'excès de risque associé à chaque modèle.

Calibration de pénalités empiriques.

Le contrôle de ces quantités à partir des données représente une tâche de même nature que l'estimation de la variance.

Les articles [19, 7] proposent des techniques d'estimation de E[Zn] à partir des données. Ces techniques se sont avérées extrêmement pertinentes lorsqu'on s'est intéressé à l'estimation de l'exces de risque à partir des données. Les résultats principaux de [19, 7] portent sur la concentration de l'entropie de Vapnik-Chervonenkis et sur la concentration d'une notion très ancienne en théorie des processus empiriques: les moyennes conditionelles de Rademacher. Depuis [34], on sait que

frac (1, 2n)E[Eε[supfFni=1εi1Yif(Xi)D1n]]≤E[Zn]≤frac (2, n)E[Eε[supfFni=1εi1Yif(Xi)D1n]] ,

où les εi sont des variables symétriques à valeur dans { - 1,1}. Cet encadrement est à l'origine de pratiquement de toutes analyses du comportement de Zn.

Les moyennes conditionnelles de Rademacher se présentent comme des fonctionnelles compliquées de l'échantillon. De fait, M. Fromont a montré très récemment que ces moyennes conditionnelles de Rademacher constituent un cas particulier d'une large famille d'estimateurs de E[Zn] qui relèvent du \" bootstrap\". Estimer E[Zn] à partir de Rn(F)=Eε[supfFni=1εi1Yif(Xi)D1n] est une idée raisonable: Rn(F) est une quantité très stable: l'inégalité d'Efron-Stein [32] permet de montrer que la variance de Rn(F) est majorée par son espérance. Les versions exponentielles de l'inégalité d'Efron-Stein [20] permettent de majorer les moments exponentiels des moyennes conditionnelles de Rademacher par ceux d'une variable de Poisson de même espérance. Cette dernière remarque permet de contrôler simultanément les moyennes de Rademacher associées à toute une collection de modèles Fk, et de majorer avec forte probabilité [Ln((f)^k) + (L((f)^k) - Ln((f)^k))] par [Ln((f)^k) + c(Rn(Fk))/n] . Par ailleurs, le cacul des moyennes conditionnelles de Rademacher n'est pas plus difficile que celui de la minimisation du risque de classification empirique (au sens des Turing-réductions polynomiales randomisées) [7].

La possibilité de calibrer des pénalités à partir des moyennes conditionnelles de Rademacher a été soulignée à la même époque par Koltchinskii et Panchenko [43, 42]. Ces derniers auteurs avaient par ailleurs noté le fait que les moyennes conditionnelles de Rademacher ne sont pas modifiées si on considère les classifieurs obtenus en seuillant une combinaison convexe de fonctions de base (ceci permet d'aborder les problèmes de \" boosting\"). Le fait de disposer d'inégalités de type Bernstein pour les moyennes conditionnelles de Rademacher permet aussi de \" localiser\" l'analyse : pour toute sous-classe G de Fk, Rn(G) satisfait aussi une inégalité de Bernstein. En empruntant une technique de recherche itérative de point fixe aux analyses de [43] et les inégalités exponentielles décrites dans [7, 20], Bartlett et al. [8] ont montré que l'on peut estimer avec une forte probabilité l'excès de risque dans les problèmes de classification.

L'idée d'utiliser les moyennes conditionnelles de Rademacher pour calibrer des pénalités en sélection de modèle dispose déjà d'une belle descendance. Toutefois, la fin de l'histoire n'est pas connue.

Estimation d'ordre et test d'hypothèses composées

Estimation d'ordre.

L'estimation d'ordre relève aussi en partie des problèmes de sélection de modèles. Mais la perspective générale est celle du test d'hypothèses composées. Je suis venu à m'intéresser à ce problème en travaillant sur de longues séries chronologiques de transmissions de paquets sur Internet [?]. Cela m'a amené aux modèles de Markov cachés (hmm). Ces modèles, utilisés massivement en traitement de la parole, en théorie de la communication et en génomique posent des problèmes d'inférence statistique considérables.

Un cas d'école: les chaines de Markov cachées.

Rappelons qu'un modèle de Markov caché est défini par un espace d'état caché X à k0 éléments, une chaîne de Markov de transition A sur X, un alphabet d'observation Y à r éléments, et une matrice d'émission B qui pour chaque état caché, définit une loi d'émission sur Y. Une chaîne de Markov cachée est donc définie par k(k + r - 2) paramètres. Traditionnellement, la paire A,B est notée θ. Si l'état caché initial est x0, la probabilité de la suite (xi,yi)1≤in est donnée par

Pθ{x1n,y1n}:=∏i=1n(A(xi - 1;xi)B(xi;yi))

et la probabilité de la suite (yi)1≤in est donnée par

Pθ{y1n}:=∑x1,…,xni=1n(A(xi - 1;xi)B(xi;yi)) .

Si un processus (Yn)nN est engendré par une chaîne de Markov cachée, l'ordre de (Yn) est la taille minimale k0 de l'espace d'états cachés d'une chaîne de Markov cachée susceptible d'engendrer (Yn)n. Le problème d'identification de l'ordre consiste à estimer k0 à partir d'une observation partielle y1n:=y1,…,yn. L'ensemble des modèles de Markov cachés d'ordre inférieur ou égal à k0 est noté Θk0. Bien sûr Θk0⊂Θk0 + 1, et si l'ensemble des paramètres de Θk0 + 1 est muni de la mesure de Lebesgue en dimension (k0 + 1)(k0 + r - 1), le sous-ensemble des paramètres de Θk0 est de mesure nulle.

Pourquoi estimer l'ordre ?

Si θ0 est d'ordre k0 et engendre (Yn)n, et si k0 est connue à l'avance, l'estimation de θ0 au maximum de vraisemblance est consistante et asymptotiquement normale. Mais le calcul de ce maximum de vraisemblance est une source de grandes difficultés calculatoires ; en pratique, on se contente du résultat de l'algorithme em (qui ne présente pas de garanties particulières).

Par ailleurs, si l'ordre k0 n'est pas connu a priori, les paramètres θ0 ne sont plus identifiables, et même si ℓn(θ):=log Pθ{y1n}, l'ordre de grandeur de

supθ∈Θkn(θ) - ℓn0)

n'est pas connu précisément mais seulement majoré par des arguments de codage universel. On sort donc du cadre formulé par Wald et Wilks où la différence entre maxima de vraisemblance calculés dans des modèles emboités est tendue et suit asymptotiquement une loi du χ2. La détermination de l'ordre d'une chaîne de Markov cachée est un préalable (souvent négligé) à l'estimation des paramêtres.

Le problème de l'estimation de l'ordre d'une hmm se trouve en fait à la croisée de trois problématiques:

  • La sélection de modèles et son cortège habituel de questions : minimaxité, regret, oracles, adaptivité.
  • La théorie des tests, plus spécialement des tests d'hypothèses composées.
  • L'utilisation des techniques de codage universel en statistique. L'estimation de l'ordre des hmm constitue une pierre de touche pour des techniques comme le bic ( Bayesian Information Criterion ) ou le mdl ( Minimum Description Length principle ) qui peuvent aussi être comprises comme des méthodes de maximum de vraisemblance pénalisée.

Dans [41], une technique fortement consistante d'estimation de l'ordre d'une hmm est proposée : code-based-identification. Inspirée directement des techniques de codage universel, cette technique peut aussi être conçue comme une méthode de maximum de vraisemblance pénalisée. L'estimateur

(k)^:=argminkinfθ∈Θk - ℓn(θ) + pen(n,k) .

coïnciderait avec l'estimateur mdl si pen(n,k) ne dépendait pas de n. En 1994, Liu et Narayan ont montré que sous des conditions restrictives, il existe des estimateurs (k)^ de l'ordre possédant un exposant de sous-estimation (un exposant d'erreur)

limn - frac (1, n)log Pθ0{(k)^<k0}

non trivial (positif, dépendant de θ0). L'identification de l'exposant d'erreur optimal et son accessibilité étaient restés des problèmes ouverts en dépit de succès obtenus sur des cas particuliers [40].

Dans [33], nous avons montré d'abord qu'une pénalisation moins conservatrice que celle envisagée dans [41] préservait la forte consistance de l'estimateur de l'ordre. Et surtout, en utilisant des arguments de grandes déviations au niveau des processus de vraisemblance, nous avons identifié les exposants de sous-estimation optimaux et montré qu'ils étaient atteints par les techniques de maximum de vraisemblance pénalisée ou par les identificateurs issus du codage universel. Nous avons par ailleurs vérifié la trivialité des exposants de sur-estimation. Ce travail répond donc à une série de questions soulevées dans [71, 48] et va au-delà des résultats récents de [40] . Il trouvera un prolongement naturel dans l'étude de l'estimation et du test de l'ordre dans les modèles auto-régressifs, voire arma qui jouent un rôle extrêmement important en économétrie, et en statistiques.

Théorie de l'information

Le codage prioritaire et la théorie de l'information multi-utilisateurs.

A la suite d'un cours de dea, donné en 1995 - 1996, j'ai commencé à m'intéresser aux questions de communications. A cette époque M. Luby et ses collaborateurs (icsi Berkeley)étudiaient la transmission de flots multimédia organisés de manière hiérachique sur Internet, dont le protocole de niveaux iii, ip, n'assure pas une transmission fiable des paquets, et dont le protocole de transport fiable le plus important, tcp, ne fait qu'agraver la gigue de délais. Luby et al. ont retrouvé et adapté à la situation la notion classique de codage à protections inégales [1]. Ils ont proposé un schéma de mise en paquets de flots organisés hierarchiquement, et proposé une inégalité caractérisant les limites de schéma. En utilisant les inégalités de Han (mises à contribution dans [19] pour montrer que les entropies combinatoires sont concentrées), Noga Alon et moi-même avions rendu plus lisible la preuve de cette inégalité [1]. Cet éclairage ne changeait rien à la nature du résultat: cela restait un résultat d'informaticien sans interprétation du point de vue de la théorie de l'Information.

Du point de vue de cette dernière, la transmission d'informations hiérarchisées (par exemple des trames mpeg) sur des réseaux susceptibles de perdre des paquets, s'inscrit dans la problématique classique de la diffusion avec ensemble de messages dégradé [25].

Si on a affaire à des canaux sans mémoire, on peut facilement déterminer la région des débits accessibles et réinterpréter l'inégalité pet proposée dans [1]. On constate alors que sur des canaux à pertes, le débit/temps partagé est indépassable, du point de vue des débits accessibles. Une analyse plus fine, s'appuyant sur les exposants d'erreur (Random Coding exponents, Sphere Packing Exponents) montre que le schéma de multiplexage proposé dans[1] n'est pas optimal. Un réglage fin des débits alloués à chaque niveau d'information montre cependant l'optimalité du multiplexage par juxtaposition et entrelacement sur des canaux à pertes [21]. }

La théorie du spectre informationnel de Han et Verdu, application au canal de diffusion.

Dans [21], K. Salamatian et moi-même avons non seulement analysé la transmission prioritaire sur le canal de diffusion à message dégradé sans mémoire mais aussi cherché à comprendre le canal de diffusion à mémoire. Pour se faire nous nous sommes appuyé sur la théorie du spectre d'information proposée par Verdu et Han [67]. Cette approche permet de définir le débit d'une source et la capacitéd'un canal sous des hypothèses minimales. Elles s'étend aux canaux multi-utilisateurs (Te-Sun Han l'a appliqué au canal à accès multiples en 1998). Dans ce cadre, nous avons montré que les codes superposés proposés par Cover il y a 30 ans épuisent bien la région des débits accessibles sur ces canaux.

Exposants d'erreurs pour les canaux à pertes.

Les études empiriques sur les pertes de l'internet montrent que celles-ci sont corrélées. Pour comprendre les propriétés informationnelles d'une connexion udp, il faut comprendre les canaux à pertes à mémoire. Si on considère des canaux à pertes dépendants, sous une une contrainte raisonnable d'ergodicité et de stationnarité, on peut alors observer [17]:

i) La capacité d'un canal à pertes dépendant est la moyenne stationnaire des capacités associées aux différents états du canal.

ii) Dans le cas de canaux à mélange rapide (Markoviens et autres), la probabilité de pertes irréparables décrot toujours exponentiellement rapidement avec la longueur des blocs d'encodage, mais la vitesse de décroissance dépend de la vitesse de mélange du canal [?].

Les canaux à pertes Markoviens admettent une caractérisation à un symbole (single letter characterization): on peut caractériser la limite du logarithme de la probabilité d'echec de bons codes de longueurs croissantes comme la solution d'un problème d'optimisation. C'est un point où théorie de l'Information et théorie des grandes déviations se rejoignent. En poussant l'étude analytique jusqu'à l'étude des grandes déviations raffinées des fonctionnelles additives des chaînes de Markov cachées, nous avons même pu constater que prédictions des modèles de Markov cachés sont au moins qualitativement compatibles avec des données collectées entre 1998 et 1999 sur l'Internet.

Inégalités stochastiques

Pour comprendre l'intérêt des inégalités stochastiques lorsqu'on travaille dans le domaine des statistiques ou de l'informatique, envisageons le problème du routage aléatoire dans le cube (posé, il y vingt ans par Brebner et Valiant). Sur un hypercube de dimension n, on associe à chaque sommet un autre sommet tiré uniformément au hasard. Pour chaque paire de sommets construite de cette façon, on choisit un chemin de longueur minimale. Les chemins sont susceptibles de se croiser, et un excès de croisements en un point conduit à une congestion. On souhaite contrôler le nombre maximal de chemins qui passent par un sommet arbitraire. Il s'agit d'une variable aléatoire, fonction assez compliquée d”un grand nombre 2n de variables aléatoires indépendantes (le choix des 2n chemins). Comment l'étudier ? Une méthode éprouvée consiste à analyser séparemment l'espérance de cette congestion maximale et les fluctuations autour de cette espérance.

L'espérance se contrôle le plus souvent à l'aide d'arguments ad hoc. Ici, il s'agit du maximum d'un grand nombre de variables binomiales au comportement presque Poissonien. En Statistiques, on invoque des techniques de chaînage pour traiter des situations comparables. En revanche, les fluctuations autour de l'espérance peuvent être traitées par des approches assez systématiques qui relèvent de ce que l'on nomme aujourd'hui la théorie de la concentration de la mesure.

Le phénomène de concentration de la mesure dans les espaces produits peut se caricaturer ainsi : une variable aléatoire Z fonction de nombreuses variables aléatoires indépendantes X1n:=X1,…,Xn, c'est-à-dire Z=f(X1n) qui ne dépend pas trop de chacune de ces arguments est presque constante. La notion de concentration de la mesure (dans les espaces produits) s'est imposée depuis 1975 à partir d'horizons très divers:

  1. Théorie de l'information, tout particulièrement Théorie de l'Information \" multi-utilisateurs\" (voir [ 25 ]),
  2. Analyse fonctionnelle (voir [ 47 , 46 ]),
  3. Théorie des Grandes Déviations (voir [ 28 ]).

Si ces spécialités relèvent souvent des Mathématiques les plus austères, l'intérêt pour le phénomène de concentration de la mesure, provient largement des disciplines appliquées.

L'approche du phénomène de concentration par la théorie des martingales (\" méthode des différences bornées\"), est devenue, durant la dernière décennie, un outil normal pour l'informatique théorique. Ceci se comprend bien si on prend les inégalités de concentration comme des prolongements des inégalités exponentielles classiques (Hoeffding, Bernstein, Bennett, Chernoff). On pourra consulter à ce sujet la monographie de M. Steele [58] et surtout le cours de C. McDiarmid à l'Ecole de Montpellier [35] et constater les citations nombreuses dont ce cours est l'objet dans des conférences en Informatique (soda,stoc,focs,colt par exemple) pour se convaincre de la pertinence du phénomène de concentration de la mesure lorsqu'on s'intéresse aux algorithmes, aux statistiques, à la théorie de l'information.

En résumé, une bonne inégalité de concentration se présente dans les cas les plus favorables comme une version de l'inégalité de Bernstein pour les sommes de variables bornées.

P{Z - E[Z]>t}≤exp( - frac (t2, 2(v + t))) ,

v est un majorant raisonnable de la variance de Z. On vise à traiter des fonctions compliquées de variables indépendantes (ou faiblement dépendantes [50]). L'un des traits qui distinguent les inégalités de concentration des résultats qui forment le coeur des probabilités classiques, c'est justement qu'elles ne sont pas asymptotiques et qu'elles disent des choses non-triviales sur des événements de très faible probabilité. Ce trait est crucial dans nombre d'applications.

Quelques approches.

La dérivation d'inégalités de concentration a suscité de nombreux travaux ces vingt-cinq dernières années. Les avancées les plus spectaculaires sont dûes à M. Talagrand (voir [60, 62, 61]). Les méthodes développées par Talagrand, qui puisent leur source en Géométrie et en Analyse fonctionnelle (voir par exemple [55]) sont élémentaires mais on ne les comprend véritablement qu'au prix d'une familiarité coûteuse avec la géométrie des espaces de Banach.

La voie de la facilité consiste à utiliser les techniques de martingales. Les variables Z qui nous intéressent peuvent toujours se représenter comme des sommes d'accroissements de martingales (c'est le plongement de Doob), si ces incréments sont contrôlés, alors les fluctuations de Z sont intimement liées au comportement de la \" variation quadratique prévisible\" de la martingale. Combinée avec une bonne dose d'astuce, cette approche a fait des merveilles en combinatoire probabiliste [35, 10, 59, 58]. L'approche par les martingales est en principe sans faille. Cependant, il faut bien constater que son potentiel est difficile à exploiter, et il n'est sans doute pas fortuit que les inégalités les plus puissantes (celles qui portent sur la sur-martingale exponentielle et qui sont connues depuis trente ans [26]) n'aient été redécouvertes et utilisées que très récemment [24, 68].

Lorsque M. Talagrand a donné un cours sur la concentration de la mesure durant l'hiver 1996-1997, il a présenté avec beaucoup de chaleur deux approches concurrentes à sa propre démarche : les méthodes de transport proposées par K. Marton [50] et la \" méthode entropique\" proposée par M. Ledoux [46]. Cette dernière est extrêmement modulaire. Elle trouve son origine dans la construction d'inégalités de Sobolev logarithmiques dans les années soixante-dix (on notera que ces inégalités ont joué un rôle critique dans l'introduction de l'analyse harmonique en théorie de la complexité [39]). D'emblée cette méthode s'est révélée prometteuse: elle a permis de construire des preuves simples de résultats très difficiles de Talagrand sur les suprema de processus empiriques (voir les travaux de M. Ledoux, P. Massart, E. Rio et O. Bousquet et en particulier [51]). Ces travaux ont abouti à une version optimale de l'inégalité de Bennett pour les suprema de processus empiriques.

Efron-Stein et au delà

Mais pour bien comprendre (a posteriori) le sens de la démarche suivie dans [19, 20, 11], il est bon de revenir à un résultat très ancien, fort simple et extrêmement utile: l'inégalité d'Efron-Stein.

Définissons une nouvelle fonctionnelle de X1n:

V + :=∑i=1nE[(Z - Z'i)2 + X1n] ,

Z'i est obtenu en évaluant la fonctionnelle Z sur X1,…,Xi - 1,X'i,Xi + 1,…,Xn en tirant X'i indépendamment de X1n selon la loi de Xi. L'espérance conditionnelle est prise par rapport à la variable X'i. La quantité V + intervient naturellement dans la fameuse inégalité d'Efron-Stein, qui majore la variance de Z (typiquement une intégrale multiple) par une somme de quantités faciles à majorer:

Var(Z)≤E[V+] .

(3)

Il est plus que tentant de chercher à relier les propriétés d'intégrabilité de V + et celles de Z.

L'inégalité d'Efron-Stein est fortement liée à la méthode entropique de Ledoux [46]. En effet, dans le langage de l'Analyse, cette inégalité s'appelle la propriété de \" tensorisation de la variance\", elle constitue la première étape de la démonstration de l'inégalité de Poincaré (satisfaite par la probabilité invariante de certaines chaînes de Markov mélangeantes).

L'estimée de Efron-Stein (V + ) joue pour nous le rôle de la variation quadratique dans les approches fondées sur les martingales. On peut rétrospectivement décrire notre travail comme une tentative (réussie) d'étendre l'inégalité d'Efron-Stein aux moments d'ordre supérieurs et aux moments exponentiels.

Pour mener à bien cette extension, il faut prendre l'inégalité d'Efron-Stein, non pas comme une fin, mais comme un moyen, considérer la variance comme une fonctionnelle (convexe) définie sur l'ensemble des variables aléatoires, et se demander quelles sont les fonctionnelles qui se \" tensorisent\". La première étape de la méthode entropique consiste justement à vérifier que l'entropie relative (information de Kullback) se tensorise facilement.

Latala et Olesckiewicz [44], nous-mêmes [11] et Chafai [23] ont caractérisé les fonctionnelles qui jouissent de la propriété de tensorisation qui prolonge naturellement l'inégalité d'Efron-Stein. Cette caractérisation conduit à développer des inégalités fonctionnelles qui interpolent entre les inégalités d'Efron-Stein et les inégalités de Sobolev logarithmiques modifiées introduites par Bobkov et Ledoux [46].

En jouant, sur la notion de gradient discret, nous avons obtenu dans [20] (entre autres) l'inégalité suivante:

log E[eλ(E-E[Z])]≤frac (λθ, (1-λθ))log E[eλV+] pour λ,θ≥0 ,

(4)

qui peut être considérée comme une version exponentielle de l'inégalité d'Efron-Stein (cf [20]) Via l'inégalité de Markov, cette inégalité permet d'obtenir des majorations souvent fines des probabilités de queue de Z.

En dépit de son élégance, l'inégalité (4) trouve cependant ses limites. Il en va d'ailleurs de même de toutes les inégalités exponentielles : celles-ci n'ont pas lieu d'être lorsqu'on somme des variables qui ne sont pas exponentiellement intégrables ! On est donc assez naturellement amené à se demander comment croissent les moments d'une fonctionnelle Z, susceptibles de dépendre parfois violemment de certains de ses arguments (pensons par exemple au nombre de cliques de tailles 5 induites dans un graphe aléatoire). Il s'agit de chercher des généralisations des inégalités classiques de Marcinkiewicz et Burkholder-Davis-Gundy (cf [27]).

En revisitant et en étendant la méthode entropique, dans [11], nous sommes parvenus (entre autres) à l'inégalité suivante:

‖(Z-E[Z])+q≤sqrt (3q‖V+q/2) ,

(5)

pour q≥2. Cette inégalité constitue une généralisation presque idéale de l'inégalité de Marcinkiewicz et l'analogue au niveau des moments de l'Inégalité (4).

Applications

L'intérêt des Inégalités (4) et (5) n'est pas pûrement mathématique. Du point de vue de l'utilisateur, qui peut les prendre comme des boîtes noires, l'estimée d'Efron-Stein, c'est-à-dire la quantité V + s'avère bien plus intelligible que la variation quadratique qui apparaît dans les approches fondées sur la théorie des martingales. Ceci permet d'aborder de nouvelles applications notamment dans le domaine de l'apprentissage artificiel.

Gábor Lugosi, Pascal Massart et moi-même [19, 20] avons montré que l'approche de la concentration par les méthodes entropiques permet d'aller bien au delà des suprema des processus empiriques. Dans [20], nous montrons notamment que tous les résultats de concentration obtenus à partir du \" contrôle par la distance convexe \" [60, 62, 53, 46] peuvent être obtenus à partir de l'approche par les inégalités de Sobolev logarithmiques.

Mais les résultats présentés dans [19, 20] permettent surtout de montrer que de nouvelles fonctionnelles sont fortement concentrées autour de leur moyenne comme des variables Poissoniennes:

  1. les entropies combinatoires (dont l'entropie de Vapnik-Chervonenkis, où le logarithme du nombre de sous-suites croissantes dans une permutation aléatoire),
  2. les moyennes conditionnelles de Rademacher. Elles jouent un rôle important en théorie des probabilités sur les espaces de Banach et en sélection de modèles [ 46 ]. Le fait que les déviations par le haut fussent très peu probables, était traditionnellement déduit à partir du \" contrôle par q points\" de M. Talagrand [ 60 , 62 , 61 ]. Dans [ 7 ], nous avons montré que les moyennes de Rademacher satisfont les conditions décrites dans [ 19 ] et qu'elles sont donc fortement concentrées autour de leur moyenne. C'est à la fois une amélioration et une simplification des résultats antérieurs ( cf [ 65 ]). Cette avancée a constitué une percée dans le domaine de la sélection de modèles en théorie de l'apprentissage.

L'inégalité (5) permet de retrouver sans peine les inégalités de moments pour les sommes de variables aléatoires (Rosenthal, Pinelis, Latala, Hoffmann-Jorgensen) mais aussi de traiter de manière très satisfaisante les problèmes de comptage dans les graphes aléatoires décrits dans [38],[37, 68], les moments centrés des chaos de Rademacher d'ordre supérieur, ou encore les moyennes conditionnelles de Rademacher des processus empiriques indexés par des classes de fonctions dont l'enveloppe n'est pas uniformément bornée.

Structures aléatoires

Trois types de structures aléatoires m'ont intéressé

  • les problèmes d'allocations aléatoires (boules et urnes),
  • la connectivité dans les graphes aléatoires,
  • l'analyse probabiliste des problèmes d'optimisation.

A propos des deux premières classes de structures, j'ai recherché des théorèmes limites, (théorèmes centraux limites et principes de grandes déviations). Dans l'analyse des problèmes d'optimisation, j'ai d'une part travaillé à l'obtention de théorèmes limites (lorsque cela était possible) et d'autre part recherché de simples lois des grands nombres et tenté de vérifier l'acuité de certaines inégalités de concentration.

Allocations aléatoires

Mon travail sur les allocations aléatoires se situe dans la perspective exposée dans le livre de Kolchin, Sevastyanov et Chistyakov (Random allocations, 1975). Mais dans ce livre, l'approche est résolument combinatoire et les auteurs traitent de processus à valeur dans R, alors que je m'intéresse à des processus à valeur dans des espaces de mesures sur N. Aussi, j'ai eu recours à des méthodes probabilistes.

Le problème des allocations aléatoires est un des problèmes de base des probabilités discrètes et de l'analyse en moyenne des algorithmes. Dans ces problèmes on jette au hasard k boules dans n urnes et on s'intéresse aux remplissages ou scores. Lorsqu'on fait tendre n et k vers l'infini, tout en imposant que t=k/n reste constant, on se place dans le domaine central. Nous nous sommes intéressés à la mesure d'occupation empirique. Notons ω une allocation aléatoire c'est-à-dire une application de {1…k} dans {1…n}. Xnk(ω,i) désigne la proportion d'urnes qui contiennent i boules, et la mesure d'occupation empirique est définie par:

Xnk(ω):=∑iXnk(ω,i) δi .

Il s'agit d'une variable aléatoire à valeur dans un espace infini-dimensionnel (ℓ1(N)). On peut vérifier facilement, c'est un exercice de \" propagation du chaos\", que Xnk converge en probabilité vers la loi de Poisson de paramètre t notée pt, c'est une des raisons pour lesquelles les problèmes d'allocation aléatoires sont importants en approximation de Poisson. On peut se demander s'il est vraiment utile de s'encombrer d'un objet pareil. Pourtant comprendre les fluctuations de cet objet, permet par le principe de l'image continue (pour les tlc) ou le principe de contraction (grandes déviations) de résoudre des problèmes qui autrement se solderaient en volumineux calculs [15].

Dans [4], nous avions montré que

sqrt (n)(Xnt n - pt)

converge en loi vers une diffusion à valeur dans ℓ1(N). Cette diffusion est en fait un mouvement Brownien (dans ℓ1(N)) ayant subi un changement de temps déterministe et une transformation linéaire. Ce résultat s'obtient sans grands calculs en s'appuyant sur une structure de martingale et sur des arguments assez élémentaires de concentration dans les espaces produits. Ce théorème central limite fonctionnel permet de répondre complètement aux questions laissées en suspens dans [15]. Par un argument de couplage, il permet aussi de caractériser l'évolution de la disribution des degrés des graphes aléatoires creux dans le modèle de Erdös-Rényi.

Dans [14], nous avons caractérisé les grandes déviations de cette mesure d'occupation empirique (des résultats complémentaires sont décrits dans [31]). L'identification de la fonction de taux du principe de grandes déviations passe par un argument de dualité, la partie délicate, c'est-à-dire la borne inférieure, repose sur la construction d'une famille suffisamment riche de changements de mesures simples. Ce travail permet d'obtenir une forme de théorème de Sanov (Principe de grande déviation pour une mesure empirique), dans un contexte qui n'est pas celui des suites de variables aléatoires indépendantes ni celui des chaînes de Markov.

Graphes aléatoires

Dans le modèle G(n,p) des graphes aléatoires, un graphe non orienté sur n sommets est construit en tirant à pile ou face avec une probabilité de succès p, l'existence d'une arête pour chacune des (
n
2
) paires de sommets. Lorsqu'on choisit p=c/n en fixant c, et lorsqu'on fait tendre n vers l'infini, le résultat classique de Erdös et Rényi nous indique qu'avec une très forte probabilité, si c<1, le graphe résultat ne contient que des composantes connexes de taille inférieure à log n, alors que si c>1, le graphe contient une composante connexe géante de taille ≈n g(c) où g(c) est l'unique solution positive de l'équation en t: 1 - t=e - c t. La forme de la transition de phase a fait l'objet d'études nombreuses (voir [2, 56] et références).

Outre sa concision, sa richesse, le modèle G(n,p) intéresse la communauté scientifique en général, parce qu'il s'agit du modèle standard de la coagulation multiplicative [3]: dans cette perspective qui provient de la chimie physique, on étudie le comportement d'un système de particules en interaction qui s'agglutinent lors des chocs. La composante géante correspond à ce que les chimistes appellent le gel. Les fluctuations de la taille de la composante géante ont en fait déjà été étudiées (Stepanov, 1970, Pittel 1990), on sait qu'elles sont asymptotiquement Gaussiennes. Les preuves que nous connaissons sont soit combinatoires (Stepanov), soit indirectes (Pittel), elles utilisent pleinement l'hypothèse que les sommets sont échangeables. Elles ne s'étendent apparemment pas à des situations comme celles de graphes aléatoires à distribution de degrés prescrite. De plus ces méthodes ne donnent pas de vitesse de convergence pour le théorème central limite.

L'analyse des fluctuations de la taille de la composante géante présentée dans [5] étudie le comportement de la file des sommets à explorer durant un parcours de graphe aléatoire, c'est une analyse d'algorithme. Par un argument de couplage, l'analyse des fluctuations de la taille de la composante géante se réduit à l'analyse des temps de passage d'un processus assez facile à caractériser (il est très proche d'une martingale, et donc à la limite se comporte comme un mouvement Brownien ayant subi un changement de temps). Cette approche directe permet, elle, d'établir un théorème central limite, avec une borne supérieure sans doute non optimale pour la vitesse de convergence.

Cette manière de procéder, qui est semble-t-il assez naturelle dans l'analyse des réseaux de files d'attente, est originale dans le domaine des graphes aléatoires (quoique proche de celle utilisée dans [2]). Comme les approches probabilistes pures, elle est robuste et peut s'appliquer à des variantes du modèle d'Erdös-Rényi comme les graphes aléatoires à distribution de degrés prescrite qui font actuellement l'objet d'une attention soutenue de la part des gens qui étudient les \" Graphes du WEB\". Dans ces modèles on s'intéresse aux graphes aléatoires conditionellement à leur distribution de degrés. Ainsi, le modèle G(n,c/n) correspond approximativement à la distribution de Poisson de paramètre c). Molloy et Reed [54] ont déjà exhibé l'équivalent des théorèmes de Erdös et Rényi (lois des grands nombres). Ils n'abordent pas les fluctuations de la taille de la composante géante lorsqu'elle existe.

L'approche suivie dans [5] s'adapte bien aux graphes aléatoires à distribution de degrés donnée. J'ai montré avec cette technique que la normalité de la taille de la composante géante est une propriété robuste des graphes aléatoires puisqu'elle subsiste dans le modèle de Molloy et Reed.

Instances aléatoires des problèmes d'optimisation

Le troisième volet de mon travail sur les structures aléatoires porte sur l'analyse probabiliste de quelques problèmes d'optimisation. Cette étude s'inscrit dans la manière de [58]: on définit une famille de distributions sur les instances d'un problème d'optimisation combinatoire et on étudie le comportement de l'optimum. Les problèmes que j'ai étudiés en compagnie de W. Fernandez de la Vega concernent les empilements d'intervalles aléatoires ou de carrés aléatoires. En dépit de leur saveur géométrique, leur étude ne requiert aucune connaissance en Géométrie. En revanche cette analyse utilise les résultats obtenus en concentration de la mesure [19], la technique mise en oeuvre pour étudier la composante géante des graphes aléatoires [5] et la technique de changement de mesure utilisée en Grandes Déviations [14].

Le problème de l'empilement des intervalles aléatoires s'appelle aussi celui de la stabilité des graphes d'intervalles aléatoires: on tire au hasard n intervalles dans [0,1] en choisissant les extrémités uniformément indépendamment. On recherche alors une sous-famille maximale au sens de l'inclusion d'intervalles deux à deux disjoints. Il ne s'agit pas d'un problème difficile d'un point de vue calculatoire: il est bien résolu par une algorithme glouton. En 1990, Justicz, Scheinermann et Winkler ont montré que le taille maximale Ln d'un empilement satisfait une loi des grands nombres: lorsque n tend vers l'infini, Ln/sqrt (n) tend vers une constante. Cette démonstration s'appuie sur un plongement dans un processus de Poisson qui évoque le procédé mis en oeuvre par Hammersley pour caractériser la taille de la plus longue sous-suite croissante dans une permutation aléatoire (le problème d'Ulam). Comme la taille de la plus longue sous-suite croissante dans une permutation aléatoire, Ln est une \" fonction de configuration\", et d'après [62][19], elle est fortement concentrée autour de sa moyenne, les fluctuations typiques de Ln ne peuvent être d'un ordre supérieur à n1/4. Nous avons voulu comprendre les fluctuations de Ln: sont- elles comparables à celles de la plus longue sous-suite croissante, c'est-à-dire extrèmement complexes, les fluctuations typiques convergeants vers la distribution de Tracy-Widom et les grandes déviations suivant un principe avec des vitesses différentes pour les déviations vers le haut et les déviations vers le bas (Deuschel et Zeitouni, 1998)?

En analysant l'algorithme glouton, nous avons identifié Ln avec le temps de passage d'une marche aléatoire à un niveau choisi aléatoirement. Ceci permet de déduire un théorème central limite et un principe de grandes déviations classiques pour Ln [12]. Ces résultats sont obtenus avec un minimum de calculs, ils illustrent la pertinence de la méthode mise en oeuvre dans [5] pour l'étude des structures aléatoires.

Dans [13], nous avons étudié une variante de l'empilement des intervalles aléatoires: l'empilement de carrés aléatoires sur le tore unité bidimensionnel. Dans une famille de carrés (aléatoires), on recherche la taille Mn d'une famille de carrés deux-à-deux disjoints de cardinalité maximale. Le problème calculatoire correspondant est np-dur. Il n'est donc plus question d'analyser le comportement d'un algorithme simple. Pour raffiner des résultats récents de Winkler et al., et établir une loi des grands nombres, nous avons dû recourrir à l'un des outils de base de l'analyse probabiliste des problèmes d'optimisation combinatoire: les arguments de sous-additivité. Nous sommes très démunis face aux fluctuations de Mn, et dans l'incapacité d'exhiber un théorème central limite ou un principe de grandes déviations. Comme Mn est encore une fonction de configuration, on doit naturellement se demander si les inégalités de concentration [62][19] sont tendues comme pour les empilements d'intervalles aléatoires ou si elles ne parviennent pas à capturer une partie du phénomène comme dans le cas de la plus longue sous-suite croissante. Un changement de mesure inspiré par la preuve de la loi des grands nombres montre que les inégalités de concentration capturent correctement les grandes déviations de Mn.

Bibliographie

[1] A. Albanese, J. Bloemer, J. Edmonds, and M. Luby. Priority encoding transmission. IEEE Trans. Inform. Theory, 42:1737–1744, 1996.

[2] D. Aldous. Brownian excursions, critical random processes, and the multiplicative coalescent. Annals of Probability, 25:812–854, 1997.

[3] D. Aldous. Deterministic and stochastic models for coalescence (aggregation,coagulation): a review of the mean-field theory for probabilists. Bernoulli, 5:3–48, 1998.

[4] D. Barraez and S. Boucheron. Diffusion approximation for random allocations. Technical report, lri, 1998. \"http://www.lri.fr/oucheron/PUB/dara97.ps\".

[5] D. Barraez, S. Boucheron, and W. Fernandez de la Véga. On the fluctuations of the giant component. Combinatorics, Probability and Computing, 9:287–304, 2000.

[6] A. Barron, L. Birgé, and P. Massart. Risks bounds for model selection via penalization. Probab. Theory Relat. Fields, 113:301–415, 1999.

[7] P. Bartlett, S. Boucheron, and G. Lugosi. Model selection and error estimation. Machine Learning, 48:85–113, 2002.

[8] P. Bartlett, O. Bousquet, and S. Mendelson. Local rademacher compleities. In Proceedings of colt 2002, page xxx. Springer LNAI, 2002.

[9] P. Bickel and K. Doksum. Mathematical statistics. Holden-Day Inc., San Francisco, Calif., 1976.

[10] B. Bollobás. Random graphs. 2nd ed. Cambridge University Press, 2001.

[11] S. Boucheron, O. Bousquet, G. Lugosi, and P. Massart. Moment inequalities for functions of independent random variables. Annals of Probability, 33(2):514–560, 2005.

[12] S. Boucheron and W. Fernandez de la Véga. On the stability number of random interval graphs. Combinatorics, Probability and Computing, 10:385–396, 2001.

[13] S. Boucheron and W. Fernandez de la Véga. On a square packing problem. Combinatorics, Probability and Computing, 11:113–127, 2002.

[14] S. Boucheron, F. Gamboa, and C. Léonard. Bins and balls: large deviations of the empirical occupancy process. Annals of Applied Probability, 12:607–636, 2002.

[15] S. Boucheron and D. Gardy. An Urn Model from Learning Theory. Random Struct. & Algorithms, 10(1-2):43–69, 1997.

[16] S. Boucheron and E. Gassiat. Inference in Hidden Markov Models, chapter Order estimation. Springer-Verlag, 2005. edited by O. Cappe, E. Moulines and T. Rydden.

[17] S. Boucheron, C. Guenzel, and K. Salamatian. Coding exponents for some markov channels. In Actes du 17eme gretsi, pages 877–880, September 1999.

[18] S. Boucheron, C. Guenzel, and K. Salamatian. Loss patterns and loss resilient codes over the internet. In Proceedings of algotel 2000, pages 113–119. inria, 2000.

[19] S. Boucheron, G. Lugosi, and P. Massart. A sharp concentration inequality with applications. Random Struct. & Algorithms, 16:277–292, 2000.

[20] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities using the entropy method. Annals of Probability, 31:1583–1614, 2003.

[21] S. Boucheron and K. Salamatian. About priority encoding transmission. IEEE Trans. Inform. Theory, 48:687–705, 2000.

[22] O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris, 334(6):495–500, 2002.

[23] D. Chafai. Entropies, convexity, and functional inequalities. arXiv.math.PR0211103, 2003.

[24] I. Csiszár. Large-scale typicality of Markov sample paths and consistency of MDL order estimators. IEEE Trans. Inform. Theory, 48:1616–1628, 2002.

[25] I. Csiszár and J. Körner. Information Theory: Coding Theorems for Discrete Memoryless Channels. Academic Press, 1981.

[26] D. Dacunha-Castelle and M. Duflo. Probabilités et statistiques, volume 2. Masson, 1983.

[27] V. de la Pena and E. Giné. Decoupling. Springer, 1999.

[28] A. Dembo and O. Zeitouni. Large deviation techniques and applications. Springer, 1998.

[29] R. DeVore and G. Lorentz. Constructive approximation, volume 303 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1993.

[30] L. Devroye, L. Gyorfi, and G. Lugosi. A probabilistic theory of pattern recognition. Springer., 1996.

[31] P. Dupuis, C. Nuzman, and P. Whiting. Large deviation asymptotics for occupancy problems. Ann. Probab., 32(3B):2765–2818, 2004.

[32] B. Efron and C. Stein. The jackknife estimate of variance. Ann. Statist., 9(3):586–596, 1981.

[33] E. Gassiat and S. Boucheron. Optimal error exponents in hidden markov model order estimation. IEEE Trans. Inform. Theory, 49:864–880, 2003.

[34] E. Giné and J. Zinn. Some limit theorems for empirical processes. Ann. Probab., 12(4):929–998, 1984.

[35] M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors. Probabilistic methods for algorithmic discrete mathematics. Springer-Verlag, 1998.

[36] T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer Series in Statistics. Springer-Verlag, New York, 2001.

[37] S. Janson, T. uczack, and A. Ruciński. Random graphs. John Wiley, 2000.

[38] S. Janson and A. Ruciński. The infamous upper tail. Random Struct. & Algorithms, 20:317–342, 2002.

[39] J. Khan, G. Kalai, and N. Linial. The influence of variables on boolean functions. In Proceedings of focs, 1988.

[40] S. Khudanpur and P. Narayan. Order estimation for a special class of hidden markov sources and binary renewal processes. IEEE Trans. Inform. Theory, 48:1704–1713, 2002.

[41] J. Kieffer. Strongly consistent code-based identification and order estimation for constrained finite-state model classes. IEEE Trans. Inform. Theory, 39:893–902, 1993.

[42] V. Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Trans. Inform. Theory, 47:1902–1914, 2001.

[43] V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of functions learning. High Dimensional Probability, II:443 – 459, 2000.

[44] R. Latala and K. Oleszkiewicz. Between Sobolev and Poincaré. In V. Milman, editor, Geometric aspects of functional analysis. Proceedings of the Israel seminar (GAFA) 1996-2000. Berlin: Springer. Lect. Notes Math. 1745, pages 147–168, 2000.

[45] M. Ledoux. On Talagrand's deviation inequalities for product measures. ESAIM Probab. Statist., 1:63–87 (electronic), 1995/97.

[46] M. Ledoux. The concentration of measure phenomenon. AMS, 2001.

[47] M. Ledoux and M. Talagrand. Probability in Banach spaces. Springer, 1991.

[48] C. Liu and P. Narayan. Order estimation and sequential universal data compression of a hidden markov source by the method of mixtures. IEEE Trans. Inform. Theory, 40:1167–1180, 1994.

[49] E. Mammen and A. Tsybakov. Smooth discrimination analysis. Annals of Statistics, 27(6):1808–1829, 1999.

[50] K. Marton. Bounding d-distance by informational divergence: a method to prove measure concentration. Annals of Probability, 24:857–866, 1996.

[51] P. Massart. About the constants in talagrand's concentration inequality. Annals of Probability, 28:863–885, 2000.

[52] P. Massart. Some applications of concentration inequalities to statistics. Ann. Fac. Sc. Toulouse, IX(2):245–303, 2000.

[53] C. McDiarmid. [35], chapter Concentration. Springer-Verlag, 1998.

[54] M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence. Combin. Probab. & Computing, 7:295–305, 1998.

[55] G. Pisier. The Volume of Convex Bodies and Banach Space Geometry. Cambridge University Press, 1989.

[56] A. Pukhalskii. Stochastic processes in random graphs. Annals of Probability, to appear(.):., 2004.

[57] E. Rio. Inégalités de concentration pour les processus empiriques de classes de parties. Probab. Theory Related Fields, 119(2):163–175, 2001.

[58] J. Steele. Probability theory and combinatorial optimization. SIAM, 1977.

[59] W. Szpankowski. Average case analysis of algorithms on sequences. J. Wiley, 2001.

[60] M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publ. Math., Inst. Hautes Etud. Sci., 81:73–205, 1995.

[61] M. Talagrand. New concentration inequalities in product spaces. Inventiones Mathematicae, 126:505–563, 1996.

[62] M. Talagrand. A new look at independence. Annals of Probability, 24:1–34, 1996.

[63] A. Tsybakov. Optimal aggregation of classifiers in statistical learning. Technical Report 682, Paris vi, 2001.

[64] S. van de Geer. A new approach to least-squares estimation, with applications. Annals of Statistics, 15:587–602, 1987.

[65] A. van der Vaart and J. Wellner. Weak convergence and Empirical Processes. Springer-Verlag, 1996.

[66] V. Vapnik. The nature of statistical learning theory. Springer-Verlag, 1995.

[67] S. Verdu and T. Han. A general formula for channel capacity. IEEE Trans. Inform. Theory, 40:1147–1157, 1994.

[68] V. Vu and J. Kim. Concentration of multivariate polynomials and applications. Combinatorica, 20:417–434, 2000.

[69] Y. Yang. Minimax nonparametric classification. I. Rates of convergence. IEEE Trans. Inform. Theory, 45(7):2271–2284, 1999.

[70] Y. Yang. Minimax nonparametric classification. II. Model selection for adaptation. IEEE Trans. Inform. Theory, 45(7):2285–2292, 1999.

[71] J. Ziv and N. Merhav. Estimating the number of states of a finite-state source. IEEE Trans. Inform. Theory, 38:61–65, 1992.