A well-known paradigm for optimisation is the evolutionary algorithm (EA). An EA maintains a population of possible solutions to a problem which converges on a global optimum using biologically-inspired selection and reproduction operators. These algorithms have been shown to perform well on a variety of hard optimisation and search problems. A recent development in evolutionary computation is the Estimation of Distribution Algorithm (EDA) which replaces the traditional genetic reproduction operators (crossover and mutation) with the construction and sampling of a probabilistic model. While this can often represent a significant computational expense, the benefit is that the model contains explicit information about the fitness function. This thesis expands on recent work using a Markov network to model fitness in an EDA, resulting in what we call the Markov Fitness Model (MFM). The work has explored the theoretical foundations of the MFM approach which are grounded in Walsh analysis of fitness functions. This has allowed us to demonstrate a clear relationship between the fitness model and the underlying dynamics of the problem. A key achievement is that we have been able to show how the model can be used to predict fitness and have devised a measure of fitness modelling capability called the fitness prediction correlation (FPC). We have performed a series of experiments which use the FPC to investigate the effect of population size and selection operator on the fitness modelling capability. The results and analysis of these experiments are an important addition to other work on diversity and fitness distribution within populations. With this improved understanding of fitness modelling we have been able to extend the framework Distribution Estimation Using Markov networks (DEUM) to use a multivariate probabilistic model. We have proposed and demonstrated the performance of a number of algorithms based on this framework which lever the MFM for optimisation, which can now be added to the EA toolbox. As part of this we have investigated existing techniques for learning the structure of the MFM; a further contribution which results from this is the introduction of precision and recall as measures of structure quality. We have also proposed a number of possible directions that future work could take.

Markov trees generalize naturally to bounded tree-width Markov networks, onwhich exact computations can still be done efficiently. However, learning themaximum likelihood Markov network with tree-width greater than 1 is NP-hard, sowe discuss a few algorithms for approximating the optimal Markov network. Wepresent a set of methods for training a density estimator. Each method isspecified by three arguments: tree-width, model scoring metric (maximumlikelihood or minimum description length), and model representation (using onejoint distribution or several class-conditional distributions). On thesemethods, we give empirical results on density estimation and classificationtasks and explore the implications of these arguments.

Faces, along with the personal identities behind them, are effective elements in organizing a collection of consumer photos, as they represent who was involved. However, the accurate discrimination and subsequent recognition of face appearances is still very challenging. This can be attributed to the fact that faces are usually neither perfectly lit nor captured, particularly in the uncontrolled environments of consumer photos. Unlike, for instance, passport photos that only show faces stripped of their surroundings, Consumer Photo Collections contain a vast amount of meaningful context. For example, consecutively shot photos often correlate in time, location or scene. Further information can also be provided by the people appearing in photos, such as their demographics (ages and gender are often easier to surmise than identities), clothing, or the social relationships among co-occurring people. Motivated by this ubiquitous context, we propose and research people recognition approaches that consider contextual information within photos, as well as across entire photo collections. Our aim of leveraging additional contextual information (as opposed to only considering faces) is to improve recognition performance. However, instead of requiring users to explicitly label specific pieces of contextual information, we wish to implicitly learn and draw from the seemingly coherent content that exists inherently across an entire photo collection. Moreover, unlike conventional approaches that usually predict the identity of only one person’s appearance at a time, we lay out a semi-supervised approach to jointly recognize multiple peoples’ appearances across an entire photo collection simultaneously. As such, our aim is to find the overall best recognition solution. To make context-based joint recognition of people feasible, we research a sparse but efficient graph-based approach that builds on Markov Networks and utilizes distance-based face description methods. We show how to exploit the following specific contextual cues: time, social semantics, body appearances (clothing), gender, scene and ambiguous captions. We also show how to leverage crowd-sourced gamified feedback to iteratively improve recognition performance. Experiments on several datasets demonstrate and validate the effectiveness of our semisupervised graph-based recognition approach compared to conventional approaches.

This thesis consists of two papers studying structure learning in probabilistic graphical models for both undirected graphs anddirected acyclic graphs (DAGs). Paper A, presents a novel family of graph theoretical algorithms, called the junction tree expanders, that incrementally construct junction trees for decomposable graphs. Due to its Markovian property, the junction tree expanders are shown to be suitable for proposal kernels in a sequential Monte Carlo (SMC) sampling scheme for approximating a graph posterior distribution. A simulation study is performed for the case of Gaussian decomposable graphical models showing efficiency of the suggested unified approach for both structural and parametric Bayesian inference. Paper B, develops a novel prior distribution over DAGs with the ability to express prior knowledge in terms of graph layerings. In conjunction with the prior, a search and score algorithm based on the layering property of DAGs, is developed for performing structure learning in Bayesian networks. A simulation study shows that the search and score algorithm along with the prior has superior performance for learning graph with a clearly layered structure compared with other priors. / <p>QC 20160111</p>

In order for assistive robots to collaborate effectively with humans for completing everyday tasks, they must be endowed with the ability to effectively perceive scenes and more importantly, recognize human intentions. As a result, we present in this dissertation a novel scene-dependent human-robot collaborative system capable of recognizing and learning human intentions based on scene objects, the actions that can be performed on them, and human interaction history. The aim of this system is to reduce the amount of human interactions necessary for communicating tasks to a robot. Accordingly, the system is partitioned into scene understanding and intention recognition modules. For scene understanding, the system is responsible for segmenting objects from captured RGB-D data, determining their positions and orientations in space, and acquiring their category labels. This information is fed into our intention recognition component where the most likely object and action pair that the user desires is determined. Our contributions to the state of the art are manifold. We propose an intention recognition framework that is appropriate for persons with limited physical capabilities, whereby we do not observe human physical actions for inferring intentions as is commonplace, but rather we only observe the scene. At the core of this framework is our novel probabilistic graphical model formulation entitled Object-Action Intention Networks. These networks are undirected graphical models where the nodes are comprised of object, action, and object feature variables, and the links between them indicate some form of direct probabilistic interaction. This setup, in tandem with a recursive Bayesian learning paradigm, enables our system to adapt to a user's preferences. We also propose an algorithm for the rapid estimation of position and orientation values of scene objects from single-view 3D point cloud data using a multi-scale superquadric fitting approach. Additionally, we leverage recent advances in computer vision for an RGB-D object categorization procedure that balances discrimination and generalization as well as a depth segmentation procedure that acquires candidate objects from tabletops. We demonstrate the feasibility of the collaborative system presented herein by conducting evaluations on multiple scenes comprised of objects from 11 categories, along with 7 possible actions, and 36 possible intentions. We achieve approximately 81% reduction in interactions overall after learning despite changes to scene structure.

Graphical techniques for modeling the dependencies of randomvariables have been explored in a variety of different areas includingstatistics, statistical physics, artificial intelligence, speech recognition, image processing, and genetics.Formalisms for manipulating these models have been developedrelatively independently in these research communities. In this paper weexplore hidden Markov models (HMMs) and related structures within the general framework of probabilistic independencenetworks (PINs). The paper contains a self-contained review of the basic principles of PINs.It is shown that the well-known forward-backward (F-B) and Viterbialgorithms for HMMs are special cases of more general inference algorithms forarbitrary PINs. Furthermore, the existence of inference and estimationalgorithms for more general graphical models provides a set of analysistools for HMM practitioners who wish to explore a richer class of HMMstructures.Examples of relatively complex models to handle sensorfusion and coarticulationin speech recognitionare introduced and treated within the graphical model framework toillustrate the advantages of the general approach.