Accéder directement au contenu Accéder directement à la navigation
Thèse

Efficient Approximations of High-Dimensional Data

Résumé : Dans cette thèse, nous étudions les approximations de systèmes d'ensembles (X,S), où X est un ensemble de base et S est constitué de sous-ensembles de X appelés plages. Étant donné un système d'ensembles finis, notre objectif est de construire un petit sous-ensemble de X tel que chaque plage soit `bien-approximée'. En particulier, pour un paramètre epsilon donné dans (0,1), nous disons qu'un sous-ensemble A de X est une epsilon-approximation de (X,S) si pour toute plage R dans S, les fractions |A cap R|/|A| et |R|/|X| sont proches de epsilon.La recherche sur de telles approximations a commencé dans les années 1950, l'échantillonnage aléatoire étant l'outil clé pour montrer leur existence. Depuis lors, la notion d'approximations est devenue une structure fondamentale dans plusieurs communautés - théorie de l'apprentissage, statistiques, combinatoire et algorithmes. Une percée dans l'étude des approximations remonte à 1971, lorsque Vapnik et Chervonenkis ont étudié les systèmes d'ensembles avec une VC-dimension finie, qui s'est avérée être un paramètre clé pour caractériser leur complexité. Par exemple, si un système d'ensembles (X, S) a une VC-dimension d, alors un échantillon uniforme de O(d/epsilon^2) points est une approximation epsilon de (X, S) avec une probabilité élevée. Il est important de noter que la taille de l'approximation ne dépend que d'epsilon et de d, et qu'elle est indépendante des tailles d'entrée |X| et |S| !Dans la première partie de cette thèse, nous donnons une preuve modulaire, autonome et intuitive de la garantie d'échantillonnage uniforme ci-dessus. Dans la deuxième partie, nous donnons une amélioration d'un goulot d'étranglement algorithmique vieux de 30 ans - la construction d'appariements avec un faible nombre de croisements. Ceci peut être appliqué pour construire des approximations avec des garanties améliorées. Enfin, nous répondons à un problème ouvert vieux de 30 ans de Blumer etal. en prouvant des bornes inférieures serrées sur la dimension VC des unions de demi-espaces - un système d'ensembles géométriques qui apparaît dans plusieurs applications, par exemple les constructions de coresets
Type de document :
Thèse
Liste complète des métadonnées

https://tel.archives-ouvertes.fr/tel-03783594
Contributeur : ABES STAR :  Contact
Soumis le : jeudi 22 septembre 2022 - 11:42:32
Dernière modification le : lundi 3 octobre 2022 - 11:25:30

Fichier

TH2022UEFL2004.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-03783594, version 1

Collections

Citation

Mónika Csikós. Efficient Approximations of High-Dimensional Data. Logic [math.LO]. Université Gustave Eiffel, 2022. English. ⟨NNT : 2022UEFL2004⟩. ⟨tel-03783594⟩

Partager

Métriques

Consultations de la notice

0

Téléchargements de fichiers

0