An Online Expectation-Maximization Algorithm for Changepoint Models

Changepoint models are widely used to model the heterogeneity of sequential data. We present a novel sequential Monte Carlo (SMC) online Expectation-Maximization (EM) algorithm for estimating the static parameters of such models. The SMC online EM algorithm has a cost per time which is linear in the number of particles and could be particularly important when the data is representable as a long sequence of observations, since it drastically reduces the computational requirements for implementation. We present an asymptotic analysis for the stability of the SMC estimates used in the online EM algorithm and demonstrate the performance of this scheme using both simulated and real data originating from DNA analysis.

An Online Expectation-Maximization Algorithm for Changepoint Models

Changepoint models are widely used to model the heterogeneity of sequential data. We present a novel sequential Monte Carlo (SMC) online Expectation-Maximization (EM) algorithm for estimating the static parameters of such models. The SMC online EM algorithm has a cost per time which is linear in the number of particles and could be particularly important when the data is representable as a long sequence of observations, since it drastically reduces the computational requirements for implementation. We present an asymptotic analysis for the stability of the SMC estimates used in the online EM algorithm and demonstrate the performance of this scheme using both simulated and real data originating from DNA analysis.

Beyond 2D-grids: A dependence maximization view on image browsing

Ideally, one would like to perform image search using an intuitive and friendly approach. Many existing image search engines, however, present users with sets of images arranged in some default order on the screen, typically the relevance to a query, only. While this certainly has its advantages, arguably, a more flexible and intuitive way would be to sort images into arbitrary structures such as grids, hierarchies, or spheres so that images that are visually or semantically alike are placed together. This paper focuses on designing such a navigation system for image browsers. This is a challenging task because arbitrary layout structure makes it difficult - if not impossible - to compute cross-similarities between images and structure coordinates, the main ingredient of traditional layouting approaches. For this reason, we resort to a recently developed machine learning technique: kernelized sorting. It is a general technique for matching pairs of objects from different domains without requiring cross-domain similarity measures and hence elegantly allows sorting images into arbitrary structures. Moreover, we extend it so that some images can be preselected for instance forming the tip of the hierarchy allowing to subsequently navigate through the search results in the lower levels in an intuitive way. Copyright 2010 ACM.

Scaling the Indian Buffet Process via Submodular Maximization

Inference for latent feature models is inherently difficult as the inference space grows exponentially with the size of the input data and number of latent features. In this work, we use Kurihara & Welling (2008)'s maximization-expectation framework to perform approximate MAP inference for linear-Gaussian latent feature models with an Indian Buffet Process (IBP) prior. This formulation yields a submodular function of the features that corresponds to a lower bound on the model evidence. By adding a constant to this function, we obtain a nonnegative submodular function that can be maximized via a greedy algorithm that obtains at least a one-third approximation to the optimal solution. Our inference method scales linearly with the size of the input data, and we show the efficacy of our method on the largest datasets currently analyzed using an IBP model.

Weighted least squares with expectation-maximization algorithm for burst detection in U.K. water distribution systems

Flow measurement data at the district meter area (DMA) level has the potential for burst detection in the water distribution systems. This work investigates using a polynomial function fitted to the historic flow measurements based on a weighted least-squares method for automatic burst detection in the U.K. water distribution networks. This approach, when used in conjunction with an expectationmaximization (EM) algorithm, can automatically select useful data from the historic flow measurements, which may contain normal and abnormal operating conditions in the distribution network, e.g., water burst. Thus, the model can estimate the normal water flow (nonburst condition), and hence the burst size on the water distribution system can be calculated from the difference between the measured flow and the estimated flow. The distinguishing feature of this method is that the burst detection is fully unsupervised, and the burst events that have occurred in the historic data do not affect the procedure and bias the burst detection algorithm. Experimental validation of the method has been carried out using a series of flushing events that simulate burst conditions to confirm that the simulated burst sizes are capable of being estimated correctly. This method was also applied to eight DMAs with known real burst events, and the results of burst detections are shown to relate to the water company's records of pipeline reparation work. © 2014 American Society of Civil Engineers.

Forward Smoothing Using Sequential Monte Carlo

Sequential Monte Carlo (SMC) methods are a widely used set of computational tools for inference in non-linear non-Gaussian state-space models. We propose a new SMC algorithm to compute the expectation of additive functionals recursively. Essentially, it is an on-line or "forward only" implementation of a forward filtering backward smoothing SMC algorithm proposed by Doucet, Godsill and Andrieu (2000). Compared to the standard \emph{path space} SMC estimator whose asymptotic variance increases quadratically with time even under favorable mixing assumptions, the non asymptotic variance of the proposed SMC estimator only increases linearly with time. We show how this allows us to perform recursive parameter estimation using an SMC implementation of an on-line version of the Expectation-Maximization algorithm which does not suffer from the particle path degeneracy problem.

Distributed maximum likelihood for self-localization in sensor networks

We show that the sensor localization problem can be cast as a static parameter estimation problem for Hidden Markov Models and we develop fully decentralized versions of the Recursive Maximum Likelihood and the Expectation-Maximization algorithms to localize the network. For linear Gaussian models, our algorithms can be implemented exactly using a distributed version of the Kalman filter and a message passing algorithm to propagate the derivatives of the likelihood. In the non-linear case, a solution based on local linearization in the spirit of the Extended Kalman Filter is proposed. In numerical examples we show that the developed algorithms are able to learn the localization parameters well.

Sequential decision making in general state space models

Many problems in control and signal processing can be formulated as sequential decision problems for general state space models. However, except for some simple models one cannot obtain analytical solutions and has to resort to approximation. In this thesis, we have investigated problems where Sequential Monte Carlo (SMC) methods can be combined with a gradient based search to provide solutions to online optimisation problems. We summarise the main contributions of the thesis as follows. Chapter 4 focuses on solving the sensor scheduling problem when cast as a controlled Hidden Markov Model. We consider the case in which the state, observation and action spaces are continuous. This general case is important as it is the natural framework for many applications. In sensor scheduling, our aim is to minimise the variance of the estimation error of the hidden state with respect to the action sequence. We present a novel SMC method that uses a stochastic gradient algorithm to find optimal actions. This is in contrast to existing works in the literature that only solve approximations to the original problem. In Chapter 5 we presented how an SMC can be used to solve a risk sensitive control problem. We adopt the use of the Feynman-Kac representation of a controlled Markov chain flow and exploit the properties of the logarithmic Lyapunov exponent, which lead to a policy gradient solution for the parameterised problem. The resulting SMC algorithm follows a similar structure with the Recursive Maximum Likelihood(RML) algorithm for online parameter estimation. In Chapters 6, 7 and 8, dynamic Graphical models were combined with with state space models for the purpose of online decentralised inference. We have concentrated more on the distributed parameter estimation problem using two Maximum Likelihood techniques, namely Recursive Maximum Likelihood (RML) and Expectation Maximization (EM). The resulting algorithms can be interpreted as an extension of the Belief Propagation (BP) algorithm to compute likelihood gradients. In order to design an SMC algorithm, in Chapter 8 uses a nonparametric approximations for Belief Propagation. The algorithms were successfully applied to solve the sensor localisation problem for sensor networks of small and medium size.

Multiscale object features from clustered complex wavelet coefficients

This paper introduces a method by which intuitive feature entities can be created from ILP (InterLevel Product) coefficients. The ILP transform is a pyramid of decimated complex-valued coefficients at multiple scales, derived from dual-tree complex wavelets, whose phases indicate the presence of different feature types (edges and ridges). We use an Expectation-Maximization algorithm to cluster large ILP coefficients that are spatially adjacent and similar in phase. We then demonstrate the relationship that these clusters possess with respect to observable image content, and conclude with a look at potential applications of these clusters, such as rotation- and scale-invariant object recognition. © 2005 IEEE.

Optimum Magnetic Circuit Configurations for Permanent Magnet Aerospace Generators

In the design of high-speed low-power electrical generators for unmanned aircraft and spacecraft, maximization of specific output (power/weight) is of prime importance. Several magnetic circuit configurations (radial-field, axial-field, flux-squeezing, homopolar) have been proposed, and in this paper the relative merits of these configurations are subjected to a quantitative investigation over the speed range 10 000–100000 rev/min and power range 250 W-10 kW. The advantages of incorporating new high energy-density magnetic materials are described. Part I deals with establishing an equivalent circuit for permanent-magnet generators. For each configuration the equivalent circuit parameters are related to the physical dimensions of the generator components and an optimization procedure produces a minimum volume design at discrete output powers and operating speeds. The technique is illustrated by a quantitative comparison of the specific outputs of conventional radial-field generators with samarium cobalt and alnico magnets. In Part II the specific outputs of conventional, flux-squeezing, and claw-rotor magnetic circuit configurations are compared. The flux-squeezing configuration is shown to produce the highest specific output for small sizes whereas the conventional configuration is best at large sizes. For all sizes the claw-rotor configuration is significantly inferior. In Part III the power densities available from axial-field and flux-switching magnetic circuit configurations are maximized, over the power range 0.25-10 kW and speed range 10 000–100000 rpm, and compared to the results of Parts I & II. For the axial-field configuration the power density is always less than that of the conventional and flux-squeezing radial-field configurations. For the flux-switching generator, which is able to withstand relatively high mechanical forces in the rotor, the power density is again inferior to the radial-field types, but the difference is less apparent for small (low power, high speed) generator sizes. From the combined results it can be concluded that the flux-squeezing and conventional radial-field magnetic circuit configurations yield designs with minimum volume over the power and speed ranges considered. © 1985, IEEE. All rights reserved.

Re-conceptualising value in the engineering design process: The value cycle map

Introducing a "Cheaper, Faster, Better" product in today's highly competitive market is a challenging target. Therefore, for organizations to improve their performance in this area, they need to adopt methods such as process modelling, risk mitigation and lean principles. Recently, several industries and researchers focused efforts on transferring the value orientation concept to other phases of the Product Life Cycle (PLC) such as Product Development (PD), after its evident success in manufacturing. In PD, value maximization, which is the main objective of lean theory, has been of particular interest as an improvement concept that can enhance process flow logistics and support decision-making. This paper presents an ongoing study of the current understanding of value thinking in PD (VPD) with a focus on value dimensions and implementation benefits. The purpose of this study is to consider the current state of knowledge regarding value thinking in PD, and to propose a definition of value and a framework for analyzing value delivery. The framework-named the Value Cycle Map (VCM)- intends to facilitate understanding of value and its delivery mechanism in the context of the PLC. We suggest the VCM could be used as a foundation for future research in value modelling and measurement in PD.

State-space inference and learning with Gaussian processes

State-space inference and learning with Gaussian processes (GPs) is an unsolved problem. We propose a new, general methodology for inference and learning in nonlinear state-space models that are described probabilistically by non-parametric GP models. We apply the expectation maximization algorithm to iterate between inference in the latent state-space and learning the parameters of the underlying GP dynamics model. Copyright 2010 by the authors.