Reasoning about Uncertainties in Discrete-Time Dynamical Systems using Polynomial Forms.
Authors: Sriram Sankaranarayanan, Yi Chou, Eric Goubault, Sylvie Putot
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we propose polynomial forms to represent distributions of state variables over time for discrete-time stochastic dynamical systems. This problem arises in a variety of applications in areas ranging from biology to robotics. Our approach allows us to rigorously represent the probability distribution of state variables over time, and provide guaranteed bounds on the expectations, moments and probabilities of tail events involving the state variables. First, we recall ideas from interval arithmetic, and use them to rigorously represent the state variables at time t as a function of the initial state variables and noise symbols that model the random exogenous inputs encountered before time t. Next, we show how concentration of measure inequalities can be employed to prove rigorous bounds on the tail probabilities of these state variables. We demonstrate interesting applications that demonstrate how our approach can be useful in some situations to establish mathematically guaranteed bounds that are of a different nature from those obtained through simulations with pseudo-random numbers. |
| Researcher Affiliation | Academia | Sriram Sankaranarayanan University of Colorado Boulder, USA srirams@colorado.edu Yi Chou University of Colorado Boulder, USA yi.chou@colorado.edu Eric Goubault LIX, CNRS, Ecole Polytechnique, IP-Paris, France goubault@lix.polytechnique.fr Sylvie Putot LIX, CNRS, Ecole Polytechnique, IP-Paris, France putot@lix.polytechnique.fr |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states it uses a "C++-based prototype implementation" and a "python program" for simulations, but it does not provide any link or explicit statement about the public availability of its source code. |
| Open Datasets | Yes | Table 1 shows the results over a set of 8 benchmark problems. taken from various domains such as robotics, physics and biology. Each benchmark involves a discrete-time nonlinear stochastic model along with some queries that take the form of computing expectations of state variables, or bounding probabilities of simple properties. A detailed description of each benchmark and properties are available as part of the appendix. |
| Dataset Splits | No | The paper studies uncertainty propagation in dynamical systems and compares its method with simulations, but it does not use a traditional train/validation/test split for a dataset, nor does it specify any data partitioning for validation purposes. |
| Hardware Specification | No | The paper describes its software implementation but does not provide any specific hardware details used for running the experiments. |
| Software Dependencies | No | Our implementation uses the MPFI library to perform interval arithmetic in order to rigorously bound the errors and guarantee soundness [23]. (No version number for MPFI is given) |
| Experiment Setup | Yes | The polynomial form for y(8) is computed with truncation applied to terms of degree 7 or more, at each step of the computation. The result is a polynomial form over 20 noise symbols of degree 6. (Table 1 lists 'D: degree of polynomial form' for each benchmark). |