Bornes de généralisation

Les bornes de généralisation fournissent des garanties probabilistes sur l'ampleur de l'écart entre l'erreur réelle d'un modèle et son erreur d'entraînement, en fonction de la taille de l'échantillon et de la capacité du modèle.

Definition

Une borne de généralisation est une inégalité qui stipule qu'avec une forte probabilité sur l'échantillon d'entraînement aléatoire, l'erreur réelle d'un modèle appris est au plus égale à son erreur d'entraînement augmentée d'un terme qui croît avec la capacité du modèle et diminue avec la taille de l'échantillon, certifiant ainsi la fiabilité du modèle sur des données non observées.

Scope

Ce sujet couvre les bornes théoriques de la généralisation : les bornes de convergence uniforme basées sur la dimension de Vapnik-Chervonenkis, les mesures de complexité telles que la complexité de Rademacher, les bornes basées sur la marge, et la notion de complexité d'échantillon probablement approximativement correcte. Il examine la dépendance de ces bornes à l'égard de la taille des données et de la capacité, ainsi que les raisons pour lesquelles elles ont tendance à être lâches en pratique.

Core questions

• Comment l'erreur réelle est-elle bornée en fonction de l'erreur d'entraînement et de la capacité ?
• Comment la borne s'améliore-t-elle à mesure que l'échantillon augmente ?
• Quelles mesures de complexité apparaissent dans les bornes modernes ?
• Pourquoi les bornes de généralisation sont-elles souvent lâches pour les modèles réels ?

Key theories

Bornes de convergence uniforme

Les bornes basées sur la dimension de Vapnik-Chervonenkis garantissent qu'avec une forte probabilité, l'erreur d'entraînement approche l'erreur réelle uniformément sur la classe de modèles, l'écart diminuant avec la racine carrée de la taille de l'échantillon par rapport à la capacité.

Bornes basées sur la marge et la complexité

Des raffinements utilisant la marge de classification ou la complexité de Rademacher fournissent des bornes plus serrées et dépendantes des données, qui expliquent mieux le succès des classifieurs à grande marge.

Complexité d'échantillon

Les bornes se traduisent en complexité d'échantillon, c'est-à-dire le nombre d'exemples nécessaires pour apprendre avec une précision et une confiance cibles, rendant explicites les exigences en données de l'apprentissage.

Clinical relevance

Les bornes de généralisation fournissent l'assurance formelle sous-jacente à la promesse centrale de l'apprentissage automatique, à savoir que l'ajustement des données conduit à la prédiction sur de nouvelles données, et elles motivent la régularisation et le contrôle de la capacité ; bien que généralement trop lâches pour prédire l'erreur exacte, elles saisissent la dépendance qualitative à l'égard de la taille et de la complexité des données qui guide la pratique.

History

Les premières bornes générales sont issues des résultats de convergence uniforme de Vapnik et Chervonenkis, affinées par la suite par des analyses basées sur la marge et la complexité de Rademacher. Le cadre « probablement approximativement correct » (PAC) a reformulé ces bornes en termes de complexité d'échantillon, et des travaux récents recherchent des bornes expliquant la généralisation des modèles fortement surparamétrés.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis
• Peter Bartlett

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

Que nous apprend une borne de généralisation ?

Elle indique qu'avec une forte probabilité, l'erreur du modèle sur des données non observées ne dépassera pas son erreur d'entraînement de plus d'une quantité qui dépend de la complexité de la classe de modèles et de la quantité de données utilisées. Plus de données et une capacité moindre resserrent la garantie.

Pourquoi ces bornes sont-elles souvent trop lâches pour être utilisées directement ?

Les bornes classiques sont des bornes de cas le plus défavorable et sont indépendantes de la distribution, elles sont donc valables pour toute distribution de données et tout modèle de la classe. Cette généralité les rend pessimistes, prédisant souvent des écarts d'erreur bien plus importants que ceux observés en pratique, elles sont donc utilisées davantage pour la compréhension conceptuelle que pour des chiffres exacts.