1. Introduction

Presented with an array of ingenious techniques for estimating features of non-linear dynamics from observations of time series (Abarbanel Reference Abarbanel1996; Broomhead and King Reference Broomhead and King1986; Fraser Reference Fraser1989; Grassberger and Procaccia Reference Grassberger and Procaccia1983; Kaplan and Glass Reference Kaplan and Glass1992; Packard et al. Reference Packard, Crutchfield, Farmer and Shaw1980; Sauer et al. Reference Sauer Tim and Casdagli1991), philosophers of science have focused on an issue largely internal to their subject, the role of models in confirmation. According to a tradition beginning at least with Pierre Duhem, theories alone imply nothing about what is or can be observed in the laboratory or observatory. To predict or explain any data, theories must be supplemented with something. A long tradition refers to the supplement as auxiliary hypotheses, but it is more fashionable nowadays to call the combination—the theory supplemented or amended with auxiliaries—a model. Models are supposed to be confirmed or disconfirmed directly by observations, while theories derive their confirmation, if that is what they have, only from the confirmation of models with which they are associated (Cartwright Reference Cartwright1983). This thesis would be more interesting were there some separate, non-circular characterization that enabled us to identify a system of claims, or a practice including such a system, as a theory, and another, distinct, characterization that did likewise for models, but there is only a list of examples: Newtonian dynamics, relativity, quantum electrodynamics, thermodynamics, and statistical mechanics are theories, the Bohr atom, the liquid drop model of the nucleus, and ideal gases are models. Nor is there some general account of how confirmation by particular observations is parceled out among the separate parts of the content of a model, or to the theory that the model mediates with the data.Footnote ¹ There is, however, the following procedural account of how data bear on a theory (Laymon Reference Laymon, Achinstein and Hannaway1985, Reference Laymon1989; Redhead Reference Redhead1980; Wimsatt Reference Wimsatt, Nitecki and Hoffman1987): it is known independently that various models are, in various respects, false, and that various measurements are inexact. As the models are made more realistic by modifying auxiliary hypotheses, and as technological improvements make measurements more exact, all the while keeping the theory without modification, if the models and data increasingly agree then the theory is confirmed.

Two recent papers provide complementary arguments that methods for inference to system structure from data on non-linear dynamics contradict this procedural picture of the role of models. According to Rueger and Sharp (Reference Rueger and Sharp1996), techniques of inference developed for non-linear dynamics refute the claim that only models, and not theories, are directly confronted by data. Features of the dynamics, the attractors or the Lyapunov exponents, for example, and even whether the system is or is not chaotic, are inferred directly from the data without the intervention of auxiliary hypotheses or a model. According to Koperski (Reference Koperski1998), a characteristic of chaotic non-linear systems, their sensitive dependence on initial conditions, is inconsistent with the procedural account of the confirmation of theories. As measurements of initial conditions successively become more exact, and the difference narrows between actual initial conditions at a time and the initial conditions estimated at that time from measurements, the observed sequences of states subsequent to the initial states do not converge uniformly to a single trajectory.

Each of these arguments seems to us opaque in some important respect. Rueger and Sharp presuppose that traditional ideas about confirmation for dynamical systems assume that a model will be numerically solved for a predictive time series, and the predictions will be compared to the empirical time series. They argue that sensitive dependence on initial conditions bars this kind of point-by-point comparison of models with data in chaotic dynamics. In techniques such as those described in Abarbanel (Reference Abarbanel1996) and the other authors mentioned above, this problem is sidestepped by using invariants of the motion (calculated from the empirical data) in place of the time series. These invariants are then, they claim, compared directly to theories without the use of mediating models.

Rueger and Sharp illustrate their point with the Belousov-Zhabotinsky reaction. In this case the “theory” is the one-dimensional map that describes the Poincaré section of the attractor for the reaction, and can be compared to data retrieved through the process of embedding.

They correctly claim that, rather than point-by-point comparisons of data to numerical simulations, scientists instead regularly compare theoretical invariants of the motion to those calculated from the data. One example of such an invariant is the Lyapunov exponent. The soundness of the procedure, and thus of Rueger and Sharp's argument, depends on whether, even for a one-dimensional system one can actually reliably infer the value of invariants such as the Lyapunov exponent from the data. They do not address the question.

Koperski offers a more detailed argument for a related conclusion. He analyzes three particular models of confirmation, and argues that unavoidable errors in measurement, coupled with round-off error in numerical solutions of mathematical equations, preclude confirmation of mathematical models point-by-point with data from chaotic systems. Koperski then goes on to claim that the problem lies in the traditional “top-down” approach to modeling, and that it can be solved by considering a different kind of model in non-linear dynamics, the reconstructed phase space. Koperski does not consider the kind of confirmation that Rueger and Sharp advocate, and that is practiced by researchers in the field—comparing invariant quantities, such as the Lyapunov exponent, calculated from a theory of the dynamics of the system, with estimated values of those invariants obtained through the reconstruction of the attractor in phase space.

The arguments of these essays seem to presume answers to important issues about inference from data to non-linear dynamics. Rueger and Sharp seem to assume that features of dynamics can be inferred from time series observations alone. Koperski seems to imply that if observations are inexact, features of dynamics cannot be inferred from time series observations alone. We take these claims as issues, issues that are of interest outside of the particular debates that generated them, and that need not be embedded in vague claims about models and confirmation.

From Rueger and Sharp, we extract the following set of issues:

1. 1. From exact observations of time series of a dynamical quantity, what features of its dynamics can be reliably inferred?

And from Koperski, the following set of issues:

1. 2. From inexact observations of time series of a dynamical quantity, what features of its dynamics can be reliably inferred?

These questions are themselves vague, specifically as to what, if any, background assumptions are to be made, and as to what is meant by “reliable inference.” In what follows we note the applicability of several, relevant, precise senses of reliability, and characterize the answers to the first of these questions for one-dimensional systems according to the various senses of reliability considered. Corresponding answers to the second of these questions depend on an open problem about Lyapunov estimators. Our broader aim is to give a very simple illustration of how the formal learning theoretic framework can illuminate and clarify intuitions in methodological discussions, transforming ill-structured debates into well posed mathematical questions (for such applications see Glymour Reference Glymour1994 and Schulte Reference Schulte2000).

The formalisms of non-linear dynamics and of techniques for their analysis are reviewed at length in the papers cited and in many other sources (Abarbanel Reference Abarbanel1996; Broomhead and King Reference Broomhead and King1986; Fraser Reference Fraser1989; Grassberger and Procaccia Reference Grassberger and Procaccia1983; Kaplan and Glass Reference Kaplan and Glass1992; Packard et al. Reference Packard, Crutchfield, Farmer and Shaw1980; Sauer et al. Reference Sauer Tim and Casdagli1991), and we will give no more background than is essential for our examples. The framework of formal learning theory is developed in several monographs (e.g., Osherson, et al. Reference Osherson, Stob and Weinstein1986; Kelly Reference Kelly1996), and we will be comparably succinct about it as well. For ease of reading, all proofs are postponed to the appendix.

2. Chaotic Systems And One-Dimensional Dynamics

We will consider one dimensional maps:

where x is an observed real variable. As Koperski correctly points out, there is not yet consensus on one precise definition of chaos; in fact different definitions may be used for different purposes. However, there does seem to be agreement that chaos requires, at least, sensitive dependence on initial conditions (SDIC). In the chaos literature, SDIC is generally taken to be quantified by the Lyapunov exponent of the system (or the largest Lyapunov exponent in the case of multi-dimensional systems). A positive Lyapunov exponent indicates SDIC (and the more positive, the greater the sensitivity), while a zero or negative exponent indicates no sensitivity.

The Lyapunov exponent for a data stream from a one-dimensional system is given by:

where x_i is the ith iterated value of the function f, f′ is the first derivative of the function f at the point x_i, λ is the Lyapunov exponent evaluated at the point x_i, and n is the number of points used to calculate the Lyapunov exponent thus far. Empirically, the Lyapunov exponent, calculated with a finite number of data points, n, is estimated by:

where

where δ_i(n) is the Euclidean distance between x_i and its nearest neighbor after n data points. Thus, we consider the following property:

3. The Formal Learning Framework And Senses Of Reliably Correct Inference

For our purposes, a data stream d is an infinite sequence of real numbers not necessarily all distinct. A hypothesis determines, or for our purposes is the same as, a set of data streams. An inference function for a data stream is a partial function from the set of initial segments of the data stream to [0,1]. An inference function for a set W of data streams is a partial function from the set of all initial segments of all data streams in W to the real interval [0,1].

Let W be a set of data streams, H a hypothesis, and F an inference function for W. We define the following senses of reliability.

We say that H is verifiable in the limit in W if there exists an inference function that verifies H in the limit in W. Analogous definitions apply in all of the cases above. An example of a hypotheses that is verifiable in the limit is: “There is a key that opens every door”, if we assume that there are an infinite number of doors and an infinite number of keys. We can see that this hypothesis is verifiable in the limit by considering its investigation. First, we pick a key, and try it in a door. Whether the door opens constitutes a point in the data stream. If it does not open the door, our inference function equals 0, and we pick another key. If the key does open the door, our inference function equals 1, and we move on to check that key in all the other doors. If the hypothesis is correct, we will eventually find the right key, and there will be only a finite segment of the data stream in which the inference function is zero, because the key will keep opening doors. If the hypothesis is incorrect, there will be an infinity of finite segments of the data stream for which the inference function is zero, because, for every key, we will eventually find a door that it did not open.

A pair 〈W, H〉 is a problem, and associated with each notion of reliable inference there is a class of problems satisfying that criterion. The intersection of the class of problems refutable with certainty and the class verifiable with certainty is the class of problems decidable with certainty; the class of problems verifiable with certainty is included in the class of problems verifiable in the limit, and so on. Kelly (Reference Kelly1996) gives a detailed characterization of the hierarchy of discovery problems of these and other kinds.

There is a connection between problems that are decidable in the limit or gradually decidable and the more popular Bayesian notion of convergence to the truth. A broad class of problems is decidable in the limit and gradually decidable if and only if there is a prior probability distribution over the hypothesis and the initial segments such that for all data streams in W the sequence of posterior distributions converges to 1 if the hypothesis is true in that data stream and to 0 otherwise.

4. Reliable Inferences About Chaos In One-Dimensional Systems With Exact Observations

The sense in which, as defined above, sensitive dependence on initial conditions can be reliably learned from time series of exact measurements of a state variable is as follows:

This result is the best possible, i.e., Positive Lyapunov Exponent is not verifiable with certainty and is not refutable in the limit (proofs of these bounds are not included here but are discussed in Harrell Reference Harrell2000).

To prove the claim we need first to determine the conditions under which estimates of the Lyapunov exponent converge to the true Lyapunov exponent. In the case of exact observations, these conditions are relatively weak (this proof is rather lengthy, and so will not be included here, but it is given in Harrell Reference Harrell2000). Second, we must prove that, under these conditions, there is a method that verifies the hypothesis in the limit, and also a (possibly different) method that refutes the hypothesis gradually. Kelly (Reference Kelly1996) gives a general proof that if a hypothesis is verifiable in the limit, then it is gradually refutable (see Proposition 3.13), so strictly speaking, we are only burdened with proving that the Positive Lyapunov Exponent hypothesis is verifiable in the limit. In the appendix we provide direct proofs of verifiability in the limit and of gradual refutability.

If we assume that the observations are subject to some error, the proof in the appendix shows that Positive Lyapunov Exponent hypothesis has the same verifiability and refutability features as it does with perfectly precise observations if estimates of the Lyapunov exponent converge to the true Lyapunov exponent. This assumption, which is commonly made by researchers in chaotic dynamics (see, e.g. Abarbanel Reference Abarbanel1996), may very well be false, but, to our knowledge, there is no characterization in the literature of conditions under which it is true or conditions under which it is false.

5. Conclusion

Rueger and Sharp claim inference to the structure of non-linear dynamical systems proceeds without the intervention of “models.” But the sense of “inference” is ambiguous. An “inference” to structure can be made with no data at all if nothing is required about the reliability of the inference procedure. When reliability is required, however, their claim fragments into several claims, and, depending on the sense of “reliability,” a variety of answers are obtained, as in our example. Koperski claims that with inexact data an approximation procedure does not converge to the truth. That is correct for some dynamical quantities, but for the Lyapunov exponent there appears to be no established answer.

Our simple results are only illustrative. We have left open questions about many other properties of discrete non-linear dynamical systems, and about multi-dimensional systems, and we have not touched on continuous systems at all. Nor have we considered reliability questions that arise when inferences are to be made to unobserved dynamical quantities through embedding theorems. We wish that such investigations would replace, or at least substantially supplement, philosophical discussions of confirmation in chaotic systems, discussions often premised, we believe, on unarticulated intuitions about learning in the limit which may sometimes be correct and sometimes not, but which are amenable to demonstration or refutation.