To see the other types of publications on this topic, follow the link: Algorithme du gradient stochastique.
Dissertations / Theses on the topic 'Algorithme du gradient stochastique'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Algorithme du gradient stochastique.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Mercier, Quentin. "Optimisation multicritère sous incertitudes : un algorithme de descente stochastique." Thesis, Université Côte d'Azur (ComUE), 2018. http://www.theses.fr/2018AZUR4076/document.
Full textAbstract:
Cette thèse s’intéresse à l’optimisation multiobjectif sans contrainte lorsque les objectifs sont exprimés comme des espérances de fonctions aléatoires. L’aléa est modélisé par l’intermédiaire de variables aléatoires et on considère qu’il n’impacte pas les variables d’optimisation du problème. La thèse consiste à proposer un algorithme de descente qui permet l’obtention des solutions de Pareto du problème d’optimisation ainsi écrit. En utilisant des résultats d’analyse convexe, il est possible de construire un vecteur de descente commun à l’ensemble des objectifs du problème d’optimisation pour un tirage des variables aléatoires donné. Une suite itérative consistant à descendre dans la direction du vecteur de descente commun calculé au point courant et pour un tirage aléatoire unique et indépendant des variables aléatoires est alors construite. De cette manière, l’estimation coûteuse des espérances à chaque étape du processus d’optimisation n’est pas nécessaire. Il est possible de prouver les convergences en norme et presque sûre de cette suite vers les solutions de Pareto du problème d’optimisation en espérance et d’obtenir un résultat de vitesse de convergence lorsque la suite de pas de descente est bien choisie. Après avoir proposé diverses méthodes numériques d’amélioration de l’algorithme, un ensemble d’essais numériques est mené et les résultats de l’algorithme proposé sont comparés à ceux obtenus par deux autres algorithmes classiques de la littérature. Les résultats obtenus sont comparés par l’intermédiaire de mesures adaptées à l’optimisation multiobjectif et sont analysés par le biais de profils de performance. Des méthodes sont alors proposées pour prendre en compte deux types de contrainte et sont illustrées sur des problèmes d’optimisation de structures mécaniques. Une première méthode consiste à pénaliser les objectifs par l’intermédiaire de fonctions de pénalisation exacte lorsque la contrainte est décrite par une fonction déterministe. Pour les contraintes probabilistes, on propose de remplacer les contraintes par des objectifs supplémentaires, ces contraintes probabilistes étant alors reformulées comme des espérances de fonctions indicatrices, le problème étant résolu à l’aide de l’algorithme proposé dans la thèse sans avoir à estimer les probabilités des contraintes à chaque itérationThis thesis deals with unconstrained multiobjective optimization when the objectives are written as expectations of random functions. The randomness is modelled through random variables and we consider that this does not impact the problem optimization variables. A descent algorithm is proposed which gives the Pareto solutions without having to estimate the expectancies. Using convex analysis results, it is possible to construct a common descent vector that is a descent vector for all the objectives simultaneously, for a given draw of the random variables. An iterative sequence is then built and consists in descending following this common descent vector calculated at the current point and for a single independent draw of the random variables. This construction avoids the costly estimation of the expectancies at each step of the algorithm. It is then possible to prove the mean square and almost sure convergence of the sequence towards Pareto solutions of the problem and at the same time, it is possible to obtain a speed rate result when the step size sequence is well chosen. After having proposed some numerical enhancements of the algorithm, it is tested on multiple test cases against two classical algorithms of the literature. The results for the three algorithms are then compared using two measures that have been devised for multiobjective optimization and analysed through performance profiles. Methods are then proposed to handle two types of constraint and are illustrated on mechanical structure optimization problems. The first method consists in penalising the objective functions using exact penalty functions when the constraint is deterministic. When the constraint is expressed as a probability, the constraint is replaced by an additional objective. The probability is then reformulated as an expectation of an indicator function and this new problem is solved using the algorithm proposed in the thesis without having to estimate the probability during the optimization process
2
Culioli, Jean-Christophe. "Algorithmes de decomposition/coordination en optimisation stochastique." Paris, ENMP, 1987. http://www.theses.fr/1987ENMP0059.
Full textAbstract:
Les systemes consideres, souvent complexes a modeliser et/ou optimiser peuvent etre constitues de sous-systemes heterogenes pour lesquels une technique globale de resolution n'est pas necessairement appropriee ou possible, meme s'ils sont equivalents et peu nombreux
3
Perrier, Alexis. "Développement et analyse de performance d'algorithmes de type gradient stochastique /." Paris : Ecole nationale supérieure des télécommunications, 1995. http://catalogue.bnf.fr/ark:/12148/cb35802687g.
Full text
4
Strugarek, Cyrille. "Approches variationnelles et autres contributions en optimisation stochastique." Phd thesis, Ecole des Ponts ParisTech, 2006. http://pastel.archives-ouvertes.fr/pastel-00001848.
Full textAbstract:
Cette thèse s'attache à l'étude des problèmes d'optimisation stochastique, en les abordant sous divers angles. Le premier chapitre donne un panorama des problèmes d'optimisation stochastique. Le deuxième chapitre montre qu'en dimension un, seuls les systèmes à espace d'état à dynamique et observation linéaire sont sans effet dual en boucle ouverte. Le troisième chapitre s'attache à montrer la nécessité de tenir compte de la structure d'information dans la discrétisation et les résultats de stabilité pour les problèmes à plusieurs pas de temps. Le quatrième chapitre propose une nouvelle famille d'algorithmes stochastiques permettant de rechercher les commandes optimales fonctionnellement sans aucune discrétisation préalable de l'aléa, et avec une garantie asymptotique d'optimalité. Le cinquième chapitre étudie les possibilités de décomposition et d'agrégation pour les problèmes stochastiques de grande taille.
5
Es-Sadek, Mohamed Zeriab. "Contribution à l'optimisation globale : approche déterministe et stochastique et application." Thesis, Rouen, INSA, 2009. http://www.theses.fr/2009ISAM0010/document.
Full textAbstract:
Dans les situations convexes, le problème d'optimisation globale peut être abordé par un ensemble de méthodes classiques, telles, par exemple, celles basées sur le gradient, qui ont montré leur efficacité en ce domaine. Lorsque la situation n'est pas convexe, ces méthodes peuvent être mises en défaut et ne pas trouver un optimum global. La contribution de cette thèse est une méthodologie pour la détermination de l'optimum global d'une fonction non convexe, en utilisant des algorithmes hybrides basés sur un couplage entre des algorithmes stochastiques issus de familles connues, telles, par exemple, celle des algorithmes génétiques ou celle du recuit simulé et des algorithmes déterministes perturbés aléatoirement de façon convenable. D'une part, les familles d'algorithmes stochastiques considérées ont fait preuve d'efficacité pour certaines classes de problèmes et, d'autre part, l'adjonction de perturbations aléatoires permet de construire des méthodes qui sont en théorie convergents vers un optimum global. En pratique, chacune de ces approches a ses limitations et insuffisantes, de manière que le couplage envisagé dans cette thèse est une alternative susceptible d'augmenter l'efficacité numérique. Nous examinons dans cette thèse quelques unes de ces possibilités de couplage. Pour établir leur efficacité, nous les appliquons à des situations test classiques et à un problème de nature stochastique du domaine des transportsThis thesis concerns the global optimization of a non convex function under non linear restrictions, this problem cannot be solved using the classic deterministic methods like the projected gradient algorithm and the sqp method because they can solve only the convex problems. The stochastic algorithms like the genetic algorithm and the simulated annealing algorithm are also inefficients for solving this type of problems. For solving this kind of problems, we try to perturb stocasicly the deterministic classic method and to combine this perturbation with genetic algorithm and the simulated annealing. So we do the combination between the perturbed projected gradient and the genetic algorithm, the perturbed sqp method and the genetic algorithm, the perturbed projected gradient and the simulated annealing, the Piyavskii algorithm and the genetic algorithm. We applicate the coupled algorithms to different classic examples for concretited the thesis. For illustration in the real life, we applicate the coupled perturbed projected gradient end the genetic algorithm to logistic problem eventuelly transport. In this view, we sold the efficient practices
6
Dedieu, Hervé. "Etude des effets de quantification dans les algorithmes adaptatifs de type gradient stochastique." Grenoble 2 : ANRT, 1988. http://catalogue.bnf.fr/ark:/12148/cb37613018c.
Full text
7
Nguyen, Thanh Huy. "Heavy-tailed nature of stochastic gradient descent in deep learning : theoretical and empirical analysis." Electronic Thesis or Diss., Institut polytechnique de Paris, 2021. http://www.theses.fr/2021IPPAT003.
Full textAbstract:
Dans cette thèse, nous nous intéressons à l'algorithme du gradient stochastique (SGD). Plus précisément, nous effectuons une analyse théorique et empirique du comportement du bruit de gradient stochastique (GN), qui est défini comme la différence entre le gradient réel et le gradient stochastique, dans les réseaux de neurones profonds. Sur la base de ces résultats, nous apportons une perspective alternative aux approches existantes pour étudier SGD. Le GN dans SGD est souvent considéré comme gaussien pour des raisons mathématiques. Cette hypothèse permet d'étudier SGD comme une équation différentielle stochastique (SDE) pilotée par un mouvement brownien. Nous soutenons que l'hypothèse de la gaussianité pourrait ne pas tenir dans les contextes d'apprentissage profond et donc rendre inappropriées les analyses basées sur le mouvement brownien. Inspiré de phénomènes naturels non gaussiens, nous considérons le GN dans un contexte plus général qui suggère que le GN est mieux approché par un vecteur aléatoire à "queue lourde" alpha-stable. En conséquence, nous proposons d'analyser SGD comme une discrétisation d'une SDE pilotée par un mouvement Lévy. Premièrement, pour justifier l'hypothèse alpha-stable, nous menons des expériences sur des scénarios communs d'apprentissage en profondeur et montrons que dans tous les contextes, le GN est hautement non gaussien et présente des queues lourdes. Deuxièmement, sous l'hypothèse du GN à queue lourde, nous fournissons une analyse non asymptotique pour que la dynamique en temps discret SGD converge vers le minimum global en termes de sous-optimalité. Enfin, nous étudions la nature de métastabilité de la SDE pilotée par le mouvement de Lévy qui peut ensuite être exploitée pour clarifier le comportement de SGD, notamment en termes de "préférence de larges minima". Plus précisément, nous fournissons une analyse théorique formelle où nous dérivons des conditions explicites pour la taille de pas de sorte que le comportement de métastabilité de SGD, considéré comme une SDE en temps discret, est similaire à sa limite de temps continu. Nos résultats ouvrent une perspective différente et éclairent davantage l'idée selon laquelle SGD préfère les minima largesIn this thesis, we are concerned with the Stochastic Gradient Descent (SGD) algorithm. Specifically, we perform theoretical and empirical analysis of the behavior of the stochastic gradient noise (GN), which is defined as the difference between the true gradient and the stochastic gradient, in deep neural networks. Based on these results, we bring an alternative perspective to the existing approaches for investigating SGD. The GN in SGD is often considered to be Gaussian for mathematical convenience. This assumption enables SGD to be studied as a stochastic differential equation (SDE) driven by a Brownian motion. We argue that the Gaussianity assumption might fail to hold in deep learning settings and hence render the Brownian motion-based analyses inappropriate. Inspired by non-Gaussian natural phenomena, we consider the GN in a more general context that suggests that the GN is better approximated by a "heavy-tailed" alpha-stable random vector. Accordingly, we propose to analyze SGD as a discretization of an SDE driven by a Lévy motion. Firstly, to justify the alpha-stable assumption, we conduct experiments on common deep learning scenarios and show that in all settings, the GN is highly non-Gaussian and exhibits heavy-tails. Secondly, under the heavy-tailed GN assumption, we provide a non-asymptotic analysis for the discrete-time dynamics SGD to converge to the global minimum in terms of suboptimality. Finally, we investigate the metastability nature of the SDE driven by Lévy motion that can then be exploited for clarifying the behavior of SGD, especially in terms of `preferring wide minima'. More precisely, we provide formal theoretical analysis where we derive explicit conditions for the step-size such that the metastability behavior of SGD, viewed as a discrete-time SDE, is similar to its continuous-time limit. We show that the behaviors of the two systems are indeed similar for small step-sizes and we describe how the error depends on the algorithm and problem parameters. We illustrate our metastability results with simulations on a synthetic model and neural networks. Our results open up a different perspective and shed more light on the view that SGD prefers wide minima
8
Letournel, Marc. "Approches duales dans la résolution de problèmes stochastiques." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00938751.
Full textAbstract:
Le travail général de cette thèse consiste à étendre les outils analytiques et algébriques usuellement employés dans la résolution de problèmes combinatoires déterministes à un cadre combinatoire stochastique. Deux cadres distincts sont étudiés : les problèmes combinatoires stochastiques discrets et les problèmes stochastiques continus. Le cadre discret est abordé à travers le problème de la forêt couvrante de poids maximal dans une formulation Two-Stage à multi-scénarios. La version déterministe très connue de ce problème établit des liens entre la fonction de rang dans un matroïde et la formulation duale, via l'algorithme glouton. La formulation stochastique discrète du problème de la forêt maximale couvrante est transformée en un problème déterministe équivalent, mais du fait de la multiplicité des scénarios, le dual associé est en quelque sorte incomplet. Le travail réalisé ici consiste à comprendre en quelles circonstances la formulation duale atteint néanmoins un minimum égal au problème primal intégral. D'ordinaire, une approche combinatoire classique des problèmes de graphes pondérés consiste à rechercher des configurations particulières au sein des graphes, comme les circuits, et à explorer d'éventuelles recombinaisons. Pour donner une illustration simple, si on change d'une manière infinitésimale les valeurs de poids des arêtes d'un graphe, il est possible que la forêt couvrante de poids maximal se réorganise complètement. Ceci est vu comme un obstacle dans une approche purement combinatoire. Pourtant, certaines grandeurs analytiques vont varier de manière continue en fonction de ces variations infinitésimales, comme la somme des poids des arêtes choisies. Nous introduisons des fonctions qui rendent compte de ces variations continues, et nous examinons dans quels cas les formulations duales atteignent la même valeur que les formulations primales intégrales. Nous proposons une méthode d'approximation dans le cas contraire et nous statuons sur la NP complétude de ce type de problème.Les problèmes stochastiques continus sont abordés via le problème de sac à dos avec contrainte stochastique. La formulation est de type ''chance constraint'', et la dualisation par variable lagrangienne est adaptée à une situation où la probabilité de respecter la contrainte doit rester proche de $1$. Le modèle étudié est celui d'un sac à dos où les objets ont une valeur et un poids déterminés par des distributions normales. Dans notre approche, nous nous attachons à appliquer des méthodes de gradient directement sur la formulation en espérance de la fonction objectif et de la contrainte. Nous délaissons donc une possible reformulation classique du problème sous forme géométrique pour détailler les conditions de convergence de la méthode du gradient stochastique. Cette partie est illustrée par des tests numériques de comparaison avec la méthode SOCP sur des instances combinatoires avec méthode de Branch and Bound, et sur des instances relaxées.
9
Doan, Thanh-Nghi. "Large scale support vector machines algorithms for visual classification." Thesis, Rennes 1, 2013. http://www.theses.fr/2013REN1S083/document.
Full textAbstract:
Nous présentons deux contributions majeures : 1) une combinaison de plusieurs descripteurs d’images pour la classification à grande échelle, 2) des algorithmes parallèles de SVM pour la classification d’images à grande échelle. Nous proposons aussi un algorithme incrémental et parallèle de classification lorsque les données ne peuvent plus tenir en mémoire viveWe have proposed a novel method of combination multiple of different features for image classification. For large scale learning classifiers, we have developed the parallel versions of both state-of-the-art linear and nonlinear SVMs. We have also proposed a novel algorithm to extend stochastic gradient descent SVM for large scale learning. A class of large scale incremental SVM classifiers has been developed in order to perform classification tasks on large datasets with very large number of classes and training data can not fit into memory
10
Younes, Laurent. "Problèmes d'estimation paramétrique pour des champs de Gibbs Markoviens : applications au traitement d'images." Paris 11, 1988. http://www.theses.fr/1988PA112269.
Full textAbstract:
Nous nous intéressons à l’estimation paramétrique par maximum de vraisemblance pour des champs de Gibbs markoviens. Apres une introduction composée d'une part d'une discussion heuristique de l'analyse statistique des images aboutissant à une modélisation par champs aléatoires. Et d'autre part d'un rappel de différentes techniques d'estimation paramétrique existant dans la littérature, nous consacrons un chapitre au rappel de quelques résultats reliés aux champs de Gibbs, et à leur étude statistique: nous introduisons la notion de potentiel, ainsi que les définitions qui s’y rattachent, puis nous rappelons des conditions d'existence et d'unicité de champs de Gibbs associés à un potentiel. Nous présentons ensuite te un algorithme de gradient stochastique permettant la maximisation de la vraisemblance. Il utilise l'échantillonneur de Gibbs qui est une méthode itérative de simulation de champs markoviens. Des propriétés relatives à l'ergodicité de cet échantillonneur sont alors données. En fin de chapitre, nous rappelons des résultats de Métivier et Priouret sur les algorithmes stochastiques du type de celui que nous utilisons, qui permettent de mesurer la (tendance à la) convergence de telles procédures. Le chapitre 4 est consacré à l'étude plus précise de la convergence de l’algorithme. A réseau fixé, tout d'abord nous étudions le cas de modèle exponentiel, et nous démontrons un résultat de convergence presque sûre de l'algorithme. Nous étudions ensuite les modèles plus généraux en nous intéressant en particulier aux problèmes d’estimation basée sur de observations imparfaites (ou bruitées). Dans le chapitre 5, nous étudions le comportement asymptotique de l'estimateur de maximum de vraisemblance proprement dit, prouvant un résultat de consistance et de normalité asyptotique. Enfin, nous donnons quelques remarques pratiques sur l'algorithme d'estimation, suivies de résultats expérimentaux, composés d'une part de simulations et d'autre part de traitements appliqués à de vraies imagesWe study parameter estimation by maximum of likelihood for Gibbs Markov Random Fields. We begin by a heuristic discussion about statistical analysis of pictures, to obtain a modelization by random fields, and by a summary of various parameter estimation technics that exist. Then, we recall some results related to Gibbs Fields, and to their statistical analysis we introduce the notion of potential, and recall existence and uniqueness conditions for an associated Gibbs field. Ln the next chapter, we present a stochastic gradient algorithm in order to maximize the Likelihood. It uses the Gibbs sampler, which is an iterative method for Markov field simulation. We give properties related to the ergodicity of this sampler. Finaly we recall some results of Métivier and Priouret about stochastic gradient algorithms, such as the one we use that allow measurement of the (trend for) convergence for this kind of procedures. Ln chapter 4, we make a precise study of the convergence of the algorithm. First, with fixed lattice, we deal with the case of exponential models and show almost sure convergence of the algorithm. We study then more general models, and especialy problems related to imperfect (or noisy) observa tions. Ln chapter 5, we study the asymptotic behaviour of the maximum of likelihood estimator, and prove consistency, and asymptotic normality. Eventualy we give some practical remarks on the estimation algorithm, followed by some experiments
11
Samé, Allou Badara. "Modèles de mélange et classification de données acoustiques en temps réel." Compiègne, 2004. http://www.theses.fr/2004COMP1540.
Full textAbstract:
Cette thèse, menée en collaboration avec le Centre Technique des Industries Mécaniques (CETIM), s'inscrit dans le cadre de la classification automatique pour le contrôle en temps réel par émission acoustique des équipements sous pression (citernes GPL. . . ). Le travail effectué vise à améliorer un logiciel temps réel (LOTERE) d'aide à la décision dans le contrôle des équipements sous pression, jugé lent quand le nombre des émissions acoustiques à traiter devient très grand. Deux approches classificatoires basées sur le modèle de mélange de lois, capables de prendre en compte les contraintes de temps d'exécution, ont été développées. La première approche consiste à classifier les 'bins' résultant de la conversion des données initiales en un histogramme et la seconde consiste à classifier les données de façon séquentielle par mise à jour récurrente de la classification. Une étude expérimentale sur des données simulées et des données réelles a permis de mettre en évidence l'efficacité des approches proposéesThe motivation for this Phd Thesis was a real-time flaw diagnosis application for pressurized containers using acoustic emissions. It has been carried out in collaboration with the Centre Technique des Industries Mécaniques (CETIM). The aim was to improve LOTERE, a real-time computer-aided-decision software, which has been found to be too slow when the number of acoustic emissions becomes large. Two mixture model-based clustering approaches, taking into account time constraints, have been proposed. The first one consists in clustering 'bins' resulting from the conversion of original observations into an histogram. The second one is an on-line approach updating recursively the classification. An experimental study using both simulated and real data has shown that the proposed methods are very efficient
12
Godichon-Baggioni, Antoine. "Algorithmes stochastiques pour la statistique robuste en grande dimension." Thesis, Dijon, 2016. http://www.theses.fr/2016DIJOS053/document.
Full textAbstract:
Cette thèse porte sur l'étude d'algorithmes stochastiques en grande dimension ainsi qu'à leur application en statistique robuste. Dans la suite, l'expression grande dimension pourra aussi bien signifier que la taille des échantillons étudiés est grande ou encore que les variables considérées sont à valeurs dans des espaces de grande dimension (pas nécessairement finie). Afin d'analyser ce type de données, il peut être avantageux de considérer des algorithmes qui soient rapides, qui ne nécessitent pas de stocker toutes les données, et qui permettent de mettre à jour facilement les estimations. Dans de grandes masses de données en grande dimension, la détection automatique de points atypiques est souvent délicate. Cependant, ces points, même s'ils sont peu nombreux, peuvent fortement perturber des indicateurs simples tels que la moyenne ou la covariance. On va se concentrer sur des estimateurs robustes, qui ne sont pas trop sensibles aux données atypiques. Dans une première partie, on s'intéresse à l'estimation récursive de la médiane géométrique, un indicateur de position robuste, et qui peut donc être préférée à la moyenne lorsqu'une partie des données étudiées est contaminée. Pour cela, on introduit un algorithme de Robbins-Monro ainsi que sa version moyennée, avant de construire des boules de confiance non asymptotiques et d'exhiber leurs vitesses de convergence $L^{p}$ et presque sûre.La deuxième partie traite de l'estimation de la "Median Covariation Matrix" (MCM), qui est un indicateur de dispersion robuste lié à la médiane, et qui, si la variable étudiée suit une loi symétrique, a les mêmes sous-espaces propres que la matrice de variance-covariance. Ces dernières propriétés rendent l'étude de la MCM particulièrement intéressante pour l'Analyse en Composantes Principales Robuste. On va donc introduire un algorithme itératif qui permet d'estimer simultanément la médiane géométrique et la MCM ainsi que les $q$ principaux vecteurs propres de cette dernière. On donne, dans un premier temps, la forte consistance des estimateurs de la MCM avant d'exhiber les vitesses de convergence en moyenne quadratique.Dans une troisième partie, en s'inspirant du travail effectué sur les estimateurs de la médiane et de la "Median Covariation Matrix", on exhibe les vitesses de convergence presque sûre et $L^{p}$ des algorithmes de gradient stochastiques et de leur version moyennée dans des espaces de Hilbert, avec des hypothèses moins restrictives que celles présentes dans la littérature. On présente alors deux applications en statistique robuste: estimation de quantiles géométriques et régression logistique robuste.Dans la dernière partie, on cherche à ajuster une sphère sur un nuage de points répartis autour d'une sphère complète où tronquée. Plus précisément, on considère une variable aléatoire ayant une distribution sphérique tronquée, et on cherche à estimer son centre ainsi que son rayon. Pour ce faire, on introduit un algorithme de gradient stochastique projeté et son moyenné. Sous des hypothèses raisonnables, on établit leurs vitesses de convergence en moyenne quadratique ainsi que la normalité asymptotique de l'algorithme moyennéThis thesis focus on stochastic algorithms in high dimension as well as their application in robust statistics. In what follows, the expression high dimension may be used when the the size of the studied sample is large or when the variables we consider take values in high dimensional spaces (not necessarily finite). In order to analyze these kind of data, it can be interesting to consider algorithms which are fast, which do not need to store all the data, and which allow to update easily the estimates. In large sample of high dimensional data, outliers detection is often complicated. Nevertheless, these outliers, even if they are not many, can strongly disturb simple indicators like the mean and the covariance. We will focus on robust estimates, which are not too much sensitive to outliers.In a first part, we are interested in the recursive estimation of the geometric median, which is a robust indicator of location which can so be preferred to the mean when a part of the studied data is contaminated. For this purpose, we introduce a Robbins-Monro algorithm as well as its averaged version, before building non asymptotic confidence balls for these estimates, and exhibiting their $L^{p}$ and almost sure rates of convergence.In a second part, we focus on the estimation of the Median Covariation Matrix (MCM), which is a robust dispersion indicator linked to the geometric median. Furthermore, if the studied variable has a symmetric law, this indicator has the same eigenvectors as the covariance matrix. This last property represent a real interest to study the MCM, especially for Robust Principal Component Analysis. We so introduce a recursive algorithm which enables us to estimate simultaneously the geometric median, the MCM, and its $q$ main eigenvectors. We give, in a first time, the strong consistency of the estimators of the MCM, before exhibiting their rates of convergence in quadratic mean.In a third part, in the light of the work on the estimates of the median and of the Median Covariation Matrix, we exhibit the almost sure and $L^{p}$ rates of convergence of averaged stochastic gradient algorithms in Hilbert spaces, with less restrictive assumptions than in the literature. Then, two applications in robust statistics are given: estimation of the geometric quantiles and application in robust logistic regression.In the last part, we aim to fit a sphere on a noisy points cloud spread around a complete or truncated sphere. More precisely, we consider a random variable with a truncated spherical distribution, and we want to estimate its center as well as its radius. In this aim, we introduce a projected stochastic gradient algorithm and its averaged version. We establish the strong consistency of these estimators as well as their rates of convergence in quadratic mean. Finally, the asymptotic normality of the averaged algorithm is given
13
Mignacco, Francesca. "Statistical physics insights on the dynamics and generalisation of artificial neural networks." Thesis, université Paris-Saclay, 2022. http://www.theses.fr/2022UPASP074.
Full textAbstract:
L'apprentissage machine est une technologie désormais omniprésente dans notre quotidien. Toutefois, ce domaine reste encore largement empirique et ses enjeux scientifiques manquent d'une compréhension théorique profonde. Cette thèse se penche vers la découverte des mécanismes sous-tendant l'apprentissage dans les réseaux de neurones artificiels à travers le prisme de la physique statistique. Dans une première partie, nous nous intéressons aux propriétés statiques des problèmes d'apprentissage, que nous introduisons au chapitre 1.1. Dans le chapitre 1.2, nous considérons la classification d'un mélange binaire de nuages gaussiens et nous dérivons des expressions rigoureuses pour les erreurs en dimension infinie, que nous appliquons pour éclairer le rôle des différents paramètres du problème. Dans le chapitre 1.3, nous montrons comment étendre le modèle de perceptron enseignant-étudiant pour considérer la classification multi-classes, en dérivant des expressions asymptotiques pour la performance optimale et la performance de la minimisation du risque empirique régularisé. Dans la deuxième partie, nous nous concentrons sur la dynamique de l'apprentissage, que nous introduisons dans le chapitre 2.1. Dans le chapitre 2.2, nous montrons comment décrire analytiquement la dynamique de l'algorithme du gradient stochastique à échantillonage mini-lots (mini-batch SGD) dans la classification binaire de mélanges gaussiens, en utilisant la théorie dynamique du champ moyen. Le chapitre 2.3 présente une analyse du bruit effectif introduit par SGD. Dans le chapitre 2.4, nous considérons le problème de la récupération des signes comme exemple d'optimisation hautement non convexe et montrons que la stochasticité est cruciale pour la généralisation. La conclusion de la thèse est présentée dans la troisième partieMachine learning technologies have become ubiquitous in our daily lives. However, this field still remains largely empirical and its scientific stakes lack a deep theoretical understanding.This thesis explores the mechanisms underlying learning in artificial neural networks through the prism of statistical physics. In the first part, we focus on the static properties of learning problems, that we introduce in Chapter 1.1. In Chapter 1.2, we consider the prototype classification of a binary mixture of Gaussian clusters and we derive rigorous closed-form expressions for the errors in the infinite-dimensional regime, that we apply to shed light on the role of different problem parameters. In Chapter 1.3, we show how to extend the teacher-student perceptron model to encompass multi-class classification deriving asymptotic expressions for the optimal performance and the performance of regularised empirical risk minimisation. In the second part, we turn our focus to the dynamics of learning, that we introduce in Chapter 2.1. In Chapter 2.2, we show how to track analytically the training dynamics of multi-pass stochastic gradient descent (SGD) via dynamical mean-field theory for generic non convex loss functions and Gaussian mixture data. Chapter 2.3 presents a late-time analysis of the effective noise introduced by SGD in the underparametrised and overparametrised regimes. In Chapter 2.4, we take the sign retrieval problem as a benchmark highly non-convex optimisation problem and show that stochasticity is crucial to achieve perfect generalisation. The third part of the thesis contains the conclusions and some future perspectives
14
Flammarion, Nicolas. "Stochastic approximation and least-squares regression, with applications to machine learning." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLEE056/document.
Full textAbstract:
De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficaceMany problems in machine learning are naturally cast as the minimization of a smooth function defined on a Euclidean space. For supervised learning, this includes least-squares regression and logistic regression. While small problems are efficiently solved by classical optimization algorithms, large-scale problems are typically solved with first-order techniques based on gradient descent. In this manuscript, we consider the particular case of the quadratic loss. In the first part, we are interestedin its minimization when its gradients are only accessible through a stochastic oracle. In the second part, we consider two applications of the quadratic loss in machine learning: clustering and estimation with shape constraints. In the first main contribution, we provided a unified framework for optimizing non-strongly convex quadratic functions, which encompasses accelerated gradient descent and averaged gradient descent. This new framework suggests an alternative algorithm that exhibits the positive behavior of both averaging and acceleration. The second main contribution aims at obtaining the optimal prediction error rates for least-squares regression, both in terms of dependence on the noise of the problem and of forgetting the initial conditions. Our new algorithm rests upon averaged accelerated gradient descent. The third main contribution deals with minimization of composite objective functions composed of the expectation of quadratic functions and a convex function. Weextend earlier results on least-squares regression to any regularizer and any geometry represented by a Bregman divergence. As a fourth contribution, we consider the the discriminative clustering framework. We propose its first theoretical analysis, a novel sparse extension, a natural extension for the multi-label scenario and an efficient iterative algorithm with better running-time complexity than existing methods. The fifth main contribution deals with the seriation problem. We propose a statistical approach to this problem where the matrix is observed with noise and study the corresponding minimax rate of estimation. We also suggest a computationally efficient estimator whose performance is studied both theoretically and experimentally
15
Dedieu, Hervé. "Étude des effets de quantification dans les algorithmes adaptatifs de type gradiant stochastique." Toulouse, INPT, 1988. http://www.theses.fr/1988INPT081H.
Full textAbstract:
Le travail presente a ete divise en quatre parties: la premiere partie rappelle les principales applications des algorithmes de type gradient stochastique en traitement du signal. La deuxieme partie est consacree au calcul du transfert des effets de quantifications sur les variables intermediaires et sur les variables de sortie de l'algorithme lorsqu'on implemente l'algorithme en virgule fixe. La troisieme partie definit le concept de quantification aleatoire. Il est montre que l'apport de la quantification aleatoire permet d'eviter les phenomenes de blocage qui sont obligatoirement presents dans toute implementation de type virgule fixe. Des ameliorations peuvent etre rendues possibles par l'introduction d'une quantification aleatoire controlee. La derniere partie s'interesse a des algorithmes simplifies et donne une methodologie de calcul complete des effets de quantification lorsqu'on remplace les multiplicateurs par des non-linearites grossieres. Cette methodologie est appliquee dans deux cas particuliers de quantification exponentielle. Enfin, un algorithme simplifie base sur une quantification adaptative de l'erreur est presente
16
Akata, Zeynep. "Contributions à l'apprentissage grande échelle pour la classification d'images." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM003/document.
Full textAbstract:
La construction d'algorithmes classifiant des images à grande échelle est devenue une t^ache essentielle du fait de la difficulté d'effectuer des recherches dans les immenses collections de données visuelles non-etiquetées présentes sur Internet. L'objetif est de classifier des images en fonction de leur contenu pour simplifier la gestion de telles bases de données. La classification d'images à grande échelle est un problème complexe, de par l'importance de la taille des ensembles de données, tant en nombre d'images qu'en nombre de classes. Certaines de ces classes sont dites "fine-grained" (sémantiquement proches les unes des autres) et peuvent même ne contenir aucun représentant étiqueté. Dans cette thèse, nous utilisons des représentations à l'état de l'art d'images et nous concentrons sur des méthodes d'apprentissage efficaces. Nos contributions sont (1) un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle et (2) un nouvel algorithme basé sur l'incorporation d'étiquettes pour apprendre sur des données peu abondantes. En premier lieu, nous introduisons un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle, dans un cadre entièrement supervisé. Il compare plusieurs fonctions objectifs pour apprendre des classifieurs linéaires, tels que "un contre tous", "multiclasse", "classement", "classement avec pondération" par descente de gradient stochastique. Ce banc d'essai se conclut en un ensemble de recommandations pour la classification à grande échelle. Avec une simple repondération des données, la stratégie "un contre tous" donne des performances meilleures que toutes les autres. Par ailleurs, en apprentissage en ligne, un pas d'apprentissage assez petit s'avère suffisant pour obtenir des résultats au niveau de l'état de l'art. Enfin, l'arrêt prématuré de la descente de gradient stochastique introduit une régularisation qui améliore la vitesse d'entraînement ainsi que la capacité de régularisation. Deuxièmement, face à des milliers de classes, il est parfois difficile de rassembler suffisamment de données d'entraînement pour chacune des classes. En particulier, certaines classes peuvent être entièrement dénuées d'exemples. En conséquence, nous proposons un nouvel algorithme adapté à ce scénario d'apprentissage dit "zero-shot". Notre algorithme utilise des données parallèles, comme les attributs, pour incorporer les classes dans un espace euclidien. Nous introduisons par ailleurs une fonction pour mesurer la compatibilité entre image et étiquette. Les paramètres de cette fonction sont appris en utilisant un objectif de type "ranking". Notre algorithme dépasse l'état de l'art pour l'apprentissage "zero-shot", et fait preuve d'une grande flexibilité en permettant d'incorporer d'autres sources d'information parallèle, comme des hiérarchies. Il permet en outre une transition sans heurt du cas "zero-shot" au cas où peu d'exemples sont disponiblesBuilding algorithms that classify images on a large scale is an essential task due to the difficulty in searching massive amount of unlabeled visual data available on the Internet. We aim at classifying images based on their content to simplify the manageability of such large-scale collections. Large-scale image classification is a difficult problem as datasets are large with respect to both the number of images and the number of classes. Some of these classes are fine grained and they may not contain any labeled representatives. In this thesis, we use state-of-the-art image representations and focus on efficient learning methods. Our contributions are (1) a benchmark of learning algorithms for large scale image classification, and (2) a novel learning algorithm based on label embedding for learning with scarce training data. Firstly, we propose a benchmark of learning algorithms for large scale image classification in the fully supervised setting. It compares several objective functions for learning linear classifiers such as one-vs-rest, multiclass, ranking and weighted average ranking using the stochastic gradient descent optimization. The output of this benchmark is a set of recommendations for large-scale learning. We experimentally show that, online learning is well suited for large-scale image classification. With simple data rebalancing, One-vs-Rest performs better than all other methods. Moreover, in online learning, using a small enough step size with respect to the learning rate is sufficient for state-of-the-art performance. Finally, regularization through early stopping results in fast training and a good generalization performance. Secondly, when dealing with thousands of classes, it is difficult to collect sufficient labeled training data for each class. For some classes we might not even have a single training example. We propose a novel algorithm for this zero-shot learning scenario. Our algorithm uses side information, such as attributes to embed classes in a Euclidean space. We also introduce a function to measure the compatibility between an image and a label. The parameters of this function are learned using a ranking objective. Our algorithm outperforms the state-of-the-art for zero-shot learning. It is flexible and can accommodate other sources of side information such as hierarchies. It also allows for a smooth transition from zero-shot to few-shots learning
17
Cénac, Peggy. "Récursivité au carrefour de la modélisation de séquences, des arbres aléatoires, des algorithmes stochastiques et des martingales." Habilitation à diriger des recherches, Université de Bourgogne, 2013. http://tel.archives-ouvertes.fr/tel-00954528.
Full textAbstract:
Ce mémoire est une synthèse de plusieurs études à l'intersection des systèmes dynamiques dans l'analyse statistique de séquences, de l'analyse d'algorithmes dans des arbres aléatoires et des processus stochastiques discrets. Les résultats établis ont des applications dans des domaines variés allant des séquences biologiques aux modèles de régression linéaire, processus de branchement, en passant par la statistique fonctionnelle et les estimations d'indicateurs de risque appliqués à l'assurance. Tous les résultats établis utilisent d'une façon ou d'une autre le caractère récursif de la structure étudiée, en faisant apparaître des invariants comme des martingales. Elles sont au coeur de ce mémoire, utilisées comme outils dans les preuves ou comme objets d'étude.
18
Cheng, Jianqiang. "Stochastic Combinatorial Optimization." Thesis, Paris 11, 2013. http://www.theses.fr/2013PA112261.
Full textAbstract:
Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entièresIn this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs
19
Urban, Bernard. "Applications du maximum d'entropie et du gradient stochastique à la météorologie." Toulouse 3, 1996. http://www.theses.fr/1996TOU30083.
Full textAbstract:
On applique le principe du maximum d'entropie pour: a) justifier certaines relations geophysiques approchees b) resoudre des problemes inverses en presence d'erreurs du modele direct et d'erreurs de mesure. Les composantes de l'erreur du modele peuvent etre correlees par l'utilisation de copules. La methode est appliquee plus specifiquement a un modele meteorologique. On presente aussi une version tronquee d'un algorithme de gradient stochastique du type kiefer-wolfowitz, dont on etudie la vitesse de convergence presque sure et la vitesse de convergence en loi
20
Hernandez, Freddy. "Fluctuations à l'équilibre d'un modèle stochastique non gradient qui conserve l'énergie." Paris 9, 2010. https://bu.dauphine.psl.eu/fileviewer/index.php?doc=2010PA090029.
Full textAbstract:
En cette thèse nous étudions le champ de fluctuations à l'équilibre de l'énergie d'un modèle non gradient réversible. Nous établissons la convergence en loi vers un processus d'Ornstein-Uhlenbeck généralisé. En adaptant la méthode non gradient introduite par S. R. S Varadhan, nous identifions le terme de diffusion, ce qui nous permet de déduire le principe de Boltzmann-Gibbs. Ceci est le point essentiel pour montrer que les lois fini dimensionnelles du champ de fluctuations, convergent vers les lois fini dimensionnelles d'un processus généralisé d'Ornstein-Uhlenbeck. De plus, en utilisant à nouveau le principe de Boltzmann-Gibbs nous obtenons aussi la tension du champ de fluctuations de l'énergie dans un certain espace de Sobolev, ce qui avec la convergence des lois fini dimensionnelles implique la convergence en loi vers le processus généralisé d'Ornstein-Uhlenbeck (mentionné ci-dessus). Le fait que la quantité conservée n'est soit pas une forme linéaire des coordonnées du système, introduit des difficultés supplémentaires de nature géométrique lors de l'application de la méthode non gradient de VaradhanIn this thesis we study the equilibrium energy fluctuation field of a one-dimensional reversible non gradient model. We prove that the limit fluctuation process is governed by a generalized Ornstein-Uhlenbeck process. By adapting the non gradient method introduced by S. R. S Varadhan, we identify the correct diffusion term, which allows us to derive the Boltzmann-Gibbs principle. This is the key point to show that the energy fluctuation field converges in the sense of finite dimensional distributions to a generalized Ornstein-Uhlenbeck process. Moreover, using again the Boltzmann-Gibbs principle we also prove tightness for the energy fluctuation field in a specified Sobolev space, which together with the finite dimensional convergence implies the convergence in distribution to the generalized Ornstein-Uhlenbeck process mentioned above. The fact that the conserved quantity is not a linear functional of the coordinates of the system, introduces new difficulties of geometric nature in applying Varadhan's non gradient method
21
Massé, Pierre-Yves. "Autour De L'Usage des gradients en apprentissage statistique." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS568/document.
Full textAbstract:
Nous établissons un théorème de convergence locale de l'algorithme classique d'optimisation de système dynamique RTRL, appliqué à un système non linéaire. L'algorithme RTRL est un algorithme en ligne, mais il doit maintenir une grande quantités d'informations, ce qui le rend impropre à entraîner des systèmes d'apprentissage de taille moyenne. L'algorithme NBT y remédie en maintenant une approximation aléatoire non biaisée de faible taille de ces informations. Nous prouvons également la convergence avec probabilité arbitrairement proche de un, de celui-ci vers l'optimum local atteint par l'algorithme RTRL. Nous formalisons également l'algorithme LLR et en effectuons une étude expérimentale, sur des données synthétiques. Cet algorithme met à jour de manière adaptive le pas d'une descente de gradient, par descente de gradient sur celui-ci. Il apporte ainsi une réponse partielle au problème de la fixation numérique du pas de descente, dont le choix influence fortement la procédure de descente et qui doit sinon faire l'objet d'une recherche empirique potentiellement longue par le praticienWe prove a local convergence theorem for the classical dynamical system optimization algorithm called RTRL, in a nonlinear setting. The rtrl works on line, but maintains a huge amount of information, which makes it unfit to train even moderately big learning models. The NBT algorithm turns it by replacing these informations by a non-biased, low dimension, random approximation. We also prove the convergence with arbitrarily close to one probability, of this algorithm to the local optimum reached by the RTRL algorithm. We also formalize the LLR algorithm and conduct experiments on it, on synthetic data. This algorithm updates in an adaptive fashion the step size of a gradient descent, by conducting a gradient descent on this very step size. It therefore partially solves the issue of the numerical choice of a step size in a gradient descent. This choice influences strongly the descent and must otherwise be hand-picked by the user, following a potentially long research
22
Zerbinati, Adrien. "Algorithme à gradients multiples pour l'optimisation multiobjectif en simulation de haute fidélité : application à l'aérodynamique compressible." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00868031.
Full textAbstract:
En optimisation multiobjectif, les connaissances du front et de l'ensemble de Pareto sont primordiales pour résoudre un problème. Un grand nombre de stratégies évolutionnaires sont proposées dans la littérature classique. Ces dernières ont prouvé leur efficacité pour identifier le front de Pareto. Pour atteindre un tel résultat, ces algorithmes nécessitent un grand nombre d'évaluations. En ingénierie, les simulations numériques sont généralement réalisées par des modèles de haute-fidélité. Aussi, chaque évaluation demande un temps de calcul élevé. A l'instar des algorithmes mono-objectif, les gradients des critères, ainsi que les dérivées successives, apportent des informations utiles sur la décroissance des fonctions. De plus, de nombreuses méthodes numériques permettent d'obtenir ces valeurs pour un coût modéré. En s'appuyant sur les résultats théoriques obtenus par Inria, nous proposons un algorithme basé sur l'utilisation des gradients de descente. Ces travaux résument la caractérisation théorique de cette méthode et la validation sur des cas tests analytiques. Dans le cas où les gradients ne sont pas accessibles, nous proposons une stratégie basée sur la construction des métamodèles de Krigeage. Ainsi, au cours de l'optimisation, les critères sont évalués sur une surface de réponse et non par simulation. Le temps de calcul est considérablement réduit, au détriment de la précision. La méthode est alors couplée à une stratégie de progression du métamodèle.
23
Makhlouf, Azmi. "Régularité fractionnaire et analyse stochastique de discrétisations ; Algorithme adaptatif de simulation en risque de crédit." Phd thesis, Grenoble INPG, 2009. http://tel.archives-ouvertes.fr/tel-00460269.
Full textAbstract:
Cette thèse concerne trois sujets de probabilités numériques et de mathématiques financières. D'abord, nous étudions le module de régularité L2 en temps de la composante Z d'une EDSR markovienne à coefficients lipschitziens, mais dont la fonction terminale g est irrégulière. Ce module est lié à l'erreur d'approximation par schéma d'Euler. Nous montrons, de façon optimale, que l'ordre de convergence est explicitement lié à la régularité fractionnaire de g. Ensuite, nous proposons une méthode de Monte-Carlo séquentielle pour le calcul efficace du prix d'une tranche de CDO, basée sur des variables de contrôle séquentielles, dans un cadre où les taux de recouvrement sont aléatoires et i.i.d. Enfin, nous analysons l'erreur de couverture associée à la stratégie en Delta-Gamma. La régularité fractionnaire de la fonction payoff joue un rôle crucial dans le choix des dates de rebalancement, afin d'atteindre des vitesses de convergence optimales.
24
Zeriab, Mohamed Zeriab. "Contribution à l'optimisation globale : approche déterministe et stochastique et application." Phd thesis, INSA de Rouen, 2009. http://tel.archives-ouvertes.fr/tel-00560887.
Full textAbstract:
Dans les situations convexes, le problème d'optimisation globale peut être abordé par un ensemble de méthodes classiques, telles, par exemple, celles basées sur le gradient, qui ont montré leur efficacité en ce domaine. Lorsque la situation n'est pas convexe, ces méthodes peuvent être mises en défaut et ne pas trouver un optimum global. La contribution de cette thèse est une méthodologie pour la détermination de l'optimum global d'une fonction non convexe, en utilisant des algorithmes hybrides basés sur un couplage entre des algorithmes stochastiques issus de familles connues, telles, par exemple, celle des algorithmes génétiques ou celle du recuit simulé et des algorithmes déterministes perturbés aléatoirement de façon convenable. D'une part, les familles d'algorithmes stochastiques considérées ont fait preuve d'efficacité pour certaines classes de problèmes et, d'autre part, l'adjonction de perturbations aléatoires permet de construire des méthodes qui sont en théorie convergents vers un optimum global. En pratique, chacune de ces approches a ses limitations et insuffisantes, de manière que le couplage envisagé dans cette thèse est une alternative susceptible d'augmenter l'efficacité numérique. Nous examinons dans cette thèse quelques unes de ces possibilités de couplage. Pour établir leur efficacité, nous les appliquons à des situations test classiques et à un problème de nature stochastique du domaine des transports.
25
Tauvel, Claire. "Optimisation stochastique à grande échelle." Phd thesis, Université Joseph Fourier (Grenoble), 2008. http://tel.archives-ouvertes.fr/tel-00364777.
Full textAbstract:
L'objet de cette thèse est l'étude d'algorithmes itératifs permettant de résoudre des problèmes d'optimisation convexe avec ou sans contraintes fonctionnelles, des problèmes de résolutions d'inégalités variationnelles à opérateur monotone et des problèmes de recherche de point selle. Ces problèmes sont envisagés lorsque la dimension de l'espace de recherche est grande et lorsque les valeurs des différentes fonctions étudiées et leur sous/sur-gradients ne sont pas connues exactement et ne sont accessibles qu'au travers d'un oracle stochastique. Les algorithmes que nous étudions sont des adaptations au cas stochastique de deux algorithmes : le premier inspiré de la méthode de descente en miroir de Nemirovski et Yudin et le second, de l'algorithme d'extrapolation duale de Nesterov. Pour chacun de ces deux algorithmes, nous donnons des bornes pour l'espérance et pour les déviations modérées de l'erreur d'approximation sous différentes hypothèses de régularité pour tous les problèmes sans contraintes fonctionnelles envisagées et nous donnons des versions adaptatives de ces algorithmes qui permettent de s'affranchir de connaître certains paramètres de ces problèmes non accessibles en pratique. Enfin nous montrons comment, à l'aide d'un algorithme auxiliaire inspiré de la méthode de Newton et des résultats obtenus lors de la résolution des problèmes de recherche de point selle, il est possible de résoudre des problèmes d'optimisation sous contraintes fonctionnelles.
26
Saadane, Sofiane. "Algorithmes stochastiques pour l'apprentissage, l'optimisation et l'approximation du régime stationnaire." Thesis, Toulouse 3, 2016. http://www.theses.fr/2016TOU30203/document.
Full textAbstract:
Dans cette thèse, nous étudions des thématiques autour des algorithmes stochastiques et c'est pour cette raison que nous débuterons ce manuscrit par des éléments généraux sur ces algorithmes en donnant des résultats historiques pour poser les bases de nos travaux. Ensuite, nous étudierons un algorithme de bandit issu des travaux de N arendra et Shapiro dont l'objectif est de déterminer parmi un choix de plusieurs sources laquelle profite le plus à l'utilisateur en évitant toutefois de passer trop de temps à tester celles qui sont moins performantes. Notre but est dans un premier temps de comprendre les faiblesses structurelles de cet algorithme pour ensuite proposer une procédure optimale pour une quantité qui mesure les performances d'un algorithme de bandit, le regret. Dans nos résultats, nous proposerons un algorithme appelé NS sur-pénalisé qui permet d'obtenir une borne de regret optimale au sens minimax au travers d'une étude fine de l'algorithme stochastique sous-jacent à cette procédure. Un second travail sera de donner des vitesses de convergence pour le processus apparaissant dans l'étude de la convergence en loi de l'algorithme NS sur-pénalisé. La particularité de l'algorithme est qu'il ne converge pas en loi vers une diffusion comme la plupart des algorithmes stochastiques mais vers un processus à sauts non-diffusif ce qui rend l'étude de la convergence à l'équilibre plus technique. Nous emploierons une technique de couplage afin d'étudier cette convergence. Le second travail de cette thèse s'inscrit dans le cadre de l'optimisation d'une fonction au moyen d'un algorithme stochastique. Nous étudierons une version stochastique de l'algorithme déterministe de boule pesante avec amortissement. La particularité de cet algorithme est d'être articulé autour d'une dynamique qui utilise une moyennisation sur tout le passé de sa trajectoire. La procédure fait appelle à une fonction dite de mémoire qui, selon les formes qu'elle prend, offre des comportements intéressants. Dans notre étude, nous verrons que deux types de mémoire sont pertinents : les mémoires exponentielles et polynomiales. Nous établirons pour commencer des résultats de convergence dans le cas général où la fonction à minimiser est non-convexe. Dans le cas de fonctions fortement convexes, nous obtenons des vitesses de convergence optimales en un sens que nous définirons. Enfin, l'étude se termine par un résultat de convergence en loi du processus après une bonne renormalisation. La troisième partie s'articule autour des algorithmes de McKean-Vlasov qui furent introduit par Anatoly Vlasov et étudié, pour la première fois, par Henry McKean dans l'optique de la modélisation de la loi de distribution du plasma. Notre objectif est de proposer un algorithme stochastique capable d'approcher la mesure invariante du processus. Les méthodes pour approcher une mesure invariante sont connues dans le cas des diffusions et de certains autre processus mais ici la particularité du processus de McKean-Vlasov est de ne pas être une diffusion linéaire. En effet, le processus a de la mémoire comme les processus de boule pesante. De ce fait, il nous faudra développer une méthode alternative pour contourner ce problème. Nous aurons besoin d'introduire la notion de pseudo-trajectoires afin de proposer une procédure efficaceIn this thesis, we are studying severa! stochastic algorithms with different purposes and this is why we will start this manuscript by giving historicals results to define the framework of our work. Then, we will study a bandit algorithm due to the work of Narendra and Shapiro whose objectif was to determine among a choice of severa! sources which one is the most profitable without spending too much times on the wrong orres. Our goal is to understand the weakness of this algorithm in order to propose an optimal procedure for a quantity measuring the performance of a bandit algorithm, the regret. In our results, we will propose an algorithm called NS over-penalized which allows to obtain a minimax regret bound. A second work will be to understand the convergence in law of this process. The particularity of the algorith is that it converges in law toward a non-diffusive process which makes the study more intricate than the standard case. We will use coupling techniques to study this process and propose rates of convergence. The second work of this thesis falls in the scope of optimization of a function using a stochastic algorithm. We will study a stochastic version of the so-called heavy bali method with friction. The particularity of the algorithm is that its dynamics is based on the ali past of the trajectory. The procedure relies on a memory term which dictates the behavior of the procedure by the form it takes. In our framework, two types of memory will investigated : polynomial and exponential. We will start with general convergence results in the non-convex case. In the case of strongly convex functions, we will provide upper-bounds for the rate of convergence. Finally, a convergence in law result is given in the case of exponential memory. The third part is about the McKean-Vlasov equations which were first introduced by Anatoly Vlasov and first studied by Henry McKean in order to mode! the distribution function of plasma. Our objective is to propose a stochastic algorithm to approach the invariant distribution of the McKean Vlasov equation. Methods in the case of diffusion processes (and sorne more general pro cesses) are known but the particularity of McKean Vlasov process is that it is strongly non-linear. Thus, we will have to develop an alternative approach. We will introduce the notion of asymptotic pseudotrajectory in odrer to get an efficient procedure
27
Ben, Elhaj Salah Sami. "Modélisation non-locale et stochastique de matériaux à fort gradient de propriétés par développement asymptotique." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2019. http://www.theses.fr/2019ESMA0018.
Full textAbstract:
Le but est de proposer un modèle macroscopique, déterministe et non-local, construit par transition d'échelle pour des matériaux hétérogènes à fort gradient de propriétés, constitués d’inclusions distribuées dans une matrice élastique suivant un processus stochastique ergodique. La méthode des développements asymptotiques, ici étendue dans un cadre aléatoire, est combinée avec une approche énergétique pour faire apparaître le second gradient de déplacement dans l'expression de l'énergie de déformation. Un premier modèle est ainsi obtenu et implique trois tenseurs d'élasticité homogénéisés fonctions du paramètre stochastique et des propriétés des phases. Contrairement à la littérature, il fait intervenir deux longueurs caractéristiques fortement reliées à la microstructure. La mise en œuvre numérique est réalisée pour deux types de microstructures tridimensionnelles de complexité morphologique croissante. Les premières sont virtuelles générées à partir d'un motif simple (une inclusion entourée de six petites) distribué aléatoirement. Les secondes sont des microstructures réelles d'Ethylène-Propylène-Diène Monomère obtenues par tomographie, contenant des clusters d'inclusions de structures complexes.Une seconde transition d'échelle à l'aide d'outils d'homogénéisation variationnelle stochastique dans le cas ergodique est réalisée afin d’obtenir un modèle homogène, exploitable en calculs de structures. Le passage à la limite sur le paramètre d’hétérogénéité émanant du développement asymptotique précédent est ainsi effectué par la méthode de Γ-convergence avec pour objectif de conserver un maximum d'information microstructurale. In fine, le modèle obtenu est macroscopique, non-local, déterministe et richement connecté à la microstructure. La non-localité s'exprime non seulement par le second gradient de déplacement mais aussi par la présence du champ de déplacement virtuel (mémoire) des inclusions. Le lien fort avec la microstructure s'exprime toujours par la présence du paramètre stochastique et des propriétés des phases, mais aussi par celle des fractions asymptotiques de la phase inclusionaire dans le matériau et dans les volumes morphologiques définis par les longueurs caractéristiques intervenant dans le modèle.Pour une future utilisation pratique du modèle, un élément fini non-local et enrichi avec des interpolations de type Hermite est implémenté dans le solveur élément fini FoXtroT de l'Institut Pprime. Il prend en compte le champ de déplacement virtuel (mémoire) des inclusions et les gradients des champs de déplacement macroscopique et virtuel. Les premiers résultats sur cet aspect inédit sont encourageantsThe aim is to propose a macroscopic, deterministic and non-local model, constructed by scale transition for heterogeneous materials with high property gradients and containing a random distribution of inclusions. More precisely, the inclusions are distributed in an elastic matrix according to a stochastic ergodic process. Several non-local models exist in the literature, but they do not allow (or very little) to obtain non-local quantities and/or fields at the macroscopic scale from a scale-transition. Besides, it is often difficult to link the non-local parameters to the microstructure. To this aim, we developed a two-step approach.In the first stage, we combined the method of asymptotic developments with an energetic approach to reveal a second displacement gradient in the strain energy. The advanced model involves three homogenized elasticity tensors functions of the stochastic parameter and of the phase properties. As opposed to the literature, the model involves two characteristic lengths strongly linked to the microstructure. These lengths define two morphological representative elementary volumes on which full field simulations are performed in order to determine the macroscopic strain tensors at orders 0 and 1 involved in the formulation of the model. In order to test this first version of the model, numerical simulations were performed. The estimate of the classical part of the energy, coming from the local part of the fields, has been successfully compared to classical bounds for a composite bar consisting of a random distribution of two homogeneous and isotropic elastic materials. Then, numerical solving of the whole model including the non-local terms has been performed in the three-dimensional case. Two types of microstructures with increasing morphological complexity were used. The first ones are virtual microstructures generated from a given simple pattern randomly distributed throughout the structure and composed of a big inclusion circled by six identical small ones. The second are real microstructures of Ethylène-Propylène-Diène Monomère (EPDM) obtained by tomography and containing clusters of inclusions with complex structures.In order to obtain a macroscopic model that can be used for structure analysis, without any full field intermediate calculations, a second scale transition has been performed using stochastic variational homogenization tools in the ergodic case. More precisely, the Γ-convergence method has been used in order to have a convergence of energy rather than that of mechanical fields, aiming at keeping a strong microstructural content. In fine, the model is macroscopic, non-local, deterministic and strongly connected to the microstructure. Non-local effects are now accounted for by the presence of the second displacement gradient but also by the presence of the virtual (memory) displacement field of the inclusions. The link with microstructure is still manifest through the presence of the stochastic parameter and phase properties, but also by the presence of the asymptotic fractions of the inclusion phase in the material and in each of the morphological volumes defined by the model characteristic lengths. In order to prepare the use of the model for structure calculations, a non-local finite element enriched with Hermit-type interpolations was implemented in FoXtroT, the finite element solver of the Pprime Institute. This element takes into account the virtual (memory) displacement field related to inclusions as well as the gradients of the macroscopic and virtual displacement fields. The first numerical results on this aspect, to our knowledge never discussed in the literature, are promising
28
Chatenet-Laurent, Nathalie. "Algorithme d'apprentissage de la politique optimale d'un processus stochastique : application à un réseau d'alimentation en eau potable." Bordeaux 1, 1997. http://www.theses.fr/1997BOR10540.
Full textAbstract:
Cette these s'interesse a l'apprentissage de problemes de controle a solutions optimales non stationnaires par une technique d'apprentissage par renforcement, le qlearning. Cette methode, comme la plupart des techniques de renforcement a toujours ete utilisee dans des applications a solutions stationnaires. La prise en compte du temps inherente a la programmation dynamique, a ete omise dans les algorithmes de type qlearning. Or un environnement non stationnaire, un cout ou une recompense dependant du temps a minimiser ou maximiser, amenent naturellement vers des solutions optimales non stationnaires. Cette dependance par rapport au temps oblige a mettre en uvre des traitements particuliers qui fournissent des solutions heuristiques economes en temps. Des simulations numeriques sont menees de maniere a mettre en evidence les solutions proposees. Enfin, la these se concretise par la mise en place d'un prototype permettant de gerer un reseau d'alimentation en eau potable de maniere optimale en utilisant une methode d'apprentissage auto-adaptatif, tel que le qlearning. Il evite, contrairement aux methodes de programmation mathematique de se heurter a la necessite de connaitre parfaitement le comportement hydraulique des reseaux, ce qui necessitait des calages a chaque modification de la structure du reseau
29
Chotin-Avot, Roselyne. "Architectures matérielles pour l'arithmétique stochastique discrète." Paris 6, 2003. http://hal.upmc.fr/tel-01267458.
Full text
30
Panloup, Fabien. "Approximation récursive du régime stationnaire d'une équation différentielle stochastique avec sauts." Paris 6, 2006. http://www.theses.fr/2006PA066397.
Full textAbstract:
Cette thèse est dans sa majeure partie consacrée à la construction et l'étude de méthodes implémentables par ordinateur permettant d'approcher le régime stationnaire d'un processus ergordique multidimensionnel solution d'une EDS dirigée par un processus de Lévy. S'appuyant sur une approche développée par Lamberton&Pagès puis Lemaire dans le cadre des diffusions Browniennes, nos méthodes basées sur des schémas d'Euler à pas décroissant, « exacts » ou « approchés », permettent de simuler efficacement la probabilité invariante mais également la loi globale d'un tel processus en régime stationnaire. Ce travail possède des applications théoriques et pratiques diverses dont certaines sont développées ici (TCL p. S. Pour les lois stables, théorème limite relatif aux valeurs extrêmes, pricing d'options pour des modèles à volatilité stochastique stationnaire. . . ).
31
Panloup, Fabien. "Approximation récursive du régime stationnaire d'une Equation Differentielle Stochastique avec sauts." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2006. http://tel.archives-ouvertes.fr/tel-00120508.
Full textAbstract:
La thématique principale de cette thèse est la construction et l'étude de méthodes implémentables par ordinateur permettant d'approcher le régime stationnaire d'un processus ergordique multidimensionnel solution d'une EDS dirigée par un processus de Lévy. S'appuyant sur une approche développée par Lamberton&Pagès puis Lemaire dans le cadre des diffusions Browniennes, nos méthodes basées sur des schémas d'Euler à pas décroissant, « exacts » ou « approchés », permettent de simuler efficacement la probabilité invariante mais également la loi globale d'un tel processus en régime stationnaire.
Ce travail possède des applications théoriques et pratiques diverses dont certaines
sont développées ici (TCL p.s. pour les lois stables, théorème limite relatif aux valeurs extrêmes, pricing d'options pour des modèles à volatilité stochastique stationnaire...).
32
Diabaté, Modibo. "Modélisation stochastique et estimation de la croissance tumorale." Thesis, Université Grenoble Alpes (ComUE), 2019. http://www.theses.fr/2019GREAM040.
Full textAbstract:
Cette thèse porte sur la modélisation mathématique de la dynamique du cancer ; elle se divise en deux projets de recherche.Dans le premier projet, nous estimons les paramètres de la limite déterministe d'un processus stochastique modélisant la dynamique du mélanome (cancer de la peau) traité par immunothérapie. L'estimation est réalisée à l'aide d'un modèle statistique non-linéaire à effets mixtes et l'algorithme SAEM, à partir des données réelles de taille tumorale mesurée au cours du temps chez plusieurs patients. Avec ce modèle mathématique qui ajuste bien les données, nous évaluons la probabilité de rechute du mélanome (à l'aide de l'algorithme Importance Splitting), et proposons une optimisation du protocole de traitement (doses et instants du traitement).Nous proposons dans le second projet, une méthode d'approximation de vraisemblance basée sur une approximation de l'algorithme Belief Propagation à l'aide de l'algorithme Expectation-Propagation, pour une approximation diffusion du modèle stochastique de mélanome observée chez un seul individu avec du bruit gaussien. Cette approximation diffusion (définie par une équation différentielle stochastique) n'ayant pas de solution analytique, nous faisons recours à une méthode d'Euler pour approcher sa solution (après avoir testé la méthode d'Euler sur le processus de diffusion d'Ornstein Uhlenbeck). Par ailleurs, nous utilisons une méthode d'approximation de moments pour faire face à la multidimensionnalité et la non-linéarité de notre modèle. A l'aide de la méthode d'approximation de vraisemblance, nous abordons l'estimation de paramètres dans des Modèles de Markov CachésThis thesis is about mathematical modeling of cancer dynamics ; it is divided into two research projects.In the first project, we estimate the parameters of the deterministic limit of a stochastic process modeling the dynamics of melanoma (skin cancer) treated by immunotherapy. The estimation is carried out with a nonlinear mixed-effect statistical model and the SAEM algorithm, using real data of tumor size. With this mathematical model that fits the data well, we evaluate the relapse probability of melanoma (using the Importance Splitting algorithm), and we optimize the treatment protocol (doses and injection times).We propose in the second project, a likelihood approximation method based on an approximation of the Belief Propagation algorithm by the Expectation-Propagation algorithm, for a diffusion approximation of the melanoma stochastic model, noisily observed in a single individual. This diffusion approximation (defined by a stochastic differential equation) having no analytical solution, we approximate its solution by using an Euler method (after testing the Euler method on the Ornstein Uhlenbeck diffusion process). Moreover, a moment approximation method is used to manage the multidimensionality and the non-linearity of the melanoma mathematical model. With the likelihood approximation method, we tackle the problem of parameter estimation in Hidden Markov Models
33
Luu, Keurfon. "Optimisation numérique stochastique évolutionniste : application aux problèmes inverses de tomographie sismique." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEM077/document.
Full textAbstract:
La tomographie sismique des temps de trajet est un problème d'optimisation mal-posé du fait de la non-linéarité entre les temps et le modèle de vitesse. Par ailleurs, l'unicité de la solution n'est pas garantie car les données peuvent être expliquées par de nombreux modèles. Les méthodes de Monte-Carlo par Chaînes de Markov qui échantillonnent l'espace des paramètres sont généralement appréciées pour répondre à cette problématique. Cependant, ces approches ne peuvent pleinement tirer partie des ressources computationnelles fournies par les super-calculateurs modernes. Dans cette thèse, je me propose de résoudre le problème de tomographie sismique à l'aide d'algorithmes évolutionnistes. Ce sont des méthodes d'optimisation stochastiques inspirées de l'évolution naturelle des espèces. Elles opèrent sur une population de modèles représentés par un ensemble d'individus qui évoluent suivant des processus stochastiques caractéristiques de l'évolution naturelle. Dès lors, la population de modèles peut être intrinsèquement évaluée en parallèle ce qui rend ces algorithmes particulièrement adaptés aux architectures des super-calculateurs. Je m'intéresse plus précisément aux trois algorithmes évolutionnistes les plus populaires, à savoir l'évolution différentielle, l'optimisation par essaim particulaire, et la stratégie d'évolution par adaptation de la matrice de covariance. Leur faisabilité est étudiée sur deux jeux de données différents: un jeu réel acquis dans le contexte de la fracturation hydraulique et un jeu synthétique de réfraction généré à partir du modèle de vitesse Marmousi réputé pour sa géologie structurale complexeSeismic traveltime tomography is an ill-posed optimization problem due to the non-linear relationship between traveltime and velocity model. Besides, the solution is not unique as many models are able to explain the observed data. The non-linearity and non-uniqueness issues are typically addressed by using methods relying on Monte Carlo Markov Chain that thoroughly sample the model parameter space. However, these approaches cannot fully handle the computer resources provided by modern supercomputers. In this thesis, I propose to solve seismic traveltime tomography problems using evolutionary algorithms which are population-based stochastic optimization methods inspired by the natural evolution of species. They operate on concurrent individuals within a population that represent independent models, and evolve through stochastic processes characterizing the different mechanisms involved in natural evolution. Therefore, the models within a population can be intrinsically evaluated in parallel which makes evolutionary algorithms particularly adapted to the parallel architecture of supercomputers. More specifically, the works presented in this manuscript emphasize on the three most popular evolutionary algorithms, namely Differential Evolution, Particle Swarm Optimization and Covariance Matrix Adaptation - Evolution Strategy. The feasibility of evolutionary algorithms to solve seismic tomography problems is assessed using two different data sets: a real data set acquired in the context of hydraulic fracturing and a synthetic refraction data set generated using the Marmousi velocity model that presents a complex geology structure
34
Vu, Thi Thanh Xuan. "Optimisation déterministe et stochastique pour des problèmes de traitement d'images en grande dimension." Thesis, Aix-Marseille, 2017. http://www.theses.fr/2017AIXM0540.
Full textAbstract:
Dans cette thèse on s’intéresse au problème des décompositions canoniques polyadiques de tenseurs d’ordre $N$ potentiellement grands et sous différentes contraintes (non-négativité, aspect creux lié à une possible surestimation du rang du tenseur). Pour traiter ce problème, nous proposons trois nouvelles approches itératives différentes: deux approches déterministes dont une approche proximale, et une approche stochastique. La première approche étend les travaux de thèse de J-P. Royer au cas de tenseurs de dimension $N$. Dans l’approche stochastique, nous considérons pour la première fois dans le domaine des décompositions tensorielles, des algorithmes génétiques (mimétiques) dont principe général repose sur l’évolution d’une population de candidats. Dans le dernier type d’approche, nous avons considéré un algorithme proximal pré-conditionné (le Block-Coordinate Variable Metric Forward-Backward), algorithme fonctionnant par blocs de données avec une matrice de pré-conditionnement liée à chaque bloc et fondé sur deux étapes successives principales : une étape de gradient et une étape proximale. Finalement, les différentes méthodes suggérées sont comparées entre elles et avec d’autres algorithmes classiques de la littérature sur des données synthétiques (à la fois aléatoires ou proches des données observées en spectroscopie de fluorescence) et sur des données expérimentales réelles correspondant à une campagne de surveillance des eaux d’une rivière et visant à la détection d’apparition de polluantsIn this PhD thesis, we consider the problem of the Canonical Polyadic Decomposition (CPD) of potentially large $N$-th order tensors under different constraints (non-negativity, sparsity due to a possible overestimation of the tensor rank, etc.). To tackle such a problem, we propose three new iterative methods: a standard gradient based deterministic approach, a stochastic approach (memetic) and finally a proximal approach (Block-Coordinate Variable Metric Forward-Backward). The first approach extends J-P. Royer's works to the case of non-negative N-th order tensors. In the stochastic approach, genetic (memetic) methods are considered for the first time to solve the CPD problem. Their general principle is based on the evolution of a family of candidates. In the third type of approaches, a proximal algorithm namely the Block-Coordinate Variable Metric Forward-Backward is presented. The algorithm relies on two main steps: a gradient step and a proximal step. The blocks of coordinates naturally correspond to latent matrices. We propose a majorant function as well as a preconditioner with regard to each block. All methods are compared with other popular algorithms of the literature on synthetic (fluorescence spectroscopy like or random) data and on real experimental data corresponding to a water monitoring campaign aiming at detecting the appearance of pollutants
35
Gerzaguet, Robin. "Méthodes de traitement numérique du signal pour l'annulation d'auto-interférences dans un terminal mobile." Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GRENT014/document.
Full textAbstract:
Les émetteurs-récepteurs actuels tendent à devenir multi-standards c’est-àdireque plusieurs standards de communication peuvent cohabiter sur la même puce. Lespuces sont donc amenées à traiter des signaux de formes très différentes, et les composantsanalogiques subissent des contraintes de conception de plus en plus fortes associées au supportdes différentes normes. Les auto-interférences, c’est à dire les interférences généréespar le système lui-même, sont donc de plus en plus présentes, et de plus en plus problématiquesdans les architectures actuelles. Ces travaux s’inscrivent dans le paradigmede la « radio sale » qui consiste à accepter une pollution partielle du signal d’intérêtet à réaliser, par l’intermédiaire d’algorithmes, une atténuation de l’impact de ces pollutionsauto-générées. Dans ce manuscrit, on s’intéresse à différentes auto-interférences(phénomène de "spurs", de "Tx leakage", ...) dont on étudie les modèles numériques etpour lesquelles nous proposons des stratégies de compensation. Les algorithmes proposéssont des algorithmes de traitement du signal adaptatif qui peuvent être vus comme des« algorithmes de soustraction de bruit » basés sur des références plus ou moins précises.Nous dérivons analytiquement les performances transitionnelles et asymptotiques théoriquesdes algorithmes proposés. On se propose également d’ajouter à nos systèmes unesur-couche originale qui permet d’accélérer la convergence, tout en maintenant des performancesasymptotiques prédictibles et paramétrables. Nous validons enfin notre approchesur une puce dédiée aux communications cellulaires ainsi que sur une plateforme de radiologicielleRadio frequency transceivers are now massively multi-standards, which meansthat several communication standards can cohabit in the same environment. As a consequence,analog components have to face critical design constraints to match the differentstandards requirements and self-interferences that are directly introduced by the architectureitself are more and more present and detrimental. This work exploits the dirty RFparadigm : we accept the signal to be polluted by self-interferences and we develop digitalsignal processing algorithms to mitigate those aforementioned pollutions and improve signalquality. We study here different self-interferences and propose baseband models anddigital adaptive algorithms for which we derive closed form formulae of both transientand asymptotic performance. We also propose an original adaptive step-size overlay toimprove transient performance of our method. We finally validate our approach on a systemon chip dedicated to cellular communications and on a software defined radio
36
Billaud, Yann. "Modélisation hybride stochastique-déterministe des incendies de forêts." Thesis, Aix-Marseille 1, 2011. http://www.theses.fr/2011AIX10100/document.
Full textAbstract:
Les grands incendies de forêts sont responsables de la quasi-totalité de la surface brulée et contribuent, par les émissions de particules et de gaz à effet de serre qu’ils génèrent, au réchauffement climatique. Des observations satellitaires ont mis en évidence un comportement fractal que l’on attribue aux hétérogénéités locales (topographie, végétation, conditions météorologiques) rencontrées par ces feux lors de leur propagation. Le présent travail a été consacré au développement et à la validation d’un modèle hybride de propagation d’incendie, capable de reproduire ce comportement. Ce modèle est une extension du modèle original de réseau de « petit monde » où les phénomènes qui se produisent à l’échelle macroscopique, comme le rayonnement du front de flammes et l’inflammation pilotée de la strate végétale sont traités de façon déterministe. Pour décrire le rayonnement, nous avons utilisé un modèle de flamme solide couplé à une méthode de Monte Carlo. La validation a porté sur des configurations simples, mais aussi plus complexes, comme le rayonnement d’un front hétérogène de flammes ou celui d’une flamme d’éthanol. Un modèle d’inflammation a ensuite été élaboré et appliqué à des litières d’aiguilles de pin. Les paramètres du modèle ont été optimisés par un algorithme génétique, conduisant au meilleur accord avec les résultats expérimentaux, en termes de temps d‘inflammation et de perte de masses. Il a été montré que l’oxydation du résidu charbonneux joue un rôle prépondérant sur l’inflammation à bas flux. Le modèle de propagation de petit monde a été validé sur un brûlage dirigé et sur un feu historique, montrant un bon accord en termes de surface brûlée, de vitesse de propagation, de contours de feu, et de propriétés fractales. On a montré qu’il pouvait être utilisé pour le dimensionnement d’ouvrages de défense, comme les coupures de combustible, ou pour expliquer le comportement atypique du feu dans certaines situations (talweg, ruptures de pente, etc.). Son application a également permis d’optimiser le nombre et l’emplacement d’un réseau de capteurs déployés dans la végétation dans le but de localiser précisément et détecter précocement le départ d’un feuMost of the area burned by forest fires is attributable to the few fires that escape initial attack to become large. As a consequence large-scale fires produce a large amount of green-house gases and particles which contribute to the global warming. Heterogeneous conditions of weather, fuel, and topography are generally encountered during the propagation of large fires. This shapes irregular contours and fractal post-fire patterns, as revealed by satellite maps. Among existing wildfire spread models, stochastic models seem to be good candidates for studying the erratic behavior of large fires, due to the above-mentioned heterogeneous conditions. The model we developed is a variant of the so-called small-world network model. Flame radiation and fuel piloted ignition are taken into account in a deterministic way at the macroscopic scale. The radiative interaction domain of a burning cell is determined from Monte Carlo simulation using the solid flame model. Some cases are studied, ranging from relatively simple to more complex geometries like an irregular flame fronts or an ethanol pool fire. Then, a numerical model is developed to investigate the piloted ignition of litters composed of maritime pine needles. A genetic algorithm is used to locate a set of model parameters that provide optimal agreement between the model predictions and the experimental data in terms of ignition time and mass loss. The model results had shown the importance of char surface oxidation for heat fluxes close to the critical flux for ignition. Finally, the small-world network model was used to simulate fire patterns in heterogeneous landscapes. Model validation was achieved to an acceptable degree in terms of contours, burned area and fractal properties, through comparison of results with data from a small controlled bushfire experiment and a historical Mediterranean fire. Therefore, it has been proven to be a powerful tool in the sizing of fortifications as fuel break areas at the wildland urban interface or in the understanding of atypical behavior in particular configurations (talweg, slope breaking, etc.). It has also been used for the optimization of an in-situ sensor network whose purpose is to detect precociously and to locate precisely small fires, preventing them from spreading and burning out of control. Our objective was to determine the minimum number and placement of sensors deployed in the forest
37
Tendeau, Frédéric. "Analyse syntaxique et sémantique avec évaluation d'attributs dans un demi-anneau : application à la linguistique calculatoire." Orléans, 1997. http://www.theses.fr/1997ORLE2064.
Full textAbstract:
Le but est de proposer des algorithmes de calcul de forêts d'analyse décorées par des attributs vérifiant la structure algébrique de demi-anneau et applicables à différents formalismes de la linguistique calculatoire. Le point de départ est l'analyse syntaxique non-contextuelle générale (incluant donc les grammaires ambiguës). Une stratégie d'analyse est présentée sous la forme d'un automate à pile non-déterministe, qui est ensuite interprété par programmation dynamique. Cette technique s'applique sur des calculs récursifs à condition que chaque sous-calcul puisse être identifié par un indice. Le mécanisme consiste à tabuler les résultats, en n'effectuant chaque sous-calcul qu'une fois. Il en résulte une complexité (en temps et en espace) cubique pour les algorithmes de reconnaissance syntaxique. Cette méthode est étendue à l'analyse stochastique, pour laquelle nous proposons une généralisation des théorèmes d'adéquation entre les calculs opérationnels de probabilités et leur définition par la grammaire probabiliste. Les quantités calculées sont les probabilités de préfixe, de sous-chaîne, et le calcul du meilleur arbre. Quatre stratégies sont présentées : earley, left corner, lr et extended lr. La théorie des séries de puissance algébriques est utilisée pour formaliser la décoration d'une grammaire dans un demi-anneau abstrait. L’analyse s'exprime alors comme le calcul du coefficient d'un mot pour la série formelle définie par la grammaire décorée, ce qui revient à résoudre un système d'équations au point fixe. Nous donnons des conditions qui assurent la solvabilité du système, et montrons qu'on peut le résoudre en utilisant la programmation dynamique. Les quatre algorithmes stochastiques sont alors reformulés pour calculer une décoration dans un demi-anneau abstrait. Enfin nous montrons que les grammaires de clauses définies et les grammaires à structure de traits peuvent être décrites comme des grammaires non-contextuelles décorées dans un demi-anneau.
38
Huang, Junbo. "Théorème de Berry-Esseen pour martingales normalisées et algorithmes stochastiques : application en contrôle stochastique." Paris 6, 2009. http://www.theses.fr/2009PA066174.
Full text
39
Slaoui, Yousri. "Application des méthodes d'approximations stochastiques à l'estimation de la densité et de la régression." Phd thesis, Université de Versailles-Saint Quentin en Yvelines, 2006. http://tel.archives-ouvertes.fr/tel-00131964.
Full textAbstract:
L'objectif de cette thèse est d'appliquer les méthodes d'approximations stochastiques à l'estimation de la densité et de la régression. Dans le premier chapitre, nous construisons un algorithme stochastique à pas simple qui définit toute une famille d'estimateurs récursifs à noyau d'une densité de probabilité. Nous étudions les différentes propriétés de cet algorithme. En particulier, nous identifions deux classes d'estimateurs; la première correspond à un choix de pas qui permet d'obtenir un risque minimal, la seconde une variance minimale. Dans le deuxième chapitre, nous nous intéressons à l'estimateur proposé par Révész (1973, 1977) pour estimer une fonction de régression r:x-> E[Y|X=x]. Son estimateur r_n, construit à l'aide d'un algorithme stochastique à pas simple, a un gros inconvénient: les hypothèses sur la densité marginale de X nécessaires pour établir la vitesse de convergence de r_n sont beaucoup plus fortes que celles habituellement requises pour étudier le comportement asymptotique d'un estimateur d'une fonction de régression. Nous montrons comment l'application du principe de moyennisation des algorithmes stochastiques permet, tout d'abord en généralisant la définition de l'estimateur de Révész, puis en moyennisant cet estimateur généralisé, de construire un estimateur récursif br_n qui possède de bonnes propriétés asymptotiques. Dans le troisième chapitre, nous appliquons à nouveau les méthodes d'approximation stochastique à l'estimation d'une fonction de régression. Mais cette fois, plutôt que d'utiliser des algorithmes stochastiques à pas simple, nous montrons comment les algorithmes stochastiques à pas doubles permettent de construire toute une classe d'estimateurs récursifs d'une fonction de régression, et nous étudions les propriétés asymptotiques de ces estimateurs. Cette approche est beaucoup plus simple que celle du deuxième chapitre: les estimateurs construits à l'aide des algorithmes à pas doubles n'ont pas besoin d'être moyennisés pour avoir les bonnes propriétés asymptotiques.
40
Papa, Guillaume. "Méthode d'échantillonnage appliqué à la minimisation du risque empirique." Electronic Thesis or Diss., Paris, ENST, 2018. http://www.theses.fr/2018ENST0005.
Full textAbstract:
Dans ce manuscrit, nous présentons et étudions des stratégies d’échantillonnage appliquées, à problèmes liés à l’apprentissage statistique. L’objectif est de traiter les problèmes qui surviennent généralement dans un contexte de données volumineuses lorsque le nombre d’observations et leur dimensionnalité contraignent le processus d’apprentissage. Nous proposons donc d’aborder ce problème en utilisant deux stratégies d’échantillonnage: - Accélérer le processus d’apprentissage en échantillonnant les observations les plus utiles. - Simplifier le problème en écartant certaines observations pour réduire la complexité et la taille du problème. Pour commencer, nous nous plaçons dans le contexte de la classification binaire, lorsque les observations utilisées pour former un classificateur sont issues d’un schéma d’échantillonnage/sondage et présentent une structure de dépendance complexe pour lequel nous établissons des bornes de généralisation. Ensuite nous étudions le problème d’implémentation de la descente de gradient stochastique quand les observations sont tirées non uniformément. Nous concluons cette thèse par l’étude du problème de reconstruction de graphes pour lequel nous établissons de nouveau résultat théoriquesIn this manuscript, we present and study applied sampling strategies, with problems related to statistical learning. The goal is to deal with the problems that usually arise in a context of large data when the number of observations and their dimensionality constrain the learning process. We therefore propose to address this problem using two sampling strategies: - Accelerate the learning process by sampling the most helpful. - Simplify the problem by discarding some observations to reduce complexity and the size of the problem. We first consider the context of the binary classification, when the observations used to form a classifier come from a sampling / survey scheme and present a complex dependency structure. for which we establish bounds of generalization. Then we study the implementation problem of stochastic gradient descent when observations are drawn non uniformly. We conclude this thesis by studying the problem of graph reconstruction for which we establish new theoretical results
41
Feoktistov, Vitaliy. "Contribution à l'évolution différentielle." Paris, ENMP, 2004. http://www.theses.fr/2004ENMP1248.
Full textAbstract:
Le domaine des algorithmes évolutionnaires a connu un grand développement ces dernières années. L'évolution différentielle (ED) est l'un de ces algorithmes. À l'origine, l'ED était conçue pour les problèmes d'optimisation continus et sans contraintes. Ses extensions actuelles peuvent traiter des problèmes en variables mixtes sous contraintes non linéaires. Depuis, l'ED est devenue une méthode efficace pour une grande quantité de problèmes réels. L'objectif principal de cette thèse était de proposer une analyse exhaustive de cette méthode : sur un plan scientifique de la situer par rapport aux méthodes plus classiques concurrentes et sur un plan technique d'améliorer son taux de convergence et d'augmenter sa capacité à trouver l'optimum global. Dans ce dessein, nous dégageons dans l'algorithme trois niveaux hiérarchiques à améliorer. Au premier niveau le comportement d'un individu a été étudié. Une formule universelle de la variation d'individu est mise au point : elle permet d'envisager la création d'un grand nombre de stratégies d'exploration et d'exploitation de l'espace de recherche. Une généralisation de l'algorithme est réalisée en introduisant l'ED transversale. Au deuxième niveau, la population entière est considérée. Afin d'accélérer la convergence, le principe de la sélection énergétique a été mis au point et testé, il permet de retenir les individus réputés les meilleurs. Une interaction de l'algorithme principal avec une méthode de régression externe est réalisée pour compléter la sélection des individus les plus intéressants et augmenter in fine le taux de convergence. Concrètement, ce troisième niveau implémente l'interaction entre l'ED et SVMFor the past few years the evolutionary computation domain has developed more and more rapidly. Differential Evolution (DE) is one of its representatives. Originally proposed for continuous unconstraint optimization, it has been enlarged into both mixed optimization and handling nonlinear constraints. Since then, DE becomes a leading method for a huge number of real problems. The main objective of this thesis was to propose an exhaustive analysis of this method : scientifically, to situate it with respect to the more classical concurrent methods and, technically, to improve its convergence rate as well as to increase its capacity to find the global optimum. For this purpose, we emphasize in the algorithm three hierarchical levels of improvement. At the first level, the individual behaviour has been investigated. A universal formula of the individual's variation is elaborated : it permits to accomplish the creation of a great number of strategies of exploration and exploitation of the search space. A generalization of the algorithm is realized by introducing transversal DE. At the second level, the entire population has been considered. In order to accelerate the convergence, the energetic selection principle has been developed and tested. This principle permits to retain the current best individuals. An interaction of the main algorithm with an external regression method has been realized in order to complete the selection by the most interesting individuals and to increase in fine the convergence rate. Concretely, the third level implements the interaction between DE and Support Vector Machine
42
DRIANCOURT, XAVIER. "Optimisation par descente de gradient stochastique de systemes modulaires combinant reseaux de neurones et programmation dynamique. Application a la reconnaissance de la parole." Paris 11, 1994. http://www.theses.fr/1994PA112203.
Full textAbstract:
Ce memoire est consacre a l'etude de systemes modulaires associant reseaux de neurones (mlp) et programmation dynamique (dp), ainsi qu'a leur application a la reconnaissance de la parole. Il est divise en trois parties. La premiere partie traite des fondements. Il arrive qu'un probleme n'ait pas trouve de solution analytique mais soit decrit par des exemples et par un critere d'erreur, permettant l'usage de procedures de descente de gradient stochastique. Nous etablissons un nouveau theoreme de convergence generalisant le theoreme de bottou. La reconnaissance des formes emploie generalement des criteres d'erreur constants par paliers, impropres a l'optimisation par descente de gradient. Il faut contourner le probleme, via les probabilites a posteriori ou via les vraissemblances conditionnelles ou encore en lissant le risque empirique: nous introduisons lvq2+. La deuxieme partie est consacree aux algorithmes, notamment systemes modulaires pour la reconnaissance de formes temporelles. Nous mettons en evidence le codage ponctuel, phenomene d'abberration propre aux systemes compose d'un filtre suivit d'un module de plus-proches voisins. Nous proposons deux familles de solutions dont l'usage de criteres d'erreur adimensionels tels que lvq2+. Ceci permet d'optimiser des systemes modulaires combinant un filtre neuronal mlp avec un module plus proche voisin dont la metrique est induite par la programmation dynamique dp. La troisieme partie est consacree a une tache reelle de reconnaissance de la parole. Nous comparons differents systemes: dp, reseaux neuronaux a delais, reseaux recurrents, kmeans, lvq nos systemes modulaires divisent par trois l'erreur des autres systemes. L'optimisation simultanee des differents modules permet au module dp de se contenter d'une reference par classe
43
Lê, Cao Kim-Anh. "Outils statistiques pour la sélection de variables et l'intégration de données "omiques"." Toulouse, INSA, 2008. http://eprint.insa-toulouse.fr/archive/00000225/.
Full textAbstract:
Les récentes avancées bio technologiques permettent maintenant de mesurer une énorme quantité de données biologiques de différentes sources (données génomiques, protéomiques, métabolomiques, phénotypiques), souvent caractérisées par un petit nombre d'échantillons ou d'observations. L'objectif de ce travail est de développer ou d'adapter des méthodes statistiques adéquates permettant d'analyser ces jeux de données de grande dimension, en proposant aux biologistes des outils efficaces pour sélectionner les variables les plus pertinentes. Dans un premier temps, nous nous intéressons spécifiquement aux données de transcriptome et à la sélection de gènes discriminants dans un cadre de classification supervisée. Puis, dans un autre contexte, nous cherchons à sélectionner des variables de types différents lors de la réconciliation (ou l'intégration) de deux tableaux de données omiques. Dans la première partie de ce travail, nous proposons une approche de type wrapper en agrégeant des méthodes de classification (CART, SVM) pour sélectionner des gènes discriminants une ou plusieurs conditions biologiques. Dans la deuxième partie, nous développons une approche PLS avec pénalisation l1 dite de type sparse car conduisant à un ensemble "creux" de paramètres, permettant de sélectionner des sous-ensembles de variables conjointement mesurées sur les mêmes échantillons biologiques. Un cadre de régression, ou d'analyse canonique est proposé pour répondre spécifiquement à la question biologique. Nous évaluons chacune des approches proposées en les comparant sur de nombreux jeux de données réels à des méthodes similaires proposées dans la littérature. Les critères statistiques usuels que nous appliquons sont souvent limités par le petit nombre d'échantillons. Par conséquent, nous nous efforçons de toujours combiner nos évaluations statistiques avec une interprétation biologique détaillée des résultats. Les approches que nous proposons sont facilement applicables et donnent des résultats très satisfaisants qui répondent aux attentes des biologistesRecent advances in biotechnology allow the monitoring of large quantities of biological data of various types, such as genomics, proteomics, metabolomics, phenotypes. . . , that are often characterized by a small number of samples or observations. The aim of this thesis was to develop, or adapt, appropriate statistical methodologies to analyse highly dimensional data, and to present efficient tools to biologists for selecting the most biologically relevant variables. In the first part, we focus on microarray data in a classification framework, and on the selection of discriminative genes. In the second part, in the context of data integration, we focus on the selection of different types of variables with two-block omics data. Firstly, we propose a wrapper method, which agregates two classifiers (CART or SVM) to select discriminative genes for binary or multiclass biological conditions. Secondly, we develop a PLS variant called sparse PLS that adapts l1 penalization and allows for the selection of a subset of variables, which are measured from the same biological samples. Either a regression or canonical analysis frameworks are proposed to answer biological questions correctly. We assess each of the proposed approaches by comparing them to similar methods known in the literature on numerous real data sets. The statistical criteria that we use are often limited by the small number of samples. We always try, therefore, to combine statistical assessments with a thorough biological interpretation of the results. The approaches that we propose are easy to apply and give relevant results that answer the biologists needs
44
Phi, Tien Cuong. "Décomposition de Kalikow pour des processus de comptage à intensité stochastique." Thesis, Université Côte d'Azur, 2022. http://www.theses.fr/2022COAZ4029.
Full textAbstract:
L'objectif de cette thèse est de construire des algorithmes capables de simuler l'activité d'un réseau de neurones. L'activité du réseau de neurones peut être modélisée par le train de spikes de chaque neurone, qui sont représentés par un processus ponctuel multivarié. La plupart des approches connues pour simuler des processus ponctuels rencontrent des difficultés lorsque le réseau sous-jacent est de grande taille.Dans cette thèse, nous proposons de nouveaux algorithmes utilisant un nouveau type de décomposition de Kalikow. En particulier, nous présentons un algorithme permettant de simuler le comportement d'un neurone intégré dans un réseau neuronal infini sans simuler l'ensemble du réseau. Nous nous concentrons sur la preuve mathématique que notre algorithme renvoie les bons processus ponctuels et sur l'étude de sa condition d'arrêt. Ensuite, une preuve constructive montre que cette nouvelle décomposition est valable pour divers processus ponctuels.Enfin, nous proposons des algorithmes, qui peuvent être parallélisés et qui permettent de simuler une centaine de milliers de neurones dans un graphe d'interaction complet, sur un ordinateur portable. Plus particulièrement, la complexité de cet algorithme semble linéaire par rapport au nombre de neurones à simulerThe goal of this thesis is to construct algorithms which are able to simulate the activity of a neural network. The activity of the neural network can be modeled by the spike train of each neuron, which are represented by a multivariate point processes. Most of the known approaches to simulate point processes encounter difficulties when the underlying network is large.In this thesis, we propose new algorithms using a new type of Kalikow decomposition. In particular, we present an algorithm to simulate the behavior of one neuron embedded in an infinite neural network without simulating the whole network. We focus on mathematically proving that our algorithm returns the right point processes and on studying its stopping condition. Then, a constructive proof shows that this new decomposition holds for on various point processes.Finally, we propose algorithms, that can be parallelized and that enables us to simulate a hundred of thousand neurons in a complete interaction graph, on a laptop computer. Most notably, the complexity of this algorithm seems linear with respect to the number of neurons on simulation
45
VIALA, JEAN-RENAUD. "Apprentissage de reseaux de neurones en couches par la regle de retropropagation du gradient : developpement d'un algorithme competitif pour la compression et la segmentation d'images." Paris 6, 1990. http://www.theses.fr/1990PA066802.
Full textAbstract:
Cette these aborde les differents aspects des reseaux de neurones en couches appeles perceptrons multicouches, depuis l'algorithme d'apprentissage, jusqu'a l'application a des problemes reels. La premiere partie est une etude parametrique de la regle d'apprentissage par retropropagation du gradient de l'erreur. Le gain et le temps de relaxation sont etudies lors de l'elaboration d'une loi d'echelle d'une fonction booleenne: la parite. Les architectures de reseau et les ensembles d'apprentissage sont analyses sur le probleme continu de la compression d'une image digitalisee. La deuxieme partie de la these est une application des reseaux de neurones en couches au probleme de la compression de signal video. Pour obtenir une qualite d'image satisfaisante, un nouvel algorithme a ete developpe. Son originalite est de mettre en competition, durant le codage, plusieurs reseaux en couches. Grace a l'apprentissage, qui associe chaque perceptron a une texture specifique, l'algorithme competitif adapte le codage d'un bloc de l'image en fonction de ses caracteristiques. Les simulations sur une sequence animee donnent des performances proches de celles obtenues par un algorithme non neuronal de compression par transformee en cosinus discrets. Les segmentations delivrees sont proches des objets figurant sur l'image. Cet algorithme peut etre implante en temps reel sur des circuits neuromimetiques elabores au laboratoire d'electronique philips
46
Baji, Bruno. "Quelques contributions à des systèmes dynamiques et algorithmes issus de la mécanique non-régulière et de l'optimisation." Montpellier 2, 2009. http://www.theses.fr/2009MON20007.
Full textAbstract:
La thèse porte sur l'analyse mathématique de problèmes issus de la mécanique unilatérale et de l'optimisation. Dans une première partie, nous étudions les propriétés d'un algorithme de type proximal qui peut être interprété comme l'équation discrétisée d'un oscillateur non linéaire soumis à des forces de frottement modélisés par un opérateur sous-différentiel. On étend l'étude au cadre général des opérateurs maximaux monotones dans un espace de Hilbert. Sous certaines conditions, la suite générée par l'algorithme est fortement convergente et sa limite est atteinte en un nombre fini d'itérations. Sinon, dans un contexte plus large, nous prouvons que la convergence est géométrique. Dans une deuxième partie, nous étudions un système dynamique continu : une équation des ondes amorties par un frottement sec avec conditions de Dirichlet au bord. Après avoir établi l'existence et l'unicité d'une solution du système, l'objectif principal est d'en étudier les propriétés asymptotiques. Dans deux situations significatives, on met en évidence un phénomène de dichotomie : la solution converge en temps fini, ou bien la convergence est exponentielle. Des conditions sont également données qui garantissent la stabilisation en temps fini du système vers une solution stationnaire. Une autre partie de la thèse est consacrée à l'étude de l'algorithme de gradient à pas variable. Le but est de montrer l'intérêt de prendre en compte la notion de courbure dans les méthodes de gradient. Nous obtenons des résultats de convergence linéaire sans condition de forte convexité. Des variantes de l'algorithme sont également étudiées notamment en considérant différentes expressions du pas dépendant de la courbure. Une large partie de l'étude porte sur la version implicite du schéma, rentrant ainsi dans le champ des méthodes du point proximal.
47
Moulard, Laurence. "Optimisation de maillages non structurés : applications à la génération, à la correction et à l'adaptation." Université Joseph Fourier (Grenoble), 1994. http://www.theses.fr/1994GRE10173.
Full textAbstract:
Nous traitons les problèmes lies aux maillages non structures par des méthodes d'optimisation utilisant des algorithmes d'exploration locale. Le principe consiste à partir d'une solution existante et a l'améliorer grâce a des opérations élémentaires. L'intérêt de cette approche est de pouvoir modifier localement la solution initiale pour qu'elle réponde a des contraintes ou des critères qui peuvent évoluer. On évite ainsi la reconstruction couteuse d'un nouveau maillage à chaque nouvelle demande des utilisateursUne étude théorique introduit de nouveaux objets, les tétraphores réalisables, en considérant les seules conditions topologiques d'un maillage. Ces objets se construisent facilement à partir de la frontière du domaine à mailler ; il suffit d'ajouter des contraintes géométriques, très simples à tester et pouvant se traduire sous la forme d'un critère à optimiser, pour obtenir un maillage. Des opérations transformant ces tétraphores sont définies. Les algorithmes d'optimisation sont ainsi bien plus efficaces car ils peuvent être appliques sur un ensemble plus vaste que les maillages
Les algorithmes décrits dans cette thèse sont utilisés industriellement. Des résultats sont donnes pour l'optimisation selon des critères géométriques et topologiques, l'adaptation selon un critère de densité, la correction après déformation des frontières et la génération de maillages
48
Loulidi, Sanae. "Modélisation stochastique en finance, application à la construction d’un modèle à changement de régime avec des sauts." Thesis, Bordeaux 1, 2008. http://www.theses.fr/2008BOR13675/document.
Full textAbstract:
Le modèle de Blacket Scholes reste le modèle de référence sur les marchés des dérivés. Sa parcimonie et sa maniabilité sont certes attractives. Il ne faut cependant pas perdre de vue les hypothèses restrictives, voire simplistes, qui lui servent de base et qui limitent sa capacité à reproduire la dynamique du marché. Afin de refléter un peu mieux cette dynamique, nous introduisons un modèle d’évaluation des options à changement de régime avec sauts. Sous ce modèle, l’hypothèse de complétude des marchés n’est plus valable. Les sources d’incertitude sont plus nombreuses que les instruments disponibles à la couverture. On ne parle plus de réplication/couverture parfaite mais plutôt de réplication optimale dans un sens à définir. Dans cette thèse, on suppose que le marché peut être décrit par plusieurs «régimes» (ou encore par des «modes») re?étant l’état de l’économie, le comportement général des investisseurs et leurs tendances. Pour chacun de ces régimes, le sous-jacent est caractérisé par un niveau de volatilité et de rendement donné. Avec en plus, et a priori des discontinuités du prix du sous-jacent à chaque fois qu’une transition d’un régime à un autre a lieu. La thèse comprend trois parties: 1.Modélisation du problème et application de la théorie du contrôle stochastique. Par l’utilisation du principe de programmation dynamique et la considération des différents régimes de marché, on aboutit à un système de M (le nombre de régimes) équations de Hamilton Jacobi Bellman «HJB» couplées. 2.La résolution numérique de l’équation HJB pour l’évolution d’options, par différences finies généralisées. 3.L’estimation des paramètres du modèle par un filtre récursif, qui produit une estimation récursive d’un état inconnu au vu d’observation bruitée supposée continue, dans le cas où l’état inconnu serait modélisé par une chaîne de Markov à temps discret et espace d’état finiAbstract
49
Allaya, Mouhamad M. "Méthodes de Monte-Carlo EM et approximations particulaires : application à la calibration d'un modèle de volatilité stochastique." Thesis, Paris 1, 2013. http://www.theses.fr/2013PA010072/document.
Full textAbstract:
Ce travail de thèse poursuit une perspective double dans l'usage conjoint des méthodes de Monte Carlo séquentielles (MMS) et de l'algorithme Espérance-Maximisation (EM) dans le cadre des modèles de Markov cachés présentant une structure de dépendance markovienne d'ordre supérieur à 1 au niveau de la composante inobservée. Tout d'abord, nous commençons par un exposé succinct de l'assise théorique des deux concepts statistiques à Travers les chapitres 1 et 2 qui leurs sont consacrés. Dans un second temps, nous nous intéressons à la mise en pratique simultanée des deux concepts au chapitre 3 et ce dans le cadre usuel ou la structure de dépendance est d'ordre 1, l'apport des méthodes MMS dans ce travail réside dans leur capacité à approximer efficacement des fonctionnelles conditionnelles bornées, notamment des quantités de filtrage et de lissage dans un cadre non linéaire et non gaussien. Quant à l'algorithme EM, il est motivé par la présence à la fois de variables observables, et inobservables (ou partiellement observées) dans les modèles de Markov Cachés et singulièrement les modèles de volatilité stochastique étudié. Après avoir présenté aussi bien l'algorithme EM que les méthodes MCS ainsi que quelques une de leurs propriétés dans les chapitres 1 et 2 respectivement, nous illustrons ces deux outils statistiques au travers de la calibration d'un modèle de volatilité stochastique. Cette application est effectuée pour des taux change ainsi que pour quelques indices boursiers au chapitre 3. Nous concluons ce chapitre sur un léger écart du modèle de volatilité stochastique canonique utilisé ainsi que des simulations de Monte Carlo portant sur le modèle résultant. Enfin, nous nous efforçons dans les chapitres 4 et 5 à fournir les assises théoriques et pratiques de l'extension des méthodes Monte Carlo séquentielles notamment le filtrage et le lissage particulaire lorsque la structure markovienne est plus prononcée. En guise d’illustration, nous donnons l'exemple d'un modèle de volatilité stochastique dégénéré dont une approximation présente une telle propriété de dépendanceThis thesis pursues a double perspective in the joint use of sequential Monte Carlo methods (SMC) and the Expectation-Maximization algorithm (EM) under hidden Markov models having a Markov dependence structure of order grater than one in the unobserved component signal. Firstly, we begin with a brief description of the theoretical basis of both statistical concepts through Chapters 1 and 2 that are devoted. In a second hand, we focus on the simultaneous implementation of both concepts in Chapter 3 in the usual setting where the dependence structure is of order 1. The contribution of SMC methods in this work lies in their ability to effectively approximate any bounded conditional functional in particular, those of filtering and smoothing quantities in a non-linear and non-Gaussian settings. The EM algorithm is itself motivated by the presence of both observable and unobservable ( or partially observed) variables in Hidden Markov Models and particularly the stochastic volatility models in study. Having presented the EM algorithm as well as the SMC methods and some of their properties in Chapters 1 and 2 respectively, we illustrate these two statistical tools through the calibration of a stochastic volatility model. This application is clone for exchange rates and for some stock indexes in Chapter 3. We conclude this chapter on a slight departure from canonical stochastic volatility model as well Monte Carlo simulations on the resulting model. Finally, we strive in Chapters 4 and 5 to provide the theoretical and practical foundation of sequential Monte Carlo methods extension including particle filtering and smoothing when the Markov structure is more pronounced. As an illustration, we give the example of a degenerate stochastic volatility model whose approximation has such a dependence property
50
Riff-Rojas, Maria-Cristina. "Résolution de problèmes de satisfaction de contraintes avec des algorithmes évolutionnistes." Phd thesis, Ecole Nationale des Ponts et Chaussées, 1997. http://tel.archives-ouvertes.fr/tel-00523169.
Full textAbstract:
Dans les disciplines de l'intelligence artificielle et de la recherche opérationnelle, on rencontre de nombreux problèmes comme l'allocation de ressources, l'ordonnancement, la, conception, le diagnostic automatisé. Ces problèmes se formulent aisément comme des problèmes de satisfaction de contraintes (CSP). Un CSP est défini comme étant un ensemble de contraintes impliquant un certain nombre de variables. L'objectif consiste simplement à trouver un ensemble de valeurs à affecter aux variables, de sorte que toutes les contraintes soient satisfaites. Dans le cas le plus général, les problèmes de satisfaction de contraintes ont un aspect fortement combinatoire qui leur confère une grande complexité. Nous nous intéressons dans le cadre de cette thèse aux problèmes de satisfaction de contraintes binaires en domaines finis. Les méthodes auxquelles nous nous intéressons pour résoudre un CSP sont, les méthodes dites incomplètes : elles font une réparation d'une configuration en parcourant de manière non systématique l'espace des configurations. Dans cette catégorie de méthodes, notre intérêt s'est plus particulièrement tourné vers les Algorithmes Evolutionnistes. Ce sont des méthodes générales d'optimisation combinatoire qui sont inspirées de la théorie de l'évolution. Dans un CSP classique, on recherche une solution, sans avoir à optimiser de fonction. Pour entrer dans le cadre des Algorithmes Évolutionnistes, on se doit de définir une fonction d'évaluation pour les CSP qui prend ses valeurs minimales sur les solutions du problème. Cette fonction pourrait être utilisée par toutes méthodes incomplètes, telles que les techniques min-conflits, GSAT et leurs variantes. Nous montrons dans cette thèse l'application de notre fonction d'évaluation pour la méthode min-conflits ainsi que pour un algorithme évolutionniste. D'un autre côté, dans le contexte plus spécifique des algorithmes génétiques, nous souhaitons guider l'évolution (i.e. recherche d'une solution), en faisant des transformations sur la population plus orientées vers le problème de satisfaction de contraintes. Nous définissons ainsi des opérateurs de mutation et de croisement spécialisés pour les CSP qui sont basés sur la structure du graphe de contraintes. Ensuite, nous incorporons le concept d'adaptation dans l'opérateur de croisement, afin d'améliorer la recherche de l'algorithme. Dans ce mémoire, nous décrivons et justifions les algorithmes mis en oeuvre, en illustrant les techniques implémentées par la résolution de problèmes de coloriage de graphe avec trois couleurs, et de CSP générés aléatoirement.