Hacker News Reader

Comment by ColinWright | Hacker News Reader

Lots of other commentators are saying that the property of MCs is that they are memory-less, but in fact it's trivial to make a MC have deeper memory: Use tuples.

So if you have observations A, B, C, B, C, A, D, A, ... then you form pairs: (A,B), (B,C), (C,B), (B,C), (C,A), (A,D), (D,A), ...

Each node in the MC is one of these pairs, and (X,Y) -> (Y,Z) if Z is the new state that appears.

The number of states grows very quickly, but if you make the system dynamic then it works fine. This is what you use to randomly generate text using the previous 3 words as a predictor for the next. Then (w0,w1,w2) predicts w3, and your next "state" is (w1,w2,w3).

And so on.

View on HN

As a confused undergrad first learning about random dynamical systems on my own (outside of any classes), this really bothered me. How could the Markov assumption be so powerful when it's clearly trivial to add memory and retain the Markov property?!

After reading through theorems and proofs for dynamical systems theory, and especially considering applications of that theory, I came up with basically two practical take-aways:

1. Complexity matters and the curse of dimensionality is real.

2. All those nice theorems (stability, convergence, splitting, invariance, bifurcations, ...) are stated with respect to a state space and make assumptions about the dynamics on that state space. So if you code up a state space representation that is history-aware with respect to the dynamics you really care about, then:

a) you might lose some theorems that hold for the original process, and

b) you sometimes realize the theorems lose a lot of power when they're telling you something about a tuple of things you care about instead of the actual thing you care about.

If I ever teach people about random dynamical systems, this explanation will come immediately after the definition of a Markov process and I'll continually remind my audience throughout the course. Understanding what goes wrong when a system is "technically" Markovian is probably the best way to obtain a deep intuition. Or at least, it was very helpful to me.

Exactly - even if your process is conceptually a Markov chain, your code doesn't have to explicitly enumerate all of the states.

I used a similar scheme to your example, but with letters for generating a word for http://password.supply

Isn't this like an "auto-regressive feed forward neural net"[0]?

> Instead of making predictions from a state that depends on the entire history, an autoregressive model directly predicts yt using only the k most recent inputs, xt−k+1,…,xt. This corresponds to a strong conditional independence assumption. In particular, a feed-forward model assumes the target only depends on the k most recent inputs. Google’s WaveNet[1] nicely illustrates this general principle.

[0] http://bair.berkeley.edu/blog/2018/08/06/recurrent/

[1] https://arxiv.org/abs/1609.03499

Is this equivalent to each node representing a memory state?

Seems like it would not solve rtkwe's concern. In their example using tuples make a node state equal (S, COUNT_OF_DAYS), (R, COUNT_OF_DAYS)? You would still need an infinite amount of nodes to represent an infinite precision integer state.

You don't store count count of days, each node is the sequence of the previous k states. Usually k=1, but set k=2 and you get something where each state is predicted based on the previous 2 states.

So no, you don't need an infinite amount of memory, it's all still finite (although rapidly gets large).

Reply on news.ycombinator.com