Bounding Approaches to System Identification

Frontmatter

1. Overview of the Volume

Abstract

The genesis of this volume was the feeling of its editors that bounding had become an important enough topic, and was attracting enough attention, to require a collection of papers as a broad introduction to the field and a review of current progress. The basic idea of describing plant uncertainty by bounds is as old as toleranced engineering design. State bounding was introduced to the control engineering community in the late 1960s and parameter bounding in the early 1980s, but the subject became prominent only in the late 1980s and early 1990s, through workshops in Turin in 1988,⁽¹⁾ Santa Barbara⁽²⁾ and Sopron⁽³⁾ in 1992, papers and special sessions at conferences such as the 1988 International Association for Mathematics and Computers in Simulation (IMACS) World Congress in Paris, the International Federation of Automatic Control (IFAC) Budapest and Copenhagen identification symposia in 1991 and 1994, the 1991 Institute of Electrical and Electronics Engineers, Inc. Conference on Decision and Control (IEEE CDC) and 1993 IEEE International Symposium on Circuits and Systems (IEEE ISCAS), and increasing exposure in leading control engineering and signal processing journals.^(4,5) The topic is now widespread over a large literature, so this volume is timely.

J. P. Norton

2. Optimal Estimation Theory for Dynamic Systems with Set Membership Uncertainty: An Overview

Abstract

In many problems, such as linear and nonlinear regressions, parameter and state estimation of dynamic systems, state space and time series prediction, interpolation, smoothing, and functions approximation, one has to evaluate some unknown variable using available data. The data are always associated with some uncertainty and it is necessary to evaluate how this uncertainty affects the estimated variables. Typically, the problem is approached assuming a probabilistic description of uncertainty and applying statistical estimation theory. An interesting alternative, referred to as set membership or unknown but bounded (UBB) error description, has been investigated since the late 60s. In this approach, uncertainty is described by an additive noise which is known only to have given integral (typically l ₁ or l ₂) or componentwise (l _∞) bounds. In this chapter the main results of this theory are reviewed, with special attention to the most recent advances obtained in the case of componentwise bounds.

M. Milanese, A. Vicino

3. Solving Linear Problems in the Presence of Bounded Data Perturbations

Abstract

In most computational problems of engineering or numerical analysis available input data (information) is not exact. Perturbations in data may arise for instance from measurement or round-off errors, to mention only these two possible sources. The problem of how inaccuracy in data influences results (for instance, how does it affect a quality of system identification or signal recovery) attracts attention not only for obvious practical reasons, but also motivates a number of theoretical papers. For example, since a long time the case of stochastic errors in information has been studied by statisticians, to mention only the monograph by Wahba,⁽¹⁾ where extensive references to the subject can be found. On the other hand, an active stream of research is based on deterministic assumptions about the noise. Such assumptions are imposed when no appropriate statistical knowledge about the behavior of data errors is available, or simply when statistical analysis is not of interest. The assumption often made in this framework is that errors in information are unknown but bounded. Among many other papers, the bounding approach is discussed in Refs. 2–5.

B. Z. Kacewicz

4. Review and Comparison of Ellipsoidal Bounding Algorithms

Abstract

This chapter is concerned with the problem of robust system identification when no statistical information is available on the noise, but only a bound on its instantaneous values is known. First, various ellipsoidal outer bounding (EOB) algorithms are presented in a unified way. Then, two types of projection algorithms are described, and their link with the EOB algorithms is established. After that, the EOB algorithms are interpreted as robust identification algorithms with a dead zone. The performance of these algorithms is compared through computer simulations where the influence of the choice of the a priori error bound is more particularly studied.

G. Favier, L. V. R. Arruda

5. The Dead Zone in System Identification

Abstract

A prediction error method for parameter estimation in a dynamical system is studied.

$$ \hat \vartheta = \arg {\mkern 1mu} \mathop {\min }\limits_\vartheta \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}\sum\limits_{t = 1}^N {{\text{E}}l\left( {\varepsilon \left( {t,\vartheta } \right)} \right)} $$

where ε are the prediction errors of a linear regression. A quadratic norm l is zero within an interval [−c, c]. This kind of a dead zone (DZ) criterion is very common in robust adaptive control. The following problems are treated in this chapter:

• When is the DZ estimate inconsistent, and what is the set of parameters which minimizes the criterion in the case of inconsistency?
• What happens to the variance of the estimate as the DZ is introduced?
• Does the DZ give a better estimate than least squares (LS) when there are unmodeled deterministic disturbances present?
• What are the relations between identification with a dead zone criterion and so called set membership identification?

K. Forsman, L. Ljung

6. Recursive Estimation Algorithms for Linear Models with Set Membership Error

Abstract

This chapter reviews some of the more recent algorithms for sequential parameter identification in the context of unknown but bounded measurement errors when the model output is linear in the parameters. The properties of the different algorithms are analyzed and compared.

The possibility of evaluating the confidence of the obtained estimates is discussed, particularly information required on the noise structure in order to assess the confidence of the estimates is shown.

Finally, the possibility of using the algorithms for time-varying system identification is considered and the case of uncertain regressors is addressed.

G. Belforte, T. T. Tay

7. Transfer Function Parameter Interval Estimation Using Recursive Least Squares in the Time and Frequency Domains

Abstract

A bank of recursive least squares (RLS) estimators is proposed for the estimation of the uncertainty intervals of the parameters of an equation error model (or RLS model), where the equation error is assumed to lie between a known upper and lower bound. It is shown that the off-line least squares method gives the maximum and minimum parameter values that could have produced the recorded input-output sequence. By modifying the RLS estimator in two ways, it is possible to recursively compute inner and outer bounds of the uncertainty intervals. It is shown that the inner bound is asymptotically tight. It is demonstrated that transfer function parameter intervals can also be estimated, by applying the method to measured frequency function data.

P.-O. Gutman

8. Volume-Optimal Inner and Outer Ellipsoids

Abstract

Approximating a complex set K by a simple geometrical form (such as a polytope, an orthotope, a sphere or an ellipsoid) is often of practical interest. Consider for instance the situation where a vector u has to be chosen so as to satisfy the property

$$ p\left( {u,x} \right) \in T,\forall x \in S, $$

(8.1)

where x and p(.,.) are vector-valued and where T and S are given sets. This can be of interest for instance in robust control, where the controller characterized by u must be designed in order to guarantee some given performances—at least stability—corresponding to a target set T for the process under study, given the information that the model parameters x lie in some specified feasible domain S. The information about S can be derived using the parameter bounding methodology, where one assumes that observations with bounded errors are performed on the process.⁽¹⁾

L. Pronzato, É. Walter

9. Linear Interpolation and Estimation Using Interval Analysis

Abstract

This chapter considers interpolation and curve fitting using generalized polynomials under bounded measurement uncertainties from the point of view of the solution set (not the parameter set). It characterizes and presents the bounding functions for the solution set using interval arithmetic. Numerical algorithms with result verification and corresponding programs for the computation of the bounding functions in given domain are reported. Some examples are presented.

S. M. Markov, E. D. Popova

10. Adaptive Approximation of Uncertainty Sets for Linear Regression Models

Abstract

This chapter deals with the problem of uncertainty evaluation in linear regression models, representing either purely parametric models or mixed parametric/non-parametric (restricted complexity) models. The hypothesis is that disturbance information and prior knowledge on the unmodeled dynamics are available as deterministic bounds. A procedure is proposed for constructing recursively an outer bounding parallelotopic estimate of the parameter uncertainty set, which can be considered as an alternative description to commonly used ellipsoidal approximations. This new type of approximation is motivated by recent developments in the robust control field, where descriptions like hyperrectangular or polytopic domains have led to appealing stability and performance robustness properties of uncertain feedback systems.

A. Vicino, G. Zappa

11. Worst-Case l 1 Identification

Abstract

In this chapter recent results on nonparametric and mixed parametric-nonparametric l ₁ identification are reviewed. These results mainly concern the evaluation of the identification errors, the design of experiment, the selection of the model structure, the construction of optimal and almost optimal algorithms, and the convergence properties of the identification algorithms.

M. Milanese

12. Recursive Robust Minimax Estimation

Abstract

An important problem arising when one wants to estimate the parameters of a model in a bounded-error context is the specification of reliable bounds for this error. In early phases of development, when no prior information is available, one may wish to know the minimum upper bound for the amplitude of the error such that the feasible parameter set is not empty. This corresponds to using a minimax estimator. For models linear in their parameters, we describe a method that takes advantage of a reparametrization in order to recursively obtain the minimax estimates and associated bounds for the error. It also provides the set of parameters compatible with any upper bound of the error. This procedure is extended to output-error models, which are nonlinear in their parameters. Its robustness to outliers is discussed and a technique is described to detect and discard them.

É. Walter, H. Piet-Lahanier

13. Robustness to Outliers of Bounded-Error Estimators and Consequences on Experiment Design

Abstract

If proper precautions are not taken, bounded-error estimators are not robust to outliers, i.e., to data points where the actual error is larger than assumed when specifying the error bounds. The outlier minimal number estimator (OMNE) has been designed to overcome this difficulty and has proved on various examples to be particularly insensitive to outliers. This chapter is devoted to a theoretical study of its robustness. The notion of breakdown point, introduced to quantify the robustness of point estimators, is extended to set-estimators. When the model output is linear in the parameters, OMNE is shown to possess the highest achievable breakdown point. A bound on the bias due to outliers is established and used to define a new policy for optimal experimental design aimed at providing a higher protection against outliers than conventional D-optimal design.

L. Pronzato, É. Walter

14. Ellipsoidal State Estimation for Uncertain Dynamical Systems

Abstract

This chapter gives a concise description of effective solutions to the guaranteed state estimation problems for dynamic systems with uncertain items being unknown but bounded. It indicates a rigorous theory for these problems based on the notion of evolution equations of the “funnel” type which could be further transformed, through exact ellipsoidal representations, into algorithmic procedures that allow effective simulation, particularly with computer graphics. The estimation problem is also interpreted as a problem of tracking a partially known system under incomplete measurements.

Mathematically, the technique described in this chapter is based on a theory of set-valued evolution equations with the ellipsoidal-valued functions formulating approximation of solutions in terms of set-valued calculus.

T. F. Filippova, A. B. Kurzhanski, K. Sugimoto, I. Vályi

15. Set-Valued Estimation of State and Parameter Vectors within Adaptive Control Systems

Abstract

The problem under consideration is that of obtaining simultaneously set-valued estimates for state and parameter vectors of linear (in parameters and in phase coordinates) discrete-time systems under uncontrollable bounded disturbances and given bounded noise in measurements.

There is no other a priori information on disturbances and noise except for they are bounded. It is shown that in the absence of noise in measurements and in the presence only of uncontrollable additive disturbances having an effect on stationary plants being investigated, the problem of obtaining set-valued parameter estimates is equivalent to the problem of determining a set-valued solution of a set of linear algebraic equations under uncertainty in their right-hand sides. With additive measurement noise, set-valued estimation procedure should be changed considerably since in this case one has to determine the whole set of solutions of a set of algebraic equations under uncertainty in coefficients as well as in right-hand sides. The problem of simultaneous estimation of state and parameter vectors can be reduced in the long run to the last-mentioned algebraic one.

The problem of set-valued estimation for nonstationary systems with restricted parameter drift rate is also considered.

V. M. Kuntsevich

16. Limited-Complexity Polyhedric Tracking

Abstract

When the errors between the data and model outputs are affine in the parameter vector θ, the set of all values of θ such that these errors fall within known prior bounds is a polytope (under some identiflability conditions, which can be described exactly and recursively. However, this polytope may turn out to be too complicated for its intended use. In this chapter, an algorithm is presented for recursively computing a limited-complexity approximation guaranteed to contain the exact polytope. Complexity is measured by the number of supporting hyperplanes. The simplest polyhedric description that can thus be obtained is in the form of a simplex, but polyhedra with more faces can be considered as well. A polyhedric algorithm is also described for tracking time-varying parameters, which can accommodate both smooth and infrequent abrupt variations of the parameters. Both algorithms are combined to yield a limited-complexity polyhedric tracker.

H. Piet-Lahanier, É. Walter

17. Parameter-Bounding Algorithms for Linear Errors-in-Variables Models

Abstract

Computational techniques are considered for the errors-in-variables (EIV) problem with bounds specified on the errors in all variables. The significant difference in difficulty in bounding the parameters of a dynamic EIV model, compared with the static case, is explained. Conditions for the feasible set of the parameters to be the union of polytopes are discussed, and a search technique to find the nonlinear bounds for the dynamic EIV problem is described. A simulation example compares EIV and equation-error bounding. Techniques for shortening the computation of EIV parameter bounds, and for finding polytope and ellipsoid approximations, are given.

S. M. Veres, J. P. Norton

18. Errors-in-Variables Models in Parameter Bounding

Abstract

When all observed variables of a model are affected by noise, parameter estimation is known as the errors-in-variables problem. While parameter bounding methods and algorithms have been extensively developed in the case of exactly known regressor variables, little attention has been paid to the bounded errors-in-variables problem. This chapter gives a formal proof of a previous result on the description of the feasible parameter region for models linear in the parameters in the presence of bounded errors in all variables. Topological features of the feasible parameter region, such as convexity and connectedness, are also discussed. Finally, approximate parameter uncertainty intervals are derived for ARMAX models when all the observed variables are affected by bounded noise. For an example involving extensive simulations, central estimates obtained by means of the bounded errors-in-variables approach and least squares estimates are computed and compared.

V. Cerone

19. Identification of Linear Objects with Bounded Disturbances in Both Input and Output Channels

Abstract

The problem under consideration is to identify an object that is described by a linear equation

$$ y = {a_1}{x_1} + \ldots + {a_n}{x_n}, $$

(19.1)

where x ₁..., x _n are input scalar signals, y is an output scalar signal, and a ₁,..., a _n are the model coefficients, which must be estimated.

Y. A. Merkuryev

20. Identification of Nonlinear State-Space Models by Deterministic Search

Abstract

An economical technique for tracing the boundary of a two-dimensional cross section of the feasible parameter set for a model with bounded output error is described. It allows exploration of a boundary which is not piecewise linear and may not be convex. First a point on the boundary is found, then a line search is executed, adapting to local behavior of the boundary. Resolution may be traded against computational speed by choice of the search parameters.

J. P. Norton, S. M. Veres

21. Robust Identification and Prediction for Nonlinear State-Space Models with Bounded Output Error

Abstract

An important application of mathematical models is prediction of the future system behavior. Due to incomplete system knowledge as well as errors in the observations obtained from the “real” system, these models will always contain some uncertainty. Hence, for the credibility of model predictions, it is desirable to quantify the prediction uncertainty. From this point of view, a single future trajectory suggest an unrealistic reliability.

K. J. Keesman

22. Estimation Theory for Nonlinear Models and Set Membership Uncertainty

Abstract

This chapter studies the problem of estimating a given function of a vector of unknowns, called the problem element, by using measurements depending non-linearly on the problem element and affected by unknown but bounded noise. Assuming that both the solution sought and the measurements depend polynomially on the unknown problem element, a method is given to compute the axis-aligned box of minimal volume containing the feasible solution set, i.e., the set of all unknowns consistent with the actual measurements and the given bound on the noise. The center of this box is a point estimate of the solution, which enjoys useful optimality properties. The sides of the box represent the intervals of possible variation of the estimates. Important problems, like parameter estimation of exponential models, time series prediction with ARMA models and parameter estimates of discrete time state space models, can be formalized and solved by using the developed theory.

M. Milanese, A. Vicino

23. Guaranteed Nonlinear Set Estimation via Interval Analysis

Abstract

Many methods have been developed for solving problems arising in mathematics and physics which are formulated in such a way as to require a point solution (e.g., a real number or vector). However, because of the uncertainty attached to the data and numerical errors induced by the finite-word-length representation in the computer, these methods are generally not appropriate to accurately characterize the uncertainty with which the solution is obtained. It is then difficult to assess the validity of the result.

L. Jaulin, É. Walter

24. Adaptive Control of Systems Subjected to Bounded Disturbances

Abstract

In practical adaptive control systems which use identification procedures, the effect of disturbances on the system behavior is the important factor. The above effect is investigated from statistical considerations.⁽¹⁾ This approach requires some knowledge of disturbance statistics. However, in various control applications, the assumptions regarding the disturbance statistics may be invalid. In these cases, the statistical approach is unsuitable. Meanwhile, in most cases the available a priori information about the disturbance is given not in statistical terms but as bounds on its absolute value. In the cases mentioned, the bounding approaches are appropriate. These approaches are developed in the identification and control theory.^(2–6)

L. S. Zhiteckij

25. Predictive Self-Tuning Control by Parameter Bounding and Worst-Case Design

Abstract

The computation of bounds on the parameters of a plant model allows worst-case control synthesis, taking account of the uncertainty in the model. This chapter introduces such a control scheme: predictive bounding control. The scheme contrasts with existing self-tuning control methods which base control synthesis on a nominal plant model. Parameter bounding also permits detection of abrupt plant changes, and adaptive tracking of time-varying plant characteristics by suitable choice of bounds on plant-model output error and plant-parameter increments. Estimation and control are closely integrated, and the control computation can compromise between reducing the model uncertainty and reducing predicted output error. Simulation examples show the excellent performance of predictive bounding control.

S. M. Veres, J. P. Norton

26. System Identification for H ∞-Robust Control Design

Abstract

In conventional identification techniques a model is proposed which is supposed to be capable of representing the process behavior under study. Parameters are then tuned such that the model outputs correspond according to some criterion for the dominant part of a measured data set. Deviations are thought to be concentrated in some error source in the model, such as output error, prediction error, equation error, and so forth. This artificial error source explains all disturbances acting on the process as well as for all model deviations from the real dynamic behavior of the process. Furthermore, stochastic assumptions have to be proposed concerning the errors leading to the criterion and as a result a “best” model is produced together with some stochastically based range for the parameters and/or dynamic behavior.

T. J. J. van den Boom, A. A. H. Damen

27. Estimation of Mobile Robot Localization: Geometric Approaches

Abstract

The real device is shown in Fig. 27.1. It is a cart-like wheeled vehicle sketched on Fig. 27.2. It is capable to perform planar displacements and its configuration q (Eq. 27.1) is composed of the 2-D coordinates (x _c y _c ) of a characteristic point together with the orientation θ defined in a world coordinate W (Fig. 27.2).

D. Meizel, A. Preciado-Ruiz, E. Halbwachs

28. Improved Image Compression Using Bounded-Error Parameter Estimation Concepts

Abstract

Classical approaches to parameter estimation yield point estimates of parameters by optimizing some criterion of fit. In contrast, bounded error parameter estimation (BEPE) methods provide sets of parameters which are consistent with the model structure, observation record, and uncertainty constraints. In general, no knowledge of the statistics of the model or observation uncertainty is assumed. The uncertainty, however, is assumed to be constrained in some manner, e.g., with bounded energy or bounded magnitude.⁽¹⁾ BEPE methods seem more appropriate than classical techniques in several situations. If the actual system is only loosely modeled by the chosen model, it appears more reasonable to attempt to optimize the model so as to bound the model mismatch error, rather than to do classical parameter estimation with erroneous assumptions on the statistics of the model mismatch error. In other cases, the statistics of the observation uncertainty may not be known and BEPE techniques may be effective.

A. K. Rao

29. Applications of OBE Algorithms to Speech Processing

Abstract

Many algorithms for identification of speech models are directly or indirectly based on linear predictive coding (LPC) analysis.^† LPC analysis is tantamount to identification of an autoregressive (AR) model using short-term batch processing of the observations.⁽¹⁾ The LPC model, therefore, is a special case of the discrete-time linear-in-parameters models treated in foregoing chapters. Accordingly, many speech processing tasks represent natural domains for applying bounded-error methods. This chapter discusses the fundamental principles requisite to application of optimal-bounded-ellipsoid (OBE) processing to problems in speech analysis, recognition and coding. The focus is the general problem of LPC identification of speech using OBE methods, including the significant issue of tracking the time-varying parameters of this very dynamic signal. Potential applications of this work in specific speech-processing endeavors include:

1.

General modeling and analysis by predictive methods for spectral (formant) estimation, pitch detection, glottal waveform deconvolution, and pathology detection.⁽¹⁾

 

2.

Automated recognition of speech in which LPC parameters, or related parameters to which LPC coefficients are converted, are used as features in classifying phones, words, or complete messages in isolated utterances or continuous speech.

 

3.

Speaker recognition, or speaker verification, in which the speaker’s identity is determined or verified, respectively, through parametric feature analysis.

 

4.

Compression and synthesis of speech in which LPC parameters are used in strategies which remove redundancy in the acoustic waveform as a means of bandwidth compression or improving storage requirements. Similarly, spectral compression based on LPC analysis can be used for translation of the spectrum for hearing aids.

 

John R. Deller Jr.

30. Robust Performances Control Design for a High Accuracy Calibration Device

Abstract

This chapter presents a case study of robust performances control design. The physical plant under examination consists of a platform for calibration of high accuracy accelerometers. It has to assume the properties of an inertial body, despite the vibrations coming from the surrounding ground. Plant modeling and parameter estimation, control system design and robustness analysis of the designed controllers are described and discussed. Besides a simplified model of the plant (the nominal model) perturbations are also considered to take into account parametric and dynamic uncertainties. The procedure followed for estimating model parameters, based on an unknown but bounded approach, is illustrated, and uncertainty intervals of parameter estimates are provided. Bounds of unstructured uncertainty are also derived from results of simulations to evaluate the main effects of the unmodeled dynamics.

The design has been carried on through iterative steps of “nominal” design and robustness analysis. The design has been performed through H _∞ synthesis, based on the nominal model and taking into account the main performance specifications required for the present case study, i.e. stability, disturbance attenuation and command power limitation. The robustness analysis has been performed using recent techniques able to deal with frequency domain specifications and with mixed non-linear parametric and dynamic perturbation, as required in the present case study.

M. Milanese, G. Fiorio, S. Malan

Backmatter