Abstracts
|
Graphical Models for Statistical Inference and Data Assimilation |
|
In data assimilation for a system which evolves in time, one combines past and current observations with a model of the dynamics of the system, in order to improve the simulation of the system as well as any future predictions about it. From a statistical point of view, this process can be regarded as estimating many random variables which are related both spatially and temporally: given observations of some of these variables, typically corresponding to times past, we require estimates of several others, typically corresponding to future times.
Graphical models have emerged as an effective formalism for assisting in these types of inference tasks, particularly for large numbers of
random variables. Graphical models provide a means of representing dependency structure among the variables, and can provide both intuition
and efficiency in estimation and other inference computations. We provide an overview and introduction to graphical models, and describe how
they can be used to represent statistical dependency and how the resulting structure can be used to organize computation. The relation between
statistical inference using graphical models and optimal sequential estimation algorithms such as Kalman filtering is discussed. We then give
several additional examples of how graphical models can be applied to climate dynamics, specifically estimation using multi-resolution models of
large-scale data sets such as satellite imagery, and learning hidden Markov models to capture rainfall patterns in space and time.
[PDF] | [PS]
|
Accuracy Bounds for Belief Propagation |
|
The belief propagation algorithm is widely applied to perform
approximate inference on arbitrary graphical models, in part due to
its excellent empirical properties and performance. However, little
is known theoretically about when this algorithm will perform well.
Using recent analysis of convergence and stability properties in
belief propagation and new results on approximations in binary
systems, we derive a bound on the error in BP's estimates for
pairwise Markov random fields over discrete--valued random variables.
Our bound is relatively simple to compute, and compares favorably
with a previous method for bounding the accuracy of
belief propagation.
[PDF] | [PS]
|
Distributed Fusion in Sensor Networks: A graphical models perspective |
|
Distributed inference methods developed for graphical models comprise a principled
approach for data fusion in sensor networks. The application of these methods, however,
requires some care due to a number of issues that are particular to sensor networks.
Chief of among these are the distributed nature of computation and
deployment coupled with communications bandwidth and energy constraints typical
of many sensor networks. Additionally, information sharing in a sensor network necessarily
involves approximation. Traditional measures of distortion are not sufficient to characterize the
quality of approximation as they do not address in an explicit manner the resulting impact on inference
which is at the core of many data fusion problems. While both graphical models and a distributed
sensor network have network structures associated with them, the mapping is not one to one.
All of these issues complicate the mapping of a particular inference problem to a given sensor network
structure. Indeed, there may be a variety of mappings with very different characteristics with
regard to computational complexity and utilization of resources. Nevertheless, it is the case that
many of the powerful distributed inference methods have a role in information fusion for sensor
networks. In this article we present an overview of research conducted by the authors that has
sought to clarify many of the important issues at the intersection
of these domains. We discuss both theoretical issues and prototypical
applications in addition to suggesting new lines of reasoning.
[PDF]
|
Gibbs Sampling for (Coupled) Infinite Mixture Models in the Stick Breaking Representation |
|
Nonparametric Bayesian approaches to clustering,
information retrieval, language modeling
and object recognition have recently shown great
promise as a new paradigm for unsupervised data
analysis. Most contributions have focused on the
Dirichlet process mixture models or extensions
thereof for which efficient Gibbs samplers exist.
In this paper we explore Gibbs samplers for
infinite complexity mixture models in the stick
breaking representation. The advantage of this
representation is improved modeling flexibility.
For instance, one can design the prior distribution
over cluster sizes or couple multiple infi-
nite mixture models (e.g., over time) at the level
of their parameters (i.e., the dependent Dirichlet
process model). However, Gibbs samplers for in-
finite mixture models (as recently introduced in
the statistics literature) seem to mix poorly over
cluster labels. Among others issues, this can have
the adverse effect that labels for the same cluster
in coupled mixture models are mixed up. We
introduce additional moves in these samplers to
improve mixing over cluster labels and to bring
clusters into correspondence. An application to
modeling of storm trajectories is used to illustrate
these ideas.
[PDF] | [PS]
|
Adaptive event detection with time-varying Poisson processes |
|
Time-series of count data are generated in many different contexts, such as web access logging, freeway traffic monitoring, and security logs associated with buildings. Since this data measures the aggregated behavior of individual human beings, it typically exhibits a periodicity in time on a number of scales (daily, weekly,etc.) that reflects the rhythms of the underlying human activity and makes the data appear non-homogeneous. At the same time, the data is often corrupted by a number of bursty periods of unusual behavior such as building events, traffic accidents, and so forth. The data mining problem of finding and extracting these anomalous events is made difficult by both of these elements. In this paper we describe a framework for unsupervised learning in this context, based on a time-varying Poisson process model that can also account for anomalous events. We show how the parameters of this model can be learned from count time series using statistical estimation techniques. We demonstrate the utility of this model on two datasets for which we have partial ground truth in the form of known events, one from freeway traffic data and another from building access data, and show that the model performs significantly better than a non-probabilistic, threshold-based technique. We also describe how the model can be used to investigate different degrees of periodicity in the data, including systematic day-of-week and time-of-day effects, and make inferences about the detected events (e.g., popularity or level of attendance). Our experimental results indicate that the proposed time-varying Poisson model provides a robust and accurate framework for adaptively and autonomously learning how to separate unusual bursty events from traces of normal human activity.
[PDF] | [PS]
|
Learning Time-Intensity Profiles of Human Activity using Non-Parametric Bayesian Models |
|
Data sets that characterize human activity over time through collections of timestamped
events or counts are of increasing interest in application areas as humancomputer
interaction, video surveillance, and Web data analysis. We propose a
non-parametric Bayesian framework for modeling collections of such data. In
particular, we use a Dirichlet process framework for learning a set of intensity
functions corresponding to different categories, which form a basis set for representing
individual time-periods (e.g., several days) depending on which categories
the time-periods are assigned to. This allows the model to learn in a data-driven
fashion what factors are generating the observations on a particular day, including
(for example) weekday versus weekend effects or day-specific effects corresponding
to unique (single-day) occurrences of unusual behavior, sharing information
where appropriate to obtain improved estimates of the behavior associated
with each category. Applications to realworld data sets of count data involving
both vehicles and people are used to illustrate the technique.
[PDF] | [PS]
|
Loopy Belief Propagation: Convergence and Effects of Message Errors |
|
Belief propagation (BP) is an increasingly popular method of performing
approximate inference on arbitrary graphical models. At times, even
further approximations are required, whether due to quantization of the
messages or model parameters, from other simplified message or model
representations, or from stochastic approximation methods. The
introduction of such errors into the BP message computations has the
potential to affect the solution obtained adversely. We analyze the
effect resulting from message approximation under two particular measures
of error, and show bounds on the accumulation of errors in the system.
This analysis leads to convergence conditions for traditional BP message
passing, and both strict bounds and estimates of the resulting error in
systems of approximate BP message passing.
[PDF] | [PS]
|
Nonparametric Belief Propagation for Self-Localization of Sensor Networks |
|
Automatic self-localization is a critical need for the effective use of
ad-hoc sensor networks in military or civilian applications. In general,
self-localization involves the combination of absolute location
information (\eg GPS) with relative calibration information (\eg distance
measurements between sensors) over regions of the network. Furthermore, it
is generally desirable to distribute the computational burden across the
network and minimize the amount of inter-sensor communication. We
demonstrate that the information used for sensor localization is
fundamentally local with regard to the network topology and use this
observation to reformulate the problem within a graphical model framework.
We then present and demonstrate the utility of \emph{nonparametric belief
propagation} (NBP), a recent generalization of particle filtering, for
both estimating sensor locations and representing location uncertainties.
NBP has the advantage that it is easily implemented in a distributed
fashion, admits a wide variety of statistical models, and can represent
multi-modal uncertainty. Using simulations of small- to moderately-sized
sensor networks, we show that NBP may be made robust to outlier
measurement errors by a simple model augmentation, and that judicious
message construction can result in better estimates. Furthermore, we
provide an analysis of NBP's communications requirements, showing that
typically only a few messages per sensor are required, and that even low
bit-rate approximations of these messages can have little or no
performance impact.
[PDF] | [PS]
|
Particle filtering under communications constraints |
|
Particle filtering is often applied to the problem of object tracking
under non-Gaussian uncertainty; however, sensor networks frequently
require that the implementation be local to the region of interest,
eventually forcing the large, sample-based representation to be moved
among power-constrained sensors. We consider the problem of successive
approximation (i.e., lossy compression) of each sample-based density
estimate, in particular exploring the consequences (both theoretical and
empirical) of several possible choices of loss function and their
interpretation in terms of future errors in inference, justifying their
use for measuring approximations in distributed particle filtering.
[PDF] | [PS]
|
Estimating Dependency and Significance for High-Dimensional Data |
|
Understanding the dependency structure of a set of variables is a
key component in various signal processing applications which involve
data association. The simple task of detecting whether any
dependency exists is particularly difficult when models of the data
are unknown or difficult to characterize because of high-dimensional
measurements. We review the use of nonparametric tests for characterizing
dependency and how to carry out these tests with highdimensional
observations. In addition we present a method to assess
the significance of the tests.
[PDF]
|
Nonparametric Hypothesis Tests for Statistical Dependency |
|
Determining the structure of dependencies among a set of variables is a
common task in many signal and image processing applications, including
multi-target tracking and computer vision. In this paper we present an
information-theoretic, machine learning approach to problems of this type.
We cast this problem as a hypothesis test between factorizations of
variables into mutually independent subsets. We show that the likelihood
ratio can be written as sums of two sets of Kullback-Leibler (KL)
divergence terms. The first set captures the structure of the statistical
dependencies within each hypothesis, while the second set measures the
details of model differences between hypotheses. We then consider the
case when the signal prior models are unknown, so that the distributions
of interest must be estimated directly from data, showing that the second
set of terms is (asymptotically) negligible and quantifying the loss in
hypothesis separability when the models are completely unknown. We
demonstrate the utility of nonparametric estimation methods for such
problems, providing a general framework for determining and distinguishing
between dependency structures in highly uncertain environments.
Additionally, we develop a machine learning approach for estimating lower
bounds on KL-divergence and mutual information from samples of
high-dimensional random variables for which direct density estimation is
infeasible. We present empirical results in the context of three
prototypical applications: association of signals generated by sources
possessing harmonic behavior, scene correspondence using video imagery,
and detection of coherent behavior among sets of moving objects.
[PDF] | [PS]
|
Message Errors in Belief Propagation |
|
Belief propagation (BP) is an increasingly popular method of performing
approximate inference on arbitrary graphical models. At times, even
further approximations are required, whether from quantization or other
simplified message representations or from stochastic approximation
methods. Introducing such errors into the BP message computations has
the potential to adversely affect the solution obtained. We analyze this
effect with respect to a particular measure of message error, and show
bounds on the accumulation of errors in the system. This leads both to
convergence conditions and error bounds in traditional and approximate BP
message passing.
[PDF] | [PS]
|
Nonparametric Belief Propagation for Sensor Self-Calibration |
|
Automatic self-calibration of ad-hoc sensor networks is a critical need
for their use in military or civilian applications. In general,
self-calibration involves the combination of absolute location information
(e.g. GPS) with relative calibration information (e.g. estimated distance
between sensors) over regions of the network. We formulate the
self-calibration problem as a graphical model, enabling application of
nonparametric belief propagation (NBP), a recent generalization of
particle filtering, for both estimating sensor locations and representing
location uncertainties. NBP has the advantage that it is easily
implemented in a distributed fashion, can represent multi-modal
uncertainty, and admits a wide variety of statistical models. This last
point is particularly appealing in that it can be used to provide
robustness against occasional high-variance (outlier) noise. We
illustrate the performance of NBP using Monte Carlo analysis on an example
network.
[PDF] | [PS]
|
Nonparametric Belief Propagation for Self-Calibration in Sensor Networks |
|
Automatic self-calibration of ad-hoc sensor networks is a critical need
for their use in military or civilian applications. In general,
self-calibration involves the combination of absolute location information
(e.g. GPS) with relative calibration information (e.g. time delay or
received signal strength between sensors) over regions of the network.
Furthermore, it is generally desirable to distribute the computational
burden across the network and minimize the amount of inter-sensor
communication. We demonstrate that the information used for sensor
calibration is fundamentally local with regard to the network topology and
use this observation to reformulate the problem within a graphical model
framework. We then demonstrate the utility of \emph{nonparametric belief
propagation} (NBP), a recent generalization of particle filtering, for
both estimating sensor locations and representing location uncertainties.
NBP has the advantage that it is easily implemented in a distributed
fashion, admits a wide variety of statistical models, and can represent
multi-modal uncertainty. We illustrate the performance of NBP on several
example networks while comparing to a previously published nonlinear least
squares method.
[PDF] | [PS]
|
Nonparametric Belief Propagation and Facial Appearance Estimation |
|
| | |
In many applications of graphical models arising in computer vision, the hidden variables of interest
are most naturally specified by continuous, non-Gaussian distributions. There exist inference algorithms
for discrete approximations to these continuous distributions, but for the high-dimensional variables
typically of interest, discrete inference becomes infeasible. Stochastic methods such as particle
filters provide an appealing alternative. However, existing techniques fail to exploit the rich
structure of the graphical models describing many vision problems. Drawing on ideas from regularized
particle filters and belief propagation (BP), this paper develops a nonparametric belief propagation
(NBP) algorithm applicable to general graphs. Each NBP iteration uses an efficient sampling procedure
to update kernel-based approximations to the true, continuous likelihoods. The algorithm can accomodate
an extremely broad class of potential functions, including nonparametric representations. Thus, NBP
extends particle filtering methods to the more general vision problems that graphical models can
describe. We apply the NBP algorithm to infer component interrelationships in a parts-based face model,
allowing location and reconstruction of occluded features.
[PDF] | [PS]
|
Efficient Multiscale Sampling from Products of Gaussian Mixtures |
|
The problem of approximating the product of several Gaussian mixture
distributions arises in a number of contexts, including the nonparametric
belief propagation (NBP) inference algorithm and the training of
product of experts models.
This paper develops two multiscale algorithms for sampling from a
product of Gaussian mixtures, and compares their performance to existing
methods. The first is a multiscale variant of previously proposed
Monte Carlo techniques, with comparable
theoretical guarantees but improved empirical convergence rates.
The second makes use of approximate kernel density evaluation
methods to construct a fast approximate sampler, which is
guaranteed to sample points to within a tunable parameter $\epsilon$
of their true probability.
We compare both multiscale samplers on a set of computational examples
motivated by NBP, demonstrating significant improvements over existing
methods.
[PDF] | [PS]
|
Hypothesis testing over factorizations for data association |
|
The issue of data association arises frequently in sensor
networks; whenever multiple sensors and sources are present, it
may be necessary to determine which observations from different
sensors correspond to the same target. In highly uncertain
environments, one may need to determine this correspondence
without the benefit of an \emph{a priori} known joint
signal/sensor model. This paper examines the data association
problem as the more general hypothesis test between factorizations
of a single, learned distribution. The optimal test between known
distributions may be decomposed into model-dependent and
statistical dependence terms, quantifying the cost incurred by
model estimation from measurements compared to a test between
known models. We demonstrate how one might evaluate a two-signal
association test efficiently using kernel density estimation
methods to model a wide class of possible distributions, and show
the resulting algorithm's ability to determine correspondence in
uncertain conditions through a series of synthetic examples. We
then describe an extension of this technique to multi-signal
association which can be used to determine correspondence while
avoiding the computationally prohibitive task of evaluating all
hypotheses. Empirical results of the approximate approach are
presented.
[PDF] | [PS]
|
Nonparametric Belief Propagation |
|
In applications of graphical models arising in fields such as computer vision,
the hidden variables of interest are most naturally specified by continuous,
non-Gaussian distributions. However, due to the limitations of existing inference
algorithms, it is often necessary to form coarse, discrete approximations to
such models. In this paper, we develop a nonparametric belief propagation
(NBP) algorithm, which uses stochastic methods to propagate kernel-based approximations
to the true continuous messages. Each NBP message update is based on an efficient
sampling procedure which can accomodate an extremely broad class of potential
functions, allowing easy adaptation to new application areas. We validate our
method using comparisons to continuous BP for Gaussian networks, and an application
to the stereo vision problem.
[PDF] | [PS]
|
Nonparametric Estimators for Online Signature Authentication |
|
We present extensions to our previous work in modelling dynamical processes.
The approach uses an information theoretic criterion for searching over
subspaces of the past observations, combined with a nonparametric density
characterizing its relation to one-step-ahead prediction and uncertainty.
We use this methodology to model handwriting stroke data, specifically
signatures, as a dynamical system and show that it is possible to learn
a model capturing their dynamics for use either in synthesizing realistic
signatures and in discriminating between signatures and forgeries even
though no forgeries have been used in constructing the model.
This novel approach yields promising results even for small training sets.
[PDF] | [PS]
|
Learning Informative Statistics: A Nonparametric Approach |
|
We discuss an information theoretic approach for categorizing and
modeling dynamic processes. The approach can learn a compact and
informative statistic which summarizes past states to predict future
observations. Furthermore, the uncertainty of the prediction is
characterized nonparametrically by a joint density over the learned
statistic and present observation. We discuss the application of the
technique to both noise driven dynamical systems and random
processes sampled from a density which is conditioned on the
past. In the first case we show results in which both the dynamics
of random walk and the statistics of the driving noise are
captured. In the second case we present results in which a
summarizing statistic is learned on noisy random telegraph waves
with differing dependencies on past states. In both cases the
algorithm yields a principled approach for discriminating processes
with differing dynamics and/or dependencies. The method is grounded
in ideas from information theory and nonparametric statistics.
[PDF] | [PS]