Not available / text

published_or_final_version / Physics / Master / Master of Philosophy

No description available.

No description available.

No description available.

This thesis contains the author’s work in and contributions to the field of Monte Carlo sampling for undirected graphical models, a class of statistical model commonly used in machine learning, computer vision, and spatial statistics; the aim is to be able to use the methodology and resultant samples to estimate integrals of functions of the variables in the model. Over the course of the study, three different but related methods were proposed and have appeared as research papers. The thesis consists of an introductory chapter discussing the models considered, the problems involved, and a general outline of Monte Carlo methods. The three subsequent chapters contain versions of the published work. The second chapter, which has appeared in (Hamze and de Freitas 2004), is a presentation of new MCMC algorithms for computing the posterior distributions and expectations of the unknown variables in undirected graphical models with regular structure. For demonstration purposes, we focus on Markov Random Fields (MRFs). By partitioning the MRFs into non-overlapping trees, it is possible to compute the posterior distribution of a particular tree exactly by conditioning on the remaining tree. These exact solutions allow us to construct efficient blocked and Rao-Blackwellised MCMC algorithms. We show empirically that tree sampling is considerably more efficient than other partitioned sampling schemes and the naive Gibbs sampler, even in cases where loopy belief propagation fails to converge. We prove that tree sampling exhibits lower variance than the naive Gibbs sampler and other naive partitioning schemes using the theoretical measure of maximal correlation. We also construct new information theory tools for comparing different MCMC schemes and show that, under these, tree sampling is more efficient. Although the work discussed in Chapter 2 exhibited promise on the class of graphs to which it was suited, there are many cases where limiting the topology is quite a handicap. The work in Chapter 3 was an exploration in an alternative methodology for approximating functions of variables representable as undirected graphical models of arbitrary connectivity with pairwise potentials, as well as for estimating the notoriously difficult partition function of the graph. The algorithm, published in (Hamze and de Freitas 2005), fits into the framework of sequential Monte Carlo methods rather than the more widely used MCMC, and relies on constructing a sequence of intermediate distributions which get closer to the desired one. While the idea of using “tempered” proposals is known, we construct a novel sequence of target distributions where, rather than dropping a global temperature parameter, we sequentially couple individual pairs of variables that are, initially, sampled exactly from a spanning treeof the variables. We present experimental results on inference and estimation of the partition function for sparse and densely-connected graphs. The final contribution of this thesis, presented in Chapter 4 and also in (Hamze and de Freitas 2007), emerged from some empirical observations that were made while trying to optimize the sequence of edges to add to a graph so as to guide the population of samples to the high-probability regions of the model. Most important among these observations was that while several heuristic approaches, discussed in Chapter 1, certainly yielded improvements over edge sequences consisting of random choices, strategies based on forcing the particles to take large, biased random walks in the state-space resulted in a more efficient exploration, particularly at low temperatures. This motivated a new Monte Carlo approach to treating complex discrete distributions. The algorithm is motivated by the N-Fold Way, which is an ingenious event-driven MCMC sampler that avoids rejection moves at any specific state. The N-Fold Way can however get “trapped” in cycles. We surmount this problem by modifying the sampling process to result in biased state-space paths of randomly chosen length. This alteration does introduce bias, but the bias is subsequently corrected with a carefully engineered importance sampler.

No description available.

No description available.

The advantages of Multilevel Item Response Theory (MLIRT) model have been studied by several researchers, and even the impact of ignoring a higher level of data structure in multilevel analysis has been studied and discussed. However, due to the technical complexity of modeling and the shortage in function of dealing with multilevel data in traditional IRT packages (e.g., BILOG and PARSCALE), researchers may not be able to analyze the multilevel IRT data accurately. The impact of this type of misspecification, especially for MLIRT models, has not yet been thoughtfully examined. This dissertation consists of two studies: one is a Monte Carlo study that investigates the impact of this type of misspecification and the other one is a study with real-world data to validate the results obtaining from the simulation study. In Study One (the simulation study), we investigate the potential impact of several factors, including: intra-class correlation (ICC), sample size, cluster size and test length, on the parameter estimates and corresponding test of significance under two situations: when the higher level nesting structure is appropriately modeled (i.e., true model condition) versus inappropriately modeled (i.e., misspecified model condition). Three-level straightly hierarchical data (i.e., items are nested within students who are further nested within schools) were generated. Two person-related and school-related covariates were added at the second level (i.e., person-level) and the third level (i.e., school-level), respectively. The results of simulation studies showed that both parameter estimates and their corresponding standard errors would be biased if the higher level nesting structure was ignored. In Study Two, a real data from the Programme for International Student Assessment with purely hierarchical structure were analyzed by comparing parameter estimates when inappropriate versus appropriate IRT models are specified. The findings mirrored the results obtained from the first study. The implication of this dissertation to researchers is that it is important to model the multilevel data structure even in item response theory models. Researchers should interpret their results in caution when ignoring a higher level nesting structure in MLIRT models. What's more, the findings may help researchers determine when MLIRT should be used to get an unbiased result. Limitations concerning about some of the constraints of the simulation study could be relaxed. For instance, although this study used only dichotomous items, the MLIRT could also be used with polytomous items. The test length could be longer and more variability could be introduced into the item parameters’ values.

This thesis shows highly encouraging results as the gain of accuracy reached 18.4% when the pairwise comparisons method was used instead of the direct method for comparing random shapes. The thesis describes a heuristic for generating random but nice shapes, called placated shapes. Random, but visually nice shapes, are often needed for cognitive experiments and processes. These shapes are produced by applying the Gaussian blur to randomly generated polygons. Afterwards, the threshold is set to transform pixels to black and white from di erent shades of gray. This transformation produces placated shapes for easier estimation of areas. Randomly generated placated shapes are used to perform the Monte Carlo method to test the accuracy of cognitive processes by using pairwise comparisons. An on-line questionnaire has been implemented and participants were asked to estimate the areas of ve shapes using a provided unit of measure. They were also asked to compare the shapes in pairs. Such Monte Carlo experiment has never been conducted for 2D case. The received results are of considerable importance.