Letteratura scientifica selezionata sul tema "Méthode stochastique itérative"

Sequential Monte Carlo methods have been a major breakthrough in the field of numerical signal processing for stochastic dynamical state-space systems with partial and noisy observations. However, these methods still present certain weaknesses. One of the most fundamental is the degeneracy of the filter due to the impoverishment of the particles: the prediction step allows the particles to explore the state-space and can lead to the impoverishment of the particles if this exploration is poorly conducted or when it conflicts with the following observation that will be used in the evaluation of the likelihood of each particle. In this article, in order to improve this last step within the framework of the classic bootstrap particle filter, we propose a simple approximation of the one step fixed- lag smoother. At each time iteration, we propose to perform additional simulations during the prediction step in order to improve the likelihood of the selected particles. Les méthodes de Monte Carlo séquentielles ont constitué une percée majeure dans le domaine du traitement numérique du signal pour les systèmes dynamiques stochastiques à espace d'état avec observations partielles et bruitées. Cependant, ces méthodes présentent encore certaines faiblesses. L'une des plus fondamentales est la dégénérescence du filtre due à l'appauvrissement des particules : l'étape de prédiction permet aux particules d'explorer l'espace d'état et peut conduire à l'appauvrissement des particules si cette exploration est mal menée ou lorsqu'elle entre en conflit avec l'observation suivante qui sera utilisée dans l'évaluation de la vraisemblance de chaque particule. Dans cet article, afin d'améliorer cette dernière étape dans le cadre du filtre particulaire bootstrap classique, nous proposons une approximation simple du lisseur à retard fixe à un pas. A chaque itération temporelle, nous proposons d'effectuer des simulations supplémentaires pendant l'étape de prédiction afin d'améliorer la vraisemblance des particules sélectionnées.

L'augmentation considérable du volume de données ainsi que de la taille des échantillons complexifie la phase d'optimisation des algorithmes d'apprentissage, nécessitant la minimisation d'une fonction de perte. La descente de gradient stochastique (SGD) et ses variantes à réduction de variance (SAGA, SVRG, MISO) sont largement utilisées pour résoudre ces problèmes. En pratique, ces méthodes sont accélérées en calculant des gradients stochastiques sur un "mini-batch" : un petit groupe d'échantillons tiré aléatoirement. En effet, les récentes améliorations technologiques permettant la parallélisation de ces calculs ont généralisé l'utilisation des mini-batchs.Dans cette thèse, nous nous intéressons à l'étude d'algorithmes du gradient stochastique à variance réduite en essayant d'en trouver les hyperparamètres optimaux: taille du pas et du mini-batch. Cette étude nous permet de donner des résultats de convergence interpolant entre celui des méthodes stochastiques tirant un seul échantillon par itération et la descente de gradient dite "full-batch" utilisant l'ensemble des échantillons disponibles à chaque itération. Notre analyse se base sur la constante de régularité moyenne, outil fondamental de notre analyse, qui permet de mesurer la régularité de la fonction aléatoire dont le gradient est calculé.Nous étudions un autre type d'algorithmes d'optimisation : les méthodes "sketch-and-project". Ces dernières peuvent être utilisées lorsque le problème d'apprentissage est équivalent à la résolution d'un système linéaire. C'est par exemple le cas des moindres carrés ou de la régression ridge. Nous analysons ici des variantes de cette méthode qui utilisent différentes stratégies de momentum et d'accélération. L'efficacité de ces méthodes dépend de la stratégie de "sketching" utilisée pour compresser l'information du système à résoudre, et ce, à chaque itération. Enfin, nous montrons que ces méthodes peuvent aussi être étendues à d'autres problèmes d'analyse numérique. En effet, l'extension des méthodes de sketch-and-project aux méthodes de direction alternée implicite (ADI) permet de les appliquer en grande dimension lorsque les solveurs classiques s'avèrent trop lents
The considerable increase in the number of data and features complicates the learning phase requiring the minimization of a loss function. Stochastic gradient descent (SGD) and variance reduction variants (SAGA, SVRG, MISO) are widely used to solve this problem. In practice, these methods are accelerated by computing these stochastic gradients on a "mini-batch": a small group of samples randomly drawn.Indeed, recent technological improvements allowing the parallelization of these calculations have generalized the use of mini-batches.In this thesis, we are interested in the study of variants of stochastic gradient algorithms with reduced variance by trying to find the optimal hyperparameters: step and mini-batch size. Our study allows us to give convergence results interpolating between stochastic methods drawing a single sample per iteration and the so-called "full-batch" gradient descent using all samples at each iteration. Our analysis is based on the expected smoothness constant which allows to capture the regularity of the random function whose gradient is calculated.We study another class of optimization algorithms: the "sketch-and-project" methods. These methods can also be applied as soon as the learning problem boils down to solving a linear system. This is the case of ridge regression. We analyze here variants of this method that use different strategies of momentum and acceleration. These methods also depend on the sketching strategy used to compress the information of the system to be solved at each iteration. Finally, we show that these methods can also be extended to numerical analysis problems. Indeed, the extension of sketch-and-project methods to Alternating-Direction Implicit (ADI) methods allows to apply them to large-scale problems, when the so-called "direct" solvers are too slow

La methode cestac de vignes et la porte permet d'estimer la precision des resultats de tout algorithme numerique execute sur ordinateur. On developpe un modele stochastique de la propagation des erreurs d'arrondi pour etudier la robustesse de cette methode

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), ajoute à LSPI un concept venant de [lambda]-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LS[lambda]PI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lorincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008
This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), adds to LSPI an idea of [lambda]-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LS[lambda]PI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lorincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition

L'objectif de notre travail est l'application de la méthode des sentinelles pour résoudre deux problèmes inverses. Il s'agit d'estimer les paramètres de deux modèles donnés, à partir de mesures effectuées sur les processus. Le cadre étant non linéaire, l'estimation des paramètres s'effectue de manière itérative à l'aide de la méthode des sentinelles tangentes. Le premier problème abordé concerne l'environnement dont les paramètres à estimer sont les coordonnées de la trajectoire d'une source de pollution dans une rivière. Le phénomène de pollution est modélisé par un système d'équations aux dérivées partielles. Le second problème étudié, entre dans un cadre médical où le but est d'estimer les paramètres cinétiques dans une réaction enzymatique. Le modèle considéré est un système d'équations différentielles. Nous montrons tout d'abord l'existence et l'unicité de la solution de ce système, ensuite, nous étudions la stabilité de la solution à l'aide de la fonction de Lyapounov. Sous certaines hypothèses, nous montrons l'identifiabilité globale des paramètres basée sur l'algèbre différentielle et sur le développement de Taylor. Nous donnons aussi une étude détaillée de la sensibilité de l'observation par rapport aux paramètres du modèle. Afin de vérifier l'efficacité de la méthode des sentinelles, nous la testons sur des données bruitées. Cette méthode est déficiente dès que le bruit sur les mesures devient important. Le problème inverse est dans ce cas mal posé dans le sens où une perturbation de la donnée entraîne une forte variation de la solution. Parmi les techniques employées pour mieux conditionner le problème, la technique de régularisation itérative de Gauss-Newton reste inefficace. Nous proposons alors une nouvelle approche de régularisation, appelée "méthode de régularisation itérative de Tikhonov". Des tests menés sur différents types d'expériences en pharmacocinétique, montrent que cette approche est robuste par rapport au bruit de mesure et permet une bonne identification des paramètres
The aim of our work is the application of the sentinels method to salve two inverse problems. It concerns the parameters estimation of two given models using measures undertaken on the process. The framework being nonlinear, the estimation of the parameters is performed in an iterative manner by the tangent sentinels method. The first problem concerns the environment for which the parameters to be estimated are the coordinates of the pollution source trajectory in a river. The pollution phenomenon is governed by a PDE's system. The second problem studied, deals with the medical framework. The aim is to estimate the kinetic parameters in the enzymatic reaction. The model considered here is a differential equations system. First, we show the existence and the uniqueness of the system solution. Then, we study the stability of the solution using the Lyapounov function. Assuming certain hypotheses, the global identifiability of parameters based on the differential algebra and Taylor development is shown. We also give a detailed study of the observation sensitivity with respect to the model parameters. Ln order to check the efficiency of this method, some tests were clone on noised data. This method becomes deficient as the noise on measures becomes important. Ln this case the inverse problem is ill-posed because a perturbation in the data will implies an important change in the solution. Among the techniques employed to improve the conditionement of the problem, the Gauss-Newton iterative regularization technique remains inefficient. Therefore, we propose a new approach of regularization, called "iterative regularized Tichonov method". Some tests were conducted on different types of experiences in pharmacokinetic. They show that this approach is robust with respect to noise measures and allows good parameters identification

Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), ajoute à LSPI un concept venant de λ-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LSλPI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lőrincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008.

Cette thèse propose des techniques numériques visant à optimiser les méthodes itératives d'évaluation de performances de modèles Markoviens. Ces techniques s'appliquent à des modèles où la matrice de transition de la chaîne de Markov associée est stockée sous un format tensoriel. Particulièrement, le formalisme des réseaux d'automates stochastiques est employé pour la description des modèles. L'évaluation de performances cherchée est la détermination de l'état stationnaire de la chaîne de Markov (\emph(résolution)). De ce fait, les propriétés de l'algèbre tensorielle généralisée sont proposées et démontrées de façon à établir la base nécessaire aux algorithmes de résolution introduits. Le principal apport de cette thèse réside dans l'efficacité des ces algorithmes, qui est obtenue avec l'accélération des méthodes itératives. Ceci est fait à deux niveaux: la réduction du coût de chaque itération; et la réduction du nombre d'itérations nécessaire à la convergence. La multiplication d'un vecteur par une matrice sous format tensoriel (produit vecteur-descripteur) est l'opération de base des itérations. L'efficacité de cette opération est le premier objectif à atteindre. Le deuxième objectif est l'implémentation des méthodes de la puissance, d'Arnoldi et GMRES dans ses versions standards et pré-conditionnées de façon a minimiser le nombre d'itérations sans trop augmenter le coût de chaque itération. La totalité des concepts introduits est alors utilisée dans le logiciel PEPS 2.0. Plusieurs exemples pratiques de modèles en réseaux d'automates stochastiques ont été mesurés sur PEPS 2.0 pour illustrer les résultats de cette thèse.