Dissertations / Theses on the topic 'Markov approximation'
To see the other types of publications on this topic, follow the link: Markov approximation.
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 'Markov approximation.'
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
Szczegot, Kamil. "Sharp approximation for density dependent Markov chains /." May be available electronically:, 2009. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full text
2
Pötzelberger, Klaus. "On the Approximation of finite Markov-exchangeable processes by mixtures of Markov Processes." Department of Statistics and Mathematics, WU Vienna University of Economics and Business, 1991. http://epub.wu.ac.at/526/1/document.pdf.
Full textAbstract:
We give an upper bound for the norm distance of (0,1) -valued Markov-exchangeable random variables to mixtures of distributions of Markov processes. A Markov-exchangeable random variable has a distribution that depends only on the starting value and the number of transitions 0-0, 0-1, 1-0 and 1-1. We show that if, for increasing length of variables, the norm distance to mixtures of Markov processes goes to 0, the rate of this convergence may be arbitrarily slow. (author's abstract)Series: Forschungsberichte / Institut für Statistik
3
Perrine, Serge. "Approximation diophantienne (théorie de Markoff)." Metz, 1988. http://docnum.univ-lorraine.fr/public/UPV-M/Theses/1988/Perrine.Serge_1.SMZ8826.pdf.
Full textAbstract:
Vers 1880, A. Markoff a précisé la structure de l'ensemble des constantes d'approximations des nombres irrationnels plus grandes que 1/3. Sa théorie établit un lien entre ces constantes, des minima arithmétiques de formes quadratiques, et les solutions entières de l'équation diophantienne x2 + y2 +z2 = 3xyz. La présente thèse généralise le formalisme original de Markoff. Ceci introduit la notion de (a,r, E) - théorie de Markoff, dont la (2,0,-1) -théorie recouvre les calculs originaux. L'équation diophantienne correspondante est donnée ainsi qu'une interprétation des calculs. Il en résulte la résolution de l'équation diophantienne x2 + y2 +z2 = (a +1)xyz et diverses constructions arborescentes. Pour la recherche systématique des trous des spectres de Markoff et Perron, l'auteur confirme les résultatd de Scheker et Freiman concernant le rayon de Hall. Il donne des exemples et confirme certains résultats de Kinney et PitcherTowards 1880, A. Markoff gave precisions about structure of the set of approximation constants greater than 1/3 for irrational numbers. This theory establishes links between constants, arithmetical minima for quadratic forms, and the solutions of the diophantine equation x2 + y2 +z2 = 3xyz. The present dissertation generalizes the original formalism built by Markoff. It introduces the notion of (a, r,E)-theory of Markoff, among which the (2,0,-1) theory is the original Markoff theory. The corresponding diophantine equation is given with an interpretation for the whole calculus. From that is derives the resolution of the diophantine equation x2 + y2 +z2 = (a +1)xyz and some arborescent constructions. For the systematic research of holes in the Markoff's spectra, the author gives confirmation for the results of Schecker and Freiman, concerning the Hall's ray. He gives examples and gives confirmation for some results of Kinney and Pitcher
4
Patrascu, Relu-Eugen. "Linear Approximations For Factored Markov Decision Processes." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1171.
Full textAbstract:
A Markov Decision Process (MDP) is a model employed to describe problems in which a decision must be made at each one of several stages, while receiving feedback from the environment. This type of model has been extensively studied in the operations research community and fundamental algorithms have been developed to solve associated problems. However, these algorithms are quite inefficient for very large problems, leading to a need for alternatives; since MDP problems are provably hard on compressed representations, one becomes content even with algorithms which may perform well at least on specific classes of problems. The class of problems we deal with in this thesis allows succinct representations for the MDP as a dynamic Bayes network, and for its solution as a weighted combination of basis functions. We develop novel algorithms for producing, improving, and calculating the error of approximate solutions for MDPs using a compressed representation. Specifically, we develop an efficient branch-and-bound algorithm for computing the Bellman error of the compact approximate solution regardless of its provenance. We introduce an efficient direct linear programming algorithm which, using incremental constraints generation, achieves run times significantly smaller than existing approximate algorithms without much loss of accuracy. We also show a novel direct linear programming algorithm which, instead of employing constraints generation, transforms the exponentially many constraints into a compact form more amenable for tractable solutions. In spite of its perceived importance, the efficient optimization of the Bellman error towards an approximate MDP solution has eluded current algorithms; to this end we propose a novel branch-and-bound approximate policy iteration algorithm which makes direct use of our branch-and-bound method for computing the Bellman error. We further investigate another procedure for obtaining an approximate solution based on the dual of the direct, approximate linear programming formulation for solving MDPs. To address both the loss of accuracy resulting from the direct, approximate linear program solution and the question of where basis functions come from we also develop a principled system able not only to produce the initial set of basis functions, but also able to augment it with new basis functions automatically generated such that the approximation error decreases according to the user's requirements and time limitations.
5
Lei, Lei. "Markov Approximations: The Characterization of Undermodeling Errors." Diss., CLICK HERE for online access, 2006. http://contentdm.lib.byu.edu/ETD/image/etd1371.pdf.
Full text
6
Kuntz, Nussio Juan. "Deterministic approximation schemes with computable errors for the distributions of Markov chains." Thesis, Imperial College London, 2017. http://hdl.handle.net/10044/1/59103.
Full textAbstract:
This thesis is a monograph on Markov chains and deterministic approximation schemes that enable the quantitative analysis thereof. We present schemes that yield approximations of the time-varying law of a Markov chain, of its stationary distributions, and of the exit distributions and occupation measures associated with its exit times. In practice, our schemes reduce to solving systems of linear ordinary differential equations, linear programs, and semidefinite pro- grams. We focus on the theoretical aspects of these schemes, proving convergence and providing computable error bounds for most of them. To a lesser extent, we study their practical use, applying them to a variety of examples and discussing the numerical issues that arise in their implementation.
7
Tanaka, Takeyuki. "Studies on Application of a Markov Approximation Methods to Structural Reliability Analyses." Kyoto University, 1995. http://hdl.handle.net/2433/160776.
Full textAbstract:
本文データは平成22年度国立国会図書館の学位論文(博士)のデジタル化実施により作成された画像ファイルを基にpdf変換したものであるKyoto University (京都大学)
0048
新制・論文博士
博士(工学)
乙第8872号
論工博第2981号
新制||工||997(附属図書館)
UT51-95-D465
(主査)教授 宗像 豊哲, 教授 茨木 俊秀, 教授 岩井 敏洋
学位規則第4条第2項該当
8
Vergne, Nicolas. "Chaînes de Markov régulées et approximation de Poisson pour l'analyse de séquences biologiques." Phd thesis, Université d'Evry-Val d'Essonne, 2008. http://tel.archives-ouvertes.fr/tel-00322434.
Full textAbstract:
L'analyse statistique des séquences biologiques telles les séquences nucléotidiques (l'ADN et l'ARN) ou d'acides aminés (les protéines) nécessite la conception de différents modèles s'adaptant chacun à un ou plusieurs cas d'étude. Etant donnée la dépendance de la succession des nucléotides dans les séquences d'ADN, les modèles généralement utilisés sont des modèles de Markov. Le problème de ces modèles est de supposer l'homogénéité des séquences. Or, les séquences biologiques ne sont pas homogènes. Un exemple bien connu est la répartition en gc : le long d'une même séquence, alternent des régions riches en gc et des régions pauvres en gc. Pour rendre compte de l'hétérogénéité des séquences, d'autres modèles sont utilisés : les modèles de Markov cachés. La séquence est divisée en plusieurs régions homogènes. Les applications sont nombreuses, telle la recherche des régions codantes. Certaines particularités biologiques ne pouvant apparaître suivant ces modèles, nous proposons de nouveaux modèles, les chaînes de Markov régulées (DMM pour drifting Markov model). Au lieu d'ajuster une matrice de transition sur une séquence entière (modèle de Markov homogène classique) ou différentes matrices de transition sur différentes régions de la séquence (modèles de Markov cachés), nous permettons à la matrice de transition de varier (to drift) du début à la fin de la séquence. A chaque position t dans la séquence, nous avons une matrice de transition Πt/n(où n est la longueur de la séquence) éventuellement différente. Nos modèles sont donc des modèles de Markov hétérogènes contraints. Dans cette thèse, nous donnerons essentiellement deux manières de contraindre les modèles : la modélisation polynomiale et la modélisation par splines. Par exemple, pour une modélisation polynomiale de degré 1 (une dérive linéaire), nous nous donnons une matrice de départ Π0 et une matrice d'arrivée Π1 puis nous passons de l'une à l'autre en fonction de la position t dans la séquence : Πt/n = (1-t/n) Π0 + t/n Π1.
Cette modélisation correspond à une évolution douce entre deux états. Par exemple cela peut traduire la transition entre deux régimes d'un chaîne de Markov cachée, qui pourrait parfois sembler trop brutale. Ces modèles peuvent donc être vus comme une alternative mais aussi comme un outil complémentaire aux modèles de Markov cachés. Tout au long de ce travail, nous avons considéré des dérives polynomiales de tout degré ainsi que des dérives par splines polynomiales : le but de ces modèles étant de les rendre plus flexibles que ceux des polynômes. Nous avons estimé nos modèles de multiples manières puis évalué la qualité de ces estimateurs avant de les utiliser en vue d'applications telle la recherche de mots exceptionnels. Nous avons mis en oeuvre le software DRIMM (bientôt disponible à http://stat.genopole.cnrs.fr/sg/software/drimm/, dédié à l'estimation de nos modèles. Ce programme regroupe toutes les possibilités offertes par nos modèles, tels le calcul des matrices en chaque position, le calcul des lois stationnaires, des distributions de probabilité en chaque position... L'utilisation de ce programme pour la recherche des mots exceptionnels est proposée dans des programmes auxiliaires (disponibles sur demande).
Plusieurs perspectives à ce travail sont envisageables. Nous avons jusqu'alors décidé de faire varier la matrice seulement en fonction de la position, mais nous pourrions prendre en compte des covariables tels le degré d'hydrophobicité, le pourcentage en gc, un indicateur de la structure des protéines (hélice α, feuillets β...). Nous pourrions aussi envisager de mêler HMM et variation continue, où sur chaque région, au lieu d'ajuster un modèle de Markov, nous ajusterions un modèle de chaînes de Markov régulées.
9
GENDRE, LAURENT. "INEGALITES DE MARKOV SINGULIERES ET APPROXIMATION DES FONCTIONS HOLOMORPHES DE LA CLASSE M." Phd thesis, Université Paul Sabatier - Toulouse III, 2005. http://tel.archives-ouvertes.fr/tel-00010810.
Full textAbstract:
En premier, nous montrons l'existence d'inégalités de Markov sur les courbes algébriques singulières de Rn. Nous donnons une signification géométrique à l'exposant de Markov en montrant qu'il est minoré par la multiplicité de la singularité de la courbe complexifiée dans Cn. Nous construisons une paramétrisation de Puiseux en la singularité réelle de la courbe complexifiée. Nous la prolongeons à un ouvert de C partout dense, afin d'obtenir la propriété d'HCP de la fonction de Green avec pôle à l'infini dans la courbe complexifiée, via la métrique des géodésiques. En second, nous montrons un théorème de type Bernstein pour les classes de fonctions intermédiaires entre les fonctions holomorphes et les fonctions indéfiniment différentiables sur des classes de compacts s-H convexes de Cn . Pour démontrer ce résultat, nous donnons une représentation intégrale sur les compacts s-H convexes de Cn des fonctions de A¥(K) via un noyau adéquat , nous approchons ce noyau par les noyaux à poids de type Henkin-Ramirez. Nous proposons une nouvelle propriété géométrique de la fonction de Green avec pôle à l'infini. Pour finir nous donnons quelques applications et corollaires.
10
Gendre, Laurent. "Inégalités de Markov singulières et approximation des fonctions holomorphes de la classe M." Toulouse 3, 2005. http://www.theses.fr/2005TOU30033.
Full textAbstract:
En premier, nous montrons l'existence d'inégalités de Markov sur les courbes algébriques singulières de Rn. Nous donnons une signification géométrique à l'exposant de Markov en montrant qu'il est minoré par la multiplicité de la singularité de la courbe complexifiée dans Cn. Nous construisons une paramétrisation de Puiseux en la singularité réelle de la courbe complexifiée. Nous la prolongeons à un ouvert de C partout dense, afin d'obtenir la propriété d'HCP de la fonction de Green avec pôle à l'infini dans la courbe complexifiée, via la métrique des géodésiques. En second, nous montrons un théorème de type Bernstein pour les classes de fonctions intermédiaires entre les fonctions holomorphes et les fonctions indéfiniment différentiables sur des classes de compacts s-H convexes de Cn. Pour démontrer ce résultat, nous donnons une représentation intégrale sur les compacts s-H convexes de Cn des fonctions de A¥(K) via un noyau adéquat , nous approchons ce noyau par les noyaux à poids de type Henkin-Ramirez. Nous proposons une nouvelle propriété géométrique de la fonction de Green avec pôle à l'infini. Pour finir nous donnons quelques applications et corollairesIn the first part, we prove that all the singular algebraic curves of Rn admit Markov tangential inequalities. We give a geometric signification of the Markov exponent. We prove that this exponent is less or equal to the multiplicity of the singularity of the complexify curve in Cn. We construct a Puiseux parameterisation on the real singularity and we extended it to a nowhere dense open subset of C. Therefore, we obtain the property HCP of the Green function with pole at infinity by geodesic metric in the complexify curve. In the second part, we prove a Bernstein type theorem for the functions of intermediate classes between holomorphic functions and C¥ functions on subclasses of s-H convex compact subsets of Cn. To prove this result, we give representative kernel on s-H convex compact for functions of A¥(K). We approach this kernel by an other kernel type Henkin-Ramirez. We propose a new geometric property of Green function with pole at infinity and we give some examples
11
Vergne, Nicolas Prum Bernard. "Chaînes de Markov régulées et approximation de Poisson pour l'analyse de séquences biologiques." S. l. : Evry-Val d'Essonne, 2008. http://www.biblio.univ-evry.fr/theses/2008/2008EVRY0006.pdf.
Full text
12
Sitaraman, Hariharakrishnan. "Approximation of a class of Markov-modulated Poisson processes with a large state-space." Diss., The University of Arizona, 1989. http://hdl.handle.net/10150/184828.
Full textAbstract:
Many queueing systems have an arrival process that can be modeled by a Markov-modulated Poisson process. The Markov-modulated Poisson process (MMPP) is a doubly stochastic Poisson process in which the arrival rate varies according to a finite state irreducible Markov process. In many applications of MMPPs, the point process is constructed by superpositions or similar constructions, which lead to modulating Markov processes with a large state space. Since this limits the feasibility of numerical computations, a useful problem is to approximate an MMPP represented by a large Markov process by one with fewer states. We focus our attention in particular, to approximating a simple but useful special case of the MMPP, namely the Birth and Death Modulated Poisson process. In the validation stage, the quality of the approximation is examined in relation to the MMPP/G/1 queue.
13
Haro, Antonio. "Example Based Processing For Image And Video Synthesis." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/5283.
Full textAbstract:
The example based processing problem can be expressed as: "Given an example of an image or video before and after processing, apply a similar processing to a new image or video".
Our thesis is that there are some problems where a single general algorithm can be used to create varieties of outputs, solely by presenting examples of what is desired to the algorithm. This is valuable if the algorithm to produce the output is non-obvious, e.g. an algorithm to emulate an example painting's style. We limit
our investigations to example based processing of images, video, and 3D models as these data types are easy to acquire and experiment with.
We represent this problem first as a texture synthesis influenced sampling problem, where the idea is to form feature vectors representative of the data and then sample them coherently to
synthesize a plausible output for the new image or video. Grounding the problem in this manner is useful as both problems involve learning the structure of training data under some assumptions to sample it properly. We then reduce the problem to a labeling problem to perform example based processing in a more generalized and principled manner than earlier techniques. This allows us to perform a different estimation of what the output
should be by approximating the optimal (and possibly not known) solution through a different approach.
14
Crudu, Alina. "Approximations hybrides de processus de Markov à sauts multi-échelles : applications aux modèles de réseaux de gènes en biologie moléculaire." Phd thesis, Université Rennes 1, 2009. http://tel.archives-ouvertes.fr/tel-00454886.
Full textAbstract:
L'objectif principal de cette thèse a été de développer des nouveaux outils mathématiques pour l'étude des phénomènes stochastiques en biologique moléculaire. Les modèles mathématiques pour la dynamique stochastique des réseaux de réactions biochimiques sont basés sur les processus de Markov à sauts. On propose des approximations hybrides pour les processus de Markov à sauts multi-échelles. En utilisant comme argument heuristique un développement limité du générateur du processus à sauts (procédé connu en chimie et en physique sous le nom de développement de Kramers-Moyal) nous identifions plusieurs types d'asymptotiques hybrides : processus déterministes par morceaux et diffusions hybrides. Le développement de Kramers-Moyal permet d'obtenir de manière systématique des modèles hybrides, qui sont simulés par la suite avec des algorithmes adaptés. Les approximations déterministes par morceaux sont étudiées avec des méthodes mathématiques rigoureuses. On montre la convergence faible du processus de Markov à sauts vers deux types de processus déterministes par morceaux : avec et sans sauts dans les variables continues. Les approximations hybrides peuvent être simplifiées davantage en utilisant des méthodes de moyennisation. On propose aussi quelques résultats dans cette direction.
15
Tracol, Mathieu. "Vérification approchée de systèmes probabilistes." Paris 11, 2010. http://www.theses.fr/2010PA112055.
Full textAbstract:
Dans cette thèse, nous considérons plusieurs types de Systèmes Probabilistes, qui modélisent le comportement de processus réels dans un environnement randomisé. De tels systèmes peuvent être des Protocoles de Communication, des Algorithmes exécutés sur des ordinateurs, des Systèmes Hybrides. . . Notre but est d'étudier leur évolution. Nous concentrons notre étude sur la comparaison quantitative de Systèmes Probabilistes, et sur l'analyse de leurs propriétés. Notre étude s'appuie sur les questions suivantes d'évaluation et de comparaison : *Étant donné le modèle d'un système réel, peut-on décider efficacement comment le système se comporte ? *Étant donnés deux modèles, comment peut-on les comparer ? Nous essayons de montrer que des algorithmes d'approximation peuvent être utiles pour l'étude de Systèmes Probabilistes. En particulier, nous montrons que des problèmes dont la solution exacte n'est pas calculable efficacement peuvent être résolus approximativement de manière efficace. Dans notre travail, nous utilisons quatres modèles de systèmes probabilistes : le modèle d'Automate Probabiliste Fini, que nous étendons au domaine des mots infinis, le modèle des Processus Markoviens avec Labels, le modèle des Processus de Décision Markoviens (MDP), et un modèle particulier de réseaux de MDPs. Nos résultats principaux concernent des méthodes de comparaison quantitatives entre systèmes, et des méthodes d'approximation de systèmes complexesLn this dissertation, we consider several types of probabilistic systems, which model the behaviors of real processes in a randomized environment. Such systems can be Communication Protocols, Algorithms executed on computers, Hybrid Systems. . . Our goal is to study their evolution. We focus our study on the quantitative comparison between Probabilistic Systems, and on the analysis of their properties. Our study relies on the following questions of evaluation and comparison: *Given the model of a real system, can we decide efficiently how the system behaves? *Given two models, how can we compare them? We try to prove that approximation algorithms can be usefuI for the analysis of Probabilistic Systems. Ln particular, we show that problems whose exact solution is not efficiently computable can be efficiently approximated. Ln our work, we use four models of probabilistic systems: the model of Finite Probabilistic Automata, on finite and infinite words, the model of Labeled Markov Processes, the model of Markovian Decision Processes (MDP), and a model of network of MDPs. Our main results concern quantitative comparison methods between systems, and approximation methods for complex systems
16
Cech, Markus. "Fahrspurschätzung aus monokularen Bildfolgen für innerstädtische Fahrerassistenzanwendungen." Karlsruhe Univ.-Verl. Karlsruhe, 2008. http://d-nb.info/994134843/04.
Full text
17
Fu, Shuting. "Bayesian Logistic Regression Model with Integrated Multivariate Normal Approximation for Big Data." Digital WPI, 2016. https://digitalcommons.wpi.edu/etd-theses/451.
Full textAbstract:
The analysis of big data is of great interest today, and this comes with challenges of improving precision and efficiency in estimation and prediction. We study binary data with covariates from numerous small areas, where direct estimation is not reliable, and there is a need to borrow strength from the ensemble. This is generally done using Bayesian logistic regression, but because there are numerous small areas, the exact computation for the logistic regression model becomes challenging. Therefore, we develop an integrated multivariate normal approximation (IMNA) method for binary data with covariates within the Bayesian paradigm, and this procedure is assisted by the empirical logistic transform. Our main goal is to provide the theory of IMNA and to show that it is many times faster than the exact logistic regression method with almost the same accuracy. We apply the IMNA method to the health status binary data (excellent health or otherwise) from the Nepal Living Standards Survey with more than 60,000 households (small areas). We estimate the proportion of Nepalese in excellent health condition for each household. For these data IMNA gives estimates of the household proportions as precise as those from the logistic regression model and it is more than fifty times faster (20 seconds versus 1,066 seconds), and clearly this gain is transferable to bigger data problems.
18
Bousfiha, Amina. "Approximation des systèmes semi-markoviens via les distributions de type phase et application en fiabilité." Compiègne, 1998. http://www.theses.fr/1998COMP1092.
Full textAbstract:
Les processus semi-markoviens sont des processus dont l'évolution future dépend du temps passé depuis la dernière transition ; ils sont fréquemment rencontrés en pratique. Ici nous nous intéressons à l'étude de la fiabilité des systèmes semi-markoviens. Leur principal inconvénient c'est la complexité des calculs pour l'obtention de la fonction de transition du processus, ce qui complique considérablement les calculs des indices de fiabilité, de performance, etc. Dans ce travail, nous nous proposons d'approximer les systèmes semi-markoviens par des systèmes markoviens en utilisant les distributions de type phase. Une distribution de type phase est une distribution de temps d'absorption d'un processus de Markov fini absorbant. Nous développons des méthodes pour approximer les fonctions de transition non exponentielles d'un système semi-markovien par des distributions de type phase. Ensuite, nous montrons comment construire le générateur du système markovien transformé. D'autre part, nous évaluons une borne sur la distance entre deux systèmes semi-markoviens. Ce résultat nous a permis de contrôler l'erreur commise sur la matrice des probabilités de transition et sur les indices de fiabilité, lors de l'approximation des systèmes semi-markoviens par des systèmes markoviens en utilisant les distributions de type phase.
19
Laroche, Pierre. "Processus décisionnels de Markov appliqués à la planification sous incertitude." Nancy 1, 2000. http://docnum.univ-lorraine.fr/public/SCD_T_2000_0012_LAROCHE.pdf.
Full textAbstract:
Un robot mobile évoluant dans un environnement dynamique doit faire face à de nombreuses incertitudes. Les actions qu'il exécute n'ont pas toujours l'effet escompté, et ses capteurs lui renvoient des données souvent bruitées. Les processus décisionnels de Markov (MDP), du fait de leur adaptation à la prise en compte d'incertitudes, sont étudiés depuis quelques années dans la communauté intelligence artificielle. Ceux-ci permettent le calcul d'un plan plus robuste que les méthodes de planification classiques, puisque calculé en prenant en compte les diverses conséquences probables des actions. Dans le cadre de la robotique mobile, ce modèle permet également de superviser l'exécution des missions, en utilisant des fonctions probabilistes pour aider le robot à se localiser. Mais les algorithmes classiques de résolution de MDP sont complexes, ce qui les rend difficilement adaptables à des environnements de grande taille, tels que ceux nécessités dans le cadre de la robotique. En conséquence, beaucoup de travaux s'intéressent aux techniques d'approximation, qui permettent d'obtenir des plans sous-optimaux en un temps de calcul réduit. C'est dans ce cadre que s'inscrit cette thèse. Apres avoir montré comment nous paramétrons un MDP pour l'appliquer à la robotique mobile, nous présentons deux techniques d'approximation. La première utilise l'agrégation d'états, chaque couloir de l'environnement donnant lieu à un ou plusieurs états abstraits. La seconde est fondée sur la décomposition d'environnements, lesquels sont représentés à l'aide d'un graphe value permettant d'approcher heuristiquement les valeurs des états. Ces deux méthodes permettent de réduire considérablement les temps de calcul, et donnent des plans très proches de l'optimal.
20
Sen, Sanjoy Kumar. "Analysis of Memory Interference in Buffered Multi-processor Systems in Presence of Hot Spots and Favorite Memories." Thesis, University of North Texas, 1995. https://digital.library.unt.edu/ark:/67531/metadc278426/.
Full text
21
Cottrell, Marie. "Modélisation de réseaux de neurones par des chaines de Markov et autres applications." Paris 11, 1988. http://www.theses.fr/1988PA112232.
Full textAbstract:
La première partie de la thèse consiste en un article publié (IEEE Trans. Aut. Control Vol. AC 28, n° 9, 1983), avec J. C. Fort et G. Malgouyres, qui propose deux méthodes d'évaluation du temps de sortie d'un bassin d'attraction pour une chaine de Markov ce temps étant extrêmement grand, on utilise pour cela un changement de probabilité exponentiel tant pour une méthode de simulation rapide que pour une approximation diffusion non standard. La deuxième partie comprend deux articles publiés avec J. C. Fort (Annales de l'IHP Probabilités et Statistiques vol. 23, n°1, 1987) et Biological Cybernetics (N° 53, 1986). Le premier donne une démonstration de la convergence de l'algorithme d'auto-organisation de Kohonen en dimension 1. Dans le second, nous définissons un algorithme d’auto-organisation qui est une version simplifiée de celui de Kohonen, et nous démontrons sa convergence en dimensions 1 et 2. Dans la troisième partie, publiée dans Biological Cybernetics (n°58, 1988) nous résolvons le problème du calcul de la matrice de connexions pour un réseau de neurones de type Mac Culloch et Pitts ou Hopfield, qui permette d'obtenir la plus grande attractivité possible, dans le cas de l'algorithme déterministe et de patrons non nécessairement orthogonaux. De plus nous calculons pour une matrice de connexion donnée l'attractivité de chaque patron mémorisé. La dernière partie est consacrée à l'étude du rôle de l'inhibition dans un réseau de neurones connectés aux plus proches voisins. Le modèle choisi est proche de la réalité biologique du cortex cérébelleux chez le jeune animal. On montre que tant que l'inhibition est plus faible qu'un certain seuil, le réseau est ergodique et que s'installe rapidement un régime stationnaire. Au contraire, lorsque l’inhibition s’accroit, on provoque des réponses en bandes ou moirures, dont la forme et la largeur dépendent du type de voisinage considéréThe first part of the thesis consists of a paper published in IEEE Trans. Aut. Control (vol. AC-28, n°9, 1983), with J. C. Fort and G. Malgouyres. It gives two methods of calculating the exit time of a Markov chain from an attraction domain this time is extremely long, sa we use an exponential change of probability (that of large deviations theory), for a fast simulation and a non-standard approximation by diffusion. The second part includes two papers published with J. C. Fort in the Annales de l'IHP, Probabilités and Statistiques (vol. 23, n° 1, 1987}, and in Biological Cybernetics (n° 53, 1986). In the first one, we prove the convergence of Kohonen's self-organizing algorithm, in dimension 1. In the second one, we define another self-organizing algorithm, which is a simplified variant of Kohonen's, and we prove its convergence in dimensions 1 and 2. In the third part, published in Biological Cybernetics (n°58, 1988), we solve the problem of the connection matrix calculus for a Mac-Culloch or Hopfield neural network, so as to get the largest attractivity for the deterministic algorithm and non-orthogonal patterns. Then we calculate the attractivity of each memorized pattern, for a given connection matrix. The last part is devoted to the study of the role of inhibition in a nearest-neighbours-connected neural network. The model closely ressembles the biological reality of the young animal's cerebellar cortex. We prove that, when inhibition is smaller than a certain threshold, the network is ergodic and works in a stationary way. Conversely, when inhibition increases, striped or moiré responses appear, whose form and width depend on the considered neighbourhood size
22
McDougall, Jeffrey Michael. "Low complexity channel models for approximating flat Rayleigh fading in network simulations." Texas A&M University, 2003. http://hdl.handle.net/1969/294.
Full text
23
Li, Jun. "Learning Average Reward Irreducible Stochastic Games: Analysis and Applications." [Tampa, Fla.] : University of South Florida, 2003. http://purl.fcla.edu/fcla/etd/SFE0000136.
Full text
24
Langenau, Holger. "Best constants in Markov-type inequalities with mixed weights." Doctoral thesis, Universitätsbibliothek Chemnitz, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-200815.
Full textAbstract:
Markov-type inequalities provide upper bounds on the norm of the (higher order) derivative of an algebraic polynomial in terms of the norm of the polynomial itself. The present thesis considers the cases in which the norms are of the Laguerre, Gegenbauer, or Hermite type, with respective weights chosen differently on both sides of the inequality. An answer is given to the question on the best constant so that such an inequality is valid for every polynomial of degree at most n. The demanded best constant turns out to be the operator norm of the differential operator. The latter conicides with the tractable spectral norm of its matrix representation in an appropriate set of orthonormal bases. The methods to determine these norms vary tremendously, depending on the difference of the parameters accompanying the weights. Up to a very small gap in the parameter range, asymptotics for the best constant in each of the aforementioned cases are givenMarkovungleichungen liefern obere Schranken an die Norm einer (höheren) Ableitung eines algebraischen Polynoms in Bezug auf die Norm des Polynoms selbst. Diese vorliegende Arbeit betrachtet den Fall, dass die Normen vom Laguerre-, Gegenbauer- oder Hermitetyp sind, wobei die entsprechenden Gewichte auf beiden Seiten unterschiedlich gewählt werden. Es wird die kleinste Konstante bestimmt, sodass diese Ungleichung für jedes Polynom vom Grad höchstens n erfüllt ist. Die gesuchte kleinste Konstante kann als die Operatornorm des Differentialoperators dargestellt werden. Diese fällt aber mit der Spektralnorm der Matrixdarstellung in einem Paar geeignet gewählter Orthonormalbasen zusammen und kann daher gut behandelt werden. Zur Abschätzung dieser Normen kommen verschiedene Methoden zum Einsatz, die durch die Differenz der in den Gewichten auftretenden Parameter bestimmt werden. Bis auch eine kleine Lücke im Parameterbereich wird das asymptotische Verhalten der kleinsten Konstanten in jedem der betrachteten Fälle ermittelt
25
Li, Jun 1974. "Learning average reward irreducible stochastic games [electronic resource] : analysis and applications / by Jun Li." University of South Florida, 2003. http://purl.fcla.edu/fcla/etd/SFE0000136.
Full textAbstract:
Includes vita.Title from PDF of title page.
Document formatted into pages; contains 111 pages.
Thesis (Ph.D.)--University of South Florida, 2003.
Includes bibliographical references.
Text (Electronic thesis) in PDF format.
ABSTRACT: A large class of sequential decision making problems under uncertainty with multiple competing decision makers/agents can be modeled as stochastic games. Stochastic games having Markov properties are called Markov games or competitive Markov decision processes. This dissertation presents an approach to solve non cooperative stochastic games, in which each decision maker makes her/his own decision independently and each has an individual payoff function. In stochastic games, the environment is nonstationary and each agent's payoff is affected by joint decisions of all agents, which results in the conflict of interest among the decision makers. In this research, the theory of Markov decision processes (MDPs) is combined with the game theory to analyze the structure of Nash equilibrium for stochastic games. In particular, the Laurent series expansion technique is used to extend the results of discounted reward stochastic games to average reward stochastic games.
ABSTRACT: As a result, auxiliary matrix games are developed that have equivalent equilibrium points and values to a class of stochastic games that are irreducible and have average reward performance metric. R-learning is a well known machine learning algorithm that deals with average reward MDPs. The R-learning algorithm is extended to develop a Nash-R reinforcement learning algorithm for obtaining the equivalent auxiliary matrices. A convergence analysis of the Nash-R algorithm is developed from the study of the asymptotic behavior of its two time scale stochastic approximation scheme, and the stability of the associated ordinary differential equations (ODEs). The Nash-R learning algorithm is tested and then benchmarked with MDP based learning methods using a well known grid game. Subsequently, a real life application of stochastic games in deregulated power market is explored.
ABSTRACT: According to the current literature, Cournot, Bertrand, and Supply Function Equilibrium (SFEs) are the three primary equilibrium models that are used to evaluate the power market designs. SFE is more realistic for pool type power markets. However, for a complicated power system, the convex assumption for optimization problems is violated in most cases, which makes the problems more difficult to solve. The SFE concept in adopted in this research, and the generators' behaviors are modeled as a stochastic game instead of one shot game. The power market is considered to have features such as multi-settlement (bilateral, day-ahead market, spot markets and transmission congestion contracts), and demand elasticity. Such a market consisting of multiple competing suppliers (generators) is modeled as a competitive Markov decision processes and is studied using the Nash-R algorithm.
System requirements: World Wide Web browser and PDF reader.
Mode of access: World Wide Web.
26
Garcia, Pascal. "Exploration guidée et induction de comportements génériques en apprentissage par renforcement." Rennes, INSA, 2004. http://www.theses.fr/2004ISAR0010.
Full textAbstract:
L'apprentissage par renforcement est un paradigme dans lequel un agent autonome apprend quelles actionseffectuer dans différentes situations (états), de façon à optimiser les renforcements (récompenses ou punitions) qu'il recevra sur le long terme. Bien qu'un très grand nombre de tâches puisse se formuler dans ce paradigme, deux problèmes fondamentaux se posent concernant les algorithmes d'apprentissage par renforcement standards : 1. Ils ne permettent pas de résoudre en un temps raisonnable des tâches ayant un assez grand nombre d'états. 2. Pour une tâche donnée, ces algorithmes doivent apprendre à partir de zéro même si cette tâche est similaire à une autre précédemment résolue. Il serait bien plus utile d'avoir des algorithmes permettant de résoudre plusieurs tâches séquentiellement, la connaissance apprise sur une tâche pouvant être transférée vers la suivante afin de guider l'apprentissage. Nous proposons des méthodes pour aborder ces deux problèmes : 1. Nous définissons deux formalismes permettant d'ajouter de la connaissance a priori, même très succincte, que l'utilisateur possède sur une tâche donnée afin de guider l'agent. L'agent est ainsi doté d'un comportement de base qui pourra se modifier lors de la phase d'apprentissage. 2. Nous définissons une méthode permettant à l'agent, après la résolution d'une ou plusieurs tâches apparentées et à partir de briques élémentaires, d'induire un comportement générique. Il pourra l'utiliserlors de la résolution d'une nouvelle tâche en plus des actions de base associées à cette tâcheReinforcement learning is a general framework in which an autonomous agent learns which actions to choose in particular situations (states) in order to optimize some reinforcements (rewards or punitions) in the long run. Even if a lot of tasks can be formulated in this framework, there are two problems with the standard reinforcement learning algorithms: 1. Due to the learning time of those algorithms, in practice, tasks with a moderatly large state space are not solvable in reasonable time. 2. Given several problems to solve in some domains, a standard reinforcement learning agent learns an optimal policy from scratch for each problem. It would be far more useful to have systems that can solve several problems over time, using the knowledge obtained from previous problem instances to guide in learning on new problems. We propose some methods to address those issues: 1. We define two formalisms to introduce a priori knowledge to guide the agent on a given task. The agent has an initial behaviour which can be modified during the learning process. 2. We define a method to induce generic behaviours,based on the previously solved tasks and on basicbuilding blocks. Those behaviours will be added to the primitive actions of a new related task tohelp the agent solve it
27
Langenau, Holger. "Best constants in Markov-type inequalities with mixed weights." Doctoral thesis, Universitätsverlag der Technischen Universität Chemnitz, 2015. https://monarch.qucosa.de/id/qucosa%3A20429.
Full textAbstract:
Markov-type inequalities provide upper bounds on the norm of the (higher order) derivative of an algebraic polynomial in terms of the norm of the polynomial itself. The present thesis considers the cases in which the norms are of the Laguerre, Gegenbauer, or Hermite type, with respective weights chosen differently on both sides of the inequality. An answer is given to the question on the best constant so that such an inequality is valid for every polynomial of degree at most n.
The demanded best constant turns out to be the operator norm of the differential operator. The latter conicides with the tractable spectral norm of its matrix representation in an appropriate set of orthonormal bases.
The methods to determine these norms vary tremendously, depending on the difference of the parameters accompanying the weights. Up to a very small gap in the parameter range, asymptotics for the best constant in each of the aforementioned cases are given.Markovungleichungen liefern obere Schranken an die Norm einer (höheren) Ableitung eines algebraischen Polynoms in Bezug auf die Norm des Polynoms selbst. Diese vorliegende Arbeit betrachtet den Fall, dass die Normen vom Laguerre-, Gegenbauer- oder Hermitetyp sind, wobei die entsprechenden Gewichte auf beiden Seiten unterschiedlich gewählt werden. Es wird die kleinste Konstante bestimmt, sodass diese Ungleichung für jedes Polynom vom Grad höchstens n erfüllt ist. Die gesuchte kleinste Konstante kann als die Operatornorm des Differentialoperators dargestellt werden. Diese fällt aber mit der Spektralnorm der Matrixdarstellung in einem Paar geeignet gewählter Orthonormalbasen zusammen und kann daher gut behandelt werden. Zur Abschätzung dieser Normen kommen verschiedene Methoden zum Einsatz, die durch die Differenz der in den Gewichten auftretenden Parameter bestimmt werden. Bis auch eine kleine Lücke im Parameterbereich wird das asymptotische Verhalten der kleinsten Konstanten in jedem der betrachteten Fälle ermittelt.
28
Touyar, Narjiss. "Approximation de Poisson du nombre de répétitions dans des chaînes de Markov d'ordre m ≥1 : Application à l'étude de significativité dans des séquences d'ADN." Rouen, 2006. http://www.theses.fr/2006ROUES007.
Full textAbstract:
Les génomes sont des structures dynamiques et redondantes qui évoluent par mutation, inversion, élimination ou duplication de certaines de leurs parties. Pour mieux comprendre la structure des génomes et leur mode d'évolution, il est devenu très important d'effectuer des analyses statistiques des répétitions au sein de ces génomes. Le but principal de ce travail consiste à étudier la significativité statistique du nombre observé Nobst de répétitions de longueur t dans une séquence markovienne. Cette distribution permet alors de calculer la p-value, probabilité d'observer autant de répétitions dans le modèle choisi. Nous commençons par traiter le cas markovien d'ordre 1 avant de généraliser nos résultats à des modèles d'ordre supérieur. Nous approchons le nombre Nt par une loi de Poisson en utilisant la méthode Chen-Stein. Nous démontrons que l'erreur d'approximation tend vers zéro. Des simulations ont été effectuées pour valider l'approximation de Poisson. Le calcul de la p-value a été mis en œuvre sur plusieurs génomesGenomes are dynamic and redondant structures which are regularly subject to mutations, deletions, duplications and inversions. In order to better understand the structure of genomes and their mecanism of evolution, it is important to make some statistical significance analyses of repeats. The goal of this thesis consists in studying the statistical significance of the number of repeats of by a given length t observed in a given sequence, denoted Nobst. This statistical study relies on the evaluation of the distribution of the random count Nt in some relevant random sequences. It will then allow to calculate the p-value. We start by studying the one-order Markov chain model and treat the general case of m-order Markov chain models m ≥1. We have used the Chen-Stein method to bound the approximation error when the number of repeats of length t is approximated by a Poisson variable. We show that this error converges to 0. To validate the Poisson approximation, some simulations were done. The calculation of the p-value has been implemented for several genomes
29
Derode, Anne-Sophie. "Approximations de la fiabilité : cas des systèmes à réparations différées pu à composants vieillissants." Lille 1, 2007. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2007/50376-2007-75.pdf.
Full textAbstract:
Les processus de Markov sont fréquemment utilisés pour modéliser les systèmes réparables et reconfigurables, comme par exemple les systèmes électriques. Mais dans le monde industriel, les systèmes réels sont de plus en plus complexes (redondance, grand nombre d'états, réparations sous condition. . . ) et conduisent à des modèles raides et de grande taille. Si tous les composants sont réparables et non-vieillissants, l'état initial est le seul état lent et les approximations exponentielles pour le calcul de la fiabilité sont à la fois précises et faciles à utiliser. En revanche, si les composants sont vieillissants, le système peut encore être modélisé par un processus de Markov en utilisant la méthode des Phases. Mais un grand nombre d'états est alors introduit et les méthodes mentionnées auparavant sont inapplicables. Dans cette thèse, nous étudions d'autres approximations de la fiabilité. Ces nouvelles méthodes répondent aux exigences de ce problème et sont pessimistes, un caractère important dans l'évaluation de la fiabilité. Ces méthodes sont également valables si certains composants sont à réparations différées (les composants ne sont pas réparés dès qu'ils tombent en panne, mais après une ou plusieurs pannes supplémentaires).
30
Simpson, Daniel Peter. "Krylov subspace methods for approximating functions of symmetric positive definite matrices with applications to applied statistics and anomalous diffusion." Thesis, Queensland University of Technology, 2008. https://eprints.qut.edu.au/29751/1/Simpson_Final_Thesis.pdf.
Full textAbstract:
Matrix function approximation is a current focus of worldwide interest and finds application in a variety of areas of applied mathematics and statistics. In this thesis we focus on the approximation of A^(-α/2)b, where A ∈ ℝ^(n×n) is a large, sparse symmetric positive definite matrix and b ∈ ℝ^n is a vector. In particular, we will focus on matrix function techniques for sampling from Gaussian Markov random fields in applied statistics and the solution of fractional-in-space partial differential equations.
Gaussian Markov random fields (GMRFs) are multivariate normal random variables characterised by a sparse precision (inverse covariance) matrix. GMRFs are popular models in computational spatial statistics as the sparse structure can be exploited, typically through the use of the sparse Cholesky decomposition, to construct fast sampling methods. It is well known, however, that for sufficiently large problems, iterative methods for solving linear systems outperform direct methods.
Fractional-in-space partial differential equations arise in models of processes undergoing anomalous diffusion. Unfortunately, as the fractional Laplacian is a non-local operator, numerical methods based on the direct discretisation of these equations typically requires the solution of dense linear systems, which is impractical for fine discretisations.
In this thesis, novel applications of Krylov subspace approximations to matrix functions for both of these problems are investigated. Matrix functions arise when sampling from a GMRF by noting that the Cholesky decomposition A = LL^T is, essentially, a `square root' of the precision matrix A. Therefore, we can replace the usual sampling method, which forms x = L^(-T)z, with x = A^(-1/2)z, where z is a vector of independent and identically distributed standard normal random variables. Similarly, the matrix transfer technique can be used to build solutions to the fractional Poisson equation of the form ϕn = A^(-α/2)b, where A is the finite difference approximation to the Laplacian. Hence both applications require the approximation of f(A)b, where f(t) = t^(-α/2) and A is sparse. In this thesis we will compare the Lanczos approximation, the shift-and-invert Lanczos approximation, the extended Krylov subspace method, rational approximations and the restarted Lanczos approximation for approximating matrix functions of this form.
A number of new and novel results are presented in this thesis. Firstly, we prove the convergence of the matrix transfer technique for the solution of the fractional Poisson equation and we give conditions by which the finite difference discretisation can be replaced by other methods for discretising the Laplacian. We then investigate a number of methods for approximating matrix functions of the form A^(-α/2)b and investigate stopping criteria for these methods. In particular, we derive a new method for restarting the Lanczos approximation to f(A)b. We then apply these techniques to the problem of sampling from a GMRF and construct a full suite of methods for sampling conditioned on linear constraints and approximating the likelihood. Finally, we consider the problem of sampling from a generalised Matern random field, which combines our techniques for solving fractional-in-space partial differential equations with our method for sampling from GMRFs.
31
Simpson, Daniel Peter. "Krylov subspace methods for approximating functions of symmetric positive definite matrices with applications to applied statistics and anomalous diffusion." Queensland University of Technology, 2008. http://eprints.qut.edu.au/29751/.
Full textAbstract:
Matrix function approximation is a current focus of worldwide interest and finds application in a variety of areas of applied mathematics and statistics. In this thesis we focus on the approximation of A..=2b, where A 2 Rnn is a large, sparse symmetric positive definite matrix and b 2 Rn is a vector. In particular, we will focus on matrix function techniques for sampling from Gaussian Markov random fields in applied statistics and the solution of fractional-in-space partial differential equations. Gaussian Markov random fields (GMRFs) are multivariate normal random variables characterised by a sparse precision (inverse covariance) matrix. GMRFs are popular models in computational spatial statistics as the sparse structure can be exploited, typically through the use of the sparse Cholesky decomposition, to construct fast sampling methods. It is well known, however, that for sufficiently large problems, iterative methods for solving linear systems outperform direct methods. Fractional-in-space partial differential equations arise in models of processes undergoing anomalous diffusion. Unfortunately, as the fractional Laplacian is a non-local operator, numerical methods based on the direct discretisation of these equations typically requires the solution of dense linear systems, which is impractical for fine discretisations. In this thesis, novel applications of Krylov subspace approximations to matrix functions for both of these problems are investigated. Matrix functions arise when sampling from a GMRF by noting that the Cholesky decomposition A = LLT is, essentially, a `square root' of the precision matrix A. Therefore, we can replace the usual sampling method, which forms x = L..T z, with x = A..1=2z, where z is a vector of independent and identically distributed standard normal random variables. Similarly, the matrix transfer technique can be used to build solutions to the fractional Poisson equation of the form n = A..=2b, where A is the finite difference approximation to the Laplacian. Hence both applications require the approximation of f(A)b, where f(t) = t..=2 and A is sparse. In this thesis we will compare the Lanczos approximation, the shift-and-invert Lanczos approximation, the extended Krylov subspace method, rational approximations and the restarted Lanczos approximation for approximating matrix functions of this form. A number of new and novel results are presented in this thesis. Firstly, we prove the convergence of the matrix transfer technique for the solution of the fractional Poisson equation and we give conditions by which the finite difference discretisation can be replaced by other methods for discretising the Laplacian. We then investigate a number of methods for approximating matrix functions of the form A..=2b and investigate stopping criteria for these methods. In particular, we derive a new method for restarting the Lanczos approximation to f(A)b. We then apply these techniques to the problem of sampling from a GMRF and construct a full suite of methods for sampling conditioned on linear constraints and approximating the likelihood. Finally, we consider the problem of sampling from a generalised Matern random field, which combines our techniques for solving fractional-in-space partial differential equations with our method for sampling from GMRFs.
32
Šnipas, Mindaugas. "Stochastinių sistemų aproksimavimas Markovo modeliais." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2008. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2008~D_20080902_100259-01228.
Full textAbstract:
Dažnai realių stochastinių sistemų negalime aprašyti Markovo procesais, nes operacijų trukmės nėra pasiskirstę pagal eksponentinį dėsnį. Šiame darbe nagrinėjome sistemų aproksimavimo galimybes, taikant eksponentinių skirstinių mišinius ir sąsūkas. Skirstinių aproksimavimui taikėme Erlango mišinius ir Kokso skirstinį. Skirstinių aproksimavimą pritaikėme aptarnavimo sistemų M/G/1 ir G/M/1 tyrimui. Atlikti teoriniai skaičiavimai parodė, kad gaunamas aukštas aproksimavimo tikslumas. Aptarnavimo sistemų modeliavimui naudojome skaitmeninio Markovo procesų modeliavimo sistemą naudojant įvykių kalbą. Darbe sukurti metodai leidžia tiksliai apskaičiuoti sistemų charakteristikas, naudojant aproksimavimą eksponentiniais mišiniais ir sąsūkomis. Sukurta programinė įranga leidžia automatizuoti sistemų M/G/1 ir G/M/1 modeliavimą, naudojant aproksimavimą eksponentiniais mišiniais. Sistemos G/G/1 ( neištiriamos analiziniais metodais ) aproksimavimo rezultatai leidžia tikėtis, kad šiame darbe nagrinėjamas metodas gali būti naudojamas ir sudėtingų sistemų modeliavime.Application of numerical methods with approximation allows to extend a class of systems represented by Markovian processes under investigation compared with analytical methods. In this paper we used approximation of positive distribution functions, using phase-type distributions: mixtures of Erlang distributions and Coxian distribution – both 2 and 3 moments-matching algorithms was used. Analysis of M/G/1 and G/M/1 queueing systems showed, that moment-based queueing approximation gives high accuracy. In purpose to compute characteristics of M/G/1 and G/M/1 systems described in an event-based language, algorithms and software was created. Comparison to simulation results shows, that event-based language enables to get more precise results. Analysis of G/G/1 systems showed, that moment-based approximation can be used to analyse difficult queueing systems.
33
Fralix, Brian Haskel. "Stability and Non-stationary Characteristics of Queues." Diss., Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/14569.
Full textAbstract:
We provide contributions to two classical areas of queueing. The first part of this thesis focuses on finding new conditions for a
Markov chain on a general state space to be Harris recurrent,
positive Harris recurrent or geometrically ergodic. Most of our
results show that establishing each property listed above is
equivalent to finding a good enough feasible solution to a
particular optimal stopping problem, and they provide a more
complete understanding of the role Foster's criterion plays in the
theory of Markov chains.
The second and third parts of the thesis involve analyzing queues
from a transient, or time-dependent perspective. In part two, we
are interested in looking at a queueing system from the
perspective of a customer that arrives at a fixed time t. Doing
this requires us to use tools from Palm theory. From an intuitive
standpoint, Palm probabilities provide us with a way of computing
probabilities of events, while conditioning on sets of measure
zero. Many studies exist in the literature that deal with Palm
probabilities for stationary systems, but very few treat the
non-stationary case. As an application of our main results, we
show that many classical results from queueing (in particular ASTA and Little's law) can be generalized to a time-dependent
setting.
In part three, we establish a continuity result for what we refer
to as jump processes. From a queueing perspective, we basically
show that if the primitives and the initial conditions of a
sequence of queueing processes converge weakly, then the
corresponding queue-length processes converge weakly as well in
some sense. Here the notion of convergence used depends on
properties of the limiting process, therefore our results
generalize classical continuity results that exist in the
literature. The way our results can be used to approximate
queueing systems is analogous to the way phase-type random
variables can be used to approximate other types of random
variables.
34
Blanchet, Juliette. "Modèles markoviens et extensions pour la classification de données complexes." Phd thesis, Université Joseph Fourier (Grenoble), 2007. http://tel.archives-ouvertes.fr/tel-00195271.
Full textAbstract:
Nous abordons le problème de la classification d'individus à partir d'observations dites " complexes " en ce sens qu'elles ne vérifient pas certaines des hypothèses simplificatrices classiquement adoptées. Dans ce travail, les individus à classer sont supposés dépendants les uns des autres. L'approche adoptée est une approche probabiliste fondée sur une modélisation markovienne. Trois problèmes de classification sont abordés.Le premier concerne la classification de données lorsque celles-ci sont de grande dimension. Pour un tel problème, nous adoptons un modèle markovien gaussien non diagonal tirant partie du fait que la plupart des observations de grande dimension vivent en réalité dans des sous-espaces propres à chacune des classes et dont les dimensions intrinsèques sont faibles. De ce fait, le nombre de paramètres libres du modèle reste raisonnable.
Le deuxième point abordé s'attache à relâcher l'hypothèse simplificatrice de bruit indépendant unimodal, et en particulier gaussien. Nous considérons pour cela le modèle récent de champ de Markov triplet et proposons une nouvelle famille de Markov triplet adaptée au cadre d'une classification supervisée. Nous illustrons la flexibilité et les performances de nos modèles sur une application à la reconnaissance d'images réelles de textures.
Enfin, nous nous intéressons au problème de la classification d'observations dites incomplètes, c'est-à-dire pour lesquelles certaines valeurs sont manquantes. Nous développons pour cela une méthode markovienne ne nécessitant pas le remplacement préalable des observations manquantes. Nous présentons une application de cette méthodologie à un problème réel de classification de gènes.
35
Quagliaro, Laurence. "Une nouvelle méthode pour l'analyse quantitative de la sûreté de fonctionnement des systèmes : la méthode des graphes fictifs." Compiègne, 1993. http://www.theses.fr/1993COMPD657.
Full textAbstract:
L'analyse quantitative de la sûreté de fonctionnement des systèmes complexes (de part leur taille ou leur topologie) se heurte à un problème d'explosion combinatoire qui ne peut être résolu que par l'utilisation d'approximations : regroupements de composants, agrégation d'états,. . . Ces approximations peuvent conduire à des résultats erronés si elles sont utilisées sans discernement et en dehors de leur domaine de validité, souvent mal connu. Nous proposons une nouvelle méthode de simplification des systèmes modélisés par graphe de Markov : la méthode des graphes fictifs qui nous permet l'élaboration hiérarchique d'un modèle approché.
36
Dandoush, Abdulhalim. "Analysis and optimization of peer-to-peer storage-bacup systems." Nice, 2010. http://www.theses.fr/2010NICE4003.
Full textAbstract:
Cette thèse évalue les performances de systèmes de stockage de données sur des réseaux de pairs. Ces systèmes reposent sur trois piliers: la fragmentation des données et leur dissémination chez les pairs, la redondance des données afin de faire face aux éventuelles indisponibilités des pairs et l'existence d'un mécanisme de recouvrement des données perdues ou temporairement indisponibles. Nous modélisons deux mécanismes de recouvrement des données par des chaînes de Markov absorbantes. Plus précisément, nous évaluons la qualité du service rendu aux utilisateurs en terme de longévité et de disponibilité des données de chaque mécanisme. Le premier mécanisme est centralisé et repose sur l'utilisation d'un serveur pour la reconstruction des donnée perdus. Le second est distribué : la reconstruction des fragments perdus met en oeuvre, séquentiellement, plusieurs pairs et s'arrête dès que le niveau de redondance requis est atteint. Les principales hypothèses faites dans nos modèles sont validées soit par des simulations soit par des traces réelles recueillies dans différents environnements distribués. Pour les processus de téléchargement et de recouvrement des données nous proposons un modèle de simulation réaliste qui est capable de prédire avec précision le comportement de ces processus mais le temps de simulation est long pour de grands réseaux. Pour surmonter cette restriction nous proposons et analysons un algorithme efficace au niveau flux. L'algorithme est simple et utilise le concept de (min-max). Il permet de caractériser le temps de réponse des téléchargements en parallèle dans un système de stockage distribuéThis thesis characterizes the performance of peer-to-peer storage systems in terms of the delivered data lifetime and data availability. Two schemes for recovering lost data are modeled and analyzed: the first is centralized and relies on a server that recovers multiple losses at once, whereas the second is distributed and recovers one loss at a time. For each scheme, we propose several Markovian models that equally apply to many distributed environments as shown through numerical computations. These allow to assess the impact of each system parameter on the performance. In particular, we provide guidelines on how to tune the system parameters in order to provide desired lifetime and/or availability of data. The key assumptions made in the models are validated through intensive packet-level simulations or real traces collected from different distributed environments. In fact, we propose a realistic simulation model implemented on the Network Simulator (NS-2) for both download and recovery processes. Although this simulator can accurately predict the behaviour of the latter processes while considering the impact of several constraints such as the heterogeneity of peers and the the underlying network topologies, this simulator requires however relatively long time. To overcome this scalability limitation, we propose and analyze an algorithm. The algorithm is efficient in time and quite simple and uses the concept of ``Progressive-Filling'' (or max-min fairness). The validation of this algorithm consists in characterizing the distribution of the response time of parallel downloads in a distributed storage system, through simulations
37
Cantarutti, Nicola. "Option pricing in exponential Lévy models with transaction costs." Doctoral thesis, Instituto Superior de Economia e Gestão, 2020. http://hdl.handle.net/10400.5/20786.
Full textAbstract:
Doutoramento em Matemática Aplicada à Economia e GestãoIn this thesis we present a new model for pricing European call options in presence of proportional transaction costs, when the stock price follows a general exponential Lévy process. The model is a generalization of the celebrated work of Davis, Panas and Zariphopoulou, where the value of the option is defined as the utility indifference price. This approach requires the solution of a stochastic singular control problem in finite time. We introduce the general formulation of the problem, and derive the associated Hamilton-Jacobi-Bellman equation (HJB), which is a nonlinear partial integro-differential equation, with the form of a variational inequality. We prove that the value function of the problem is a solution of the HJB equation in the viscosity sense. The original problem is then simplified for the specific case of the exponential utility function, under the assumption of absence of default for the investor's portfolio. We solve numerically the optimization problems using the Markov chain approximation method. We also apply the multinomial method to the Variance Gamma process, which is an alternative and more efficient approach to discretize the continuous time process. We provide a numerical scheme and prove that it is monotone, stable and consistent and that the solution converges to the viscosity solution of the original HJB equation. Several numerical solutions are presented for both the original problem and the simplified problem. Numerical results are obtained for the cases of diffusion, Merton and Variance Gamma processes. We provide convergence and time complexity analysis and comparisons with option prices computed using the standard martingale pricing theory.
info:eu-repo/semantics/publishedVersion
38
Ben, Henda Noomene. "Infinite-state Stochastic and Parameterized Systems." Doctoral thesis, Uppsala University, Department of Information Technology, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8915.
Full textAbstract:
A major current challenge consists in extending formal methods in order to handle infinite-state systems. Infiniteness stems from the fact that the system operates on unbounded data structure such as stacks, queues, clocks, integers; as well as parameterization.
Systems with unbounded data structure are natural models for reasoning about communication protocols, concurrent programs, real-time systems, etc. While parameterized systems are more suitable if the system consists of an arbitrary number of identical processes which is the case for cache coherence protocols, distributed algorithms and so forth.
In this thesis, we consider model checking problems for certain fundamental classes of probabilistic infinite-state systems, as well as the verification of safety properties in parameterized systems. First, we consider probabilistic systems with unbounded data structures. In particular, we study probabilistic extensions of Lossy Channel Systems (PLCS), Vector addition Systems with States (PVASS) and Noisy Turing Machine (PNTM). We show how we can describe the semantics of such models by infinite-state Markov chains; and then define certain abstract properties, which allow model checking several qualitative and quantitative problems.
Then, we consider parameterized systems and provide a method which allows checking safety for several classes that differ in the topologies (linear or tree) and the semantics (atomic or non-atomic). The method is based on deriving an over-approximation which allows the use of a symbolic backward reachability scheme. For each class, the over-approximation we define guarantees monotonicity of the induced approximate transition system with respect to an appropriate order. This property is convenient in the sense that it preserves upward closedness when computing sets of predecessors.
39
Liu, Yi. "Time-Varying Coefficient Models for Recurrent Events." Diss., Virginia Tech, 2018. http://hdl.handle.net/10919/97999.
Full textAbstract:
I have developed time-varying coefficient models for recurrent event data to evaluate the temporal profiles for recurrence rate and covariate effects. There are three major parts in this dissertation. The first two parts propose a mixed Poisson process model with gamma frailties for single type recurrent events. The third part proposes a Bayesian joint model based on multivariate log-normal frailties for multi-type recurrent events. In the first part, I propose an approach based on penalized B-splines to obtain smooth estimation for both time-varying coefficients and the log baseline intensity. An EM algorithm is developed for parameter estimation. One issue with this approach is that the estimating procedure is conditional on smoothing parameters, which have to be selected by cross-validation or optimizing certain performance criterion. The procedure can be computationally demanding with a large number of time-varying coefficients. To achieve objective estimation of smoothing parameters, I propose a mixed-model representation approach for penalized splines. Spline coefficients are treated as random effects and smoothing parameters are to be estimated as variance components. An EM algorithm embedded with penalized quasi-likelihood approximation is developed to estimate the model parameters. The third part proposes a Bayesian joint model with time-varying coefficients for multi-type recurrent events. Bayesian penalized splines are used to estimate time-varying coefficients and the log baseline intensity. One challenge in Bayesian penalized splines is that the smoothness of a spline fit is considerably sensitive to the subjective choice of hyperparameters. I establish a procedure to objectively determine the hyperparameters through a robust prior specification. A Markov chain Monte Carlo procedure based on Metropolis-adjusted Langevin algorithms is developed to sample from the high-dimensional distribution of spline coefficients. The procedure includes a joint sampling scheme to achieve better convergence and mixing properties. Simulation studies in the second and third part have confirmed satisfactory model performance in estimating time-varying coefficients under different curvature and event rate conditions. The models in the second and third part were applied to data from a commercial truck driver naturalistic driving study. The application results reveal that drivers with 7-hours-or-less sleep prior to a shift have a significantly higher intensity after 8 hours of on-duty driving and that their intensity remains higher after taking a break. In addition, the results also show drivers' self-selection on sleep time, total driving hours in a shift, and breaks. These applications provide crucial insight into the impact of sleep time on driving performance for commercial truck drivers and highlights the on-road safety implications of insufficient sleep and breaks while driving. This dissertation provides flexible and robust tools to evaluate the temporal profile of intensity for recurrent events.PHD
40
Haddani, Mostafa. "Étude de modèles probabilistes de réseaux de télécommunication." Paris 6, 2001. http://www.theses.fr/2001PA066515.
Full text
41
Ryan, Elizabeth G. "Contributions to Bayesian experimental design." Thesis, Queensland University of Technology, 2014. https://eprints.qut.edu.au/79628/1/Elizabeth_Ryan_Thesis.pdf.
Full textAbstract:
This thesis progresses Bayesian experimental design by developing novel methodologies and extensions to existing algorithms. Through these advancements, this thesis provides solutions to several important and complex experimental design problems, many of which have applications in biology and medicine. This thesis consists of a series of published and submitted papers. In the first paper, we provide a comprehensive literature review on Bayesian design. In the second paper, we discuss methods which may be used to solve design problems in which one is interested in finding a large number of (near) optimal design points. The third paper presents methods for finding fully Bayesian experimental designs for nonlinear mixed effects models, and the fourth paper investigates methods to rapidly approximate the posterior distribution for use in Bayesian utility functions.
42
Schwarzenegger, Rafael. "Matematické modely spolehlivosti v technické praxi." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2017. http://www.nusl.cz/ntk/nusl-318802.
Full textAbstract:
Tato práce popisuje a aplikuje parametrické a neparametrické modely spolehlivosti na cenzorovaná data. Ukazuje implementaci spolehlivosti v metodologii Six Sigma. Metody jsou využity pro přežití/spolehlivost reálných technických dat.
43
Wegmann, Bertil. "Bayesian Inference in Structural Second-Price Auctions." Doctoral thesis, Stockholms universitet, Statistiska institutionen, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-57278.
Full textAbstract:
The aim of this thesis is to develop efficient and practically useful Bayesian methods for statistical inference in structural second-price auctions. The models are applied to a carefully collected coin auction dataset with bids and auction-specific characteristics from one thousand Internet auctions on eBay. Bidders are assumed to be risk-neutral and symmetric, and compete for a single object using the same game-theoretic strategy. A key contribution in the thesis is the derivation of very accurate approximations of the otherwise intractable equilibrium bid functions under different model assumptions. These easily computed and numerically stable approximations are shown to be crucial for statistical inference, where the inverse bid functions typically needs to be evaluated several million times. In the first paper, the approximate bid is a linear function of a bidder's signal and a Gaussian common value model is estimated. We find that the publicly available book value and the condition of the auctioned object are important determinants of bidders' valuations, while eBay's detailed seller information is essentially ignored by the bidders. In the second paper, the Gaussian model in the first paper is contrasted to a Gamma model that allows intrinsically non-negative common values. The Gaussian model performs slightly better than the Gamma model on the eBay data, which we attribute to an almost normal or at least symmetrical distribution of valuations. The third paper compares the model in the first paper to a directly comparable model for private values. We find many interesting empirical regularities between the models, but no strong and consistent evidence in favor of one model over the other. In the last paper, we consider auctions with both private-value and common-value bidders. The equilibrium bid function is given as the solution to an ordinary differential equation, from which we derive an approximate inverse bid as an explicit function of a given bid. The paper proposes an elaborate model where the probability of being a common value bidder is a function of covariates at the auction level. The model is estimated by a Metropolis-within-Gibbs algorithm and the results point strongly to an active influx of both private-value and common-value bidders.At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 1: Epub ahead of print. Paper 2: Manuscript. Paper 3: Manuscript. Paper 4: Manuscript.
44
Goubet, Étienne. "Contrôle non destructif par analyse supervisée d'images 3D ultrasonores." Cachan, Ecole normale supérieure, 1999. http://www.theses.fr/1999DENS0011.
Full textAbstract:
L'objet de cette thèse consiste en l'élaboration d'une chaine de traitements permettant d'extraire l'information utile de données 3d ultrasonores et de caractériser les défauts éventuellement présents dans la pièce inspectée. Cette caractérisation a été abordée pour des fissures contrôlées par un même émetteur/récepteur. Dans une première partie nous rappelons les principes du contrôle non destructif par ultrasons ainsi que les représentations classiques des données ultrasonores. La deuxième partie est consacrée à l'étude d'un modèle d'extraction de l'information d'échos présents sur les données au moyen d'une base d'ondelettes adaptée. L'utilisation d'une ondelette unique translatée dans le temps est rendue possible par un travail sur une représentation complexe des données réelles originales. Une première étape permet de détecter et de positionner les échos d'amplitude significative. Dans un deuxième temps, on effectue une régularisation spatialement cohérente des instants de détection à l'aide d'un modèle markovien. On élimine ainsi les échos dont les instants de détection ne font pas partie de surfaces d'instants régulières. Les parties suivantes traitent de la localisation et du dimensionnement des fissures. On utilise des caractéristiques extraites du faisceau ultrasonore afin de déterminer le trajet de l'onde ultrasonore du capteur à l'objet diffractant lorsque la réponse de l'écho est maximale. On met en correspondance l'instant de détection obtenu pour cet écho et le temps de parcours selon le trajet défini afin de positionner un point d'arête dans la pièce. On obtient ainsi un ensemble de points de discrétisation pour chaque arête. Dans le cadre de données 3d obtenues sur un matériau isotrope, on élimine les points d'arête extrêmes en utilisant un critère de comparaison sur les courbes échodynamiques associées aux points de détection sur les données réelles et sur des données simulées équivalentes. La localisation est abordée pour des fissures situées dans un matériau isotrope ou acier revêtu d'anisotrope.
45
Austad, Haakon Michael. "Approximations of Binary Markov Random Fields." Doctoral thesis, Norges teknisk-naturvitenskapelige universitet, Institutt for matematiske fag, 2011. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-14922.
Full text
46
Estandia, Gonzalez Luna Antonio. "Stable approximations for Markov-chain filters." Thesis, Imperial College London, 1987. http://hdl.handle.net/10044/1/38303.
Full text
47
Chaput, Philippe. "Approximating Markov processes by averaging." Thesis, McGill University, 2009. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=66654.
Full textAbstract:
We recast the theory of labelled Markov processes in a new setting, in a way "dual" to the usual point of view. Instead of considering state transitions as a collection of subprobability distributions on the state space, we view them as transformers of real-valued functions. By generalizing the operation of conditional expectation, we build a category consisting of labelled Markov processes viewed as a collection of operators; the arrows of this category behave as projections on a smaller state space. We define a notion of equivalence for such processes, called bisimulation, which is closely linked to the usual definition for probabilistic processes. We show that we can categorically construct the smallest bisimilar process, and that this smallest object is linked to a well-known modal logic. We also expose an approximation scheme based on this logic, where the state space of the approximants is finite; furthermore, we show that these finite approximants categorically converge to the smallest bisimilar process.Nous reconsidérons les processus de Markov étiquetés sous une nouvelle approche, dans un certain sens "dual'' au point de vue usuel. Au lieu de considérer les transitions d'état en état en tant qu'une collection de distributions de sous-probabilités sur l'espace d'états, nous les regardons en tant que transformations de fonctions réelles. En généralisant l'opération d'espérance conditionelle, nous construisons une catégorie où les objets sont des processus de Markov étiquetés regardés en tant qu'un rassemblement d'opérateurs; les flèches de cette catégorie se comportent comme des projections sur un espace d'états plus petit. Nous définissons une notion d'équivalence pour de tels processus, que l'on appelle bisimulation, qui est intimement liée avec la définition usuelle pour les processus probabilistes. Nous démontrons que nous pouvons construire, d'une manière catégorique, le plus petit processus bisimilaire à un processus donné, et que ce plus petit object est lié à une logique modale bien connue. Nous développons une méthode d'approximation basée sur cette logique, où l'espace d'états des processus approximatifs est fini; de plus, nous démontrons que ces processus approximatifs convergent, d'une manière catégorique, au plus petit processus bisimilaire.
48
Nguepedja, Nankep Mac jugal. "Modélisation stochastique de systèmes biologiques multi-échelles et inhomogènes en espace." Thesis, Rennes, École normale supérieure, 2018. http://www.theses.fr/2018ENSR0012/document.
Full textAbstract:
Les besoins grandissants de prévisions robustes pour des systèmes complexes conduisent à introduire des modèles mathématiques considérant un nombre croissant de paramètres. Au temps s'ajoutent l'espace, l'aléa, les échelles de dynamiques, donnant lieu à des modèles stochastiques multi-échelles avec dépendance spatiale (modèles spatiaux). Cependant, l'explosion du temps de simulation de tels modèles complique leur utilisation. Leur analyse difficile a néanmoins permis, pour les modèles à une échelle, de développer des outils puissants: loi des grands nombres (LGN), théorème central limite (TCL), ..., puis d'en dériver des modèles simplifiés et algorithmes accélérés. Dans le processus de dérivation, des modèles et algorithmes dits hybrides ont vu le jour dans le cas multi-échelle, mais sans analyse rigoureuse préalable, soulevant ainsi la question d'approximation hybride dont la consistance constitue l'une des motivations principales de cette thèse.En 2012, Crudu, Debussche, Muller et Radulescu établissent des critères d'approximation hybride pour des modèles homogènes en espace de réseaux de régulation de gènes. Le but de cette thèse est de compléter leur travail et le généraliser à un cadre spatial.Nous avons développé et simplifié différents modèles, tous des processus de Markov de sauts pures à temps continu. La démarche met en avant, d'une part, des conditions d'approximations déterministes par des solutions d'équations d'évolution (type réaction-advection-diffusion), et, d'autre part, des conditions d'approximations hybrides par des processus stochastiques hybrides. Dans le cadre des réseaux de réactions biochimiques, un TCL est établi. Il correspond à une approximation hybride d'un modèle homogène simplifié à deux échelles de temps (suivant Crudu et al.). Puis, une LGN est obtenue pour un modèle spatial à deux échelles de temps. Ensuite, une approximation hybride est établie pour un modèle spatial à deux échelles de dynamique en temps et en espace. Enfin, des comportements asymptotiques en grandes populations et en temps long sont présentés pour un modèle d'épidémie de choléra, via une LGN suivie d'une borne supérieure pour les sous-ensembles compacts, dans le cadre d'un principe de grande déviation (PGD) correspondant.À l'avenir, il serait intéressant, entre autres, de varier la géométrie spatiale, de généraliser le TCL, de compléter les estimations du PGD, et d'explorer des systèmes complexes issus d'autres domainesThe growing needs of precise predictions for complex systems lead to introducing stronger mathematical models, taking into account an increasing number of parameters added to time: space, stochasticity, scales of dynamics. Combining these parameters gives rise to spatial --or spatially inhomogeneous-- multiscale stochastic models. However, such models are difficult to study and their simulation is extremely time consuming, making their use not easy. Still, their analysis has allowed one to develop powerful tools for one scale models, among which are the law of large numbers (LLN) and the central limit theorem (CLT), and, afterward, to derive simpler models and accelrated algorithms. In that deduction process, the so-called hybrid models and algorithms have arisen in the multiscale case, but without any prior rigorous analysis. The question of hybrid approximation then shows up, and its consistency is a particularly important motivation of this PhD thesis.In 2012, criteria for hybrid approximations of some homogeneous regulation gene network models were established by Crudu, Debussche, Muller and Radulescu. The aim of this PhD thesis is to complete their work and generalize it afterward to a spatial framework.We have developed and simplified different models. They all are time continuous pure jump Markov processes. The approach points out the conditions allowing on the the one hand deterministic approximations by solutions of evolution equations of type reaction-advection-diffusion, and, on the other hand, hybrid approximations by hybrid stochastic processes. In the field of biochemical reaction networks, we establish a CLT. It corresponds to a hybrid approximation of a simplified homogeneous model (due to Crudu et al.). Then a LLN is obtained for a spatial model with two time scales. Afterward, a hybrid approximation is established, for a two time-space scales spatial model. Finally, the asymptotic behaviour in large population and long time are respectively presented for a model of cholera epidemic, through a LLN followed by the upper bound for compact sets, in the context of a corresponding large deviation principle (LDP).Interesting future works would be, among others, to study other spatial geometries, to generalize the CLT, to complete the LDP estimates, and to study complex systems from other fields
49
Patrascu, Relu-Eugen. "Linear approximations from factored Markov Dicision Processes." Waterloo, Ont. : University of Waterloo, 2004. http://etd.uwaterloo.ca/etd/rpatrasc2004.pdf.
Full textAbstract:
Thesis (Ph.D.)--University of Waterloo, 2004."A thesis presented to the University of Waterloo in fulfillment of the thesis requirement for the degree of Doctor of Philosophy in Computer Science". Includes bibliographical references.
50
Thiéry, Christophe. "Itération sur les politiques optimiste et apprentissage du jeu de Tetris." Thesis, Nancy 1, 2010. http://www.theses.fr/2010NAN10128/document.
Full textAbstract:
Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), ajoute à LSPI un concept venant de [lambda]-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LS[lambda]PI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lorincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares [lambda] Policy Iteration (LS[lambda]PI), adds to LSPI an idea of [lambda]-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LS[lambda]PI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lorincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition