4 ms·

Could someone here enlighten me what a nonlinear system in this context is, or rather what it is not? What I mean is: If I give you an arbitrary black box that

Could someone here enlighten me what a nonlinear system in this context is, or rather what it is not? What I mean is: If I give you an arbitrary black box that computes outputs based on inputs I could make it arbitrarily hard to find any relationship whatsoever between input and output. Say I take the input, an internal hidden variable of some kilobytes and return some hash of the two. There's (nearly) certainly no way to learn anything meaningful about my internal variable by just observing input and output. So what's the limitation in the context of this paper? Differentiable functions?

doppioandante 5y ago
The term nonlinear system here must be understood from the point of view of control engineering. In control theory, a system is usually described in a white-box manner by a differential equation and an observation equation: dx/dt = f(x, u, t) y = h(x, u, t) x is a vector of the so called state-variables, while y is the output vectors which usually represents what we can measure about the system, u is a function which represents the inputs to the system, and t is the time. A very useful and simple modeling tool is that of linear time-invariant systems (LTI), where the above equations are specifically dx/dt = Ax+Bu y = Cx+Du where (A,B,C,D) are matrices. Every bit of theory is known about LTI systems: how to control them, global properties, etc. Nonlinear systems are, loosely speaking, dynamical systems which are not linear in the above sense. Depending on the specific nonlinear system form, much less can be said than the linear system case.
- choeger 5y ago
  Thanks. So we are talking about ODE in state-space form, right? So in my example, if x was a (largish) time constant integer (f(x,u,t) = 0) and the observation function was h(x,u,t) = sha256sum(x,u) What could a control theorist tell about that (nonlinear) system?
  - 317070 5y ago
    sha256sum is not a continuous function. These functions should be continuous. Usually there are light restrictions on these functions to avoid what you are trying to do. Lyapunov bounded, C2 continuous, ... Control engineers could use a piecewise approximation of an observer or controller, or use non-linear methods (like reinforcement learning, model predictive control, LQR, ...)
    - choeger 5y ago
      Thanks. That makes a lot of sense, indeed.
  - dataflow 5y ago
    ...nothing? Why makes you think they should be able to say anything? I'm so perplexed by your question... you seem already quite familiar with ordinary differential equations and state-space models... which are concerned with the observability of continuous-time models, right? And yet you pose a counterexample using a cryptographic hash function, which is a (very!) discrete function, and one that is specifically designed to be unobservable? Isn't that even more jarring than asking physicists to predict human life expectancy from the Standard Model? What makes you think the answer might be anything other than "no prediction"...?
    - choeger 5y ago
      I did not expect a positive answer here. I wanted to know what the implicit constraints are so I chose an example that was obviously impossible. I worked across domains for a while (CS, simulation, mathematics) and one thing that was really problematic was that people from one domain used a lot of implicit constraints that the other partners weren't aware of. This then led to incorrect software and weird simulation results.
    - spenczar5 5y ago
      Sometimes someone asks a question in earnest. They really don’t know, and want to know more. They aren’t trying to score points or win a debate or strike a rhetorical victory. I had just the same question as the commenter. I just don’t know much about this topic, and think that this question and its answers really helped my understanding.
  - jamessb 5y ago
    I think you might also be confused about the difference between system identification and observability. The problem of constructing a model of a system's dynamics is system identification [0]. A state observer [1] tries to determine the internal state of the system given measurements of a system's inputs outputs and a model of its dynamics. The system is observable [2] if the state observer can fully reconstruct the internal state. One motivation for checking whether a system is observable is to determine whether a given combination of sensors (corresponding to a particular set of outputs) is sufficient to for the internal state to be determined, or whether more should be added. The state observer of a process is another dynamical system whose inputs are the process input and process output, and whose output is an estimate of the process' internal state; if the system is observable, then this estimate converges to the true state over time. This whole formalism doesn't really apply to something like your example, which has no dynamics. If you have the code for the hash function in your example, then determining the values that its internal variables take for an arbitrary input is trivial; if you don't then it is very difficult. In either case, your problem is different to the problem of observabilty in control theory. [0]: https://en.wikipedia.org/wiki/System_identification https://en.wikipedia.org/wiki/System_identification [1]: https://en.wikipedia.org/wiki/State_observer https://en.wikipedia.org/wiki/State_observer [2]: https://en.wikipedia.org/wiki/Observability https://en.wikipedia.org/wiki/Observability
    - goldbattle 5y ago
      Observability is interested in asking if you, as an external observer, are given a set of inputs and measurements are you able to recover the initial state of the system? While identiability typically is just a person running an experiment and saying "hey look these state values are unable to be recovered / estimated when I ran the algorithm". This is why I never understood why this analysis was very helpful as it isn't very useful outside of the specific experiment / motion / inputs used. For example from [1] has these reasonably straightforward definitions. Observability is a structural property of a control system dened as the possibility to deduce the state of the system from observing its input-output behaviour Identiability is the possibility to identify the parameters of a control system from its input-output behaviour. Parameter identiability is a special case of the observability problem. [1] http://www.math.chalmers.se/Math/Research/Preprints/Doctoral/2007/3.pdf http://www.math.chalmers.se/Math/Research/Preprints/Doctoral...
justincormack 5y ago
Sibling comment is very helpful in terms of what linear is. In terms of the abstract, your system isn't "observable" as even with all the inputs and outputs in a given time period, and knowledge of the hash functions, you still won't be able to work out the internal state. If you had all the inputs since it started you could (assuming it was deterministic and so on) but thats "less observable" in some sense as you need potentially unbounded information. While linear systems are tractable, some nonlinear systems could be tractable too. Software is interesting from this point of view as while its clearly nonlinear, we can create mechanisms to expose otherwise hidden internal state and to control it, although there is generally such a large number of internal states that this is difficult.

doppioandante 5y ago

The term nonlinear system here must be understood from the point of view of control engineering. In control theory, a system is usually described in a white-box manner by a differential equation and an observation equation: dx/dt = f(x, u, t) y = h(x, u, t) x is a vector of the so called state-variables, while y is the output vectors which usually represents what we can measure about the system, u is a function which represents the inputs to the system, and t is the time. A very useful and simple modeling tool is that of linear time-invariant systems (LTI), where the above equations are specifically dx/dt = Ax+Bu y = Cx+Du where (A,B,C,D) are matrices. Every bit of theory is known about LTI systems: how to control them, global properties, etc. Nonlinear systems are, loosely speaking, dynamical systems which are not linear in the above sense. Depending on the specific nonlinear system form, much less can be said than the linear system case.

choeger 5y ago
Thanks. So we are talking about ODE in state-space form, right? So in my example, if x was a (largish) time constant integer (f(x,u,t) = 0) and the observation function was h(x,u,t) = sha256sum(x,u) What could a control theorist tell about that (nonlinear) system?
- 317070 5y ago
  sha256sum is not a continuous function. These functions should be continuous. Usually there are light restrictions on these functions to avoid what you are trying to do. Lyapunov bounded, C2 continuous, ... Control engineers could use a piecewise approximation of an observer or controller, or use non-linear methods (like reinforcement learning, model predictive control, LQR, ...)
  - choeger 5y ago
    Thanks. That makes a lot of sense, indeed.
- dataflow 5y ago
  ...nothing? Why makes you think they should be able to say anything? I'm so perplexed by your question... you seem already quite familiar with ordinary differential equations and state-space models... which are concerned with the observability of continuous-time models, right? And yet you pose a counterexample using a cryptographic hash function, which is a (very!) discrete function, and one that is specifically designed to be unobservable? Isn't that even more jarring than asking physicists to predict human life expectancy from the Standard Model? What makes you think the answer might be anything other than "no prediction"...?
  - choeger 5y ago
    I did not expect a positive answer here. I wanted to know what the implicit constraints are so I chose an example that was obviously impossible. I worked across domains for a while (CS, simulation, mathematics) and one thing that was really problematic was that people from one domain used a lot of implicit constraints that the other partners weren't aware of. This then led to incorrect software and weird simulation results.
  - spenczar5 5y ago
    Sometimes someone asks a question in earnest. They really don’t know, and want to know more. They aren’t trying to score points or win a debate or strike a rhetorical victory. I had just the same question as the commenter. I just don’t know much about this topic, and think that this question and its answers really helped my understanding.
- jamessb 5y ago
  I think you might also be confused about the difference between system identification and observability. The problem of constructing a model of a system's dynamics is system identification [0]. A state observer [1] tries to determine the internal state of the system given measurements of a system's inputs outputs and a model of its dynamics. The system is observable [2] if the state observer can fully reconstruct the internal state. One motivation for checking whether a system is observable is to determine whether a given combination of sensors (corresponding to a particular set of outputs) is sufficient to for the internal state to be determined, or whether more should be added. The state observer of a process is another dynamical system whose inputs are the process input and process output, and whose output is an estimate of the process' internal state; if the system is observable, then this estimate converges to the true state over time. This whole formalism doesn't really apply to something like your example, which has no dynamics. If you have the code for the hash function in your example, then determining the values that its internal variables take for an arbitrary input is trivial; if you don't then it is very difficult. In either case, your problem is different to the problem of observabilty in control theory. [0]: https://en.wikipedia.org/wiki/System_identification https://en.wikipedia.org/wiki/System_identification [1]: https://en.wikipedia.org/wiki/State_observer https://en.wikipedia.org/wiki/State_observer [2]: https://en.wikipedia.org/wiki/Observability https://en.wikipedia.org/wiki/Observability
  - goldbattle 5y ago
    Observability is interested in asking if you, as an external observer, are given a set of inputs and measurements are you able to recover the initial state of the system? While identiability typically is just a person running an experiment and saying "hey look these state values are unable to be recovered / estimated when I ran the algorithm". This is why I never understood why this analysis was very helpful as it isn't very useful outside of the specific experiment / motion / inputs used. For example from [1] has these reasonably straightforward definitions. Observability is a structural property of a control system dened as the possibility to deduce the state of the system from observing its input-output behaviour Identiability is the possibility to identify the parameters of a control system from its input-output behaviour. Parameter identiability is a special case of the observability problem. [1] http://www.math.chalmers.se/Math/Research/Preprints/Doctoral/2007/3.pdf http://www.math.chalmers.se/Math/Research/Preprints/Doctoral...

justincormack 5y ago

Sibling comment is very helpful in terms of what linear is. In terms of the abstract, your system isn't "observable" as even with all the inputs and outputs in a given time period, and knowledge of the hash functions, you still won't be able to work out the internal state. If you had all the inputs since it started you could (assuming it was deterministic and so on) but thats "less observable" in some sense as you need potentially unbounded information. While linear systems are tractable, some nonlinear systems could be tractable too. Software is interesting from this point of view as while its clearly nonlinear, we can create mechanisms to expose otherwise hidden internal state and to control it, although there is generally such a large number of internal states that this is difficult.