Thesis (MSc (Applied Mathematics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: In this dissertation we study the machine learning subfield of Reinforcement Learning (RL). After developing a coherent background, we apply a Monte Carlo (MC) control algorithm with exploring starts (MCES), as well as an off-policy Temporal-Difference (TD) learning control algorithm, Q-learning, to a simplified version of the Weapon Assignment (WA) problem. For the MCES control algorithm, a discount parameter of τ = 1 is used. This gives very promising results when applied to 7 × 7 grids, as well as 71 × 71 grids. The same discount parameter cannot be applied to the Q-learning algorithm, as it causes the Q-values to diverge. We take a greedy approach, setting ε = 0, and vary the learning rate (α ) and the discount parameter (τ). Experimentation shows that the best results are found with set to 0.1 and constrained in the region 0.4 ≤ τ ≤ 0.7. The MC control algorithm with exploring starts gives promising results when applied to the WA problem. It performs significantly better than the off-policy TD algorithm, Q-learning, even though it is almost twice as slow. The modern battlefield is a fast paced, information rich environment, where discovery of intent, situation awareness and the rapid evolution of concepts of operation and doctrine are critical success factors. Combining the techniques investigated and tested in this work with other techniques in Artificial Intelligence (AI) and modern computational techniques may hold the key to solving some of the problems we now face in warfare. / AFRIKAANSE OPSOMMING: Die fokus van hierdie verhandeling is die masjienleer-algoritmes in die veld van versterkingsleer. ’n Koherente agtergrond van die veld word gevolg deur die toepassing van ’n Monte Carlo (MC) beheer-algoritme met ondersoekende begintoestande, sowel as ’n afbeleid Temporale-Verskil beheer-algoritme, Q-leer, op ’n vereenvoudigde weergawe van die wapentoekenningsprobleem. Vir die MC beheer-algoritme word ’n afslagparameter van τ = 1 gebruik. Dit lewer belowende resultate wanneer toegepas op 7 × 7 roosters, asook op 71 × 71 roosters. Dieselfde afslagparameter kan nie op die Q-leer algoritme toegepas word nie, aangesien dit veroorsaak dat die Q-waardes divergeer. Ons neem ’n gulsige aanslag deur die gulsigheidsparameter te verstel na ε = 0. Ons varieer dan die leertempo ( α) en die afslagparameter (τ). Die beste eksperimentele resultate is behaal wanneer = 0.1 en as die afslagparameter vasgehou word in die gebied 0.4 ≤ τ ≤ 0.7. Die MC beheer-algoritme lewer belowende resultate wanneer toegepas op die wapentoekenningsprobleem. Dit lewer beduidend beter resultate as die Q-leer algoritme, al neem dit omtrent twee keer so lank om uit te voer. Die moderne slagveld is ’n omgewing ryk aan inligting, waar dit kritiek belangrik is om vinnig die vyand se planne te verstaan, om bedag te wees op die omgewing en die konteks van gebeure, en waar die snelle ontwikkeling van die konsepte van operasie en doktrine lei tot sukses. Die tegniekes wat in die verhandeling ondersoek en getoets is, en ander kunsmatige intelligensie tegnieke en moderne berekeningstegnieke saamgesnoer, mag dalk die sleutel hou tot die oplossing van die probleme wat ons tans in die gesig staar in oorlogvoering.

Thesis (MComm (Statistics and Actuarial Science)--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: Life insurance and pension funds offer a wide range of products that are invested in a mix of assets. These portfolios (II), underlying the products, are rebalanced back to predetermined fixed proportions on a regular basis. This is done by selling the better performing assets and buying the worse performing assets. Life insurance or pension fund contracts can offer the client a minimum payout guarantee on the contract by charging them an extra premium (a). This problem can be changed to that of the pricing of a put option with underlying . It forms a liability for the insurance firm, and therefore needs to be managed in terms of risks as well. This can be done by studying the option’s sensitivities. In this thesis the premium and sensitivities of this put option are calculated, using different Monte Carlo methods, in order to find the most efficient method. Using general Monte Carlo methods, a simplistic pricing method is found which is refined by applying mathematical techniques so that the computational time is reduced significantly. After considering Antithetic Variables, Control Variates and Latin Hypercube Sampling as variance reduction techniques, option prices as Control Variates prove to reduce the error of the refined method most efficiently. This is improved by considering different Quasi-Monte Carlo techniques, namely Halton, Faure, normal Sobol’ and other randomised Sobol’ sequences. Owen and Faure-Tezuke type randomised Sobol’ sequences improved the convergence of the estimator the most efficiently. Furthermore, the best methods between Pathwise Derivatives Estimates and Finite Difference Approximations for estimating sensitivities of this option are found. Therefore by using the refined pricing method with option prices as Control Variates together with Owen and Faure-Tezuke type randomised Sobol’ sequences as a Quasi-Monte Carlo method, more efficient methods to price this option (compared to simplistic Monte Carlo methods) are obtained. In addition, more efficient sensitivity estimators are obtained to help manage risks. / AFRIKAANSE OPSOMMING: Lewensversekering en pensioenfondse bied die mark ’n wye reeks produkte wat belê word in ’n mengsel van bates. Hierdie portefeuljes (II), onderliggend aan die produkte, word op ’n gereelde basis terug herbalanseer volgens voorafbepaalde vaste proporsies. Dit word gedoen deur bates wat beter opbrengste gehad het te verkoop, en bates met swakker opbrengste aan te koop. Lewensversekeringof pensioenfondskontrakte kan ’n kliënt ’n verdere minimum uitbetaling aan die einde van die kontrak waarborg deur ’n ekstra premie (a) op die kontrak te vra. Die probleem kan verander word na die prysing van ’n verkoopopsie met onderliggende bate . Hierdie vorm deel van die versekeringsmaatskappy se laste en moet dus ook bestuur word in terme van sy risiko’s. Dit kan gedoen word deur die opsie se sensitiwiteite te bestudeer. In hierdie tesis word die premie en sensitiwiteite van die verkoopopsie met behulp van verskillende Monte Carlo metodes bereken, om sodoende die effektiefste metode te vind. Deur die gebruik van algemene Monte Carlo metodes word ’n simplistiese prysingsmetode, wat verfyn is met behulp van wiskundige tegnieke wat die berekeningstyd wesenlik verminder, gevind. Nadat Antitetiese Veranderlikes, Kontrole Variate en Latynse Hiperkubus Steekproefneming as variansiereduksietegnieke oorweeg is, word gevind dat die verfynde metode se fout die effektiefste verminder met behulp van opsiepryse as Kontrole Variate. Dit word verbeter deur verskillende Quasi-Monte Carlo tegnieke, naamlik Halton, Faure, normale Sobol’ en ander verewekansigde Sobol’ reekse, te vergelyk. Die Owen en Faure-Tezuke tipe verewekansigde Sobol’ reeks verbeter die konvergensie van die beramer die effektiefste. Verder is die beste metode tussen Baanafhanklike Afgeleide Beramers en Eindige Differensie Benaderings om die sensitiwiteit vir die opsie te bepaal, ook gevind. Deur dus die verfynde prysingsmetode met opsiepryse as Kontrole Variate, saam met Owen en Faure-Tezuke tipe verewekansigde Sobol’ reekse as ’n Quasi-Monte Carlo metode te gebruik, word meer effektiewe metodes om die opsie te prys, gevind (in vergelyking met simplistiese Monte Carlo metodes). Verder is meer effektiewe sensitiwiteitsberamers as voorheen gevind wat gebruik kan word om risiko’s te help bestuur.

In this thesis, we consider some popular stochastic differential equation models used in finance, such as the Vasicek Interest Rate model, the Heston model and a new fractional Heston model. We discuss how to perform inference about unknown quantities associated with these models in the Bayesian framework. We describe sequential importance sampling, the particle filter and the auxiliary particle filter. We apply these inference methods to the Vasicek Interest Rate model and the standard stochastic volatility model, both to sample from the posterior distribution of the underlying processes and to update the posterior distribution of the parameters sequentially, as data arrive over time. We discuss the sensitivity of our results to prior assumptions. We then consider the use of Markov chain Monte Carlo (MCMC) methodology to sample from the posterior distribution of the underlying volatility process and of the unknown model parameters in the Heston model. The particle filter and the auxiliary particle filter are also employed to perform sequential inference. Next we extend the Heston model to the fractional Heston model, by replacing the Brownian motions that drive the underlying stochastic differential equations by fractional Brownian motions, so allowing a richer dependence structure across time. Again, we use a variety of methods to perform inference. We apply our methodology to simulated and real financial data with success. We then discuss how to make forecasts using both the Heston and the fractional Heston model. We make comparisons between the models and show that using our new fractional Heston model can lead to improve forecasts for real financial data.

The problem of this study was to determine the differences in experimentwise and comparisonwise Type I error rate among six multiple comparison procedures when applied to twenty-eight combinations of normally distributed data. These were the Least Significant Difference, the Fisher-protected Least Significant Difference, the Student Newman-Keuls Test, the Duncan Multiple Range Test, the Tukey Honestly Significant Difference, and the Scheffe Significant Difference. The Spjøtvoll-Stoline and Tukey—Kramer HSD modifications were used for unequal n conditions. A Monte Carlo simulation was used for twenty-eight combinations of k and n. The scores were normally distributed (µ=100; σ=10). Specified multiple comparison procedures were applied under two conditions: (a) all experiments and (b) experiments in which the F-ratio was significant (0.05). Error counts were maintained over 1000 repetitions. The FLSD held experimentwise Type I error rate to nominal alpha for the complete null hypothesis. The FLSD was more sensitive to sample mean differences than the HSD while protecting against experimentwise error. The unprotected LSD was the only procedure to yield comparisonwise Type I error rate at nominal alpha. The SNK and MRT error rates fell between the FLSD and HSD rates. The SSD error rate was the most conservative. Use of the harmonic mean of the two unequal sample n's (HSD-TK) yielded uniformly better results than use of the minimum n (HSD-SS). Bernhardson's formulas controlled the experimentwise Type I error rate of the LSD and MRT to nominal alpha, but pushed the HSD below the 0.95 confidence interval. Use of the unprotected HSD produced fewer significant departures from nominal alpha. The formulas had no effect on the SSD.

Title: Sequential Monte Carlo Methods Author: David Coufal Department: Department of Probability and Mathematical Statistics Supervisor: prof. RNDr. Viktor Beneš, DrSc. Abstract: The thesis summarizes theoretical foundations of sequential Monte Carlo methods with a focus on the application in the area of particle filters; and basic results from the theory of nonparametric kernel density estimation. The summary creates the basis for investigation of application of kernel meth- ods for approximation of densities of distributions generated by particle filters. The main results of the work are the proof of convergence of kernel estimates to related theoretical densities and the specification of the development of approx- imation error with respect to time evolution of a filter. The work is completed by an experimental part demonstrating the work of presented algorithms by simulations in the MATLABR⃝ computational environment. Keywords: sequential Monte Carlo methods, particle filters, nonparametric kernel estimates

This work presents an empirical analysis of popular scenario generation methods for stochastic optimization, including quasi-Monte Carlo, moment matching, and methods based on probability metrics, as well as a new method referred to as Voronoi cell sampling. Solution quality is assessed by measuring the error that arises from using scenarios to solve a multi-dimensional newsvendor problem, for which analytical solutions are available. In addition to the expected value, the work also studies scenario quality when minimizing the expected shortfall using the conditional value-at-risk. To quickly solve problems with millions of random parameters, a reformulation of the risk-averse newsvendor problem is proposed which can be solved via Benders decomposition. The empirical analysis identifies Voronoi cell sampling as the method that provides the lowest errors, with particularly good results for heavy-tailed distributions. A controversial finding concerns evidence for the ineffectiveness of widely used methods based on minimizing probability metrics under high-dimensional randomness.

In this paper, we consider the capture dynamics of a particle undergoing a random walk above a sheet of absorbing traps. In particular, we seek to characterize the distribution in time from when the particle is released to when it is absorbed. This problem is motivated by the study of lymphocytes in the human blood stream; for a particle near the surface of a lymphocyte, how long will it take for the particle to be captured? We model this problem as a diffusive process with a mixture of reflecting and absorbing boundary conditions. The model is analyzed from two approaches. The first is a numerical simulation using a Kinetic Monte Carlo (KMC) method that exploits exact solutions to accelerate a particle-based simulation of the capture time. A notable advantage of KMC is that run time is independent of how far from the traps one begins. We compare our results to the second approach, which is asymptotic approximations of the FPT distribution for particles that start far from the traps. Our goal is to validate the efficacy of homogenizing the surface boundary conditions, replacing the reflecting (Neumann) and absorbing (Dirichlet) boundary conditions with a mixed (Robin) boundary condition.

<p>Integrated tracking and detection, based on unthresholded measurements, also referred to as track before detect (TBD) is a hard nonlinear and non-Gaussian dynamical estimation and detection problem. However, it is a technique that enables the user to track and detect targets that would be extremely hard to track and detect, if possible at all with ''classical'' methods. TBD enables us to be better able to detect and track weak, stealthy or dim targets in noise and clutter and particles filter have shown to be very useful in the implementation of TBD algorithms. </p><p>This Master's thesis has investigated the use of particle filters on radar measurements, in a TBD approach.</p><p>The work has been divided into two major problems, a time efficient implementation and new functional features, as estimating the radar cross section (RCS) and the extension of the target. The later is of great importance when the resolution of the radar is such, that specific features of the target can be distinguished. Results will be illustrated by means of realistic examples.</p>

Non-linear Bayesian estimation, or estimation of the state of a non-linear stochastic system from a set of indirect noisy measurements is a problem encountered in several fields of science. The particle filter and the ensemble Kalman filter are both used to get sub-optimal solutions of Bayesian inference problems, particularly for high-dimensional non-Gaussian and non-linear models. Both are essentially Monte Carlo techniques that compute their results using a set of estimated trajectories of the variable to be monitored. It has been shown that in a linear and Gaussian environment, solutions obtained from both these filters converge to the optimal solution obtained by the Kalman Filter. However, it is of interest to explore how the two filters compare to each other in basic methodology and construction, especially due to the similarity between them. In this work, we take up a specific problem of Bayesian inference in a restricted framework and compare analytically the results obtained from the particle filter and the ensemble Kalman filter. We show that for the chosen model, under certain assumptions, the two filters become methodologically analogous as the sample size goes to infinity.

Integrated tracking and detection, based on unthresholded measurements, also referred to as track before detect (TBD) is a hard nonlinear and non-Gaussian dynamical estimation and detection problem. However, it is a technique that enables the user to track and detect targets that would be extremely hard to track and detect, if possible at all with ''classical'' methods. TBD enables us to be better able to detect and track weak, stealthy or dim targets in noise and clutter and particles filter have shown to be very useful in the implementation of TBD algorithms. This Master's thesis has investigated the use of particle filters on radar measurements, in a TBD approach. The work has been divided into two major problems, a time efficient implementation and new functional features, as estimating the radar cross section (RCS) and the extension of the target. The later is of great importance when the resolution of the radar is such, that specific features of the target can be distinguished. Results will be illustrated by means of realistic examples.