Adapting machine learning methods to U-statistics

Résumé : L?explosion re?cente des volumes de donne?es disponibles a fait de la complexite? algorithmique un e?le?ment central des me?thodes d?apprentissage automatique. Les algorithmes d?optimisation stochastique ainsi que les me?thodes distribue?es et de?centralise?es ont e?te? largement de?veloppe?s durant les dix dernie?res anne?es. Ces me?thodes ont permis de faciliter le passage a? l?e?chelle pour optimiser des risques empiriques dont la formulation est se?parable en les observations associe?es. Pourtant, dans de nombreux proble?mes d?apprentissage statistique, l?estimation pre?cise du risque s?effectue a? l?aide de U-statistiques, des fonctions des donne?es prenant la forme de moyennes sur des d-uplets. Nous nous inte?ressons tout d?abord au proble?me de l?e?chantillonnage pour la minimisation du risque empirique. Nous montrons que le risque peut e?tre remplace? par un estimateur de Monte-Carlo, intitule? U-statistique incomple?te, base? sur seulement O(n) termes et permettant de conserver un taux d?apprentissage du me?me ordre. Nous e?tablissons des bornes sur l?erreur d?approximation du U-processus et les simulations nume?riques mettent en e?vidence l?avantage d?une telle technique d?e?chantillonnage. Nous portons par la suite notre attention sur l?estimation de?centralise?e, ou? les observations sont de?sormais distribue?es sur un re?seau connexe. Nous e?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 a? estimer. Nous de?montrons la convergence de ces algorithmes avec des de?pendances explicites en les donne?es et la topologie du re?seau. Enfin, nous traitons de l?optimisation de?centralise?e de fonctions de?pendant de paires d?observations. De me?me que pour l?estimation, nos me?thodes sont base?es sur la concomitance de la propagation des observations et l?optimisation local du risque. Notre analyse the?orique souligne que ces me?thodes conservent une vitesse de convergence du me?me ordre que dans le cas centralise?. Les expe?riences nume?riques confirment l?inte?re?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 [56 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 : mardi 13 novembre 2018 - 16:02:51
Document(s) archivé(s) le : mardi 8 mai 2018 - 06:21:48

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

298

Téléchargements de fichiers

208