Identifiability and complexity of identification of input-output systems.
Glenn Karl Heitman · Deep Blue (University of Michigan) · 1989
This thesis is concerned with characterizing abstractly situations in which system identification is possible and with identification complexity. "Identification", as used in this thesis, means the following: from prior knowledge and observation of outputs produced by a finite number of known inputs it is desired to construct a mathematical model for the unknown system (which belongs to some class of systems) that allows one to predict to within a specified tolerance the system output resulting from an arbitrarily chosen input belonging to a specified class of inputs. "System", as used here, means a function from an input space to an output space. Both exact and approximate identifiability are considered, beginning at a general level with no structure on input and output spaces, then imposing linear structure on output spaces, and finally adding topological structure on input and output spaces. The concept of a determination function is defined and the discussion of identification is transferred to a discussion of determination functions; emphasis is laid on determination functions having the form of an interpolation on the output data. The main result in exact identifiability is that if the output space is linear and the class H of system is a linear space of finite dimension N then there exists a test set of N elements that will exactly identify H. As an important example, it is shown that the identification of finite-dimensional subclass of Volterra polynomials operating on finite-dimensional input spaces can be given by a weakly interpolative determination function. In approximate identifiability, consideration is restricted to uniform approximations. Conditions are given under which any F in the class G can be uniformly approximated to within a specified tolerance by an interpolative determination function. The term size is defined and an argument is made for using size as a measure of identification complexity. Roughly, size is the number of tests required to give an identification. Estimates of size in terms of the metric entropy of the class of systems are obtained by applying a theorem of Lorentz. Finally, some observations are made on the identification of causal systems.