A zero-one law for one-shot system identification
Machine Learning
Summary
The authors study when it's possible to figure out the exact rules governing a system from just one experiment. They focus on systems made from combined building blocks like certain math operations, and find that getting the right answer depends on these building blocks being uniquely recognizable from the experiment data. They show a clear yes-or-no rule: either no single experiment can identify the system, or almost any random experiment can. Their findings also give a way to check if the identified model is trustworthy and help spot when more experiments are needed.
Authors
Nicolas Boullé, Diana Halikias, Samuel E. Otto, Alex Townsend
Abstract
Can a model be identified from one experiment? We study analytic systems that are linearly parameterized by a combination of prescribed dictionary terms, such as partial differential operators and dynamical systems. For a single input-response pair, recovery is possible exactly when the evaluated dictionary terms are linearly independent. We prove a sharp zero-one law: either no input uniquely determines the coefficients, or almost every random input sampled from a nondegenerate Gaussian measure does. This dichotomy reduces one-shot system identification to a question about degenerate inputs and provides an a posteriori certificate for any recovered model. Numerical examples recover dynamical systems, nonlinear partial differential equations, and structured matrix families from single trajectory data, while also detecting when an extra probe is necessary.