Apprentissage en ligneOnline Learning — Regret · Exponential Weighting · Cours 11 (10/15)
Slides 7-online-learning (23 p.)
MLAPP §8.5.1 Online learning and regret minimization p.262
Lecture officielle : FML (Mohri et al.) ch. 8.2 — pas dans le dossier Textbooks
Tous les chapitres précédents reposaient sur une hypothèse silencieuse : les exemples sont tirés i.i.d. d'une loi fixe $P$, et on juge un modèle par son erreur de généralisation $L(f) = \E_P[\ell]$ (chapitre 4). Ce chapitre répond à une seule question : que peut-on encore garantir quand il n'y a plus de loi du tout — quand les données arrivent une par une, changent de comportement, ou sont même choisies par un adversaire qui connaît notre algorithme ? La réponse tient en trois idées : changer de mesure (le regret, qui compare à ce qu'on aurait pu faire), randomiser ses prédictions pour ne pas être prévisible, et pondérer des experts de façon exponentielle en leurs erreurs. Au début de chaque section, un encadré Où on en est fait le point.
Feuille de route
Les slides ont deux parties : une métrique (le regret) et un algorithme (exponential weighting). Entre les deux, un résultat négatif explique pourquoi l'algorithme doit être aléatoire. La chaîne complète, cliquable :
① Cadre · §1plus d'hypothèse i.i.d.les exemples arrivent un par un, éventuellement choisis par un adversaire
→
② Métrique · §2regret = ma perte − celle du meilleur expertobjectif : $\mathrm{Reg}_T = O(\sqrt T)$→
③ Obstacle · §3un apprenant déterministe a $\mathrm{Reg}_T\ge T/2$il faut randomiser→
④ Première idée · §4Weighted Majority : vote pondérébon nombre d'erreurs, mais déterministe→
⑤ Algorithme · §5tirer un expert $I_t\sim p_t$, poids $e^{-\eta L}$Randomized WM → Exponential Weighting→
⑥ Garantie · §6$\E[\mathrm{Reg}_T]\le\sqrt{T\ln|\mathcal H|}$regret moyen → 0, sans aucune hypothèse sur les données
Le raisonnement, maillon par maillon
- ①Le cadre change. Plus de loi fixe : la suite $(x_t,y_t)$ peut dériver, ou être fabriquée par un adversaire qui observe nos prédictions passées. L'erreur de généralisation $\E_P[\ell]$ n'a plus de sens (il n'y a pas de $P$). → Il faut une autre mesure de qualité.
- ②La bonne mesure. La perte cumulée seule ne suffit pas : si la suite est très difficile, tout le monde se trompe beaucoup. On se compare donc au meilleur expert a posteriori d'un ensemble fini $\mathcal H$ : c'est le regret. On veut qu'il croisse moins vite que $T$ (idéalement comme $\sqrt T$), pour que le regret par tour tende vers 0.
- ③L'obstacle. Si l'apprenant est déterministe, l'adversaire peut calculer sa prédiction et jouer l'inverse : perte $T$. Avec deux experts « toujours $-1$ » et « toujours $+1$ », l'un des deux a au plus $T/2$ erreurs. Regret $\ge T/2$ : linéaire, perdu. → Il faut que la prédiction soit imprévisible : la tirer au hasard.
- ④Une première idée : pondérer les experts. Weighted Majority fait voter les experts, chacun avec un poids, et multiplie par $\beta$ le poids de ceux qui se trompent. Son nombre d'erreurs est contrôlé par celui du meilleur expert, mais il reste déterministe (donc battu par l'adversaire) et limité à la classification.
- ⑤Randomiser, puis lisser. Au lieu de voter, on tire un expert avec probabilité proportionnelle à son poids. En écrivant la pénalité $(1-\eta)^{\ell}$, puis $e^{-\eta\ell}$, on obtient l'exponential weighting : valable pour toute perte dans $[0,1]$, et $p_t$ est une softmax des pertes cumulées.
- ⑥La garantie. Un argument de potentiel ($W_t = \sum_iw_t(i)$) et le lemme de Hoeffding donnent $\E[\mathrm{Reg}_T]\le\frac{\ln K}\eta+\frac{\eta T}8$, puis $\sqrt{T\ln K/2}$ avec le bon $\eta$ : aucune hypothèse sur les données, et seulement $\ln K$ pour $K$ experts.
À la fin du chapitre, tu dois savoir…
- écrire le protocole de l'apprentissage en ligne avec experts, et le comparer au cadre statistique ;
- définir perte cumulée, meilleur expert a posteriori, regret statique et dynamique, et expliquer pourquoi on vise $\mathrm{Reg}_T = O(\sqrt T)$ ;
- démontrer que tout apprenant déterministe a un regret $\ge T/2$, et expliquer pourquoi la randomisation (contre un adversaire non anticipant) contourne ce résultat ;
- dérouler Weighted Majority, Randomized Weighted Majority et Exponential Weighting sur un petit exemple ;
- démontrer la borne $\E[\mathrm{Reg}_T]\le\frac{\ln K}{\eta}+\frac{\eta T}{8}$ et en déduire le choix $\eta = \sqrt{8\ln K/T}$.
Notations du chapitre
Toutes les lettres utilisées dans la page (et dans les slides), au même endroit. Plusieurs lettres changent de sens d'une slide à l'autre : voir l'encadré qui suit le tableau.
| Symbole | Se lit / signifie | Nature | Où |
|---|---|---|---|
| Le protocole | |||
| $t,\ T$ | numéro du tour ; nombre total de tours (horizon, time horizon) | entiers | partout |
| $x_t,\ y_t$ | entrée et vraie étiquette du tour $t$ (révélée après la prédiction) | $\mathcal X$, $\mathcal Y$ | partout |
| $\hat y_t$ | prédiction de l'apprenant au tour $t$ | $\mathcal Y$ | partout |
| $\mathcal H = \{h_1,\dots,h_K\}$, $K = |\mathcal H|$ | ensemble fini d'experts (de prédicteurs fixés), et leur nombre | ensemble de fonctions | §2 → |
| $\hat y_{t,k} = \hat h_{t,k}(x_t)$ | prédiction de l'expert $k$ au tour $t$ (slide 3) | $\mathcal Y$ | §1 |
| $\ell(y,\hat y)$, $\ell_t(i)$ | perte, à valeurs dans $[0,1]$ ; abréviation $\ell_t(i) := \ell(y_t,h_i(x_t))$ = perte de l'expert $i$ au tour $t$ (hors slides) | réel $\in[0,1]$ | partout |
| Mesurer un apprenant (§2) | |||
| $L_{T,i} = \sum_{t=1}^T\ell_t(i)$ | perte cumulée de l'expert $i$ (hors slides) | réel $\ge0$ | §2, §6 |
| $L^\star = \min_iL_{T,i}$ | perte du meilleur expert a posteriori (best in hindsight) | réel $\ge0$ | §2, §6 |
| $\mathrm{Reg}_T$ | regret : perte cumulée de l'apprenant − $L^\star$ | réel | §2 → |
| $\mathrm{Reg}^{\text{static}}_T,\ \mathrm{Reg}^{\text{dynamic}}_T$ | regret contre un expert fixe ; contre une suite d'experts $(h_1,\dots,h_T)\in\mathcal H^T$ | réels | §2 |
| Algorithmes (§4–6) | |||
| $w_t(i)$ | poids de l'expert $i$ au début du tour $t$ ; $w_1(i) = 1$ | réel $>0$ | §4 → |
| $W_t = \sum_iw_t(i)$ | poids total (le potentiel des preuves) (hors slides) | réel $>0$ | §4, §6 |
| $p_t(i) = w_t(i)/W_t$ | probabilité de suivre l'expert $i$ au tour $t$ | $p_t\in$ simplexe | §5 → |
| $I_t\sim p_t$ | expert tiré au tour $t$ ; $\hat y_t = h_{I_t}(x_t)$ | indice aléatoire | §5 → |
| $\langle p_t,\ell_t\rangle$ | perte espérée de l'apprenant au tour $t$ : $\sum_ip_t(i)\ell_t(i)$ (hors slides) | réel $\in[0,1]$ | §6 |
| $\beta\in(0,1)$ | facteur de pénalité de Weighted Majority | réel | §4, §5 |
| $\eta>0$ | taux d'apprentissage : $\beta = 1-\eta$ (RWM), poids $e^{-\eta\ell}$ (EW) | réel | §5, §6 |
| $M_T,\ m^\star$ | nombre d'erreurs de Weighted Majority ; nombre d'erreurs du meilleur expert (hors slides) | entiers | §4 |
Pièges de notation (ils viennent des slides)
- $h$ a trois rôles : $h_t$ = le prédicteur que l'apprenant utilise au tour $t$ (slide 7) ; $h_i$ ou $h_k$ = l'expert numéro $i$ de $\mathcal H$ (slides 6, 16) ; $h_{-1}$, $h_{+1}$ = deux experts constants (slide 12), indexés par leur prédiction. L'indice dit lequel : temps, numéro d'expert, ou valeur prédite.
- Étiquettes : $\{-1,+1\}$ pour le résultat négatif (slide 11), $\{0,1\}$ pour Weighted Majority (slide 16).
- $\mathrm{Reg}_T$ est aléatoire pour un apprenant randomisé : la slide 22 borne son espérance, prise sur le hasard interne de l'apprenant (les tirages $I_t$), pas sur les données (il n'y a pas de loi sur les données).
- $\eta$ n'est plus un pas de gradient (chapitres 1–5) mais la « sensibilité » des poids aux erreurs. Et $\beta = 1-\eta$ (slide 19).
- Le meilleur expert est choisi a posteriori, après avoir vu les $T$ tours : il n'est pas connu pendant le jeu, sinon il suffirait de le suivre.
- $\ln$ est le logarithme népérien ; la borne de la slide 22 contient $\ln|\mathcal H|$.
- $L$ désignait l'erreur de généralisation au chapitre 4 et le nombre de couches au chapitre 5 ; ici $L_{T,i}$ et $L^\star$ sont des pertes cumulées.
Mode d'emploi des scènes
- ▶ Lecture fait avancer les tours ; « Pas +1 » avance d'un cran ; ↺ recommence (avec une autre séquence quand c'est pertinent).
- Les points à halo se déplacent à la souris. ◉ Affichage (en haut à droite) masque ou affiche les éléments de chaque figure.
- Les séquences sont générées par un générateur aléatoire à graine : « nouvelle séquence » en tire une autre.
1Pourquoi l'apprentissage en ligne ?
Où on en est
Acquis
Chapitres 1–5 : apprentissage statistique. Données i.i.d. d'une loi fixe $P$, objectif $L(f) = \E_P[\ell]$, garanties « en moyenne sur l'échantillon » (chapitre 4).
Il manque
Que faire quand la loi change (distribution shift), ou quand les données sont produites par quelqu'un qui réagit à nos prédictions (spam, fraude, marchés) ?
Cette partie
Le cadre en ligne : aucune hypothèse sur la suite, apprentissage tour par tour, et l'exemple des slides (prévisions météo de $K$ experts).
▶ Vidéosen anglais · s'ouvrent sur YouTube
Apprentissage statistique vs apprentissage en ligne (slide 2)
| Statistique (chapitres 1–5) | En ligne (ce chapitre) | |
|---|---|---|
| Loi | une loi $P$ fixe sur $\mathcal X\times\mathcal Y$ | aucune hypothèse de loi |
| Dépendance | exemples indépendants, identiquement distribués | suite arbitraire, ou adaptative (qui réagit à l'apprenant) |
| Déroulement | tout l'échantillon d'un coup, puis évaluation | un exemple par tour : prédire, puis recevoir la vérité |
| Objectif | erreur de généralisation $L(f)$ | regret (§2) |
Nouvelle question : sans hypothèse de loi, comment apprendre un modèle performant ?
Protocole avec conseils d'experts (slide 3)
Pour $t = 1,\dots,T$ :
- chaque expert observe $x_t$ et prédit $\hat y_{t,k} = \hat h_{t,k}(x_t)$, $k = 1,\dots,K$ ;
- l'apprenant reçoit les prédictions des experts $\hat y_{t,1},\dots,\hat y_{t,K}$ ;
- l'apprenant produit sa prédiction $\hat y_t$ à partir de $\hat y_{t,1},\dots,\hat y_{t,K}$ ;
- l'apprenant reçoit la vraie étiquette $y_t$ ;
- il subit la perte $\ell(y_t,\hat y_t)$ ;
- il met à jour ses paramètres.
Les objets en jeu
- expert
- prédicteur donnéUne source de prédictions qu'on ne contrôle pas : un site météo, un modèle déjà entraîné, une règle simple. L'apprenant n'apprend pas les experts, il apprend à qui faire confiance.
- $\hat y_t$
- décisionElle doit être produite avant de voir $y_t$ : c'est ce qui rend le problème difficile. Ensuite seulement, la perte est révélée.
- « full feedback »
- ce qu'on observeAprès chaque tour on voit $y_t$, donc la perte de tous les experts, pas seulement de celui qu'on a suivi (slide 23). Avec une information partielle, on parle de bandits ; on y reviendra en apprentissage par renforcement.
Dans la scène, quatre sites météo prédisent soleil ou pluie. L'apprenant donne un poids à chacun, tire un expert au hasard selon ces poids, puis met à jour les poids quand la vérité arrive. Au milieu de la séquence, le meilleur site change : c'est un distribution shift, et les poids doivent basculer.
Pourquoi ce cadre est utile
Les experts n'ont pas besoin d'être bons « en moyenne sous une loi » : ils peuvent être bons à certaines périodes et mauvais à d'autres. Les garanties de ce chapitre tiennent pour toute suite de données, même choisie pour nous nuire. C'est une garantie plus forte que celle du chapitre 4, en échange d'une ambition plus modeste : faire presque aussi bien que le meilleur expert, pas aussi bien que la meilleure fonction possible.
2Mesurer un apprenant : le regret
Où on en est
Acquis
Le protocole : prédire, puis voir la vérité, tour après tour, sans loi sur les données.
Il manque
Un critère pour dire qu'un apprenant est « bon », qui ait un sens même quand la suite est arbitraire.
Cette partie
Perte cumulée, meilleure perte cumulée, regret ; l'environnement adversarial ; l'objectif $\mathrm{Reg}_T = O(\sqrt T)$ ; regret statique vs dynamique.
Perte cumulée (slide 5) · meilleure perte cumulée (slide 6)
Si l'apprenant prédit $\hat y_t := h_t(x_t)$, sa perte cumulée est
$$\sum_{t=1}^T\ell(y_t,\hat y_t).$$
Pour un ensemble fini $\mathcal H = \{h_1,\dots,h_K\}$, la meilleure perte cumulée est celle du meilleur prédicteur a posteriori (in hindsight), après les $T$ tours :
$$\min_{h\in\mathcal H}\sum_{t=1}^T\ell\big(y_t,h(x_t)\big).$$
C'est la performance de référence (benchmark).
La perte cumulée suffit-elle sous distribution shift ? (slide 5)
Réponse
Non. La perte cumulée dépend surtout de la difficulté de la suite : si les étiquettes sont du bruit pur, tout apprenant fait environ $T/2$ erreurs, et ce n'est pas sa faute. Sans hypothèse de loi, on ne peut pas dire si « 300 erreurs » est bon ou mauvais. Il faut une référence calculée sur la même suite : la perte du meilleur expert a posteriori. Le regret mesure l'écart à cette référence, et il a un sens même si la suite change ou est adverse.
Regret (slide 7)
$$\mathrm{Reg}_T := \sum_{t=1}^T\ell\big(y_t,h_t(x_t)\big)-\min_{h\in\mathcal H}\sum_{t=1}^T\ell\big(y_t,h(x_t)\big).$$
Le regret mesure la qualité de l'apprenant par l'écart entre la perte de sa suite de prédicteurs $h_1,\dots,h_T$ et la meilleure performance de référence.
Les objets en jeu
- $h_t$
- choix de l'apprenantIl peut changer à chaque tour ; il dépend de tout ce que l'apprenant a vu avant le tour $t$.
- $\min_{h\in\mathcal H}$
- comparateurUn seul expert, le même pour les $T$ tours, choisi après coup en connaissant toute la suite. Il « triche » (il connaît l'avenir) mais il n'a pas le droit de changer d'avis.
- signe du regret
- réelIl peut être négatif : en changeant d'expert au bon moment, l'apprenant peut battre tout expert fixe. On veut surtout qu'il ne soit pas grand.
Environnement adversarial non anticipant (slide 8)
Un adversaire génère $(x_t,y_t)$ de façon arbitraire, en pouvant dépendre des prédictions passées de l'apprenant $\hat y_1,\dots,\hat y_{t-1}$. On l'appelle simplement « environnement adversarial ». Un environnement stochastique (i.i.d.) en est un cas particulier.
Le regret fait-il une hypothèse stochastique ? Et si un adversaire manipule $(x_t,y_t)$ ? (slide 7)
Réponse
Aucune hypothèse : la définition ne contient que la suite effectivement observée, pas de loi ni d'espérance sur les données. Si un adversaire rend la suite difficile, il la rend difficile aussi pour le comparateur : la perte du meilleur expert augmente avec celle de l'apprenant. Pour avoir un grand regret, l'adversaire doit faire échouer l'apprenant sans faire échouer tous les experts. Le §3 montre qu'il y arrive contre un apprenant déterministe, et le §6 qu'il n'y arrive pas contre l'exponential weighting.
Pourquoi les prédictions passées, et pas la prédiction courante ? (slide 8)
Réponse
Si l'adversaire voyait $\hat y_t$ avant de choisir $y_t$, il jouerait toujours $y_t\ne\hat y_t$ : l'apprenant se tromperait à chaque tour, même en tirant $\hat y_t$ à pile ou face, et aucun algorithme ne pourrait rien garantir (le §3 donne alors un regret $\ge T/2$ pour tout apprenant). L'adversaire non anticipant peut connaître l'algorithme et tout le passé, donc la distribution $p_t$ de la prochaine prédiction, mais pas le tirage. C'est le plus fort adversaire contre lequel on peut encore gagner.
Objectif : minimiser le regret (slide 9)
Trouver un apprenant qui minimise $\mathrm{Reg}_T$ dans un environnement adversarial, pour tout $\mathcal H$ fini et toute suite de données. Plus précisément : un apprenant avec $\mathrm{Reg}_T = O(\sqrt T)$.
Pourquoi un regret sous-linéaire est le bon critère (et pourquoi $\sqrt T$) — question de la slide 9
① Sous-linéaire ⇔ regret moyen → 0. « $\mathrm{Reg}_T = o(T)$ » veut dire par définition $\frac{\mathrm{Reg}_T}T\to0$. Or $\frac{\mathrm{Reg}_T}T$ est l'écart par tour entre la perte moyenne de l'apprenant et celle du meilleur expert. Sous-linéaire = « à la longue, on fait en moyenne aussi bien que le meilleur expert, sans savoir à l'avance lequel c'est ».
② Avec $\mathrm{Reg}_T\le c\sqrt T$ : $\frac{\mathrm{Reg}_T}T\le\frac{c}{\sqrt T}\to0$, avec une vitesse explicite. Un regret linéaire $\mathrm{Reg}_T\ge aT$ ($a>0$), au contraire, veut dire qu'on perd $a$ par tour pour toujours : on n'apprend pas.
③ Pourquoi on ne peut pas espérer mieux que $\sqrt T$ hors slides. Prenons deux experts dont les pertes 0-1 sont des pile ou face indépendants et équilibrés, à chaque tour. Quel que soit l'apprenant, sa perte espérée au tour $t$ vaut $\frac12$ (la perte de chaque expert est indépendante du passé), donc sa perte cumulée espérée vaut $\frac T2$. Mais $\min(L_1,L_2) = \frac{L_1+L_2}2-\frac{|L_1-L_2|}2$, et $L_1-L_2$ est une somme de $T$ variables indépendantes centrées de variance $\frac12$, donc de l'ordre de $\sqrt{T/2}$ (théorème central limite : $\E|L_1-L_2|\approx\sqrt{T/\pi}$). Donc $\E[\min_iL_{T,i}]\approx\frac T2-\frac12\sqrt{T/\pi}$ et $\E[\mathrm{Reg}_T]\approx\frac12\sqrt{T/\pi}$ : tout apprenant a un regret d'ordre $\sqrt T$ sur cet exemple, même aléatoire et pas adverse.
Intuition : le meilleur expert a posteriori bénéficie de la chance (ses fluctuations sont d'ordre $\sqrt T$), et l'apprenant ne peut pas prévoir la chance. $\sqrt T$ est donc la bonne échelle, et le §6 montre qu'on l'atteint.
∎
Regret statique et regret dynamique (slide 10)
$$\mathrm{Reg}^{\text{static}}_T := \sum_{t=1}^T\ell(y_t,\hat y_t)-\min_{h\in\mathcal H}\sum_{t=1}^T\ell\big(y_t,h(x_t)\big),\qquad\mathrm{Reg}^{\text{dynamic}}_T := \sum_{t=1}^T\ell(y_t,\hat y_t)-\min_{(h_1,\dots,h_T)\in\mathcal H^T}\sum_{t=1}^T\ell\big(y_t,h_t(x_t)\big).$$
Statique : le comparateur est un expert fixe pour tous les tours. Dynamique : il peut changer au cours du temps ; pour une garantie utile, on doit limiter son nombre de changements. Ce cours analyse l'exponential weighting avec le regret statique.
Preuve — le regret dynamique est toujours plus grand, et il peut être forcé à être linéaire hors slides
① Le comparateur dynamique est plus fort. Pour tout $h\in\mathcal H$, la suite constante $(h,h,\dots,h)$ appartient à $\mathcal H^T$. Le minimum sur $\mathcal H^T$ est donc $\le$ le minimum sur les suites constantes, c'est-à-dire $\le\min_h\sum_t\ell(y_t,h(x_t))$. On retranche un nombre plus petit : $\mathrm{Reg}^{\text{dynamic}}_T\ge\mathrm{Reg}^{\text{static}}_T$.
② Le minimum sur $\mathcal H^T$ se calcule tour par tour. La somme $\sum_t\ell(y_t,h_t(x_t))$ se découpe en termes qui ne dépendent chacun que d'un $h_t$ : on minimise chacun séparément, $\min_{(h_t)}\sum_t\ell = \sum_t\min_{h\in\mathcal H}\ell(y_t,h(x_t))$.
③ Exemple où il est linéaire. Avec $\mathcal H = \{h_{-1},h_{+1}\}$ (experts constants) et la perte 0-1, à chaque tour l'un des deux a raison : $\min_h\ell(y_t,h) = 0$, et le comparateur dynamique a une perte nulle. Le regret dynamique est alors la perte de l'apprenant tout entière ; un adversaire non anticipant qui joue l'étiquette la moins probable sous $p_t$ lui inflige au moins $\frac12$ par tour en espérance : $\E[\mathrm{Reg}^{\text{dynamic}}_T]\ge\frac T2$.
Moralité : se comparer à un oracle qui change d'avis à chaque tour est trop ambitieux sans hypothèse. D'où la restriction du nombre de changements de la slide 10. Dans la scène, coche « comparateur et regret dynamiques ».
∎
3Un résultat négatif : il faut randomiser
Où on en est
Acquis
Le regret, et l'objectif : $\mathrm{Reg}_T$ sous-linéaire contre tout adversaire non anticipant.
Il manque
Savoir si c'est seulement possible. Peut-on obtenir un regret sous-linéaire avec un algorithme « raisonnable » et déterministe ?
Cette partie
Non : tout apprenant déterministe a un regret $\ge T/2$. Puis les deux échappatoires : randomiser, ou supposer une structure sur la suite.
▶ Vidéosen anglais · s'ouvrent sur YouTube
Lemme (slide 11)
En classification binaire, pour tout apprenant déterministe, il existe un $\mathcal H$ et une suite d'exemples étiquetés tels que
$$\mathrm{Reg}_T\ge\frac T2.$$
Un apprenant déterministe ne peut pas garantir un regret sous-linéaire sans hypothèse sur les données.
Preuve — détaillée (slide 12)
① Le cadre. Étiquettes $y_t\in\{-1,+1\}$, perte 0-1 $\ell(y_t,\hat y_t) = \mathbb 1(\hat y_t\ne y_t)$, apprenant déterministe : sa prédiction est une fonction fixée de ce qu'il a vu,
$$\hat y_t = A\big(x_1,y_1,\dots,x_{t-1},y_{t-1},x_t\big).$$
② L'adversaire. Il connaît $A$ (l'algorithme est public). Au tour $t$, il choisit n'importe quel $x_t$, calcule $\hat y_t = A(\text{passé},x_t)$ — il connaît le passé et $A$ est déterministe — et choisit $y_t := -\hat y_t$.
C'est bien un adversaire non anticipant : il n'utilise que le passé et la connaissance de l'algorithme. Pour un apprenant déterministe, « connaître le passé » suffit pour connaître la prédiction courante : il n'y a rien de caché.
③ La perte de l'apprenant. À chaque tour $\hat y_t\ne y_t$, donc $\ell(y_t,\hat y_t) = 1$ et $\sum_{t=1}^T\ell(y_t,\hat y_t) = T$.
④ Il faut aussi regarder le meilleur expert. Une perte de $T$ ne suffit pas : si les experts se trompaient aussi à chaque tour, le regret serait nul. On choisit $\mathcal H := \{h_{-1},h_{+1}\}$, où $h_y$ prédit toujours $y$. À chaque tour, exactement un des deux a raison (celui qui prédit $y_t$), donc
$$\ell\big(y_t,h_{-1}(x_t)\big)+\ell\big(y_t,h_{+1}(x_t)\big) = 1\quad\Longrightarrow\quad\sum_{t=1}^T\ell\big(y_t,h_{-1}(x_t)\big)+\sum_{t=1}^T\ell\big(y_t,h_{+1}(x_t)\big) = T.$$
⑤ Le meilleur des deux a au plus $T/2$ erreurs. Deux nombres de somme $T$ ne peuvent pas être tous les deux $>T/2$ (leur somme dépasserait $T$). Donc $L(h_{-1})\le\frac T2$ ou $L(h_{+1})\le\frac T2$, c'est-à-dire $\min_{h\in\mathcal H}\sum_t\ell(y_t,h(x_t))\le\frac T2$.
⑥ Conclusion.
$$\mathrm{Reg}_T = \underbrace{\sum_{t=1}^T\ell(y_t,\hat y_t)}_{=\ T}-\underbrace{\min_{h\in\mathcal H}\sum_{t=1}^T\ell\big(y_t,h(x_t)\big)}_{\le\ T/2}\ \ge\ T-\frac T2 = \frac T2.$$
∎
Intuitivement, pourquoi ? (slide 11)
Réponse
Un algorithme déterministe est prévisible : quiconque connaît le code et le passé sait ce qu'il va dire. Un adversaire n'a qu'à dire le contraire. Les experts, eux, ne sont pas visés : l'un d'eux est d'accord avec l'adversaire au moins une fois sur deux. L'apprenant perd à tous les coups pendant qu'un expert fixe ne perd qu'une fois sur deux : l'écart grandit comme $T/2$.
Dans la scène, essaie les apprenants déterministes : quelle que soit leur règle, la courbe jaune est la diagonale (perte $T$), et le regret dépasse $T/2$. Passe ensuite à l'exponential weighting contre un adversaire non anticipant.
Deux façons d'échapper à la borne (slide 13)
- Un apprenant randomisé, sans hypothèse sur la suite → exponential weighting (§5–6).
- Un apprenant déterministe, avec une hypothèse de structure sur la suite → par exemple le perceptron sous séparabilité.
Pourquoi « non anticipant » ? L'adversaire peut dépendre du passé et connaître $p_t$, mais doit choisir $y_t$ avant d'observer la prédiction. S'il la voyait d'abord, la randomisation ne servirait à rien.
Ce que la randomisation change, en une ligne de calcul hors slides
① Contre un adversaire non anticipant. Au tour $t$, $y_t$ est fixé (en fonction du passé), puis l'apprenant tire $\hat y_t$ selon une loi $q_t$. La perte espérée de ce tour vaut $\Pr(\hat y_t\ne y_t) = 1-q_t(y_t)$. Le pire que puisse faire l'adversaire est de choisir l'étiquette la moins probable : perte espérée $\max_yq_t(y)$, qui vaut $\frac12$ si $q_t$ est équilibrée. Il ne peut plus forcer une perte de 1 à chaque tour.
② Mais randomiser ne suffit pas. Pile ou face à chaque tour donne une perte espérée $T/2$ ; si l'adversaire joue toujours $-1$, l'expert $h_{-1}$ ne se trompe jamais, et le regret vaut $T/2$. Il faut randomiser et apprendre : déplacer la masse de $q_t$ vers les experts qui réussissent. C'est exactement l'exponential weighting.
③ Contre un adversaire anticipant. Il voit $\hat y_t$ puis choisit $y_t = -\hat y_t$ : la preuve du lemme s'applique mot pour mot, même à un apprenant randomisé.
L'autre échappatoire : le perceptron hors slides
Si l'on suppose que la suite est séparable par un hyperplan avec une marge $\gamma>0$ (chapitre 3) et que $\|\bx_t\|\le R$, le perceptron (déterministe) fait au plus $(R/\gamma)^2$ erreurs, quel que soit $T$ (théorème de Novikoff). L'adversaire ne peut plus jouer n'importe quelle étiquette : il doit rester cohérent avec un séparateur à marge. La garantie vient de l'hypothèse, pas du hasard.
4Weighted Majority
Où on en est
Acquis
La mesure (regret), et l'obstacle : un apprenant déterministe est battu ; il faudra randomiser.
Il manque
Un mécanisme pour apprendre à qui faire confiance quand la qualité des experts change au cours du temps.
Cette partie
Weighted Majority : des poids, un vote pondéré, une pénalité multiplicative $\beta$. Sa garantie (hors slides) et ses deux défauts, qui motivent le §5.
Pourquoi pondérer des experts ? (slide 15)
C'est une méthode générale pour apprendre avec des conseils d'experts, par exemple $\{$wunderground.com, bbc.com, weather.com, cnn.com$\}$. On pourrait choisir le meilleur expert et répéter sa prédiction, mais la qualité des experts change au cours du temps : on préfère garder une confiance graduée en chacun.
Algorithme 1 — Weighted Majority (slide 16)
Classification binaire, $\mathcal Y = \{0,1\}$, $\beta\in(0,1)$.
- $w_1\leftarrow(1,\dots,1)$
- pour $t = 1,\dots,T$ :
- observer $x_t$ ;
- prédire $\hat y_t\leftarrow\mathbb 1\Big(\sum_{i:\,h_i(x_t) = 1}w_t(i)\ \ge\sum_{i:\,h_i(x_t) = 0}w_t(i)\Big)$ ;
- observer $y_t$ ;
- si $\hat y_t\ne y_t$ : $w_{t+1}(i)\leftarrow\beta\,w_t(i)$ si $h_i(x_t)\ne y_t$, et $w_{t+1}(i)\leftarrow w_t(i)$ si $h_i(x_t) = y_t$ ;
- sinon : $w_{t+1}\leftarrow w_t$.
Les objets en jeu
- $w_t(i)$
- confianceAprès $m$ pénalités, $w_t(i) = \beta^m$ : chaque erreur sanctionnée divise la confiance par $1/\beta$ (par 2 si $\beta = \frac12$).
- vote pondéré
- décision déterministeOn compare le poids total des experts qui disent 1 à celui des experts qui disent 0 ; égalité → 1.
- $\beta$
- sévéritéProche de 0 : on élimine presque un expert dès sa première faute. Proche de 1 : on pardonne beaucoup, on s'adapte lentement.
Preuve — le nombre d'erreurs de Weighted Majority est contrôlé par celui du meilleur expert hors slides
Notons $M$ le nombre d'erreurs de WM sur les $T$ tours, $m^\star$ celui du meilleur expert $i^\star$, et $W_t = \sum_iw_t(i)$ le poids total. On montre $$M\le\frac{\ln K+m^\star\ln(1/\beta)}{\ln\big(2/(1+\beta)\big)}.$$
① Au départ. $W_1 = K$ (tous les poids valent 1).
② Un tour où WM a raison. Les poids ne changent pas : $W_{t+1} = W_t$.
③ Un tour où WM se trompe. WM a prédit l'étiquette qui avait au moins la moitié du poids. Comme $\hat y_t\ne y_t$, tous les experts qui ont prédit $\hat y_t$ se sont trompés : leur poids total $W^{\text{faux}}$ vérifie $W^{\text{faux}}\ge\frac12W_t$. Après la mise à jour :
$$W_{t+1} = \underbrace{(W_t-W^{\text{faux}})}_{\text{poids inchangés}}+\beta W^{\text{faux}} = W_t-(1-\beta)W^{\text{faux}}\le W_t-(1-\beta)\frac{W_t}2 = \frac{1+\beta}2\,W_t.$$
C'est le cœur de l'argument : chaque erreur de l'apprenant fait fondre le poids total d'au moins un facteur $\frac{1+\beta}2<1$, parce qu'une erreur du vote implique qu'une majorité (en poids) s'est trompée.
④ Après $M$ erreurs. En enchaînant ② et ③ : $W_{T+1}\le K\Big(\frac{1+\beta}2\Big)^M$.
⑤ Le poids du meilleur expert résiste. $w(i^\star)$ n'est multiplié par $\beta$ que lors des tours où WM se trompe et $i^\star$ se trompe, donc au plus $m^\star$ fois : $w_{T+1}(i^\star)\ge\beta^{m^\star}$.
⑥ Comparer. Un poids est inférieur au total : $\beta^{m^\star}\le w_{T+1}(i^\star)\le W_{T+1}\le K\big(\frac{1+\beta}2\big)^M$. On prend le logarithme (croissant) :
$$m^\star\ln\beta\le\ln K+M\ln\frac{1+\beta}2.$$
Comme $\ln\frac{1+\beta}2 = -\ln\frac2{1+\beta}<0$ et $\ln\beta = -\ln\frac1\beta$, on réarrange : $M\ln\frac2{1+\beta}\le\ln K+m^\star\ln\frac1\beta$, puis on divise par $\ln\frac2{1+\beta}>0$.
⑦ Exemple $\beta = \frac12$. $M\le\frac{\ln K+m^\star\ln2}{\ln(4/3)}\approx2.41\,m^\star+3.48\ln K$. Le facteur devant $m^\star$ est supérieur à 2, et ce n'est pas un défaut de la preuve : contre l'adversaire du §3, $M = T$ alors que $m^\star\le T/2$, donc aucune borne de la forme $M\le c\,m^\star+\dots$ avec $c<2$ n'est possible pour un algorithme déterministe.
∎
Les deux défauts de Weighted Majority (slide 17)
- ✗ L'algorithme est déterministe. Le lemme du §3 s'applique : un adversaire fait se tromper WM à chaque tour, et avec $\mathcal H = \{h_{-1},h_{+1}\}$ le regret vaut au moins $T/2$. Coche « adversaire » dans la scène.
- ✗ L'algorithme est limité à la classification : le vote majoritaire et la pénalité « s'est trompé / a eu raison » supposent des étiquettes discrètes et une perte 0-1.
Qu'est-ce qui ne va pas avec un algorithme déterministe ? (slide 17)
Réponse
Il est prévisible. Connaissant les poids (calculables à partir du passé), l'adversaire connaît le vote et joue l'inverse : $M_T = T$. La borne ci-dessus reste vraie, mais elle devient inutile, car le meilleur expert a alors au moins $\approx T/2.4$ erreurs. Le regret, lui, est $\ge T/2$ : linéaire.
5Randomiser : de Weighted Majority à l'exponential weighting
Où on en est
Acquis
Des poids multiplicatifs suivent bien la qualité des experts (§4), mais le vote déterministe est battu (§3).
Il manque
Rendre la prédiction imprévisible, et sortir de la classification.
Cette partie
Randomized Weighted Majority (tirer un expert au lieu de voter), la réécriture $(1-\eta)^{\ell}$, puis $e^{-\eta\ell}$ : l'algorithme exponential weighting, et sa forme « softmax des pertes cumulées ».
▶ Vidéosen anglais · s'ouvrent sur YouTube
Algorithme 2 — Randomized Weighted Majority (slide 18)
Classification, $\beta\in(0,1)$.
- $w_1\leftarrow(1,\dots,1)$
- pour $t = 1,\dots,T$ :
- observer $x_t$ ;
- poser $p_t(i) := w_t(i)/\sum_jw_t(j)$ pour tout $i$ ;
- tirer $i\sim p_t$ et prédire $\hat y_t\leftarrow h_i(x_t)$ ;
- observer $y_t$ ;
- $w_{t+1}(i)\leftarrow\beta\,w_t(i)$ si $h_i(x_t)\ne y_t$, et $w_{t+1}(i)\leftarrow w_t(i)$ si $h_i(x_t) = y_t$.
Réécrire la mise à jour pour toute perte bornée (slide 19)
Avec $\beta := 1-\eta$ et $\ell(y_t,h_i(x_t)) := \mathbb 1(h_i(x_t)\ne y_t)$, la mise à jour de RWM s'écrit
$$w_{t+1}(i)\leftarrow w_t(i)\,(1-\eta)^{\ell(y_t,h_i(x_t))}.$$
Cette écriture a un sens pour n'importe quelle perte bornée, pas seulement 0-1. De plus, pour $\eta$ petit,
$$(1-\eta)^{\ell}\approx\exp(-\eta\,\ell).$$
L'exponentielle n'est qu'une approximation de la mise à jour « linéaire », mais elle a de meilleures propriétés mathématiques (interprétation probabiliste, preuves de regret plus simples).
Preuve — $(1-\eta)^{\ell}$ et $e^{-\eta\ell}$ : l'encadrement précis hors slides
① Pour $\ell\in\{0,1\}$, c'est bien RWM. $\ell = 0$ (l'expert a raison) : $(1-\eta)^0 = 1$, le poids ne change pas. $\ell = 1$ : $(1-\eta)^1 = \beta$. Exactement la ligne 5 de l'algorithme 2.
② Majorant : $\ln(1-\eta)\le-\eta$ pour $\eta\in[0,1)$. La fonction $u\mapsto\ln(1+u)$ est concave, donc sous sa tangente en 0, qui est $u\mapsto u$. Avec $u = -\eta$ : $\ln(1-\eta)\le-\eta$, donc $1-\eta\le e^{-\eta}$.
③ Minorant : $\ln(1-\eta)\ge-\eta-\eta^2$ pour $\eta\in[0,\frac12]$. Posons $g(\eta) = \ln(1-\eta)+\eta+\eta^2$. Alors $g(0) = 0$ et
$$g'(\eta) = -\frac1{1-\eta}+1+2\eta = \frac{-1+(1+2\eta)(1-\eta)}{1-\eta} = \frac{\eta-2\eta^2}{1-\eta} = \frac{\eta(1-2\eta)}{1-\eta}\ge0\quad\text{sur }[0,\tfrac12].$$
$g$ est croissante et part de 0, donc $g\ge0$ sur $[0,\frac12]$.
④ L'encadrement. En multipliant par $\ell\ge0$ et en prenant l'exponentielle : $e^{-(\eta+\eta^2)\ell}\le(1-\eta)^{\ell}\le e^{-\eta\ell}$. Les deux mises à jour coïncident à l'ordre 1 en $\eta$ ; elles diffèrent d'un facteur $e^{-\eta^2\ell}$ au plus, négligeable quand $\eta$ est petit (et l'analyse du §6 choisit $\eta\approx\sqrt{8\ln K/T}$, petit).
∎
La scène reproduit la figure de la slide 20 : le poids d'un expert en fonction de sa perte cumulée $c$, pour les deux mises à jour.
Algorithme 3 — Exponential Weighting (slide 21)
$\mathcal H := \{h_1,\dots,h_{|\mathcal H|}\}$ un ensemble d'experts, perte $\ell(\cdot)\in[0,1]$.
- $w_1\leftarrow(1,\dots,1)$
- pour $t = 1,\dots,T$ :
- observer $x_t$ ;
- poser $p_t(i) := w_t(i)/\sum_jw_t(j)$ pour tout $i$ ;
- tirer $i\sim p_t$ et prédire $\hat y_t\leftarrow h_i(x_t)$ ;
- observer $y_t$ ;
- $w_{t+1}(i)\leftarrow w_t(i)\exp\{-\eta\cdot\ell(y_t,h_i(x_t))\}$ pour tout $i\in\{1,\dots,|\mathcal H|\}$.
Les objets en jeu
- $w_t(i)$
- poids non normaliséNe dépend que de la perte cumulée de l'expert $i$ (voir la preuve ci-dessous).
- $p_t$
- loi sur les expertsCalculée avant de voir $y_t$ ; c'est tout ce qu'un adversaire non anticipant peut connaître de la prochaine prédiction.
- $I_t\sim p_t$
- tirage interneLa seule source de hasard. Le regret de la slide 22 est une espérance sur ces tirages.
- $\eta$
- sensibilitéCombien une unité de perte coûte en confiance : $e^{-\eta}$ par unité.
Preuve — $p_t$ est une softmax des pertes cumulées, de température $1/\eta$ hors slides
① Poids en forme close. Partant de $w_1(i) = 1$ et multipliant à chaque tour : $w_{t+1}(i) = \prod_{s=1}^te^{-\eta\ell_s(i)} = \exp\big(-\eta\sum_{s=1}^t\ell_s(i)\big) = e^{-\eta L_{t,i}}$, en notant $L_{t,i} = \sum_{s\le t}\ell_s(i)$ (et $L_{0,i} = 0$). L'ordre des pertes n'a aucune importance : seule compte leur somme.
② La distribution. $p_t(i) = \dfrac{e^{-\eta L_{t-1,i}}}{\sum_je^{-\eta L_{t-1,j}}} = \mathrm{softmax}\big(-\eta\,L_{t-1}\big)_i$ : la softmax du chapitre 5 appliquée aux « logits » $-\eta L_{t-1,i}$, c'est-à-dire de température $T_{\text{soft}} = 1/\eta$.
③ Les deux extrêmes. $\eta\to0$ : tous les logits tendent vers 0, $p_t$ tend vers la loi uniforme (on n'apprend rien). $\eta\to\infty$ : toute la masse va sur l'expert de plus petite perte cumulée, c'est « suivre le meneur » (follow the leader), déterministe, donc battu par l'adversaire. L'exponential weighting interpole entre les deux ; le §6 dit où se placer.
④ Rapport de deux experts. $\frac{p_t(i)}{p_t(j)} = e^{-\eta(L_{t-1,i}-L_{t-1,j})}$ : chaque unité de perte d'écart multiplie la préférence par $e^{\eta}$.
∎
La scène montre la distribution $p_t$ au fil des tours (aires empilées) et le regret espéré, avec la borne du §6. Compare les environnements : stationnaire, changement à mi-parcours, et un adversaire adaptatif : les pertes sont tirées au hasard (l'expert 1 est le meilleur), mais dès qu'un expert porte plus de la moitié du poids, l'adversaire lui inflige une perte 1. Il punit donc à la fois la lenteur (petit $\eta$) et la concentration (grand $\eta$).
Pourquoi les poids basculent tard après un changement hors slides
Avec « changement à mi-parcours », le nouvel expert ne prend la tête qu'une fois son retard en perte cumulée rattrapé, souvent bien après le changement : $p_t$ ne dépend que de $L_{t-1}$, pas des performances récentes. Ce n'est pas un défaut vis-à-vis du théorème, qui compare à un expert fixe (regret statique). Pour suivre un meilleur expert qui change, on utilise des variantes qui « oublient » (par exemple fixed share : remélanger un peu de poids uniforme à chaque tour), analysées avec le regret dynamique à nombre de changements limité (slide 10).
6La garantie : $\E[\mathrm{Reg}_T]\le\sqrt{T\ln|\mathcal H|}$
Où on en est
Acquis
L'algorithme : tirer $I_t\sim p_t$ avec $p_t\propto e^{-\eta L_{t-1}}$.
Il manque
Une preuve que son regret est sous-linéaire contre tout adversaire non anticipant, et le choix de $\eta$.
Cette partie
Le théorème de la slide 22, sa preuve complète par le potentiel $W_t$ et le lemme de Hoeffding (prouvé aussi), puis le choix $\eta^\star = \sqrt{8\ln K/T}$.
▶ Vidéosen anglais · s'ouvrent sur YouTube
Théorème (slide 22)
Pour tout $\mathcal H$ fini et toute perte $\ell$ à valeurs dans $[0,1]$, dans un environnement adversarial,
$$\E[\mathrm{Reg}_T] = \E\Big[\sum_{t=1}^T\ell\big(y_t,h_{I_t}(x_t)\big)-\min_{h\in\mathcal H}\sum_{t=1}^T\ell\big(y_t,h(x_t)\big)\Big]\le\sqrt{T\ln|\mathcal H|},$$
où $I_t\sim p_t$ et $\eta = \sqrt{\frac{8\ln|\mathcal H|}T}$. L'espérance porte sur la randomisation interne de l'apprenant. On en déduit que $\mathcal H$ fini est « apprenable » : $\frac{\E[\mathrm{Reg}_T]}T\le\sqrt{\frac{\ln|\mathcal H|}T}\to0$.
Les objets en jeu dans la preuve
- $W_t = \sum_iw_t(i)$
- potentielUne seule quantité qu'on encadre de deux façons : par le bas grâce au meilleur expert, par le haut grâce à la perte de l'apprenant.
- $\langle p_t,\ell_t\rangle = \sum_ip_t(i)\ell_t(i)$
- perte espérée du tour $t$Ce que l'apprenant perd en moyenne au tour $t$, sachant le passé.
- $K = |\mathcal H|$, $L^\star = \min_iL_{T,i}$
- entiers, réelNombre d'experts ; perte du meilleur expert a posteriori.
Preuve — complète, étape par étape
On montre d'abord, pour tout $\eta>0$ et toute suite de pertes $\ell_t(i)\in[0,1]$, l'inégalité déterministe $$\sum_{t=1}^T\langle p_t,\ell_t\rangle-L^\star\ \le\ \frac{\ln K}\eta+\frac{\eta T}8,\qquad(\star)$$ puis on en déduit le théorème.
① Minorer le potentiel final par le meilleur expert. Par la forme close du §5, $w_{T+1}(i) = e^{-\eta L_{T,i}}$. Une somme de termes positifs est plus grande que chacun de ses termes, en particulier que celui du meilleur expert $i^\star$ :
$$W_{T+1} = \sum_ie^{-\eta L_{T,i}}\ \ge\ e^{-\eta L^\star}.$$
Avec $W_1 = K$ : $\ \ln\dfrac{W_{T+1}}{W_1}\ \ge\ -\eta L^\star-\ln K.$
Si un expert est bon, son poids reste gros, donc le total aussi. Le prix de ne pas savoir lequel est bon est seulement $\ln K$ : le poids initial du bon expert est $1$ sur un total de $K$.
② Le rapport d'un tour au suivant est une espérance.
$$\frac{W_{t+1}}{W_t} = \frac{\sum_iw_t(i)e^{-\eta\ell_t(i)}}{W_t} = \sum_i\underbrace{\frac{w_t(i)}{W_t}}_{=\ p_t(i)}e^{-\eta\ell_t(i)} = \E_{i\sim p_t}\Big[e^{-\eta\ell_t(i)}\Big].$$
③ Majorer chaque rapport (lemme de Hoeffding). Soit $X = \ell_t(i)$ avec $i\sim p_t$ : c'est une variable aléatoire à valeurs dans $[0,1]$, de moyenne $\E X = \langle p_t,\ell_t\rangle$. Le lemme de Hoeffding (prouvé plus bas), avec $s = -\eta$, donne
$$\ln\E\big[e^{-\eta X}\big]\le-\eta\,\E X+\frac{\eta^2}8,\qquad\text{donc}\qquad\ln\frac{W_{t+1}}{W_t}\le-\eta\,\langle p_t,\ell_t\rangle+\frac{\eta^2}8.$$
Lecture : le potentiel diminue d'autant plus que l'apprenant perd en moyenne. Chaque perte de l'apprenant se paie en potentiel, au terme $\eta^2/8$ près.
④ Sommer sur les tours (somme télescopique). $\ln\frac{W_{T+1}}{W_1} = \sum_{t=1}^T\ln\frac{W_{t+1}}{W_t}$ (les termes intermédiaires se simplifient), donc
$$\ln\frac{W_{T+1}}{W_1}\le-\eta\sum_{t=1}^T\langle p_t,\ell_t\rangle+\frac{\eta^2T}8.$$
⑤ Combiner ① et ④. La même quantité est encadrée des deux côtés :
$$-\eta L^\star-\ln K\ \le\ \ln\frac{W_{T+1}}{W_1}\ \le\ -\eta\sum_t\langle p_t,\ell_t\rangle+\frac{\eta^2T}8.$$
On passe $-\eta\sum_t\langle p_t,\ell_t\rangle$ à gauche et $-\ln K$ à droite : $\eta\big(\sum_t\langle p_t,\ell_t\rangle-L^\star\big)\le\ln K+\frac{\eta^2T}8$. On divise par $\eta>0$ : c'est $(\star)$.
⑥ Passer à l'espérance du regret. L'adversaire choisit $y_t$ (donc le vecteur $\ell_t$) avant le tirage $I_t$, et $p_t$ ne dépend que du passé. Sachant le passé, $I_t\sim p_t$, donc
$$\E\big[\ell_t(I_t)\,\big|\,\text{passé}\big] = \sum_ip_t(i)\ell_t(i) = \langle p_t,\ell_t\rangle.$$
Par la tour des espérances, $\E\big[\sum_t\ell_t(I_t)\big] = \E\big[\sum_t\langle p_t,\ell_t\rangle\big]$, et donc
$$\E[\mathrm{Reg}_T] = \E\Big[\sum_t\langle p_t,\ell_t\rangle-L^\star\Big]\le\frac{\ln K}\eta+\frac{\eta T}8,$$
car $(\star)$ est vraie pour chaque réalisation (même si l'adversaire adaptatif rend les $\ell_t$, donc $L^\star$, aléatoires).
C'est ici que « non anticipant » sert : si $\ell_t$ pouvait dépendre de $I_t$, l'égalité $\E[\ell_t(I_t)\,|\,\text{passé}] = \langle p_t,\ell_t\rangle$ serait fausse.
⑦ Choisir $\eta$. $f(\eta) = \frac a\eta+b\eta$ avec $a = \ln K$, $b = \frac T8$. $f'(\eta) = -\frac a{\eta^2}+b = 0\iff\eta^\star = \sqrt{a/b} = \sqrt{\frac{8\ln K}T}$ ; $f''(\eta) = \frac{2a}{\eta^3}>0$, c'est donc un minimum global sur $(0,\infty)$, de valeur
$$f(\eta^\star) = \sqrt{ab}+\sqrt{ab} = 2\sqrt{\frac{T\ln K}8} = \sqrt{\frac{T\ln K}2}\ \le\ \sqrt{T\ln K}.$$
Les deux termes se disputent : $\frac{\ln K}\eta$ est le prix de la lenteur (avec $\eta$ petit, il faut longtemps pour se détacher de l'uniforme), $\frac{\eta T}8$ le prix de l'instabilité (avec $\eta$ grand, on suit le meneur du moment et l'adversaire en profite). À l'optimum, les deux termes sont égaux.
⑧ Regret moyen. $\frac{\E[\mathrm{Reg}_T]}T\le\sqrt{\frac{\ln K}{2T}}\le\sqrt{\frac{\ln K}T}\to0$. La dépendance en $K$ est seulement logarithmique : un million d'experts ne coûte que $\ln10^6\approx14$.
∎
Lemme de Hoeffding hors slides
Si $X\in[0,1]$ presque sûrement et $\mu = \E X$, alors pour tout $s\in\R$ :
$$\ln\E\big[e^{sX}\big]\le s\mu+\frac{s^2}8.$$
Preuve du lemme de Hoeffding, étape par étape
① Se ramener à une Bernoulli (convexité). Pour $x\in[0,1]$, on écrit $x$ comme mélange de 0 et 1 : $x = (1-x)\cdot0+x\cdot1$. L'exponentielle $u\mapsto e^{su}$ est convexe, donc elle est sous sa corde entre 0 et 1 :
$$e^{sx}\le(1-x)e^{0}+x\,e^{s}.$$
On prend l'espérance : $\E[e^{sX}]\le1-\mu+\mu e^s$. Il suffit donc de montrer $\psi(s) := \ln(1-\mu+\mu e^s)\le s\mu+\frac{s^2}8$.
Le pire cas, à moyenne fixée, est la variable qui ne prend que les valeurs extrêmes 0 et 1 (une Bernoulli) : c'est la plus « étalée ».
② Valeur et pente en 0. $\psi(0) = \ln1 = 0$. En dérivant : $\psi'(s) = \dfrac{\mu e^s}{1-\mu+\mu e^s} =: q(s)$, et $\psi'(0) = \mu$.
③ La courbure est au plus $\frac14$. En dérivant $q$ (quotient) :
$$q'(s) = \frac{\mu e^s(1-\mu+\mu e^s)-\mu e^s\cdot\mu e^s}{(1-\mu+\mu e^s)^2} = \frac{\mu e^s(1-\mu)}{(1-\mu+\mu e^s)^2} = q(s)\big(1-q(s)\big).$$
Comme $q(s)\in[0,1]$ et que $u(1-u)\le\frac14$ sur $[0,1]$ (parabole de sommet $u = \frac12$), on a $\psi''(s) = q(1-q)\le\frac14$ pour tout $s$.
④ Taylor avec reste de Lagrange. Il existe $\xi$ entre 0 et $s$ tel que
$$\psi(s) = \psi(0)+s\,\psi'(0)+\frac{s^2}2\psi''(\xi)\ \le\ 0+s\mu+\frac{s^2}2\cdot\frac14 = s\mu+\frac{s^2}8.$$
⑤ Les cas limites. Si $\mu = 0$, alors $X = 0$ presque sûrement et $\ln\E[e^{sX}] = 0\le\frac{s^2}8$. Si $\mu = 1$, alors $X = 1$ et $\ln\E[e^{sX}] = s\le s+\frac{s^2}8$. La preuve vaut aussi pour $s\lt0$ : c'est le cas $s = -\eta$ utilisé au théorème.
∎
La dernière scène trace le regret mesuré à l'horizon $T$ en fonction de $\eta$, avec la borne $\frac{\ln K}\eta+\frac{\eta T}8$ et ses deux termes : on voit la forme en U et l'optimum $\eta^\star$.
Remarques hors slides
- Constante. La preuve donne $\sqrt{T\ln K/2}$, mieux que le $\sqrt{T\ln K}$ de la slide ; les deux sont $O(\sqrt{T\ln K})$. On sait aussi qu'aucun algorithme ne fait mieux qu'un ordre $\sqrt{T\ln K}$ dans le pire cas : l'exponential weighting est optimal à constante près.
- Horizon inconnu. $\eta^\star$ dépend de $T$. Si $T$ n'est pas connu, on peut relancer l'algorithme sur des périodes de longueur $1,2,4,8,\dots$ avec le $\eta$ adapté à chacune (« doubling trick »), ou prendre $\eta_t\propto\sqrt{\ln K/t}$ : même ordre de regret.
- Limite (slide 22). On suppose toujours un ensemble fini d'experts, ce qui peut être une limite en pratique.
7Résumé & questions des slides
Tout le chapitre en une chaîne
$$\underbrace{\text{aucune loi, adversaire non anticipant}}_{\text{§1}}\ \to\ \underbrace{\mathrm{Reg}_T = \sum_t\ell(y_t,\hat y_t)-\min_{h\in\mathcal H}\sum_t\ell(y_t,h(x_t))}_{\text{§2 : objectif }o(T)}\ \to\ \underbrace{\text{déterministe}\Rightarrow\mathrm{Reg}_T\ge\tfrac T2}_{\text{§3}}$$
$$\to\ \underbrace{I_t\sim p_t,\ \ p_t(i)\propto e^{-\eta L_{t-1,i}}}_{\text{§4–5 : WM → RWM → EW}}\ \to\ \underbrace{\E[\mathrm{Reg}_T]\le\tfrac{\ln K}\eta+\tfrac{\eta T}8 = \sqrt{\tfrac{T\ln K}2}\ \text{avec}\ \eta = \sqrt{\tfrac{8\ln K}T}}_{\text{§6}}$$
Messages clés (slide 23)
L'apprentissage en ligne est un nouveau cadre d'apprentissage, où le regret sert de mesure d'évaluation. Ce cadre suppose un environnement adversarial ou stochastique. L'algorithme d'exponential weighting garantit un regret espéré en $O(\sqrt{T\ln|\mathcal H|})$. On a supposé un retour complet (full feedback) : on voit la perte de tous les experts. L'apprentissage par renforcement considérera un retour partiel.
Pourquoi viser $\mathrm{Reg}_T = O(\sqrt T)$ ? (slide 9)
Réponse
Parce qu'alors le regret par tour $\mathrm{Reg}_T/T = O(1/\sqrt T)$ tend vers 0 : à la longue, on fait en moyenne aussi bien que le meilleur expert, sans savoir lequel c'est. Et on ne peut pas faire mieux en général : même avec des experts qui se trompent au hasard, le meilleur a posteriori a de l'avance par chance, d'ordre $\sqrt T$ (voir la preuve au §2).
Pourquoi l'adversaire voit-il les prédictions passées, et pas la courante ? (slide 8)
Réponse
Voir la courante, c'est pouvoir dire le contraire à chaque tour : aucune garantie n'est alors possible, même pour un apprenant randomisé. Voir le passé est réaliste (un fraudeur observe nos décisions passées) et laisse une chance à la randomisation : l'adversaire connaît $p_t$, pas $I_t$. Voir la réponse détaillée au §2.
Pourquoi un apprenant déterministe échoue-t-il, intuitivement ? (slides 11, 17)
Réponse
Il est prévisible : l'adversaire calcule sa prédiction et joue l'inverse, alors qu'un des deux experts constants a raison au moins une fois sur deux. Regret $\ge T/2$. Weighted Majority, déterministe, n'y échappe pas.
Pourquoi passer de $(1-\eta)^{\ell}$ à $e^{-\eta\ell}$ ? (slide 19)
Réponse
Les deux sont presque égales pour $\eta$ petit ($e^{-(\eta+\eta^2)\ell}\le(1-\eta)^{\ell}\le e^{-\eta\ell}$ si $\eta\le\frac12$). Mais l'exponentielle donne une forme close $w_{t+1}(i) = e^{-\eta L_{t,i}}$, une interprétation probabiliste ($p_t$ est une softmax des pertes cumulées), et une preuve courte grâce au lemme de Hoeffding, qui porte précisément sur $\E[e^{sX}]$.
Pour s'entraîner : exercices à trous (filtre « 6 · en ligne »).