Discrete location analysis is one of the most widely studied branches of operations research, whose applications arise in a wide variety of settings. This thesis describes a powerful new approach to facility location problems - that of message passing inference in probabilistic graphical models. Using this framework, we develop new heuristic algorithms, as well as a new approximation algorithm for a particular problem type. In machine learning applications, facility location can be seen a discrete formulation of clustering and mixture modeling problems. We apply the developed algorithms to such problems in computer vision. We tackle the problem of motion segmentation in video sequences by formulating it as a facility location instance and demonstrate the advantages of message passing algorithms over current segmentation methods.

A phenomenon as complex as protein folding requires a complex model to approximate it. This thesis presents a bottom-up approach for building complex probabilistic models of protein secondary structure by incorporating the multiple information sources which we call experts. Expert opinions are represented by probability distributions over the set of possible structures. Bayesian treatment of a group of experts results in a consensus opinion that combines the experts' probability distributions using the operators of normalized product, quotient and exponentiation. The expression of this consensus opinion simplifiesto a product of the expert opinions with two assumptions: (1) balanced training of experts, i. e. , uniform prior probability over all structures, and (2) conditional independence between expert opinions,given the structure. This research also studies how Markov chains and hidden Markov models may be used to represent expert opinion. Closure properties areproven, and construction algorithms are given for product of hidden Markov models, and product, quotient and exponentiation of Markovchains. Algorithms for extracting single-structure predictions from these models are also given. Current product-of-experts approaches in machine learning are top-down modeling strategies that assume expert independence, and require simultaneous training of all experts. This research describes a bottom-up modeling strategy that can incorporate conditionally dependent experts, and assumes separately trained experts.

Conventional pattern recognition systems have two components: feature analysis and pattern classification. For any object in an image, features could be considered as the major characteristic of the object either for object recognition or object tracking purpose. Features extracted from a training image, can be used to identify the object when attempting to locate the object in a test image containing many other objects. To perform reliable scene analysis, it is important that the features extracted from the training image are detectable even under changes in image scale, noise and illumination. Scale invariant feature has wide applications such as image classification, object recognition and object tracking in the image processing area. In this thesis, color feature and SIFT (scale invariant feature transform) are considered to be scale invariant feature. The classification, recognition and tracking result were evaluated with novel evaluation criterion and compared with some existing methods. I also studied different types of scale invariant feature for the purpose of solving scene analysis problems. I propose probabilistic models as the foundation of analysis scene scenario of images. In order to differential the content of image, I develop novel algorithms for the adaptive combination for multiple features extracted from images. I demonstrate the performance of the developed algorithm on several scene analysis tasks, including object tracking, video stabilization, medical video segmentation and scene classification.

Probabilistic modeling with latent variables is a powerful paradigm that has led to key advances in many applications such natural language processing, text mining, and computational biology. Unfortunately, while introducing latent variables substantially increases representation power, learning and modeling can become considerably more complicated. Most existing solutions largely ignore non-identifiability issues in modeling and formulate learning as a nonconvex optimization problem, where convergence to the optimal solution is not guaranteed due to local minima. In this thesis, we propose to tackle these problems through the lens of linear/multi-linear algebra. Viewing latent variable models from this perspective allows us to approach key problems such as structure learning and parameter learning using tools such as matrix/tensor decompositions, inversion, and additive metrics. These new tools enable us to develop novel solutions to learning in latent variable models with theoretical and practical advantages. For example, our spectral parameter learning methods for latent trees and junction trees are provably consistent, local-optima-free, and 1-2 orders of magnitude faster thanEMfor large sample sizes. In addition, we focus on applications in Natural Language Processing, using our insights to not only devise new algorithms, but also to propose new models. Our method for unsupervised parsing is the first algorithm that has both theoretical guarantees and is also practical, performing favorably to theCCMmethod of Klein and Manning. We also developed power low rank ensembles, a framework for language modeling that generalizes existing n-gram techniques to non-integer n. It consistently outperforms state-of-the-art Kneser Ney baselines and can train on billion-word datasets in a few hours.

Mining association rules is an important technique for discovering meaningful patterns in transaction databases. Many different measures of interestingness have been proposed for association rules. However, these measures fail to take the probabilistic properties of the mined data into account. In this paper, we start with presenting a simple probabilistic framework for transaction data which can be used to simulate transaction data when no associations are present. We use such data and a real-world database from a grocery outlet to explore the behavior of confidence and lift, two popular interest measures used for rule mining. The results show that confidence is systematically influenced by the frequency of the items in the left hand side of rules and that lift performs poorly to filter random noise in transaction data. Based on the probabilistic framework we develop two new interest measures, hyper-lift and hyper-confidence, which can be used to filter or order mined association rules. The new measures show significant better performance than lift for applications where spurious rules are problematic. / Series: Research Report Series / Department of Statistics and Mathematics

This thesis lies in the field of probabilistic and extremal combinatorics: we study discrete structures, with a focus on thresholds, when the behaviour of a structure changes from one mode into another. From a probabilistic perspective, we consider models for a random structure depending on some parameter. The questions we study are then: When (i.e. for what values of the parameter) does the probability of a given property go from being almost 0 to being almost 1? How do the models behave as this transition occurs? From an extremal perspective, we study classes of structures depending on some parameter. We are then interested in the following questions: When (for what value of the parameter) does a particular property become unavoidable? What do the extremal structures look like? The topics covered in this thesis are random geometric graphs, dependent percolation, extremal hypergraph theory and combinatorics in the hypercube.

Imagine a world where computational simulations can be inverted as easily as running them forwards, where data can be used to refine models automatically, and where the only expertise one needs to carry out powerful statistical analysis is a basic proficiency in scientific coding. Creating such a world is the ambitious long-term aim of probabilistic programming. The bottleneck for improving the probabilistic models, or simulators, used throughout the quantitative sciences, is often not an ability to devise better models conceptually, but a lack of expertise, time, or resources to realize such innovations. Probabilistic programming systems (PPSs) help alleviate this bottleneck by providing an expressive and accessible modeling framework, then automating the required computation to draw inferences from the model, for example finding the model parameters likely to give rise to a certain output. By decoupling model specification and inference, PPSs streamline the process of developing and drawing inferences from new models, while opening up powerful statistical methods to non-experts. Many systems further provide the flexibility to write new and exciting models which would be hard, or even impossible, to convey using conventional statistical frameworks. The central goal of this thesis is to improve and extend PPSs. In particular, we will make advancements to the underlying inference engines and increase the range of problems which can be tackled. For example, we will extend PPSs to a mixed inference-optimization framework, thereby providing automation of tasks such as model learning and engineering design. Meanwhile, we make inroads into constructing systems for automating adaptive sequential design problems, providing potential applications across the sciences. Furthermore, the contributions of the work reach far beyond probabilistic programming, as achieving our goal will require us to make advancements in a number of related fields such as particle Markov chain Monte Carlo methods, Bayesian optimization, and Monte Carlo fundamentals.

This thesis focuses on probabilistic associative learning. One of the classic effects in this field is the stimulus associability effect for which I derive a statistically optimal inference model and a corresponding approximation that addresses a number of problems with the original account of Mackintosh. My proposed account of associability - a variable learning rate depending on a relative informativeness of stimuli - also accounts of the classic blocking effect \cite{kamin1969predictability} without the need for Prediction Error [PE] computation. Given that blocking was the main impetus for placing PE at the centre of learning theories, I critically re-evaluate other evidence for PE in learning, particularly the recent neuroimaging evidence. I conclude that the brain data are not as clear cut as often presumed. The main shortcoming of the evidence implicating PE in learning is that probabilistic associative learning is mostly described as a transition from one state of belief to another, yet those beliefs are typically observed only after multiple learning episodes and in a very coarse manner. To address this problem, I develop an experimental paradigm and accompanying statistical methods that allow one to infer the beliefs at any given point in time. However, even with the rich data provided by this new paradigm, the blocking effect still cannot provide conclusive evidence for the role of PE in learning. I solve this problem by deriving a novel conceptualisation of learning as a flow in probability space. This allows me to derive two novel effects that can unambiguously distinguish learning that is driven by PE from learning not driven by PE. I call these effectsgeneralized blocking and false blocking, given their inspiration by the original paradigm of Kamin (1969). These two effects can be generalized to the entirety of probability space, rather than just the two specific points provided by the paradigms used by Mackintosh and Kamin, and therefore offer greater sensitivity to differences in learning mechanisms. In particular, I demonstrate that these effects are necessary consequences of PE-driven learning, but not learning based on the relative informativeness of stimuli. Lastly I develop an online experiment to acquire data on the new paradigm from a large number (approximately 2000) of participants recruited via social media. The results of model fitting, together with statistical tests of generalized blocking and false blocking, provide strong evidence against a PE-driven account of learning, instead favouring the relative informativeness account derived at the start of the thesis.

abstract: Pipeline infrastructure forms a vital aspect of the United States economy and standard of living. A majority of the current pipeline systems were installed in the early 1900’s and often lack a reliable database reporting the mechanical properties, and information about manufacturing and installation, thereby raising a concern for their safety and integrity. Testing for the aging pipe strength and toughness estimation without interrupting the transmission and operations thus becomes important. The state-of-the-art techniques tend to focus on the single modality deterministic estimation of pipe strength and do not account for inhomogeneity and uncertainties, many others appear to rely on destructive means. These gaps provide an impetus for novel methods to better characterize the pipe material properties. The focus of this study is the design of a Bayesian Network information fusion model for the prediction of accurate probabilistic pipe strength and consequently the maximum allowable operating pressure. A multimodal diagnosis is performed by assessing the mechanical property variation within the pipe in terms of material property measurements, such as microstructure, composition, hardness and other mechanical properties through experimental analysis, which are then integrated with the Bayesian network model that uses a Markov chain Monte Carlo (MCMC) algorithm. Prototype testing is carried out for model verification, validation and demonstration and data training of the model is employed to obtain a more accurate measure of the probabilistic pipe strength. With a view of providing a holistic measure of material performance in service, the fatigue properties of the pipe steel are investigated. The variation in the fatigue crack growth rate (da/dN) along the direction of the pipe wall thickness is studied in relation to the microstructure and the material constants for the crack growth have been reported. A combination of imaging and composition analysis is incorporated to study the fracture surface of the fatigue specimen. Finally, some well-known statistical inference models are employed for prediction of manufacturing process parameters for steel pipelines. The adaptability of the small datasets for the accuracy of the prediction outcomes is discussed and the models are compared for their performance. / Dissertation/Thesis / Doctoral Dissertation Materials Science and Engineering 2018

Dois modelos principais de planejamento em inteligência artificial são os usados, respectivamente, em planejamento probabilístico (MDPs e suas generalizações) e em planejamento não-determinístico (baseado em model checking). Nessa dissertação será: (1) exibido que planejamento probabilístico e não-determinístico são extremos de um rico contínuo de problemas capaz de lidar simultaneamente com risco e incerteza (Knightiana); (2) obtido um modelo para unificar esses dois tipos de problemas usando MDPs imprecisos; (3) derivado uma versão simplificada do princípio ótimo de Bellman para esse novo modelo; (4) exibido como adaptar e analisar algoritmos do estado-da-arte, como (L)RTDP e LDFS, nesse modelo unificado. Também será discutido exemplos e relações entre modelos já propostos para planejamento sob incerteza e o modelo proposto. / Two noteworthy models of planning in AI are probabilistic planning (based on MDPs and its generalizations) and nondeterministic planning (mainly based on model checking). In this dissertation we: (1) show that probabilistic and nondeterministic planning are extremes of a rich continuum of problems that deal simultaneously with risk and (Knightian) uncertainty; (2) obtain a unifying model for these problems using imprecise MDPs; (3) derive a simplified Bellman\'s principle of optimality for our model; and (4) show how to adapt and analyze state-of-art algorithms such as (L)RTDP and LDFS in this unifying setup. We discuss examples and connections to various proposals for planning under (general) uncertainty.