Dissertations / Theses on the topic 'Méthodes récursives'

Avec le développement rapide des technologies et l'acquisition de données de plus en plus massives, les méthodes capables de traiter les données de manière séquentielle (en ligne) sont devenues indispensables. Parmi ces méthodes, les algorithmes de gradient stochastique se sont imposés pour estimer le minimiseur d'une fonction exprimée comme l'espérance d'une fonction aléatoire. Bien qu'ils soient devenus incontournables, ces algorithmes rencontrent des difficultés lorsque le problème est mal conditionné. Dans cette thèse, nous nous intéressons sur les algorithmes stochastiques du second ordre, tels que ceux de type Newton, et leurs applications à diverses problématiques statistiques et d'optimisation. Après avoir établi des bases théoriques et exposé les motivations qui nous amènent à explorer les algorithmes de Newton stochastiques, nous développons les différentes contributions de cette thèse. La première contribution concerne l'étude et le développement d'algorithmes de Newton stochastiques pour la régression linéaire ridge et la régression logistique ridge. Ces algorithmes sont basés sur la formule de Riccati (Sherman-Morrison) pour estimer récursivement l'inverse de la Hessienne. Comme l'acquisition de données massives s'accompagne généralement d'une contamination de ces dernières, on s'intéresse, dans une deuxième contribution, à l'estimation en ligne de la médiane géométrique, qui est un indicateur robuste, i.e. peu sensible à la présence de données atypiques. Plus précisément, nous proposons un nouvel estimateur de Newton stochastique pour estimer la médiane géométrique. Dans les deux premières contributions, les estimateurs des inverses de Hessienne sont construits à l'aide de la formule de Riccati, mais cela n'est possible que pour certaines fonctions. Ainsi, notre troisième contribution introduit une nouvelle méthode de type Robbins-Monro pour l'estimation en ligne de l'inverse de la Hessienne, nous permettant ensuite de développer des algorithmes de Newton stochastiques dits universels. Enfin, notre dernière contribution se focalise sur des algorithmes de type Full Adagrad, où la difficulté réside dans le fait que l'on a un pas adaptatif basé sur la racine carré de l'inverse de la variance du gradient. On propose donc un algorithme de type Robbins-Monro pour estimer cette matrice, nous permettant ainsi de proposer une approche récursive pour Full AdaGrad et sa version streaming, avec des coûts de calcul réduits. Pour tous les nouveaux estimateurs que nous proposons, nous établissons leurs vitesses de convergence ainsi que leur efficacité asymptotique. De plus, nous illustrons l'efficacité de ces algorithmes à l'aide de simulations numériques et en les appliquant à des données réelles<br>With the rapid development of technologies and the acquisition of big data, methods capable of processing data sequentially (online) have become indispensable. Among these methods, stochastic gradient algorithms have been established for estimating the minimizer of a function expressed as the expectation of a random function. Although they have become essential, these algorithms encounter difficulties when the problem is ill-conditioned. In this thesis, we focus on second-order stochastic algorithms, such as those of the Newton type, and their applications to various statistical and optimization problems. After establishing theoretical foundations and exposing the motivations that lead us to explore stochastic Newton algorithms, we develop the various contributions of this thesis. The first contribution concerns the study and development of stochastic Newton algorithms for ridge linear regression and ridge logistic regression. These algorithms are based on the Riccati formula (Sherman-Morrison) to recursively estimate the inverse of the Hessian. As the acquisition of big data is generally accompanied by a contamination of the latter, in a second contribution, we focus on the online estimation of the geometric median, which is a robust indicator, i.e., not very sensitive to the presence of atypical data. More specifically, we propose a new stochastic Newton estimator to estimate the geometric median. In the first two contributions, the estimators of the Hessians' inverses are constructed using the Riccati formula, but this is only possible for certain functions. Thus, our third contribution introduces a new Robbins-Monro type method for online estimation of the Hessian's inverse, allowing us then to develop universal stochastic Newton algorithms. Finally, our last contribution focuses on Full Adagrad type algorithms, where the difficulty lies in the fact that there is an adaptive step based on the square root of the inverse of the gradient's covariance. We thus propose a Robbins-Monro type algorithm to estimate this matrix, allowing us to propose a recursive approach for Full AdaGrad and its streaming version, with reduced computational costs. For all the new estimators we propose, we establish their convergence rates as well as their asymptotic efficiency. Moreover, we illustrate the efficiency of these algorithms using numerical simulations and by applying them to real data

Cette thèse s'inscrit dans le cadre des travaux consacrés au développement des modèles sémantiques destinés aux langages de programmation concurrents. Une particularité de notre étude réside dans la considération explicite d'une récursivité au niveau des programmes parallèles. Pour ces programmes nous proposons une sémantique originale, dont nous étudions en détail les propriétés. Bien que le modèle proposé ne soit pas d'états finis, il est possible de le munir d'une structure de systèmes de transitions bien structurés au sens de Finkel ce qui établit la décidabilité de nombreux problèmes de vérification. Cette sémantique à la Plotkin permet de mieux comprendre le comportement des programmes récursifs-parallèles, d'analyser formellement certaines de leurs propriétés, de décrire la stratégie d'implémentation et d'énoncer en quel sens elle est correcte.

Le travail présenté dans ce mémoire concerne l'étude et le développement de méthodes d'identification récursive. Le chapitre 2 présente une synthèse des principaux algorithmes adaptatifs classiques fondés sur les moindres carrés. Les difficultés rencontrées lors de l'utilisation de telles approches dans certaines situations pratiques motivent la création de techniques récursives employant la forme d'état. Ce type de représentation a démontré son efficacité en identification grâce à l'émergence des méthodes hors ligne des sous-espaces. Ainsi, le chapitre 3 propose une description des algorithmes MOESP. Ces derniers sont en effet considérés comme le point de départ des techniques récursives des sous-espaces. Bien que robuste, la décomposition en valeurs singulières (DVS) employée par ces méthodes les rend inapplicables en ligne de par sa charge calculatoire. Le chapitre 4 est dédié à un état de l'art des algorithmes récursifs des sous-espaces énoncés jusqu'en 2003. Ces méthodes ont en commun d'adapter un critère particulier de traitement d'antennes conduisant à des techniques alternatives à la DVS. Une description de ces algorithmes dans un contexte unifié est plus précisément présentée. Ces techniques présentent néanmoins un certain nombre de limitations principalement liées à la fonction coût utilisée. Afin de remédier à ces inconvénients, nous développons, au sein du chapitre 5, de nouvelles méthodes récursives des sous-espaces. L'approche proposée consiste à adapter un opérateur particulier du traitement d'antennes jusqu'alors inexploité en identification : le propagateur. L'ajustement de ce dernier au problème d'identification récursive permet d'obtenir des critères quadratiques sans approximation et sans contrainte. Le problème des perturbations est traité en introduisant une variable instrumentale. L'étude expérimentale sur des données réelles et simulées est réalisée dans le chapitre 6.

Dans cette these, nous presentons la forme generale d'un filtre recursif oriente vitesse dont les parametres permettent de regler sa selectivite vis-a-vis d'une vitesse donnee. Une architecture de filtrage, composee d'un ensemble de filtres orientes pour un ensemble de vitesses donnees, est appliquee a une sequence d'images. L'analyse des reponses de chaque filtre nous permet de definir le champ des vitesses apparentes de la sequence. Dans un premier temps, en rapprochant les methodes d'estimation du mouvement qui exploitent le principe de correlation et la structure biologique du systeme visuel animal, nous decrivons la structure non recursive d'un filtre selectif. Nous validons de maniere theorique la propriete de selectivite du filtre en etudiant la transformee de fourier de son expression mathematique. Afin de reduire le nombre d'operations elementaires necessaires au calcul de la reponse d'un filtre, nous modifions la definition precedente afin d'aboutir a une formulation recursive. Nous implantons une architecture de filtrage fonde sur une structure particuliere des filtres recursifs. Nous precisons les demarches a suivre pour concevoir un banc de filtres qui nous permette de rechercher un ensemble fini de vitesses. Nous appliquons la methode sur plusieurs sequences d'images de synthese dont certains champs des vitesses apparentes presentent des discontinuites.