Comment by m-hilgendorf | Hacker News Reader

Comment by m-hilgendorf | Hacker News Reader

Parent Full thread

> will apply to software contexts if one “squints right"

Not just "squint right." All systems can be represented as a pair of functions that map current state to next state and the observation of current state, in response to some perturbation. Aka state evolution/observation.

    F: s_n, x_n -> s_n+1
    G: s_n, x_n -> y_n

Everything from Markov Chains, stochastic processes, ANNs, controls, signal processes, electrical systems, finite automata, Turing machines, etc can all be formulated in those terms. The cool part is when you break apart those specific formulations into the abstract notion of a signal flow graph (a directed graph that represents the operations of F and G) you start thinking a lot about homological algebra, category theory, and the general nature of things.

Abstractions in programming that express this nature cleanly are often the ones that we find the most beautiful, at least for me. For example, an iterator has a void perturbation, F is the next() function, and G is just the observation of the current element (the actual state may be hidden behind a getter of some kind). The abstractions that we build on top of iterators through combinators like map/flatten/fold, etc are then homomorphisms between various iterators by chaining the state evolution/observation functions with other operations.

So if you go one degree higher than an iterator you get a generator, where your perturbation might be non-void. In controls then, you can express your plant and controller (even the "hardware" stages) as one generator composed of smaller ones and combinators across them.

A lot of the math behind this in the general case is kind of heady, at least for me (just an undergrad experience here). There's a lot of ground to be covered in particular understanding for machine learning and other nonlinear dynamical systems where analysis/synthesis of a state-space formulation is currently lacking in formal methods.

> Everything from Markov Chains, stochastic processes, ANNs, controls, signal processes, electrical systems, finite automata, Turing machines, etc can all be formulated in those terms. The cool part is when you break apart those specific formulations into the abstract notion of a signal flow graph (a directed graph that represents the operations of F and G) you start thinking a lot about homological algebra, category theory, and the general nature of things.

Very interesting! Do you have any references where such reformulations are done? Or where control problems are formulated in terms of algebra or category theory?

I'm not really an academic, this is mostly something I read about in bits and pieces. It's my own observation that roughly everything that needs a formal model can be expressed that way, the formulation of those two functions can be pulled out with varying degrees of difficulty.

In controls/linear dynamical systems for example, the canonical forms express it directly [1]. Same goes for anything with a clean state-space representation, like Markov Processes.

The notion of "observation" could also be called "doing something useful with state." For a lot of simple state models, like finite automata, the observation is the identity function.

As for the algebra/category theory, I'm not aware of any formal works that get into it (but also I don't keep up with the literature at that level). It's mentioned by various people (because the work was classified) but Shannon was the first to use topological representations of controls. Mason published these as "signal flow graphs" where multiplication/addition/differentiation/integration operations are represented by the edges and vertices of a directed graph, which he used to derive his famous gain rule [2].

My own interest in the abstract algebra related to this was the fact that the edge of a SFG is a multiplication by a state variable and constant (g * s|z^k) and vertices are summations. SFGs themselves are algebraic structures inside what I understand to be an Abelian group (I'm self taught on this, so forgive terminology/notation).

In the pro-audio niche there's a transform on SFGs called the Topology Preserving Transform and has various derivations (Andy Simper, Will Pirkle, Vadim Zavalishin all have writings on it). It's a fairly manual approach, so about a year ago I wrote an algorithm to do it by reformulating Zavalishin's algebraic derivation [3] as a graph transformation. The interesting bit is that when you look at it that way, the TPT is a homomorphism between Abelian groups (the former in the continuous time, the latter discrete time). At least that's how I understand it.

Anyway, this is mostly my self study. I like the abstraction and it makes composing systems very simple. I'm using these approaches in a Rust crate with some combinators on state evolutions/observations like one would iterators, I find it makes things very composable and elegant [4].

[1] https://www.engr.mun.ca/~millan/Eng6825/canonicals.pdf

[2] https://en.wikipedia.org/wiki/Mason%27s_gain_formula

[3] https://www.native-instruments.com/fileadmin/ni_media/downlo...

[4] https://github.com/m-hilgendorf/dsp64

Ah and yet you are not really an academic :) Loved the comment and the various pointers. Learned a few new things, or at least found the entrance.

> All systems can be represented as a pair of functions that map current state to next state and the observation of current state, in response to some perturbation.

If you are assuming the next state depends on the current state, doesn't this work for only Markov system i.e where you can make predictions for the future based solely on its present state?

There's a whole bunch of systems where this doesn't apply, no?

No, because a Markov process only depends on current state. All Markov processes are stateful systems, but not all stateful systems are Markov processes.

For example, an exponential moving average:

    s_n+1 = a x_n + (1 - a) s_n 
      y_n = s_n

    where a, x, s, y in Reals

The next state depends on all past state, including initial conditions.

Conceptually, stateful systems are the notion "where I am going depends on where I am." Markov processes are stateful systems where "where I am going depends on where I am, but not upon where I came from."

Allowing for hidden state variables, (HMMs) for example, one can expand their reach.

Reply on news.ycombinator.com