Abstract This position paper argues for the use of structured generative models (SGMs) for the understanding of static scenes. This requires the reconstruction of a 3D scene from an input image (or a set of multi-view images), whereby the contents of the image(s) are causally explained in terms of models of instantiated objects, each with their own type, shape, appearance and pose, along with global variables like scene lighting and camera parameters. This approach also requires scene models which account for the co-occurrences and inter-relationships of objects in a scene. The SGM approach has the merits that it is compositional and generative, which lead to interpretability and editability. To pursue the SGM agenda, we need models for objects and scenes, and approaches to carry out inference. We first review models for objects, which include “things” (object categories that have a well defined shape), and “stuff” (categories which have amorphous spatial extent). We then move on to review scene models which describe the inter-relationships of objects. Perhaps the most challenging problem for SGMs is inference of the objects, lighting and camera parameters, and scene inter-relationships from input consisting of a single or multiple images. We conclude with a discussion of issues that need addressing to advance the SGM agenda.

Humans (and many vertebrates) face the problem of fusing together multiple fixations of a scene in order to obtain a representation of the whole, where each fixation uses a high-resolution fovea and decreasing resolution in the periphery. In this letter, we explicitly represent the retinal transformation of a fixation as a linear downsampling of a high-resolution latent image of the scene, exploiting the known geometry. This linear transformation allows us to carry out exact inference for the latent variables in factor analysis (FA) and mixtures of FA models of the scene. This also allows us to formulate and solve the choice of where to look next as a Bayesian experimental design problem using the expected information gain criterion. Experiments on the Frey faces and MNIST data sets demonstrate the effectiveness of our models.

Behavioural experiments often happen in specialised arenas, but this may confound the analysis. To address this issue, we provide tools to study mice in the home-cage environment, equipping biologists with the possibility to capture the temporal aspect of the individual's behaviour and model the interaction and interdependence between cage-mates with minimal human intervention. Our main contribution is the novel Global Behaviour Model (GBM) which summarises the joint behaviour of groups of mice across cages, using a permutation matrix to match the mouse identities in each cage to the model. In support of the above, we also (a) developed the Activity Labelling Module (ALM) to automatically classify mouse behaviour from video, and (b) released two datasets, ABODe for training behaviour classifiers and IMADGE for modelling behaviour. Supplementary Information: The online version contains supplementary material available at 10.1007/s11263-024-02118-3.

Abstract Our objective is to locate and provide a unique identifier for each mouse in a cluttered home-cage environment through time, as a precursor to automated behaviour recognition for biological research. This is a very challenging problem due to (i) the lack of distinguishing visual features for each mouse, and (ii) the close confines of the scene with constant occlusion, making standard visual tracking approaches unusable. However, a coarse estimate of each mouse’s location is available from a unique RFID implant, so there is the potential to optimally combine information from (weak) tracking with coarse information on identity. To achieve our objective, we make the following key contributions: (a) the formulation of theobject identificationproblem as an assignment problem (solved using Integer Linear Programming), (b) a novel probabilistic model of the affinity between tracklets and RFID data, and (c) a curated dataset with per-frame BB and regularly spaced ground-truth annotations for evaluating the models. The latter is a crucial part of the model, as it provides a principled probabilistic treatment of object detections given coarse localisation. Our approach achieves 77% accuracy on this animal identification problem, and is able to reject spurious detections when the animals are hidden.

Capsule networks (see Hinton et al., 2018) aim to encode knowledge of and reason about the relationship between an object and its parts. In this letter, we specify a generative model for such data and derive a variational algorithm for inferring the transformation of each model object in a scene and the assignments of observed parts to the objects. We derive a learning algorithm for the object models, based on variational expectation maximization (Jordan et al., 1999). We also study an alternative inference algorithm based on the RANSAC method of Fischler and Bolles (1981). We apply these inference methods to data generated from multiple geometric objects like squares and triangles ("constellations") and data from a parts-based model of faces. Recent work by Kosiorek et al. (2019) has used amortized inference via stacked capsule autoencoders to tackle this problem; our results show that we significantly outperform them where we can make comparisons (on the constellations data).

Data wrangling tasks such as obtaining and linking data from various sources, transforming data formats, and correcting erroneous records, can constitute up to 80% of typical data engineering work. Despite the rise of machine learning and artificial intelligence, data wrangling remains a tedious and manual task. We introduceAI assistants, a class of semi-automatic interactive tools to streamline data wrangling. An AI assistant guides the analyst through a specific data wrangling task by recommending a suitable data transformation that respects the constraints obtained through interaction with the analyst. We formally define the structure of AI assistants and describe how existing tools that treat data cleaning as an optimization problem fit the definition. We implement AI assistants for four common data wrangling tasks and make AI assistants easily accessible to data analysts in an open-source notebook environment for data science, by leveraging the common structure they follow. We evaluate our AI assistants both quantitatively and qualitatively through three example scenarios. We show that the unified and interactive design makes it easy to perform tasks that would be difficult to do manually or with a fully automatic tool.

Time series datasets are often composed of a variety of sequences from the same domain, but from different entities, such as individuals, products, or organizations. We are interested in how time series models can be specialized to individual sequences (capturing the specific characteristics) while still retaining statistical power by sharing commonalities across the sequences. This paper describes the multi-task dynamical system (MTDS); a general methodology for extending multi-task learning (MTL) to time series models. Our approach endows dynamical systems with a set of hierarchical latent variables which can modulate all model parameters. To our knowledge, this is a novel development of MTL, and applies to time series both with and without control inputs. We apply the MTDS to motion-capture data of people walking in various styles using a multi-task recurrent neural network (RNN), and to patient drug-response data using a multi-task pharmacodynamic model.

Barlow (1985) hypothesized that the co-occurrence of two events A and B is "suspicious" if P(A,B)≫P(A)P(B). We first review classical measures of association for 2 × 2 contingency tables, including Yule's Y (Yule, 1912), which depends only on the odds ratio λ and is independent of the marginal probabilities of the table. We then discuss the mutual information (MI) and pointwise mutual information (PMI), which depend on the ratio P(A,B)/P(A)P(B), as measures of association. We show that once the effect of the marginals is removed, MI and PMI behave similarly to Y as functions of λ. The pointwise mutual information is used extensively in some research communities for flagging suspicious coincidences. We discuss the pros and cons of using it in this way, bearing in mind the sensitivity of the PMI to the marginals, with increased scores for sparser events.

Recent advances in deep generative models have led to impressive results in a variety of application domains. Motivated by the possibility that deep learning models might memorize part of the input data, there have been increased efforts to understand how memorization arises. In this work, we extend a recently proposed measure of memorization for supervised learning (Feldman, 2019) to the unsupervised density estimation problem and adapt it to be more computationally efficient. Next, we present a study that demonstrates how memorization can occur in probabilistic deep generative models such as variational autoencoders. This reveals that the form of memorization to which these models are susceptible differs fundamentally from mode collapse and overfitting. Furthermore, we show that the proposed memorization score measures a phenomenon that is not captured by commonly-used nearest neighbor tests. Finally, we discuss several strategies that can be used to limit memorization in practice. Our work thus provides a framework for understanding problematic memorization in probabilistic generative models.

In this note, I study how the precision of a binary classifier depends on the ratio r of positive to negative cases in the test set, as well as the classifier's true and false-positive rates. This relationship allows prediction of how the precision-recall curve will change with r, which seems not to be well known. It also allows prediction of how Fβ and the precision gain and recall gain measures of Flach and Kull (2015) vary with r.

We focus on the problem of unsupervised cell outlier detection and repair inmixed-type tabular data. Traditional methods are concerned only with detecting which rows in the dataset areoutliers. However, identifying which cells are corrupted in aspecific row is an important problem in practice, and the very first steptowards repairing them. We introduce the Robust VariationalAutoencoder (RVAE), a deep generative model that learns the jointdistribution of the clean data while identifying the outlier cells, allowing their imputation (repair). RVAE explicitly learns the probability of each cell being an outlier, balancing differentlikelihood models in the row outlier score, making the method suitablefor outlier detection in mixed-type datasets.We show experimentallythat not only RVAE performs better than several state-of-the-art methods incell outlier detection and repair for tabular data, but also that is robust against theinitial hyper-parameter selection.

Abstract Type inference refers to the task of inferring the data type of a given column of data. Current approaches often fail when data contains missing data and anomalies, which are found commonly in real-world data sets. In this paper, we propose ptype, a probabilistic robust type inference method that allows us to detect such entries, and infer data types. We further show that the proposed method outperforms existing methods.

Time series models such as dynamical systems are frequently fitted to a cohort of data, ignoring variation between individual entities such as patients. In this paper we show how these models can be personalised to an individual level while retaining statistical power, via use of multi-task learning (MTL). To our knowledge this is a novel development of MTL which applies to time series both with and without control inputs. The modelling framework is demonstrated on a physiological drug response problem which results in improved predictive accuracy and uncertainty estimation over existing state-of-the-art models.

We present a method for feature interpretation that makes use of recent advances in autoregressive density estimation models to invert model representations. We train generative inversion models to express a distribution over input features conditioned on intermediate model representations. Insights into the invariances learned by supervised models can be gained by viewing samples from these inversion models. In addition, we can use these inversion models to estimate the mutual information between a model’s inputs and its intermediate representations, thus quantifying the amount of information preserved by the network at different stages. Using this method we examine the types of information preserved at different layers of convolutional neural networks, and explore the invariances induced by different architectural choices. Finally we show that the mutual information between inputs and network layers initially increases and then decreases over the course of training, supporting recent work by Shwartz-Ziv and Tishby (2017) on the information bottleneck theory of deep learning.

Abstract We introduce a generative model of part‐segmented 3D objects: the shape variational auto‐encoder (ShapeVAE). The ShapeVAE describes a joint distribution over the existence of object parts, the locations of a dense set of surface points, and over surface normals associated with these points. Our model makes use of a deep encoder‐decoder architecture that leverages the part‐decomposability of 3D objects to embed high‐dimensional shape representations and sample novel instances. Given an input collection of part‐segmented objects with dense point correspondences the ShapeVAE is capable of synthesizing novel, realistic shapes, and by performing conditional inference enables imputation of missing parts or surface normals. In addition, by generating both points and surface normals, our model allows for the use of powerful surface‐reconstruction methods for mesh synthesis. We provide a quantitative evaluation of the ShapeVAE on shape‐completion and test‐set log‐likelihood tasks and demonstrate that the model performs favourably against strong baselines. We demonstrate qualitatively that the ShapeVAE produces plausible shape samples, and that it captures a semantically meaningful shape‐embedding. In addition we show that the ShapeVAE facilitates mesh reconstruction by sampling consistent surface normals.

This paper investigates visual boundary detection, i.e. prediction of the presence of a boundary at a given image location. We develop a novel neurally-inspired deep architecture for the task. Notable aspects of our work are (i) the use of “covariance features” [Ranzato and Hinton, 2010] which depend on the \emphsquared response of a filter to the input image, and (ii) the integration of image information from multiple scales and semantic levels via multiple streams of interlinked, layered, and non-linear “deep” processing. Our results on the Berkeley Segmentation Data Set 500 (BSDS500) show comparable or better performance to the top-performing methods [Arbelaez et al., 2011, Ren and Bo, 2012, Lim et al., 2013, Dollár and Zitnick, 2013] with effective inference times. We also propose novel quantitative assessment techniques for improved method understanding and comparison. We carefully dissect the performance of our architecture, feature-types used and training methods, providing clear signals for model understanding and development.

Late onset neonatal sepsis is one of the major clinical concerns when premature babies receive intensive care. Current practice relies on slow laboratory testing of blood cultures for diagnosis. A valuable research question is whether sepsis can be reliably detected before the blood sample is taken. This paper investigates the extent to which physiological events observed in the patient's monitoring traces could be used for the early detection of neonatal sepsis. We model the distribution of these events with an autoregressive hidden Markov model (AR-HMM). Both learning and inference carefully use domain knowledge to extract the baby's true physiology from the monitoring data. Our model can produce real-time predictions about the onset of the infection and also handles missing data. We evaluate the effectiveness of the AR-HMM for sepsis detection on a dataset collected from the Neonatal Intensive Care Unit at the Royal Infirmary of Edinburgh.

The Shape Boltzmann Machine (SBM) has recently been introduced as a state-of-the-art model of foreground/background object shape. We extend the SBM to account for the foreground object's parts. Our model, the Multinomial SBM (MSBM), can capture both local and global statistics of part shapes accurately. We combine the MSBM with an appearance model to form a fully generative model of images of objects. Parts-based image segmentations are obtained simply by performing probabilistic inference in the model. We apply the model to two challenging datasets which exhibit significant shape and appearance variability, and find that it obtains results that are comparable to the state-of-the-art.

Recounts the career and contributions pf Mark Everingham.

We present a novel generative framework for learning parts-based representations of object classes. Our model, Factored Shapes and Appearances (FSA), employs a highly factored representation to reason about appearance and shape variability across datasets of images. We propose Markov Chain Monte Carlo sampling schemes for efficient inference and learning, and evaluate the model on a number of datasets. Here we consider datasets that exhibit large amounts of variability, both in the shapes of objects in the scene, and in their appearances. We show that the FSA model extracts meaningful parts from training data, and that its parameters and representation can be used to perform a range of tasks, including object parsing, segmentation and fine-grained categorisation.

Inferring latent structures from observations helps to model and possibly also understand underlying data generating processes. A rich class of latent structures is the latent trees, i.e., tree-structured distributions involving latent variables where the visible variables are leaves. These are also called hierarchical latent class (HLC) models. Zhang and Kocka proposed a search algorithm for learning such models in the spirit of Bayesian network structure learning. While such an approach can find good solutions, it can be computationally expensive. As an alternative, we investigate two greedy procedures: the BIN-G algorithm determines both the structure of the tree and the cardinality of the latent variables in a bottom-up fashion. The BIN-A algorithm first determines the tree structure using agglomerative hierarchical clustering, and then determines the cardinality of the latent variables as for BIN-G. We show that even with restricting ourselves to binary trees, we obtain HLC models of comparable quality to Zhang's solutions (in terms of cross-validated log-likelihood), while being generally faster to compute. This claim is validated by a comprehensive comparison on several data sets. Furthermore, we demonstrate that our methods are able to estimate interpretable latent structures on real-world data with a large number of variables. By applying our method to a restricted version of the 20 newsgroups data, these models turn out to be related to topic models, and on data from the PASCAL Visual Object Classes (VOC) 2007 challenge, we show how such treestructured models help us understand how objects co-occur in images. For reproducibility of all experiments in this paper, all code and data sets (or links to data) are available at http://people.kyb.tuebingen.mpg.de/harmeling/code/ltt-1.4.tar.

We evaluate the ability of the popular Field-of-Experts (FoE) to model structure in images. As a test case we focus on modeling synthetic and natural textures. We find that even for modeling single textures, the FoE provides insufficient flexibility to learn good generative models – it does not perform any better than the much simpler Gaussian FoE. We propose an extended version of the FoE (allowing for bimodal potentials) and demonstrate that this novel formulation, when trained with a better approximation of the likelihood gradient, gives rise to a more powerful generative model of specific visualstructure that produces significantly better results for the texture task.

Condition monitoring often involves the analysis of systems with hidden factors that switch between different modes of operation in some way. Given a sequence of observations, the task is to infer the filtering distribution of the switch setting at each time step. In this paper, we present factorial switching linear dynamical systems as a general framework for handling such problems. We show how domain knowledge and learning can be successfully combined in this framework, and introduce a new factor (the "X-factor") for dealing with unmodeled variation. We demonstrate the flexibility of this type of model by applying it to the problem of monitoring the condition of a premature baby receiving intensive care. The state of health of a baby cannot be observed directly, but different underlying factors are associated with particular patterns of physiological measurements and artifacts. We have explicit knowledge of common factors and use the X-factor to model novel patterns which are clinically significant but have unknown cause. Experimental results are given which show the developed methods to be effective on typical intensive care unit monitoring data.

We consider the problem of modifying the noise properties of a channel in order to make the source as indecipherable as possible given the output. Applications include jamming communications, maintaining confidentiality near spoken conversations and masking noise pollution. We present results as to how this can be done efficiently, assuming that we have a Gaussian channel and a constraint on the power of the noise. We go on to consider the case in which there is a positive signal which we want to remain coherent, as well as a negative signal which we wish to confound. We also discuss the application of the theory to acoustic signals, where we consider aspects of the human auditory system.

The inverse dynamics problem for a robotic manipulator is to compute the torques needed at the joints to drive it along a given trajectory; it is beneficial to be able to learn this function for adaptive control. A given robot manipulator will often need to be controlled while holding different loads in its end effector, giving rise to a multi-task learning problem. We show how the structure of the inverse dynamics problem gives rise to a multi-task Gaussian process prior over functions, where the inter-task similarity depends on the underlying dynamic parameters. Experiments demonstrate that this multi-task formulation generally improves performance over either learning only on single tasks or pooling the data over all tasks.

In this paper we investigate multi-task learning in the context of Gaussian Pro- cesses (GP). We propose a model that learns a shared covariance function on input-dependent features and a “free-form” covariance matrix over tasks. This al- lows for good flexibility when modelling inter-task dependencies while avoiding the need for large amounts of data for training. We show that under the assump- tion of noise-free observations and a block design, predictions for a given task only depend on its target values and therefore a cancellation of inter-task trans- fer occurs. We evaluate the benefits of our model on two practical applications: a compiler performance prediction problem and an exam score prediction task. Additionally, we make use of GP approximations and properties of our model in order to provide scalability to large data sets.

Iterative compiler optimization has been shown to outperform static approaches. This, however, is at the cost of large numbers of evaluations of the program. This paper develops a new methodology to reduce this number and hence speed up iterative optimization. It uses predictive modelling from the domain of machine learning to automatically focus search on those areas likely to give greatest performance. This approach is independent of search algorithm, search space or compiler infrastructure and scales gracefully with the compiler optimization space size. Off-line, a training set of programs is iteratively evaluated and the shape of the spaces and program features are modelled. These models are learnt and used to focus the iterative optimization of a new program. We evaluate two learnt models, an independent and Markov model, and evaluate their worth on two embedded platforms, the Texas Instrument C67I3 and the AMD Au1500. We show that such learnt models can speed up iterative search on large spaces by an order of magnitude. This translates into an average speedup of 1.22 on the TI C6713 and 1.27 on the AMD Au1500 in just 2 evaluations.

Estimation of Distribution Algorithms (EDAs) are a popular approach to learn a probability distribution over the "good" solutions to a combinatorial optimization problem. Here we consider the case where there is a collection of such optimization problems with learned distributions, and where each problem can be characterized by some vector of features. Now we can define a machine learning problem to predict the distribution of good solutions q(s|x) for a new problem with features x, where s denotes a solution. This predictive distribution is then used to focus the search. We demonstrate the utility of our method on a compiler optimization task where the goal is to find a sequence of code transformations to make the code run fastest. Results on a set of 12 different benchmarks on two distinct architectures show that our approach consistently leads to significant improvements in performance.

MOTIVATION: Short well-defined domains known as peptide recognition modules (PRMs) regulate many important protein-protein interactions involved in the formation of macromolecular complexes and biochemical pathways. Since high-throughput experiments like yeast two-hybrid and phage display are expensive and intrinsically noisy, it would be desirable to more specifically target or partially bypass them with complementary in silico approaches. In the present paper, we present a probabilistic discriminative approach to predicting PRM-mediated protein-protein interactions from sequence data. The model is motivated by the discriminative model of Segal and Sharan as an alternative to the generative approach of Reiss and Schwikowski. In our evaluation, we focus on predicting the interaction network. As proposed by Williams, we overcome the problem of susceptibility to over-fitting by adopting a Bayesian a posteriori approach based on a Laplacian prior in parameter space. RESULTS: The proposed method was tested on two datasets of protein-protein interactions involving 28 SH3 domain proteins in Saccharmomyces cerevisiae, where the datasets were obtained with different experimental techniques. The predictions were evaluated with out-of-sample receiver operator characteristic (ROC) curves. In both cases, Laplacian regularization turned out to be crucial for achieving a reasonable generalization performance. The Laplacian-regularized discriminative model outperformed the generative model of Reiss and Schwikowski in terms of the area under the ROC curve on both datasets. The performance was further improved with a hybrid approach, in which our model was initialized with the motifs obtained with the method of Reiss and Schwikowski. AVAILABILITY: Software and supplementary material is available from http://lehrach.com/wolfgang/dmf.

A popular framework for the interpretation of image sequences is the layers or sprite model of e.g. Wang and Adelson (1994), Irani et al. (1994). Jojic and Frey (2001) provide a generative probabilistic model framework for this task, but their algorithm is slow as it needs to search over discretized transformations (e.g. translations, or affines) for each layer. In this paper we show that by using invariant features (e.g. Lowe’s SIFT features) and clustering their motions we can reduce or eliminate the search and thus learn the sprites much faster. We demonstrate our algorithm on two image sequences. 1

The observed physiological dynamics of an infant receiving intensive care are affected by many possible factors, including interventions to the baby, the operation of the monitoring equipment and the state of health. The Factorial Switching Kalman Filter can be used to infer the presence of such factors from a sequence of observations, and to estimate the true values where these observations have been corrupted. We apply this model to clinical time series data and show it to be effective in identifying a number of artifactual and physiological patterns.

In many areas of data modeling, observations at different locations (e.g.,time frames or pixel locations) are augmented by differences of nea r by observations (e.g., delta features in speech recognition, Gabor jets in image analysis). These augmented observations are then often modeled as being independent. How can this make sense?We provide two interpretations,showing (1) that the likelihood of data generated from an auto regressive process can be computed in terms of "independent" augmented observations and (2) that the augmented observations can be given a coherent treatment in terms of the products of experts model (Hinton, 1999).

In this paper, the relationships between the eigenvalues of the m/spl times/m Gram matrix K for a kernel /spl kappa/(/spl middot/,/spl middot/) corresponding to a sample x/sub 1/,...,x/sub m/ drawn from a density p(x) and the eigenvalues of the corresponding continuous eigenproblem is analyzed. The differences between the two spectra are bounded and a performance bound on kernel principal component analysis (PCA) is provided showing that good performance can be expected even in very-high-dimensional feature spaces provided the sample eigenvalues fall sufficiently quickly.

We describe how we used a data set of chorale harmonisations composed by Johann Sebastian Bach to train Hidden Markov Models. Using a prob- abilistic framework allows us to create a harmonisation system which learns from examples, and which can compose new harmonisations. We make a quantitative comparison of our system's harmonisation perfor- mance against simpler models, and provide example harmonisations.

The equivalent kernel [1] is a way of understanding how Gaussian pro- cess regression works for large sample sizes based on a continuum limit. In this paper we show (1) how to approximate the equivalent kernel of the widely-used squared exponential (or Gaussian) kernel and related ker- nels, and (2) how analysis using the equivalent kernel helps to understand the learning curves for Gaussian processes. Consider the supervised regression problem for a dataset D with entries (xi, yi) for i = 1, . . . , n. Under Gaussian Process (GP) assumptions the predictive mean at a test point x is given by f (x) = k (x)(K + 2I)-1y, (1) where K denotes the n n matrix of covariances between the training points with entries k(xi, xj), k(x) is the vector of covariances k(xi, x), 2 is the noise variance on the observations and y is a n 1 vector holding the training targets. See e.g. [2] for further details. We can define a vector of functions h(x) = (K + 2I)-1k(x) . Thus we have f (x) = h (x)y, making it clear that the mean prediction at a point x is a linear combination of the target values y. Gaussian process regression is thus a linear smoother, see [3, section 2.8] for further details. For a fixed test point x, h(x) gives the vector of weights applied to targets y. Silverman [1] called h (x) the weight function. Understanding the form of the weight function is made complicated by the matrix inversion of K + 2I and the fact that K depends on the specific locations of the n datapoints. Idealizing the situation one can consider the observations to be "smeared out" in x-space at some constant density of observations. In this case analytic tools can be brought to bear on the problem, as shown below. By analogy to kernel smoothing Silverman [1] called the idealized weight function the equivalent kernel (EK). The structure of the remainder of the paper is as follows: In section 1 we describe how to derive the equivalent kernel in Fourier space. Section 2 derives approximations for the EK for the squared exponential and other kernels. In section 3 we show how use the EK approach to estimate learning curves for GP regression, and compare GP regression to kernel regression using the EK. 1 Gaussian Process Regression and the Equivalent Kernel It is well known (see e.g. [4]) that the posterior mean for GP regression can be obtained as the function which minimizes the functional 1 1 n J[f ] = f 2 (y 2 H + 22 i - f (xi))2, (2) n i=1 where f H is the RKHS norm corresponding to kernel k. (However, note that the GP framework gives much more than just this mean prediction, for example the predictive variance and the marginal likelihood p(y) of the data under the model.) Let (x) = E[y|x] be the target function for our regression problem and write E[(y - f (x))2] = E[(y - (x))2] + ((x) - f(x))2. Using the fact that the first term on the RHS is independent of f motivates considering a smoothed version of equation 2, 1 J[f ] = ((x) - f (x))2dx + f 2 22 2 H, where has dimensions of the number of observations per unit of x-space (length/area/volume etc. as appropriate). If we consider kernels that are stationary, k(x, x ) = k(x - x ), the natural basis in which to analyse equation 1 is the Fourier basis of complex sinusoids so that f (x) is represented as ~ f (s)e2isxds and similarly for (x). Thus we obtain 1 | ~ f (s)|2 J[f ] = | ~ f (s) - ~ (s)|2 + ds, 2 2 S(s) as f 2 = | ~ f ( H s)|2/S(s)ds where S(s) is the power spectrum of the kernel k, S(s) = k(x)e-2isxdx. J[f ] can be minimized using calculus of variations to ob- tain ~ f (s) = S(s)(s)/(2/ + S(s)) which is recognized as the convolution f (x) = h(x - x)(x)dx. Here the Fourier transform of the equivalent kernel h(x) is ~ S(s) 1 h(s) = = . (3) S(s) + 2/ 1 + 2/(S(s)) The term 2/ in the first expression for ~ h(s) corresponds to the power spectrum of a white noise process, whose delta-function covariance function becomes a constant in the Fourier domain. This analysis is known as Wiener filtering; see, e.g. [5, 14-1]. Notice that as , h(x) tends to the delta function. If the input density is non-uniform the analysis above should be interpreted as computing the equivalent kernel for np(x) = . This approximation will be valid if the scale of variation of p(x) is larger than the width of the equivalent kernel. 2 The EK for the Squared Exponential and Related Kernels For certain kernels/covariance functions the EK h(x) can be computed exactly by Fourier inversion. Examples include the Ornstein-Uhlenbeck process in D = 1 with covariance k(x) = e-|x| (see [5, p. 326]), splines in D = 1 corresponding to the regularizer P f 2 = (f (m))2dx [1, 6], and the regularizer P f 2 = ( 2f )2dx in two dimen- sions, where the EK is given in terms of the Kelvin function kei [7]. We now consider the commonly used squared exponential (SE) kernel k(r) = exp(-r2/2 2), where r2 = ||x-x ||2. (This is sometimes called the Gaussian or radial ba- sis function kernel.) Its Fourier transform is given by S(s) = (2 2)D/2 exp(-22 2|s|2), where D denotes the dimensionality of x (and s) space. From equation 3 we obtain ~ 1 hSE(s) = , 1 + b exp(22 2|s|2) where b = 2/(2 2)D/2. We are unaware of an exact result in this case, but the following initial approximation is simple but effective. For large , b will be small. Thus for small s = |s| we have that ~ hSE 1, but for large s it is approximately 0. The change takes place around the point sc where b exp(22 2s2c) = 1, i.e. s2c = log(1/b)/22 2. As exp(22 2s2) grows quickly with s, the transition of ~ hSE between 1 and 0 can be expected to be rapid, and thus be well-approximated by a step function. Proposition 1 The approximate form of the equivalent kernel for the squared-exponential kernel in D-dimensions is given by s D/2 h c SE(r) = J r D/2(2scr). Proof: hSE(s) is a function of s = |s| only, and for D > 1 the Fourier integral can be simplified by changing to spherical polar coordinates and integrating out the angular variables to give s +1 hSE(r) = 2r J(2rs)~hSE(s) ds (4) 0 r sc s +1 s D/2 2r J c (2rs) ds = JD/2(2scr). 0 r r where = D/2 - 1, J(z) is a Bessel function of the first kind and we have used the identity z+1J(z) = (d/dz)[z+1J+1(z)]. Note that in D = 1 by computing the Fourier transform of the boxcar function we obtain hSE(x) = 2scsinc(2scx) where sinc(z) = sin(z)/z. This is consistent with Proposition 1 and J1/2(z) = (2/z)1/2 sin(z). The asymptotic form of the EK in D = 2 is shown in Figure 2(left) below. Notice that sc scales as (log())1/2 so that the width of the EK (which is proportional to 1/sc) will decay very slowly as increases. In contrast for a spline of order m (with power spectrum |s|-2m) the width of the EK scales as -1/2m [1]. If instead of RD we consider the input set to be the unit circle, a stationary kernel can be periodized by the construction kp(x, x ) = k(x - x + 2n). This kernel will nZ be represented as a Fourier series (rather than with a Fourier transform) because of the periodicity. In this case the step function in Fourier space approximation would give rise to a Dirichlet kernel as the EK (see [8, section 4.4.3] for further details on the Dirichlet kernel). We now show that the result of Proposition 1 is asymptotically exact for , and calcu- late the leading corrections for finite . The scaling of the width of the EK as 1/sc suggests writing hSE(r) = (2sc)Dg(2scr). Then from equation 4 and using the definition of sc z 2s +1 J g(z) = cs (zs/sc) ds sc(2sc)D 0 z 1 + exp[22 2(s2 - s2c)] u +1 J = z (zu) du (5) 0 2z 1 + exp[22 2s2c(u2 - 1)] where we have rescaled s = scu in the second step. The value of sc, and hence , now enters only in the exponential via a = 22 2s2c. For a , the exponential tends to zero for u < 1 and to infinity for u > 1. The factor 1/[1 + exp(. . .)] is therefore a step function (1 - u) in the limit and Proposition 1 becomes exact, with g(z) lima g(z) = (2z)-D/2JD/2(z). To calculate corrections to this, one uses that for large but finite a the difference (u) = {1 + exp[a(u2 - 1)]}-1 - (1 - u) is non-negligible only in a range of order 1/a around u = 1. The other factors in the integrand of equation 5 can thus be Taylor-expanded around that point to give I dk u +1 g(z) = g k (z) + z J , I (u)(u - 1)k du k! duk 2z (zu) k = k=0 u=1 0 The problem is thus reduced to calculating the integrals Ik. Setting u = 1 + v/a one has 0 1 vk ak+1Ik = - 1 vk dv + dv -a 1 + exp(v2/a + 2v) 0 1 + exp(v2/a + 2v) a (-1)k+1vk vk = dv + dv 0 1 + exp(-v2/a + 2v) 0 1 + exp(v2/a + 2v) In the first integral, extending the upper limit to gives an error that is exponentially small in a. Expanding the remaining 1/a-dependence of the integrand one then gets, to leading order in 1/a, I0 = c0/a2, I1 = c1/a2 while all Ik with k 2 are smaller by at least 1/a2. The numerical constants are -c0 = c1 = 2/24. This gives, using that (d/dz)[z+1J(z)] = zJ(z) + z+1J-1(z) = (2 + 1)zJ(z) - z+1J+1(z): Proposition 2 The equivalent kernel for the squared-exponential kernel is given for large by hSE(r) = (2sc)Dg(2scr) with 1 z 1 g(z) = J (c ) D D/2(z) + 0 + c1(D - 1))JD/2-1(z) - c1zJD/2(z) +O( (2z) 2 a2 a4 For e.g. D = 1 this becomes g(z) = -1{sin(z)/z - 2/(24a2)[cos(z) + z sin(z)]}. Here and in general, by comparing the second part of the 1/a2 correction with the leading order term, one estimates that the correction is of relative size z2/a2. It will therefore provide a useful improvement as long as z = 2scr < a; for larger z the expansion in powers of 1/a becomes a poor approximation because the correction terms (of all orders in 1/a) are comparable to the leading order. 2.1 Accuracy of the approximation To evaluate the accuracy of the approximation we can compute the EK numerically as follows: Consider a dense grid of points in RD with a sampling density grid. For making predictions at the grid points we obtain the smoother matrix K(K + 2 I)-1 grid , where1 2 = 2 grid grid/, as per equation 1. Each row of this matrix is an approximation to the EK at the appropriate location, as this is the response to a y vector which is zero at all points except one. Note that in theory one should use a grid over the whole of RD but in practice one can obtain an excellent approximation to the EK by only considering a grid around the point of interest as the EK typically decays with distance. Also, by only considering a finite grid one can understand how the EK is affected by edge effects. 1To understand this scaling of 2grid consider the case where grid > which means that the effective variance at each of the grid points per unit x-space is larger, but as there are correspondingly more points this effect cancels out. This can be understood by imagining the situation where there are grid/ independent Gaussian observations with variance 2grid at a single x-point; this would be equivalent to one Gaussian observation with variance 2. In effect the observations per unit x-space have been smoothed out uniformly. 0.16 0.35 0.35 Numerical Numerical 0.3 0.3 Proposition 1 Proposition 1 0.25 Proposition 2 0.25 Proposition 2 0.14 0.2 0.2 0.15 0.15 0.12 0.1 0.1 0.05 0.05 0.1 0 0 -0.05 -0.05 0.08 -0.1 -0.1 0 5 10 15 0 5 10 15 0.06 0.04 0.02 0 -0.02 Numerical Proposition 1 -0.04 Sample -0.5 -0.4 -0.3 -0.2 -0.1 0 0.1 0.2 0.3 0.4 0.5 Figure 1: Main figure: plot of the weight function corresponding to = 100 training points/unit length, plus the numerically computed equivalent kernel at x = 0.0 and the sinc approximation from Proposition 1. Insets: numerically evaluated g(z) together with sinc and Proposition 2 approximations for = 100 (left) and = 104 (right). Figure 1 shows plots of the weight function for = 100, the EK computed on the grid as described above and the analytical sinc approximation. These are computed for parameter values of 2 = 0.004 and 2 = 0.1, with grid/ = 5/3. To reduce edge effects, the interval [-3/2, 3/2] was used for computations, although only the centre of this is shown in the figure. There is quite good agreement between the numerical computation and the analytical approximation, although the sidelobes decay more rapidly for the numerically computed EK. This is not surprising because the absence of a truly hard cutoff in Fourier space means one should expect less "ringing" than the analytical approximation predicts. The figure also shows good agreement between the weight function (based on the finite sample) and the numerically computed EK. The insets show the approximation of Proposi- tion 2 to g(z) for = 100 (a = 5.67, left) and = 104 (a = 9.67, right). As expected, the addition of the 1/a2-correction gives better agreement with the numerical result for z < a. Numerical experiments also show that the mean squared error between the numerically computed EK and the sinc approximation decreases like 1/ log(). The is larger than the naive estimate (1/a2)2 1/(log())4 based on the first correction term from Proposition 2, because the dominant part of the error comes from the region z > a where the 1/a expansion breaks down. 2.2 Other kernels Our analysis is not in fact restricted to the SE kernel. Consider an isotropic kernel, for which the power spectrum S(s) depends on s = |s| only. Then we can again define from equation 3 an effective cutoff sc on the range of s in the EK via 2/ = S(sc), so that ~ h(s) = [1 + S(sc)/S(s)]-1. The EK will then have the limiting form given in Proposi- tion 1 if ~ h(s) approaches a step function (sc - s), i.e. if it becomes infinitely "steep" around the point s = sc for sc . A quantitative criterion for this is that the slope |~ h (sc)| should become much larger than 1/sc, the inverse of the range of the step func- tion. Since ~ h (s) = S (s)S(sc)S-2(s)[1 + S(sc)/S(s)]-2, this is equivalent to requiring that -scS (sc)/4S(sc) -d log S(sc)/d log sc must diverge for sc . The result of Proposition 1 therefore applies to any kernel whose power spectrum S(s) decays more rapidly than any positive power of 1/s. A trivial example of a kernel obeying this condition would be a superposition of finitely many SE kernels with different lengthscales 2; the asymptotic behaviour of sc is then governed by the smallest . A less obvious case is the "rational quadratic" k(r) = [1 + (r/l)2]-(D+1)/2 which has an exponentially decaying power spectrum S(s) exp(-2 s). (This relationship is often used in the reverse direction, to obtain the power spectrum of the Ornstein-Uhlenbeck (OU) kernel exp(-r/ ).) Proposition 1 then applies, with the width of the EK now scaling as 1/sc 1/ log(). The previous example is a special case of kernels which can be written as superpositions of SE kernels with a distribution p( ) of lengthscales , k(r) = exp(-r2/2 2)p( ) d . This is in fact the most general representation for an isotropic kernel which defines a valid covariance function in any dimension D, see [9, 2.10]. Such a kernel has power spectrum S(s) = (2)D/2 D exp(-22 2s2)p( ) d (6) 0 and one easily verifies that the rational quadratic kernel, which has S(s) exp(-2 0s), is obtained for p( ) -D-2 exp(- 20/2 2). More generally, because the exponential factor in equation 6 acts like a cutoff for > 1/s, one estimates S(s) 1/s Dp( ) d 0 for large s. This will decay more strongly than any power of 1/s for s if p( ) itself decreases more strongly than any power of for 0. Any such choice of p( ) will therefore yield a kernel to which Proposition 1 applies. 3 Understanding GP Learning Using the Equivalent Kernel We now turn to using EK analysis to get a handle on average case learning curves for Gaus- sian processes. Here the setup is that a function is drawn from a Gaussian process, and we obtain noisy observations of per unit x-space at random x locations. We are concerned with the mean squared error (MSE) between the GP prediction f and . Averaging over the noise process, the x-locations of the training data and the prior over we obtain the average MSE as a function of . See e.g. [10] and [11] for an overview of earlier work on GP learning curves. To understand the asymptotic behaviour of for large , we now approximate the true GP predictions with the EK predictions from noisy data, given by fEK(x) = h(x - x )y(x )dx in the continuum limit of "smoothed out" input locations. We assume as before that y = target + noise, i.e. y(x) = (x) + (x) where E[(x)(x )] = (2/)(x - x ). Here 2 denotes the true noise variance, as opposed to the noise variance assumed in the EK; the scaling of 2 with is explained in footnote 1. For a fixed target , the MSE is = ( dx)-1 [(x) - fEK(x)]2dx. Averaging over the noise process and target function gives in Fourier space 2 (2/)S = S (s)/S2(s) + 2 /2 (s)[1 - ~ h(s)]2 + (2/)~h2(s) ds = ds [1 + 2/(S(s))]2 (7) where S(s) is the power spectrum of the prior over target functions. In the case S(s) = S(s) and 2 = 2 where the kernel is exactly matched to the structure of the target, equation 7 gives the Bayes error B and simplifies to B = (2/) [1 + 2/(S(s))]-1ds (see also [5, eq. 14-16]). Interestingly, this is just the analogue (for a continuous power spectrum of the kernel rather than a discrete set of eigenvalues) of the lower bound of [10] 0.5 0.5 =2 0.03 0.025 0.02 0.015 0.01 0.1 =4 0.005 0 -0.005 1 0.05 0.5 1 0.5 0 0 -0.5 25 50 100 -0.5 250 500 -1 -1 Figure 2: Left: plot of the asymptotic form of the EK (sc/r)J1(2scr) for D = 2 and = 1225. Right: log-log plot of against log() for the OU and Matern-class processes ( = 2, 4 respectively). The dashed lines have gradients of -1/2 and -3/2 which are the predicted rates. on the MSE of standard GP prediction from finite datasets. In experiments this bound provides a good approximation to the actual average MSE for large dataset size n [11]. This supports our approach of using the EK to understand the learning behaviour of GP regression. Treating the denominator in the expression for B again as a hard cutoff at s = sc, which is justified for large , one obtains for an SE target and learner 2sc/ (log())D/2/. To get analogous predictions for the mismatched case, one can write equation 7 as 2 [1 + 2/(S(s))] - 2/(S(s)) S = d (s) s + ds. [1 + 2/(S(s))]2 [S(s)/2 + 1]2 The first integral is smaller than (2/2) B and can be neglected as long as B. In the second integral we can again make the cutoff approximation--though now with s having to be above sc to get the scaling sD-1S s (s) ds. For target functions with a c power-law decay S(s) s- of the power spectrum at large s this predicts sD- c (log())(D-)/2. So we generically get slow logarithmic learning, consistent with the observations in [12]. For D = 1 and an OU target ( = 2) we obtain (log())-1/2, and for the Matern-class covariance function k(r) = (1 + r/ ) exp(-r/ ) (which has power spectrum (3/ 2 + 42s2)-2, so = 4) we get (log())-3/2. These predictions were tested experimentally using a GP learner with SE covariance function ( = 0.1 and assumed noise level 2 = 0.1) against targets from the OU and Matern-class priors (with = 0.05) and with noise level 2 = 0.01, averaging over 100 replications for each value of . To demonstrate the predicted power-law dependence of on log(), in Figure 2(right) we make a log-log plot of against log(). The dashed lines show the gradients of -1/2 and -3/2 and we observe good agreement between experimental and theoretical results for large . 3.1 Using the Equivalent Kernel in Kernel Regression Above we have used the EK to understand how standard GP regression works. One could alternatively envisage using the EK to perform kernel regression, on given finite data sets, producing a prediction -1 h(x i - xi)yi at x. Intuitively this seems appealing as a cheap alternative to full GP regression, particularly for kernels such as the SE where the EK can be calculated analytically, at least to a good approximation. We now analyze briefly how such an EK predictor would perform compared to standard GP prediction. Letting denote averaging over noise, training input points and the test point and setting f(x) = h(x, x)(x)dx, the average MSE of the EK predictor is pred = [(x) - (1/) h(x, x i i)yi]2 = [(x) - f(x)]2 + 2 h2(x, x )dx + 1 h2(x, x )2(x )dx - 1 f 2 (x) 2 (2/)S 2 ds = (s)/S2(s) + 2 /2 ds + [1 + 2/(S(s))]2 [1 + 2/(S(s))]2 Here we have set 2 = ( dx)-1 2(x) dx = S(s) ds for the spatial average of the squared target amplitude. Taking the matched case, (S(s) = S(s) and 2 = 2) as an example, the first term (which is the one we get for the prediction from "smoothed out" training inputs, see eq. 7) is of order 2sD c /, while the second one is 2 sD c /. Thus both terms scale in the same way, but the ratio of the second term to the first is the signal- to-noise ratio 2 /2, which in practice is often large. The EK predictor will then perform significantly worse than standard GP prediction, by a roughly constant factor, and we have confirmed this prediction numerically. This result is somewhat surprising given the good agreement between the weight function h(x) and the EK that we saw in figure 1, leading to the conclusion that the detailed structure of the weight function is important for optimal prediction from finite data sets. In summary, we have derived accurate approximations for the equivalent kernel (EK) of GP regression with the widely used squared exponential kernel, and have shown that the same analysis in fact extends to a whole class of kernels. We have also demonstrated that EKs provide a simple means of understanding the learning behaviour of GP regression, even in cases where the learner's covariance function is not well matched to the structure of the target function. In future work, it will be interesting to explore in more detail the use of the EK in kernel smoothing. This is suboptimal compared to standard GP regression as we saw. However, it does remain feasible even for very large datasets, and may then be competitive with sparse methods for approximating GP regression. From the theoretical point of view, the average error of the EK predictor which we calculated may also provide the basis for useful upper bounds on GP learning curves. Acknowledgments: This work was supported in part by the IST Programme of the Eu- ropean Community, under the PASCAL Network of Excellence, IST-2002-506778. This publication only reflects the authors' views.

We consider data that are images containing views of multiple objects. Our task is to learn about each of the objects present in the images. This task can be approached as a factorial learning problem, where each image must be explained by instantiating a model for each of the objects present with the correct instantiation parameters. A major problem with learning a factorial model is that as the number of objects increases, there is a combinatorial explosion of the number of configurations that need to be considered. We develop a method to extract object models sequentially from the data by making use of a robust statistical method, thus avoiding the combinatorial explosion, and present results showing successful extraction of objects from real images.

Principal components analysis (PCA) is one of the most widely used techniques in machine learning and data mining. Minor components analysis (MCA) is less well known, but can also play an important role in the presence of constraints on the data distribution. In this paper we present a probabilistic model for “extreme components analysis” (XCA) which at the maximum likelihood solution extracts an optimal combina- tion of principal and minor components. For a given number of compo- nents, the log-likelihood of the XCA model is guaranteed to be larger or equal than that of the probabilistic models for PCA and MCA. We de- scribe an efficient algorithm to solve for the globally optimal solution. For log-convex spectra we prove that the solution consists of principal components only, while for log-concave spectra the solution consists of minor components. In general, the solution admits a combination of both. In experiments we explore the properties of XCA on some synthetic and real-world datasets.

This paper describes the position-encoding dynamic tree (PEDT). The PEDT is a probabilistic model for images that improves on the dynamic tree by allowing the positions of objects to play a part in the model. This increases the flexibility of the model over the dynamic tree and allows the positions of objects to be located and manipulated. This paper motivates and defines this form of probabilistic model using the belief network formalism. A structured variational approach for inference and learning in the PEDT is developed, and the resulting variational updates are obtained, along with additional implementation considerations that ensure the computational cost scales linearly in the number of nodes of the belief network. The PEDT model is demonstrated and compared with the dynamic tree and fixed tree. The structured variational learning method is compared with mean field approaches.

In this paper we analyze the relationships between the eigenvalues of the m x m Gram matrix K for a kernel k(·, .) corresponding to a sample Xl, ... ,Xm drawn from a density p(x) and the eigenvalues of the corresponding continuous eigenproblem. We bound the dif(cid:173) ferences between the two spectra and provide a performance bound on kernel peA.

We consider data which are images containing views of multiple objects. Our task is to learn about each of the objects present in the images. This task can be approached as a factorial learning problem, where each image must be explained by instantiating a model for each of the objects present with the correct instantiation parameters. A major problem with learning a factorial model is that as the number of objects increases, there is a combinatorial explosion of the number of configurations that need to be considered. We develop a method to extract object models sequentially from the data by making use of a robust statistical method, thus avoid- ing the combinatorial explosion, and present results showing successful extraction of objects from real images.

Recently, Hinton introduced the products of experts architecture for density estimation, where individual expert probabilities are multiplied and renormalized. We consider products of gaussian "pancakes" equally elongated in all directions except one and prove that the maximum likelihood solution for the model gives rise to a minor component analysis solution. We also discuss the covariance structure of sums and products of gaussian pancakes or one-factor probabilistic principal component analysis models.

We are concerned with the problem of image segmentation, in which each pixel is assigned to one of a predefined finite number of labels. In Bayesian image analysis, this requires fusing together local predictions for the class labels with a prior model of label images. Following the work of Bouman and Shapiro (1994), we consider the use of tree-structured belief networks (TSBNs) as prior models. The parameters in the TSBN are trained using a maximum-likelihood objective function with the EM algorithm and the resulting model is evaluated by calculating how efficiently it codes label images. A number of authors have used Gaussian mixture models to connect the label field to the image data. We compare this approach to the scaled-likelihood method of Smyth (1994) and Morgan and Bourlard (1995), where local predictions of pixel classification from neural networks are fused with the TSBN prior. Our results show a higher performance is obtained with the neural networks. We evaluate the classification results obtained and emphasize not only the maximum a posteriori segmentation, but also the uncertainty, as evidenced e.g., by the pixelwise posterior marginal entropies. We also investigate the use of conditional maximum-likelihood training for the TSBN and find that this gives rise to improved classification performance over the ML-trained TSBN.

Recently Hinton (1999) has introduced the Products of Experts (PoE) model in which several individual probabilistic models for data are combined to provide an overall model of the data. Be(cid:173) low we consider PoE models in which each expert is a Gaussian. Although the product of Gaussians is also a Gaussian, if each Gaus(cid:173) sian has a simple structure the product can have a richer structure. We examine (1) Products of Gaussian pancakes which give rise to probabilistic Minor Components Analysis, (2) products of I-factor PPCA models and (3) a products of experts construction for an AR(l) process. Recently Hinton (1999) has introduced the Products of Experts (PoE) model in which several individual probabilistic models for data are combined to provide an overall model of the data. In this paper we consider PoE models in which each expert is a Gaussian. It is easy to see that in this case the product model will also be Gaussian. However, if each Gaussian has a simple structure, the product can have a richer structure. Using Gaussian experts is attractive as it permits a thorough analysis of the product architecture, which can be difficult with other models, e.g. models defined over discrete random variables. Below we examine three cases of the products of Gaussians construction: (1) Prod(cid:173) ucts of Gaussian pancakes (PoGP) which give rise to probabilistic Minor Compo(cid:173) nents Analysis (MCA), providing a complementary result to probabilistic Principal Components Analysis (PPCA) obtained by Tipping and Bishop (1999); (2) Prod(cid:173) ucts of I-factor PPCA models; (3) A products of experts construction for an AR(l) process. Products of Gaussians If each expert is a Gaussian pi(xI8i ) '" N(J1i' ( i), the resulting distribution of the product of m Gaussians may be expressed as By completing the square in the exponent it may be easily shown that p(xI8) N(/1;E, (2:), where (E l = 2::1 (i l . To simplify the following derivations we will assume that pi(xI8i ) '" N(O, (i) and thus that p(xI8) '" N(O, (2:). J12: i ° can be obtained by translation of the coordinate system. 1 Products of Gaussian Pancakes A Gaussian "pancake" (GP) is a d-dimensional Gaussian, contracted in one dimen(cid:173) sion and elongated in the other d - 1 dimensions. In this section we show that the maximum likelihood solution for a product of Gaussian pancakes (PoGP) yields a probabilistic formulation of Minor Components Analysis (MCA). 1.1 Covariance Structure of a GP Expert Consider a d-dimensional Gaussian whose probability contours are contracted in the direction w and equally elongated in mutually orthogonal directions VI , ... , vd-l.We call this a Gaussian pancake or GP. Its inverse covariance may be written as

Tree structured belief networks are attractive for image segmentation tasks. However, networks with fixed architectures are not very suitable as they lead to blocky artefacts, and led to the introduction of dynamic trees (DTs). The Dynamic trees architecture provide a prior distribution over tree structures, and simulated annealing (SA) was used to search for structures with high posterior probability. In this paper we introduce a mean field approach to inference in DTs. We find that the mean field method captures the posterior better than just using the maximum a posteriori solution found by SA.

In this paper we show that the kernel peA algorithm of Sch6lkopf et al (1998) can be interpreted as a form of metric multidimensional scaling (MDS) when the kernel function k(x, y) is isotropic, i.e. it depends only on Ilx - yll. This leads to a metric MDS algorithm where the desired configuration of points is found via the solution of an eigenproblem rather than through the iterative optimization of the stress objective function. The question of kernel choice is also discussed.

Latent variable models represent the probability density of data in a space of several dimensions in terms of a smaller number of latent, or hidden, variables. A familiar example is factor analysis, which is based on a linear transformation between the latent space and the data space. In this article, we introduce a form of nonlinear latent variable model called the generative topographic mapping, for which the parameters of the model can be determined using the expectation-maximization algorithm. GTM provides a principled alternative to the widely used self-organizing map (SOM) of Kohonen (1982) and overcomes most of the significant limitations of the SOM. We demonstrate the performance of the GTM algorithm on a toy problem and on simulated data from flow diagnostics for a multiphase oil pipeline.

For neural networks with a wide class of weight priors, it can be shown that in the limit of an infinite number of hidden units, the prior over functions tends to a gaussian process. In this article, analytic forms are derived for the covariance function of the gaussian processes corresponding to networks with sigmoidal and gaussian hidden units. This allows predictions to be made efficiently using networks with an infinite number of hidden units and shows, somewhat paradoxically, that it may be easier to carry out Bayesian prediction with infinite networks rather than finite ones.

We consider the problem of assigning an input vector to one of m classes by predicting P(c|x) for c=1,...,m. For a two-class problem, the probability of class one given x is estimated by /spl sigma/(y(x)), where /spl sigma/(y)=1/(1+e/sup -y/). A Gaussian process prior is placed on y(x), and is combined with the training data to obtain predictions for new x points. We provide a Bayesian treatment, integrating over uncertainty in y and in the parameters that control the Gaussian process prior the necessary integration over y is carried out using Laplace's approximation. The method is generalized to multiclass problems (m>2) using the softmax function. We demonstrate the effectiveness of the method on a number of datasets.

We describe a method of recognizing handwritten digits by fitting generative models that are built from deformable B-splines with Gaussian "ink generators" spaced along the length of the spline. The splines are adjusted using a novel elastic matching procedure based on the expectation maximization algorithm that maximizes the likelihood of the model generating the data. This approach has many advantages: 1) the system not only produces a classification of the digit but also a rich description of the instantiation parameters which can yield information such as the writing style; 2) the generative models can perform recognition driven segmentation; 3) the method involves a relatively small number of parameters and hence training is relatively easy and fast; and 4) unlike many other recognition schemes, it does not rely on some form of pre-normalization of input images, but can handle arbitrary scalings, translations and a limited degree of image rotation. We have demonstrated that our method of fitting models to images does not get trapped in poor local minima. The main disadvantage of the method is that it requires much more computation than more standard OCR techniques.

Deformable models are an attractive approach to recognizing non(cid:173) rigid objects which have considerable within class variability. How(cid:173) ever, there are severe search problems associated with fitting the models to data. We show that by using neural networks to provide better starting points, the search time can be significantly reduced. The method is demonstrated on a character recognition task. In previous work we have developed an approach to handwritten character recogni(cid:173) tion based on the use of deformable models (Hinton, Williams and Revow, 1992a; Revow, Williams and Hinton, 1993). We have obtained good performance with this method, but a major problem is that the search procedure for fitting each model to an image is very computationally intensive, because there is no efficient algorithm (like dynamic programming) for this task. In this paper we demonstrate that it is possible to "compile down" some of the knowledge gained while fitting models to data to obtain better starting points that significantly reduce the search time. 1 DEFORMABLE MODELS FOR DIGIT RECOGNITION The basic idea in using deformable models for digit recognition is that each digit has a model, and a test image is classified by finding the model which is most likely to have generated it. The quality of the match between model and test image depends on the deformation of the model, the amount of ink that is attributed to noise and the distance of the remaining ink from the deformed model. ·Current address: Department of Computer Science and Applied Mathematics, Aston University, Birmingham B4 7ET, UK. 966 Christopher K. T. Williams, Michael D. Revow, Geoffrey E. Hinton More formally, the two important terms in assessing the fit are the prior probabil(cid:173) ity distribution for the instantiation parameters of a model (which penalizes very distorted models), and the imaging model that characterizes the probability distri(cid:173) bution over possible images given the instantiated model l . Let I be an image, M be a model and z be its instantiation parameters. Then the evidence for model M is given by P(IIM) = J P(zIM)P(IIM, z)dz (1) The first term in the integrand is the prior on the instantiation parameters and the second is the imaging model i.e., the likelihood of the data given the instantiated model. P(MII) is directly proportional to P(IIM), as we assume a uniform prior on each digit. Equation 1 is formally correct, but if z has more than a few dimensions the evalua(cid:173) tion of this integral is very computationally intensive. However, it is often possible to make an approximation based on the assumption that the integrand is strongly peaked around a (global) maximum value z*. In this case, the evidence can be ap(cid:173) proximated by the highest peak of the integrand times a volume factor ~(zII, M), which measures the sharpness of the peak2 . P(IIM) ~ P(zIM)P(Ilz, M)~(zII, M) (2) By Taylor expanding around z* to second order it can be shown that the volume factor depends on the determinant of the Hessian of 10gP(z, 11M) . Taking logs of equation 2, defining EdeJ as the negative log of P(z*IM), and EJit as the cor(cid:173) responding term for the imaging model, then the aim of the search is to find the minimum of E tot = EdeJ + EJit . Of course the total energy will have many local minima; for the character recognition task we aim to find the global minimum by using a continuation method (see section 1.2). 1.1 SPLINES, AFFINE TRANSFORMS AND IMAGING MODELS This section presents a brief overview of our work on using deformable models for digit recognition. For a fuller treatment, see Revow, Williams and Hinton (1993) . Each digit is modelled by a cubic B-spline whose shape is determined by the posi(cid:173) tions of the control points in the object-based frame. The models have eight control points, except for the one model which has three, and the seven model which has five. To generate an ideal example of a digit the control points are positioned at their "home" locations. Deformed characters are produced by perturbing the con(cid:173) trol points away from their home locations. The home locations and covariance matrix for each model were adapted in order to improve the performance. The deformation energy only penalizes shape deformations. Affine transformations, i.e., translation, rotation, dilation, elongation, and shear, do not change the under(cid:173) lying shape of an object so we want the deformation energy to be invariant under them . We achieve this by giving each model its own "object-based frame" and computing the deformation energy relative to this frame. lThis framework has been used by many authors, e.g. Grenander et al (1991) . 2The Gaussian approximation has been popularized in the neural net community by

Despite the fact that complex visual scenes contain multiple, overlapping objects, people perform object recognition with ease and accuracy. One operation that facilitates recognition is an early segmentation process in which features of objects are grouped and labeled according to which object they belong. Current computational systems that perform this operation are based on predefined grouping heuristics. We describe a system called MAGIC that learns how to group features based on a set of presegmented examples. In many cases, MAGIC discovers grouping heuristics similar to those previously proposed, but it also has the capability of finding nonintuitive structural regularities in images. Grouping is performed by a relaxation network that attempts to dynamically bind related features. Features transmit a complex-valued signal (amplitude and phase) to one another; binding can thus be represented by phase locking related features. MAGIC's training procedure is a generalization of recurrent backpropagation to complex-valued units.