The Worst-Case Data-Generating Probability Measure - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2023

The Worst-Case Data-Generating Probability Measure

La mesure de probabilité génératrice de données dans le pire des cas

Résumé

In this report, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More specifically, the worst-case probability measure is a solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference σ-finite measure. Given a model, the central result consists of an explicit expression for the difference between the expectations of the loss with respect to any two given probability measures over the datasets. Such a difference is characterized in terms of “statistical distances” measured via KL-divergences involving the given measures; the reference measure; and the worst-case probability measure. When the given measures are the types (empirical probability measures) induced by two datasets, a closed-form expression for the difference between the corresponding empirical risks is obtained. Finally, the generalization gap induced by any arbitrary machine learning algorithm is characterized. Existing results for the Gibbs algorithm, such as the equality between the generalization gap and a sum of mutual information and lautum information, up to a constant factor, are recovered. All the above suggests a duality between the Gibbs algorithm and the worst-case measure beyond the fact that both are represented by Gibbs probability measures.
Dans ce rapport, la mesure de probabilité du pire cas sur les données est présentée comme un outil pour caractériser les capacités de généralisation des algorithmes d’apprentissage automatique. Plus précisément, la mesure de probabilité du pire cas est une solution à la maximisation de la valeur espérée de la perte (ou risque) induite par un modèle sous une contrainte d’entropie relative par rapport à une mesure σ-finie de référence. Étant donné un modèle, le résultat central consiste en une expression explicite de la différence entre les valeurs espérées de la perte par rapport à deux mesures de probabilité quelconques sur l’ensemble de données. Cette différence est caractérisée en termes de “distances statistiques” mesurées via des divergences KL impliquant les mesures données ; la mesure de référence ; et la mesure de probabilité du pire cas. Lorsque les mesures données sont les types (mesures de probabilité empiriques) induits par deux ensembles de données, une expression sous forme fermée pour la différence entre les risques empiriques correspondants est obtenue. Enfin, l’écart de généralisation induit par un algorithme d’apprentissage quelconque est caractérisé. Les résultats existants pour l’algorithme de Gibbs, tels que l’égalité entre l’écart de généralisation et une somme d’informations mutuelles et d’informations de lautum, à un facteur constant près, sont récupérés. Tout ce qui précède suggère une dualité entre l’algorithme de Gibbs et la mesure du pire cas au-delà du fait que les deux sont représentés par des mesures de probabilité de Gibbs.
Fichier principal
Vignette du fichier
INRIA-RR9515.pdf (882.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04181971 , version 1 (23-08-2023)
hal-04181971 , version 2 (03-01-2024)

Licence

Paternité

Identifiants

  • HAL Id : hal-04181971 , version 1

Citer

Xinying Zou, Samir M. Perlaza, Iñaki Esnaola, Eitan Altman. The Worst-Case Data-Generating Probability Measure. RR-9515, INRIA. 2023, pp.29. ⟨hal-04181971v1⟩
359 Consultations
395 Téléchargements

Partager

Gmail Facebook X LinkedIn More