Massive training datasets, ranging in size from tens of gigabytes to several terabytes, arise in diverse machine learning applications in areas such as text mining of web corpora, multimedia analysis of image and video data, retail modeling of customer transaction data, bioinformatic analysis of genomic and microarray data, medical analysis of clinical diagnostic data such as functional magnetic resonance imaging (fMRI) images, and environmental modeling using sensor and streaming data. Provost and Kolluri (1999) in their overview of machine learning with massive datasets, emphasize the need for developing parallel algorithms and implementations for these applications.

In this chapter, we describe the Transform Regression (TReg) algorithm (Pednault, 2006), which is a general-purpose, non-parametric methodology suitable for a wide variety of regression applications. TReg was originally created for the data mining component of the IBM InfoSphere Warehouse product, guided by a challenging set of requirements:

1. The modeling time should be comparable to linear regression.

2. The resulting models should be compact and efficient to apply.

3. The model quality should be reliable without any further tuning.

4. The model training and scoring should be parallelized for large datasets stored as partitioned tables in IBM's DB2 database systems.

Requirements 1 and 2 were deemed necessary for a successful commercial algorithm, although this ruled out certain ensemble-based methods that produce highquality models but have high computation and storage requirements. Requirement 3 ensured that the chosen algorithm did not unduly compromise the concomitant model quality in view of requirements 1 and 2.

Support Vector Machines (SVMs) are some of the most widely used classification and regression algorithms for data analysis, pattern recognition, or cognitive tasks. Yet learning problems that can be solved by SVMs are limited in size because of high computational cost and excessive storage requirements. Many variations of the original SVM algorithm were introduced that scale better to large problems. They change the SVM framework quite drastically, such as apply optimizations other than the maximum margin, or introduce different error metrics for the cost function. Such algorithms may work for some applications, but they do not have the robustness and universality that make SVMs so popular.

The approach taken here is to maintain the SVM algorithm in its original form and scale it to large problems through parallelization. Computer performance cannot be improved anymore at the pace of the last few decades by increasing the clock frequencies. Today, significant accelerations are achieved mostly through parallel architectures, and multicore processors are commonplace nowadays. Mapping the SVM algorithm to multicore processors with shared-memory architectures is straightforward, yet this approach does not scale to a large number of processors. Here we investigate parallelization concepts that scale to hundreds and thousands of cores where, for example, cache coherence can no longer be maintained.

A number of SVM implementations on clusters or graphics processors (GPUs) have been proposed recently. A parallel optimization algorithm based on gradient projections has been demonstrated (see Zanghirati, and Zanni, 2003; Zanni, Serafini, and Zanghirati, 2006) that uses a spectral gradient method for fast convergence while maintaining the Karush-Kuhn-Tucker (KKT) constraints.

Machine learning and data-mining technologies have already achieved significant success in many knowledge engineering areas including web search, computational advertising, recommender systems, etc. A major challenge in machine learning is the data sparsity problem. For example, in the domain of online recommender systems, we attempt to recommend information items (e.g., movies, TV, books, news, images, web pages, etc.) that are likely to be of interest to the user. However, the item space is usually very large and the amount of user preference values is small. When the user data are too sparse, it is difficult to obtain a reliable and useful model for recommendation. Whereas large online sites like Amazon and Google can easily access huge volumes of user data, the enormous number of smaller online business sites, which collectively constitute the long tail of the web, are much more likely to have very sparse user data and have difficulty in generating accurate recommendations. One potential solution to the data sparsity problem is to transfer knowledge from other information sources (e.g., Mehta and Hofmann, 2007; Li, Yang, and Xue, 2009). Such techniques for knowledge transfer are called transfer learning (see, e.g., Pan and Yang, 2010). An additional issue is that, in reality, many small websites often attract similar users and/or provide similar items, if not the identical ones, which implies that data about such users/items could potentially be distributed across different systems. For example, Delicious and Digg are both popular online social bookmarking tools.

Introduction

Many real-world problems can be described by models that extend the classical linear Gaussian dynamical system with (unobserved) discrete regime indicators. In such extended models the discrete indicators dictate what transition and observation model the process follows at a particular time. The problems of tracking and estimation in models with manoeuvring targets [1], multiple targets [25], non-Gaussian disturbances [15], unknown model parameters [9], failing sensors [20] and different trends [8] are all examples of problems that have been formulated in a conditionally Gaussian state space model framework. Since the extended model is so general it has been invented and re-invented many times in multiple fields, and is known by many different names, such as switching linear dynamical system, conditionally Gaussian state space model, switching Kalman filter model and hybrid model.

Although the extended model has a lot of expressive power, it is notorious for the fact that exact estimation of posteriors is intractable. In general, exact filtered, smoothed or predicted posteriors have a complexity exponential in the number of observations. Even when only marginals on the indicator variables are required the problem remains NP-hard [19].

In this chapter we introduce a deterministic approximation scheme that is particularly suited to find smoothed one and two time slice posteriors. It can be seen as a symmetric backward pass and iteration scheme for previously proposed assumed density filtering approaches [9].

The chapter is organised as follows. In Section 7.2 we present the general model; variants where only the transition or only the observation model switch, or where states or observations are multi-or univariate can be treated as special cases.

Introduction

Markov processes are probabilistic models for describing data with a sequential structure. Probably the most common example is a dynamical system, of which the state evolves over time. For modelling purposes it is often convenient to assume that the system states are not directly observed: each observation is a possibly incomplete, non-linear and noisy measurement (or transformation) of the underlying hidden state. In general, observations of the system occur only at discrete times, while the underlying system is inherently continuous in time. Continuous-time Markov processes arise in a variety of scientific areas such as physics, environmental modelling, finance, engineering and systems biology.

The continuous-time evolution of the system imposes strong constraints on the model dynamics. For example, the individual trajectories of a diffusion process are rough, but the mean trajectory is a smooth function of time. Unfortunately, this information is often under- or unexploited when devising practical systems. The main reason is that inferring the state trajectories and the model parameters is a difficult problem as trajectories are infinite-dimensional objects. Hence, a practical approach usually requires some sort of approximation. For example, Markov chain Monte Carlo (MCMC) methods usually discretise time [41, 16, 34, 2, 20], while particle filters approximate continuous densities by a finite number of point masses [13, 14, 15]. More recently, approaches using perfect simulation have been proposed [7, 8, 18]. The main advantage of these MCMC techniques is that they do not require approximations of the transition density using time discretisations.

Introduction

In nature there are many examples of group behaviour arising from the action of individuals without any apparent central coordinator, such as the highly coordinated movements of flocks of birds or schools of fish. These are among the most fascinating phenomena to be found in nature; where the groups seem to turn and manoeuvre as a single unit, changing direction almost instantaneously. Similarly, in man-made activities, there are many cases of group-like behaviour, such as a group of aircraft flying in formation.

There are two principal reasons why it is very helpful to model the behaviour of groups explicitly, as opposed to treating all objects independently as in most multiple target tracking approaches. The first is that the joint tracking of (a priori) dependent objects within a group will lead to greater detection and tracking ability in hostile environments with high noise and low detection probabilities. For example, in the radar target tracking application, if several targets are in a group formation, then some information on the positions and speeds of those targets with missing measurements (due to poor detection probability) can be inferred given those targets that are detected. Similarly, if a newly detected target appears close to an existing group, the target can be initialised using the group velocity.

Introduction

Many time series are characterised by abrupt changes in structure, such as sudden jumps in level or volatility. We consider changepoints to be those time points which divide a dataset into distinct homogeneous segments. In practice the number of changepoints will not be known. The ability to detect changepoints is important for both methodological and practical reasons including: the validation of an untested scientific hypothesis [27]; monitoring and assessment of safety critical processes [14]; and the validation of modelling assumptions [21].

The development of inference methods for changepoint problems is by no means a recent phenomenon, with early works including [39], [45] and [28]. Increasingly the ability to detect changepoints quickly and accurately is of interest to a wide range of disciplines. Recent examples of application areas include numerous bioinformatic applications [37, 15], the detection of malware within software [51], network traffic analysis [35], finance [46], climatology [32] and oceanography [34].

In this chapter we describe and compare a number of different approaches for estimating changepoints. For a more general overview of changepoint methods, we refer interested readers to [8] and [11]. The structure of this chapter is as follows. First we introduce the model we focus on. We then describe methods for detecting a single changepoint and methods for detecting multiple changepoint, which will cover both frequentist and Bayesian approaches.

Introduction

A common way to handle non-linearity in complex time series data is to try splitting the data up into a number of simpler segments. Sometimes we have domain knowledge to support this piecewise modelling approach, for example in condition monitoring applications. In such problems, the evolution of some observed data is governed by a number of hidden factors that switch between different modes of operation. In real-world data, e.g. from medicine, robotic control or finance, we might be interested in factors which represent pathologies, mechanical failure modes, or economic conditions respectively. Given just the monitoring data, we are interested in recovering the state of the factors that gave rise to it.

A good model for this type of problem is the switching linear dynamical system (SLDS), which has been discussed in previous chapters. A latent ‘switch’ variable in this type of model selects between different linear-Gaussian state spaces. In this chapter we consider a generalisation, the factorial switching linear dynamical system (FSLDS), where instead of a single switch setting there are multiple discrete factors that collectively determine the dynamics. In practice there may be a very large number of possible factors, and we may only have explicit knowledge of commonly occurring ones.

We illustrate how the FSLDS can be used in the physiological monitoring of premature babies in intensive care. This application is a useful introduction because it has complex observed data, a diverse range of factors affecting the observations, and the challenge of many ‘unknown’ factors.

Probabilistic time series modelling

Time series are studied in a variety of disciplines and appear in many modern applications such as financial time series prediction, video-tracking, music analysis, control and genetic sequence analysis. This widespread interest at times obscures the commonalities in the developed models and techniques. A central aim of this book is to attempt to make modern time series techniques, specifically those based on probabilistic modelling, accessible to a broad range of researchers.

In order to achieve this goal, leading researchers that span the more traditional disciplines of statistics, control theory, engineering and signal processing, and the more recent areas of machine learning and pattern recognition, have been brought together to discuss advancements and developments in their respective fields. In addition, the book makes extensive use of the graphical models framework. This framework facilitates the representation of many classical models and provides insight into the computational complexity of their implementation. Furthermore, it enables to easily envisage new models tailored for a particular environment. For example, the book discusses novel state space models and their application in signal processing including condition monitoring and tracking. The book also describes modern developments in the machine learning community applied to more traditional areas of control theory.

The effective application of probabilistic models in the real world is gaining pace, largely through increased computational power which brings more general models into consideration through carefully developed implementations.

Introduction

Sensor networks have recently generated a great deal of research interest within the computer and physical sciences, and their use for the scientific monitoring of remote and hostile environments is increasingly commonplace. While early sensor networks were a simple evolution of existing automated data loggers, that collected data for later offline scientific analysis, more recent sensor networks typically make current data available through the Internet, and thus, are increasingly being used for the real-time monitoring of environmental events such as floods or storm events (see [10] for a review of such environmental sensor networks).

Using real-time sensor data in this manner presents many novel challenges. However, more significantly for us, many of the information processing tasks that would previously have been performed offline by the owner or single user of an environmental sensor network (such as detecting faulty sensors, fusing noisy measurements from several sensors, and deciding how frequently readings should be taken), must now be performed in real-time on the mobile computers and PDAs carried by the multiple different users of the system (who may have different goals and may be using sensor readings for very different tasks). Importantly, it may also be necessary to use the trends and correlations observed in previous data to predict the value of environmental parameters into the future, or to predict the reading of a sensor that is temporarily unavailable (e.g. due to network outages).

Introduction

Optimising a sequence of actions to attain some future goal is the general topic of control theory [26, 9]. It views an agent as an automaton that seeks to maximise expected reward (or minimise cost) over some future time period. Two typical examples that illustrate this are motor control and foraging for food.

As an example of a motor control task, consider a human throwing a spear to kill an animal. Throwing a spear requires the execution of a motor program that is such that at the moment that the hand releases the spear it has the correct speed and direction to hit the desired target. A motor program is a sequence of actions, and this sequence can be assigned a cost that consists generally of two terms: a path cost that specifies the energy consumption to contract the muscles to execute the motor program, and an end cost that specifies whether the spear will kill the animal, just hurt it, or miss it altogether. The optimal control solution is a sequence of motor commands that results in killing the animal by throwing the spear with minimal physical effort. If x denotes the state space (the positions and velocities of the muscles), the optimal control solution is a function u(x, t) that depends both on the actual state of the system at each time t and also explicitly on time.