Skip to main content
main-content

Über dieses Buch

Adaptive systems are widely encountered in many applications ranging through adaptive filtering and more generally adaptive signal processing, systems identification and adaptive control, to pattern recognition and machine intelligence: adaptation is now recognised as keystone of "intelligence" within computerised systems. These diverse areas echo the classes of models which conveniently describe each corresponding system. Thus although there can hardly be a "general theory of adaptive systems" encompassing both the modelling task and the design of the adaptation procedure, nevertheless, these diverse issues have a major common component: namely the use of adaptive algorithms, also known as stochastic approximations in the mathematical statistics literature, that is to say the adaptation procedure (once all modelling problems have been resolved). The juxtaposition of these two expressions in the title reflects the ambition of the authors to produce a reference work, both for engineers who use these adaptive algorithms and for probabilists or statisticians who would like to study stochastic approximations in terms of problems arising from real applications. Hence the book is organised in two parts, the first one user-oriented, and the second providing the mathematical foundations to support the practice described in the first part. The book covers the topcis of convergence, convergence rate, permanent adaptation and tracking, change detection, and is illustrated by various realistic applications originating from these areas of applications.

Inhaltsverzeichnis

Frontmatter

Introduction

Introduction

Abstract
The use of adaptive algorithms is now very widespread across such varied applications as system identification, adaptive control, transmission systems, adaptive filtering for signal processing, and several aspects of pattern recognition. Numerous, very different examples of applications are given in the text. The success of adaptive algorithms has inspired an abundance of literature, and more recently a number of significant works such as the books of Ljung and Soderström (1983) and of Goodwin and Sin (1984).
Albert Benveniste, Michel Métivier, Pierre Priouret

Adaptive Algorithms: Applications

Frontmatter

Chapter 1. General Adaptive Algorithm Form

Abstract
In which an example is used to determine a general adaptive algorithm form and to illustrate some of the problems associated with adaptive algorithms.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 2. Convergence: the ODE Method

Abstract
This chapter has a double purpose. Starting from a few informally stated theorems, backed up by appropriate heuristics, we shall present, firstly a guide for an initial coarse analysis (convergence) of the adaptive algorithms, and secondly, a guide to the essentials of algorithm design. The transient phase of the algorithm will be studied briefly.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 3. Rate of Convergence

Abstract
In this chapter, the rate of convergence of the algorithm to its ODE and/or to the desired value θ* is described in more detail. The analysis is again asymptotic.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 4. Tracking Non-Stationary Parameters

Abstract
Here we come to the very heart of the subject, namely an analysis of adaptive algorithms in the context in which they are mainly used (as described in Chapter 1). Throughout this chapter the “true” parameter θ* will be considered to be time-varying.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 5. Sequential Detection; Model Validation

Abstract
In this chapter we continue our analysis of non-stationary systems. After having shown in Chapter 4 how adaptive algorithms may be used to track non-stationary parameters, we shall now investigate ways of proceeding when the underlying system is subject to abrupt change.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 6. Appendices to Part I

Abstract
A linear system or filter is a linear, homogeneous function of time which transforms an input signal (un)n ∈ ℤ to an output signal (yn)n ∈ ℤ thus it may be represented by the convolution
$$ {y_n} = \sum\limits_{{k \in \mathbb{Z}}} {{s_k}{u_{{n - k}}}} $$
(6.1.1)
(6.1.1) where S ≔ (sk)k ∈ ℤ is the impulse response of the system. To avoid convergence problems, we shall assume in this paragraph that the entries (un) are almost always zero, which means that they are zero except for a finite number of instants n.
Albert Benveniste, Michel Métivier, Pierre Priouret

Stochastic Approximations: Theory

Frontmatter

Chapter 1. O.D.E. and Convergence A.S. for an Algorithm with Locally Bounded Moments

Abstract
We now begin the mathematical study of the algorithms considered in Part I. In this first chapter, we shall consider their behaviour (approximation by solution of the “mean” differential equation termed ODE in Part I, and asymptotic analysis) in a framework which is sufficiently general to cover most of the cases introduced in Part I. Applications to the previous cases will be discussed in detail in Chapter 2.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 2. Application to the Examples of Part I

Abstract
The aim of this chapter is to provide criteria under which Assumption (A.4) of the previous chapter is valid. We shall see that the algorithms given in Part I satisfy the general assumptions of Chapter 1; thus the conclusions of the theorems involving approximation by solution of the ODE (Theorems 9 and 14) and of the theorems involving asymptotic approximation (Theorems 13, 14, 17) may be applied to these algorithms. As previously noted in Chapter 1, Subsection 1.1.3, comment c, in verifying that Assumption (A.4) is satisfied, we shall require that the Markov chain with transition probability Πθ is ergodic, and the functions ΠθHθ are regular in θ.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 3. Analysis of the Algorithm in the General Case

Abstract
In the stochastic algorithms studied in Chapter 1 there is a fairly strong condition on the moments of the process (Xn)n≥0 (Assumption (A.5)): for any compact set Q, there exists a constant μq(Q) < ∞ such that for any initial condition (x, a)
$${E_{{x,a}}}\left\{ {I\left( {{\theta_k} \in Q,k \leqslant n} \right)\left( {1 + {{\left| {{X_{{n + 1}}}} \right|}^q}} \right)} \right\} \leqslant {\mu_q}(Q)\left( {1 + {{\left| x \right|}^q}} \right)$$
As soon as the evolution of the process (Xn) depends on the sequence n) (unlike the equaliser discussed in Chapter 2), as in the algorithm with general linear dynamics, there is no reason for (A.5) to be satisfied.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 4. Gaussian Approximations to the Algorithms

Abstract
In this chapter, we shall formally state and prove the “asymptotic normality” properties described in Chapter 3 of Part I.
Albert Benveniste, Michel Métivier, Pierre Priouret

Chapter 5. Appendix to Part II

Abstract
This section was principally intended to provide course support. It was meant to be self-contained and all technical difficulties were to be eliminated through over-realistic assumptions. In fact, the particular instance which we shall describe has already been seen in substance in Example 4 of Subsection 1.1.2 (cf. also 1.1.4), and studied in particular in Subsection 1.10.1. Here once again is the algorithm with its assumptions.
$${\theta_{{n + 1}}} = {\theta_n} + {\gamma_{{n + 1}}}H\left( {{\theta_n},\,{X_{{n + 1}}}} \right)$$
Albert Benveniste, Michel Métivier, Pierre Priouret

Backmatter

Weitere Informationen