Étude du compromis précision statistique-temps ...
Document type :
Thèse
Title :
Étude du compromis précision statistique-temps de calcul
English title :
Study of the trade-off between statistic accuracy and computation time
Author(s) :
Brunin, Maxime [Auteur]
Laboratoire Paul Painlevé - UMR 8524 [LPP]
Inria Lille - Nord Europe
Ed, École [Auteur]
Spi, Régionale [Auteur]
Le 16 Janvier, Soutenue [Auteur]
Laboratoire Paul Painlevé - UMR 8524 [LPP]
Inria Lille - Nord Europe
Ed, École [Auteur]
Spi, Régionale [Auteur]
Le 16 Janvier, Soutenue [Auteur]
Thesis director(s) :
Christophe BIERNACKI
Alain Celisse
Alain Celisse
Defence date :
2018-01-16
Jury president :
Bertrand Michel, Professeur, Ecole Centrale de Nantes [Examinateur]
Guillem Rigaill
Guillem Rigaill
Jury member(s) :
Bertrand Michel, Professeur, Ecole Centrale de Nantes [Examinateur]
Guillem Rigaill
Guillem Rigaill
Accredited body :
Université de Lille 1 - Sciences et Technologies
Keyword(s) :
algorithme itératif
règle d'arrêt
détection de ruptures
régression linéaire
estimateur sous contrainte de temps
règle d'arrêt
détection de ruptures
régression linéaire
estimateur sous contrainte de temps
English keyword(s) :
iterative algorithm
stopping rule
change-point detection
linear regression
estimate under time constraint
stopping rule
change-point detection
linear regression
estimate under time constraint
HAL domain(s) :
Statistiques [stat]
French abstract :
Dans le contexte actuel, il est nécessaire de concevoir des algorithmes capables de traiter des données volumineuses en un minimum de temps de calcul. Par exemple, la programmation dynamique appliquée au problème de détection ...
Show more >Dans le contexte actuel, il est nécessaire de concevoir des algorithmes capables de traiter des données volumineuses en un minimum de temps de calcul. Par exemple, la programmation dynamique appliquée au problème de détection de ruptures ne permet pas de traiter rapidement des données ayant une taille d'échantillon supérieure à $10^{6}$. Les algorithmes itératifs fournissent une famille ordonnée d'estimateurs indexée par le nombre d'itérations. Dans cette thèse, nous avons étudié statistiquement cette famille d'estimateurs afin de sélectionner un estimateur ayant de bonnes performances statistiques et peu coûteux en temps de calcul. Pour cela, nous avons suivi l'approche utilisant les règles d'arrêt pour proposer un tel estimateur dans le cadre du problème de détection de ruptures dans la distribution et le problème de régression linéaire. Il est d'usage de faire un grand nombre d'itérations pour calculer un estimateur usuel. Une règle d'arrêt est l'itération à laquelle nous stoppons l'algorithme afin de limiter le phénomène de surapprentissage dont souffre ces estimateurs usuels. En stoppant l'algorithme plus tôt, les règles d'arrêt permettent aussi d'économiser du temps de calcul. Lorsque le budget de temps est limité, il se peut que nous n'ayons pas le temps d'itérer jusqu'à la règle d'arrêt. Dans ce contexte, nous avons étudié le choix optimal du nombre d'itérations et de la taille d'échantillon pour atteindre une précision statistique optimale. Des simulations ont mis en évidence un compromis entre le nombre d'itérations et la taille d'échantillon pour atteindre une précision statistique optimale à budget de temps limité.Show less >
Show more >Dans le contexte actuel, il est nécessaire de concevoir des algorithmes capables de traiter des données volumineuses en un minimum de temps de calcul. Par exemple, la programmation dynamique appliquée au problème de détection de ruptures ne permet pas de traiter rapidement des données ayant une taille d'échantillon supérieure à $10^{6}$. Les algorithmes itératifs fournissent une famille ordonnée d'estimateurs indexée par le nombre d'itérations. Dans cette thèse, nous avons étudié statistiquement cette famille d'estimateurs afin de sélectionner un estimateur ayant de bonnes performances statistiques et peu coûteux en temps de calcul. Pour cela, nous avons suivi l'approche utilisant les règles d'arrêt pour proposer un tel estimateur dans le cadre du problème de détection de ruptures dans la distribution et le problème de régression linéaire. Il est d'usage de faire un grand nombre d'itérations pour calculer un estimateur usuel. Une règle d'arrêt est l'itération à laquelle nous stoppons l'algorithme afin de limiter le phénomène de surapprentissage dont souffre ces estimateurs usuels. En stoppant l'algorithme plus tôt, les règles d'arrêt permettent aussi d'économiser du temps de calcul. Lorsque le budget de temps est limité, il se peut que nous n'ayons pas le temps d'itérer jusqu'à la règle d'arrêt. Dans ce contexte, nous avons étudié le choix optimal du nombre d'itérations et de la taille d'échantillon pour atteindre une précision statistique optimale. Des simulations ont mis en évidence un compromis entre le nombre d'itérations et la taille d'échantillon pour atteindre une précision statistique optimale à budget de temps limité.Show less >
English abstract : [en]
In the current context, we need to develop algorithms which are able to treat voluminous data with a short computation time. For instance, the dynamic programming applied to the change-point detection problem in the ...
Show more >In the current context, we need to develop algorithms which are able to treat voluminous data with a short computation time. For instance, the dynamic programming applied to the change-point detection problem in the distribution can not treat quickly data with a sample size greater than $10^{6}$. The iterative algorithms provide an ordered family of estimators indexed by the number of iterations. In this thesis, we have studied statistically this family of estimators in oder to select one of them with good statistics performance and a low computation cost. To this end, we have followed the approach using the stopping rules to suggest an estimator within the framework of the change-point detection problem in the distribution and the linear regression problem. We use to do a lot of iterations to compute an usual estimator. A stopping rule is the iteration to which we stop the algorithm in oder to limit overfitting whose some usual estimators suffer from. By stopping the algorithm earlier, the stopping rules enable also to save computation time. Under time constraint, we may have no time to iterate until the stopping rule. In this context, we have studied the optimal choice of the number of iterations and the sample size to reach an optimal accuracy. Simulations highlight the trade-off between the number of iterations and the sample size in order to reach an optimal accuracy under time constraint.Show less >
Show more >In the current context, we need to develop algorithms which are able to treat voluminous data with a short computation time. For instance, the dynamic programming applied to the change-point detection problem in the distribution can not treat quickly data with a sample size greater than $10^{6}$. The iterative algorithms provide an ordered family of estimators indexed by the number of iterations. In this thesis, we have studied statistically this family of estimators in oder to select one of them with good statistics performance and a low computation cost. To this end, we have followed the approach using the stopping rules to suggest an estimator within the framework of the change-point detection problem in the distribution and the linear regression problem. We use to do a lot of iterations to compute an usual estimator. A stopping rule is the iteration to which we stop the algorithm in oder to limit overfitting whose some usual estimators suffer from. By stopping the algorithm earlier, the stopping rules enable also to save computation time. Under time constraint, we may have no time to iterate until the stopping rule. In this context, we have studied the optimal choice of the number of iterations and the sample size to reach an optimal accuracy. Simulations highlight the trade-off between the number of iterations and the sample size in order to reach an optimal accuracy under time constraint.Show less >
Language :
Français
Collections :
Source :
Files
- document
- Open access
- Access the document
- 50376-2018-Brunin.pdf
- Open access
- Access the document