An analog circuit for beamforming in a mobile Ku band satellite TV antenna array has been implemented. The circuit performs continuous-time gradient descent using simultaneous perturbation gradient estimation. Simulations were performed using Agilent ADS circuit simulator. Field tests were performed in a realistic scenario using a satellite signal. The results were comparable to the simulation predictions and to results obtained using a digital implementation of a similar stochastic approximation algorithm.

This dissertation research consists of two topics, population stochastics approximation Monte Carlo (Pop-SAMC) for Baysian model selection problems and ChIP-chip data analysis. The following two paragraphs give a brief introduction to each of the two topics, respectively. Although the reversible jump MCMC (RJMCMC) has the ability to traverse the space of possible models in Bayesian model selection problems, it is prone to becoming trapped into local mode, when the model space is complex. SAMC, proposed by Liang, Liu and Carroll, essentially overcomes the difficulty in dimension-jumping moves, by introducing a self-adjusting mechanism. However, this learning mechanism has not yet reached its maximum efficiency. In this dissertation, we propose a Pop-SAMC algorithm; it works on population chains of SAMC, which can provide a more efficient self-adjusting mechanism and make use of crossover operator from genetic algorithms to further increase its efficiency. Under mild conditions, the convergence of this algorithm is proved. The effectiveness of Pop-SAMC in Bayesian model selection problems is examined through a change-point identification example and a large-p linear regression variable selection example. The numerical results indicate that Pop- SAMC outperforms both the single chain SAMC and RJMCMC significantly. In the ChIP-chip data analysis study, we developed two methodologies to identify the transcription factor binding sites: Bayesian latent model and population-based test. The former models the neighboring dependence of probes by introducing a latent indicator vector; The later provides a nonparametric method for evaluation of test scores in a multiple hypothesis test by making use of population information of samples. Both methods are applied to real and simulated datasets. The numerical results indicate the Bayesian latent model can outperform the existing methods, especially when the data contain outliers, and the use of population information can significantly improve the power of multiple hypothesis tests.

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.

Computational stereo estimates 3D structure by analyzing visual changes between two or more passive images of a scene that are captured from different viewpoints. It is a key enabler for ubiquitous autonomous systems, large-scale surveying, virtual reality, and improved techniques for compression, tracking, and object recognition. The fact that computational stereo is an under-constrained inverse problem causes many challenges. Its computational and memory requirements are high. Typical heuristics and assumptions, used to constrain solutions or reduce computation, prevent treatment of key realities such as reflection, translucency, ambient lighting changes, or moving objects in the scene. As a result, a general solution is lacking. Stochastic models are common in computational stereo, but stochastic algorithms are severely under-represented. In this dissertation I present two stochastic algorithms and demonstrate their advantages over deterministic approaches. I first present the Quality-Efficient Stochastic Sampling (QUESS) approach. QUESS reduces the number of match quality function evaluations needed to estimate dense stereo correspondences. This facilitates the use of complex quality metrics or metrics that take unique values at non-integer disparities. QUESS is shown to outperform two competing approaches, and to have more attractive memory and scaling properties than approaches based on exhaustive sampling. I then present a second novel approach based on the Hough transform and extend it with distributed ray tracing (DRT). DRT is a stochastic anti-aliasing technique common to computer rendering but which has not been used in computational stereo. I demonstrate that the DRT-enhanced approach outperforms the unenhanced approach, a competing variation that uses re-accumulation in the Hough domain, and another baseline approach. DRT’s advantages are particularly strong for reduced image resolution and/or reduced accumulator matrix resolution. In support of this second approach, I develop two novel variations of the Hough transform that use DRT, and demonstrate that they outperform competing variations on a traditional line segment detection problem. I generalize these two examples to draw broader conclusions, suggest future work, and call for a deeper exploration by the community. Both practical and academic gaps in the state of the art can be reduced by a renewed exploration of stochastic computational stereo techniques. / text

This PhD thesis consists of a summary and four papers which deal with stochastic approximation algorithms and first-passage percolation. Paper I deals with the a.s. limiting properties of bounded stochastic approximation algorithms in relation to the equilibrium points of the drift function. Applications are given to some generalized Pólya urn processes. Paper II continues the work of Paper I and investigates under what circumstances one gets asymptotic normality from a properly scaled algorithm. The algorithms are shown to converge in some other circumstances, although the limiting distribution is not identified. Paper III deals with the asymptotic speed of first-passage percolation on a graph called the ladder when the times associated to the edges are independent, exponentially distributed with the same intensity. Paper IV generalizes the work of Paper III in allowing more edges in the graph as well as not having all intensities equal.

In this dissertation, we have proposed two new algorithms for statistical inference for models with intractable normalizing constants: the Monte Carlo Metropolis-Hastings algorithm and the Bayesian Stochastic Approximation Monte Carlo algorithm. The MCMH algorithm is a Monte Carlo version of the Metropolis-Hastings algorithm. At each iteration, it replaces the unknown normalizing constant ratio by a Monte Carlo estimate. Although the algorithm violates the detailed balance condition, it still converges, as shown in the paper, to the desired target distribution under mild conditions. The BSAMC algorithm works by simulating from a sequence of approximated distributions using the SAMC algorithm. A strong law of large numbers has been established for BSAMC estimators under mild conditions. One significant advantage of our algorithms over the auxiliary variable MCMC methods is that they avoid the requirement for perfect samples, and thus it can be applied to many models for which perfect sampling is not available or very expensive. In addition, although the normalizing constant approximation is also involved in BSAMC, BSAMC can perform very robustly to initial guesses of parameters due to the powerful ability of SAMC in sample space exploration. BSAMC has also provided a general framework for approximated Bayesian inference for the models for which the likelihood function is intractable: sampling from a sequence of approximated distributions with their average converging to the target distribution. With these two illustrated algorithms, we have demonstrated how the SAMCMC method can be applied to estimate the parameters of ERGMs, which is one of the typical examples of statistical models with intractable normalizing constants. We showed that the resulting estimate is consistent, asymptotically normal and asymptotically efficient. Compared to the MCMLE and SSA methods, a significant advantage of SAMCMC is that it overcomes the model degeneracy problem. The strength of SAMCMC comes from its varying truncation mechanism, which enables SAMCMC to avoid the model degeneracy problem through re-initialization. MCMLE and SSA do not possess the re-initialization mechanism, and tend to converge to a solution near the starting point, so they often fail for the models which suffer from the model degeneracy problem.

This dissertation contains two topics in operations research. The first topic is to design a distribution network to facilitate the repeated movement of shipments from many origins to many destinations. A method is developed to estimate transportation costs as a function of the number of terminals and moreover to determine the best number of terminals. The second topic is to study dynamics of a buyer's behavior when the buyer can buy goods through both option contracts and a spot market and the buyer attempts to learn the probability distribution of the spot price. The buyer estimates the spot price distribution as though it is exogenous. However, the spot price distribution is not exogenous but is endogenous because it is affected by the buyer's decision regarding option purchases.

L'approche de la biologie des systèmes vise à intégrer les méthodologies appliquées dans la conception et l'analyse des systèmes technologiques complexes, au sein de la biologie afin de comprendre les principes de fonctionnement globaux des systèmes biologiques. La thèse s'inscrit dans le cadre de la biologie des systèmes et en particulier dans la prolongation d'une méthode issue de ce cadre : la méthode Resource Blance Analysis (RBA). Nous visons dans cette thèse à augmenter le pouvoir prédictif de la méthode via un travail de modélisation tout en gardant un bon compromis entre représentativité des modèles issus de ce cadre et leur résolution numérique efficace. La thèse se décompose en deux grandes parties : la première vise à intégrer les aspects thermodynamiques et cinétiques inhérents aux réseaux métaboliques. La deuxième vise à comprendre l'impact de l'aspect stochastique de la production des enzymes sur le croissance de la bactérie. Des méthodes numériques ont été élaborées pour la résolution des modèles ainsi établis dans les deux cas déterministe et stochastique. / In order to understand the global functioning principals of biological systems, system bio- logy approach aims to integrate the methodologies used in the conception and the analysis of complex technological systems, within the biology. This PhD thesis fits into the system biology framework and in particular the extension of the already existing method Resource Balance Analysis (RBA). We aim in this PhD thesis to improve the predictive power of this method by introducing more complex model. However, this new model should respect a good trade-off between the representativity of the model and its efficient numerical computation. This PhD thesis is decomposed into two major parts. The first part aims the integration of the metabolic network inherent thermodynamical and kinetic aspects. The second part aims the comprehension of the impact of enzyme production stochastic aspect on the bacteria growth. Numerical methods are elaborated to solve the obtained models in both deterministic and stochastic cases.

La thèse porte sur l'apport de la méthode de Laplace pour l'approximation du filtre bayésien dans des modèles de Markov cachés généraux, c'est-à-dire dans un cadre séquentiel, avec comme domaine d'application privilégié la poursuite de cibles mobiles. A la base, la méthode de Laplace est une méthode asymptotique pour le calcul d'intégrales, c'est-à-dire dans un cadre statique, valide en théorie dès que la fonction à intégrer présente un maximum de plus en plus significatif, lequel apporte la contribution essentielle au résultat. En pratique, cette méthode donne des résultats souvent très précis même en dehors de ce cadre de validité théorique. Les deux contributions principales de la thèse sont les suivantes. Premièrement, nous avons utilisé la méthode de Laplace en complément du filtrage particulaire : on sait en effet que les méthodes de Monte Carlo séquentielles basées sur l'échantillonnage pondéré sont mises en difficulté quand la fonction de pondération (ici la fonction de vraisemblance) est trop localisée, par exemple quand la variance du bruit d'observation est trop faible, or c'est précisément là le domaine où la méthode de Laplace est efficace et justifiée théoriquement, d'où l'idée naturelle de combiner les deux points de vue. Nous proposons ainsi un algorithme associant la méthode de Laplace et le filtrage particulaire, appelé le Laplace particle filter. Deuxièmement, nous avons analysé l'approximation du filtre bayésien grâce à la méthode de Laplace seulement (c'est-à-dire sans génération d'échantillons aléatoires) : il s'agit ici de contrôler la propagation de l'erreur d'approximation d'un pas de temps au pas de temps suivant, dans un cadre asymptotique approprié, par exemple quand le bruit d'observation tend vers zéro, ou quand le bruit d'état et le bruit d'observation tendent conjointement (et à la même vitesse) vers zéro, ou plus généralement quand l'information contenue dans le système tend vers l'infini, avec une interprétation en terme d'identifiabilité. / The thesis deals with the contribution of the Laplace method to the approximation of the Bayesian filter in hidden Markov models with continuous state--space, i.e. in a sequential framework, with target tracking as the main application domain. Originally, the Laplace method is an asymptotic method used to compute integrals, i.e. in a static framework, valid in theory as soon as the function to be integrated exhibits an increasingly dominating maximum point, which brings the essential contribution to the integral. The two main contributions of the thesis are the following. Firstly, we have combined the Laplace method and particle filters: indeed, it is well-known that sequential Monte Carlo methods based on importance sampling are inefficient when the weighting function (here, the likelihood function) is too much spatially localized, e.g. when the variance of the observation noise is too small, whereas this is precisely the situation where the Laplace method is efficient and theoretically justified, hence the natural idea of combining the two approaches. We thus propose an algorithm associating the Laplace method and particle filtering, called the Laplace particle filter. Secondly, we have analyzed the approximation of the Bayesian filter based on the Laplace method only (i.e. without any generation of random samples): the objective has been to control the propagation of the approximation error from one time step to the next time step, in an appropriate asymptotic framework, e.g. when the variance of the observation noise goes to zero, or when the variances of the model noise and of the observation noise jointly go (with the same rate) to zero, or more generally when the information contained in the system goes to infinity, with an interpretation in terms of identifiability.

La diversité croissante des différents agents constituant les réseaux de communication actuels ainsi que la capacité accrue des technologies concurrentes dans l’environnement réseau a conduit à la prise en compte d’une nouvelle approche distribuée de la gestion du réseau. Dans cet environnement réseau évolué, le besoin en accroissement de la bande passante et en ressources rares, s’oppose à la réduction de la consommation énergétique globale.Dans notre travail nous nous intéressons à l’application de mécanismes distribués et de méthodes d’apprentissages visant à introduire d’avantage d’autonomie dans les réseaux hétérogènes, mobiles en particulier, tout en améliorant les performances par rapport aux débits et à la qualité de service. Notre étude se concentre principalement sur l’élaboration de mécanismes distribués stochastiques et énergétiquement efficaces en profitant des capacités de calcul de tous les agents et entités du réseau. Divers outils de la théorie des jeux nous permettent de modéliser et d’étudier différents types de systèmes dont la complexité est induite par la grande taille, l’hétérogénéité et le caractère dynamique des interconnexions. Plus spécifiquement, nous utilisons des outils d’apprentissage par renforcement pour aborder des questions telles que l’attachement distribué des utilisateurs permettant une gestion dynamique, décentralisée et efficace des ressources radio. Nous combinons ensuite les procédures de sélection d’accès à des méthodes d’optimisation distribuées du type gradient stochastique, pour adresser le problème de coordination des interférences intercellulaires (ICIC) dans les réseaux LTE-A. Cette approche se base sur un contrôle de puissance dynamique conduisant à une réutilisation fractionnaire des fréquences radios. Par ailleurs nous adressons dans les réseaux décentralisés non-hiérarchiques, plus précisément les réseaux tolérants aux délais (DTNs), des méthodes décentralisées liées à la minimisation du délai de transmission de bout en bout. Dans ce cadre nous nous intéressons, en outre des équilibres de Nash, à la notion d’équilibre évolutionnairement stables dans différents contextes de jeux évolutionnaires, jeux évolutionnaires décisionnels markoviens et jeux de minorité. Enfin, la majeure partie du travail effectué se rattachant aux tests et validations par simulations,nous présentons plusieurs éléments d’implémentations et d’intégrations liés à la mise en place de plateformes de simulations et d’expérimentations / Growing diversity of agents in current communication networks and increasing capacitiesof concurrent technologies in the network environment has lead to the considerationof a novel distributed approach of the network management. In this evolvednetwork environment the increasing need for bandwidth and rare channel resources,opposes to reduction of the total energy consumption.This thesis focuses on application of distributed mechanisms and learning methodsto allow for more autonomy in the heterogeneous network, this in order to improveits performances. We are mainly interested in energy efficient stochastic mechanismsthat will operate in a distributed fashion by taking advantage of the computationalcapabilities of all the agents and entities of the network. We rely on application ofGame theory to study different types of complex systems in the distributed wirelessnetworks with dynamic interconnectivity.Specifically, we use the stochastic reinforcement learning tools to address issuessuch as, distributed user-network association that allows achieving an efficient dynamicand decentralized radio resource management. Then, we combine access selectionprocedures with distributed optimization to address the inter-cells interferencescoordination (ICIC) for LTE-advanced networks using dynamic power control and designof fractional frequency reuse mechanisms. Moreover we address in non-hierarchicalnetworks, more precisely in Delay Tolerant Networks (DTNs), decentralized methodsrelated to minimization of the end-to-end communication delay. In this framework weare interested, in addition to Nash equilibrium, to the notion of evolutionary stableequiliria in the different context of Evolutionary Games, Markov Decision EvolutionaryGames and Minority Games. As the major parts of our work includes testing andvalidations by simulations, eventually we present several implementations and integrationsmaterials for edition of simulation platforms and test beds