Probabilistic programming languages (PPLs) provide users with an interface to write probabilistic models and leave the statistical inference to the compiler and runtime systems. Ideally, the purpose of PPLs is to provide a seamless inference interface that makes the model and the inference parts modular. Yet, the structure of the user-defined model affects inference accuracy and execution time. Users can utilize certain structures, such as conjugate prior relations or tree structures within a given model, to improve inference efficiency; however, manually utilizing these structures in a model is time-consuming and error-prone. Especially as the PPL's expressiveness increases, the models may become too complex to rewrite. This thesis tackles the problems related to the automation of optimizations, improving the execution time and the accuracy of the inference based on the structure of the model. Further, it aims to make these optimizations expressive enough to handle complex models written in universal PPLs. 

The scope of this thesis is to optimize Bayesian inference in universal PPLs. The three contributions presented propose automated optimization approaches to improving the inference accuracy and execution time while preserving the expressiveness of the optimized program. The first contribution considers dynamic delayed sampling, a runtime algorithm to reduce inference variance through analytical relationships between random variables. We develop a compile-time version of the delayed sampling algorithm to reduce execution overhead. The second contribution regards the design and implementation of dynamic delayed sampling in a statically typed universal PPL, Miking CorePPL. Integrating delayed sampling into a statically typed PPL requires introducing additional constructs to the language. The third contribution is related to the forward pass of belief propagation algorithm, an efficient inference algorithm on tree graphs. We propose an approach automating this forward pass of belief propagation in statically typed universal PPLs to optimize likelihood calculations by utilizing the tree structures in a model. We evaluate the proposed approaches on real-world problems, such as topic modeling and phylogenetic problems.

Probabilistiska programmeringsspråk (PPS) ger användare ett gränssnitt för att skriva probabilistiska modeller och överlåta den statistiska inferensen till kompilatorn och runtime-systemen. Idealiskt sett är syftet med PPS att erbjuda ett sömlöst inferencesgränssnitt som gör modell- och inferensdelarna modulära. Dock påverkas inferensens noggrannhet och exekveringstid av strukturen hos den användardefinierade modellen. Användare kan utnyttja vissa strukturer, såsom konjugerade prior-relationer eller trädsstrukturer inom en given modell, för att förbättra inferensens effektivitet; men att manuellt använda dessa strukturer i en modell är tidskrävande och felbenäget. Speciellt när PPL uttrycksförmåga ökar, kan modellerna bli för komplexa för att skrivas om på detta sätt. Denna avhandling tar itu med problemen relaterade till automatisering av optimeringar, förbättring av exekveringstid och noggrannheten hos inferens baserat på modellens struktur. Vidare fokuseras hur dessa optimeringar kan göras tillräckligt uttrycksfulla för att hantera komplexa modeller skrivna i universella PPS.

Omfattningen av denna avhandling är att optimera Bayesiansk inferens i universella PPS. De tre bidragen som presenteras föreslår automatiserade optimeringsmetoder för att förbättra inferensens noggrannhet och exekveringstid samtidigt som uttrycksfullheten hos det optimerade programmet bevaras. Det första bidraget behandlar dynamisk fördröjd sampling, en runtime-algoritm för att minska inferensens varians genom att använda analytiska relationer mellan slumpmässiga variabler. Vi utvecklar en kompileringstid-version av den fördröjda samplingalgoritmen för att minska exekveringsomkostnad. Det andra bidraget gäller design och implementering av dynamisk fördröjd sampling i Miking CorePPL, som är ett statiskt typat universellt PPS. Att integrera fördröjd sampling i ett statiskt typat PPS kräver införande av ytterligare konstruktioner i språket. Det tredje bidraget är relaterat till framåtpasset av belief propagation-algoritmen, en effektiv inferensalgoritm på trädgrafer. Vi föreslår en metod för att automatisera detta framåtpass av belief propagation i statiskt typade universella PPS för att optimera sannolikhetsberäkningar genom att utnyttja trädsstrukturer i en modell. Vi utvärderar de föreslagna metoderna på verkliga problem, såsom ämnesmodellering och fylogenetiska problem.

Probabilistic programming languages (PPLs) make it possible to separate the concerns between probabilistic models and Bayesian inference algorithms. However, to make such inference efficient is technically very challenging, both in terms of execution time performance and inference accuracy. One successful optimization approach is the previously published work on dynamically delayed sampling. This runtime method makes use of analytical relations between random variables to reduce inference variance; however, tracking these relations introduces runtime overhead. Furthermore, implementing the dynamic approach in a statically typed language introduces type problems because delaying the sampling of random variables changes their types. Our work advances the state-of-the-art in two aspects. Firstly, to reduce the runtime overhead, we develop a compile-time version of delayed sampling. By incorporating optimization procedures during compilation, we eliminate the need for runtime relation tracking and consequent overhead. However, the compile-time version may not always be effective due to the program's possible dynamic behavior, such as stochastic branches, or the complexity of handling recursion. Secondly, we introduce constructs to implement dynamically delayed sampling in a statically typed universal PPL. Dynamically delayed sampling in statically typed languages is a viable optimization for complex Bayesian models, whereas simple models ought to be statically optimized. We evaluate both statically and dynamically delayed sampling on real-world examples, such as latent Dirichlet allocation and epidemiology models, and implement the methods in a statically typed PPL, Miking CorePPL.

Probabilistic Programming Languages (PPLs) allow users to encode statistical inference problems and automatically apply an inference algorithm to solve them. Popular inference algorithms for PPLs, such as sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC), are built around checkpoints—relevant events for the inference algorithm during the execution of a probabilistic program. Deciding the location of checkpoints is, in current PPLs, not done optimally. To solve this problem, we present a static analysis technique that automatically determines checkpoints in programs, relieving PPL users of this task. The analysis identifies a set of checkpoints that execute in the same order in every program run—they are aligned. We formalize alignment, prove the correctness of the analysis, and implement the analysis as part of the higher-order functional PPL Miking CorePPL. By utilizing the alignment analysis, we design two novel inference algorithm variants: aligned SMC and aligned lightweight MCMC. We show, through real-world experiments, that they significantly improve inference execution time and accuracy compared to standard PPL versions of SMC and MCMC.

Genome-wide association studies explain a fraction of the underlying heritability of genetic diseases. Investigating epistatic interactions between two or more loci help closing this gap. Unfortunately, sheer number of loci combinations to process and hypotheses to test prohibit the process both computationally and statistically. Epistasis test prioritization algorithms rank likely-epistatic SNP pairs to limit the number of tests. Yet, they still suffer from very low precision. It was shown in the literature that selecting SNPs that are individually correlated with the phenotype and also diverse with respect to genomic location, leads to better phenotype prediction due to genetic complementation. Here, we propose that an algorithm that pairs SNPs from such diverse regions and ranks them can improve prediction power. We propose an epistasis test prioritization algorithm which optimizes a submodular set function to select a diverse and complementary set of genomic regions that span the underlying genome. SNP pairs from these regions are then further ranked w.r.t. their co-coverage of the case cohort. We compare our algorithm with the state-of-the-art on three GWAS and show that (i) we substantially improve precision (from 0.003 to 0.652) while maintaining the significance of selected pairs, (ii) decrease the number of tests by 25 folds, and (iii) decrease the runtime by 4 folds. We also show that promoting SNPs from regulatory/coding regions improves the performance (up to 0.8). Potpourri is available at http:/ciceklab.cs.bilkent.edu.tr/potpourri.

Probabilistic programming languages aim to separate the user-specified model from the inference allowing users to focus on model design and leave inference to the compiler and runtime systems. However, the structure of the model affects the inference efficiency. We can utilize specific structures in the model to improve inference efficiency, such as random variables forming trees. In this work, we propose pruning, an approach that automates the forward pass of belief propagation to improve the efficiency of likelihood calculations in statically typed universal probabilistic programming languages (PPLs) by utilizing the tree structures within a model. Specifically, users annotate variables for marginalization, making the likelihood calculation more efficient. We present our method implemented in the probabilistic programming language Miking CorePPL and demonstrate the performance of our approach through a series of case studies in phylogenetics.

Probabilistic programming languages (PPLs) make it possible to separate the concerns between probabilistic models and Bayesian inference algorithms. However, to make such inference efficient is technically very challenging, both in terms of execution time performance and inference accuracy. One successful optimization approach is the previously published work on dynamically delayed sampling. This runtime method makes use of analytical relations between random variables to reduce inference variance; however, tracking these relations introduces runtime overhead. Furthermore, implementing the dynamic approach in a statically typed language introduces type problems because delaying the sampling of random variables changes their types. Our work advances the state-of-the-art in two aspects. Firstly, to reduce the runtime overhead, we develop a compile-time version of delayed sampling. By incorporating optimization procedures during compilation, we eliminate the need for runtime relation tracking and consequent overhead. However, the compile-time version may not always be effective due to the program's possible dynamic behavior, such as stochastic branches, or the complexity of handling recursion. Secondly, we introduce constructs to implement dynamically delayed sampling in a statically typed universal PPL. Dynamically delayed sampling in statically typed languages is a viable optimization for complex Bayesian models, whereas simple models ought to be statically optimized. We evaluate both statically and dynamically delayed sampling on real-world examples, such as latent Dirichlet allocation and phylogenetic models, and implement the methods in a statically typed PPL, Miking CorePPL.