Adapting machine learning methods to U-statistics

Résumé : L’explosion récente des volumes de données disponibles a fait de la complexité algorithmique un élément central des méthodes d’apprentissage automatique. Les algorithmes d’optimisation stochastique ainsi que les méthodes distribuées et décentralisées ont été largement développés durant les dix dernières années. Ces méthodes ont permis de faciliter le passage à l’échelle pour optimiser des risques empiriques dont la formulation est séparable en les observations associées. Pourtant, dans de nombreux problèmes d’apprentissage statistique, l’estimation précise du risque s’effectue à l’aide de U-statistiques, des fonctions des données prenant la forme de moyennes sur des d-uplets. Nous nous intéressons tout d’abord au problème de l’échantillonnage pour la minimisation du risque empirique. Nous montrons que le risque peut être remplacé par un estimateur de Monte-Carlo, intitulé U-statistique incomplète, basé sur seulement O(n) termes et permettant de conserver un taux d’apprentissage du même ordre. Nous établissons des bornes sur l’erreur d’approximation du U-processus et les simulations numériques mettent en évidence l’avantage d’une telle technique d’échantillonnage. Nous portons par la suite notre attention sur l’estimation décentralisée, où les observations sont désormais distribuées sur un réseau connexe. Nous élaborons des algorithmes dits gossip, dans des cadres synchrones et asynchrones, qui diffusent les observations tout en maintenant des estimateurs locaux de la U-statistique à estimer. Nous démontrons la convergence de ces algorithmes avec des dépendances explicites en les données et la topologie du réseau. Enfin, nous traitons de l’optimisation décentralisée de fonctions dépendant de paires d’observations. De même que pour l’estimation, nos méthodes sont basées sur la concomitance de la propagation des observations et l’optimisation local du risque. Notre analyse théorique souligne que ces méthodes conservent une vitesse de convergence du même ordre que dans le cas centralisé. Les expériences numériques confirment l’intérêt pratique de notre approche.
Type de document :
Thèse
Machine Learning [cs.LG]. Télécom ParisTech, 2016. English. 〈NNT : 2016ENST0070〉
Liste complète des métadonnées

Littérature citée [101 références]  Voir  Masquer  Télécharger

https://pastel.archives-ouvertes.fr/tel-01701636
Contributeur : Abes Star <>
Soumis le : mardi 6 février 2018 - 01:16:11
Dernière modification le : vendredi 9 février 2018 - 01:20:30

Fichier

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

Identifiants

  • HAL Id : tel-01701636, version 1

Citation

Igor Colin. Adapting machine learning methods to U-statistics. Machine Learning [cs.LG]. Télécom ParisTech, 2016. English. 〈NNT : 2016ENST0070〉. 〈tel-01701636〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

20