Probably Approximately Correct
La question de Valiant (1984)
Leslie Valiant a posé une question trompeusement simple : qu'est-ce qu'apprendre pour une machine ? Pas « peut-elle mémoriser ? » Ni « peut-elle prédire parfaitement ? » Mais plutôt : peut-elle apprendre de manière approximativement correcte, avec une forte probabilité, à partir d'un échantillon fini, en temps polynomial ?
Cette formulation lui a valu le Turing Award en 2010 et a fondé la théorie computationnelle de l'apprentissage.
Deux boutons
ε (epsilon) — tolérance d’erreur. Approximativement correct signifie erreur ≤ ε. Plus ε est petit, plus l’apprentissage est strict.
δ (delta) — paramètre de confiance. Probablement correct signifie probabilité de succès ≥ 1 − δ. Plus δ est petit, plus la confiance requise est élevée.
Définition
Une classe de concepts C est dite PAC-apprenable s’il existe un algorithme tel que, pour toute distribution de données D et tout concept cible c ∈ C, étant donné m échantillons tirés de D et étiquetés par c, notre algorithme renvoie une hypothèse h satisfaisant :
P[erreur(h) ≤ ε] ≥ 1 − δ
avec m polynomial en 1/ε, 1/δ et la taille du concept.
En anglais : lui fournir suffisamment d’exemples et il s’en rapproche assez souvent, et « suffisamment » n’explose pas de manière exponentielle.
Complexité d’échantillonnage pour les espaces d’hypothèses finis
Si notre espace d’hypothèses H contient un nombre fini d’hypothèses candidates, l’analyse classique donne :
m ≥ (1/ε)(ln|H| + ln(1/δ))
Lisez cette formule comme un budget. Diviser ε par deux double le nombre d’échantillons requis. Diviser δ par deux ajoute une constante. Doubler |H| ajoute ln(2) échantillons — une croissance logarithmique, remarquablement maîtrisée.
Dimensionnement d’un échantillon pour une classe d’hypothèses
Un filtre anti-spam choisit parmi |H| = 1 000 000 ensembles de règles candidats. Nous voulons une erreur ε ≤ 0,05 avec une confiance 1 − δ = 0,99 (donc δ = 0,01).
Shattering et dimension VC
Quand les espaces d'hypothèses deviennent infinis
La borne m ≥ (1/ε)(ln|H| + ln(1/δ)) ne tient plus lorsque |H| = ∞. La plupart des classes d'hypothèses utiles (classifieurs linéaires dans ℝᵈ, arbres de décision, réseaux de neurones) contiennent un nombre infini de candidats. Vapnik et Chervonenkis ont résolu ce problème vers 1971 grâce à une mesure de complexité plus riche : la dimension VC.
Shattering
Une classe d'hypothèses H shatter un ensemble de n points si H peut produire tous les étiquetages possibles de ces n points (les 2ⁿ dichotomies). Les classifieurs linéaires dans ℝ² shatter n'importe quels 3 points en position générale : pour chacun des 8 étiquetages +/− possibles de ces 3 points, il existe une droite qui les sépare correctement.
Mais les classifieurs linéaires dans ℝ² ne peuvent pas briser 4 points disposés en configuration XOR. Aucune droite ne sépare la paire diagonale de la paire anti-diagonale.
Dimension VC
VC(H) = le plus grand n tel que H brise un certain ensemble de n points. Pour les classifieurs linéaires 2D : VC = 3. Pour les rectangles alignés sur les axes en 2D : VC = 4. Pour les réseaux de neurones avec W poids : VC ≤ O(W² log W) (Bartlett & Anthony 1999).
Complexité d'échantillonnage avec la dimension VC
Remplacer ln|H| dans notre borne PAC par la dimension VC d :
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))
La dimension VC agit comme notre « complexité effective » d’une classe infinie. Une classe d’hypothèses de faible dimension VC se généralise à partir de peu d’échantillons ; une classe de forte dimension VC exige davantage de données.
Dimension VC comme nombre effectif d’hypothèses
Un réseau de neurones possède W = 10⁹ poids. D’après la borne de Bartlett-Anthony, VC ≤ O(W² log W). On approxime VC ≈ W² log₂ W.
Abandon de la réalisabilité, Postérieurs sur les hypothèses
Deux généralisations importantes
Le PAC classique suppose que notre concept cible c appartient à notre classe d’hypothèses H. Les données réelles comportent du bruit, des erreurs d’étiquetage et des concepts que notre classe ne peut pas représenter. Deux extensions permettent de gérer cela.
PAC agnostique
Abandonnons l’hypothèse c ∈ H. Nous allons maintenant rivaliser avec notre hypothèse meilleure de sa classe h* = argmin_{h ∈ H} risk(h). La forme de la borne change : au lieu de nous rapprocher de la perfection, nous nous rapprochons du meilleur résultat possible dans H.
Borne agnostique : P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ avec une complexité d’échantillonnage m = O(1/ε² × (VC(H) + log(1/δ))). Notez ε² au lieu de ε au dénominateur : l’apprentissage agnostique nécessite plus d’exemples pour la même précision.
PAC-Bayes (McAllester 1999)
Passons du choix d’une seule hypothèse au choix d’une distribution sur les hypothèses. Partons d’une a priori P. Observons les données. Déduisons la postérieure Q. Les bornes PAC-Bayes portent sur le risque espéré sous Q :
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P) mesure à quel point notre postérieure s’est éloignée de notre a priori. Deux interprétations :
1. Vue compression. Une postérieure proche de son a priori (petit KL) généralise bien — faible coût d’information = petit écart de généralisation.
2. Vue bayésienne. A priori fort + mise à jour faible des données = borne serrée ; a priori faible + mise à jour forte des données = borne plus lâche.
Pourquoi PAC-Bayes est important. Les bornes PAC-Bayes empiriques (Catoni 2007, Dziugaite & Roy 2017) fournissent des garanties de généralisation numériquement significatives pour de vrais réseaux de neurones, là où les bornes PAC classiques sont vides. Elles restent notre outil théorique le plus serré sur la généralisation en surparamétrisation.
Lecture d’une borne PAC-Bayes
Supposez que nous entraînions un réseau sur n = 50 000 exemples étiquetés. Après l’entraînement, notre postérieur Q sur les poids a KL(Q‖P) = 200 nats par rapport à une a priori gaussienne P. Le risque empirique sous Q est de 0,10. Fixons δ = 0,05.
Surparamétrisation et double descent
La catastrophe prédite par le PAC classique
Le PAC classique prédit : plus de paramètres que d’échantillons = surapprentissage catastrophique. Apprentissage parfait sur les données d’entraînement, généralisation aléatoire sur les données de test. La borne VC prédit une mémorisation sans apprentissage.
Les réseaux de neurones modernes ont couramment 10× à 1000× plus de paramètres que d’échantillons d’entraînement et généralisent quand même. Cela ne devrait pas se produire selon la théorie classique. Cela se produit pourtant.
La courbe en U qu’on nous a enseignée
Biais-variance classique : lorsque la capacité du modèle augmente, l’erreur d’entraînement diminue de façon monotone ; l’erreur de test diminue d’abord (moins de sous-apprentissage), atteint un minimum, puis augmente (surapprentissage). Forme en U prédite par la théorie VC.
Ce qui se passe réellement — Double descente
Belkin et al (2019) ont montré que l’erreur de test suit notre courbe en U classique jusqu’au seuil d’interpolation (capacité = #échantillons), puis REDESCEND au-delà de ce seuil. Les modèles massivement surparamétrés généralisent mieux que les modèles juste assez grands.
Pourquoi le PAC classique ne capture pas ce phénomène
1. L’hypothèse distribution-free est trop pessimiste. Les données réelles possèdent une structure (dimension intrinsèque faible, géométrie de variété). Les bornes PAC s’appliquent sur des distributions du pire cas ; les distributions réelles exploitent une structure que la SGD exploite également.
2. Régularisation implicite. La SGD sur des réseaux surparamétrés trouve des solutions interpolantes de norme minimale ou de complexité minimale, et non des solutions arbitraires. La théorie classique suppose un minimiseur du risque empirique dans le pire des cas ; les algorithmes réels sélectionnent des solutions bénignes.
3. Définition incorrecte de la classe d’hypothèses. La classe d’hypothèses effective explorée par la SGD est bien plus petite que l’espace des poids nominal. Les posteriors PAC-Bayes capturent cela ; la dimension VC ne le fait pas.
Les travaux théoriques modernes (Bartlett, Long, Lugosi, Tsigler 2020 sur le surapprentissage bénin ; Nakkiran et al. 2020 sur la double descent) construisent une théorie de généralisation post-PAC qui tient compte de notre régime surparamétré.
Diagnostic d’un échec de la PAC classique
Une équipe de recherche entraîne un réseau de 1 milliard de paramètres sur 100 000 exemples étiquetés. La PAC classique prédit des bornes vides. Empiriquement, la précision sur le test atteint 95 %.
Kaplan, Chinchilla et le dimensionnement de l’Intelligence Générale Automatisée
Des bornes aux lois empiriques de mise à l’échelle
La PAC classique prédit théoriquement la taille des jeux de données et donne des résultats vides. Les lois empiriques de mise à l’échelle prédisent la taille des jeux de données à partir de l’observation et fonctionnent réellement. Elles ont remplacé la PAC comme outil pratique de dimensionnement pour les grands modèles.
Kaplan et al (2020)
La perte suit une loi de puissance en fonction des paramètres N, des tokens du jeu de données D et du calcul C :
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
Doubler les paramètres réduit la perte par un facteur multiplicatif fixe. Doubler les données réduit la perte par un autre facteur fixe. Ces exposants (αN, αD, αC) mesurent et prédisent le comportement de pointe sur de nombreux ordres de grandeur.
Hoffmann et al 2022 (Chinchilla)
Chinchilla a montré que les exposants de Kaplan surpondéraient les paramètres par rapport aux données. L’entraînement optimal en termes de calcul nécessite environ 20 tokens par paramètre :
D_opt ≈ 20 × N
GPT-3 (175 milliards de paramètres) a été entraîné sur ~300 milliards de tokens — largement sous-entraîné selon les calculs de Chinchilla. Un modèle optimal en calcul de 175 milliards de paramètres nécessite ~3,5 billions de tokens.
Le mur des données
Pour scaler notre nombre de paramètres, nous devons scaler proportionnellement notre nombre de tokens. Le crawl web public fournit environ ~10¹³ tokens utiles. Une intelligence générale automatisée hypothétique de 10¹⁵ paramètres nécessiterait ~2×10¹⁶ tokens — trois ordres de grandeur au-delà des données web disponibles.
C’est notre mur de données. Les lois de scaling prédisent que nous rencontrerons une pénurie de corpus bien avant une pénurie de calcul. Les données synthétiques, les corpus multimodaux (vidéo, audio, flux de capteurs) et le RL à partir de l’environnement visent tous à le dépasser.
Le PAC classique nous disait (incorrectement) que nous avions besoin de 10²¹ échantillons. Les lois de scaling nous disent (calibrées à la réalité) que nous avons besoin de 2×10¹⁶. Les deux nombres dépassent le texte disponible. Le travail de pointe actuel consiste à combler cet écart.
Estimation d’un corpus pour une intelligence générale automatisée
Supposons qu’un laboratoire de pointe propose un modèle de 10¹⁴ paramètres et affirme qu’il atteindra l’intelligence générale automatisée. Nous voulons dimensionner son corpus d’entraînement selon la règle de Chinchilla.
Des bornes théoriques aux mesures en production
Arrêter de calculer les bornes ; commencer à les mesurer
Les bornes PAC classiques sont vides. Les bornes PAC-Bayes sont serrées sous des hypothèses difficiles à vérifier. Une alternative pratique : mesurer ε empiriquement sur votre distribution réelle et le mettre à jour au fur et à mesure que votre système fonctionne.
Idée 1 — Rendre la couverture aussi empirique que PAC
Une cible make coverage exécute N questions de validation à travers votre système de requêtes et mesure deux taux :
- cache_hit_rate — fraction des cas où votre système a trouvé une réponse connue
- i_dont_know_rate — fraction des cas où votre système a honnêtement différé
Chaque mesure = un essai de Bernoulli. À partir des comptages observés, calculez un intervalle de confiance de Wilson sur le taux réel. Exemple : N = 1000 requêtes, i_dont_know_rate observé = 0,20 → IC 95 % ≈ [0,177, 0,226]. La borne supérieure 0,226 fonctionne exactement comme un ε PAC à δ = 0,05, dérivé de données réelles sur une distribution réelle plutôt que d’une analyse théorique du pire cas.
Le vocabulaire classique du PAC s’applique (ε, δ, confiance). Mécanisme différent (concentration binomiale vs. théorie VC). Résultat plus serré car les distributions réelles possèdent une structure exploitable.
Idée 2 — Audit PAC-Bayes via événements de falsification
Traiter chaque falsification (réponse du système manifestement erronée) comme une preuve mettant à jour la postérieure sur le taux d’erreur réel ε :
1. Prior : ε ~ Beta(α₀, β₀). Choisir un prior faible, ex. Beta(1, 1) = uniforme.
2. Chaque requête produit un résultat de Bernoulli : falsifié (1) ou maintenu (0).
3. Postérieur après k falsifications sur n requêtes : Beta(α₀ + k, β₀ + n − k).
4. Moyenne postérieure : (α₀ + k) / (α₀ + β₀ + n) → taux empirique de falsification lorsque n → ∞.
5. Intervalle crédible à 95 % sur ε se resserre comme 1/√n.
Ce que cela nous apporte
- Estimation réelle de ε₀ à partir du déploiement effectif, et non d’une théorie du pire cas
- Alarme anytime-valid : lorsque l’intervalle crédible postérieur franchit le seuil du contrat, alerter une personne
- Confiance monotone : plus de requêtes observées → IC plus serré → garantie plus forte
Techniques apparentées : prédiction conforme avec recalibrage en ligne (Vovk), tests séquentiels du rapport de vraisemblance (Wald), PAC-Bayes en ligne (Haddouche & Guedj 2022). Même famille, outils mathématiques différents.
Calcul d’une postérieure Beta sur les falsifications
Notre équipe réalise un audit de couverture sur un système de requêtes en production. A priori sur le taux d’erreur réel ε : Beta(1, 1) (uniforme). Après 200 requêtes de validation, nous avons observé 8 falsifications.