Uncertainty modeling in high dimensions


Motivation

The Computational Mathematics research group at the Faculty of Mathematics of the University of Vienna is investigating methods for the reliable modeling of uncertainty in situations where a large (or even infinite) number of parameters is uncertain.

In this case, the data sets available are usually not sufficiently large to allow the estimation of a full high-dimensional probability model. Using simple-minded default distributions (such as Gaussians based on estimated means and covariance matrix) may lead to a severe underestimation of the risk (sometimes exponential in the dimension).

Thus different, more robust approaches are needed. We explore the use of clouds for objective (data-driven) uncertainty and of surprise functions for subjective uncertainty. Both can be integrated with traditional methods and work (in principle) in high dimensions. Box clouds can even be treated rigorously with interval techniques, and yield in certain cases reliable worst case bounds even for a very large number of uncertain parameters.

Current applications include geography (terrain modeling), medicine (radiation therapy planning), and engineering (truss structure analysis, robust space system design).

Extension of the techniques to applications involving partial differential equations are work in progress.


Clouds

Clouds are a concept for uncertainty mediating between the concept of a fuzzy set and that of a probability distribution. A cloud is to a random variable more or less what an interval is to a number.

Clouds give - within the traditional probabilistic framework - a concept for imprecise probability with which quantitative conclusions can be derived from uncertain probabilistic information.

Problems involving box clouds (clouds whose alpha cuts are axiparallel boxes) can be rigorously treated by means of interval techniques, even in fairly high dimensions, in certain cases even in very large (truss structures) or infinite (partial differentail equations) dimension.

Problems involving ellipsoidal clouds, which are able to account for correlated uncertainity, can in principle be treated by ellipsoid arithmetics, although we currently have no practical experience with it in applications.

We currently treat correlated uncertainty by means of sparse polyhedral clouds, which seem to suffer least from the curse of dimensionality.


Surprise

Surprise functions form an alternative approach to fuzzy modeling. The surprise concept is related to the traditional membership function by an antitone transformation. Advantages of the surprise approach include:
1. It has a consistent semantic interpretation.
2. It allows the joint use of quantitative and qualitative knowledge, using simple rules of logic.
3. It is a direct extension of (and allows combination with) the least squares approach to reconciling conflicting approximate numerical data.
4. It is ideally suited to optimization under imprecise or conflicting goals, specified by a combination of soft and hard interval constraints.
5. It gives a straightforward approach to constructing families of functions consistent with fuzzy associative memories as used in fuzzy control, with tuning parameters (reflecting linguistic ambiguity) that can be adapted to available performance data.

Fuzzyland, a tale of wisdom
''Once upon a time, the country of Fuzzyland had a leadership that was famous for ...''


Theory

A. Neumaier, Towards optimization-based error bounds for uncertain PDEs, Slides, 2008
Using tools from functional analysis and global optimization, methods are presented for obtaining, given an approximate solution of a partial differential equation, realistic error bounds for some response functional of the solution.
The method is based on computable bounds for the inverse of linear elliptic operators. Like in the dual weighted residual (DWR) method, our error bounds for response functionals have the quadratic approximation property (so that they are asymptotically optimal), but in contrast to DWR, our bounds are rigorous and also capture the higher order contributions to the error.
Using global optimization techniques, bounds can be found that not only cover the errors in solving the differential equations but also the errors caused by the uncertainty in the parameters. This provides reliable tools for the assessment of uncertainty in the solution of elliptic partial differential equations. Our bounds are independent of the way the approximations are obtained, hence can be used to independently verify the quality of an approximation computed by an arbitrary solver. The bounds not only account for discretization errors but also for other numerical errors introduced through numerical integration and boundary aproximations.
We also discuss how to represent model uncertainty in terms of so-called clouds, which describe the rough shapes of typical samples of various size, without fixing the details of the distribution. Clouds use only information from 1- and 2-dimensional marginal distributions, readily available in practice.

A. Neumaier, Certified error bounds for uncertain elliptic equations, J. Comput. Appl. Math. 218 (2008), 125--136.
Using tools from functional analysis and global optimization, methods are presented for obtaining certificates for rigorous and realistic error bounds on the solution of linear elliptic partial differential equations in arbitrary domains, either in an energy norm, or of key functionals of the solutions, given an approximate solution.
Uncertainty in the parameters specifying the partial differential equations can be taken into account, either in a worst case setting, or given limited probabilistic information in terms of clouds.

A. Neumaier and A. Pownuk, Linear systems with large uncertainties, with applications to truss structures, Reliable Computing 13 (2007), 149-172.
Linear systems whose coefficients have large uncertainties arise routinely in finite element calculations for structures with uncertain geometry, material properties, or loads. However, a true worst case analysis of the influence of such uncertainties was previously possible only for very small systems and uncertainties, or in special cases where the coefficients do not exhibit dependence.
This paper presents a method for computing rigorous bounds on the solution of such systems, with a computable overestimation factor that is frequently quite small. The merits of the new approach are demonstrated by computing realistic bounds for some large, uncertain truss structures, some leading to linear systems with over 5000 variables and over 10000 interval parameters, with excellent bounds for up to about 10% input uncertainty.
Also discussed are some counterexamples for the performance of traditional approximate methods for worst case uncertainty analysis.

A. Neumaier, Uncertainty modeling for robust verifiable design, Slides, 2004.
pdf file (318K)

A. Neumaier, Clouds, fuzzy sets and probability intervals, Reliable Computing 10 (2004), 249-272.
This paper discusses the basic theoretical and numerical properties of clouds, and relate them to histograms, cumulative distribution functions, and likelihood ratios.
We show how to compute nonlinear transformations of clouds, using global optimization and constraint satisfaction techniques. We also show how to compute rigorous enclosures for the expectation of arbitrary functions of random variables, and for probabilities of arbitrary statements involving random variables, even for problems involving more than a few variables.
Finally, we relate clouds to concepts from fuzzy set theory, in particular to the consistent possibility and necessity measures of Jamison and Lodwick.

A. Neumaier, On the structure of clouds, Manuscript (2003).
In this paper, some structural results about clouds are derived. In particular, it is shown that every cloud contains some random variable.

A. Neumaier, Fuzzy modeling in terms of surprise, Fuzzy Sets and Systems 135 (2003), 21-38.
This paper presents an approach to fuzzy modeling based on the concept of surprise.

A. Neumaier, The wrapping effect, ellipsoid arithmetic, stability and confidence regions, Computing Supplementum 9 (1993), 175-190.
The wrapping effect is one of the main reasons that the application of interval arithmetic to the enclosure of dynamical systems is difficult. In this paper the source of wrapping is analyzed algebraically and geometrically. A new method for reducing the wrapping effect is proposed, based on an interval ellipsoid arithmetic.
Applications are given to the verification of stability regions for nonlinear discrete dynamical systems and to the computation of rigorous confidence regions for nonlinear functions of normally distributed random vectors.


Applications

M. Fuchs and A. Neumaier, Autonomous robust design optimization with potential clouds, Int. J. Reliability Safety 3 (2009), 23-34.
The task of autonomous and robust design cannot be regarded as a single task, but consists of two tasks that have to be accomplished concurrently. First, the design should be found autonomously; this indicates the existence of a method which is able to find the optimal design choice automatically. Second, the design should be robust; in other words: the design should be safeguarded against uncertain perturbations. Traditional modeling of uncertainties faces several problems. The lack of knowledge about distributions of uncertain variables or about correlations between uncertain data, respectively, typically leads to underestimation of error probabilities. Moreover, in higher dimensions the numerical computation of the error probabilities is very expensive, if not impossible, even provided the knowledge of the multivariate probability distributions. Based on the clouds formalism we have developed new methodologies to gather all available uncertainty information from expert engineers, process it to a reliable worst-case analysis and finally optimize the design seeking the optimal robust design.

M. Fuchs and A. Neumaier, Handling uncertainty in higher dimensions with potential clouds towards robust design optimization, pp. 376-382 in: Soft Methods for Handling Variability and Imprecision (D. Dubois et al., eds.), Advances in Soft Computing, Vol. 48, Springer 2008.
Robust design optimization methods applied to real life problems face some major difficulties: how to deal with the estimation of probability densities when data are sparse, how to cope with high dimensional problems and how to use valuable information in the form of unformalized expert knowledge.
We introduce the clouds formalism as means to process available uncertainty information reliably, even if limited in amount and possibly lacking a formal description. We provide a worst-case analysis with confidence regions of relevant scenarios which can be involved in an optimization problem formulation for robust design.

M. Fuchs and A. Neumaier, Potential based clouds in robust design optimization, J. Stat. Theory Practice, Special Issue on Imprecision, to appear (2008).
pdf file (970K)
downloading/printing problems?
Robust design optimization methods applied to real life problem face some major difficulties: how to deal with the estimation of probability densities when data are sparse, how to cope with high dimensional problems and how to use valuable information in the form of unformalized expert knowledge.
In this paper we introduce in detail the clouds formalism as means to process available uncertainty information reliably, even if limited in amount and possibly lacking a formal description, to providing a worst-case analysis with confidence regions of relevant scenarios which can be involved in an optimization problem formulation for robust design.

M. Fuchs and A. Neumaier, Uncertainty modeling with clouds in autonomous robust design optimization, pp. 1-22 in: Proc. 3rd Int. Workshop Reliable Engineering Computing, Savannah, Georgia, USA, 2008.
The task of autonomous and robust design cannot be regarded as a single task, but consists of two tasks that have to be accomplished concurrently.
First, the design should be found autonomously; this indicates the existence of a method which is able to find the optimal design choice automatically.
Second, the design should be robust; in other words: the design should be safeguarded against uncertain perturbations. Traditional modeling of uncertainties faces several problems. The lack of knowledge about distributions of uncertain variables or about correlations between uncertain data, respectively, typically leads to underestimation of error probabilities. Moreover, in higher dimensions the numerical computation of the error probabilities is very expensive, if not impossible, even provided the knowledge of the multivariate probability distributions.
Based on the clouds formalism we have developed new methodologies to gather all available uncertainty information from expert engineers, process it to a reliable worst-case analysis and finally optimize the design seeking the optimal robust design.
The new methods are applied to problems for autonomous optimization in robust spacecraft system design at the European Space Agency (ESA).

M. Fuchs, D. Girimonte, D. Izzo, and A. Neumaier, Robust and automated space system design, Chapter (pp. 251-272) in: Robust intelligent systems (A. Schuster, ed.), Springer, 2008.
Over the last few years, much research has been dedicated to the creation of decisions support systems for space system engineers or even for completely automated design methods capturing the reasoning of system experts. However, the problem of taking into account the uncertainties of variables and models defining an optimal and robust spacecraft design have not been tackled effectively yet. This chapter proposes a novel, simple approach based on the clouds formalism to elicit and process the uncertainty information provided by expert designers and to incorporate this information into the automated search for a robust, optimal design.

M. Fuchs, A. Neumaier, and D. Girimonte, Uncertainty modeling in autonomous robust spacecraft system design , Proc. Appl. Math. Mech. 7 (2007), 2060041-2060042.
In the last few years, much research has been dedicated to the development of decisions support systems for the space system engineers or even of completely automated design methods capturing the reasoning of the system experts. However, the problem of taking into account the uncertainties of the variables and models to determine an optimal and robust spacecraft design has not been tackled effectively yet. Based on the clouds formalism we propose a novel approach to process the uncertainty information provided by expert designers and incorporate it into the automated search for a robust optimal design.

A. Neumaier, M. Fuchs, E. Dolejsi, T. Csendes, J. Dombi, B. Bánhelyi, Z. Gera, Application of clouds for modeling uncertainties in robust space system design, Final Report, ARIADNA Study 05/5201, European Space Agency (ESA), 2007.
Ariadna Completed Studies
This report discusses a case study for modeling uncertainties with clouds in a model for space system design, with the goal of determining robust feasible designs for the model.
The problem structure involves all difficulties an optimization problem can have: discrete variables, strong nonlinearities, discontinuities due to branching decisions, multiple objectives, multiple local minima.
The formal modeling of uncertainty by means of clouds, and the robust optimization of a resulting uncertain model was considered. A heuristic approach using surrogate function modeling, corner searches, and discrete line searches was used to solve the robust optimization problem in case of interval uncertainties. This approach works satisfactorily for the model problem for the case of interval uncertainty.
Solving the model problem with uncertainty revealed significant robustness advantages of the approach using uncertainty. The influence on assumed knowledge about additional uncertainty information was illustrated by for a few model choices.


J. Santos, W.A. Lodwick and A. Neumaier, A New Approach to Incorporate Uncertainty in Terrain Modeling, pp. 291-299 in: Geographic Information Science: Second International Conference, GIScience 2002, Proceedings (M. Egenhofer and D. Mark, eds.), Lecture Notes in Computer Science Vol. 2478, Springer, New York 2002.
A method for incorporating uncertainty in terrain modelling by expressing elevations as fuzzy numbers is proposed. Given a finite set of fuzzy elevations representative of the topographic surface in a certain region, we develop methods to construct surfaces that incorporate the uncertainty. The smoothness and continuity conditions of the surface generating method are maintained. Using this approach, we generalize some classic interpolators and compare them qualitatively. Extensions to wider classes of interpolators follow naturally from our approach. A numerical example is presented to illustrate this idea.

W.A. Lodwick, A. Neumaier and F. Newman, Optimization under uncertainity: methods and applications in radiation therapy, Proc. 10th IEEE Int. Conf. Fuzzy Systems, December 2-5, 2001, Melbourne, Australia, pp.1219-1222.
This research focuses on the methods and application of optimization under uncertainty to radiation therapy planning, where it is natural and useful to model the uncertainity of the problem directly. In particular, we present methods of optimization under uncertainty in radiation therapy of tumors and compare their results. Two themes are developed in this study: (1) the modeling of inherent uncertainty of the problems and (2) the application of uncertainty optimization.


C. Elster and A. Neumaier, Screening by conference designs, Biometrika 82 (1995), 589-602.
dvi.gz file (28K), ps.gz file (92K), pdf file (215K), downloading/printing problems?
Screening experiments are addressed to the identification of the relevant variables within some process or experimental outcome potentially depending on a large number of variables. In this paper we introduce a new class of experimental designs called edge designs. These designs are very useful for screening experiments since they allow a model-independent estimate of the set of relevant variables, thus providing more robustness than traditional designs.
We give a bound on the determinant of the information matrix of certain edge designs, and show that a large class of edge designs meeting this bound can be constructed from conference matrices. We also show that the resulting conference designs have an optimal space exploration property which is important as a guard against unexpected nonlinearities. We survey the existence of and constructions for conference matrices, and give, for n<50 variables, explicit such matrices when n is a prime, and references to explicit constructions otherwise.



Slides

A. Neumaier, Towards optimization-based error bounds for uncertain PDEs, Slides, 2008

A. Neumaier, Worst case analysis of mechanical structures by interval methods, Slides, 2005.
pdf file (263K)

A. Neumaier, Uncertainty modeling for robust verifiable design, Slides, 2004.
pdf file (318K)

A. Neumaier and J.-P. Merlet, Constraint satisfaction and global optimization in robotics, Slides, 2002.
pdf file (449K)


CBDO: A Matlab toolbox for Cloud Based Design Optimization
Software for uncertainty modeling by clouds by Martin Fuchs

M. Fuchs, Uncertainty modeling in higher dimensions: Towards robust design optimization, Ph.D. Thesis, Wien 2008.
Modern design problems impose multiple major tasks an engineer has to accomplish. * The design should account for the designated functionalities. * It should be optimal with respect to a given design objective. * Ultimately the design must be safeguarded against uncertain perturbations which should not cause failure of the design. These tasks are united in the problem of robust design optimization giving rise to the development of computational methods for uncertainty modeling and design optimization, simultaneously.
Methods for uncertainty modeling face some fundamental challenges: The computational effort should not exceed certain limitations; unjustified assumptions must be avoided as far as possible. However, the most critical issues concern the handling of incomplete information and of high dimensionality. While the low dimensional case is well studied and several methods exist to handle incomplete information, in higher dimensions there are only very few techniques. Imprecision and lack of sufficient information cause severe difficulties - but the situation is not hopeless.
In this dissertation, it is shown how to transfer the high-dimensional to the one-dimensional case by means of the potential clouds formalism. Using a potential function, this enables a worst-case analysis on confidence regions of relevant scenarios. The confidence regions are weaved into an optimization problem formulation for robust design as safety constraints. Thus an interaction between optimization phase and worst-case analysis is modeled which permits a posteriori adaptive information updating. Finally, we apply our approach in two case studies in 24 and 34 dimensions, respectively.


External links

Interval Computations
Vladik Kreinovich's comprehensive interval archive

Intervals and Probability Distributions
Dan Berleant's comprehensive archive on interval probability

Reliable Engineering Computing
Rafi Muhanna's site at Georgia Tech Savannah, with biannual conferences on reliable engineering.

Weldon Lodwick
who worked with me on applying surprise methods to terrain modeling and radiation therapy planning


Some of My Other Pages

Global Optimization
Interval Methods
FMathL - Formal mathematical language
Regularization
Mathematical Software
Computational Mathematics Links
Mathematics Links
Statistics Links
my home page (http://www.mat.univie.ac.at/~neum)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)